uka.util
Class DoubleIDMap

java.lang.Object
  uka.util.IDConstants
      uka.util.DoubleIDMap

All Implemented Interfaces:

Printable, java.io.Serializable

public class DoubleIDMap

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.DoubleHashFunction.getHashCode(double) % 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 DoubleHashFunction	hashFunction
private int	hashSize
private int[]	hashToID
protected EnlargingDoubleArray	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

DoubleIDMap()

DoubleIDMap(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(double obj)
private int	findIDInternal(double obj, int index)
protected double	get(int id)
protected int	getHash(double obj) Computes an index into the hashToID array from the hash value for the given object.
int	getID(double obj)
protected int	getIndexForHash(int hash)
protected int	getIndexForID(int id)
double	getObject(int id)
DoubleIterator	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(double obj, int hash)
private void	readObject(java.io.ObjectInputStream in)
void	remove(int id)
void	resetObject(int id, double obj)
protected void	restoreBeforeReadObject()
protected void	set(int id, double obj) Access to the underlying idToObject array is encapsulated through the set(int, double) and get(int) methods.
void	setObject(int id, double 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 EnlargingDoubleArray idToObject

hashFunction

private transient DoubleHashFunction 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

DoubleIDMap

public DoubleIDMap()

DoubleIDMap

public DoubleIDMap(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(double obj)

getUsedIDs

public IntIterator getUsedIDs()

getObjects

public DoubleIterator getObjects()

findID

public int findID(double obj)

findIDInternal

private int findIDInternal(double obj,
                           int index)

rawFindID

protected final int rawFindID(double obj,
                              int hash)

dump

public void dump()

setObject

public void setObject(int id,
                      double obj)

resetObject

public void resetObject(int id,
                        double obj)

set

protected void set(int id,
                   double obj)

Access to the underlying idToObject array is encapsulated through the set(int, double) 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 double getObject(int id)

get

protected double get(int id)

See Also:

set(int, double)

getHash

protected final int getHash(double 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)