1 package org.apache.lucene.util.collections;
3 import java.util.Arrays;
4 import java.util.Iterator;
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
14 * http://www.apache.org/licenses/LICENSE-2.0
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.
25 * An Array-based hashtable which maps primitive float to Objects of generic type
27 * The hashtable is constracted with a given capacity, or 16 as a default. In
28 * case there's not enough room for new pairs, the hashtable grows. <br>
29 * Capacity is adjusted to a power of 2, and there are 2 * capacity entries for
32 * The pre allocated arrays (for keys, values) are at length of capacity + 1,
33 * when index 0 is used as 'Ground' or 'NULL'.<br>
35 * The arrays are allocated ahead of hash operations, and form an 'empty space'
36 * list, to which the key,value pair is allocated.
38 * @lucene.experimental
40 public class FloatToObjectMap<T> implements Iterable<T> {
43 * Implements an IntIterator which iterates over all the allocated indexes.
45 private final class IndexIterator implements IntIterator {
47 * The last used baseHashIndex. Needed for "jumping" from one hash entry
50 private int baseHashIndex = 0;
53 * The next not-yet-visited index.
55 private int index = 0;
58 * Index of the last visited pair. Used in {@link #remove()}.
60 private int lastIndex = 0;
63 * Create the Iterator, make <code>index</code> point to the "first"
64 * index which is not empty. If such does not exist (eg. the map is
65 * empty) it would be zero.
67 public IndexIterator() {
68 for (baseHashIndex = 0; baseHashIndex < baseHash.length; ++baseHashIndex) {
69 index = baseHash[baseHashIndex];
76 public boolean hasNext() {
81 // Save the last index visited
87 // if the next index points to the 'Ground' it means we're done with
88 // the current hash entry and we need to jump to the next one. This
89 // is done until all the hash entries had been visited.
90 while (index == 0 && ++baseHashIndex < baseHash.length) {
91 index = baseHash[baseHashIndex];
97 public void remove() {
98 FloatToObjectMap.this.remove(keys[lastIndex]);
104 * Implements an IntIterator, used for iteration over the map's keys.
106 private final class KeyIterator implements FloatIterator {
107 private IntIterator iterator = new IndexIterator();
111 public boolean hasNext() {
112 return iterator.hasNext();
115 public float next() {
116 return keys[iterator.next()];
119 public void remove() {
125 * Implements an Iterator of a generic type T used for iteration over the
128 private final class ValueIterator implements Iterator<T> {
129 private IntIterator iterator = new IndexIterator();
133 public boolean hasNext() {
134 return iterator.hasNext();
137 @SuppressWarnings("unchecked")
139 return (T) values[iterator.next()];
142 public void remove() {
148 * Default capacity - in case no capacity was specified in the constructor
150 private static int defaultCapacity = 16;
153 * Holds the base hash entries. if the capacity is 2^N, than the base hash
154 * holds 2^(N+1). It can hold
159 * The current capacity of the map. Always 2^N and never less than 16. We
160 * never use the zero index. It is needed to improve performance and is also
163 private int capacity;
165 * All objects are being allocated at map creation. Those objects are "free"
166 * or empty. Whenever a new pair comes along, a pair is being "allocated" or
167 * taken from the free-linked list. as this is just a free list.
169 private int firstEmpty;
172 * hashFactor is always (2^(N+1)) - 1. Used for faster hashing.
174 private int hashFactor;
177 * This array holds the unique keys
182 * In case of collisions, we implement a double linked list of the colliding
183 * hash's with the following next[] and prev[]. Those are also used to store
191 * Number of currently objects in the map.
196 * This array holds the values
201 * Constructs a map with default capacity.
203 public FloatToObjectMap() {
204 this(defaultCapacity);
208 * Constructs a map with given capacity. Capacity is adjusted to a native
209 * power of 2, with minimum of 16.
212 * minimum capacity for the map.
214 public FloatToObjectMap(int capacity) {
216 // Minimum capacity is 16..
217 while (this.capacity < capacity) {
218 // Multiply by 2 as long as we're still under the requested capacity
222 // As mentioned, we use the first index (0) as 'Ground', so we need the
223 // length of the arrays to be one more than the capacity
224 int arrayLength = this.capacity + 1;
226 this.values = new Object[arrayLength];
227 this.keys = new float[arrayLength];
228 this.next = new int[arrayLength];
230 // Hash entries are twice as big as the capacity.
231 int baseHashSize = this.capacity << 1;
233 this.baseHash = new int[baseHashSize];
235 // The has factor is 2^M - 1 which is used as an "AND" hashing operator.
236 // {@link #calcBaseHash()}
237 this.hashFactor = baseHashSize - 1;
245 * Adds a pair to the map. Takes the first empty position from the
246 * empty-linked-list's head - {@link firstEmpty}.
248 * New pairs are always inserted to baseHash, and are followed by the old
252 * integer which maps the given Object
254 * element which is being mapped using the given key
256 private void prvt_put(float key, T e) {
257 // Hash entry to which the new pair would be inserted
258 int hashIndex = calcBaseHashIndex(key);
260 // 'Allocating' a pair from the "Empty" list.
261 int objectIndex = firstEmpty;
264 firstEmpty = next[firstEmpty];
265 values[objectIndex] = e;
266 keys[objectIndex] = key;
268 // Inserting the new pair as the first node in the specific hash entry
269 next[objectIndex] = baseHash[hashIndex];
270 baseHash[hashIndex] = objectIndex;
272 // Announcing a new pair was added!
277 * Calculating the baseHash index using the internal <code>hashFactor</code>.
280 protected int calcBaseHashIndex(float key) {
281 return Float.floatToIntBits(key) & hashFactor;
285 * Empties the map. Generates the "Empty" space list for later allocation.
287 public void clear() {
288 // Clears the hash entries
289 Arrays.fill(this.baseHash, 0);
294 // Mark all array entries as empty. This is done with
295 // <code>firstEmpty</code> pointing to the first valid index (1 as 0 is
296 // used as 'Ground').
299 // And setting all the <code>next[i]</code> to point at
301 for (int i = 1; i < this.capacity;) {
305 // Surly, the last one should point to the 'Ground'.
306 next[this.capacity] = 0;
310 * Checks if a given key exists in the map.
313 * that is checked against the map data.
314 * @return true if the key exists in the map. false otherwise.
316 public boolean containsKey(float key) {
317 return find(key) != 0;
321 * Checks if the given object exists in the map.<br>
322 * This method iterates over the collection, trying to find an equal object.
325 * object that is checked against the map data.
326 * @return true if the object exists in the map (in .equals() meaning).
329 public boolean containsValue(Object o) {
330 for (Iterator<T> iterator = iterator(); iterator.hasNext();) {
331 T object = iterator.next();
332 if (object.equals(o)) {
340 * Find the actual index of a given key.
343 * @return index of the key. zero if the key wasn't found.
345 protected int find(float key) {
346 // Calculate the hash entry.
347 int baseHashIndex = calcBaseHashIndex(key);
349 // Start from the hash entry.
350 int localIndex = baseHash[baseHashIndex];
352 // while the index does not point to the 'Ground'
353 while (localIndex != 0) {
354 // returns the index found in case of of a matching key.
355 if (keys[localIndex] == key) {
359 // next the local index
360 localIndex = next[localIndex];
363 // If we got this far, it could only mean we did not find the key we
364 // were asked for. return 'Ground' index.
369 * Find the actual index of a given key with it's baseHashIndex.<br>
370 * Some methods use the baseHashIndex. If those call {@link #find()} there's
371 * no need to re-calculate that hash.
374 * @param baseHashIndex
375 * @return the index of the given key, or 0 as 'Ground' if the key wasn't
378 private int findForRemove(float key, int baseHashIndex) {
379 // Start from the hash entry.
381 int index = baseHash[baseHashIndex];
383 // while the index does not point to the 'Ground'
385 // returns the index found in case of of a matching key.
386 if (keys[index] == key) {
390 // next the local index
395 // If we got this far, it could only mean we did not find the key we
396 // were asked for. return 'Ground' index.
402 * Returns the object mapped with the given key.
405 * int who's mapped object we're interested in.
406 * @return an object mapped by the given key. null if the key wasn't found.
408 @SuppressWarnings("unchecked")
409 public T get(float key) {
410 return (T) values[find(key)];
414 * Grows the map. Allocates a new map of double the capacity, and
415 * fast-insert the old key-value pairs.
417 @SuppressWarnings("unchecked")
418 protected void grow() {
419 FloatToObjectMap<T> that = new FloatToObjectMap<T>(
422 // Iterates fast over the collection. Any valid pair is put into the new
423 // map without checking for duplicates or if there's enough space for
425 for (IndexIterator iterator = new IndexIterator(); iterator.hasNext();) {
426 int index = iterator.next();
427 that.prvt_put(this.keys[index], (T) this.values[index]);
430 // Copy that's data into this.
431 this.capacity = that.capacity;
432 this.size = that.size;
433 this.firstEmpty = that.firstEmpty;
434 this.values = that.values;
435 this.keys = that.keys;
436 this.next = that.next;
437 this.baseHash = that.baseHash;
438 this.hashFactor = that.hashFactor;
443 * @return true if the map is empty. false otherwise.
445 public boolean isEmpty() {
450 * Returns a new iterator for the mapped objects.
452 public Iterator<T> iterator() {
453 return new ValueIterator();
456 /** Returns an iterator on the map keys. */
457 public FloatIterator keyIterator() {
458 return new KeyIterator();
462 * Prints the baseHash array, used for DEBUG purposes.
464 @SuppressWarnings("unused")
465 private void printBaseHash() {
466 for (int i = 0; i < this.baseHash.length; i++) {
467 System.out.println(i + ".\t" + baseHash[i]);
472 * Inserts the <key,value> pair into the map. If the key already exists,
473 * this method updates the mapped value to the given one, returning the old
476 * @return the old mapped value, or null if the key didn't exist.
478 @SuppressWarnings("unchecked")
479 public T put(float key, T e) {
481 int index = find(key);
485 // Set new data and exit.
486 T old = (T) values[index];
491 // Is there enough room for a new pair?
492 if (size == capacity) {
497 // Now that everything is set, the pair can be just put inside with no
505 * Removes a <key,value> pair from the map and returns the mapped value,
506 * or null if the none existed.
508 * @param key used to find the value to remove
509 * @return the removed value or null if none existed.
511 @SuppressWarnings("unchecked")
512 public T remove(float key) {
513 int baseHashIndex = calcBaseHashIndex(key);
514 int index = findForRemove(key, baseHashIndex);
516 // If it is the first in the collision list, we should promote its
517 // next colliding element.
519 baseHash[baseHashIndex] = next[index];
522 next[prev] = next[index];
523 next[index] = firstEmpty;
526 return (T) values[index];
533 * @return number of pairs currently in the map
540 * Translates the mapped pairs' values into an array of Objects
542 * @return an object array of all the values currently in the map.
544 public Object[] toArray() {
546 Object[] array = new Object[size];
548 // Iterates over the values, adding them to the array.
549 for (Iterator<T> iterator = iterator(); iterator.hasNext();) {
550 array[++j] = iterator.next();
556 * Translates the mapped pairs' values into an array of T
559 * the array into which the elements of the list are to be
560 * stored, if it is big enough; otherwise, use whatever space we
561 * have, setting the one after the true data as null.
563 * @return an array containing the elements of the list
566 public T[] toArray(T[] a) {
568 // Iterates over the values, adding them to the array.
569 for (Iterator<T> iterator = iterator(); j < a.length
570 && iterator.hasNext(); ++j) {
571 a[j] = iterator.next();
582 public String toString() {
583 StringBuffer sb = new StringBuffer();
585 FloatIterator keyIterator = keyIterator();
586 while (keyIterator.hasNext()) {
587 float key = keyIterator.next();
591 if (keyIterator.hasNext()) {
597 return sb.toString();
601 public int hashCode() {
602 return getClass().hashCode() ^ size();
605 @SuppressWarnings("unchecked")
607 public boolean equals(Object o) {
608 FloatToObjectMap<T> that = (FloatToObjectMap<T>)o;
609 if (that.size() != this.size()) {
613 FloatIterator it = keyIterator();
614 while (it.hasNext()) {
615 float key = it.next();
616 if (!that.containsKey(key)) {
620 T v1 = this.get(key);
621 T v2 = that.get(key);
622 if ((v1 == null && v2 != null) ||
623 (v1 != null && v2 == null) ||