Logo Search packages:      
Sourcecode: u++ version File versions

uHeap.h

//                              -*- Mode: C++ -*- 
// 
// uC++ Version 5.0.1, Copyright (C) Peter A. Buhr 2000
// 
// uHeap.h -- generic heap data structure
// 
// Author           : Ashif S. Harji
// Created On       : Tue Jun 20 11:12:58 2000
// Last Modified By : Peter A. Buhr
// Last Modified On : Fri Aug 13 16:51:37 2004
// Update Count     : 44
//
// This  library is free  software; you  can redistribute  it and/or  modify it
// under the terms of the GNU Lesser General Public License as published by the
// Free Software  Foundation; either  version 2.1 of  the License, or  (at your
// option) any later version.
// 
// This library is distributed in the  hope that it will be useful, but WITHOUT
// ANY  WARRANTY;  without even  the  implied  warranty  of MERCHANTABILITY  or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
// for more details.
// 
// You should  have received a  copy of the  GNU Lesser General  Public License
// along  with this library.
// 

#ifndef __HEAP_H__
#define __HEAP_H__

#pragma __U_NOT_USER_CODE__


#include <uC++.h>
#include <uAssert.h>
//#include <uDebug.h>


template<class KeyType, class DataType> class uHeapable {
  public:
    KeyType key;
    DataType data;
    uHeapable() {};
    uHeapable( KeyType key, DataType data ) : key( key ), data( data ) {};
}; // uHeapable


// array size a compile time constant => allocate space within the object
template<class KeyType, class DataType, int MaxSize> class uHeapArray {
    uHeapable<KeyType, DataType> A[ MaxSize ];
  public:
    uHeapArray() {}

    uHeapArray( int size ) {
      uAssert( size <= MaxSize );
    } // uHeapArray::uHeapArray

    uHeapable< KeyType, DataType > &operator[]( int index ) {
      return A[ index - 1 ];
    } // uHeapArray::operator[]
}; // uHeapArray


template<class T> class uFlexArray;             // forward declaration

// array size not a compile time constant => use flexible array
template<class KeyType, class DataType> class uHeapArray<KeyType, DataType, 0> {
    uFlexArray< uHeapable<KeyType, DataType> > A;
  public:
    uHeapArray() {}
    uHeapArray( int size ) : A( size ) {}

    uHeapable< KeyType, DataType > &operator[]( int index ) {
      A.reserve( index );                       // ensure sufficient space allocated
      return A[ index - 1 ];
    } // uHeapArray::operator[]
}; // uHeapArray


// Heap is generic in the type of elements stored in the heap and the maximum
// number of elements that can be stored in the heap.  Specifying 0 for MaxSize
// allows the heap to grow dynamically

