org.basex.util.hash
Class ASet

java.lang.Object
  extended by org.basex.util.hash.ASet
Direct Known Subclasses:
HashItemSet, IntSet, TokenSet

public abstract class ASet
extends java.lang.Object

This is the basic structure of an efficient and memory-saving hash set. The first entry of the token set (offset 0) will always be kept empty.

Author:
BaseX Team 2005-13, BSD License, Christian Gruen

Field Summary
protected  int[] bucket
          Hash table buckets.
protected  int[] next
          Pointers to the next entry.
protected  int size
          Hash entries.
 
Constructor Summary
protected ASet()
          Empty constructor.
protected ASet(int capacity)
          Initializes the data structure with an initial array size.
 
Method Summary
protected  void checkSize()
          Resizes the hash table.
 void clear()
          Resets the data structure.
protected abstract  int hash(int id)
          Returns the hash value of the element with the specified id.
 boolean isEmpty()
          Tests is the set is empty.
protected abstract  void rehash(int newSize)
          Rehashes all entries.
 int size()
          Returns the number of entries.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

bucket

protected int[] bucket
Hash table buckets.


next

protected int[] next
Pointers to the next entry.


size

protected int size
Hash entries. The actual number of entries is size - 1.

Constructor Detail

ASet

protected ASet()
Empty constructor.


ASet

protected ASet(int capacity)
Initializes the data structure with an initial array size.

Parameters:
capacity - initial array capacity (will be resized to a power of two)
Method Detail

clear

public void clear()
Resets the data structure. Must be called when data structure is initialized.


size

public final int size()
Returns the number of entries. The actual number of keys may be smaller if keys have been deleted.

Returns:
number of entries

isEmpty

public final boolean isEmpty()
Tests is the set is empty.

Returns:
result of check

checkSize

protected final void checkSize()
Resizes the hash table.


hash

protected abstract int hash(int id)
Returns the hash value of the element with the specified id.

Parameters:
id - id of the element
Returns:
hash value

rehash

protected abstract void rehash(int newSize)
Rehashes all entries.

Parameters:
newSize - new hash size