tHeapBase Class Reference

#include <tHeap.h>

Inheritance diagram for tHeapBase:

[legend]

Collaboration diagram for tHeapBase:

[legend]

List of all members.

Public Member Functions
	tHeapBase ()
	~tHeapBase ()
Static Public Member Functions
static int	UpperL (int i)
static int	UpperR (int i)
Protected Member Functions
int	Lower (int i)
int	Len () const
tHeapElement *	operator() (int i)
const tHeapElement *	operator() (int i) const
bool	SwapIf (int i, int j)
void	SwapDown (int j)
void	SwapUp (int i)
void	CheckHeap ()
void	Insert (tHeapElement *e)
void	Remove (tHeapElement *e)
tHeapElement *	Remove (int i)
void	Replace (int i)
void	Replace (tHeapElement *e)
Friends
class	tHeapElement

---

Detailed Description

Definition at line 46 of file tHeap.h.

---

Constructor & Destructor Documentation

tHeapBase::tHeapBase

(

)

[inline]

Definition at line 81 of file tHeap.h.

{}

tHeapBase::~tHeapBase

(

)

Definition at line 56 of file tHeap.cpp.

References Len(), and Remove().

{
    while(Len() > 0)
        Remove(0);
}

Here is the call graph for this function:

---

Member Function Documentation

int tHeapBase::Lower

(

int

i

)

[inline, protected]

Definition at line 49 of file tHeap.h.

Referenced by CheckHeap(), Replace(), and SwapDown().

                     { // the element below i in the heap
        if(i%2==0)  // just to make sure what happens; you never know what 1/2 is..
            return i/2-1;
        else
            return (i-1)/2;
    }

Here is the caller graph for this function:

int tHeapBase::Len

(

)

const [inline, protected]

Reimplemented from GrowingArrayBase.

Reimplemented in tHeap< T >, tHeap< nBandwidthArbitrator >, and tHeap< tEvent >.

Definition at line 56 of file tHeap.h.

References GrowingArrayBase::Len().

Referenced by CheckHeap(), Insert(), tHeap< tEvent >::Len(), Remove(), Replace(), SwapUp(), and ~tHeapBase().

{ return tList<tHeapElement>::Len(); }

Here is the call graph for this function:

Here is the caller graph for this function:

tHeapElement* tHeapBase::operator()

(

int

i

)

[inline, protected]

Reimplemented in tHeap< T >, tHeap< nBandwidthArbitrator >, and tHeap< tEvent >.

Definition at line 57 of file tHeap.h.

References tArray< T *, MALLOC >::operator()().

Referenced by CheckHeap(), tHeap< tEvent >::Events(), tHeap< tEvent >::operator()(), Remove(), and SwapIf().

{ return const_cast< tHeapElement* >( tList<tHeapElement>::operator()(i) ); }

Here is the call graph for this function:

Here is the caller graph for this function:

const tHeapElement* tHeapBase::operator()

(

int

i

)

const [inline, protected]

Reimplemented from tArray< tHeapElement *, false >.

Reimplemented in tHeap< T >, tHeap< nBandwidthArbitrator >, and tHeap< tEvent >.

Definition at line 58 of file tHeap.h.

References tArray< T *, MALLOC >::operator()().

{ return tList<tHeapElement>::operator()(i); }

Here is the call graph for this function:

bool tHeapBase::SwapIf	(	int	i,
		int	j
	)			[protected]

Definition at line 37 of file tHeap.cpp.

References tHeapElement::hID, operator()(), Swap(), tASSERT, and tHeapElement::Val().

Referenced by SwapDown(), and SwapUp().

