uka.util
Class BooleanIDMap

java.lang.Object
  uka.util.IDConstants
      uka.util.BooleanIDMap

All Implemented Interfaces:

Printable, java.io.Serializable

public class BooleanIDMap

extends IDConstants

implements java.io.Serializable, Printable

An instance of IDMap establishes a mapping between objects and identifiers of type int.

Suppose, 3 objects have already been assigned an identifier. Each of these objects is stored at an uniquie index within the idToObject array. This index is the object's identifier. The identifier that will be assigned to the next object is #nextID.

 nextID = 3

                                        nextID
                                          v
 idToObject     = [ obj0 | obj1 | obj2 ]

                                        nextID
                                          v
 idToObject     = [ obj0 | obj1 | obj2 | obj ]
 

An index into the hashToID array is generated from a hashcode of an object using a hash function. At this index, the identifier corresponding to the object is stored.

 index = hashFunction.BooleanHashFunction.getHashCode(boolean) % hashSize
 

In case of a hash clash, for another object the same hash index could have been generated. Therefore all objects with the same hash index are chained. This happens in the chainID array.

In the following picture, the object with ID 1 (obj1) has the same hash index as the newly inserted object (obj). Therefore a link from the newly inserted object with identifier 4 is created to the formerly inserted object with identifier 1. The old value (identifer 1) at hashToID[index] can be replaced with the ID of the newly inserted object (identifier 4).

 Before:                                      index
                                                v
 hashToID     = [   |   |   |   |   |   |   |   1    |   |   |   |   ]
                                                |
                           +--------------------+
                           v
 chainID      = [      |  -1  |     ]
                           |
                           -
 After:                                       index
                                                v
 hashToID     = [   |   |   |   |   |   |   | nextID |   |   |   |   ]
                                                |
                           -            +-------+
                           |            v
 chainID      = [      |  -1  |      |  1  ]
                           ^            |
                           +------------+
 

When searching for an object with a known hash index, all objects from idToObject with the following identifiers have to be considered:

 hashToID[index], 
 chainID.get(chainID.get(hashToID.get(index))),
 chainID.get(chainID.get(chainID.get(hashToID.get[index]))),
 chainID.get(chainID.get(chainID.get(chainID.get(hashToID[index])))),
 ...
 

The search stops, either if the object is found in idToObject, or chainID points to -1 for the current identifier.

Last but not least, the next identifier is incremented.

 nextID = 4
 

Author:

Bernhard Haumacher

See Also:

Serialized Form

Field Summary

private EnlargingIntArray	chainID Function ID \rightarrow ID \cup {INVALID_ID}
private int	hashCapacity
private BooleanHashFunction	hashFunction
private int	hashSize
private int[]	hashToID
protected EnlargingBooleanArray	idToObject
protected static int	INVALID_INDEX
private int	size
protected IDSpace	space

Fields inherited from class uka.util.IDConstants

FIRST_NEW_ID, FIRST_VALID_ID, INVALID_ID, UNUSED_ID

Constructor Summary

BooleanIDMap()

BooleanIDMap(IDSpace space)

Method Summary

void	appendTo(ToString s) This method should append the contents of each instance variable of the current object to the given ToString object.
void	clear()
private static int	computeHashCapacity(int hashSize)
private static int	computeHashSize(int size)
void	dump()
int	findID(boolean obj)
private int	findIDInternal(boolean obj, int index)
protected boolean	get(int id)
protected int	getHash(boolean obj) Computes an index into the hashToID array from the hash value for the given object.
int	getID(boolean obj)
protected int	getIndexForHash(int hash)
protected int	getIndexForID(int id)
boolean	getObject(int id)
BooleanIterator	getObjects()
int	getSize()
IntIterator	getUsedIDs()
private void	growHashtable()
private void	hashInsert(int index, int id)
private void	hashRemove(int id)
private void	init()
boolean	isUsed(int id)
protected int	rawFindID(boolean obj, int hash)
private void	readObject(java.io.ObjectInputStream in)
void	remove(int id)
void	resetObject(int id, boolean obj)
protected void	restoreBeforeReadObject()
protected void	set(int id, boolean obj) Access to the underlying idToObject array is encapsulated through the set(int, boolean) and get(int) methods.
void	setObject(int id, boolean obj)
private void	writeObject(java.io.ObjectOutputStream out) For serializing an instance of this class, it has to be externalized, because weak references are not serializable.

