net.ajaest.lib.data
Class SequenceTree<S,E>

java.lang.Object
  extended by net.ajaest.lib.data.SequenceTree<S,E>
Type Parameters:
S - the class of the sequence objects
E - the class of the stored nodes objects
All Implemented Interfaces:
java.io.Externalizable, java.io.Serializable, java.lang.Iterable<SequenceTree<S,E>>
Direct Known Subclasses:
SequenceEnumTree

public class SequenceTree<S,E>
extends java.lang.Object
implements java.io.Externalizable, java.lang.Iterable<SequenceTree<S,E>>

Search tree by sequence. This class allows to sort a list of node objects using a unique sequence of other objects. Every level of the tree represents all the node objects that can be retrieved through the same object sequence. This class can use either ArrayList or LinkedList implementations for final nodes list. It's recommended to use ArrayList implementation for fixed trees and LinkedList implementation for dynamic trees.

You must be aware that the node circularity of the tree isn't checked when a new node is added. Circular connection between nodes could cause unexpected behavior.

Keep in mind too that if the serialization process of an instance of this class won't retrieve information about the parent structure. This means that the readObject() method will always assign null to the parent field of the tree's root node.

Author:
Luis Alfonso Arce González
See Also:
Serialized Form

Nested Class Summary
private  class SequenceTree.TreeIterator
           
 
Field Summary
protected  java.util.List<E> finalNodes
           
protected  boolean isLinked
           
protected  SequenceTree<S,E> parent
           
protected  S sequenceValue
           
protected  int serialID
          Used to keep node reference in serialization
protected static java.lang.Integer serialIDseed
           
private static long serialVersionUID
           
protected  java.util.Map<S,SequenceTree<S,E>> subtrees
          Serialization of big trees causes stack overflow because of recursive reflection, so maps are serialized horizontally instead of deeply.
 
Constructor Summary
SequenceTree()
          Creates a sequence tree using either theLinkedList implementation for final nodes list.
SequenceTree(boolean linked)
          Creates a sequence tree using either ArrayList or LinkedList implementation for final nodes list.
 
Method Summary
 void add(java.util.List<S> sequence, E finalNode)
          Creates needed sequence tree if necessary in order to add a final node to the tree.
 void add(S[] sequence, E finalNode)
          Creates needed sequence tree if necessary in order to add a final node to the tree.
 boolean addFinalNode(E node)
          Appends the specified element to the end of this list.
 void addSubTree(S sequenceValue, SequenceTree<S,E> subtree)
          Adds a subtree to this tree using either provided sequenceValue or subtree.sequenceValue.
protected  java.util.Map<S,SequenceTree<S,E>> createSubTreeMapInstance()
           
 boolean equals(java.lang.Object obj)
          To sequence tree equals if they have the same sequence value and final nodes.
 boolean exist(java.util.List<S> sequence)
          Says whether exists or not any final node in this tree referenced by the specified sequence
 java.util.List<E> getFinalNodes()
           
 SequenceTree<S,E> getParent()
           
 S getSequenceValue()
           
 SequenceTree<S,E> getSubTree(S sequenceValue)
          Returns the subtree whose sequence value equals the specified one.
 java.util.Map<S,SequenceTree<S,E>> getSubTrees()
          Returns an unmodifiable map that maps subtrees from this tree by his sequence value.
 int hashCode()
           
