net.sf.ivmaidns.storage
Class SortedStorage

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.SortedStorage
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable, MultiObservable, ReallyCloneable, Sortable, TrimToSizeable, Verifiable

public class SortedStorage
extends ObjectStorage

Class for ascending-sorted storage. Storage elements are placed during insertAt/setAt/readObject operations into ascending order according to the supplied comparator. If two (compared) elements are equal or uncomparable then they are ordered by their locations. Add, remove and search effectiveness is logarithmic.

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

Field Summary
protected  int approxLoc
          NOTE: Used internally by setAt/locationOf/findLessGreater operations to speed up addressOf function. approxLoc must be either 0 or a non-empty location.
protected  GComparator comparator
          NOTE: comparator must be !
protected  int[] links
          NOTE: links must be !
 
Fields inherited from class net.sf.ivmaidns.storage.ObjectStorage
elements
 
Constructor Summary
SortedStorage()
          NOTE: The default comparator is used.
SortedStorage(GComparator comparator)
          NOTE: comparator must be !
 
Method Summary
protected static int addressOf(java.lang.Object value, int location, java.lang.Object[] elements, int[] links, int approxLoc, GComparator comparator)
          NOTE: Find place for the child link to the value (value may be == null, location may be of any int value, abs(approxLoc) must be either 0 or a non-empty location, comparator must be !
protected static void changeLinks(int[] links, int address, int emptyLocation)
          NOTE: If emptyLocation > 0 then another leaf is added to the tree else one leaf (which is refered by non-zero address) is removed.
 int childLocation(int parentLocation, boolean forward)
          NOTE: Must be synchronized outside.
 java.lang.Object clone()
          NOTE: Must be synchronized outside.
 GComparator comparator()
          NOTE: Result !
 int emptyLocation()
          NOTE: Result is an empty location (result > 0).
 int findLessGreater(java.lang.Object value, boolean greater, int prevLocation, boolean forward)
          NOTE: Search is performed using the supplied comparator.
protected static int followLinks(int[] links, int address)
          NOTE: (address / 2) must be either 0 or a non-empty location.
 int insertAt(int prevLoc, int emptyLocation, java.lang.Object value)
          NOTE: prevLoc must be >= 0, value must be comparable and insertion of this value must not destroy the order of elements in this storage (according to the semantics of sorted collection), otherwise ArrayStoreException is thrown.
 void integrityCheck()
          NOTE: Shallow check for integrity of this object.
 int locationOf(java.lang.Object value, int prevLocation, boolean forward)
          NOTE: Search is performed using the supplied comparator.
protected  void minimizeCapacity()
          NOTE: Must be synchronized outside.
 void setApproxLoc(int approxLoc)
          NOTE: This is a special operation for manual setting of approxLoc (approxLoc is also set internally by insertAt, setAt, locationOf and findLessGreater operations). approxLoc is entirely used internally to speed up setAt, locationOf and findLessGreater operations. approxLoc must be either 0 or a non-empty location, otherwise IllegalArgumentException is thrown.
 java.lang.Object setAt(int location, java.lang.Object value)
          NOTE: The effectiveness is logarithmic (may be nearly constant).
 int siblingLocation(int location, boolean forward)
          NOTE: Must be synchronized outside.
 
Methods inherited from class net.sf.ivmaidns.storage.ObjectStorage
getAt, isValidAt, parentLocation
 
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 == 2 + elements length * 3, links[0] = rootAddress, links[1] = emptyLocation() - 1, links[loc * 2] = elements[loc - 1] != null ? leftAddress(loc) : -nextEmptyLocation(loc), links[loc * 2 + 1] = elements[loc - 1] != null ? rightAddress(loc) : -prevEmptyLocation(loc), links[links length - loc] = upperAddress(loc) (if elements[loc - 1] != null). Equal (or uncomparable) elements are ordered ascending by their locations. Tree node balance is held in the least bit of each leftAddress/rightAddress. The order of empty locations is not serialized.


comparator

protected final GComparator comparator
NOTE: comparator must be != null. This field is serialized and cloned (shallow).


approxLoc

protected transient int approxLoc
NOTE: Used internally by setAt/locationOf/findLessGreater operations to speed up addressOf function. approxLoc must be either 0 or a non-empty location. This field is not serialized but cloned.

Constructor Detail

SortedStorage

public SortedStorage()
NOTE: The default comparator is used.


SortedStorage

public SortedStorage(GComparator comparator)
              throws java.lang.NullPointerException
NOTE: comparator must be != null.

Throws:
java.lang.NullPointerException
Method Detail

comparator

public final GComparator comparator()
NOTE: Result != null.


minimizeCapacity

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

Overrides:
minimizeCapacity in class ObjectStorage

addressOf

protected static final int addressOf(java.lang.Object value,
                                     int location,
                                     java.lang.Object[] elements,
                                     int[] links,
                                     int approxLoc,
                                     GComparator comparator)
                              throws java.lang.NullPointerException,
                                     java.lang.ArrayIndexOutOfBoundsException
NOTE: Find place for the child link to the value (value may be == null, location may be of any int value, abs(approxLoc) must be either 0 or a non-empty location, comparator must be != null). Result >= 0. If 0 >= location or location > elements length then links[result] == 0. NullPointerException and ArrayIndexOutOfBoundsException are thrown only if parameters are bad. Must be synchronized outside.

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

followLinks

protected static final int followLinks(int[] links,
                                       int address)
                                throws java.lang.NullPointerException,
                                       java.lang.ArrayIndexOutOfBoundsException
NOTE: (address / 2) must be either 0 or a non-empty location. The follow direction is specified in the least bit of address (this direction bit is not preserved in the resulting address). If resulting address is 0 then tree end is reached. NullPointerException and ArrayIndexOutOfBoundsException are thrown only if parameters are bad. Must be synchronized outside.

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

changeLinks

protected static final void changeLinks(int[] links,
                                        int address,
                                        int emptyLocation)
                                 throws java.lang.NullPointerException,
                                        java.lang.ArrayIndexOutOfBoundsException
NOTE: If emptyLocation > 0 then another leaf is added to the tree else one leaf (which is refered by non-zero address) is removed. The tree remains balanced. 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

insertAt

public int insertAt(int prevLoc,
                    int emptyLocation,
                    java.lang.Object value)
             throws java.lang.IllegalArgumentException,
                    java.lang.ArrayStoreException
NOTE: prevLoc must be >= 0, value must be comparable and insertion of this value must not destroy the order of elements in this storage (according to the semantics of sorted collection), otherwise ArrayStoreException is thrown. The effectiveness is constant. Observers notification is performed. Must be synchronized outside.

Overrides:
insertAt in class ObjectStorage
Throws:
java.lang.IllegalArgumentException
java.lang.ArrayStoreException

setApproxLoc

public final void setApproxLoc(int approxLoc)
                        throws java.lang.IllegalArgumentException
NOTE: This is a special operation for manual setting of approxLoc (approxLoc is also set internally by insertAt, setAt, locationOf and findLessGreater operations). approxLoc is entirely used internally to speed up setAt, locationOf and findLessGreater operations. approxLoc must be either 0 or a non-empty location, otherwise IllegalArgumentException is thrown. Must be synchronized outside.

Throws:
java.lang.IllegalArgumentException

setAt

public java.lang.Object setAt(int location,
                              java.lang.Object value)
                       throws java.lang.IllegalArgumentException
NOTE: The effectiveness is logarithmic (may be nearly constant). Observers notification is performed. Must be synchronized outside.

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

childLocation

public int childLocation(int parentLocation,
                         boolean forward)
                  throws java.lang.IllegalArgumentException
NOTE: Must be synchronized outside.

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

siblingLocation

public int siblingLocation(int location,
                           boolean forward)
                    throws java.lang.IllegalArgumentException
NOTE: Must be synchronized outside.

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

locationOf

public int locationOf(java.lang.Object value,
                      int prevLocation,
                      boolean forward)
               throws java.lang.IllegalArgumentException
NOTE: Search is performed using the supplied comparator. The effectiveness is logarithmic (may be nearly constant). Must be synchronized outside.

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

findLessGreater

public int findLessGreater(java.lang.Object value,
                           boolean greater,
                           int prevLocation,
                           boolean forward)
                    throws java.lang.IllegalArgumentException
NOTE: Search is performed using the supplied comparator. The effectiveness is logarithmic (may be nearly constant). Must be synchronized outside.

Overrides:
findLessGreater 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