template<class KeyType, class DataType, int MaxSize = 0> class uHeap {
#ifdef DEBUG_SHOW_COUNT
    int NumCompares, NumExchg, NumTransfers, NumHeapifies;
#endif
    int maxSize, heapSize, cursor;
    int (*compare)( KeyType, KeyType );
    void (*exchange)( uHeapable<KeyType,DataType> &, uHeapable<KeyType,DataType> & );
  public:
    uHeapArray<KeyType,DataType,MaxSize> A;     // do not use A[0], valid subscripts are 1..MaxSize
  private:
    int parent( int i ) {
      return i >> 1;
    } // uHeap::parent
    
    int left( int i ) {
      return i << 1;
    } // uHeap::left
    
    int right( int i ) {
      return i << 1 | 1;
    } // uHeap::right
    
    static void defaultExchange( uHeapable<KeyType,DataType> &x, uHeapable<KeyType,DataType> &y ) {
      uHeapable<KeyType,DataType> temp = x;
      x = y;   
      y = temp;
#ifdef DEBUG_SHOW_COUNT
      NumExchg += 1;
#endif
    } // uHeap::defaultExchange

    void init1( int (*compare)( KeyType, KeyType ), void (*exchange)( uHeapable<KeyType,DataType> &, uHeapable<KeyType,DataType> & ), int size ) {
      uHeap::compare = compare;
      uHeap::exchange = exchange;
      maxSize = size;
      heapSize = 0;
      cursor = 1;
#ifdef DEBUG_SHOW_COUNT
      NumCompares = NumExchg = NumTransfers = NumHeapifies = 0;
#endif
    } // uHeap::init1
    
    void init2( int (*compare)( KeyType, KeyType ), void (*exchange)( uHeapable<KeyType,DataType> &, uHeapable<KeyType,DataType> & ), int size,
            uHeapable<KeyType,DataType> a[], int n ) {
#ifdef __U_DEBUG__
      uAssert( n <= maxSize );
#endif // __U_DEBUG__
      
      uHeap::compare = compare;
      uHeap::exchange = exchange;
      for ( int i = 0; i < n; i += 1 ) {
          A[i + 1] = a[i];
      } // for
      maxSize = size;
      heapSize = n;
      buildHeap();
      cursor = 1;
#ifdef DEBUG_SHOW_COUNT
      NumCompares = NumExchg = NumTransfers = NumHeapifies = 0;
#endif
    } // uHeap::init2
  public:
    uHeap( int (*compare)( KeyType, KeyType ), int size = MaxSize ) : A( size ) {
#ifdef __U_DEBUG__
      uAssert( MaxSize == 0 );                  // assumes that storage for heap is allocated in an external arena
#endif // __U_DEBUG__
      init1( compare, defaultExchange, size );
    } // uHeap::uHeap

    uHeap( int (*compare)( KeyType, KeyType ), void (*exchange)( uHeapable<KeyType,DataType> &, uHeapable<KeyType,DataType> & ) ) {
#ifdef __U_DEBUG__
      uAssert( MaxSize > 0 );
#endif // __U_DEBUG__
      init1( compare, exchange, MaxSize );
    } // uHeap::uHeap

    uHeap( int (*compare)( KeyType, KeyType ), void (*exchange)( uHeapable<KeyType,DataType> &, uHeapable<KeyType,DataType> & ), int size ) : A( size ) {
#ifdef __U_DEBUG__
      uAssert( MaxSize > 0 );
#endif // __U_DEBUG__
      init1( compare, exchange, size );
    } // uHeap::uHeap
    
    uHeap( int (*compare)( KeyType, KeyType ), uHeapable<KeyType,DataType> a[], int n, int size = MaxSize ) : A( size ) {
#ifdef __U_DEBUG__
      uAssert( MaxSize > 0 );
#endif // __U_DEBUG__
      init2( compare, defaultExchange, size, a, n );
    } // uHeap::uHeap
    
    uHeap( int (*compare)( KeyType, KeyType ), uHeapable<KeyType,DataType> a[], int n, void (*exchange)( uHeapable<KeyType,DataType> &, uHeapable<KeyType,DataType> & ) ) {
#ifdef __U_DEBUG__
      uAssert( MaxSize > 0 );
#endif // __U_DEBUG__
      init2( compare, exchange, MaxSize, a, n );
    } // uHeap::uHeap
    
    uHeap( int (*compare)( KeyType, KeyType ), uHeapable<KeyType,DataType> a[], int n,
         int size, void (*exchange)( uHeapable<KeyType,DataType> &, uHeapable<KeyType,DataType> & ) ) : A( size ) {
#ifdef __U_DEBUG__
      uAssert( MaxSize == 0 );                  // assumes that storage for heap is allocated in an external arena
#endif // __U_DEBUG__
      init2( compare, exchange, size, a, n );
    } // uHeap::uHeap

#ifdef DEBUG_SHOW_COUNT
    void display_counts() {
      uCerr << uAcquire;
      uCerr << "Heap::~Heap() - Total Number of Compare Operations = " << NumCompares << "\n";
      uCerr << "Heap::~Heap() - Total Number of Exchange Operations = " << NumExchg << "\n";
      uCerr << "Heap::~Heap() - Total Number of Transfer Operations = " << NumTransfers << "\n";
      uCerr << "Heap::~Heap() - Total Number of Heapify Operations = " << NumHeapifies << "\n";
      uCerr << uRelease;
    } // uHeap::display_counts
    
    void accumulate_counts( int &C, int &E, int &T, int &H ) {
      C += NumCompares;
      E += NumExchg;
      T += NumTransfers;
      H += NumHeapifies;
    } // uHeap::accumulate_counts
#endif

    int size() const {                          // heap size
      return heapSize;
    } // uHeap::size

    void getRoot( uHeapable<KeyType,DataType> &root ) {
      root = A[1];
#ifdef DEBUG_SHOW_COUNT
      NumTransfers += 1;
#endif
    } // uHeap::getRoot
    
    void deleteInsert( KeyType new_key, DataType new_data ) { // remove root element
#ifdef __U_DEBUG__
      uAssert( heapSize > 0 );
#endif // __U_DEBUG__
      
      A[1].key = new_key;
      A[1].data = new_data;
#ifdef DEBUG_SHOW_COUNT
      NumTransfers += 1;
#endif
      heapify( 1 );
    } // uHeap::deleteInsert

    void deleteRoot() {                         // remove root element
#ifdef __U_DEBUG__
      uAssert( heapSize > 0 );
#endif // __U_DEBUG__
      
      exchange( A[1], A[size()] );
#ifdef DEBUG_SHOW_COUNT
      NumTransfers += 1;
#endif
      heapSize -= 1;
      heapify( 1 );
    } // uHeap::extractRoot

    void deletenode( uHeapable<KeyType,DataType> &node ) {
      exchange( node, A[size()] );
      heapSize -= 1;
      heapify( 1 );
    } // uHeap::deletenode

    void insert( KeyType key, DataType data ) {       // insert element into heap
#ifdef __U_DEBUG__
      uAssert( heapSize < maxSize || maxSize == 0 );
#endif // __U_DEBUG__
      
      heapSize += 1;
      A[heapSize].key = key;
      A[heapSize].data = data;
      for ( int i = heapSize; i > 1 && compare( A[parent( i )].key, key ) == -1; exchange( A[i], A[parent( i )] ), i = parent( i ) ) {
#ifdef DEBUG_SHOW_COUNT
          NumTransfers += 1;
          NumCompares += 1;
#endif
      } // for
#ifdef DEBUG_SHOW_COUNT
      NumCompares += 1;
      NumTransfers += 1;
#endif
    } // uHeap::insert

    void insert_last( KeyType key, DataType data ) {
#ifdef __U_DEBUG__
      uAssert( heapSize < maxSize || maxSize == 0 );
#endif // __U_DEBUG__
      
      heapSize += 1;
#ifdef DEBUG_SHOW_COUNT
      NumTransfers += 1;
#endif
      A[heapSize].key = key;
      A[heapSize].data = data;
    } // uHeap::insert
    
    DataType find( KeyType key ) {              // find if element is in heap
      for ( int i = 1; i <= heapSize; i += 1 ) {
         if ( compare( A[i].key, key ) == 0 ) return A[i].data;
      } // for

      return( (DataType)NULL );
    } // uHeap::find

    void sort() {
      int last, saveHeapSize = heapSize;
      
      for ( last = heapSize; last >= 2; last -= 1 ) {
          uHeapable<KeyType,DataType> saveA1 = A[1];  // save A[1]

          int h = pullDown( 1 );                // let the hole at A[1] fall to the bottom
          // put A[last] in the hole at the bottom and bubble up
          if ( h < last ) {
#ifdef DEBUG_SHOW_COUNT
            NumCompares += 1;
            NumTransfers += 1;
#endif
            for ( exchange( A[h], A[last] );
                 h > 1 && compare( A[parent(h)].key, A[h].key) == -1;
                 exchange( A[h],A[parent( h)]), h=parent( h)) {
#ifdef DEBUG_SHOW_COUNT
                NumCompares += 1;
#endif
            }
          }
          A[last] = saveA1;                     // put the earlier saved A[1] at vacated last
          heapSize -= 1;
#ifdef DEBUG_SHOW_COUNT
          NumTransfers += 2;
#endif
      } // for
      heapSize = saveHeapSize;
    } // uHeap::sort
  private:
    int pullDown( int j ) {
      // There is a hole at the top of the heap rooted at j make the hole
      // move down to the last level by moving the children up

      int  larger;
      for ( int i = j; ; i = larger) {
          int l, r;

          l = left( i );
          if ( l > size() ) return i;                 // i has no children; return
          r = right( i );
            
          // find the position of the largee of the 2 (or 1) children
          larger = l;
          if ( r <= size() ) {
            if ( compare( A[r].key, A[larger].key ) != -1 )
                larger = r;
#ifdef DEBUG_SHOW_COUNT
            NumCompares += 1;
#endif
          } // if
            
          exchange( A[i], A[larger] ); 
            
#ifdef DEBUG_SHOW_COUNT
          NumTransfers += 1;
          NumHeapifies += 1;
#endif
      } // for
    } // uHeap::pullDown
    
    void heapify( int j ) {
      int  largest;
      for ( int i = j; ; i = largest ) {
          int l, r;

          l = left( i );
        if ( l > size() ) break;
          r = right( i );

          // find the position of the largest of the 3 values

#ifdef DEBUG_SHOW_COUNT
          NumCompares += 1;
#endif
          if ( compare( A[l].key, A[i].key ) == 1) 
            largest = l;
          else
            largest = i;

          if ( r <= size() ) {
            if ( compare( A[r].key, A[largest].key ) == 1)
                largest = r;
#ifdef DEBUG_SHOW_COUNT
            NumCompares += 1;
#endif
          } // if
#ifdef DEBUG_SHOW_COUNT
          NumHeapifies += 1;
#endif
        if ( largest == i ) break;
          exchange( A[i], A[largest] );
      } // for
    } // uHeap::heapify
  public:
    void buildHeap() {
      for ( int i = heapSize >> 1; i >= 1; i -= 1 ) {
          heapify( i );
      } // for
    } // uHeap::buildHeap
}; // uHeap


