-/*******************************************************************************\r
- * Copyright (c) 2007, 2010 Association for Decentralized Information Management\r
- * in Industry THTH ry.\r
- * All rights reserved. This program and the accompanying materials\r
- * are made available under the terms of the Eclipse Public License v1.0\r
- * which accompanies this distribution, and is available at\r
- * http://www.eclipse.org/legal/epl-v10.html\r
- *\r
- * Contributors:\r
- * VTT Technical Research Centre of Finland - initial API and implementation\r
- *******************************************************************************/\r
-package org.simantics.db.impl.query;\r
-\r
-///////////////////////////////////////////////////////////////////////////////\r
-//Copyright (c) 2001, Eric D. Friedman All Rights Reserved.\r
-//\r
-//This library is free software; you can redistribute it and/or\r
-//modify it under the terms of the GNU Lesser General Public\r
-//License as published by the Free Software Foundation; either\r
-//version 2.1 of the License, or (at your option) any later version.\r
-//\r
-//This library is distributed in the hope that it will be useful,\r
-//but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
-//GNU General Public License for more details.\r
-//\r
-//You should have received a copy of the GNU Lesser General Public\r
-//License along with this program; if not, write to the Free Software\r
-//Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.\r
-///////////////////////////////////////////////////////////////////////////////\r
-\r
-import gnu.trove.impl.hash.THash;\r
-import gnu.trove.procedure.TObjectProcedure;\r
-import gnu.trove.strategy.HashingStrategy;\r
-\r
-import java.io.IOException;\r
-import java.io.ObjectInput;\r
-import java.io.ObjectOutput;\r
-import java.util.Arrays;\r
-\r
-\r
-/**\r
-* An open addressed hashing implementation for Object types.\r
-*\r
-* Created: Sun Nov 4 08:56:06 2001\r
-*\r
-* @author Eric D. Friedman\r
-* @version $Id: TObjectHash.java,v 1.26 2008/05/07 21:25:45 robeden Exp $\r
-*/\r
-abstract public class StableObjectHash<T> extends THash\r
- implements HashingStrategy<T> {\r
-\r
- static final long serialVersionUID = -3461112548087185871L;\r
-\r
-\r
- /** the set of Objects */\r
- protected transient Object[] _set;\r
-\r
- /** the strategy used to hash objects in this collection. */\r
- protected HashingStrategy<T> _hashingStrategy;\r
-\r
- protected static final Object REMOVED = new Object(), FREE = new Object();\r
-\r
- /**\r
- * Creates a new <code>TObjectHash</code> instance with the\r
- * default capacity and load factor.\r
- */\r
- public StableObjectHash() {\r
- super(DEFAULT_CAPACITY, 0.75f);\r
- this._hashingStrategy = this;\r
- }\r
-\r
-// /**\r
-// * Creates a new <code>TObjectHash</code> instance with the\r
-// * default capacity and load factor and a custom hashing strategy.\r
-// *\r
-// * @param strategy used to compute hash codes and to compare objects.\r
-// */\r
-// public StableObjectHash(TObjectHashingStrategy<T> strategy) {\r
-// super();\r
-// this._hashingStrategy = strategy;\r
-// }\r
-//\r
-// /**\r
-// * Creates a new <code>TObjectHash</code> instance whose capacity\r
-// * is the next highest prime above <tt>initialCapacity + 1</tt>\r
-// * unless that value is already prime.\r
-// *\r
-// * @param initialCapacity an <code>int</code> value\r
-// */\r
-// public StableObjectHash(int initialCapacity) {\r
-// super(initialCapacity);\r
-// this._hashingStrategy = this;\r
-// }\r
-//\r
-// /**\r
-// * Creates a new <code>TObjectHash</code> instance whose capacity\r
-// * is the next highest prime above <tt>initialCapacity + 1</tt>\r
-// * unless that value is already prime. Uses the specified custom\r
-// * hashing strategy.\r
-// *\r
-// * @param initialCapacity an <code>int</code> value\r
-// * @param strategy used to compute hash codes and to compare objects.\r
-// */\r
-// public StableObjectHash(int initialCapacity, TObjectHashingStrategy<T> strategy) {\r
-// super(initialCapacity);\r
-// this._hashingStrategy = strategy;\r
-// }\r
-//\r
-// /**\r
-// * Creates a new <code>TObjectHash</code> instance with a prime\r
-// * value at or near the specified capacity and load factor.\r
-// *\r
-// * @param initialCapacity used to find a prime capacity for the table.\r
-// * @param loadFactor used to calculate the threshold over which\r
-// * rehashing takes place.\r
-// */\r
-// public StableObjectHash(int initialCapacity, float loadFactor) {\r
-// super(initialCapacity, loadFactor);\r
-// this._hashingStrategy = this;\r
-// }\r
-//\r
-// /**\r
-// * Creates a new <code>TObjectHash</code> instance with a prime\r
-// * value at or near the specified capacity and load factor. Uses\r
-// * the specified custom hashing strategy.\r
-// *\r
-// * @param initialCapacity used to find a prime capacity for the table.\r
-// * @param loadFactor used to calculate the threshold over which\r
-// * rehashing takes place.\r
-// * @param strategy used to compute hash codes and to compare objects.\r
-// */\r
-// public StableObjectHash(int initialCapacity, float loadFactor, TObjectHashingStrategy<T> strategy) {\r
-// super(initialCapacity, loadFactor);\r
-// this._hashingStrategy = strategy;\r
-// }\r
-\r
- /**\r
- * @return a shallow clone of this collection\r
- */\r
- public StableObjectHash<T> clone() {\r
- StableObjectHash<T> h;\r
- try {\r
- h = (StableObjectHash<T>)super.clone();\r
- } catch (CloneNotSupportedException e) {\r
- // It's supported\r
- throw new Error(e);\r
- }\r
- h._set = (Object[])this._set.clone();\r
- return h;\r
- }\r
-\r
- public int capacity() {\r
- return _set.length;\r
- }\r
-\r
- protected void removeAt(int index) {\r
- _set[index] = REMOVED;\r
- super.removeAt(index);\r
- }\r
-\r
- /**\r
- * initializes the Object set of this hash table.\r
- *\r
- * @param initialCapacity an <code>int</code> value\r
- * @return an <code>int</code> value\r
- */\r
- protected int setUp(int initialCapacity) {\r
- int capacity;\r
-\r
- capacity = super.setUp(initialCapacity);\r
- _set = new Object[capacity];\r
- Arrays.fill(_set,FREE);\r
- return capacity;\r
- }\r
-\r
- /**\r
- * Executes <tt>procedure</tt> for each element in the set.\r
- *\r
- * @param procedure a <code>TObjectProcedure</code> value\r
- * @return false if the loop over the set terminated because\r
- * the procedure returned false for some value.\r
- */\r
- public boolean forEach(TObjectProcedure<T> procedure) {\r
- Object[] set = _set;\r
- for (int i = set.length; i-- > 0;) {\r
- if (set[i] != FREE\r
- && set[i] != REMOVED\r
- && ! procedure.execute((T) set[i])) {\r
- return false;\r
- }\r
- }\r
- return true;\r
- }\r
-\r
- /**\r
- * Searches the set for <tt>obj</tt>\r
- *\r
- * @param obj an <code>Object</code> value\r
- * @return a <code>boolean</code> value\r
- */\r
- public boolean contains(Object obj) {\r
- throw new UnsupportedOperationException();\r
- }\r
-\r
- /**\r
- * Locates the index of <tt>obj</tt>.\r
- *\r
- * @param obj an <code>Object</code> value\r
- * @return the index of <tt>obj</tt> or -1 if it isn't in the set.\r
- */\r
- protected int index(T obj, Object[] _set) {\r
-\r
- final Object[] set = _set;\r
- final int length = set.length;\r
- final int hash = obj.hashCode() & 0x7fffffff;\r
- int index = hash % length;\r
- Object cur = set[index];\r
-\r
- if ( cur == FREE ) return -1;\r
-\r
- // NOTE: here it has to be REMOVED or FULL (some user-given value)\r
- if ( cur == REMOVED || !obj.equals(cur)) {\r
- // see Knuth, p. 529\r
- final int probe = 1 + (hash % (length - 2));\r
-\r
- do {\r
- index -= probe;\r
- if (index < 0) {\r
- index += length;\r
- }\r
- cur = set[index];\r
- } while (cur != FREE\r
- && (cur == REMOVED || !obj.equals(cur)));\r
- }\r
-\r
- return cur == FREE ? -1 : index;\r
- }\r
-\r
- protected int index(T obj, int hash_, Object[] _set) {\r
-\r
- final Object[] set = _set;\r
- final int length = set.length;\r
- final int hash = hash_ & 0x7fffffff;\r
- int index = hash % length;\r
- Object cur = set[index];\r
-\r
- if ( cur == FREE ) return -1;\r
-\r
- // NOTE: here it has to be REMOVED or FULL (some user-given value)\r
- if ( cur == REMOVED || !obj.equals(cur)) {\r
- // see Knuth, p. 529\r
- final int probe = 1 + (hash % (length - 2));\r
-\r
- do {\r
- index -= probe;\r
- if (index < 0) {\r
- index += length;\r
- }\r
- cur = set[index];\r
- } while (cur != FREE\r
- && (cur == REMOVED || !obj.equals(cur)));\r
- }\r
-\r
- return cur == FREE ? -1 : index;\r
- }\r
- \r
- /**\r
- * Locates the index at which <tt>obj</tt> can be inserted. if\r
- * there is already a value equal()ing <tt>obj</tt> in the set,\r
- * returns that value's index as <tt>-index - 1</tt>.\r
- *\r
- * @param obj an <code>Object</code> value\r
- * @return the index of a FREE slot at which obj can be inserted\r
- * or, if obj is already stored in the hash, the negative value of\r
- * that index, minus 1: -index -1.\r
- */\r
- protected int insertionIndex(T obj) {\r
-\r
- final Object[] set = _set;\r
- final int length = set.length;\r
- final int hash = obj.hashCode() & 0x7fffffff;\r
- int index = hash % length;\r
- Object cur = set[index];\r
-\r
- if (cur == FREE) {\r
- return index; // empty, all done\r
- } else if (cur != REMOVED && obj.equals((T) cur)) {\r
- return -index -1; // already stored\r
- } else { // already FULL or REMOVED, must probe\r
- // compute the double hash\r
- final int probe = 1 + (hash % (length - 2));\r
-\r
- // if the slot we landed on is FULL (but not removed), probe\r
- // until we find an empty slot, a REMOVED slot, or an element\r
- // equal to the one we are trying to insert.\r
- // finding an empty slot means that the value is not present\r
- // and that we should use that slot as the insertion point;\r
- // finding a REMOVED slot means that we need to keep searching,\r
- // however we want to remember the offset of that REMOVED slot\r
- // so we can reuse it in case a "new" insertion (i.e. not an update)\r
- // is possible.\r
- // finding a matching value means that we've found that our desired\r
- // key is already in the table\r
- if (cur != REMOVED) {\r
- // starting at the natural offset, probe until we find an\r
- // offset that isn't full.\r
- do {\r
- index -= probe;\r
- if (index < 0) {\r
- index += length;\r
- }\r
- cur = set[index];\r
- } while (cur != FREE\r
- && cur != REMOVED\r
- && ! obj.equals((T) cur));\r
- }\r
-\r
- // if the index we found was removed: continue probing until we\r
- // locate a free location or an element which equal()s the\r
- // one we have.\r
- if (cur == REMOVED) {\r
- int firstRemoved = index;\r
- while (cur != FREE\r
- && (cur == REMOVED || ! obj.equals((T) cur))) {\r
- index -= probe;\r
- if (index < 0) {\r
- index += length;\r
- }\r
- cur = set[index];\r
- }\r
- // NOTE: cur cannot == REMOVED in this block\r
- return (cur != FREE) ? -index -1 : firstRemoved;\r
- }\r
- // if it's full, the key is already stored\r
- // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)\r
- return (cur != FREE) ? -index -1 : index;\r
- }\r
- }\r
-\r
- protected int insertionIndex(T obj, int hash_) {\r
-\r
- final Object[] set = _set;\r
- final int length = set.length;\r
- final int hash = hash_ & 0x7fffffff;\r
- int index = hash % length;\r
- Object cur = set[index];\r
-\r
- if (cur == FREE) {\r
- return index; // empty, all done\r
- } else if (cur != REMOVED && obj.equals((T) cur)) {\r
- return -index -1; // already stored\r
- } else { // already FULL or REMOVED, must probe\r
- // compute the double hash\r
- final int probe = 1 + (hash % (length - 2));\r
-\r
- // if the slot we landed on is FULL (but not removed), probe\r
- // until we find an empty slot, a REMOVED slot, or an element\r
- // equal to the one we are trying to insert.\r
- // finding an empty slot means that the value is not present\r
- // and that we should use that slot as the insertion point;\r
- // finding a REMOVED slot means that we need to keep searching,\r
- // however we want to remember the offset of that REMOVED slot\r
- // so we can reuse it in case a "new" insertion (i.e. not an update)\r
- // is possible.\r
- // finding a matching value means that we've found that our desired\r
- // key is already in the table\r
- if (cur != REMOVED) {\r
- // starting at the natural offset, probe until we find an\r
- // offset that isn't full.\r
- do {\r
- index -= probe;\r
- if (index < 0) {\r
- index += length;\r
- }\r
- cur = set[index];\r
- } while (cur != FREE\r
- && cur != REMOVED\r
- && ! obj.equals((T) cur));\r
- }\r
-\r
- // if the index we found was removed: continue probing until we\r
- // locate a free location or an element which equal()s the\r
- // one we have.\r
- if (cur == REMOVED) {\r
- int firstRemoved = index;\r
- while (cur != FREE\r
- && (cur == REMOVED || ! obj.equals((T) cur))) {\r
- index -= probe;\r
- if (index < 0) {\r
- index += length;\r
- }\r
- cur = set[index];\r
- }\r
- // NOTE: cur cannot == REMOVED in this block\r
- return (cur != FREE) ? -index -1 : firstRemoved;\r
- }\r
- // if it's full, the key is already stored\r
- // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)\r
- return (cur != FREE) ? -index -1 : index;\r
- }\r
- }\r
- \r
- /**\r
- * This is the default implementation of TObjectHashingStrategy:\r
- * it delegates hashing to the Object's hashCode method.\r
- *\r
- * @param o for which the hashcode is to be computed\r
- * @return the hashCode\r
- * @see Object#hashCode()\r
- */\r
- public final int computeHashCode(T o) {\r
- return o == null ? 0 : o.hashCode();\r
- }\r
-\r
- /**\r
- * This is the default implementation of TObjectHashingStrategy:\r
- * it delegates equality comparisons to the first parameter's\r
- * equals() method.\r
- *\r
- * @param o1 an <code>Object</code> value\r
- * @param o2 an <code>Object</code> value\r
- * @return true if the objects are equal\r
- * @see Object#equals(Object)\r
- */\r
- public final boolean equals(T o1, T o2) {\r
- return o1 == null ? o2 == null : o1.equals(o2);\r
- }\r
-\r
- /**\r
- * Convenience methods for subclasses to use in throwing exceptions about\r
- * badly behaved user objects employed as keys. We have to throw an\r
- * IllegalArgumentException with a rather verbose message telling the\r
- * user that they need to fix their object implementation to conform\r
- * to the general contract for java.lang.Object.\r
- *\r
- * @param o1 the first of the equal elements with unequal hash codes.\r
- * @param o2 the second of the equal elements with unequal hash codes.\r
- * @exception IllegalArgumentException the whole point of this method.\r
- */\r
- protected final void throwObjectContractViolation(Object o1, Object o2)\r
- throws IllegalArgumentException {\r
- throw new IllegalArgumentException("Equal objects must have equal hashcodes. "\r
- + "During rehashing, Trove discovered that "\r
- + "the following two objects claim to be "\r
- + "equal (as in java.lang.Object.equals()) "\r
- + "but their hashCodes (or those calculated by "\r
- + "your TObjectHashingStrategy) are not equal."\r
- + "This violates the general contract of "\r
- + "java.lang.Object.hashCode(). See bullet point two "\r
- + "in that method's documentation. "\r
- + "object #1 =" + o1\r
- + "; object #2 =" + o2);\r
- }\r
-\r
-\r
- @Override\r
- public void writeExternal( ObjectOutput out ) throws IOException {\r
- super.writeExternal( out );\r
-\r
- // VERSION\r
- out.writeByte( 0 );\r
-\r
- // HASHING STRATEGY\r
- out.writeObject( _hashingStrategy );\r
- }\r
-\r
- @Override\r
- public void readExternal( ObjectInput in )\r
- throws IOException, ClassNotFoundException {\r
-\r
- super.readExternal( in );\r
-\r
- // VERSION\r
- in.readByte();\r
-\r
- // HASHING STRATEGY\r
- //noinspection unchecked\r
- _hashingStrategy = ( HashingStrategy<T> ) in.readObject();\r
- }\r
-} // TObjectHash\r
+/*******************************************************************************
+ * Copyright (c) 2007, 2010 Association for Decentralized Information Management
+ * in Industry THTH ry.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ * VTT Technical Research Centre of Finland - initial API and implementation
+ *******************************************************************************/
+package org.simantics.db.impl.query;
+
+///////////////////////////////////////////////////////////////////////////////
+//Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
+//
+//This library is free software; you can redistribute it and/or
+//modify it under the terms of the GNU Lesser General Public
+//License as published by the Free Software Foundation; either
+//version 2.1 of the License, or (at your option) any later version.
+//
+//This library is distributed in the hope that it will be useful,
+//but WITHOUT ANY WARRANTY; without even the implied warranty of
+//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+//GNU General Public License for more details.
+//
+//You should have received a copy of the GNU Lesser General Public
+//License along with this program; if not, write to the Free Software
+//Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+///////////////////////////////////////////////////////////////////////////////
+
+import gnu.trove.impl.hash.THash;
+import gnu.trove.procedure.TObjectProcedure;
+import gnu.trove.strategy.HashingStrategy;
+
+import java.io.IOException;
+import java.io.ObjectInput;
+import java.io.ObjectOutput;
+import java.util.Arrays;
+
+
+/**
+* An open addressed hashing implementation for Object types.
+*
+* Created: Sun Nov 4 08:56:06 2001
+*
+* @author Eric D. Friedman
+* @version $Id: TObjectHash.java,v 1.26 2008/05/07 21:25:45 robeden Exp $
+*/
+abstract public class StableObjectHash<T> extends THash
+ implements HashingStrategy<T> {
+
+ static final long serialVersionUID = -3461112548087185871L;
+
+
+ /** the set of Objects */
+ protected transient Object[] _set;
+
+ /** the strategy used to hash objects in this collection. */
+ protected HashingStrategy<T> _hashingStrategy;
+
+ protected static final Object REMOVED = new Object(), FREE = new Object();
+
+ /**
+ * Creates a new <code>TObjectHash</code> instance with the
+ * default capacity and load factor.
+ */
+ public StableObjectHash() {
+ super(DEFAULT_CAPACITY, 0.75f);
+ this._hashingStrategy = this;
+ }
+
+// /**
+// * Creates a new <code>TObjectHash</code> instance with the
+// * default capacity and load factor and a custom hashing strategy.
+// *
+// * @param strategy used to compute hash codes and to compare objects.
+// */
+// public StableObjectHash(TObjectHashingStrategy<T> strategy) {
+// super();
+// this._hashingStrategy = strategy;
+// }
+//
+// /**
+// * Creates a new <code>TObjectHash</code> instance whose capacity
+// * is the next highest prime above <tt>initialCapacity + 1</tt>
+// * unless that value is already prime.
+// *
+// * @param initialCapacity an <code>int</code> value
+// */
+// public StableObjectHash(int initialCapacity) {
+// super(initialCapacity);
+// this._hashingStrategy = this;
+// }
+//
+// /**
+// * Creates a new <code>TObjectHash</code> instance whose capacity
+// * is the next highest prime above <tt>initialCapacity + 1</tt>
+// * unless that value is already prime. Uses the specified custom
+// * hashing strategy.
+// *
+// * @param initialCapacity an <code>int</code> value
+// * @param strategy used to compute hash codes and to compare objects.
+// */
+// public StableObjectHash(int initialCapacity, TObjectHashingStrategy<T> strategy) {
+// super(initialCapacity);
+// this._hashingStrategy = strategy;
+// }
+//
+// /**
+// * Creates a new <code>TObjectHash</code> instance with a prime
+// * value at or near the specified capacity and load factor.
+// *
+// * @param initialCapacity used to find a prime capacity for the table.
+// * @param loadFactor used to calculate the threshold over which
+// * rehashing takes place.
+// */
+// public StableObjectHash(int initialCapacity, float loadFactor) {
+// super(initialCapacity, loadFactor);
+// this._hashingStrategy = this;
+// }
+//
+// /**
+// * Creates a new <code>TObjectHash</code> instance with a prime
+// * value at or near the specified capacity and load factor. Uses
+// * the specified custom hashing strategy.
+// *
+// * @param initialCapacity used to find a prime capacity for the table.
+// * @param loadFactor used to calculate the threshold over which
+// * rehashing takes place.
+// * @param strategy used to compute hash codes and to compare objects.
+// */
+// public StableObjectHash(int initialCapacity, float loadFactor, TObjectHashingStrategy<T> strategy) {
+// super(initialCapacity, loadFactor);
+// this._hashingStrategy = strategy;
+// }
+
+ /**
+ * @return a shallow clone of this collection
+ */
+ public StableObjectHash<T> clone() {
+ StableObjectHash<T> h;
+ try {
+ h = (StableObjectHash<T>)super.clone();
+ } catch (CloneNotSupportedException e) {
+ // It's supported
+ throw new Error(e);
+ }
+ h._set = (Object[])this._set.clone();
+ return h;
+ }
+
+ public int capacity() {
+ return _set.length;
+ }
+
+ protected void removeAt(int index) {
+ _set[index] = REMOVED;
+ super.removeAt(index);
+ }
+
+ /**
+ * initializes the Object set of this hash table.
+ *
+ * @param initialCapacity an <code>int</code> value
+ * @return an <code>int</code> value
+ */
+ protected int setUp(int initialCapacity) {
+ int capacity;
+
+ capacity = super.setUp(initialCapacity);
+ _set = new Object[capacity];
+ Arrays.fill(_set,FREE);
+ return capacity;
+ }
+
+ /**
+ * Executes <tt>procedure</tt> for each element in the set.
+ *
+ * @param procedure a <code>TObjectProcedure</code> value
+ * @return false if the loop over the set terminated because
+ * the procedure returned false for some value.
+ */
+ public boolean forEach(TObjectProcedure<T> procedure) {
+ Object[] set = _set;
+ for (int i = set.length; i-- > 0;) {
+ if (set[i] != FREE
+ && set[i] != REMOVED
+ && ! procedure.execute((T) set[i])) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /**
+ * Searches the set for <tt>obj</tt>
+ *
+ * @param obj an <code>Object</code> value
+ * @return a <code>boolean</code> value
+ */
+ public boolean contains(Object obj) {
+ throw new UnsupportedOperationException();
+ }
+
+ /**
+ * Locates the index of <tt>obj</tt>.
+ *
+ * @param obj an <code>Object</code> value
+ * @return the index of <tt>obj</tt> or -1 if it isn't in the set.
+ */
+ protected int index(T obj, Object[] _set) {
+
+ final Object[] set = _set;
+ final int length = set.length;
+ final int hash = obj.hashCode() & 0x7fffffff;
+ int index = hash % length;
+ Object cur = set[index];
+
+ if ( cur == FREE ) return -1;
+
+ // NOTE: here it has to be REMOVED or FULL (some user-given value)
+ if ( cur == REMOVED || !obj.equals(cur)) {
+ // see Knuth, p. 529
+ final int probe = 1 + (hash % (length - 2));
+
+ do {
+ index -= probe;
+ if (index < 0) {
+ index += length;
+ }
+ cur = set[index];
+ } while (cur != FREE
+ && (cur == REMOVED || !obj.equals(cur)));
+ }
+
+ return cur == FREE ? -1 : index;
+ }
+
+ protected int index(T obj, int hash_, Object[] _set) {
+
+ final Object[] set = _set;
+ final int length = set.length;
+ final int hash = hash_ & 0x7fffffff;
+ int index = hash % length;
+ Object cur = set[index];
+
+ if ( cur == FREE ) return -1;
+
+ // NOTE: here it has to be REMOVED or FULL (some user-given value)
+ if ( cur == REMOVED || !obj.equals(cur)) {
+ // see Knuth, p. 529
+ final int probe = 1 + (hash % (length - 2));
+
+ do {
+ index -= probe;
+ if (index < 0) {
+ index += length;
+ }
+ cur = set[index];
+ } while (cur != FREE
+ && (cur == REMOVED || !obj.equals(cur)));
+ }
+
+ return cur == FREE ? -1 : index;
+ }
+
+ /**
+ * Locates the index at which <tt>obj</tt> can be inserted. if
+ * there is already a value equal()ing <tt>obj</tt> in the set,
+ * returns that value's index as <tt>-index - 1</tt>.
+ *
+ * @param obj an <code>Object</code> value
+ * @return the index of a FREE slot at which obj can be inserted
+ * or, if obj is already stored in the hash, the negative value of
+ * that index, minus 1: -index -1.
+ */
+ protected int insertionIndex(T obj) {
+
+ final Object[] set = _set;
+ final int length = set.length;
+ final int hash = obj.hashCode() & 0x7fffffff;
+ int index = hash % length;
+ Object cur = set[index];
+
+ if (cur == FREE) {
+ return index; // empty, all done
+ } else if (cur != REMOVED && obj.equals((T) cur)) {
+ return -index -1; // already stored
+ } else { // already FULL or REMOVED, must probe
+ // compute the double hash
+ final int probe = 1 + (hash % (length - 2));
+
+ // if the slot we landed on is FULL (but not removed), probe
+ // until we find an empty slot, a REMOVED slot, or an element
+ // equal to the one we are trying to insert.
+ // finding an empty slot means that the value is not present
+ // and that we should use that slot as the insertion point;
+ // finding a REMOVED slot means that we need to keep searching,
+ // however we want to remember the offset of that REMOVED slot
+ // so we can reuse it in case a "new" insertion (i.e. not an update)
+ // is possible.
+ // finding a matching value means that we've found that our desired
+ // key is already in the table
+ if (cur != REMOVED) {
+ // starting at the natural offset, probe until we find an
+ // offset that isn't full.
+ do {
+ index -= probe;
+ if (index < 0) {
+ index += length;
+ }
+ cur = set[index];
+ } while (cur != FREE
+ && cur != REMOVED
+ && ! obj.equals((T) cur));
+ }
+
+ // if the index we found was removed: continue probing until we
+ // locate a free location or an element which equal()s the
+ // one we have.
+ if (cur == REMOVED) {
+ int firstRemoved = index;
+ while (cur != FREE
+ && (cur == REMOVED || ! obj.equals((T) cur))) {
+ index -= probe;
+ if (index < 0) {
+ index += length;
+ }
+ cur = set[index];
+ }
+ // NOTE: cur cannot == REMOVED in this block
+ return (cur != FREE) ? -index -1 : firstRemoved;
+ }
+ // if it's full, the key is already stored
+ // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
+ return (cur != FREE) ? -index -1 : index;
+ }
+ }
+
+ protected int insertionIndex(T obj, int hash_) {
+
+ final Object[] set = _set;
+ final int length = set.length;
+ final int hash = hash_ & 0x7fffffff;
+ int index = hash % length;
+ Object cur = set[index];
+
+ if (cur == FREE) {
+ return index; // empty, all done
+ } else if (cur != REMOVED && obj.equals((T) cur)) {
+ return -index -1; // already stored
+ } else { // already FULL or REMOVED, must probe
+ // compute the double hash
+ final int probe = 1 + (hash % (length - 2));
+
+ // if the slot we landed on is FULL (but not removed), probe
+ // until we find an empty slot, a REMOVED slot, or an element
+ // equal to the one we are trying to insert.
+ // finding an empty slot means that the value is not present
+ // and that we should use that slot as the insertion point;
+ // finding a REMOVED slot means that we need to keep searching,
+ // however we want to remember the offset of that REMOVED slot
+ // so we can reuse it in case a "new" insertion (i.e. not an update)
+ // is possible.
+ // finding a matching value means that we've found that our desired
+ // key is already in the table
+ if (cur != REMOVED) {
+ // starting at the natural offset, probe until we find an
+ // offset that isn't full.
+ do {
+ index -= probe;
+ if (index < 0) {
+ index += length;
+ }
+ cur = set[index];
+ } while (cur != FREE
+ && cur != REMOVED
+ && ! obj.equals((T) cur));
+ }
+
+ // if the index we found was removed: continue probing until we
+ // locate a free location or an element which equal()s the
+ // one we have.
+ if (cur == REMOVED) {
+ int firstRemoved = index;
+ while (cur != FREE
+ && (cur == REMOVED || ! obj.equals((T) cur))) {
+ index -= probe;
+ if (index < 0) {
+ index += length;
+ }
+ cur = set[index];
+ }
+ // NOTE: cur cannot == REMOVED in this block
+ return (cur != FREE) ? -index -1 : firstRemoved;
+ }
+ // if it's full, the key is already stored
+ // NOTE: cur cannot equal REMOVE here (would have retuned already (see above)
+ return (cur != FREE) ? -index -1 : index;
+ }
+ }
+
+ /**
+ * This is the default implementation of TObjectHashingStrategy:
+ * it delegates hashing to the Object's hashCode method.
+ *
+ * @param o for which the hashcode is to be computed
+ * @return the hashCode
+ * @see Object#hashCode()
+ */
+ public final int computeHashCode(T o) {
+ return o == null ? 0 : o.hashCode();
+ }
+
+ /**
+ * This is the default implementation of TObjectHashingStrategy:
+ * it delegates equality comparisons to the first parameter's
+ * equals() method.
+ *
+ * @param o1 an <code>Object</code> value
+ * @param o2 an <code>Object</code> value
+ * @return true if the objects are equal
+ * @see Object#equals(Object)
+ */
+ public final boolean equals(T o1, T o2) {
+ return o1 == null ? o2 == null : o1.equals(o2);
+ }
+
+ /**
+ * Convenience methods for subclasses to use in throwing exceptions about
+ * badly behaved user objects employed as keys. We have to throw an
+ * IllegalArgumentException with a rather verbose message telling the
+ * user that they need to fix their object implementation to conform
+ * to the general contract for java.lang.Object.
+ *
+ * @param o1 the first of the equal elements with unequal hash codes.
+ * @param o2 the second of the equal elements with unequal hash codes.
+ * @exception IllegalArgumentException the whole point of this method.
+ */
+ protected final void throwObjectContractViolation(Object o1, Object o2)
+ throws IllegalArgumentException {
+ throw new IllegalArgumentException("Equal objects must have equal hashcodes. "
+ + "During rehashing, Trove discovered that "
+ + "the following two objects claim to be "
+ + "equal (as in java.lang.Object.equals()) "
+ + "but their hashCodes (or those calculated by "
+ + "your TObjectHashingStrategy) are not equal."
+ + "This violates the general contract of "
+ + "java.lang.Object.hashCode(). See bullet point two "
+ + "in that method's documentation. "
+ + "object #1 =" + o1
+ + "; object #2 =" + o2);
+ }
+
+
+ @Override
+ public void writeExternal( ObjectOutput out ) throws IOException {
+ super.writeExternal( out );
+
+ // VERSION
+ out.writeByte( 0 );
+
+ // HASHING STRATEGY
+ out.writeObject( _hashingStrategy );
+ }
+
+ @Override
+ public void readExternal( ObjectInput in )
+ throws IOException, ClassNotFoundException {
+
+ super.readExternal( in );
+
+ // VERSION
+ in.readByte();
+
+ // HASHING STRATEGY
+ //noinspection unchecked
+ _hashingStrategy = ( HashingStrategy<T> ) in.readObject();
+ }
+} // TObjectHash
Code Review / simantics / platform.git / blobdiff