1 package org.apache.lucene.util.collections;
3 import java.util.Arrays;
6 * Licensed to the Apache Software Foundation (ASF) under one or more
7 * contributor license agreements. See the NOTICE file distributed with
8 * this work for additional information regarding copyright ownership.
9 * The ASF licenses this file to You under the Apache License, Version 2.0
10 * (the "License"); you may not use this file except in compliance with
11 * the License. You may obtain a copy of the License at
13 * http://www.apache.org/licenses/LICENSE-2.0
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
23 * An Array-based hashtable which maps primitive int to primitive int.<br>
24 * The hashtable is constracted with a given capacity, or 16 as a default. In
25 * case there's not enough room for new pairs, the hashtable grows. <br>
26 * Capacity is adjusted to a power of 2, and there are 2 * capacity entries for
29 * The pre allocated arrays (for keys, values) are at length of capacity + 1,
30 * when index 0 is used as 'Ground' or 'NULL'.<br>
32 * The arrays are allocated ahead of hash operations, and form an 'empty space'
33 * list, to which the key,value pair is allocated.
35 * @lucene.experimental
37 public class IntToIntMap {
39 public static final int GROUD = -1;
41 * Implements an IntIterator which iterates over all the allocated indexes.
43 private final class IndexIterator implements IntIterator {
45 * The last used baseHashIndex. Needed for "jumping" from one hash entry
48 private int baseHashIndex = 0;
51 * The next not-yet-visited index.
53 private int index = 0;
56 * Index of the last visited pair. Used in {@link #remove()}.
58 private int lastIndex = 0;
61 * Create the Iterator, make <code>index</code> point to the "first"
62 * index which is not empty. If such does not exist (eg. the map is
63 * empty) it would be zero.
65 public IndexIterator() {
66 for (baseHashIndex = 0; baseHashIndex < baseHash.length; ++baseHashIndex) {
67 index = baseHash[baseHashIndex];
74 public boolean hasNext() {
79 // Save the last index visited
85 // if the next index points to the 'Ground' it means we're done with
86 // the current hash entry and we need to jump to the next one. This
87 // is done until all the hash entries had been visited.
88 while (index == 0 && ++baseHashIndex < baseHash.length) {
89 index = baseHash[baseHashIndex];
95 public void remove() {
96 IntToIntMap.this.remove(keys[lastIndex]);
102 * Implements an IntIterator, used for iteration over the map's keys.
104 private final class KeyIterator implements IntIterator {
105 private IntIterator iterator = new IndexIterator();
109 public boolean hasNext() {
110 return iterator.hasNext();
114 return keys[iterator.next()];
117 public void remove() {
123 * Implements an IntIterator used for iteration over the map's values.
125 private final class ValueIterator implements IntIterator {
126 private IntIterator iterator = new IndexIterator();
130 public boolean hasNext() {
131 return iterator.hasNext();
135 return values[iterator.next()];
138 public void remove() {
144 * Default capacity - in case no capacity was specified in the constructor
146 private static int defaultCapacity = 16;
149 * Holds the base hash entries. if the capacity is 2^N, than the base hash
150 * holds 2^(N+1). It can hold
155 * The current capacity of the map. Always 2^N and never less than 16. We
156 * never use the zero index. It is needed to improve performance and is also
159 private int capacity;
161 * All objects are being allocated at map creation. Those objects are "free"
162 * or empty. Whenever a new pair comes along, a pair is being "allocated" or
163 * taken from the free-linked list. as this is just a free list.
165 private int firstEmpty;
168 * hashFactor is always (2^(N+1)) - 1. Used for faster hashing.
170 private int hashFactor;
173 * This array holds the unique keys
178 * In case of collisions, we implement a double linked list of the colliding
179 * hash's with the following next[] and prev[]. Those are also used to store
187 * Number of currently objects in the map.
192 * This array holds the values
197 * Constructs a map with default capacity.
199 public IntToIntMap() {
200 this(defaultCapacity);
204 * Constructs a map with given capacity. Capacity is adjusted to a native
205 * power of 2, with minimum of 16.
208 * minimum capacity for the map.
210 public IntToIntMap(int capacity) {
212 // Minimum capacity is 16..
213 while (this.capacity < capacity) {
214 // Multiply by 2 as long as we're still under the requested capacity
218 // As mentioned, we use the first index (0) as 'Ground', so we need the
219 // length of the arrays to be one more than the capacity
220 int arrayLength = this.capacity + 1;
222 this.values = new int[arrayLength];
223 this.keys = new int[arrayLength];
224 this.next = new int[arrayLength];
226 this.values[0] = GROUD;
228 // Hash entries are twice as big as the capacity.
229 int baseHashSize = this.capacity << 1;
231 this.baseHash = new int[baseHashSize];
233 // The has factor is 2^M - 1 which is used as an "AND" hashing operator.
234 // {@link #calcBaseHash()}
235 this.hashFactor = baseHashSize - 1;
243 * Adds a pair to the map. Takes the first empty position from the
244 * empty-linked-list's head - {@link firstEmpty}.
246 * New pairs are always inserted to baseHash, and are followed by the old
250 * integer which maps the given value
252 * value which is being mapped using the given key
254 private void prvt_put(int key, int e) {
255 // Hash entry to which the new pair would be inserted
256 int hashIndex = calcBaseHashIndex(key);
258 // 'Allocating' a pair from the "Empty" list.
259 int objectIndex = firstEmpty;
262 firstEmpty = next[firstEmpty];
263 values[objectIndex] = e;
264 keys[objectIndex] = key;
266 // Inserting the new pair as the first node in the specific hash entry
267 next[objectIndex] = baseHash[hashIndex];
268 baseHash[hashIndex] = objectIndex;
270 // Announcing a new pair was added!
275 * Calculating the baseHash index using the internal <code>hashFactor</code>.
279 protected int calcBaseHashIndex(int key) {
280 return key & hashFactor;
284 * Empties the map. Generates the "Empty" space list for later allocation.
286 public void clear() {
287 // Clears the hash entries
288 Arrays.fill(this.baseHash, 0);
293 // Mark all array entries as empty. This is done with
294 // <code>firstEmpty</code> pointing to the first valid index (1 as 0 is
295 // used as 'Ground').
298 // And setting all the <code>next[i]</code> to point at
300 for (int i = 1; i < this.capacity;) {
304 // Surly, the last one should point to the 'Ground'.
305 next[this.capacity] = 0;
309 * Checks if a given key exists in the map.
312 * that is checked against the map data.
313 * @return true if the key exists in the map. false otherwise.
315 public boolean containsKey(int key) {
316 return find(key) != 0;
320 * Checks if the given object exists in the map.<br>
321 * This method iterates over the collection, trying to find an equal object.
324 * value that is checked against the map data.
325 * @return true if the value exists in the map (in .equals() meaning).
328 public boolean containsValue(int v) {
329 for (IntIterator iterator = iterator(); iterator.hasNext();) {
330 if (v == iterator.next()) {
338 * Find the actual index of a given key.
341 * @return index of the key. zero if the key wasn't found.
343 protected int find(int key) {
344 // Calculate the hash entry.
345 int baseHashIndex = calcBaseHashIndex(key);
347 // Start from the hash entry.
348 int localIndex = baseHash[baseHashIndex];
350 // while the index does not point to the 'Ground'
351 while (localIndex != 0) {
352 // returns the index found in case of of a matching key.
353 if (keys[localIndex] == key) {
357 // next the local index
358 localIndex = next[localIndex];
361 // If we got this far, it could only mean we did not find the key we
362 // were asked for. return 'Ground' index.
367 * Find the actual index of a given key with it's baseHashIndex.<br>
368 * Some methods use the baseHashIndex. If those call {@link #find()} there's
369 * no need to re-calculate that hash.
372 * @param baseHashIndex
373 * @return the index of the given key, or 0 as 'Ground' if the key wasn't
376 private int findForRemove(int key, int baseHashIndex) {
377 // Start from the hash entry.
379 int index = baseHash[baseHashIndex];
381 // while the index does not point to the 'Ground'
383 // returns the index found in case of of a matching key.
384 if (keys[index] == key) {
388 // next the local index
393 // If we got this far, it could only mean we did not find the key we
394 // were asked for. return 'Ground' index.
400 * Returns the object mapped with the given key.
403 * int who's mapped object we're interested in.
404 * @return an object mapped by the given key. null if the key wasn't found.
406 public int get(int key) {
407 return values[find(key)];
411 * Grows the map. Allocates a new map of double the capacity, and
412 * fast-insert the old key-value pairs.
414 protected void grow() {
415 IntToIntMap that = new IntToIntMap(
418 // Iterates fast over the collection. Any valid pair is put into the new
419 // map without checking for duplicates or if there's enough space for
421 for (IndexIterator iterator = new IndexIterator(); iterator.hasNext();) {
422 int index = iterator.next();
423 that.prvt_put(this.keys[index], this.values[index]);
426 // Copy that's data into this.
427 this.capacity = that.capacity;
428 this.size = that.size;
429 this.firstEmpty = that.firstEmpty;
430 this.values = that.values;
431 this.keys = that.keys;
432 this.next = that.next;
433 this.baseHash = that.baseHash;
434 this.hashFactor = that.hashFactor;
439 * @return true if the map is empty. false otherwise.
441 public boolean isEmpty() {
446 * Returns a new iterator for the mapped objects.
448 public IntIterator iterator() {
449 return new ValueIterator();
452 /** Returns an iterator on the map keys. */
453 public IntIterator keyIterator() {
454 return new KeyIterator();
458 * Prints the baseHash array, used for debug purposes.
460 @SuppressWarnings("unused")
461 private void printBaseHash() {
462 for (int i = 0; i < this.baseHash.length; i++) {
463 System.out.println(i + ".\t" + baseHash[i]);
468 * Inserts the <key,value> pair into the map. If the key already exists,
469 * this method updates the mapped value to the given one, returning the old
472 * @return the old mapped value, or 0 if the key didn't exist.
474 public int put(int key, int e) {
476 int index = find(key);
480 // Set new data and exit.
481 int old = values[index];
486 // Is there enough room for a new pair?
487 if (size == capacity) {
492 // Now that everything is set, the pair can be just put inside with no
500 * Removes a <key,value> pair from the map and returns the mapped value,
501 * or 0 if the none existed.
503 * @param key used to find the value to remove
504 * @return the removed value or 0 if none existed.
506 public int remove(int key) {
507 int baseHashIndex = calcBaseHashIndex(key);
508 int index = findForRemove(key, baseHashIndex);
510 // If it is the first in the collision list, we should promote its
511 // next colliding element.
513 baseHash[baseHashIndex] = next[index];
516 next[prev] = next[index];
517 next[index] = firstEmpty;
520 return values[index];
527 * @return number of pairs currently in the map
534 * Translates the mapped pairs' values into an array of Objects
536 * @return an object array of all the values currently in the map.
538 public int[] toArray() {
540 int[] array = new int[size];
542 // Iterates over the values, adding them to the array.
543 for (IntIterator iterator = iterator(); iterator.hasNext();) {
544 array[++j] = iterator.next();
550 * Translates the mapped pairs' values into an array of ints
553 * the array into which the elements of the map are to be
554 * stored, if it is big enough; otherwise, a new array of the
555 * same runtime type is allocated for this purpose.
557 * @return an array containing the values stored in the map
560 public int[] toArray(int[] a) {
562 if (a.length < size) {
565 // Iterates over the values, adding them to the array.
566 for (IntIterator iterator = iterator(); j < a.length
567 && iterator.hasNext(); ++j) {
568 a[j] = iterator.next();
574 public String toString() {
575 StringBuffer sb = new StringBuffer();
577 IntIterator keyIterator = keyIterator();
578 while (keyIterator.hasNext()) {
579 int key = keyIterator.next();
583 if (keyIterator.hasNext()) {
589 return sb.toString();
593 public int hashCode() {
594 return getClass().hashCode() ^ size();
598 public boolean equals(Object o) {
599 IntToIntMap that = (IntToIntMap)o;
600 if (that.size() != this.size()) {
604 IntIterator it = keyIterator();
605 while (it.hasNext()) {
608 if (!that.containsKey(key)) {
612 int v1 = this.get(key);
613 int v2 = that.get(key);