/Users/mourrain/Devel/mmx/basix/include/basix/heap.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : heap.hpp
* DESCRIPTION: Ordered heaps
* COPYRIGHT  : (C) 2005  Joris van der Hoeven
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#ifndef __MMX_HEAP_HPP
#define __MMX_HEAP_HPP
#include <basix/vector.hpp>


namespace mmx {
#define TMPL_DEF template<typename C>
#define TMPL template<typename C>
#define Heap heap<C>
#define Heap_rep heap_rep<C>

TMPL class heap_rep;
TMPL class heap;
TMPL Heap copy (const Heap& h);
TMPL inline void set_top (Heap& h, const C& x);
TMPL inline C    get_top (const Heap& h);
TMPL inline void push (Heap& h, const C& x);
TMPL inline C    pull (Heap& h);
TMPL inline nat  N (const Heap& h);

/******************************************************************************
* Heap class and its representation class
******************************************************************************/

TMPL_DEF
class heap_rep REP_STRUCT {
  typedef bool (*comparison) (const C&, const C&);
  comparison compare;

  C*  a;  // entries of heap
  nat n;  // dimension of heap
  nat l;  // allocated number of entries

public:
  inline Heap_rep (comparison compare2):
    compare (compare2), a (mmx_new<C> (0)), n (0), l (0) {}
  inline Heap_rep (C* a2, nat n2, nat l2, comparison compare2):
    compare (compare2), a (a2), n (n2), l (l2) {}
  inline ~Heap_rep () { mmx_delete<C> (a, l); }

  void resize (nat n2);
  void correct_downwards ();
  void correct_upwards ();
  void Set_top (const C& x);
  C    Get_top () const;
  void Push (const C& x);
  C    Pull ();

  friend class Heap;
  friend Heap copy    LESSGTR (const Heap& h);
  friend void set_top LESSGTR (Heap& h, const C& x);
  friend C    get_top LESSGTR (const Heap& h);
  friend void push    LESSGTR (Heap& h, const C& x);
  friend C    pull    LESSGTR (Heap& h);
  friend nat  N       LESSGTR (const Heap& h);
};


TMPL_DEF
class heap {
INDIRECT_PROTO_1 (heap, heap_rep, C)
  typedef bool (*comparison) (const C&, const C&);
  inline heap (C* a, nat n, nat l, comparison compare):
    rep (new Heap_rep (a, n, l, compare)) {}

public:
  inline heap (comparison compare):
    rep (new Heap_rep (compare)) {}
  heap (const iterator<C>& it, comparison compare):
    rep (new Heap_rep (compare)) {
      while (busy (it)) { rep->Push (*it); ++it; } }
  inline C operator [] (nat i) const {
    ASSERT (i < rep->n, "out of range");
    return rep->a[i]; }

