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.util.Arrays;
022:
023: /**
024: * An open addressed hashing implementation for Object types.
025: *
026: * Created: Sun Nov 4 08:56:06 2001
027: *
028: * @author Eric D. Friedman
029: * @version $Id: TObjectHash.java,v 1.25 2007/03/30 20:53:22 robeden Exp $
030: */
031: abstract public class TObjectHash<T> extends THash implements
032: TObjectHashingStrategy<T> {
033: static final long serialVersionUID = -3461112548087185871L;
034:
035: /** the set of Objects */
036: protected transient Object[] _set;
037:
038: /** the strategy used to hash objects in this collection. */
039: protected TObjectHashingStrategy<T> _hashingStrategy;
040:
041: protected static final Object REMOVED = new Object(),
042: FREE = new Object();
043:
044: /**
045: * Creates a new <code>TObjectHash</code> instance with the
046: * default capacity and load factor.
047: */
048: public TObjectHash() {
049: super ();
050: this ._hashingStrategy = this ;
051: }
052:
053: /**
054: * Creates a new <code>TObjectHash</code> instance with the
055: * default capacity and load factor and a custom hashing strategy.
056: *
057: * @param strategy used to compute hash codes and to compare objects.
058: */
059: public TObjectHash(TObjectHashingStrategy<T> strategy) {
060: super ();
061: this ._hashingStrategy = strategy;
062: }
063:
064: /**
065: * Creates a new <code>TObjectHash</code> instance whose capacity
066: * is the next highest prime above <tt>initialCapacity + 1</tt>
067: * unless that value is already prime.
068: *
069: * @param initialCapacity an <code>int</code> value
070: */
071: public TObjectHash(int initialCapacity) {
072: super (initialCapacity);
073: this ._hashingStrategy = this ;
074: }
075:
076: /**
077: * Creates a new <code>TObjectHash</code> instance whose capacity
078: * is the next highest prime above <tt>initialCapacity + 1</tt>
079: * unless that value is already prime. Uses the specified custom
080: * hashing strategy.
081: *
082: * @param initialCapacity an <code>int</code> value
083: * @param strategy used to compute hash codes and to compare objects.
084: */
085: public TObjectHash(int initialCapacity,
086: TObjectHashingStrategy<T> strategy) {
087: super (initialCapacity);
088: this ._hashingStrategy = strategy;
089: }
090:
091: /**
092: * Creates a new <code>TObjectHash</code> instance with a prime
093: * value at or near the specified capacity and load factor.
094: *
095: * @param initialCapacity used to find a prime capacity for the table.
096: * @param loadFactor used to calculate the threshold over which
097: * rehashing takes place.
098: */
099: public TObjectHash(int initialCapacity, float loadFactor) {
100: super (initialCapacity, loadFactor);
101: this ._hashingStrategy = this ;
102: }
103:
104: /**
105: * Creates a new <code>TObjectHash</code> instance with a prime
106: * value at or near the specified capacity and load factor. Uses
107: * the specified custom hashing strategy.
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 objects.
113: */
114: public TObjectHash(int initialCapacity, float loadFactor,
115: TObjectHashingStrategy<T> strategy) {
116: super (initialCapacity, loadFactor);
117: this ._hashingStrategy = strategy;
118: }
119:
120: /**
121: * @return a shallow clone of this collection
122: */
123: public TObjectHash<T> clone() {
124: TObjectHash<T> h = (TObjectHash<T>) super .clone();
125: h._set = (Object[]) this ._set.clone();
126: return h;
127: }
128:
129: protected int capacity() {
130: return _set.length;
131: }
132:
133: protected void removeAt(int index) {
134: _set[index] = REMOVED;
135: super .removeAt(index);
136: }
137:
138: /**
139: * initializes the Object set of this hash table.
140: *
141: * @param initialCapacity an <code>int</code> value
142: * @return an <code>int</code> value
143: */
144: protected int setUp(int initialCapacity) {
145: int capacity;
146:
147: capacity = super .setUp(initialCapacity);
148: _set = new Object[capacity];
149: Arrays.fill(_set, FREE);
150: return capacity;
151: }
152:
153: /**
154: * Executes <tt>procedure</tt> for each element in the set.
155: *
156: * @param procedure a <code>TObjectProcedure</code> value
157: * @return false if the loop over the set terminated because
158: * the procedure returned false for some value.
159: */
160: public boolean forEach(TObjectProcedure<T> procedure) {
161: Object[] set = _set;
162: for (int i = set.length; i-- > 0;) {
163: if (set[i] != FREE && set[i] != REMOVED
164: && !procedure.execute((T) set[i])) {
165: return false;
166: }
167: }
168: return true;
169: }
170:
171: /**
172: * Searches the set for <tt>obj</tt>
173: *
174: * @param obj an <code>Object</code> value
175: * @return a <code>boolean</code> value
176: */
177: public boolean contains(Object obj) {
178: return index((T) obj) >= 0;
179: }
180:
181: /**
182: * Locates the index of <tt>obj</tt>.
183: *
184: * @param obj an <code>Object</code> value
185: * @return the index of <tt>obj</tt> or -1 if it isn't in the set.
186: */
187: protected int index(T obj) {
188: final TObjectHashingStrategy<T> hashing_strategy = _hashingStrategy;
189:
190: final Object[] set = _set;
191: final int length = set.length;
192: final int hash = hashing_strategy.computeHashCode(obj) & 0x7fffffff;
193: int index = hash % length;
194: Object cur = set[index];
195:
196: if (cur == FREE)
197: return -1;
198:
199: // NOTE: here it has to be REMOVED or FULL (some user-given value)
200: if (cur == REMOVED || !hashing_strategy.equals((T) cur, obj)) {
201: // see Knuth, p. 529
202: final int probe = 1 + (hash % (length - 2));
203:
204: do {
205: index -= probe;
206: if (index < 0) {
207: index += length;
208: }
209: cur = set[index];
210: } while (cur != FREE
211: && (cur == REMOVED || !_hashingStrategy.equals(
212: (T) cur, obj)));
213: }
214:
215: return cur == FREE ? -1 : index;
216: }
217:
218: /**
219: * Locates the index at which <tt>obj</tt> can be inserted. if
220: * there is already a value equal()ing <tt>obj</tt> in the set,
221: * returns that value's index as <tt>-index - 1</tt>.
222: *
223: * @param obj an <code>Object</code> value
224: * @return the index of a FREE slot at which obj can be inserted
225: * or, if obj is already stored in the hash, the negative value of
226: * that index, minus 1: -index -1.
227: */
228: protected int insertionIndex(T obj) {
229: final TObjectHashingStrategy<T> hashing_strategy = _hashingStrategy;
230:
231: final Object[] set = _set;
232: final int length = set.length;
233: final int hash = hashing_strategy.computeHashCode(obj) & 0x7fffffff;
234: int index = hash % length;
235: Object cur = set[index];
236:
237: if (cur == FREE) {
238: return index; // empty, all done
239: } else if (cur != REMOVED
240: && hashing_strategy.equals((T) cur, obj)) {
241: return -index - 1; // already stored
242: } else { // already FULL or REMOVED, must probe
243: // compute the double hash
244: final int probe = 1 + (hash % (length - 2));
245:
246: // if the slot we landed on is FULL (but not removed), probe
247: // until we find an empty slot, a REMOVED slot, or an element
248: // equal to the one we are trying to insert.
249: // finding an empty slot means that the value is not present
250: // and that we should use that slot as the insertion point;
251: // finding a REMOVED slot means that we need to keep searching,
252: // however we want to remember the offset of that REMOVED slot
253: // so we can reuse it in case a "new" insertion (i.e. not an update)
254: // is possible.
255: // finding a matching value means that we've found that our desired
256: // key is already in the table
257: if (cur != REMOVED) {
258: // starting at the natural offset, probe until we find an
259: // offset that isn't full.
260: do {
261: index -= probe;
262: if (index < 0) {
263: index += length;
264: }
265: cur = set[index];
266: } while (cur != FREE && cur != REMOVED
267: && !hashing_strategy.equals((T) cur, obj));
268: }
269:
270: // if the index we found was removed: continue probing until we
271: // locate a free location or an element which equal()s the
272: // one we have.
273: if (cur == REMOVED) {
274: int firstRemoved = index;
275: while (cur != FREE
276: && (cur == REMOVED || !hashing_strategy.equals(
277: (T) cur, obj))) {
278: index -= probe;
279: if (index < 0) {
280: index += length;
281: }
282: cur = set[index];
283: }
284: // NOTE: cur cannot == REMOVED in this block
285: return (cur != FREE) ? -index - 1 : firstRemoved;
286: }
287: // if it's full, the key is already stored
288: // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
289: return (cur != FREE) ? -index - 1 : index;
290: }
291: }
292:
293: /**
294: * This is the default implementation of TObjectHashingStrategy:
295: * it delegates hashing to the Object's hashCode method.
296: *
297: * @param o for which the hashcode is to be computed
298: * @return the hashCode
299: * @see Object#hashCode()
300: */
301: public final int computeHashCode(T o) {
302: return o == null ? 0 : o.hashCode();
303: }
304:
305: /**
306: * This is the default implementation of TObjectHashingStrategy:
307: * it delegates equality comparisons to the first parameter's
308: * equals() method.
309: *
310: * @param o1 an <code>Object</code> value
311: * @param o2 an <code>Object</code> value
312: * @return true if the objects are equal
313: * @see Object#equals(Object)
314: */
315: public final boolean equals(T o1, T o2) {
316: return o1 == null ? o2 == null : o1.equals(o2);
317: }
318:
319: /**
320: * Convenience methods for subclasses to use in throwing exceptions about
321: * badly behaved user objects employed as keys. We have to throw an
322: * IllegalArgumentException with a rather verbose message telling the
323: * user that they need to fix their object implementation to conform
324: * to the general contract for java.lang.Object.
325: *
326: * @param o1 the first of the equal elements with unequal hash codes.
327: * @param o2 the second of the equal elements with unequal hash codes.
328: * @exception IllegalArgumentException the whole point of this method.
329: */
330: protected final void throwObjectContractViolation(Object o1,
331: Object o2) throws IllegalArgumentException {
332: throw new IllegalArgumentException(
333: "Equal objects must have equal hashcodes. "
334: + "During rehashing, Trove discovered that "
335: + "the following two objects claim to be "
336: + "equal (as in java.lang.Object.equals()) "
337: + "but their hashCodes (or those calculated by "
338: + "your TObjectHashingStrategy) are not equal."
339: + "This violates the general contract of "
340: + "java.lang.Object.hashCode(). See bullet point two "
341: + "in that method's documentation. "
342: + "object #1 =" + o1 + "; object #2 =" + o2);
343: }
344: } // TObjectHash
|