home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / hashedse.jav < prev    next >
Encoding:
Text File  |  1995-12-14  |  9.0 KB  |  364 lines
  1. /*
  2.   File: HashedSet.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.   13Oct95  dl                 Changed protection statuses
  12.  
  13. */
  14.   
  15. package collections;
  16.  
  17. import java.util.Enumeration;
  18. import java.util.NoSuchElementException;
  19.  
  20. /**
  21.  *
  22.  * Hash table implementation of set
  23.  * @author Doug Lea
  24.  * @version 0.93
  25.  *
  26.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  27. **/
  28.  
  29. public class HashedSet extends    UpdatableSetImpl 
  30.                        implements UpdatableSet, HashTableParams  {
  31.  
  32. // instance variables 
  33.  
  34. /**
  35.  * The table. Each entry is a list. Null if no table allocated
  36. **/
  37.   protected LLCell table_[];
  38. /**
  39.  * The threshold load factor
  40. **/
  41.   protected float loadFactor_;
  42.  
  43.  
  44. // constructors
  45.  
  46. /**
  47.  * Make an empty HashedSet.
  48. **/
  49.  
  50.   public HashedSet() { this(null, defaultLoadFactor); }
  51.  
  52. /**
  53.  * Make an empty HashedSet using given element screener
  54. **/
  55.  
  56.   public HashedSet(Predicate screener) { this(screener, defaultLoadFactor); }
  57.  
  58. /**
  59.  * Special version of constructor needed by clone()
  60. **/
  61.  
  62.   protected HashedSet(Predicate s, float f) { 
  63.     super(s); table_ = null; loadFactor_ = f;
  64.   }
  65.  
  66. /**
  67.  * Make an independent copy of the table. Does not clone elements.
  68. **/
  69.   
  70.   protected Object clone() throws CloneNotSupportedException { 
  71.     HashedSet c =  new HashedSet(screener_, loadFactor_);
  72.     if (count_ != 0) {
  73.       int cap = 2 * (int)(count_ / loadFactor_) + 1;
  74.       if (cap < defaultInitialBuckets) cap = defaultInitialBuckets;
  75.       c.buckets(cap);
  76.       for (int i = 0; i < table_.length; ++i) 
  77.         for (LLCell p = table_[i]; p != null; p = p.next())
  78.           c.include(p.element());
  79.     }
  80.     return c;
  81.   }
  82.  
  83.  
  84. // HashTableParams methods
  85.  
  86. /**
  87.  * Implements collections.HashTableParams.buckets.
  88.  * Time complexity: O(1).
  89.  * @see collections.HashTableParams#buckets.
  90. **/
  91.  
  92.   public synchronized int buckets() { 
  93.     return (table_ == null)? 0 : table_.length; 
  94.   }
  95.  
  96. /**
  97.  * Implements collections.HashTableParams.buckets.
  98.  * Time complexity: O(n).
  99.  * @see collections.HashTableParams#buckets.
  100. **/
  101.  
  102.   public synchronized void buckets(int newCap) 
  103.   throws IllegalArgumentException {
  104.     if (newCap == buckets()) 
  105.       return;
  106.     else if (newCap >= 1) 
  107.       resize(newCap);
  108.     else 
  109.       throw new IllegalArgumentException("Impossible Hash table size:" + newCap);
  110.  
  111.   }
  112.  
  113. /**
  114.  * Implements collections.HashTableParams.thresholdLoadfactor
  115.  * Time complexity: O(1).
  116.  * @see collections.HashTableParams#thresholdLoadfactor
  117. **/
  118.  
  119.   public synchronized float thresholdLoadFactor() { 
  120.     return loadFactor_;
  121.   }
  122.  
  123. /**
  124.  * Implements collections.HashTableParams.thresholdLoadfactor
  125.  * Time complexity: O(n).
  126.  * @see collections.HashTableParams#thresholdLoadfactor
  127. **/
  128.  
  129.   public synchronized void thresholdLoadFactor(float desired)
  130.   throws IllegalArgumentException {
  131.     if (desired > 0.0) {
  132.       loadFactor_ = desired;
  133.       checkLoadFactor();
  134.     }
  135.     else
  136.       throw new IllegalArgumentException("Impossible Hash table load factor:" + desired);
  137.   }
  138.  
  139.  
  140.  
  141.  
  142.  
  143. // Collection methods
  144.  
  145. /**
  146.  * Implements collections.Collection.includes.
  147.  * Time complexity: O(1) average; O(n) worst.
  148.  * @see collections.Collection#includes
  149. **/
  150.   public synchronized boolean includes(Object element) {
  151.     if (element == null || count_ == 0) return false;
  152.     LLCell p = table_[hashOf(element)];
  153.     if (p != null) return p.find(element) != null;
  154.     else return false;
  155.   }
  156.  
  157. /**
  158.  * Implements collections.Collection.occurrencesOf.
  159.  * Time complexity: O(n).
  160.  * @see collections.Collection#occurrencesOf
  161. **/
  162.   public synchronized int occurrencesOf(Object element) {
  163.     if (includes(element)) return 1; else return 0;
  164.   }
  165.  
  166. /**
  167.  * Implements collections.Collection.elements.
  168.  * Time complexity: O(1).
  169.  * @see collections.Collection#elements
  170. **/
  171.   public synchronized CollectionEnumeration elements() { 
  172.     return new HTEnumeration(this, table_); 
  173.   }
  174.  
  175. // UpdatableCollection methods
  176.  
  177. /**
  178.  * Implements collections.UpdatableCollection.clear.
  179.  * Time complexity: O(1).
  180.  * @see collections.UpdatableCollection#clear
  181. **/
  182.   public synchronized void clear() { 
  183.     setCount(0);
  184.     table_ = null;
  185.   }
  186.  
  187. /**
  188.  * Implements collections.UpdatableCollection.exclude.
  189.  * Time complexity: O(1) average; O(n) worst.
  190.  * @see collections.UpdatableCollection#exclude
  191. **/
  192.   public synchronized void exclude(Object element) {
  193.     removeOneOf(element);
  194.   }
  195.  
  196.   public synchronized void removeOneOf(Object element) {
  197.     if (element == null || count_ == 0) return;
  198.     int h = hashOf(element);
  199.     LLCell hd = table_[h];
  200.     LLCell p = hd;
  201.     LLCell trail = p;
  202.     while (p != null) {
  203.       LLCell n = p.next();
  204.       if (p.element().equals(element)) {
  205.         decCount();
  206.         if (p == table_[h]) { table_[h] = n; trail = n; }
  207.         else trail.next(n);
  208.         return;
  209.       }
  210.       else {
  211.         trail = p;
  212.         p = n;
  213.       }
  214.     }
  215.   }
  216.  
  217.   public synchronized void replaceOneOf(Object oldElement, Object newElement) 
  218.   throws IllegalElementException {
  219.  
  220.     if (count_ == 0 || oldElement == null || oldElement.equals(newElement))
  221.       return;
  222.     if (includes(oldElement)) {
  223.       checkElement(newElement);
  224.       exclude(oldElement);
  225.       include(newElement);
  226.     }
  227.   }
  228.  
  229.   public synchronized void replaceAllOf(Object oldElement, Object newElement) 
  230.   throws IllegalElementException {
  231.     replaceOneOf(oldElement, newElement);
  232.   }
  233.  
  234. /**
  235.  * Implements collections.UpdatableCollection.take.
  236.  * Time complexity: O(number of buckets).
  237.  * @see collections.UpdatableCollection#take
  238. **/
  239.   public synchronized Object take() 
  240.   throws NoSuchElementException {
  241.     if (count_ != 0) {
  242.       for (int i = 0; i < table_.length; ++i) {
  243.         if (table_[i] != null) {
  244.           decCount();
  245.           Object v = table_[i].element();
  246.           table_[i] = table_[i].next();
  247.           return v;
  248.         }
  249.       }
  250.     }
  251.     checkIndex(0);
  252.     return null; // not reached
  253.   }
  254.  
  255.  
  256. // UpdatableSet methods
  257.  
  258. /**
  259.  * Implements collections.UpdatableSet.include.
  260.  * Time complexity: O(1) average; O(n) worst.
  261.  * @see collections.UpdatableSet#include
  262. **/
  263.   public synchronized void include(Object element) {
  264.     checkElement(element);
  265.     if (table_ == null) resize(defaultInitialBuckets);
  266.     int h = hashOf(element);
  267.     LLCell hd = table_[h];
  268.     if (hd != null && hd.find(element) != null) return;
  269.     LLCell n = new LLCell(element, hd);
  270.     table_[h] = n;
  271.     incCount();
  272.     if (hd != null) checkLoadFactor(); // only check if bin was nonempty
  273.   }
  274.  
  275.  
  276.  
  277. // Helper methods
  278.  
  279. /**
  280.  * Check to see if we are past load factor threshold. If so, resize
  281.  * so that we are at half of the desired threshold.
  282.  * Also while at it, check to see if we are empty so can just
  283.  * unlink table.
  284. **/
  285.   protected void checkLoadFactor() {
  286.     if (table_ == null) {
  287.       if (count_ != 0) resize(defaultInitialBuckets);
  288.     }
  289.     else {
  290.       float fc = (float)(count_);
  291.       float ft = table_.length;
  292.       if (fc / ft > loadFactor_) {
  293.         int newCap = 2 * (int)(fc / loadFactor_) + 1;
  294.         resize(newCap);
  295.       }
  296.     }
  297.   }
  298.  
  299. /**
  300.  * Mask off and remainder the hashCode for element
  301.  * so it can be used as table index
  302. **/
  303.  
  304.   protected final int hashOf(Object element) {
  305.     return (element.hashCode() & 0x7FFFFFFF) % table_.length;
  306.   }
  307.  
  308.  
  309. /**
  310.  * resize table to new capacity, rehashing all elements
  311. **/
  312.   protected void resize(int newCap) {
  313.     LLCell newtab[] = new LLCell[newCap];
  314.     
  315.     if (table_ != null) {
  316.       for (int i = 0; i < table_.length; ++i) {
  317.         LLCell p = table_[i];
  318.         while (p != null) {
  319.           LLCell n = p.next();
  320.           int h =  (p.element().hashCode() & 0x7FFFFFFF) % newCap;
  321.           p.next(newtab[h]);
  322.           newtab[h] = p;
  323.           p = n;
  324.         }
  325.       }
  326.     }
  327.     table_ = newtab;
  328.     incVersion();
  329.   }
  330.  
  331. // ImplementationCheckable methods
  332.  
  333. /**
  334.  * Implements collections.ImplementationCheckable.checkImplementation.
  335.  * @see collections.ImplementationCheckable#checkImplementation
  336. **/
  337.   public synchronized void checkImplementation() 
  338.   throws ImplementationError {
  339.  
  340.     super.checkImplementation();
  341.  
  342.     assert(!(table_ == null && count_ != 0));
  343.     assert((table_ == null || table_.length > 0));
  344.     assert(loadFactor_ > 0.0f);
  345.  
  346.     if (table_ != null) {
  347.       int c = 0;
  348.       for (int i = 0; i < table_.length; ++i) {
  349.         for (LLCell p = table_[i]; p != null; p = p.next()) {
  350.           ++c;
  351.           assert(canInclude(p.element()));
  352.           assert(includes(p.element()));
  353.           assert(occurrencesOf(p.element()) == 1);
  354.           assert(hashOf(p.element()) == i);
  355.         }
  356.       }
  357.       assert(c == count_);
  358.     }
  359.   }
  360.  
  361.  
  362. }
  363.  
  364.