Package org.apache.lucene.util
Class SentinelIntSet
java.lang.Object
org.apache.lucene.util.SentinelIntSet
A native int hash-based set where one value is reserved to mean "EMPTY" internally. The space overhead is fairly low
as there is only one power-of-two sized int[] to hold the values. The set is re-hashed when adding a value that
would make it >= 75% full. Consider extending and over-riding
hash(int)
if the values might be poor
hash keys; Lucene docids should be fine.
The internal fields are exposed publicly to enable more efficient use at the expense of better O-O principles.
To iterate over the integers held in this set, simply use code like this:
SentinelIntSet set = ... for (int v : set.keys) { if (v == set.emptyVal) continue; //use v... }
-
Field Summary
FieldsModifier and TypeFieldDescriptionint
final int
int[]
A power-of-2 over-sized array holding the integers in the set along with empty values.int
the count at which a rehash should be done -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
clear()
boolean
exists
(int key) Does this set contain the specified integer?int
find
(int key) (internal) Returns the slot for this key, or -slot-1 if not foundint
getSlot
(int key) (internal) Returns the slot for this keyint
hash
(int key) (internal) Return the hash for the key.int
put
(int key) Puts this integer (key) in the set, and returns the slot index it was added to.void
rehash()
(internal) Rehashes by doublingint[] key
and filling with the old values.int
size()
The number of integers in this set.
-
Field Details
-
keys
public int[] keysA power-of-2 over-sized array holding the integers in the set along with empty values. -
count
public int count -
emptyVal
public final int emptyVal -
rehashCount
public int rehashCountthe count at which a rehash should be done
-
-
Constructor Details
-
SentinelIntSet
public SentinelIntSet(int size, int emptyVal) - Parameters:
size
- The minimum number of elements this set should be able to hold without rehashing (i.e. the slots are guaranteed not to change)emptyVal
- The integer value to use for EMPTY
-
-
Method Details
-
clear
public void clear() -
hash
public int hash(int key) (internal) Return the hash for the key. The default implementation just returns the key, which is not appropriate for general purpose use. -
size
public int size()The number of integers in this set. -
getSlot
public int getSlot(int key) (internal) Returns the slot for this key -
find
public int find(int key) (internal) Returns the slot for this key, or -slot-1 if not found -
exists
public boolean exists(int key) Does this set contain the specified integer? -
put
public int put(int key) Puts this integer (key) in the set, and returns the slot index it was added to. It rehashes if adding it would make the set more than 75% full. -
rehash
public void rehash()(internal) Rehashes by doublingint[] key
and filling with the old values.
-