Methods inherited from class uka.util.IDConstants

isNew, isValid, normalizeID, toggleNew

Methods inherited from class java.lang.Object

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

Field Detail

INVALID_INDEX

protected static final int INVALID_INDEX

See Also:

Constant Field Values

space

protected IDSpace space

idToObject

protected EnlargingBooleanArray idToObject

hashFunction

private transient BooleanHashFunction hashFunction

size

private transient int size

hashToID

private transient int[] hashToID

chainID

private transient EnlargingIntArray chainID

Function ID \rightarrow ID \cup {INVALID_ID}

hashCapacity

private transient int hashCapacity

hashSize

private transient int hashSize

Constructor Detail

BooleanIDMap

public BooleanIDMap()

BooleanIDMap

public BooleanIDMap(IDSpace space)

Method Detail

computeHashCapacity

private static int computeHashCapacity(int hashSize)

computeHashSize

private static int computeHashSize(int size)

init

private void init()

getSize

public int getSize()

clear

public void clear()

getID

public int getID(boolean obj)

getUsedIDs

public IntIterator getUsedIDs()

getObjects

public BooleanIterator getObjects()

findID

public int findID(boolean obj)

findIDInternal

private int findIDInternal(boolean obj,
                           int index)

rawFindID

protected final int rawFindID(boolean obj,
                              int hash)

dump

public void dump()

setObject

public void setObject(int id,
                      boolean obj)

resetObject

public void resetObject(int id,
                        boolean obj)

set

protected void set(int id,
                   boolean obj)

Access to the underlying idToObject array is encapsulated through the set(int, boolean) and get(int) methods. Subclasses may use this hooks to add functionality whenever an object is stored or retrieved.

isUsed

public final boolean isUsed(int id)

getObject

public boolean getObject(int id)

get

protected boolean get(int id)

See Also:

set(int, boolean)

getHash

protected final int getHash(boolean obj)

Computes an index into the hashToID array from the hash value for the given object.

getIndexForHash

protected final int getIndexForHash(int hash)

getIndexForID

protected int getIndexForID(int id)

growHashtable

private void growHashtable()

hashInsert

private void hashInsert(int index,
                        int id)

hashRemove

private void hashRemove(int id)

remove

public void remove(int id)

writeObject

private void writeObject(java.io.ObjectOutputStream out)
                  throws java.io.IOException

For serializing an instance of this class, it has to be externalized, because weak references are not serializable. Only objects that are currently alive can be marshaled and inserted to the unmarshaled copy. Therefore, the validity of identifiers may differ from the copy that is marshaled and the copy that is unmarshaled.

Throws:

java.io.IOException

restoreBeforeReadObject

protected void restoreBeforeReadObject()
                                throws java.lang.ClassNotFoundException,
                                       java.io.IOException

Throws:

java.lang.ClassNotFoundException

java.io.IOException

readObject

private void readObject(java.io.ObjectInputStream in)
                 throws java.io.IOException,
                        java.lang.ClassNotFoundException

Throws:

java.io.IOException

java.lang.ClassNotFoundException

appendTo

public void appendTo(ToString s)

Description copied from interface: Printable

This method should append the contents of each instance variable of the current object to the given ToString object. The appended data should be labeled with the name of the corresponding instance variable.

Specified by:

appendTo in interface Printable

See Also:

ToString, ToString.append(String, Object), ToString.append(String, boolean), ToString.append(String, byte), ToString.append(String, int)