net.sf.ivmaidns.storage
Class HashedStorage

java.lang.Object
  extended by net.sf.ivmaidns.util.ObservedCore
      extended by net.sf.ivmaidns.storage.Storage
          extended by net.sf.ivmaidns.storage.ObjectStorage
              extended by net.sf.ivmaidns.storage.HashedStorage
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, MultiObservable, ReallyCloneable, Sortable, TrimToSizeable, Verifiable

public class HashedStorage
extends ObjectStorage

Class for storage of hashed elements.

Version:
2.0
Author:
Ivan Maidanski
See Also:
Serialized Form

Field Summary
protected  int[] links
          NOTE: links must be !
protected  int size
          NOTE: size must be the number of elements in the storage.
 
Fields inherited from class net.sf.ivmaidns.storage.ObjectStorage
elements
 
Constructor Summary
HashedStorage()
           
HashedStorage(java.lang.Object[] initialValues)
          NOTE: initialValues must be !
 
Method Summary
protected static int addressOf(int hash, int location, int[] links)
          NOTE: location must be > 0.
 java.lang.Object clone()
          NOTE: Must be synchronized outside.
 int emptyLocation()
          NOTE: Result is an empty location (result > 0).
 void integrityCheck()
          NOTE: Shallow check for integrity of this object.
 int locationOf(java.lang.Object value, int prevLocation, boolean forward)
          NOTE: value is compared against elements.
protected  void minimizeCapacity()
          NOTE: Must be synchronized outside.
protected static void randomize(int[] links, int count)
          NOTE: Called internally only just before rehashing or if size == 0.
 void rehash()
          NOTE: The effectiveness is nearly linear.
 java.lang.Object setAt(int location, java.lang.Object value)
          NOTE: No equals checking is performed here.
 int size()
          NOTE: Result is the count of elements.
 
Methods inherited from class net.sf.ivmaidns.storage.ObjectStorage
childLocation, findLessGreater, getAt, insertAt, isValidAt, parentLocation, siblingLocation
 
Methods inherited from class net.sf.ivmaidns.storage.Storage
add, addAll, addAll, clear, contains, containsAll, containsAll, containsCount, equals, greaterThan, hasChildren, hashCode, insertAtAll, insertAtAll, nextLocation, notifyObservers, notifyObservers, remove, removeAll, removeAll, removeAt, toArray, toInlineString, toOutlineString, toString, trimToSize
 
Methods inherited from class net.sf.ivmaidns.util.ObservedCore
addObserver, hasObservers, removeObserver
 
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

links

protected transient int[] links
NOTE: links must be != null, links length == (elements length + 1) * 2 + (2 leftShift ~links[0]), links[0] = seedAndShift, links[1] = emptyLocation() - 1, links[loc * 2] = elements[loc - 1] != null ? elements[loc - 1] hashCode() : -nextEmptyLocation(loc), links[loc * 2 + 1] = elements[loc - 1] != null ? chainNext(loc) : -prevEmptyLocation(loc), links[links length - rootIndex - 1] = chainRoots(rootIndex), where rootIndex = ((links[loc * 2] ^ links[0]) * JavaConsts GOLD_MEDIAN) >>> links[0]. All values in each chain are ordered ascending first by their (signed) hash, and then by their locations. seed and order of empty locations are not serialized.


size

protected transient int size
NOTE: size must be the number of elements in the storage.

Constructor Detail

HashedStorage

public HashedStorage()

HashedStorage

public HashedStorage(java.lang.Object[] initialValues)
              throws java.lang.NullPointerException
NOTE: initialValues must be != null, initialValues[index] may be == null (ignored) for any index. capacity is set to initialValues length, each value from initialValues is added to storage. The effectiveness is nearly linear.

Throws:
java.lang.NullPointerException
Method Detail

size

public final int size()
NOTE: Result is the count of elements. Result >= 0.


minimizeCapacity

protected void minimizeCapacity()
NOTE: Must be synchronized outside.

Overrides:
minimizeCapacity in class ObjectStorage

rehash

public void rehash()
NOTE: The effectiveness is nearly linear. Hash values are not recalculated. Must be synchronized outside.


randomize

protected static final void randomize(int[] links,
                                      int count)
                               throws java.lang.NullPointerException,
                                      java.lang.ArrayIndexOutOfBoundsException
NOTE: Called internally only just before rehashing or if size == 0. NullPointerException and ArrayIndexOutOfBoundsException are thrown only if parameters are bad. Must be synchronized outside.

Throws:
java.lang.NullPointerException
java.lang.ArrayIndexOutOfBoundsException

addressOf

protected static final int addressOf(int hash,
                                     int location,
                                     int[] links)
                              throws java.lang.NullPointerException,
                                     java.lang.ArrayIndexOutOfBoundsException
NOTE: location must be > 0. Result > 0. NullPointerException and ArrayIndexOutOfBoundsException are thrown only if parameters are bad. Must be synchronized outside.

Throws:
java.lang.NullPointerException
java.lang.ArrayIndexOutOfBoundsException

emptyLocation

public final int emptyLocation()
Description copied from class: Storage
NOTE: Result is an empty location (result > 0). Storage state is not altered. The effectiveness is constant (typically). The order of empty locations is undefined. Requires no synchronization.

Overrides:
emptyLocation in class ObjectStorage

setAt

public java.lang.Object setAt(int location,
                              java.lang.Object value)
                       throws java.lang.IllegalArgumentException
NOTE: No equals checking is performed here. The effectiveness is nearly constant (may be linear in the worst case). Observers notification is performed. Must be synchronized outside.

Overrides:
setAt in class ObjectStorage
Throws:
java.lang.IllegalArgumentException

locationOf

public int locationOf(java.lang.Object value,
                      int prevLocation,
                      boolean forward)
               throws java.lang.IllegalArgumentException
NOTE: value is compared against elements. The effectiveness is nearly constant (may be linear in the worst case). Must be synchronized outside.

Overrides:
locationOf in class ObjectStorage
Throws:
java.lang.IllegalArgumentException

clone

public java.lang.Object clone()
NOTE: Must be synchronized outside.

Specified by:
clone in interface ReallyCloneable
Overrides:
clone in class ObjectStorage
Returns:
a copy (may be null) of this instance.

integrityCheck

public void integrityCheck()
NOTE: Shallow check for integrity of this object. Must be synchronized outside. For debug purpose only.

Specified by:
integrityCheck in interface Verifiable
Overrides:
integrityCheck in class ObjectStorage