bundles/org.simantics.scenegraph/src/gnu/trove/TIntHash.java

   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 //////////////////////////////////////////////////
  22 // THIS IS A GENERATED CLASS. DO NOT HAND EDIT! //
  23 //////////////////////////////////////////////////
  24
  25
  26 /**
  27  * An open addressed hashing implementation for int primitives.
  28  *
  29  * Created: Sun Nov  4 08:56:06 2001
  30  *
  31  * @author Eric D. Friedman
  32  * @version $Id: PHash.template,v 1.2 2007/06/29 22:39:46 robeden Exp $
  33  */
  34
  35 abstract public class TIntHash extends TPrimitiveHash implements TIntHashingStrategy {
  36
  37     /** the set of ints */
  38     protected transient int[] _set;
  39
  40     /** strategy used to hash values in this collection */
  41     protected TIntHashingStrategy _hashingStrategy;
  42
  43     /**
  44      * Creates a new <code>TIntHash</code> instance with the default
  45      * capacity and load factor.
  46      */
  47     public TIntHash() {
  48         super();
  49         this._hashingStrategy = this;
  50     }
  51
  52     /**
  53      * Creates a new <code>TIntHash</code> instance whose capacity
  54      * is the next highest prime above <tt>initialCapacity + 1</tt>
  55      * unless that value is already prime.
  56      *
  57      * @param initialCapacity an <code>int</code> value
  58      */
  59     public TIntHash(int initialCapacity) {
  60         super(initialCapacity);
  61         this._hashingStrategy = this;
  62     }
  63
  64     /**
  65      * Creates a new <code>TIntHash</code> instance with a prime
  66      * value at or near the specified capacity and load factor.
  67      *
  68      * @param initialCapacity used to find a prime capacity for the table.
  69      * @param loadFactor used to calculate the threshold over which
  70      * rehashing takes place.
  71      */
  72     public TIntHash(int initialCapacity, float loadFactor) {
  73         super(initialCapacity, loadFactor);
  74         this._hashingStrategy = this;
  75     }
  76
  77     /**
  78      * Creates a new <code>TIntHash</code> instance with the default
  79      * capacity and load factor.
  80      * @param strategy used to compute hash codes and to compare keys.
  81      */
  82     public TIntHash(TIntHashingStrategy strategy) {
  83         super();
  84         this._hashingStrategy = strategy;
  85     }
  86
  87     /**
  88      * Creates a new <code>TIntHash</code> instance whose capacity
  89      * is the next highest prime above <tt>initialCapacity + 1</tt>
  90      * unless that value is already prime.
  91      *
  92      * @param initialCapacity an <code>int</code> value
  93      * @param strategy used to compute hash codes and to compare keys.
  94      */
  95     public TIntHash(int initialCapacity, TIntHashingStrategy strategy) {
  96         super(initialCapacity);
  97         this._hashingStrategy = strategy;
  98     }
  99
 100     /**
 101      * Creates a new <code>TIntHash</code> instance with a prime
 102      * value at or near the specified capacity and load factor.
 103      *
 104      * @param initialCapacity used to find a prime capacity for the table.
 105      * @param loadFactor used to calculate the threshold over which
 106      * rehashing takes place.
 107      * @param strategy used to compute hash codes and to compare keys.
 108      */
 109     public TIntHash(int initialCapacity, float loadFactor, TIntHashingStrategy strategy) {
 110         super(initialCapacity, loadFactor);
 111         this._hashingStrategy = strategy;
 112     }
 113
 114     /**
 115      * @return a deep clone of this collection
 116      */
 117     public Object clone() {
 118         TIntHash h = (TIntHash)super.clone();
 119         h._set = (int[])this._set.clone();
 120         return h;
 121     }
 122
 123     /**
 124      * initializes the hashtable to a prime capacity which is at least
 125      * <tt>initialCapacity + 1</tt>.
 126      *
 127      * @param initialCapacity an <code>int</code> value
 128      * @return the actual capacity chosen
 129      */
 130     protected int setUp(int initialCapacity) {
 131         int capacity;
 132
 133         capacity = super.setUp(initialCapacity);
 134         _set = new int[capacity];
 135         return capacity;
 136     }
 137
 138     /**
 139      * Searches the set for <tt>val</tt>
 140      *
 141      * @param val an <code>int</code> value
 142      * @return a <code>boolean</code> value
 143      */
 144     public boolean contains(int val) {
 145         return index(val) >= 0;
 146     }
 147
 148     /**
 149      * Executes <tt>procedure</tt> for each element in the set.
 150      *
 151      * @param procedure a <code>TObjectProcedure</code> value
 152      * @return false if the loop over the set terminated because
 153      * the procedure returned false for some value.
 154      */
 155     public boolean forEach(TIntProcedure procedure) {
 156         byte[] states = _states;
 157         int[] set = _set;
 158         for (int i = set.length; i-- > 0;) {
 159             if (states[i] == FULL && ! procedure.execute(set[i])) {
 160                 return false;
 161             }
 162         }
 163         return true;
 164     }
 165
 166     /**
 167      * Releases the element currently stored at <tt>index</tt>.
 168      *
 169      * @param index an <code>int</code> value
 170      */
 171     protected void removeAt(int index) {
 172         _set[index] = (int)0;
 173         super.removeAt(index);
 174     }
 175
 176     /**
 177      * Locates the index of <tt>val</tt>.
 178      *
 179      * @param val an <code>int</code> value
 180      * @return the index of <tt>val</tt> or -1 if it isn't in the set.
 181      */
 182     protected int index(int val) {
 183         int hash, probe, index, length;
 184
 185         final byte[] states = _states;
 186         final int[] set = _set;
 187         length = states.length;
 188         hash = _hashingStrategy.computeHashCode(val) & 0x7fffffff;
 189         index = hash % length;
 190
 191         if (states[index] != FREE &&
 192             (states[index] == REMOVED || set[index] != val)) {
 193             // see Knuth, p. 529
 194             probe = 1 + (hash % (length - 2));
 195
 196             do {
 197                 index -= probe;
 198                 if (index < 0) {
 199                     index += length;
 200                 }
 201             } while (states[index] != FREE &&
 202                      (states[index] == REMOVED || set[index] != val));
 203         }
 204
 205         return states[index] == FREE ? -1 : index;
 206     }
 207
 208     /**
 209      * Locates the index at which <tt>val</tt> can be inserted.  if
 210      * there is already a value equal()ing <tt>val</tt> in the set,
 211      * returns that value as a negative integer.
 212      *
 213      * @param val an <code>int</code> value
 214      * @return an <code>int</code> value
 215      */
 216     protected int insertionIndex(int val) {
 217         int hash, probe, index, length;
 218
 219         final byte[] states = _states;
 220         final int[] set = _set;
 221         length = states.length;
 222         hash = _hashingStrategy.computeHashCode(val) & 0x7fffffff;
 223         index = hash % length;
 224
 225         if (states[index] == FREE) {
 226             return index;       // empty, all done
 227         } else if (states[index] == FULL && set[index] == val) {
 228             return -index -1;   // already stored
 229         } else {                // already FULL or REMOVED, must probe
 230             // compute the double hash
 231             probe = 1 + (hash % (length - 2));
 232
 233             // if the slot we landed on is FULL (but not removed), probe
 234             // until we find an empty slot, a REMOVED slot, or an element
 235             // equal to the one we are trying to insert.
 236             // finding an empty slot means that the value is not present
 237             // and that we should use that slot as the insertion point;
 238             // finding a REMOVED slot means that we need to keep searching,
 239             // however we want to remember the offset of that REMOVED slot
 240             // so we can reuse it in case a "new" insertion (i.e. not an update)
 241             // is possible.
 242             // finding a matching value means that we've found that our desired
 243             // key is already in the table
 244
 245             if (states[index] != REMOVED) {
 246                                 // starting at the natural offset, probe until we find an
 247                                 // offset that isn't full.
 248                                 do {
 249                                         index -= probe;
 250                                         if (index < 0) {
 251                                                 index += length;
 252                                         }
 253                                 } while (states[index] == FULL && set[index] != val);
 254             }
 255
 256             // if the index we found was removed: continue probing until we
 257             // locate a free location or an element which equal()s the
 258             // one we have.
 259             if (states[index] == REMOVED) {
 260                 int firstRemoved = index;
 261                 while (states[index] != FREE &&
 262                        (states[index] == REMOVED || set[index] != val)) {
 263                     index -= probe;
 264                     if (index < 0) {
 265                         index += length;
 266                     }
 267                 }
 268                 return states[index] == FULL ? -index -1 : firstRemoved;
 269             }
 270             // if it's full, the key is already stored
 271             return states[index] == FULL ? -index -1 : index;
 272         }
 273     }
 274
 275     /**
 276      * Default implementation of TIntHashingStrategy:
 277      * delegates hashing to HashFunctions.hash(int).
 278      *
 279      * @param val the value to hash
 280      * @return the hashcode.
 281      */
 282     public final int computeHashCode(int val) {
 283         return HashFunctions.hash(val);
 284     }
 285 } // TIntHash