001: ///////////////////////////////////////////////////////////////////////////////
002: // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
003: //
004: // This library is free software; you can redistribute it and/or
005: // modify it under the terms of the GNU Lesser General Public
006: // License as published by the Free Software Foundation; either
007: // version 2.1 of the License, or (at your option) any later version.
008: //
009: // This library is distributed in the hope that it will be useful,
010: // but WITHOUT ANY WARRANTY; without even the implied warranty of
011: // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: // GNU General Public License for more details.
013: //
014: // You should have received a copy of the GNU Lesser General Public
015: // License along with this program; if not, write to the Free Software
016: // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
017: ///////////////////////////////////////////////////////////////////////////////
018:
019: package gnu.trove;
020:
021: import java.io.*;
022: import java.util.Collection;
023: import java.util.Iterator;
024: import java.util.Set;
025: import java.util.Arrays;
026: import java.lang.reflect.Array;
027:
028: /**
029: * An implementation of the <tt>Set</tt> interface that uses an
030: * open-addressed hash table to store its contents.
031: *
032: * Created: Sat Nov 3 10:38:17 2001
033: *
034: * @author Eric D. Friedman
035: * @version $Id: THashSet.java,v 1.17 2007/11/01 16:08:14 robeden Exp $
036: */
037:
038: public class THashSet<E> extends TObjectHash<E> implements Set<E>,
039: Iterable<E>, Externalizable {
040:
041: static final long serialVersionUID = 1L;
042:
043: /**
044: * Creates a new <code>THashSet</code> instance with the default
045: * capacity and load factor.
046: */
047: public THashSet() {
048: super ();
049: }
050:
051: /**
052: * Creates a new <code>THashSet</code> instance with the default
053: * capacity and load factor.
054: *
055: * @param strategy used to compute hash codes and to compare objects.
056: */
057: public THashSet(TObjectHashingStrategy<E> strategy) {
058: super (strategy);
059: }
060:
061: /**
062: * Creates a new <code>THashSet</code> instance with a prime
063: * capacity equal to or greater than <tt>initialCapacity</tt> and
064: * with the default load factor.
065: *
066: * @param initialCapacity an <code>int</code> value
067: */
068: public THashSet(int initialCapacity) {
069: super (initialCapacity);
070: }
071:
072: /**
073: * Creates a new <code>THashSet</code> instance with a prime
074: * capacity equal to or greater than <tt>initialCapacity</tt> and
075: * with the default load factor.
076: *
077: * @param initialCapacity an <code>int</code> value
078: * @param strategy used to compute hash codes and to compare objects.
079: */
080: public THashSet(int initialCapacity,
081: TObjectHashingStrategy<E> strategy) {
082: super (initialCapacity, strategy);
083: }
084:
085: /**
086: * Creates a new <code>THashSet</code> instance with a prime
087: * capacity equal to or greater than <tt>initialCapacity</tt> and
088: * with the specified load factor.
089: *
090: * @param initialCapacity an <code>int</code> value
091: * @param loadFactor a <code>float</code> value
092: */
093: public THashSet(int initialCapacity, float loadFactor) {
094: super (initialCapacity, loadFactor);
095: }
096:
097: /**
098: * Creates a new <code>THashSet</code> instance with a prime
099: * capacity equal to or greater than <tt>initialCapacity</tt> and
100: * with the specified load factor.
101: *
102: * @param initialCapacity an <code>int</code> value
103: * @param loadFactor a <code>float</code> value
104: * @param strategy used to compute hash codes and to compare objects.
105: */
106: public THashSet(int initialCapacity, float loadFactor,
107: TObjectHashingStrategy<E> strategy) {
108: super (initialCapacity, loadFactor, strategy);
109: }
110:
111: /**
112: * Creates a new <code>THashSet</code> instance containing the
113: * elements of <tt>collection</tt>.
114: *
115: * @param collection a <code>Collection</code> value
116: */
117: public THashSet(Collection<? extends E> collection) {
118: this (collection.size());
119: addAll(collection);
120: }
121:
122: /**
123: * Creates a new <code>THashSet</code> instance containing the
124: * elements of <tt>collection</tt>.
125: *
126: * @param collection a <code>Collection</code> value
127: * @param strategy used to compute hash codes and to compare objects.
128: */
129: public THashSet(Collection<? extends E> collection,
130: TObjectHashingStrategy<E> strategy) {
131: this (collection.size(), strategy);
132: addAll(collection);
133: }
134:
135: /**
136: * Inserts a value into the set.
137: *
138: * @param obj an <code>Object</code> value
139: * @return true if the set was modified by the add operation
140: */
141: public boolean add(E obj) {
142: int index = insertionIndex(obj);
143:
144: if (index < 0) {
145: return false; // already present in set, nothing to add
146: }
147:
148: Object old = _set[index];
149: _set[index] = obj;
150:
151: postInsertHook(old == FREE);
152: return true; // yes, we added something
153: }
154:
155: public boolean equals(Object other) {
156: if (!(other instanceof Set)) {
157: return false;
158: }
159: Set that = (Set) other;
160: if (that.size() != this .size()) {
161: return false;
162: }
163: return containsAll(that);
164: }
165:
166: public int hashCode() {
167: HashProcedure p = new HashProcedure();
168: forEach(p);
169: return p.getHashCode();
170: }
171:
172: private final class HashProcedure implements TObjectProcedure<E> {
173: private int h = 0;
174:
175: public int getHashCode() {
176: return h;
177: }
178:
179: public final boolean execute(E key) {
180: h += _hashingStrategy.computeHashCode(key);
181: return true;
182: }
183: }
184:
185: /**
186: * Expands the set to accommodate new values.
187: *
188: * @param newCapacity an <code>int</code> value
189: */
190: protected void rehash(int newCapacity) {
191: int oldCapacity = _set.length;
192: Object oldSet[] = _set;
193:
194: _set = new Object[newCapacity];
195: Arrays.fill(_set, FREE);
196:
197: for (int i = oldCapacity; i-- > 0;) {
198: if (oldSet[i] != FREE && oldSet[i] != REMOVED) {
199: E o = (E) oldSet[i];
200: int index = insertionIndex(o);
201: if (index < 0) { // everyone pays for this because some people can't RTFM
202: throwObjectContractViolation(_set[(-index - 1)], o);
203: }
204: _set[index] = o;
205: }
206: }
207: }
208:
209: /**
210: * Returns a new array containing the objects in the set.
211: *
212: * @return an <code>Object[]</code> value
213: */
214: public Object[] toArray() {
215: Object[] result = new Object[size()];
216: forEach(new ToObjectArrayProcedure(result));
217: return result;
218: }
219:
220: /**
221: * Returns a typed array of the objects in the set.
222: *
223: * @param a an <code>Object[]</code> value
224: * @return an <code>Object[]</code> value
225: */
226: public <T> T[] toArray(T[] a) {
227: int size = size();
228: if (a.length < size)
229: a = (T[]) Array.newInstance(
230: a.getClass().getComponentType(), size);
231:
232: forEach(new ToObjectArrayProcedure(a));
233:
234: // If this collection fits in the specified array with room to
235: // spare (i.e., the array has more elements than this
236: // collection), the element in the array immediately following
237: // the end of the collection is set to null. This is useful in
238: // determining the length of this collection only if the
239: // caller knows that this collection does not contain any null
240: // elements.)
241:
242: if (a.length > size) {
243: a[size] = null;
244: }
245:
246: return a;
247: }
248:
249: /**
250: * Empties the set.
251: */
252: public void clear() {
253: super .clear();
254: Object[] set = _set;
255:
256: for (int i = set.length; i-- > 0;) {
257: set[i] = FREE;
258: }
259: }
260:
261: /**
262: * Removes <tt>obj</tt> from the set.
263: *
264: * @param obj an <code>Object</code> value
265: * @return true if the set was modified by the remove operation.
266: */
267: public boolean remove(Object obj) {
268: int index = index((E) obj);
269: if (index >= 0) {
270: removeAt(index);
271: return true;
272: }
273: return false;
274: }
275:
276: /**
277: * Creates an iterator over the values of the set. The iterator
278: * supports element deletion.
279: *
280: * @return an <code>Iterator</code> value
281: */
282: public Iterator<E> iterator() {
283: return new TObjectHashIterator<E>(this );
284: }
285:
286: /**
287: * Tests the set to determine if all of the elements in
288: * <tt>collection</tt> are present.
289: *
290: * @param collection a <code>Collection</code> value
291: * @return true if all elements were present in the set.
292: */
293: public boolean containsAll(Collection<?> collection) {
294: for (Iterator i = collection.iterator(); i.hasNext();) {
295: if (!contains(i.next())) {
296: return false;
297: }
298: }
299: return true;
300: }
301:
302: /**
303: * Adds all of the elements in <tt>collection</tt> to the set.
304: *
305: * @param collection a <code>Collection</code> value
306: * @return true if the set was modified by the add all operation.
307: */
308: public boolean addAll(Collection<? extends E> collection) {
309: boolean changed = false;
310: int size = collection.size();
311:
312: ensureCapacity(size);
313: Iterator<? extends E> it = collection.iterator();
314: while (size-- > 0) {
315: if (add(it.next())) {
316: changed = true;
317: }
318: }
319: return changed;
320: }
321:
322: /**
323: * Removes all of the elements in <tt>collection</tt> from the set.
324: *
325: * @param collection a <code>Collection</code> value
326: * @return true if the set was modified by the remove all operation.
327: */
328: public boolean removeAll(Collection<?> collection) {
329: boolean changed = false;
330: int size = collection.size();
331: Iterator it;
332:
333: it = collection.iterator();
334: while (size-- > 0) {
335: if (remove(it.next())) {
336: changed = true;
337: }
338: }
339: return changed;
340: }
341:
342: /**
343: * Removes any values in the set which are not contained in
344: * <tt>collection</tt>.
345: *
346: * @param collection a <code>Collection</code> value
347: * @return true if the set was modified by the retain all operation
348: */
349: public boolean retainAll(Collection<?> collection) {
350: boolean changed = false;
351: int size = size();
352: Iterator it;
353:
354: it = iterator();
355: while (size-- > 0) {
356: if (!collection.contains(it.next())) {
357: it.remove();
358: changed = true;
359: }
360: }
361: return changed;
362: }
363:
364: public void writeExternal(ObjectOutput out) throws IOException {
365: // VERSION
366: out.writeByte(0);
367:
368: // NUMBER OF ENTRIES
369: out.writeInt(_size);
370:
371: // ENTRIES
372: SerializationProcedure writeProcedure = new SerializationProcedure(
373: out);
374: if (!forEach(writeProcedure)) {
375: throw writeProcedure.exception;
376: }
377: }
378:
379: public void readExternal(ObjectInput in) throws IOException,
380: ClassNotFoundException {
381:
382: // VERSION
383: in.readByte();
384:
385: // NUMBER OF ENTRIES
386: int size = in.readInt();
387: setUp(size);
388:
389: // ENTRIES
390: while (size-- > 0) {
391: E val = (E) in.readObject();
392: add(val);
393: }
394: }
395: } // THashSet
|