← Back to branch summary

~slub.team/goobi-indexserver/3.x

« back to all changes in this revision

Viewing changes to lucene/contrib/facet/src/java/org/apache/lucene/util/collections/FloatToObjectMap.java

  • Committer: Sebastian Meyer
  • Date: 2012-08-03 09:12:40 UTC
  • Revision ID: sebastian.meyer@slub-dresden.de-20120803091240-x6861b0vabq1xror
https://launchpad.net/bugs/985487
Remove Lucene and Solr source code and add patches instead
Fix Bug #985487: Auto-suggestion for the search interface

Show diffs side-by-side

added added

removed removed

Lines of Context:
lucene/contrib/facet/src/java/org/apache/lucene/util/collections/FloatToObjectMap.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
 
 
25
 
 * An Array-based hashtable which maps primitive float to Objects of generic type
26
 
 * T.<br>
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
30
 
 * the hash.
31
 
 * 
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>
34
 
 * 
35
 
 * The arrays are allocated ahead of hash operations, and form an 'empty space'
36
 
 * list, to which the key,value pair is allocated.
37
 
 * 
38
 
 * @lucene.experimental
39
 
 */
40
 
public class FloatToObjectMap<T> implements Iterable<T> {
41
 
 
42
 
  /**
43
 
   * Implements an IntIterator which iterates over all the allocated indexes.
44
 
   */
45
 
  private final class IndexIterator implements IntIterator {
46
 
    /**
47
 
     * The last used baseHashIndex. Needed for "jumping" from one hash entry
48
 
     * to another.
49
 
     */
50
 
    private int baseHashIndex = 0;
51
 
 
52
 
    /**
53
 
     * The next not-yet-visited index.
54
 
     */
55
 
    private int index = 0;
56
 
 
57
 
    /**
58
 
     * Index of the last visited pair. Used in {@link #remove()}.
59
 
     */
60
 
    private int lastIndex = 0;
61
 
 
62
 
    /**
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.
66
 
     */
67
 
    public IndexIterator() {
68
 
      for (baseHashIndex = 0; baseHashIndex < baseHash.length; ++baseHashIndex) {
69
 
        index = baseHash[baseHashIndex];
70
 
        if (index != 0) {
71
 
          break;
72
 
        }
73
 
      }
74
 
    }
75
 
 
76
 
    public boolean hasNext() {
77
 
      return (index != 0);
78
 
    }
79
 
 
80
 
    public int next() {
81
 
      // Save the last index visited
82
 
      lastIndex = index;
83
 
 
84
 
      // next the index
85
 
      index = next[index];
86
 
 
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];
92
 
      }
93
 
 
94
 
      return lastIndex;
95
 
    }
96
 
 
97
 
    public void remove() {
98
 
      FloatToObjectMap.this.remove(keys[lastIndex]);
99
 
    }
100
 
 
101
 
  }
102
 
 
103
 
  /**
104
 
   * Implements an IntIterator, used for iteration over the map's keys.
105
 
   */
106
 
  private final class KeyIterator implements FloatIterator {
107
 
    private IntIterator iterator = new IndexIterator();
108
 
 
109
 
    KeyIterator() { }
110
 
 
111
 
    public boolean hasNext() {
112
 
      return iterator.hasNext();
113
 
    }
114
 
 
115
 
    public float next() {
116
 
      return keys[iterator.next()];
117
 
    }
118
 
 
119
 
    public void remove() {
120
 
      iterator.remove();
121
 
    }
122
 
  }
123
 
 
124
 
  /**
125
 
   * Implements an Iterator of a generic type T used for iteration over the
126
 
   * map's values.
127
 
   */
128
 
  private final class ValueIterator implements Iterator<T> {
129
 
    private IntIterator iterator = new IndexIterator();
130
 
 
131
 
    ValueIterator() { }
132
 
 
133
 
    public boolean hasNext() {
134
 
      return iterator.hasNext();
135
 
    }
136
 
 
137
 
    @SuppressWarnings("unchecked")
138
 
    public T next() {
139
 
      return (T) values[iterator.next()];
140
 
    }
141
 
 
142
 
    public void remove() {
143
 
      iterator.remove();
144
 
    }
145
 
  }
146
 
 
147
 
  /**
148
 
   * Default capacity - in case no capacity was specified in the constructor
149
 
   */
150
 
  private static int defaultCapacity = 16;
151
 
 
152
 
  /**
153
 
   * Holds the base hash entries. if the capacity is 2^N, than the base hash
154
 
   * holds 2^(N+1). It can hold
155
 
   */
156
 
  int[] baseHash;
157
 
 
158
 
  /**
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
161
 
   * used as "ground".
162
 
   */
163
 
  private int capacity;
164
 
  /**
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.
168
 
   */
