← Back to branch summary

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

« back to all changes in this revision

Viewing changes to lucene/contrib/grouping/src/java/org/apache/lucene/search/grouping/SentinelIntSet.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/grouping/src/java/org/apache/lucene/search/grouping/SentinelIntSet.java
1
 
/**
2
 
 * Licensed to the Apache Software Foundation (ASF) under one or more
3
 
 * contributor license agreements.  See the NOTICE file distributed with
4
 
 * this work for additional information regarding copyright ownership.
5
 
 * The ASF licenses this file to You under the Apache License, Version 2.0
6
 
 * (the "License"); you may not use this file except in compliance with
7
 
 * the License.  You may obtain a copy of the License at
8
 
 *
9
 
 *     http://www.apache.org/licenses/LICENSE-2.0
10
 
 *
11
 
 * Unless required by applicable law or agreed to in writing, software
12
 
 * distributed under the License is distributed on an "AS IS" BASIS,
13
 
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14
 
 * See the License for the specific language governing permissions and
15
 
 * limitations under the License.
16
 
 */
17
 
 
18
 
package org.apache.lucene.search.grouping;
19
 
 
20
 
import java.util.Arrays;
21
 
 
22
 
/** A native int set where one value is reserved to mean "EMPTY" */
23
 
class SentinelIntSet {
24
 
  public int[] keys;
25
 
  public int count;
26
 
  public final int emptyVal;
27
 
  public int rehashCount;   // the count at which a rehash should be done
28
 
 
29
 
  public SentinelIntSet(int size, int emptyVal) {
30
 
    this.emptyVal = emptyVal;
31
 
    int tsize = Math.max(org.apache.lucene.util.BitUtil.nextHighestPowerOfTwo(size), 1);
32
 
    rehashCount = tsize - (tsize>>2);
33
 
    if (size >= rehashCount) {  // should be able to hold "size" w/o rehashing
34
 
      tsize <<= 1;
35
 
      rehashCount = tsize - (tsize>>2);
36
 
    }
37
 
    keys = new int[tsize];
38
 
    if (emptyVal != 0)
39
 
      clear();
40
 
  }
41
 
 
42
 
  public void clear() {
43
 
    Arrays.fill(keys, emptyVal);
44
 
    count = 0;
45
 
  }
46
 
 
47
 
  public int hash(int key) {
48
 
    return key;
49
 
  }
50
 
 
51
 
  public int size() { return count; }
52
 
 
53
 
  /** returns the slot for this key */
54
 
  public int getSlot(int key) {
55
 
    assert key != emptyVal;
56
 
    int h = hash(key);
57
 
    int s = h & (keys.length-1);
58
 
    if (keys[s] == key || keys[s]== emptyVal) return s;
59
 
 
60
 
    int increment = (h>>7)|1;
61
 
    do {
62
 
      s = (s + increment) & (keys.length-1);
63
 
    } while (keys[s] != key && keys[s] != emptyVal);
64
 
    return s;
65
 
  }
66
 
 
67
 
  /** returns the slot for this key, or -slot-1 if not found */
68
 
  public int find(int key) {
69
 
    assert key != emptyVal;
70
 
    int h = hash(key);
71
 
    int s = h & (keys.length-1);
72
 
    if (keys[s] == key) return s;
73
 
    if (keys[s] == emptyVal) return -s-1;
74
 
 
75
 
    int increment = (h>>7)|1;
76
 
    for(;;) {
77
 
      s = (s + increment) & (keys.length-1);
78
 
      if (keys[s] == key) return s;
79
 
      if (keys[s] == emptyVal) return -s-1;
80
 
    }
81
 
  }
82
 
 
83
 
  public boolean exists(int key) {
84
 
    return find(key) >= 0;
85
 
  }
86
 
 
87
 
  public int put(int key) {
88
 
    int s = find(key);
89
 
    if (s < 0) {
90
 
      if (count >= rehashCount) {
91
 
        rehash();
92
 
        s = getSlot(key);
93
 
      } else {
94
 
        s = -s-1;
95
 
      }
96
 
      count++;
97
 
      keys[s] = key;
98
 
    }
99
 
    return s;
100
 
  }
101
 
 
102
 
  public void rehash() {
103
 
    int newSize = keys.length << 1;
104
 
    int[] oldKeys = keys;
105
 
    keys = new int[newSize];
106
 
    if (emptyVal != 0) Arrays.fill(keys, emptyVal);
107
 
 
108
 
    for (int i=0; i<oldKeys.length; i++) {
109
 
      int key = oldKeys[i];
110
 
      if (key == emptyVal) continue;
111
 
      int newSlot = getSlot(key);
112
 
      keys[newSlot] = key;
113
 
    }
114
 
    rehashCount = newSize - (newSize>>2);
115
 
  }
116
 
}