home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 6.ddi / MWHC.006 / 22 < prev    next >
Encoding:
Text File  |  1992-06-07  |  4.5 KB  |  128 lines
  1. #ifndef  __RWSET_H__
  2. #define  __RWSET_H__
  3. pragma push_align_members(64);
  4.  
  5. /*
  6.  * Declarations for RWSet --- hash table lookup.
  7.  *
  8.  * $Header:   E:/vcs/rw/rwset.h_v   1.2   18 Feb 1992 09:54:40   KEFFER  $
  9.  *
  10.  ****************************************************************************
  11.  *
  12.  * Rogue Wave 
  13.  * P.O. Box 2328
  14.  * Corvallis, OR 97339
  15.  * Voice: (503) 754-3010    FAX: (503) 757-6650
  16.  *
  17.  * Copyright (C) 1989, 1990, 1991. This software is subject to copyright 
  18.  * protection under the laws of the United States and other countries.
  19.  *
  20.  ***************************************************************************
  21.  *
  22.  * Duplicates are not allowed.
  23.  * Hash table look up with linear probing via double hashing.  
  24.  *
  25.  * The table size must be a prime number, so that the linear probing
  26.  * does not wrap around back onto itself.
  27.  *
  28.  * $Log:   E:/vcs/rw/rwset.h_v  $
  29.  * 
  30.  *    Rev 1.2   18 Feb 1992 09:54:40   KEFFER
  31.  * 
  32.  *    Rev 1.1   28 Oct 1991 09:08:22   keffer
  33.  * Changed inclusions to <rw/xxx.h>
  34.  * 
  35.  *    Rev 1.0   28 Jul 1991 08:16:38   keffer
  36.  * Tools.h++ V4.0.5 PVCS baseline version
  37.  *
  38.  */
  39.  
  40. #include "rw/colclass.h"
  41. #include "rw/iterator.h"
  42.  
  43. class RWExport RWSetIterator;
  44.  
  45. class RWExport RWSet : public RWCollection {
  46.   friend RWSetIterator;
  47. protected:
  48.   enum                hashStatus {empty, occupied, deleted};
  49. protected:
  50.   typedef char            infoType;
  51.   RWCollectableP*        table;    // Pointer to an array of pointers to objects.
  52.   infoType*            info;    // Array giving information about status of array indices.
  53.   unsigned            npts;    // Size of above arrays.
  54.   unsigned            items;    // Total number of stored objects.
  55.   unsigned            resizeThreshold;  // Resize if items > resizeThreshold.
  56.   static unsigned        nextPrime(unsigned);
  57. protected:
  58.   void                copyOld(const RWSet&);
  59.   virtual unsigned        findIndex(const RWCollectable* a) const;        // Return index of a.
  60.   unsigned            findIndexReference(const RWCollectable* a) const;
  61.   RWCollectable*         removeAtIndex(unsigned);
  62.   static unsigned        secondaryHash(unsigned i){ return 8-(i&0x7); }
  63. public:
  64.  
  65.   RWSet(unsigned N = RWCollection::DEFAULT_CAPACITY); 
  66.   RWSet (const RWSet&);
  67.   ~RWSet();
  68.  
  69.   /******************** Member operators ****************************/
  70.   void                operator=(const RWSet&);
  71.   RWBoolean             operator<=(const RWSet&) const;
  72.   RWBoolean             operator==(const RWSet&) const;
  73.   RWBoolean             operator!=(const RWSet&) const;
  74.  
  75.   /****************** Virtual member functions *******************/
  76.   virtual void            apply(RWapplyCollectable, void*);
  77. //virtual unsigned        binaryStoreSize() const;
  78.   virtual void            clear();
  79. //virtual void            clearAndDestroy();
  80. //virtual int            compareTo(const RWCollectable*) const;
  81. //virtual RWBoolean        contains(const RWCollectable*) const;
  82.   virtual unsigned        entries() const        {return items;}
  83.   virtual RWCollectable*    find(const RWCollectable*) const;
  84. //virtual unsigned        hash() const;
  85.   virtual RWCollectable*    insert(RWCollectable*);
  86.   virtual ClassID        isA() const {return __RWSET;}
  87.   virtual RWBoolean        isEmpty() const        {return items==0;}
  88.   virtual RWBoolean        isEqual(const RWCollectable*) const;
  89.   virtual RWCollectable*    newSpecies() const;
  90.   virtual unsigned        occurrencesOf(const RWCollectable*) const;
  91.   virtual RWCollectable*    remove(const RWCollectable*);
  92. //virtual void            removeAndDestroy(const RWCollectable*); 
  93. //virtual void            restoreGuts(RWvistream&);
  94. //virtual void            restoreGuts(RWFile&);
  95. //virtual void            saveGuts(RWvostream&) const;
  96. //virtual void            saveGuts(RWFile&) const;
  97.  
  98. /********************** Special functions **********************************/
  99.   void                resize(unsigned n = 0);    // Resize to n, or if n==0, next prime > 2*size
  100.  
  101. #ifdef RDEBUG
  102.   // Print status of hash table:
  103.   friend ostream&        operator<<(ostream&, const RWSet&);
  104. #endif
  105. };
  106.  
  107. class RWExport RWSetIterator : public RWIterator {
  108.   RWSet*        theTable;
  109.   int            place;    // Iterator position.
  110. public:
  111.   RWSetIterator(RWSet& h);
  112.  
  113. /*********** Virtual functions inherited from class RWIterator ***********/
  114.   RWCollectable*        findNext(const RWCollectable*);    // Find next matching item
  115.   RWCollectable*        key() const;            // Return current item
  116.   RWCollectable*        operator()();            // Advance iterator
  117.   void            reset();
  118. /******************* Special iterator functions *******************************/
  119.   RWCollectable*        remove();            // Remove current item
  120.   RWCollectable*           removeNext(const RWCollectable*);    // Remove next matching item
  121. };
  122.  
  123. inline void
  124. RWSetIterator::reset() {place=-1;}
  125.  
  126. pragma pop_align_members();
  127. #endif /* __RWSET_H__ */
  128.