169
 
  private int firstEmpty;
170
 
 
171
 
  /**
172
 
   * hashFactor is always (2^(N+1)) - 1. Used for faster hashing.
173
 
   */
174
 
  private int hashFactor;
175
 
 
176
 
  /**
177
 
   * This array holds the unique keys
178
 
   */
179
 
  float[] keys;
180
 
 
181
 
  /**
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
184
 
   * the "empty" list.
185
 
   */
186
 
  int[] next;
187
 
 
188
 
  private int prev;
189
 
 
190
 
  /**
191
 
   * Number of currently objects in the map.
192
 
   */
193
 
  private int size;
194
 
 
195
 
  /**
196
 
   * This array holds the values
197
 
   */
198
 
  Object[] values;
199
 
 
200
 
  /**
201
 
   * Constructs a map with default capacity.
202
 
   */
203
 
  public FloatToObjectMap() {
204
 
    this(defaultCapacity);
205
 
  }
206
 
 
207
 
  /**
208
 
   * Constructs a map with given capacity. Capacity is adjusted to a native
209
 
   * power of 2, with minimum of 16.
210
 
   * 
211
 
   * @param capacity
212
 
   *            minimum capacity for the map.
213
 
   */
214
 
  public FloatToObjectMap(int capacity) {
215
 
    this.capacity = 16;
216
 
    // Minimum capacity is 16..
217
 
    while (this.capacity < capacity) {
218
 
      // Multiply by 2 as long as we're still under the requested capacity
219
 
      this.capacity <<= 1;
220
 
    }
221
 
 
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;
225
 
 
226
 
    this.values = new Object[arrayLength];
227
 
    this.keys = new float[arrayLength];
228
 
    this.next = new int[arrayLength];
229
 
 
230
 
    // Hash entries are twice as big as the capacity.
231
 
    int baseHashSize = this.capacity << 1;
232
 
 
233
 
    this.baseHash = new int[baseHashSize];
234
 
 
235
 
    // The has factor is 2^M - 1 which is used as an "AND" hashing operator.
236
 
    // {@link #calcBaseHash()}
237
 
    this.hashFactor = baseHashSize - 1;
238
 
 
239
 
    this.size = 0;
240
 
 
241
 
    clear();
242
 
  }
243
 
 
244
 
  /**
245
 
   * Adds a pair to the map. Takes the first empty position from the
246
 
   * empty-linked-list's head - {@link firstEmpty}.
247
 
   * 
248
 
   * New pairs are always inserted to baseHash, and are followed by the old
249
 
   * colliding pair.
250
 
   * 
251
 
   * @param key
252
 
   *            integer which maps the given Object
253
 
   * @param e
254
 
   *            element which is being mapped using the given key
255
 
   */
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);
259
 
 
260
 
    // 'Allocating' a pair from the "Empty" list.
261
 
    int objectIndex = firstEmpty;
262
 
 
263
 
    // Setting data
264
 
    firstEmpty = next[firstEmpty];
265
 
    values[objectIndex] = e;
266
 
    keys[objectIndex] = key;
267
 
 
268
 
    // Inserting the new pair as the first node in the specific hash entry
269
 
    next[objectIndex] = baseHash[hashIndex];
270
 
    baseHash[hashIndex] = objectIndex;
271
 
 
272
 
    // Announcing a new pair was added!
273
 
    ++size;
274
 
  }
275
 
 
276
 
  /**
277
 
   * Calculating the baseHash index using the internal <code>hashFactor</code>.
278
 
   * @param key
279
 
   */
280
 
  protected int calcBaseHashIndex(float key) {
281
 
    return Float.floatToIntBits(key) & hashFactor;
282
 
  }
283
 
 
284
 
  /**
285
 
   * Empties the map. Generates the "Empty" space list for later allocation.
286
 
   */
287
 
  public void clear() {
288
 
    // Clears the hash entries
289
 
    Arrays.fill(this.baseHash, 0);
290
 
 
291
 
    // Set size to zero
292
 
    size = 0;
293
 
 
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').
297
 
    firstEmpty = 1;
298
 
 
299
 
    // And setting all the <code>next[i]</code> to point at
300
 
    // <code>i+1</code>.
301
 
    for (int i = 1; i < this.capacity;) {
302
 
      next[i] = ++i;
303
 
    }
304
 
 
305
 
    // Surly, the last one should point to the 'Ground'.
306
 
    next[this.capacity] = 0;
307
 
  }
308
 
 
309
 
  /**
310
 
   * Checks if a given key exists in the map.
311
 
   * 
312
 
   * @param key
313
 
   *            that is checked against the map data.
314
 
   * @return true if the key exists in the map. false otherwise.
315
 
   */
316
 
  public boolean containsKey(float key) {
317
 
    return find(key) != 0;
318
 
  }