protected  void init(boolean linked)
          Me Method extracted in order to allow post-construction initialization in inherited classes(For example, in SequenceEnumTree
 java.util.Iterator<SequenceTree<S,E>> iterator()
          Returns an iterator that iterates through all the nodes contained in this tree.
protected  void readAndAssignToThis(java.io.ObjectInput in)
           
 void readExternal(java.io.ObjectInput in)
          Reconstitute the OrderedSequenceTree instance from a stream (i.e., deserialize it).
protected  SequenceTree<S,E> readTreeSequentially(java.io.ObjectInput in)
          Parent field is not retrieved
 boolean removeFinalNode(E node)
          Removes the first occurrence of the specified element from this list, if it is present.
 E removeFinalNode(int index)
          Removes the element at the specified position in this list.
 SequenceTree<S,E> removeSubTree(S sequenceValue)
          Removes the mapping for the specified key from this map if present.
 java.util.List<E> search(java.util.List<S> sequence)
          Does a recursive search along subtrees of this tree in order to get final nodes that matches the specified sequence.
 java.util.List<E> search(S[] sequence)
          Does a recursive search along subtrees of this tree in order to get final nodes that matches the specified sequence.
 E searchFirst(java.util.List<S> sequence)
          Does a recursive search along subtrees of this tree in order to get the first final node added to this tree that matches the specified sequence.
 E searchFirst(S[] sequence)
          Does a recursive search along subtrees of this tree in order to get the first final node added to this tree that matches the specified sequence.
 E setFinalNode(int index, E element)
          Replaces the element at the specified position in this list with the specified element.
 void writeExternal(java.io.ObjectOutput out)
          Save the state of the OrderedSequenceTree instance to a stream (i.e., serialize it).
protected  void writeTreeSequentially(java.io.ObjectOutput out, SequenceTree<S,E> ost)
          Parent field is not stored
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

serialVersionUID

private static final long serialVersionUID
See Also:
Constant Field Values

serialIDseed

protected static java.lang.Integer serialIDseed

serialID

protected int serialID
Used to keep node reference in serialization


parent

protected SequenceTree<S,E> parent

sequenceValue

protected S sequenceValue

subtrees

protected transient java.util.Map<S,SequenceTree<S,E>> subtrees
Serialization of big trees causes stack overflow because of recursive reflection, so maps are serialized horizontally instead of deeply.

See Also:
writeExternal(ObjectOutput), readExternal(ObjectInput)

finalNodes

protected java.util.List<E> finalNodes

isLinked

protected boolean isLinked
Constructor Detail

SequenceTree

public SequenceTree()
Creates a sequence tree using either theLinkedList implementation for final nodes list.


SequenceTree

public SequenceTree(boolean linked)
Creates a sequence tree using either ArrayList or LinkedList implementation for final nodes list. It's recommended to use ArrayList implementations for fixed trees and LinkedList implementation for dynamic trees.

Parameters:
linked - if it's true, object will use LinkedList implementation. Object will use ArrayList implementation if it's false.
Method Detail

init

protected void init(boolean linked)
Me Method extracted in order to allow post-construction initialization in inherited classes(For example, in SequenceEnumTree

Parameters:
linked -

add

public void add(java.util.List<S> sequence,
                E finalNode)
Creates needed sequence tree if necessary in order to add a final node to the tree. If the sequence.size()==0, the final node is added to this tree.

Parameters:
sequence - the sorting sequence
finalNode - the final node

add

public void add(S[] sequence,
                E finalNode)
Creates needed sequence tree if necessary in order to add a final node to the tree. If the sequence.length==0, the final node is added to this tree.

Parameters:
sequence - the sorting sequence
finalNode - the final node

getSubTrees

public java.util.Map<S,SequenceTree<S,E>> getSubTrees()
Returns an unmodifiable map that maps subtrees from this tree by his sequence value.

Returns:
a map with this tree's subtrees

getFinalNodes

public java.util.List<E> getFinalNodes()
Returns:
the list of final nodes related to this tree

getSubTree

public SequenceTree<S,E> getSubTree(S sequenceValue)
Returns the subtree whose sequence value equals the specified one.

Parameters:
sequenceValue - the sequence value of the requested subtree
Returns:
the requested subtree, null otherwise

getSequenceValue

public S getSequenceValue()
Returns:
the sequence value that maps this tree

getParent

public SequenceTree<S,E> getParent()
Returns:
the tree parent of this tree

addSubTree

public void addSubTree(S sequenceValue,
                       SequenceTree<S,E> subtree)
Adds a subtree to this tree using either provided sequenceValue or subtree.sequenceValue. If sequenceValue don't equals null, this value will be used to map the subtree. subtree.sequenceValue will be used to map the subtree if sequenceValue equals null only if subtree.sequenceValue does not equals null. If both sequence values equals null exception will be thrown.
Keep in mind that if subtree was nested in another tree before adding to this, previous parent information and sequence value will be overwritten in order to nest it to this structure.

Parameters:
sequenceValue - order mapping value, if null sequenceValue will be used
subtree - subtree to be added
Throws:
java.lang.NullPointerException - if sequenceValue and subtree.sequenceValue are both null

setFinalNode

public E setFinalNode(int index,
                      E element)
Replaces the element at the specified position in this list with the specified element.

Parameters:
index - index of the element to replace
element - element to be stored at the specified position
Returns:
the element previously at the specified position
Throws:
java.lang.IndexOutOfBoundsException

addFinalNode

public boolean addFinalNode(E node)
Appends the specified element to the end of this list.

Parameters:
node - element to be appended to this list
Returns:
true (as specified by Collection.add(E))

removeSubTree

public SequenceTree<S,E> removeSubTree(S sequenceValue)
Removes the mapping for the specified key from this map if present.

Parameters:
sequenceValue - key whose mapping is to be removed from the map
Returns:
the previous value associated with key, or null if there was no mapping for key.

removeFinalNode

public E removeFinalNode(int index)
Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).

Parameters:
index - the index of the element to be removed
Returns:
the element that was removed from the list
Throws:
java.lang.IndexOutOfBoundsException

removeFinalNode

public boolean removeFinalNode(E node)
Removes the first occurrence of the specified element from this list, if it is present. If the list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))) (if such an element exists). Returns true if this list contained the specified element (or equivalently, if this list changed as a result of the call).

