net.sf.ivmaidns.storage
Class TreeStorage

java.lang.Object
  net.sf.ivmaidns.util.ObservedCore
      net.sf.ivmaidns.storage.Storage
          net.sf.ivmaidns.storage.ObjectStorage
              net.sf.ivmaidns.storage.TreeStorage

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, MultiObservable, ReallyCloneable, Sortable, TrimToSizeable, Verifiable

public class TreeStorage
extends ObjectStorage

Class for tree storage.

Version:

2.0

Author:

Ivan Maidanski

See Also:

Serialized Form

Field Summary

protected int[]

links NOTE: links must be !

Fields inherited from class net.sf.ivmaidns.storage.ObjectStorage

elements

Constructor Summary

TreeStorage()

Method Summary

int	childLocation(int parentLocation, boolean forward) NOTE: Must be synchronized outside.
java.lang.Object	clone() NOTE: Must be synchronized outside.
int	emptyLocation() NOTE: Result is an empty location (result > 0).
int	insertAt(int prevLoc, int emptyLocation, java.lang.Object value) NOTE: ArrayStoreException is thrown only if value == null.
void	integrityCheck() NOTE: Shallow check for integrity of this object.
protected void	minimizeCapacity() NOTE: Must be synchronized outside.
int	parentLocation(int location) NOTE: If location is "empty" then IllegalArgumentException is thrown.
java.lang.Object	setAt(int location, java.lang.Object value) NOTE: If value is added then it is placed to the end of tree (at the first level).
int	siblingLocation(int location, boolean forward) NOTE: Must be synchronized outside.

Methods inherited from class net.sf.ivmaidns.storage.ObjectStorage

findLessGreater, getAt, isValidAt, locationOf

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 * 4, links[0] = childLocation(0, true), links[1] = emptyLocation() - 1, links[loc * 4] = elements[loc - 1] != null ? childLocation(loc, true) : -nextEmptyLocation(loc), links[loc * 4 + 1] = elements[loc - 1] != null ? parentLocation(loc) : -prevEmptyLocation(loc), links[loc * 4 - 2] = loc != childLocation(parentLocation(loc), false) ? siblingLocation(loc, true) : childLocation(parentLocation(loc), true) (if elements[loc - 1] != null), links[loc * 4 - 1] = loc != childLocation(parentLocation(loc), true) ? siblingLocation(loc, false) : childLocation(parentLocation(loc), false) (if elements[loc - 1] != null). Empty locations order is not serialized.

Constructor Detail

TreeStorage

public TreeStorage()

Method Detail

minimizeCapacity

protected void minimizeCapacity()

NOTE: Must be synchronized outside.

Overrides:

minimizeCapacity in class ObjectStorage

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: ArrayStoreException is thrown only if value == null. The effectiveness is constant. Observers notification is performed. Must be synchronized outside.

Overrides:

insertAt in class ObjectStorage

Throws:

java.lang.IllegalArgumentException

java.lang.ArrayStoreException

setAt

public java.lang.Object setAt(int location,
                              java.lang.Object value)
                       throws java.lang.IllegalArgumentException

NOTE: If value is added then it is placed to the end of tree (at the first level). The effectiveness is constant (linear when deleting an inner tree node). 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

parentLocation

public int parentLocation(int location)
                   throws java.lang.IllegalArgumentException

Description copied from class: Storage

NOTE: If location is "empty" then IllegalArgumentException is thrown. Result is either 0 (not found) or a found (not "empty") location. If location is "valid" and result != 0 then result is a "valid" location. Storage state is not altered. The effectiveness is constant. Must be synchronized outside.

Overrides:

parentLocation 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