TIntHashSet


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.IOException;
22  import java.io.ObjectInputStream;
23  import java.io.ObjectOutputStream;
24  import java.io.Serializable;
25  import java.io.Serializable;
26  import java.util.Arrays;
27  
28  /**
29   * An open addressed set implementation for int primitives.
30   *
31   * Created: Sat Nov  3 10:38:17 2001
32   *
33   * @author Eric D. Friedman
34   * @version $Id: TIntHashSet.java,v 1.13 2005/03/26 17:52:56 ericdf Exp $
35   */
36  
37  public class TIntHashSet extends TIntHash implements Serializable {
38  
39      /** compatible serialization ID - not present in 1.1b3 and earlier */
40      static final long serialVersionUID = 1L;
41  
42      /**
43       * Creates a new <code>TIntHashSet</code> instance with the default
44       * capacity and load factor.
45       */
46      public TIntHashSet() {
47          super();
48      }
49  
50      /**
51       * Creates a new <code>TIntHashSet</code> instance with a prime
52       * capacity equal to or greater than <tt>initialCapacity</tt> and
53       * with the default load factor.
54       *
55       * @param initialCapacity an <code>int</code> value
56       */
57      public TIntHashSet(int initialCapacity) {
58          super(initialCapacity);
59      }
60  
61      /**
62       * Creates a new <code>TIntHashSet</code> instance with a prime
63       * capacity equal to or greater than <tt>initialCapacity</tt> and
64       * with the specified load factor.
65       *
66       * @param initialCapacity an <code>int</code> value
67       * @param loadFactor a <code>float</code> value
68       */
69      public TIntHashSet(int initialCapacity, float loadFactor) {
70          super(initialCapacity, loadFactor);
71      }
72  
73      /**
74       * Creates a new <code>TIntHashSet</code> instance containing the
75       * elements of <tt>array</tt>.
76       *
77       * @param array an array of <code>int</code> primitives
78       */
79      public TIntHashSet(int[] array) {
80          this(array.length);
81          addAll(array);
82      }
83  
84      /**
85       * Creates a new <code>TIntHash</code> instance with the default
86       * capacity and load factor.
87       * @param strategy used to compute hash codes and to compare keys.
88       */
89      public TIntHashSet(TIntHashingStrategy strategy) {
90          super(strategy);
91      }
92  
93      /**
94       * Creates a new <code>TIntHash</code> instance whose capacity
95       * is the next highest prime above <tt>initialCapacity + 1</tt>
96       * unless that value is already prime.
97       *
98       * @param initialCapacity an <code>int</code> value
99       * @param strategy used to compute hash codes and to compare keys.
100      */
101     public TIntHashSet(int initialCapacity, TIntHashingStrategy strategy) {
102         super(initialCapacity, strategy);
103     }
104 
105     /**
106      * Creates a new <code>TIntHash</code> instance with a prime
107      * value at or near the specified capacity and load factor.
108      *
109      * @param initialCapacity used to find a prime capacity for the table.
110      * @param loadFactor used to calculate the threshold over which
111      * rehashing takes place.
112      * @param strategy used to compute hash codes and to compare keys.
113      */
114     public TIntHashSet(int initialCapacity, float loadFactor, TIntHashingStrategy strategy) {
115         super(initialCapacity, loadFactor, strategy);
116     }
117 
118     /**
119      * Creates a new <code>TIntHashSet</code> instance containing the
120      * elements of <tt>array</tt>.
121      *
122      * @param array an array of <code>int</code> primitives
123      * @param strategy used to compute hash codes and to compare keys.
124      */
125     public TIntHashSet(int[] array, TIntHashingStrategy strategy) {
126         this(array.length, strategy);
127         addAll(array);
128     }
129 
130     /**
131      * @return a TIntIterator with access to the values in this set
132      */
133     public TIntIterator iterator() {
134         return new TIntIterator(this);
135     }
136 
137     /**
138      * Inserts a value into the set.
139      *
140      * @param val an <code>int</code> value
141      * @return true if the set was modified by the add operation
142      */
143     public boolean add(int val) {
144         int index = insertionIndex(val);
145 
146         if (index < 0) {
147             return false;       // already present in set, nothing to add
148         }
149 
150         byte previousState = _states[index];
151         _set[index] = val;
152         _states[index] = FULL;
153         postInsertHook(previousState == FREE);
154         
155         return true;            // yes, we added something
156     }
157 
158     /**
159      * Expands the set to accomodate new values.
160      *
161      * @param newCapacity an <code>int</code> value
162      */
163     protected void rehash(int newCapacity) {
164         int oldCapacity = _set.length;
165         int oldSet[] = _set;
166         byte oldStates[] = _states;
167 
168         _set = new int[newCapacity];
169         _states = new byte[newCapacity];
170 
171         for (int i = oldCapacity; i-- > 0;) {
172             if(oldStates[i] == FULL) {
173                 int o = oldSet[i];
174                 int index = insertionIndex(o);
175                 _set[index] = o;
176                 _states[index] = FULL;
177             }
178         }
179     }
180 
181     /**
182      * Returns a new array containing the values in the set.
183      *
184      * @return an <code>int[]</code> value
185      */
186     public int[] toArray() {
187         int[] result = new int[size()];
188         int[] set = _set;
189         byte[] states = _states;
190         
191         for (int i = states.length, j = 0; i-- > 0;) {
192             if (states[i] == FULL) {
193                 result[j++] = set[i];
194             }
195         }
196         return result;
197     }
198 
199     /**
200      * Empties the set.
201      */
202     public void clear() {
203         super.clear();
204         int[] set = _set;
205         byte[] states = _states;
206 
207         for (int i = set.length; i-- > 0;) {
208             set[i] = (int)0;
209             states[i] = FREE;
210         }
211     }
212 
213     /**
214      * Compares this set with another set for equality of their stored
215      * entries.
216      *
217      * @param other an <code>Object</code> value
218      * @return a <code>boolean</code> value
219      */
220     public boolean equals(Object other) {
221         if (! (other instanceof TIntHashSet)) {
222             return false;
223         }
224         final TIntHashSet that = (TIntHashSet)other;
225         if (that.size() != this.size()) {
226             return false;
227         }
228         return forEach(new TIntProcedure() {
229             public final boolean execute(int value) {
230                 return that.contains(value);
231             }
232         });
233     }
234 
235     public int hashCode() {
236         HashProcedure p = new HashProcedure();
237         forEach(p);
238         return p.getHashCode();
239     }
240 
241     private final class HashProcedure implements TIntProcedure {
242         private int h = 0;
243         
244         public int getHashCode() {
245             return h;
246         }
247         
248         public final boolean execute(int key) {
249             h += _hashingStrategy.computeHashCode(key);
250             return true;
251         }
252     }
253 
254     /**
255      * Removes <tt>val</tt> from the set.
256      *
257      * @param val an <code>int</code> value
258      * @return true if the set was modified by the remove operation.
259      */
260     public boolean remove(int val) {
261         int index = index(val);
262         if (index >= 0) {
263             removeAt(index);
264             return true;
265         }
266         return false;
267     }
268 
269     /**
270      * Tests the set to determine if all of the elements in
271      * <tt>array</tt> are present.
272      *
273      * @param array an <code>array</code> of int primitives.
274      * @return true if all elements were present in the set.
275      */
276     public boolean containsAll(int[] array) {
277       for (int i = array.length; i-- > 0;) {
278             if (! contains(array[i])) {
279                 return false;
280             }
281         }
282         return true;
283     }
284 
285     /**
286      * Adds all of the elements in <tt>array</tt> to the set.
287      *
288      * @param array an <code>array</code> of int primitives.
289      * @return true if the set was modified by the add all operation.
290      */
291     public boolean addAll(int[] array) {
292         boolean changed = false;
293         for (int i = array.length; i-- > 0;) {
294             if (add(array[i])) {
295                 changed = true;
296             }
297         }
298         return changed;
299     }
300 
301     /**
302      * Removes all of the elements in <tt>array</tt> from the set.
303      *
304      * @param array an <code>array</code> of int primitives.
305      * @return true if the set was modified by the remove all operation.
306      */
307     public boolean removeAll(int[] array) {
308         boolean changed = false;
309         for (int i = array.length; i-- > 0;) {
310             if (remove(array[i])) {
311                 changed = true;
312             }
313         }
314         return changed;
315     }
316 
317     /**
318      * Removes any values in the set which are not contained in
319      * <tt>array</tt>.
320      *
321      * @param array an <code>array</code> of int primitives.
322      * @return true if the set was modified by the retain all operation
323      */
324     public boolean retainAll(int[] array) {
325         boolean changed = false;
326         Arrays.sort(array);
327         int[] set = _set;
328         byte[] states = _states;
329 
330         for (int i = set.length; i-- > 0;) {
331             if (states[i] == FULL && (Arrays.binarySearch(array,set[i]) < 0)) {
332                 remove(set[i]);
333                 changed = true;
334             }
335         }
336         return changed;
337     }
338 
339     private void writeObject(ObjectOutputStream stream)
340         throws IOException {
341         stream.defaultWriteObject();
342 
343         // number of entries
344         stream.writeInt(_size);
345 
346         SerializationProcedure writeProcedure = new SerializationProcedure(stream);
347         if (! forEach(writeProcedure)) {
348             throw writeProcedure.exception;
349         }
350     }
351 
352     private void readObject(ObjectInputStream stream)
353         throws IOException, ClassNotFoundException {
354         stream.defaultReadObject();
355 
356         int size = stream.readInt();
357         setUp(size);
358         while (size-- > 0) {
359             int val = stream.readInt();
360             add(val);
361         }
362     }
363 } // TIntHashSet
364
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Java Books Remove Frame
Popular Tags