{
    if (i==j || i<0) return false; // safety

    tHeapElement *e1=operator()(i),*e2=operator()(j);

    tASSERT( e1->hID == i );
    tASSERT( e2->hID == j );

    if (e1->Val() > e2->Val()){
        Swap(tList< tHeapElement >::operator()(i),tList< tHeapElement >::operator()(j));
        e1->hID=j;
        e2->hID=i;
        return true;
    }
    else
        return false;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void tHeapBase::SwapDown

(

int

j

)

[protected]

Definition at line 79 of file tHeap.cpp.

References CheckHeap(), Lower(), and SwapIf().

Referenced by Insert(), and Replace().

                             {
    int i=j;
    // e is now at position i. swap it down
    // as far as it goes:
    do{
        j=i;
        i=Lower(j);
    }
    while(SwapIf(i,j)); // mean: relies on the fact that SwapIf returns -1
    // if i<0.

#ifdef EVENT_DEB
    CheckHeap();
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

void tHeapBase::SwapUp

(

int

i

)

[protected]

Definition at line 95 of file tHeap.cpp.

References CheckHeap(), Len(), SwapIf(), UpperL(), and UpperR().

Referenced by Replace().

                           {
#ifdef EVENT_DEB
    //  static int su=0;
    //  if (su%100 ==0 )
    //    con << "su=" << su << '\n';
    //  if (su > 11594 )
    // con << "su=" << su << '\n';
    //  su ++;
#endif

    int ul,ur;
    bool goon=1;
    while(goon && UpperL(i)<Len()){
        ul=UpperL(i);
        ur=UpperR(i);
        if(ur>=Len() ||
                operator()(ul)->Val() < operator()(ur)->Val() ){
            goon=SwapIf(i,ul);
            i=ul;
        }
        else{
            goon=SwapIf(i,ur);
            i=ur;
        }
    }

#ifdef EVENT_DEB
    CheckHeap();
#endif

}

Here is the call graph for this function:

Here is the caller graph for this function:

void tHeapBase::CheckHeap

(

)

[protected]

Definition at line 63 of file tHeap.cpp.

References tHeapElement::hID, Len(), Lower(), operator()(), tERR_ERROR_INT, UpperL(), UpperR(), and tHeapElement::Val().

Referenced by Insert(), Remove(), Replace(), SwapDown(), SwapUp(), and tEventQueue::Timestep().

                         {
    for(int i=Len()-1;i>0;i--){
        tHeapElement *current=operator()(i);
        tHeapElement *low=operator()(Lower(i));
        if (Lower(UpperL(i))!=i || Lower(UpperR(i))!=i)
            tERR_ERROR_INT("Error in lower/upper " << i << "!");

        if (low->Val() > current->Val() )
            tERR_ERROR_INT("Heap structure corrupt!");

        if ( current->hID != i )
            tERR_ERROR_INT("Heap list structure corrupt!");
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void tHeapBase::Insert

(

tHeapElement *

e

)

[protected]

Definition at line 127 of file tHeap.cpp.

References tList< tHeapElement >::Add(), CheckHeap(), tHeapElement::hID, Len(), SwapDown(), and tASSERT.

Referenced by tHeap< tEvent >::Insert(), and tHeapElement::SetVal().

                                     {
#ifdef EVENT_DEB
    CheckHeap();
#endif

    Add(e,e->hID); // relies on the implementation of List: e is
    // put to the back of the heap.
    tASSERT(e->hID == Len()-1);
    SwapDown(Len()-1);  // bring it to the right place

#ifdef EVENT_DEB
    CheckHeap();
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

void tHeapBase::Remove

(

tHeapElement *

e

)

[protected]

Reimplemented from tList< tHeapElement >.

Definition at line 142 of file tHeap.cpp.

References CheckHeap(), tHeapElement::Heap(), tHeapElement::hID, tERR_ERROR_INT, and tERR_WARN.

Referenced by tHeap< tEvent >::Remove(), tHeapElement::RemoveFromHeap(), and ~tHeapBase().

                                     {
    int i=e->hID;

#ifdef EVENT_DEB
    CheckHeap();
#endif

    // element
    if(i<0 )
    {
#ifdef DEBUG
        static bool warn = true;
        if ( warn )
        {
            tERR_WARN("Element to be removed from heap was already removed. Unless there is a fatal exit in process, this is not right.");
            warn=false;
        }
#endif
        return;
    }

    if( this != e->Heap())
        tERR_ERROR_INT("Element is not in this heap! (Note: this usually is a followup error when the system fails to recover from another error. When reporting, please also include whatever happened before this.)");

    Remove(i);

#ifdef EVENT_DEB
    CheckHeap();
#endif
}

Here is the call graph for this function:

Here is the caller graph for this function:

tHeapElement * tHeapBase::Remove

(

int

i

)

[protected]

Reimplemented in tHeap< T >, tHeap< nBandwidthArbitrator >, and tHeap< tEvent >.

Definition at line 199 of file tHeap.cpp.

References CheckHeap(), tHeapElement::hID, Len(), NULL, operator()(), tList< T, MALLOC, REFERENCE >::Remove(), Replace(), and tASSERT.

                                     {
#ifdef EVENT_DEB
    CheckHeap();
#endif

    if (i>=0 && i<Len())
    {
        tHeapElement *ret=operator()(i);

        tASSERT( ret->hID == i );

        tList<tHeapElement>::Remove(ret,ret->hID);

        // now we have an misplaced element at pos i. (if i was not at the end..)
        if (i<Len())
            Replace(i);

#ifdef EVENT_DEB
        CheckHeap();
#endif

        return ret;
    }
    return NULL;
}

Here is the call graph for this function:

void tHeapBase::Replace

(

int

i

)

[protected]

Definition at line 173 of file tHeap.cpp.

References CheckHeap(), Len(), Lower(), SwapDown(), and SwapUp().

Referenced by Remove(), tHeap< tEvent >::Replace(), Replace(), and tHeapElement::SetVal().

                            {
    if (i>=0 && i < Len()){
        if (i==0 || operator()(i)->Val() > operator()(Lower(i))->Val() )
            SwapUp(i);          // put it up where it belongs
        else
            SwapDown(i);

#ifdef EVENT_DEB
        CheckHeap();
#endif
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void tHeapBase::Replace

(

tHeapElement *

e

)

[protected]

Definition at line 186 of file tHeap.cpp.

References CheckHeap(), tHeapElement::hID, Replace(), and tERR_ERROR_INT.

                                      {
    int i=e->hID;

    if(i<0 || this != e->Heap())
        tERR_ERROR_INT("Element is not in this heap! (Note: this usually is a followup error when the system fails to recover from another error. When reporting, please also include whatever happened before this.)");

    Replace(i);

#ifdef EVENT_DEB
    CheckHeap();
#endif
}

Here is the call graph for this function:

static int tHeapBase::UpperL

(

int

i

)

[inline, static]

Definition at line 78 of file tHeap.h.

Referenced by CheckHeap(), draw_eWall(), and SwapUp().

{return 2*i+1;} // the elements left and

Here is the caller graph for this function:

static int tHeapBase::UpperR

(

int

i

)

[inline, static]

Definition at line 79 of file tHeap.h.

Referenced by CheckHeap(), draw_eWall(), and SwapUp().

{return 2*i+2;} // right above i

Here is the caller graph for this function:

---

Friends And Related Function Documentation

friend class tHeapElement [friend]

Definition at line 47 of file tHeap.h.

---

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

• src/tools/tHeap.h
• src/tools/tHeap.cpp

---