home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / nihcl-3.0 / lib / Set.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-19  |  7.4 KB  |  348 lines
  1. /* Set.c -- implemenation of hash tables
  2.  
  3.     THIS SOFTWARE FITS THE DESCRIPTION IN THE U.S. COPYRIGHT ACT OF A
  4.     "UNITED STATES GOVERNMENT WORK".  IT WAS WRITTEN AS A PART OF THE
  5.     AUTHOR'S OFFICIAL DUTIES AS A GOVERNMENT EMPLOYEE.  THIS MEANS IT
  6.     CANNOT BE COPYRIGHTED.  THIS SOFTWARE IS FREELY AVAILABLE TO THE
  7.     PUBLIC FOR USE WITHOUT A COPYRIGHT NOTICE, AND THERE ARE NO
  8.     RESTRICTIONS ON ITS USE, NOW OR SUBSEQUENTLY.
  9.  
  10. Author:
  11.     K. E. Gorlen
  12.     Bg. 12A, Rm. 2033
  13.     Computer Systems Laboratory
  14.     Division of Computer Research and Technology
  15.     National Institutes of Health
  16.     Bethesda, Maryland 20892
  17.     Phone: (301) 496-1111
  18.     uucp: uunet!nih-csl!kgorlen
  19.     Internet: kgorlen@alw.nih.gov
  20.     September, 1985
  21.  
  22. Function:
  23.     
  24. A Set is an unordered collection of objects in which no object is
  25. duplicated.  Duplicate objects are defined by the function isEqual.
  26. Sets are implemented using a hash table.  The capacity() function
  27. returns the 1/2 the capacity of the hash table and the size() function
  28. returns the number of objects currently in the Set.  For efficiency, the
  29. capacity is always a power of two and is doubled whenever the table
  30. becomes half full.
  31.  
  32. $Log:    Set.c,v $
  33.  * Revision 3.0  90/05/20  00:21:14  kgorlen
  34.  * Release for 1st edition.
  35.  * 
  36. */
  37.  
  38. #include "Set.h"
  39. #include "OrderedCltn.h"
  40. #include "nihclIO.h"
  41.  
  42. #define    THIS    Set
  43. #define    BASE    Collection
  44. #define BASE_CLASSES BASE::desc()
  45. #define MEMBER_CLASSES ArrayOb::desc()
  46. #define VIRTUAL_BASE_CLASSES
  47.  
  48. DEFINE_CLASS(Set,1,"$Header: /afs/alw.nih.gov/unix/sun4_40c/usr/local/src/nihcl-3.0/share/lib/RCS/Set.c,v 3.0 90/05/20 00:21:14 kgorlen Rel $",NULL,NULL);
  49.  
  50. extern const int NIHCL_ALLOCSIZE,NIHCL_REMOVEERR;
  51.  
  52. unsigned Set::setCapacity(unsigned int size)
  53. /*
  54.     Establish the Set capacity.  Round size up to the next highest
  55.     power of two, if necessary.
  56. */
  57. {
  58.     if (size==0) setError(NIHCL_ALLOCSIZE,DEFAULT,this,className());
  59.     count = 0;
  60.     nbits = 0;
  61.     for (register unsigned s=size; s!=0; s>>=1) nbits++;
  62.     if ((size&(size-1)) != 0) nbits++;    // round up if not power of 2
  63.     size = 1<<nbits;
  64.     mask = size-1;
  65.     return size;        // return hash table size
  66. }
  67.  
  68. Set::Set(unsigned size) : contents(setCapacity(size)) {}
  69.  
  70. int Set::h(unsigned long K) const
  71. /*
  72. multiplicative hash function
  73.  
  74. Enter:
  75.     K = key to be hashed
  76.     
  77. Returns:
  78.     hash table index
  79.     
  80. Knuth Vol. 3, Section 6.4, pp. 508-512
  81. */
  82. {
  83. //mjs:    const unsigned long Aw = 2654435769UL;
  84.     const unsigned long Aw = 0x9E3779B9;
  85. //    const unsigned long Aw = 40503;        use for 16 bit machines? 
  86.     return ((Aw*K)>>((8*sizeof(unsigned))-nbits)) & mask;
  87. }
  88.  
  89. int Set::findIndexOf(const Object& ob) const
  90. /*
  91. Search this set for the specified object
  92.  
  93. Enter:
  94.     ob = pointer to object to search for
  95.  
  96. Returns:
  97.     index of object if found or of nil slot if not found
  98.     
  99. Algorithm L, Knuth Vol. 3, p. 519
  100. */
  101. {
  102.     register int i;
  103.     for (i = h(ob.hash()); contents[i]!=nil; i = (i-1)&mask) {
  104.         if (contents[i]->isEqual(ob)) return i;
  105.     }
  106.     return i;
  107. }
  108.  
  109. void Set::reSize(unsigned newSize)
  110. /*
  111.     Change the capacity of this Set to newSize.
  112. */
  113. {
  114.     if (newSize <= count) return;
  115.     if (count > 0) {
  116.         OrderedCltn oldcontents(count);
  117.         unsigned n = contents.size();
  118.         for (int i=0; i<n; i++) {
  119.             Object* ob = contents[i];
  120.             if (ob != nil) {
  121.                 oldcontents.add(*ob);
  122.                 contents.elem(i) = nil;
  123.             }
  124.         }
  125.         contents.reSize(setCapacity(newSize));
  126.         addAll(oldcontents);
  127.     }
  128.     else contents.reSize(setCapacity(newSize));
  129. }
  130.  
  131. Object* Set::add(Object& ob)
  132. /*
  133.     Add an object to this Set, making the Set larger if it
  134.     becomes half full.
  135. */
  136. {
  137.     register int i = findIndexOf(ob);
  138.     if (contents[i]==nil) {        // add new object to set 
  139.         contents[i] = &ob;
  140.         if (++count > capacity()) reSize(capacity()*EXPANSION_FACTOR);
  141.         return &ob;        // successful add 
  142.     }
  143.     else return contents[i];    // object already in set 
  144. }
  145.  
  146. Object* Set::remove(const Object& ob)
  147. /*
  148. remove object from set
  149.  
  150. Enter:
  151.     ob = reference to object to be removed
  152.  
  153. Returns:
  154.     pointer to removed object
  155.  
  156. Algorithm R, Knuth Vol. 3 p. 527
  157. */
  158. {
  159.     register int i = findIndexOf(ob);
  160.     Object* rob = contents[i];
  161.     if (rob==nil) setError(NIHCL_REMOVEERR,DEFAULT,this,className(),ob.className(),&ob);
  162.     else {
  163.         register int j,r;
  164.         while (YES) {
  165.             contents[j=i] = nil;
  166.             do {
  167.                 i = (i-1)&mask;
  168.                 if (contents[i]==nil) {
  169.                     count--;
  170.                     return rob;
  171.                 }
  172.                 r = h(contents[i]->hash());
  173.             } while ((i<=r&&r<j) || (r<j&&j<i) || (j<i&&i<=r));
  174.             contents[j] = contents[i];
  175.         }
  176.     }
  177. }
  178.  
  179. void Set::removeAll()
  180. {
  181.     contents.removeAll();
  182.     count = 0;
  183. }
  184.  
  185. bool Set::operator==(const Set& s) const
  186. /*
  187.     Return YES if the specified Set equals this Set.
  188. */
  189. {
  190.     if (count!=s.count) return NO;
  191.     unsigned n = contents.capacity();
  192.     for (register int i=0; i<n; i++) {
  193.         if (contents[i]!=nil && !s.includes(*contents[i])) return NO;
  194.     }
  195.     return YES;
  196. }
  197.  
  198. Set Set::operator-(const Set& s) const
  199. /*
  200.     Returns a Set of all of the objects that are contained in this
  201.     Set but not in the specified Set.
  202. */
  203. {
  204.     Set diff = *this;
  205.     unsigned n = contents.capacity();
  206.     for (register int i=0; i<n; i++) {
  207.         if (contents[i]!=nil && s.includes(*contents[i])) diff.remove(*contents[i]);
  208.     }
  209.     return diff;
  210. }
  211.  
  212. Set Set::operator&(const Set& s) const
  213. /*
  214.     Returns a Set of all objects that are in both this Set and
  215.     the specified Set.
  216. */
  217. {
  218.     Set intersection = *this;
  219.     unsigned n = contents.capacity();
  220.     for (register int i=0; i<n; i++) {
  221.         if (contents[i]!=nil && !s.includes(*contents[i])) intersection.remove(*contents[i]);
  222.     }
  223.     return intersection;
  224. }
  225.  
  226. Set Set::operator|(const Set& s) const
  227. /*
  228.     Returns a Set of all objects that are in either this Set
  229.     or the specified Set.
  230. */
  231. {
  232.     Set u = *this;
  233.     u.addAll(s);
  234.     return u;
  235. }
  236.  
  237. Object*& Set::at(int i)                { return contents[i]; }
  238.  
  239. const Object *const& Set::at(int i) const    { return contents[i]; }
  240.  
  241. bool Set::isEqual(const Object& p) const
  242. /*
  243.     Returns YES if this Set equals the specified object.
  244. */
  245. {
  246.     return p.isSpecies(classDesc) && *this==castdown(p);
  247. }
  248.  
  249. const Class* Set::species() const { return &classDesc; }
  250.  
  251. void Set::deepenShallowCopy()
  252. {
  253.     BASE::deepenShallowCopy();
  254.     contents.deepenShallowCopy();
  255. }
  256.  
  257. Object* Set::doNext(Iterator& pos) const
  258. {
  259.     Object* ob;
  260.     unsigned n = contents.capacity();
  261.     while (pos.index < n) {
  262.         if ((ob = (Object*)contents[pos.index++]) != nil) return ob;
  263.     }
  264.     return 0;
  265. }
  266.  
  267. unsigned Set::capacity() const  { return contents.capacity()>>1; }
  268.  
  269. unsigned Set::hash() const
  270. {
  271.     unsigned h = 0;
  272.     DO(*this,Object,o) h ^= o->hash(); OD
  273.     return h;
  274. }
  275.  
  276. unsigned Set::occurrencesOf(const Object& ob) const
  277. /*
  278.     Return the number of occurences of thw specified object
  279.     in this Set (either 0 or 1).
  280. */
  281. {
  282.     if (contents[findIndexOf(ob)]!=nil) return 1;
  283.     else return 0;
  284. }
  285.  
  286. Object* Set::findObjectWithKey(const Object& ob) const
  287. {
  288.     return (Object*)contents[findIndexOf(ob)];
  289. }
  290.  
  291. unsigned Set::size() const        { return count; }
  292.  
  293. Set Collection::asSet() const
  294. /*
  295.     Convert this Collection to a Set.
  296. */
  297. {
  298.     Set cltn(MAX(size(),DEFAULT_CAPACITY));
  299.     addContentsTo(cltn);
  300.     return cltn;
  301. }
  302.  
  303. static unsigned set_capacity;
  304.  
  305. Set::Set(OIOin& strm)
  306. :
  307. #ifdef MI
  308.     Object(strm),
  309. #endif
  310.     BASE(strm),
  311.     contents((strm >> set_capacity, setCapacity(set_capacity)))
  312. {
  313.     unsigned n;
  314.     strm >> n;        // read Set size 
  315.     while (n--) add(*Object::readFrom(strm));
  316. }
  317.  
  318. Set::Set(OIOifd& fd)
  319. :
  320. #ifdef MI
  321.     Object(fd),
  322. #endif
  323.     BASE(fd),
  324.     contents((fd >> set_capacity, setCapacity(set_capacity) ))
  325. {
  326.     unsigned n;
  327.     fd >> n;
  328.     while (n--) add(*Object::readFrom(fd));
  329. }
  330.  
  331. void Set::storer(OIOofd& fd) const
  332. {
  333.     BASE::storer(fd);
  334.     _storer(fd);
  335. }
  336.  
  337. void Set::storer(OIOout& strm) const
  338. {
  339.     BASE::storer(strm);
  340.     _storer(strm);
  341. }
  342.  
  343. int Set::compare(const Object&) const
  344. {
  345.     shouldNotImplement("compare");
  346.     return 0;
  347. }
  348.