THashSet


1   ///////////////////////////////////////////////////////////////////////////////
2   // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
3   //
4   // This library is free software; you can redistribute it and/or
5   // modify it under the terms of the GNU Lesser General Public
6   // License as published by the Free Software Foundation; either
7   // version 2.1 of the License, or (at your option) any later version.
8   //
9   // This library is distributed in the hope that it will be useful,
10  // but WITHOUT ANY WARRANTY; without even the implied warranty of
11  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  // GNU General Public License for more details.
13  //
14  // You should have received a copy of the GNU Lesser General Public
15  // License along with this program; if not, write to the Free Software
16  // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
17  ///////////////////////////////////////////////////////////////////////////////
18  
19  package gnu.trove;
20  
21  import java.io.*;
22  import java.util.Collection  ;
23  import java.util.Iterator  ;
24  import java.util.Set  ;
25  import java.util.Arrays  ;
26  import java.lang.reflect.Array  ;
27  
28  /**
29   * An implementation of the <tt>Set</tt> interface that uses an
30   * open-addressed hash table to store its contents.
31   *
32   * Created: Sat Nov  3 10:38:17 2001
33   *
34   * @author Eric D. Friedman
35   * @version $Id: THashSet.java,v 1.15 2006/11/10 23:27:55 robeden Exp $
36   */
37  
38  public class THashSet<E> extends TObjectHash<E> implements Set  <E>, Externalizable {
39      static final long serialVersionUID = 1L;
40  
41      /**
42       * Creates a new <code>THashSet</code> instance with the default
43       * capacity and load factor.
44       */
45      public THashSet() {
46          super();
47      }
48  
49      /**
50       * Creates a new <code>THashSet</code> instance with the default
51       * capacity and load factor.
52       * 
53       * @param strategy used to compute hash codes and to compare objects.
54       */
55      public THashSet(TObjectHashingStrategy<E> strategy) {
56          super(strategy);
57      }
58  
59      /**
60       * Creates a new <code>THashSet</code> instance with a prime
61       * capacity equal to or greater than <tt>initialCapacity</tt> and
62       * with the default load factor.
63       *
64       * @param initialCapacity an <code>int</code> value
65       */
66      public THashSet(int initialCapacity) {
67          super(initialCapacity);
68      }
69  
70      /**
71       * Creates a new <code>THashSet</code> instance with a prime
72       * capacity equal to or greater than <tt>initialCapacity</tt> and
73       * with the default load factor.
74       *
75       * @param initialCapacity an <code>int</code> value
76       * @param strategy used to compute hash codes and to compare objects.
77       */
78      public THashSet(int initialCapacity, TObjectHashingStrategy<E> strategy) {
79          super(initialCapacity, strategy);
80      }
81  
82      /**
83       * Creates a new <code>THashSet</code> instance with a prime
84       * capacity equal to or greater than <tt>initialCapacity</tt> and
85       * with the specified load factor.
86       *
87       * @param initialCapacity an <code>int</code> value
88       * @param loadFactor a <code>float</code> value
89       */
90      public THashSet(int initialCapacity, float loadFactor) {
91          super(initialCapacity, loadFactor);
92      }
93  
94      /**
95       * Creates a new <code>THashSet</code> instance with a prime
96       * capacity equal to or greater than <tt>initialCapacity</tt> and
97       * with the specified load factor.
98       *
99       * @param initialCapacity an <code>int</code> value
100      * @param loadFactor a <code>float</code> value
101      * @param strategy used to compute hash codes and to compare objects.
102      */
103     public THashSet(int initialCapacity, float loadFactor, TObjectHashingStrategy<E> strategy) {
104         super(initialCapacity, loadFactor, strategy);
105     }
106 
107     /**
108      * Creates a new <code>THashSet</code> instance containing the
109      * elements of <tt>collection</tt>.
110      *
111      * @param collection a <code>Collection</code> value
112      */
113     public THashSet(Collection  <? extends E> collection) {
114         this(collection.size());
115         addAll(collection);
116     }
117 
118     /**
119      * Creates a new <code>THashSet</code> instance containing the
120      * elements of <tt>collection</tt>.
121      *
122      * @param collection a <code>Collection</code> value
123      * @param strategy used to compute hash codes and to compare objects.
124      */
125     public THashSet(Collection  <? extends E> collection, TObjectHashingStrategy<E> strategy) {
126         this(collection.size(), strategy);
127         addAll(collection);
128     }
129 
130     /**
131      * Inserts a value into the set.
132      *
133      * @param obj an <code>Object</code> value
134      * @return true if the set was modified by the add operation
135      */
136     public boolean add(E obj) {
137         int index = insertionIndex(obj);
138 
139         if (index < 0) {
140             return false;       // already present in set, nothing to add
141         }
142 
143         Object   old = _set[index];
144         _set[index] = obj;
145 
146         postInsertHook(old == FREE);
147         return true;            // yes, we added something
148     }
149 
150     public boolean equals(Object   other) {
151         if (! (other instanceof Set  )) {
152             return false;
153         }
154         Set   that = (Set  )other;
155         if (that.size() != this.size()) {
156             return false;
157         }
158         return containsAll(that);
159     }
160 
161     public int hashCode() {
162         HashProcedure p = new HashProcedure();
163         forEach(p);
164         return p.getHashCode();
165     }
166 
167     private final class HashProcedure implements TObjectProcedure<E> {
168         private int h = 0;
169 
170         public int getHashCode() {
171             return h;
172         }
173 
174         public final boolean execute(E key) {
175             h += _hashingStrategy.computeHashCode(key);
176             return true;
177         }
178     }
179 
180     /**
181      * Expands the set to accomodate new values.
182      *
183      * @param newCapacity an <code>int</code> value
184      */
185     protected void rehash(int newCapacity) {
186         int oldCapacity = _set.length;
187         Object   oldSet[] = _set;
188 
189         _set = new Object  [newCapacity];
190         Arrays.fill(_set, FREE);
191 
192         for (int i = oldCapacity; i-- > 0;) {
193             if(oldSet[i] != FREE && oldSet[i] != REMOVED) {
194                 E o = (E) oldSet[i];
195                 int index = insertionIndex(o);
196                 if (index < 0) { // everyone pays for this because some people can't RTFM
197                     throwObjectContractViolation(_set[(-index -1)], o);
198                 }
199                 _set[index] = o;
200             }
201         }
202     }
203 
204     /**
205      * Returns a new array containing the objects in the set.
206      *
207      * @return an <code>Object[]</code> value
208      */
209     public Object  [] toArray() {
210         Object  [] result = new Object  [size()];
211         forEach(new ToObjectArrayProcedure(result));
212         return result;
213     }
214 
215     /**
216      * Returns a typed array of the objects in the set.
217      *
218      * @param a an <code>Object[]</code> value
219      * @return an <code>Object[]</code> value
220      */
221     public <T> T[] toArray(T[] a) {
222         int size = size();
223         if (a.length < size)
224             a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
225 
226         forEach(new ToObjectArrayProcedure(a));
227 
228         // If this collection fits in the specified array with room to
229         // spare (i.e., the array has more elements than this
230         // collection), the element in the array immediately following
231         // the end of the collection is set to null. This is useful in
232         // determining the length of this collection only if the
233         // caller knows that this collection does not contain any null
234         // elements.)
235         
236         if (a.length > size) {
237             a[size] = null;
238         }
239 
240         return a;
241     }
242 
243     /**
244      * Empties the set.
245      */
246     public void clear() {
247         super.clear();
248         Object  [] set = _set;
249 
250         for (int i = set.length; i-- > 0;) {
251             set[i] = FREE;
252         }
253     }
254 
255     /**
256      * Removes <tt>obj</tt> from the set.
257      *
258      * @param obj an <code>Object</code> value
259      * @return true if the set was modified by the remove operation.
260      */
261     public boolean remove(Object   obj) {
262         int index = index((E) obj);
263         if (index >= 0) {
264             removeAt(index);
265             return true;
266         }
267         return false;
268     }
269 
270     /**
271      * Creates an iterator over the values of the set.  The iterator
272      * supports element deletion.
273      *
274      * @return an <code>Iterator</code> value
275      */
276     public Iterator  <E> iterator() {
277         return new TObjectHashIterator<E>(this);
278     }
279 
280     /**
281      * Tests the set to determine if all of the elements in
282      * <tt>collection</tt> are present.
283      *
284      * @param collection a <code>Collection</code> value
285      * @return true if all elements were present in the set.
286      */
287     public boolean containsAll(Collection  <?> collection) {
288         for (Iterator   i = collection.iterator(); i.hasNext();) {
289             if (! contains(i.next())) {
290                 return false;
291             }
292         }
293         return true;
294     }
295 
296     /**
297      * Adds all of the elements in <tt>collection</tt> to the set.
298      *
299      * @param collection a <code>Collection</code> value
300      * @return true if the set was modified by the add all operation.
301      */
302     public boolean addAll(Collection  <? extends E> collection) {
303         boolean changed = false;
304         int size = collection.size();
305 
306         ensureCapacity(size);
307         Iterator  <? extends E> it = collection.iterator();
308         while (size-- > 0) {
309             if (add(it.next())) {
310                 changed = true;
311             }
312         }
313         return changed;
314     }
315 
316     /**
317      * Removes all of the elements in <tt>collection</tt> from the set.
318      *
319      * @param collection a <code>Collection</code> value
320      * @return true if the set was modified by the remove all operation.
321      */
322     public boolean removeAll(Collection  <?> collection) {
323         boolean changed = false;
324         int size = collection.size();
325         Iterator   it;
326 
327         it = collection.iterator();
328         while (size-- > 0) {
329             if (remove(it.next())) {
330                 changed = true;
331             }
332         }
333         return changed;
334     }
335 
336     /**
337      * Removes any values in the set which are not contained in
338      * <tt>collection</tt>.
339      *
340      * @param collection a <code>Collection</code> value
341      * @return true if the set was modified by the retain all operation
342      */
343     public boolean retainAll(Collection  <?> collection) {
344         boolean changed = false;
345         int size = size();
346         Iterator   it;
347 
348         it = iterator();
349         while (size-- > 0) {
350             if (! collection.contains(it.next())) {
351                 it.remove();
352                 changed = true;
353             }
354         }
355         return changed;
356     }
357 
358 
359     public void writeExternal( ObjectOutput out ) throws IOException {
360         // VERSION
361         out.writeByte( 0 );
362 
363         // NUMBER OF ENTRIES
364         out.writeInt( _size );
365 
366         // ENTRIES
367         SerializationProcedure writeProcedure = new SerializationProcedure( out );
368         if (! forEach(writeProcedure)) {
369             throw writeProcedure.exception;
370         }
371     }
372 
373     public void readExternal( ObjectInput in )
374         throws IOException, ClassNotFoundException   {
375 
376         // VERSION
377         in.readByte();
378 
379         // NUMBER OF ENTRIES
380         int size = in.readInt();
381         setUp( size );
382 
383         // ENTRIES
384         while (size-- > 0) {
385             E val = (E) in.readObject();
386             add(val);
387         }
388     }
389 } // THashSet
390
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags