lucene-java-3.5.0/lucene/contrib/facet/src/java/org/apache/lucene/util/collections/ArrayHashMap.java

   1 package org.apache.lucene.util.collections;
   2
   3 import java.util.Arrays;
   4 import java.util.Iterator;
   5
   6 /**
   7  * Licensed to the Apache Software Foundation (ASF) under one or more
   8  * contributor license agreements.  See the NOTICE file distributed with
   9  * this work for additional information regarding copyright ownership.
  10  * The ASF licenses this file to You under the Apache License, Version 2.0
  11  * (the "License"); you may not use this file except in compliance with
  12  * the License.  You may obtain a copy of the License at
  13  *
  14  *     http://www.apache.org/licenses/LICENSE-2.0
  15  *
  16  * Unless required by applicable law or agreed to in writing, software
  17  * distributed under the License is distributed on an "AS IS" BASIS,
  18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  19  * See the License for the specific language governing permissions and
  20  * limitations under the License.
  21  */
  22
  23 /**
  24  * An Array-based hashtable which maps, similar to Java's HashMap, only
  25  * performance tests showed it performs better.
  26  * <p>
  27  * The hashtable is constructed with a given capacity, or 16 as a default. In
  28  * case there's not enough room for new pairs, the hashtable grows. Capacity is
  29  * adjusted to a power of 2, and there are 2 * capacity entries for the hash.
  30  * The pre allocated arrays (for keys, values) are at length of capacity + 1,
  31  * where index 0 is used as 'Ground' or 'NULL'.
  32  * <p>
  33  * The arrays are allocated ahead of hash operations, and form an 'empty space'
  34  * list, to which the &lt;key,value&gt; pair is allocated.
  35  *
  36  * @lucene.experimental
  37  */
  38 public class ArrayHashMap<K,V> implements Iterable<V> {
  39
  40   /** Implements an IntIterator which iterates over all the allocated indexes. */
  41   private final class IndexIterator implements IntIterator {
  42     /**
  43      * The last used baseHashIndex. Needed for "jumping" from one hash entry
  44      * to another.
  45      */
  46     private int baseHashIndex = 0;
  47
  48     /** The next not-yet-visited index. */
  49     private int index = 0;
  50
  51     /** Index of the last visited pair. Used in {@link #remove()}. */
  52     private int lastIndex = 0;
  53
  54     /**
  55      * Create the Iterator, make <code>index</code> point to the "first"
  56      * index which is not empty. If such does not exist (eg. the map is
  57      * empty) it would be zero.
  58      */
  59     public IndexIterator() {
  60       for (baseHashIndex = 0; baseHashIndex < baseHash.length; ++baseHashIndex) {
  61         index = baseHash[baseHashIndex];
  62         if (index != 0) {
  63           break;
  64         }
  65       }
  66     }
  67
  68     public boolean hasNext() {
  69       return index != 0;
  70     }
  71
  72     public int next() {
  73       // Save the last index visited
  74       lastIndex = index;
  75
  76       // next the index
  77       index = next[index];
  78
  79       // if the next index points to the 'Ground' it means we're done with
  80       // the current hash entry and we need to jump to the next one. This
  81       // is done until all the hash entries had been visited.
  82       while (index == 0 && ++baseHashIndex < baseHash.length) {
  83         index = baseHash[baseHashIndex];
  84       }
  85
  86       return lastIndex;
  87     }
  88
  89     @SuppressWarnings("unchecked")
  90     public void remove() {
  91       ArrayHashMap.this.remove((K) keys[lastIndex]);
  92     }
  93
  94   }
  95
  96   /** Implements an Iterator, used for iteration over the map's keys. */
  97   private final class KeyIterator implements Iterator<K> {
  98     private IntIterator iterator = new IndexIterator();
  99
 100     KeyIterator() { }
 101
 102     public boolean hasNext() {
 103       return iterator.hasNext();
 104     }
 105
 106     @SuppressWarnings("unchecked")
 107     public K next() {
 108       return (K) keys[iterator.next()];
 109     }
 110
 111     public void remove() {
 112       iterator.remove();
 113     }
 114   }
 115
 116   /** Implements an Iterator, used for iteration over the map's values. */
 117   private final class ValueIterator implements Iterator<V> {
 118     private IntIterator iterator = new IndexIterator();
 119
 120     ValueIterator() { }
 121
 122     public boolean hasNext() {
 123       return iterator.hasNext();
 124     }
 125
 126     @SuppressWarnings("unchecked")
 127     public V next() {
 128       return (V) values[iterator.next()];
 129     }
 130
 131     public void remove() {
 132       iterator.remove();
 133     }
 134   }
 135
 136   /** Default capacity - in case no capacity was specified in the constructor */
 137   private static final int DEFAULT_CAPACITY = 16;
 138
 139   /**
 140    * Holds the base hash entries. if the capacity is 2^N, than the base hash
 141    * holds 2^(N+1).
 142    */
 143   int[] baseHash;
 144
 145   /**
 146    * The current capacity of the map. Always 2^N and never less than 16. We
 147    * never use the zero index. It is needed to improve performance and is also
 148    * used as "ground".
 149    */
 150   private int capacity;
 151
 152   /**
 153    * All objects are being allocated at map creation. Those objects are "free"
 154    * or empty. Whenever a new pair comes along, a pair is being "allocated" or
 155    * taken from the free-linked list. as this is just a free list.
 156    */
 157   private int firstEmpty;
 158
 159   /** hashFactor is always (2^(N+1)) - 1. Used for faster hashing. */
 160   private int hashFactor;
 161
 162   /** Holds the unique keys. */
 163   Object[] keys;
 164
 165   /**
 166    * In case of collisions, we implement a double linked list of the colliding
 167    * hash's with the following next[] and prev[]. Those are also used to store
 168    * the "empty" list.
 169    */
 170   int[] next;
 171
 172   private int prev;
 173
 174   /** Number of currently stored objects in the map. */
 175   private int size;
 176
 177   /** Holds the values. */
 178   Object[] values;
 179
 180   /** Constructs a map with default capacity. */
 181   public ArrayHashMap() {
 182     this(DEFAULT_CAPACITY);
 183   }
 184
 185   /**
 186    * Constructs a map with given capacity. Capacity is adjusted to a native
 187    * power of 2, with minimum of 16.
 188    *
 189    * @param capacity minimum capacity for the map.
 190    */
 191   public ArrayHashMap(int capacity) {
 192     this.capacity = 16;
 193     while (this.capacity < capacity) {
 194       // Multiply by 2 as long as we're still under the requested capacity
 195       this.capacity <<= 1;
 196     }
 197
 198     // As mentioned, we use the first index (0) as 'Ground', so we need the
 199     // length of the arrays to be one more than the capacity
 200     int arrayLength = this.capacity + 1;
 201
 202     values = new Object[arrayLength];
 203     keys = new Object[arrayLength];
 204     next = new int[arrayLength];
 205
 206     // Hash entries are twice as big as the capacity.
 207     int baseHashSize = this.capacity << 1;
 208
 209     baseHash = new int[baseHashSize];
 210
 211     // The has factor is 2^M - 1 which is used as an "AND" hashing operator.
 212     // {@link #calcBaseHash()}
 213     hashFactor = baseHashSize - 1;
 214
 215     size = 0;
 216
 217     clear();
 218   }
 219
 220   /**
 221    * Adds a pair to the map. Takes the first empty position from the
 222    * empty-linked-list's head - {@link firstEmpty}. New pairs are always
 223    * inserted to baseHash, and are followed by the old colliding pair.
 224    */
 225   private void prvt_put(K key, V value) {
 226     // Hash entry to which the new pair would be inserted
 227     int hashIndex = calcBaseHashIndex(key);
 228
 229     // 'Allocating' a pair from the "Empty" list.
 230     int objectIndex = firstEmpty;
 231
 232     // Setting data
 233     firstEmpty = next[firstEmpty];
 234     values[objectIndex] = value;
 235     keys[objectIndex] = key;
 236
 237     // Inserting the new pair as the first node in the specific hash entry
 238     next[objectIndex] = baseHash[hashIndex];
 239     baseHash[hashIndex] = objectIndex;
 240
 241     // Announcing a new pair was added!
 242     ++size;
 243   }
 244
 245   /** Calculating the baseHash index using the internal internal <code>hashFactor</code>. */
 246   protected int calcBaseHashIndex(K key) {
 247     return key.hashCode() & hashFactor;
 248   }
 249
 250   /** Empties the map. Generates the "Empty" space list for later allocation. */
 251   public void clear() {
 252     // Clears the hash entries
 253     Arrays.fill(baseHash, 0);
 254
 255     // Set size to zero
 256     size = 0;
 257
 258     // Mark all array entries as empty. This is done with
 259     // <code>firstEmpty</code> pointing to the first valid index (1 as 0 is
 260     // used as 'Ground').
 261     firstEmpty = 1;
 262
 263     // And setting all the <code>next[i]</code> to point at
 264     // <code>i+1</code>.
 265     for (int i = 1; i < capacity;) {
 266       next[i] = ++i;
 267     }
 268
 269     // Surly, the last one should point to the 'Ground'.
 270     next[capacity] = 0;
 271   }
 272
 273   /** Returns true iff the key exists in the map. */
 274   public boolean containsKey(K key) {
 275     return find(key) != 0;
 276   }
 277
 278   /** Returns true iff the object exists in the map. */
 279   public boolean containsValue(Object o) {
 280     for (Iterator<V> iterator = iterator(); iterator.hasNext();) {
 281       V object = iterator.next();
 282       if (object.equals(o)) {
 283         return true;
 284       }
 285     }
 286     return false;
 287   }
 288
 289   /** Returns the index of the given key, or zero if the key wasn't found. */
 290   protected int find(K key) {
 291     // Calculate the hash entry.
 292     int baseHashIndex = calcBaseHashIndex(key);
 293
 294     // Start from the hash entry.
 295     int localIndex = baseHash[baseHashIndex];
 296
 297     // while the index does not point to the 'Ground'
 298     while (localIndex != 0) {
 299       // returns the index found in case of of a matching key.
 300       if (keys[localIndex].equals(key)) {
 301         return localIndex;
 302       }
 303
 304       // next the local index
 305       localIndex = next[localIndex];
 306     }
 307
 308     // If we got this far, it could only mean we did not find the key we
 309     // were asked for. return 'Ground' index.
 310     return 0;
 311   }
 312
 313   /**
 314    * Finds the actual index of a given key with it's baseHashIndex. Some methods
 315    * use the baseHashIndex. If those call {@link #find()} there's no need to
 316    * re-calculate that hash.
 317    *
 318    * @return the index of the given key, or 0 if the key wasn't found.
 319    */
 320   private int findForRemove(K key, int baseHashIndex) {
 321     // Start from the hash entry.
 322     prev = 0;
 323     int index = baseHash[baseHashIndex];
 324
 325     // while the index does not point to the 'Ground'
 326     while (index != 0) {
 327       // returns the index found in case of of a matching key.
 328       if (keys[index].equals(key)) {
 329         return index;
 330       }
 331
 332       // next the local index
 333       prev = index;
 334       index = next[index];
 335     }
 336
 337     // If we got thus far, it could only mean we did not find the key we
 338     // were asked for. return 'Ground' index.
 339     return prev = 0;
 340   }
 341
 342   /** Returns the object mapped with the given key, or null if the key wasn't found. */
 343   @SuppressWarnings("unchecked")
 344   public V get(K key) {
 345     return (V) values[find(key)];
 346   }
 347
 348   /**
 349    * Allocates a new map of double the capacity, and fast-insert the old
 350    * key-value pairs.
 351    */
 352   @SuppressWarnings("unchecked")
 353   protected void grow() {
 354     ArrayHashMap<K,V> newmap = new ArrayHashMap<K,V>(capacity * 2);
 355
 356     // Iterates fast over the collection. Any valid pair is put into the new
 357     // map without checking for duplicates or if there's enough space for
 358     // it.
 359     for (IndexIterator iterator = new IndexIterator(); iterator.hasNext();) {
 360       int index = iterator.next();
 361       newmap.prvt_put((K) keys[index], (V) values[index]);
 362     }
 363
 364     // Copy that's data into this.
 365     capacity = newmap.capacity;
 366     size = newmap.size;
 367     firstEmpty = newmap.firstEmpty;
 368     values = newmap.values;
 369     keys = newmap.keys;
 370     next = newmap.next;
 371     baseHash = newmap.baseHash;
 372     hashFactor = newmap.hashFactor;
 373   }
 374
 375   /** Returns true iff the map is empty. */
 376   public boolean isEmpty() {
 377     return size == 0;
 378   }
 379
 380   /** Returns an iterator on the mapped objects. */
 381   public Iterator<V> iterator() {
 382     return new ValueIterator();
 383   }
 384
 385   /** Returns an iterator on the map keys. */
 386   public Iterator<K> keyIterator() {
 387     return new KeyIterator();
 388   }
 389
 390   /** Prints the baseHash array, used for debugging purposes. */
 391   @SuppressWarnings("unused")
 392   private void printBaseHash() {
 393     for (int i : baseHash) {
 394       System.out.println(i + ".\t" + i);
 395     }
 396   }
 397
 398   /**
 399    * Inserts the &lt;key,value&gt; pair into the map. If the key already exists,
 400    * this method updates the mapped value to the given one, returning the old
 401    * mapped value.
 402    *
 403    * @return the old mapped value, or null if the key didn't exist.
 404    */
 405   @SuppressWarnings("unchecked")
 406   public V put(K key, V e) {
 407     // Does key exists?
 408     int index = find(key);
 409
 410     // Yes!
 411     if (index != 0) {
 412       // Set new data and exit.
 413       V old = (V) values[index];
 414       values[index] = e;
 415       return old;
 416     }
 417
 418     // Is there enough room for a new pair?
 419     if (size == capacity) {
 420       // No? Than grow up!
 421       grow();
 422     }
 423
 424     // Now that everything is set, the pair can be just put inside with no
 425     // worries.
 426     prvt_put(key, e);
 427
 428     return null;
 429   }
 430
 431   /**
 432    * Removes a &lt;key,value&gt; pair from the map and returns the mapped value,
 433    * or null if the none existed.
 434    *
 435    * @param key used to find the value to remove
 436    * @return the removed value or null if none existed.
 437    */
 438   @SuppressWarnings("unchecked")
 439   public V remove(K key) {
 440     int baseHashIndex = calcBaseHashIndex(key);
 441     int index = findForRemove(key, baseHashIndex);
 442     if (index != 0) {
 443       // If it is the first in the collision list, we should promote its
 444       // next colliding element.
 445       if (prev == 0) {
 446         baseHash[baseHashIndex] = next[index];
 447       }
 448
 449       next[prev] = next[index];
 450       next[index] = firstEmpty;
 451       firstEmpty = index;
 452       --size;
 453       return (V) values[index];
 454     }
 455
 456     return null;
 457   }
 458
 459   /** Returns number of pairs currently in the map. */
 460   public int size() {
 461     return this.size;
 462   }
 463
 464   /**
 465    * Translates the mapped pairs' values into an array of Objects
 466    *
 467    * @return an object array of all the values currently in the map.
 468    */
 469   public Object[] toArray() {
 470     int j = -1;
 471     Object[] array = new Object[size];
 472
 473     // Iterates over the values, adding them to the array.
 474     for (Iterator<V> iterator = iterator(); iterator.hasNext();) {
 475       array[++j] = iterator.next();
 476     }
 477     return array;
 478   }
 479
 480   /**
 481    * Translates the mapped pairs' values into an array of V
 482    *
 483    * @param a the array into which the elements of the list are to be stored, if
 484    *        it is big enough; otherwise, use as much space as it can.
 485    * @return an array containing the elements of the list
 486    */
 487   public V[] toArray(V[] a) {
 488     int j = 0;
 489     // Iterates over the values, adding them to the array.
 490     for (Iterator<V> iterator = iterator(); j < a.length
 491     && iterator.hasNext(); ++j) {
 492       a[j] = iterator.next();
 493     }
 494     if (j < a.length) {
 495       a[j] = null;
 496     }
 497
 498     return a;
 499   }
 500
 501   @Override
 502   public String toString() {
 503     StringBuffer sb = new StringBuffer();
 504     sb.append('{');
 505     Iterator<K> keyIterator = keyIterator();
 506     while (keyIterator.hasNext()) {
 507       K key = keyIterator.next();
 508       sb.append(key);
 509       sb.append('=');
 510       sb.append(get(key));
 511       if (keyIterator.hasNext()) {
 512         sb.append(',');
 513         sb.append(' ');
 514       }
 515     }
 516     sb.append('}');
 517     return sb.toString();
 518   }
 519
 520   @Override
 521   public int hashCode() {
 522     return getClass().hashCode() ^ size();
 523   }
 524
 525   @SuppressWarnings("unchecked")
 526   @Override
 527   public boolean equals(Object o) {
 528     ArrayHashMap<K, V> that = (ArrayHashMap<K,V>)o;
 529     if (that.size() != this.size()) {
 530       return false;
 531     }
 532
 533     Iterator<K> it = keyIterator();
 534     while (it.hasNext()) {
 535       K key = it.next();
 536       V v1 = this.get(key);
 537       V v2 = that.get(key);
 538       if ((v1 == null && v2 != null) ||
 539           (v1 != null && v2 == null) ||
 540           (!v1.equals(v2))) {
 541         return false;
 542       }
 543     }
 544     return true;
 545   }
 546 }