home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / nihcl-3.0 / lib / Heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-19  |  3.0 KB  |  99 lines
  1. #ifndef    HEAP_H
  2. #define    HEAP_H
  3.  
  4. /*$Header: /afs/alw.nih.gov/unix/sun4_40c/usr/local/src/nihcl-3.0/share/lib/RCS/Heap.h,v 3.0 90/05/20 00:19:43 kgorlen Rel $*/
  5.  
  6. /* Heap.h -- declarations for abstract heap          
  7.  
  8.     THIS SOFTWARE FITS THE DESCRIPTION IN THE U.S. COPYRIGHT ACT OF A
  9.     "UNITED STATES GOVERNMENT WORK".  IT WAS WRITTEN AS A PART OF THE
  10.     AUTHOR'S OFFICIAL DUTIES AS A GOVERNMENT EMPLOYEE.  THIS MEANS IT
  11.     CANNOT BE COPYRIGHTED.  THIS SOFTWARE IS FREELY AVAILABLE TO THE
  12.     PUBLIC FOR USE WITHOUT A COPYRIGHT NOTICE, AND THERE ARE NO
  13.     RESTRICTIONS ON ITS USE, NOW OR SUBSEQUENTLY.
  14.  
  15. Author:
  16.     C. J. Eppich
  17.     Computer Systems Laboratory, DCRT
  18.     National Institutes of Health
  19.     Bethesda, MD 20892
  20.  
  21. $Log:    Heap.h,v $
  22.  * Revision 3.0  90/05/20  00:19:43  kgorlen
  23.  * Release for 1st edition.
  24.  * 
  25. */
  26.  
  27. #include "Collection.h"
  28. #include "OrderedCltn.h"
  29. #include "ArrayOb.h"
  30.  
  31. class Heap: public SeqCltn {
  32.     DECLARE_MEMBERS(Heap);
  33.     int endIndex;
  34.     ArrayOb contents;
  35. private:        // static member functions
  36.     static int child(int i)        { return (i << 1) + 1; }
  37.     static int grandchild(int i)    { return (child(i) << 1) + 1; }
  38.     static int parent(int i)    { return (i - 1) >> 1; }
  39.     static int level(int);
  40. private:
  41.     void bubbleUp(int);
  42.     void bubbleUpMax(int);
  43.     void bubbleUpMin(int);
  44.     int descendents(int) const;
  45.     void errEmpty(const char* fn) const;
  46.     int largest(int,int) const;
  47.     Object* removeAtIndex(int i);
  48.     int smallest(int,int) const;
  49.     void swap(int a,int b)     {
  50.         Object* temp = contents[a];
  51.         contents[a] = contents[b]; 
  52.         contents[b] = temp;
  53.     }
  54.     void trickleDown(int);
  55.     void trickleDownMax(int);
  56.     void trickleDownMin(int);
  57. protected:        // storer() functions for object I/O
  58.     virtual void storer(OIOofd&) const;
  59.     virtual void storer(OIOout&) const;
  60. public:
  61.     Heap(int size=DEFAULT_CAPACITY);
  62.     Heap(const ArrayOb&);
  63. #ifndef BUG_TOOBIG
  64. // yacc stack overflow
  65.     Heap(const Heap&);
  66. #endif
  67.     void operator=(const Heap&);
  68.     bool operator==(const Heap&) const;
  69.     bool operator!=(const Heap& a) const {  return !(*this==a);  }
  70.     virtual Object* add(Object&);
  71.     virtual Object*& at(int index);
  72.     virtual const Object *const& at(int index) const;
  73.     virtual unsigned capacity() const;
  74.     virtual void deepenShallowCopy();
  75.     virtual    void doFinish(Iterator& pos) const;
  76.     virtual Object* doNext(Iterator&) const;
  77.     virtual    void doReset(Iterator& pos) const;
  78.     virtual Object* first() const;
  79.     virtual unsigned hash() const;
  80.     virtual bool isEmpty() const;
  81.     virtual Object* last() const;
  82.     virtual unsigned occurrencesOf(const Object&) const;
  83.     virtual Object* remove(const Object&);
  84.     virtual void removeAll();
  85.     virtual Object* removeFirst();
  86.     virtual Object* removeId(const Object&);
  87.     virtual Object* removeLast();
  88.     virtual void reSize(int newSize);
  89.     virtual unsigned size() const;
  90.     OrderedCltn sort();
  91. private:                    // shouldNotImplement()
  92.     virtual void atAllPut(Object& ob);
  93.     virtual int indexOf(const Object& ob) const;
  94.     virtual int indexOfSubCollection(const SeqCltn& cltn, int start=0) const;
  95.     virtual void replaceFrom(int start, int stop, const SeqCltn& replacement, int startAt =0);
  96. };
  97.  
  98. #endif
  99.