org.apache.lucene.util

Class SentinelIntSet

java.lang.Object

org.apache.lucene.util.SentinelIntSet

public class SentinelIntSet
extends java.lang.Object

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

Fields

Modifier and Type	Field and Description
int	count
int	emptyVal
int[]	keys A power-of-2 over-sized array holding the integers in the set along with empty values.
int	rehashCount the count at which a rehash should be done

Constructor Summary

Constructors

Constructor and Description
SentinelIntSet(int size, int emptyVal)

Method Summary

Modifier and Type	Method and Description
void	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 found
int	getSlot(int key) (internal) Returns the slot for this key
int	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 doubling int[] key and filling with the old values.
int	size() The number of integers in this set.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

keys

public int[] keys

A 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 rehashCount

the count at which a rehash should be done

Constructor Detail

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 Detail

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 doubling int[] key and filling with the old values.