001: import java.util.AbstractSet;
002: import java.util.Iterator;
003: import java.util.NoSuchElementException;
004: 
005: /**
006:    A hash set stores an unordered collection of objects, using
007:    a hash table.
008: */
009: public class HashSet extends AbstractSet
010: {
011:    /**
012:       Constructs a hash table.
013:       @param bucketsLength the length of the buckets array
014:    */
015:    public HashSet(int bucketsLength)
016:    {
017:       buckets = new Node[bucketsLength];
018:       size = 0;
019:    }
020: 
021:    /**
022:       Tests for set membership.
023:       @param x an object
024:       @return true if x is an element of this set
025:    */
026:    public boolean contains(Object x)
027:    {
028:       int h = x.hashCode();
029:       if (h < 0) h = -h;
030:       h = h % buckets.length;
031:       
032:       Node current = buckets[h];
033:       while (current != null)
034:       {
035:          if (current.data.equals(x)) return true;
036:          current = current.next;
037:       }
038:       return false;
039:    }
040: 
041:    /**
042:       Adds an element to this set.
043:       @param x an object
044:       @return true if x is a new object, false if x was
045:       already in the set
046:    */
047:    public boolean add(Object x)
048:    {
049:       int h = x.hashCode();
050:       if (h < 0) h = -h;
051:       h = h % buckets.length;
052:       
053:       Node current = buckets[h];
054:       while (current != null)
055:       {
056:          if (current.data.equals(x)) 
057:             return false; // Already in the set
058:          current = current.next;
059:       }
060:       Node newNode = new Node();
061:       newNode.data = x;
062:       newNode.next = buckets[h];
063:       buckets[h] = newNode;
064:       size++;
065:       return true;
066:    }
067: 
068:    /**
069:       Removes an object from this set.
070:       @param x an object
071:       @return true if x was removed from this set, false
072:       if x was not an element of this set
073:    */
074:    public boolean remove(Object x)
075:    {
076:       int h = x.hashCode();
077:       if (h < 0) h = -h;
078:       h = h % buckets.length;
079:       
080:       Node current = buckets[h];
081:       Node previous = null;
082:       while (current != null)
083:       {
084:          if (current.data.equals(x)) 
085:          {
086:             if (previous == null) buckets[h] = current.next;
087:             else previous.next = current.next;
088:             size--;
089:             return true;
090:          }
091:          previous = current;
092:          current = current.next;
093:       }
094:       return false;
095:    }
096: 
097:    /**
098:       Returns an iterator that traverses the elements of this set.
099:       @param a hash set iterator
100:    */
101:    public Iterator iterator()
102:    {
103:       return new HashSetIterator();
104:    }
105: 
106:    /**
107:       Gets the number of elements in this set.
108:       @return the number of elements
109:    */
110:    public int size()
111:    {
112:       return size;
113:    }
114: 
115:    private Node[] buckets;
116:    private int size;
117: 
118:    private class Node
119:    {
120:       public Object data;
121:       public Node next;
122:    }
123: 
124:    private class HashSetIterator implements Iterator
125:    {
126:       /**
127:          Constructs a hash set iterator that points to the
128:          first element of the hash set.
129:       */
130:       public HashSetIterator()
131:       {
132:          current = null;
133:          bucket = -1;
134:          previous = null;
135:          previousBucket = -1;
136:       }
137:       
138:       public boolean hasNext()
139:       {
140:          if (current != null && current.next != null) 
141:             return true;
142:          for (int b = bucket + 1; b < buckets.length; b++)
143:             if (buckets[b] != null) return true;
144:          return false;
145:       }
146:        
147:       public Object next()
148:       {
149:          previous = current;
150:          previousBucket = bucket;
151:          if (current == null || current.next == null) 
152:          {
153:             // Move to next bucket
154:             bucket++;
155: 
156:             while (bucket < buckets.length 
157:                   && buckets[bucket] == null)
158:                bucket++;
159:             if (bucket < buckets.length) 
160:                current = buckets[bucket];
161:             else
162:                throw new NoSuchElementException();
163:          }
164:          else // Move to next element in bucket
165:             current = current.next; 
166:          return current.data;
167:       }
168: 
169:       public void remove()
170:       {
171:          if (previous != null && previous.next == current)
172:             previous.next = current.next;
173:          else if (previousBucket < bucket) 
174:             buckets[bucket] = current.next; 
175:          else
176:             throw new IllegalStateException();
177:          current = previous;
178:          bucket = previousBucket;
179:       }
180: 
181:       private int bucket;
182:       private Node current;
183:       private int previousBucket;
184:       private Node previous;
185:    }
186: }