heap_rep< C > Class Template Reference

#include <heap.hpp>

Inheritance diagram for heap_rep< C >:

List of all members.

Public Member Functions

• heap_rep (comparison compare2)
• heap_rep (C *a2, nat n2, nat l2, comparison compare2)
• ~heap_rep ()
• 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 ()

Public Attributes

• MMX_ALLOCATORS int ref_count

Friends

• class heap< C >
• heap< C > copy (const heap< C > &h)
• void set_top (heap< C > &h, const C &x)
• C get_top (const heap< C > &h)
• void push (heap< C > &h, const C &x)
• C pull (heap< C > &h)
• nat N (const heap< C > &h)

---

Detailed Description

template<typename C>
class mmx::heap_rep< C >

Definition at line 39 of file heap.hpp.

---

Constructor & Destructor Documentation

heap_rep

(

comparison

compare2

)

[inline]

heap_rep	(	C *	a2,
		nat	n2,
		nat	l2,
		comparison	compare2
	)			[inline]

~heap_rep

(

)

[inline]

---

Member Function Documentation

void correct_downwards

(

)

[inline]

Definition at line 117 of file heap.hpp.

References mmx::swap().

Referenced by heap_rep< C >::Pull(), and heap_rep< C >::Set_top().

                             {
  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;
      }
    }
  }
}

void correct_upwards

(

)

[inline]

Definition at line 143 of file heap.hpp.

References mmx::swap().

Referenced by heap_rep< C >::Push().

                           {
  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;
    }
  }
}

C Get_top

(

)

const [inline]

Definition at line 163 of file heap.hpp.

References ASSERT.

                         {
  ASSERT (n>0, "non-empty heap expected");
  return a[0];
}

C Pull

(

)

[inline]

Definition at line 176 of file heap.hpp.

References ASSERT, mmx::C, heap_rep< C >::correct_downwards(), and heap_rep< C >::resize().

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

void Push

(

const C &

x

)

[inline]

Definition at line 169 of file heap.hpp.

References heap_rep< C >::correct_upwards(), and heap_rep< C >::resize().

                          {
  resize (n+1);
  a[n-1]= x;
  correct_upwards ();
}

void resize

(

nat

n2

)

[inline]

Definition at line 103 of file heap.hpp.

References mmx::C, mmx::min(), and n.

Referenced by heap_rep< C >::Pull(), and heap_rep< C >::Push().

                        {
  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;
}

void Set_top

(

const C &

x

)

[inline]

Definition at line 156 of file heap.hpp.

References ASSERT, and heap_rep< C >::correct_downwards().

                             {
  ASSERT (n>0, "non-empty heap expected");
  a[0]= x;
  correct_downwards ();
}

---

Friends And Related Function Documentation

heap<C> copy

(

const heap< C > &

h

)

[friend]

Definition at line 247 of file heap.hpp.

                     {
  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);
}

C get_top

(

const heap< C > &

h

)

[friend]

Definition at line 187 of file heap.hpp.

                                      {
  return h.rep->Get_top (); }

friend class heap< C > [friend]

Definition at line 62 of file heap.hpp.

nat N

(

const heap< C > &

h

)

[friend]

Definition at line 193 of file heap.hpp.

                                  {
  return l.rep->n; }

C pull

(

heap< C > &

h

)

[friend]

Definition at line 191 of file heap.hpp.

                             {
  h.secure(); return h.rep->Pull (); }

void push	(	heap< C > &	h,
		const C &	x
	)			[friend]

Definition at line 189 of file heap.hpp.

                                            {
  h.secure(); h.rep->Push (x); }

void set_top	(	heap< C > &	h,
		const C &	x
	)			[friend]

Definition at line 185 of file heap.hpp.

                                               {
  h.secure(); h.rep->Set_top (x); }

---

Member Data Documentation

MMX_ALLOCATORS int ref_count [inherited]

Definition at line 164 of file basix.hpp.

---

The documentation for this class was generated from the following file:

• include/basix/heap.hpp