Parameters:
node - element to be removed from this list, if present
Returns:
true if this list contained the specified element

search

public java.util.List<E> search(java.util.List<S> sequence)
Does a recursive search along subtrees of this tree in order to get final nodes that matches the specified sequence. If not matching final node is found, it returns an empty list.

Parameters:
sequence - sequence to be searched
Returns:
list of final nodes that matches the sequence

searchFirst

public E searchFirst(java.util.List<S> sequence)
Does a recursive search along subtrees of this tree in order to get the first final node added to this tree that matches the specified sequence. If not matching final node is found, it returns null

Parameters:
sequence - sequence to be searched
Returns:
the final node that matches the sequence, null otherwise

searchFirst

public E searchFirst(S[] sequence)
Does a recursive search along subtrees of this tree in order to get the first final node added to this tree that matches the specified sequence. If not matching final node is found, it returns null

Parameters:
sequence - sequence to be searched
Returns:
the final node that matches the sequence, null otherwise

search

public java.util.List<E> search(S[] sequence)
Does a recursive search along subtrees of this tree in order to get final nodes that matches the specified sequence. If not matching final node is found, it returns an empty list.

Parameters:
sequence - sequence to be searched
Returns:
list of final nodes that matches the sequence

exist

public boolean exist(java.util.List<S> sequence)
Says whether exists or not any final node in this tree referenced by the specified sequence

Parameters:
sequence - sequence to be checked
Returns:
true if search(sequence) does not returns an empty list, false otherwise

iterator

public java.util.Iterator<SequenceTree<S,E>> iterator()
Returns an iterator that iterates through all the nodes contained in this tree. No special ordering is used. The root isn't returned by next().

Specified by:
iterator in interface java.lang.Iterable<SequenceTree<S,E>>

hashCode

public int hashCode()
Overrides:
hashCode in class java.lang.Object

equals

public boolean equals(java.lang.Object obj)
To sequence tree equals if they have the same sequence value and final nodes.

Overrides:
equals in class java.lang.Object

createSubTreeMapInstance

protected java.util.Map<S,SequenceTree<S,E>> createSubTreeMapInstance()

readExternal

public void readExternal(java.io.ObjectInput in)
                  throws java.io.IOException,
                         java.lang.ClassNotFoundException
Reconstitute the OrderedSequenceTree instance from a stream (i.e., deserialize it).

Specified by:
readExternal in interface java.io.Externalizable
Throws:
java.io.IOException
java.lang.ClassNotFoundException
See Also:
writeExternal(ObjectOutput)

writeExternal

public void writeExternal(java.io.ObjectOutput out)
                   throws java.io.IOException
Save the state of the OrderedSequenceTree instance to a stream (i.e., serialize it).

Specified by:
writeExternal in interface java.io.Externalizable
Throws:
java.io.IOException

writeTreeSequentially

protected void writeTreeSequentially(java.io.ObjectOutput out,
                                     SequenceTree<S,E> ost)
                              throws java.io.IOException
Parent field is not stored

Throws:
java.io.IOException

readTreeSequentially

protected SequenceTree<S,E> readTreeSequentially(java.io.ObjectInput in)
                                          throws java.io.IOException,
                                                 java.lang.ClassNotFoundException
Parent field is not retrieved

Throws:
java.io.IOException
java.lang.ClassNotFoundException

readAndAssignToThis

protected void readAndAssignToThis(java.io.ObjectInput in)
                            throws java.io.IOException,
                                   java.lang.ClassNotFoundException
Throws:
java.io.IOException
java.lang.ClassNotFoundException