319
 
 
320
 
  /**
321
 
   * Checks if the given object exists in the map.<br>
322
 
   * This method iterates over the collection, trying to find an equal object.
323
 
   * 
324
 
   * @param o
325
 
   *            object that is checked against the map data.
326
 
   * @return true if the object exists in the map (in .equals() meaning).
327
 
   *         false otherwise.
328
 
   */
329
 
  public boolean containsValue(Object o) {
330
 
    for (Iterator<T> iterator = iterator(); iterator.hasNext();) {
331
 
      T object = iterator.next();
332
 
      if (object.equals(o)) {
333
 
        return true;
334
 
      }
335
 
    }
336
 
    return false;
337
 
  }
338
 
 
339
 
  /**
340
 
   * Find the actual index of a given key.
341
 
   * 
342
 
   * @param key
343
 
   * @return index of the key. zero if the key wasn't found.
344
 
   */
345
 
  protected int find(float key) {
346
 
    // Calculate the hash entry.
347
 
    int baseHashIndex = calcBaseHashIndex(key);
348
 
 
349
 
    // Start from the hash entry.
350
 
    int localIndex = baseHash[baseHashIndex];
351
 
 
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) {
356
 
        return localIndex;
357
 
      }
358
 
 
359
 
      // next the local index
360
 
      localIndex = next[localIndex];
361
 
    }
362
 
 
363
 
    // If we got this far, it could only mean we did not find the key we
364
 
    // were asked for. return 'Ground' index.
365
 
    return 0;
366
 
  }
367
 
 
368
 
  /**
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.
372
 
   * 
373
 
   * @param key
374
 
   * @param baseHashIndex
375
 
   * @return the index of the given key, or 0 as 'Ground' if the key wasn't
376
 
   *         found.
377
 
   */
378
 
  private int findForRemove(float key, int baseHashIndex) {
379
 
    // Start from the hash entry.
380
 
    this.prev = 0;
381
 
    int index = baseHash[baseHashIndex];
382
 
 
383
 
    // while the index does not point to the 'Ground'
384
 
    while (index != 0) {
385
 
      // returns the index found in case of of a matching key.
386
 
      if (keys[index] == key) {
387
 
        return index;
388
 
      }
389
 
 
390
 
      // next the local index
391
 
      prev = index;
392
 
      index = next[index];
393
 
    }
394
 
 
395
 
    // If we got this far, it could only mean we did not find the key we
396
 
    // were asked for. return 'Ground' index.
397
 
    this.prev = 0;
398
 
    return 0;
399
 
  }
400
 
 
401
 
  /**
402
 
   * Returns the object mapped with the given key.
403
 
   * 
404
 
   * @param 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.
407
 
   */
408
 
  @SuppressWarnings("unchecked")
409
 
  public T get(float key) {
410
 
    return (T) values[find(key)];
411
 
  }
412
 
 
413
 
  /**
414
 
   * Grows the map. Allocates a new map of double the capacity, and
415
 
   * fast-insert the old key-value pairs.
416
 
   */
417
 
  @SuppressWarnings("unchecked")
418
 
  protected void grow() {
419
 
    FloatToObjectMap<T> that = new FloatToObjectMap<T>(
420
 
        this.capacity * 2);
421
 
 
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
424
 
    // it.
425
 
    for (IndexIterator iterator = new IndexIterator(); iterator.hasNext();) {
426
 
      int index = iterator.next();
427
 
      that.prvt_put(this.keys[index], (T) this.values[index]);
428
 
    }
429
 
 
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;
439
 
  }
440
 
 
441
 
  /**
442
 
   * 
443
 
   * @return true if the map is empty. false otherwise.
444
 
   */
445
 
  public boolean isEmpty() {
446
 
    return size == 0;
447
 
  }
448
 
 
449
 
  /**
450
 
   * Returns a new iterator for the mapped objects.
451
 
   */
452
 
  public Iterator<T> iterator() {
453
 
    return new ValueIterator();
454
 
  }
455
 
 
456
 
  /** Returns an iterator on the map keys. */
457
 
  public FloatIterator keyIterator() {
458
 
    return new KeyIterator();
459
 
  }
460
 
 
461
 
  /**
462
 
   * Prints the baseHash array, used for DEBUG purposes.
463
 
   */
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]);
468
 
    }
469
 
  }
470
 
 
471
 
  /**
472
 
   * Inserts the &lt;key,value&gt; pair into the map. If the key already exists,
473
 
   * this method updates the mapped value to the given one, returning the old
474
 
   * mapped value.
475
 
   * 
476
 
   * @return the old mapped value, or null if the key didn't exist.
477
 
   */
478
 
  @SuppressWarnings("unchecked")