template<class KeyType, class DataType, int MaxSize> class uHeapPtrSort {
  public:
    uHeapPtrSort( uHeap<KeyType,DataType,MaxSize> *h, DataType DataRecords, DataType tempRecPtr ) {
      sortRecs( h, DataRecords, tempRecPtr );
    } // uHeapPtrSort::uHeapPtrSort
    
    // assumes DataType is a pointer to records and that the heap is already sorted
    // arranges the data records pointed to by DataType in the same order as that in
    // the heap...
    // IMPORTANT: this is destructive - wipes out the Data fields in the heap...
    // The records are assumed to be to stored in array DataRecords.
    // Algorithm based on discussions with Anna Lubiw/Ian Munro - akg
    
    void sortRecs( uHeap<KeyType,DataType,MaxSize> *h, DataType DataRecords, DataType tempRecPtr ) {
#ifdef DEBUG_SHOW_COUNT
      int recsMoved = 0;
#endif
      // let's convert DataType pointers into indices into DataRecords for simplicity.
      for ( int i = 1; i <= h->heapSize; i += 1 ) {
          *((int *)&(h->A[i].data)) = h->A[i].data - DataRecords;
      } // for

      for ( int cycleStart = 1; cycleStart <= h->heapSize; cycleStart += 1 ) {
          if ( (int)h->A[cycleStart].data != 0) {
            if ( (int)h->A[cycleStart].data == cycleStart ) {
                h->A[cycleStart].data = 0;
            } else {
                int current = cycleStart;
                *tempRecPtr = DataRecords[current];
#ifdef DEBUG_SHOW_COUNT
                recsMoved += 1;
#endif
                for ( ;; ) {
                  int next = (int)h->A[current].data;
                  h->A[current].data = 0;
                  if ( next == cycleStart) break;

                  DataRecords[current] = DataRecords[next];
#ifdef DEBUG_SHOW_COUNT
                  recsMoved += 1;
#endif
                  current = next;
                } // for
                DataRecords[current] = *tempRecPtr;
#ifdef DEBUG_SHOW_COUNT
                recsMoved += 1;
#endif
            } // if
          } // if
      } // for
#ifdef DEBUG_SHOW_COUNT
      // uCerr << uAcquire << "Total Records Moved = " << recsMoved << "\n" << uRelease;
#endif
    } // uHeapPtrSort::sortRecs
};

#endif


// Local Variables: //
// compile-command: "gmake install" //
// End: //

Generated by  Doxygen 1.6.0   Back to index