  friend Heap copy    LESSGTR (const Heap& h);
  friend void set_top LESSGTR (Heap& h, const C& x);
  friend C    get_top LESSGTR (const Heap& h);
  friend void push    LESSGTR (Heap& h, const C& x);
  friend C    pull    LESSGTR (Heap& h);
  friend nat  N       LESSGTR (const Heap& h);
};
INDIRECT_IMPL_1 (heap, heap_rep, typename C, C)

/******************************************************************************
* Fundamental operations on heaps
******************************************************************************/

TMPL void 
Heap_rep::resize (nat n2) {
  if (n2 > l || n2 < ((l+1)>>1)) {
    nat l2= (((n2 < ((l+1)>>1)) || (n2 > (l<<1))) ? n2: l<<1);
    C* b= mmx_new<C> (l2);
    nat nn= min (n, n2);
    for (nat i=0; i<nn; i++) b[i]= a[i];
    mmx_delete<C> (a, l);
    a= b;
    l= l2;
  }
  n= n2;
}

TMPL void 
Heap_rep::correct_downwards () {
  nat i= 0;
  while (true) {
    nat l= (i<<1) + 1, r= l+1;
    if (l >= n) break;
    if (compare (a[i], a[l])) {
      if (r >= n || compare (a[i], a[r])) break;
      else {
        swap (a[i], a[r]);
        i= r;
      }
    }
    else {
      if (r >= n || compare (a[i], a[r]) || compare (a[l], a[r])) {
        swap (a[i], a[l]);
        i= l;
      }
      else {
        swap (a[i], a[r]);
        i= r;
      }
    }
  }
}

TMPL void 
Heap_rep::correct_upwards () {
  nat i= n-1;
  while (i>0) {
    nat u= (i-1) >> 1;
    if (compare (a[u], a[i])) break;
    else {
      swap (a[u], a[i]);
      i= u;
    }
  }
}

TMPL void
Heap_rep::Set_top (const C& x) {
  ASSERT (n>0, "non-empty heap expected");
  a[0]= x;
  correct_downwards ();
}

TMPL C
Heap_rep::Get_top () const {
  ASSERT (n>0, "non-empty heap expected");
  return a[0];
}

TMPL void
Heap_rep::Push (const C& x) {
  resize (n+1);
  a[n-1]= x;
  correct_upwards ();
}

TMPL C
Heap_rep::Pull () {
  ASSERT (n>0, "non-empty heap expected");
  C r = a[0];
  a[0]= a[n-1];
  resize (n-1);
  correct_downwards ();
  return r;
}

TMPL inline void set_top (Heap& h, const C& x) {
  h.secure(); h.rep->Set_top (x); }
TMPL inline C get_top (const Heap& h) {
  return h.rep->Get_top (); }
TMPL inline void push (Heap& h, const C& x) {
  h.secure(); h.rep->Push (x); }
TMPL inline C pull (Heap& h) {
  h.secure(); return h.rep->Pull (); }
TMPL inline nat N (const Heap& l) {
  return l.rep->n; }

TMPL inline Heap& operator << (Heap& h, const C& x) {
  push (h, x); return h; }
TMPL inline Heap& operator >> (Heap& h, C& x) {
  x= pull (h); return h; }

/******************************************************************************
* Heap iteration
******************************************************************************/

TMPL_DEF
class heap_iterator_rep: public iterator_rep<C> {
  Heap h;  // the heap to traverse
protected:
  bool is_busy () { return N(h) != 0; }
  void advance () { (void) pull (h); }
  C current () { return get_top (h); }
public:
  heap_iterator_rep (const Heap& h2): h (copy (h2)) {}
};

TMPL iterator<C>
iterate (const Heap& h) {
  return iterator<C> (new heap_iterator_rep<C> (h));
}

/******************************************************************************
* Common operations on heaps
******************************************************************************/

template<typename Op, typename C> nat
unary_hash (const Heap& HH) {
  Heap H= copy (HH);
  register nat h= 2531648;
  while (N(H) > 0)
    h= (h<<1) ^ (h<<5) ^ (h>>27) ^ Op::op (pull (H));
  return h;
}

template<typename Op, typename C> bool
binary_test (const Heap& h1b, const Heap& h2b) {
  if (N(h1b) != N(h2b)) return false;
  Heap h1= copy (h1b), h2= copy (h2b);
  while (N(h1) > 0)
    if (Op::not_op (pull (h1), pull (h2))) return false;
  return true;
}

TRUE_IDENTITY_OP_SUGAR(TMPL,Heap)
EXACT_IDENTITY_OP_SUGAR(TMPL,Heap)

TMPL Heap
copy (const Heap& h) {
  C* b= mmx_new<C> (h->l);
  for (nat i=0; i<h->n; i++) b[i]= h->a[i];
  return Heap (b, h->n, h->l, h->compare);
}

TMPL syntactic
flatten (const Heap& h) {
  return flatten (syntactic ("heap"), iterate (h));
}

TMPL
struct binary_helper<Heap >: public void_binary_helper<Heap > {
  static inline string short_type_name () {
    return "H" * Short_type_name (C); }
  static inline generic full_type_name () {
    return gen ("Heap", Full_type_name (C)); }
  static inline nat size (const Heap& v) {
    return N(v); }
  static inline generic access (const Heap& v, nat i) {
    return as<generic> (v[i]); }
  static inline generic disassemble (const Heap& v) {
    vector<generic> r;
    for (nat i=0; i<N(v); i++) r << as<generic> (v[i]);
    return as<generic> (r); }
  static inline Heap assemble (const generic& x) {
    Heap h;
    vector<generic> v= as<vector<generic> > (x);
    for (nat i=0; i<N(v); i++) push (h, v[i]);
    return h; }
  static inline void write (const port& out, const Heap& h) {
    binary_write<nat> (out, N(h));
    Heap c= copy (h);
    for (nat i=0; i<N(h); i++)
      binary_write<C> (out, pull (c)); }
  static inline Heap read (const port& in) {
    nat n= binary_read<nat> (in);
    Heap h;
    for (nat i=0; i<n; i++)
      push (h, binary_read<C> (in));
    return h; }
};

#undef TMPL_DEF
#undef TMPL
#undef Heap
#undef Heap_rep
} // namespace mmx
#endif // __MMX_HEAP_HPP