479
 
  public T put(float key, T e) {
480
 
    // Does key exists?
481
 
    int index = find(key);
482
 
 
483
 
    // Yes!
484
 
    if (index != 0) {
485
 
      // Set new data and exit.
486
 
      T old = (T) values[index];
487
 
      values[index] = e;
488
 
      return old;
489
 
    }
490
 
 
491
 
    // Is there enough room for a new pair?
492
 
    if (size == capacity) {
493
 
      // No? Than grow up!
494
 
      grow();
495
 
    }
496
 
 
497
 
    // Now that everything is set, the pair can be just put inside with no
498
 
    // worries.
499
 
    prvt_put(key, e);
500
 
 
501
 
    return null;
502
 
  }
503
 
 
504
 
  /**
505
 
   * Removes a &lt;key,value&gt; pair from the map and returns the mapped value,
506
 
   * or null if the none existed.
507
 
   * 
508
 
   * @param key used to find the value to remove
509
 
   * @return the removed value or null if none existed.
510
 
   */
511
 
  @SuppressWarnings("unchecked")
512
 
  public T remove(float key) {
513
 
    int baseHashIndex = calcBaseHashIndex(key);
514
 
    int index = findForRemove(key, baseHashIndex);
515
 
    if (index != 0) {
516
 
      // If it is the first in the collision list, we should promote its
517
 
      // next colliding element.
518
 
      if (prev == 0) {
519
 
        baseHash[baseHashIndex] = next[index];
520
 
      }
521
 
 
522
 
      next[prev] = next[index];
523
 
      next[index] = firstEmpty;
524
 
      firstEmpty = index;
525
 
      --size;
526
 
      return (T) values[index];
527
 
    }
528
 
 
529
 
    return null;
530
 
  }
531
 
 
532
 
  /**
533
 
   * @return number of pairs currently in the map
534
 
   */
535
 
  public int size() {
536
 
    return this.size;
537
 
  }
538
 
 
539
 
  /**
540
 
   * Translates the mapped pairs' values into an array of Objects
541
 
   * 
542
 
   * @return an object array of all the values currently in the map.
543
 
   */
544
 
  public Object[] toArray() {
545
 
    int j = -1;
546
 
    Object[] array = new Object[size];
547
 
 
548
 
    // Iterates over the values, adding them to the array.
549
 
    for (Iterator<T> iterator = iterator(); iterator.hasNext();) {
550
 
      array[++j] = iterator.next();
551
 
    }
552
 
    return array;
553
 
  }
554
 
 
555
 
  /**
556
 
   * Translates the mapped pairs' values into an array of T
557
 
   * 
558
 
   * @param a
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.
562
 
   * 
563
 
   * @return an array containing the elements of the list
564
 
   * 
565
 
   */
566
 
  public T[] toArray(T[] a) {
567
 
    int j = 0;
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();
572
 
    }
573
 
 
574
 
    if (j < a.length) {
575
 
      a[j] = null;
576
 
    }
577
 
 
578
 
    return a;
579
 
  }
580
 
 
581
 
  @Override
582
 
  public String toString() {
583
 
    StringBuffer sb = new StringBuffer();
584
 
    sb.append('{');
585
 
    FloatIterator keyIterator = keyIterator();
586
 
    while (keyIterator.hasNext()) {
587
 
      float key = keyIterator.next();
588
 
      sb.append(key);
589
 
      sb.append('=');
590
 
      sb.append(get(key));
591
 
      if (keyIterator.hasNext()) {
592
 
        sb.append(',');
593
 
        sb.append(' ');
594
 
      }
595
 
    }
596
 
    sb.append('}');
597
 
    return sb.toString();
598
 
  }
599
 
 
600
 
  @Override
601
 
  public int hashCode() {
602
 
    return getClass().hashCode() ^ size();
603
 
  }
604
 
 
605
 
  @SuppressWarnings("unchecked")
606
 
  @Override
607
 
  public boolean equals(Object o) {
608
 
    FloatToObjectMap<T> that = (FloatToObjectMap<T>)o;
609
 
    if (that.size() != this.size()) {
610
 
      return false;
611
 
    }
612
 
 
613
 
    FloatIterator it = keyIterator();
614
 
    while (it.hasNext()) {
615
 
      float key = it.next();
616
 
      if (!that.containsKey(key)) {
617
 
        return false;
618
 
      }
619
 
 
620
 
      T v1 = this.get(key);
621
 
      T v2 = that.get(key);
622
 
      if ((v1 == null && v2 != null) ||
623
 
          (v1 != null && v2 == null) ||
624
 
          (!v1.equals(v2))) {
625
 
        return false;
626
 
      }
627
 
    }
628
 
    return true;
629
 
  }
630
 
}
 
 
b'\\ No newline at end of file'