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

java.lang.Object
  extended by net.ajaest.lib.data.OrderedSequenceTree<S,E>
Type Parameters:
S - the class of the sequence objects
E - the class of the stored nodes objects

public class OrderedSequenceTree<S,E>
extends java.lang.Object

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 have in common a particular list in specific order of other objects. 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.

Author:
Luis Alfonso Arce González

Field Summary
private  java.util.List<E> finalNodes
           
private  boolean isLinked
           
private  OrderedSequenceTree<S,E> parent
           
private  S sequenceValue
           
private  java.util.Map<S,OrderedSequenceTree<S,E>> subtrees
           
 
Constructor Summary
OrderedSequenceTree(boolean linked)
          Creates a ordered 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.
 boolean addFinalNode(E node)
          Appends the specified element to the end of this list.
 void addSubTree(S sequenceValue, OrderedSequenceTree<S,E> subtree)
          Adds a subtree to this tree using either provided sequenceValue or subtree.sequenceValue.
 boolean equals(java.lang.Object obj)
          To sequence tree equals if they have the same sequence value and final nodes.
 boolean exits(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()
           
 OrderedSequenceTree<S,E> getParent()
           
 S getSequenceValue()
           
 OrderedSequenceTree<S,E> getSubTree(S sequenceValue)
          Returns the subtree whose sequence value equals the specified one.
 java.util.Map<S,OrderedSequenceTree<S,E>> getSubTrees()
          Returns an unmodifiable map that maps subtrees from this tree by his sequence value.
 int hashCode()
           
 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.
 OrderedSequenceTree<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.
 E setFinalNode(int index, E element)
          Replaces the element at the specified position in this list with the specified element.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

parent

private OrderedSequenceTree<S,E> parent

sequenceValue

private S sequenceValue

subtrees

private java.util.Map<S,OrderedSequenceTree<S,E>> subtrees

finalNodes

private java.util.List<E> finalNodes

isLinked

private boolean isLinked
Constructor Detail

OrderedSequenceTree

public OrderedSequenceTree(boolean linked)
Creates a ordered 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

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

getSubTrees

public java.util.Map<S,OrderedSequenceTree<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 OrderedSequenceTree<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 OrderedSequenceTree<S,E> getParent()
Returns:
the tree parent of this tree

addSubTree

public void addSubTree(S sequenceValue,
                       OrderedSequenceTree<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 OrderedSequenceTree<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

exits

public boolean exits(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

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