infovis.tree
Class DefaultTree

java.lang.Object
  infovis.utils.ChangeManager
      infovis.column.AbstractColumn
          infovis.column.BasicColumn
              infovis.column.BasicObjectColumn
                  infovis.column.ColumnColumn
                      infovis.table.DefaultTable
                          infovis.table.DefaultDynamicTable
                              infovis.tree.DefaultTree

All Implemented Interfaces:

IntComparator, Column, DynamicTable, Metadata, Constants, Table, Tree, RowComparator, Serializable, EventListener, ChangeListener, TableModel, TreeModel

public class DefaultTree
extends DefaultDynamicTable
implements Tree

Default implementation of the Tree interface.

A DefaultTree is a Table proxy, not a Table itself (it references a table).

Topology is build using four internal IntColumns:

1. #child contains the index of the first child of a node or NIL if the node is a leaf
2. #next contains the index of the next sibling of a node
3. #last contains the index of the last child of a node
4. #parent contains the index of the parent of a node

Version:

$Revision: 1.26 $

Author:

Jean-Daniel Fekete

See Also:

Serialized Form

Field Summary

static String	CHILD_COLUMN Name of the IntColumn referencing the first child of a node.
static String	LAST_COLUMN Name of the IntColumn referencing the last child of a node.
static String	NEXT_COLUMN Name of the IntColumn referencing the next sibling of a node.
static String	PARENT_COLUMN Name of the IntColumn referencing the parent of a node.

Fields inherited from class infovis.column.AbstractColumn

MODIFIED_ALL, MODIFIED_NONE

Fields inherited from interface infovis.Tree

ROOT, TREE_METADATA

Fields inherited from interface infovis.Table

FILTER_COLUMN, INTERNAL_PREFIX, NIL, SELECTION_COLUMN

Fields inherited from interface infovis.metadata.Constants

CONTRIBUTOR, COVERAGE, CREATOR, DATE, DESCRITION, FORMAT, IDENTIFIER, LANGUAGE, PUBLISHER, RELATION, RIGHTS, SOURCE, SUBJECT, TITLE, TYPE

Constructor Summary

DefaultTree()
Creates a new DefaultTree object.

Method Summary

int	addNode(int par) Adds a node to the tree.
int	addRow() Creates a new row and returns it.
void	addTreeModelListener(TreeModelListener l)
Object[]	buildPath(int node)
int[]	children(int node) Returns a table of children of this node.
RowIterator	childrenIterator(int node) Returns the iterator over the children of a node.
void	clear() Removes all of the elements from this column. The Column will be empty after this call returns. WARNING: if there is an associated format that maintains a status, such as a CategoricalFormat, it is not cleared so results may not be what you expected. The CategoricalFormat can be cleared explicitely if needed.
int	computeDegree(int node) Returns the degree of a node, i˙e˙ the number of children.
int	computeDepth(int node) Computes the depth of the node in the tree and return it.
int	getChild(int node, int index) Returns the nth child of a node.
Object	getChild(Object parent, int index)
int	getChildCount(int node) Returns the degree of a node using either a degree column if it has been computed or the computeDegree method.
int	getChildCount(Object parent)
int	getDepth(int node) Returns the depth of a node using either a depth column if it has been computed or the computeDepth method.
int	getFirstChild(int node) Returns the first child of a node.
int	getIndexOfChild(int node)
int	getIndexOfChild(Object parent, Object child)
int	getLastChild(int node) Returns the last child of a node.
int	getNextSibling(int node) Returns the next sibling of a node.
int	getNodeCount() Returns the number of proper nodes in the Tree.
int	getParent(int node) Returns the parent of a node.
Object	getRoot()
boolean	isAncestor(int node, int par) Returns true if the first node has the second node as ancestor.
boolean	isLeaf(int node) Returns true if the node is a leaf_node.
boolean	isLeaf(Object node)
infovis.tree.DefaultTree.LeafIterator	leafIterator()
int	nextNode() Returns the next node to be returned by addNode.
boolean	removeNode(int node) Removes a node from the tree.
void	removeRow(int row) Removes a specified row.
void	removeTreeModelListener(TreeModelListener l)
void	reparent(int node, int newparent) Change the parent of a specified node, changing the structure.
void	valueForPathChanged(TreePath path, Object newValue)
void	visit(BreadthFirst.Visitor visitor) Traverse the tree with a depth first traversal, calling the visitor at each node.
void	visit(DepthFirst.Visitor visitor) Traverse the tree with a depth first traversal, calling the visitor at each node.
void	visit(DepthFirst.Visitor visitor, int root) Traverse the tree with a depth first traversal, calling the visitor at each node from a specified root.

Methods inherited from class infovis.table.DefaultDynamicTable

getLastRow, getRowCount, isRowValid, iterator, reverseIterator

Methods inherited from class infovis.table.DefaultTable

addColumn, addTableModelListener, disableNotify, enableNotify, fireTableChanged, fireTableDataChanged, fireTableDataChanged, fireTableStructureChanged, getColumn, getColumnAt, getColumnClass, getColumnCount, getColumnName, getObjectFromRow, getRowFromObject, getTable, getValueAt, hasTableModelListener, indexOf, indexOf, isCellEditable, isColumnInternal, removeColumn, removeTableModelListener, setColumnAt, setValueAt, stateChanged

Methods inherited from class infovis.column.ColumnColumn

add, compare, compare, definedValue, fill, findColumn, get, getColumn, getColumn, getValueClass, set, setExtend

Methods inherited from class infovis.column.BasicObjectColumn

add, capacity, compare, compareValues, ensureCapacity, fill, format, getObjectAt, getOrder, getValueAt, getValueReference, hasUndefinedValue, indexOf, isValueUndefined, parse, remove, remove, setExtend, setObjectAt, setOrder, setSize, setValueAt, setValueUndefined, size

Methods inherited from class infovis.column.BasicColumn

addValue, addValueOrNull, firstValidRow, getClientProperty, getFormat, getMaxIndex, getMetadata, getMinIndex, getName, isEmpty, isInternal, lastValidRow, setFormat, setName, setValueOrNullAt, toString

Methods inherited from class infovis.column.AbstractColumn

addChangeListener, computeValueMap, computeValueMap, equalObj, equals, getLastModifiedRow

Methods inherited from class infovis.utils.ChangeManager

getModCount, removeChangeListener

Methods inherited from class java.lang.Object

getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface infovis.Table

addColumn, getColumn, getColumnAt, getColumnCount, getLastRow, getRowCount, getTable, indexOf, indexOf, isRowValid, removeColumn, reverseIterator, setColumnAt

Methods inherited from interface infovis.Column

addChangeListener, addValue, addValueOrNull, capacity, disableNotify, enableNotify, ensureCapacity, getFormat, getMaxIndex, getMinIndex, getName, getValueAt, getValueClass, hasUndefinedValue, isEmpty, isInternal, isValueUndefined, iterator, removeChangeListener, setFormat, setName, setSize, setValueAt, setValueOrNullAt, setValueUndefined, size

Methods inherited from interface infovis.Metadata

getClientProperty, getMetadata

Methods inherited from interface cern.colt.function.IntComparator

compare, equals

Methods inherited from interface javax.swing.table.TableModel

addTableModelListener, getColumnClass, getColumnName, getValueAt, isCellEditable, removeTableModelListener, setValueAt

Field Detail

CHILD_COLUMN

public static final String CHILD_COLUMN

Name of the IntColumn referencing the first child of a node.

See Also:

Constant Field Values

NEXT_COLUMN

public static final String NEXT_COLUMN

Name of the IntColumn referencing the next sibling of a node.

See Also:

Constant Field Values

LAST_COLUMN

public static final String LAST_COLUMN

Name of the IntColumn referencing the last child of a node.

See Also:

Constant Field Values

PARENT_COLUMN

public static final String PARENT_COLUMN

Name of the IntColumn referencing the parent of a node.

See Also:

Constant Field Values

Constructor Detail

DefaultTree

public DefaultTree()

Creates a new DefaultTree object.

Method Detail

clear

public void clear()

Description copied from class: DefaultDynamicTable

Removes all of the elements from this column. The Column will be empty after this call returns. WARNING: if there is an associated format that maintains a status, such as a CategoricalFormat, it is not cleared so results may not be what you expected. The CategoricalFormat can be cleared explicitely if needed.

Specified by:

clear in interface Column

Specified by:

clear in interface Table

Overrides:

clear in class DefaultDynamicTable

See Also:

Table.clear()

addRow

public int addRow()

Description copied from class: DefaultDynamicTable

Creates a new row and returns it.

Specified by:

addRow in interface DynamicTable

Overrides:

addRow in class DefaultDynamicTable

Returns:

the new created row.

removeRow

public void removeRow(int row)

Description copied from class: DefaultDynamicTable

Removes a specified row.

Specified by:

removeRow in interface DynamicTable

Overrides:

removeRow in class DefaultDynamicTable

Parameters:

row - the row to remove.

getChild

public int getChild(int node,
                    int index)

Description copied from interface: Tree

Returns the nth child of a node.

Specified by:

getChild in interface Tree

Parameters:

node - the node

index - the index if the requested child

Returns:

the requested child or NIL if node has not so many children.

See Also:

Tree.getChild(int, int)

getParent

public int getParent(int node)

Returns the parent of a node.

Specified by:

getParent in interface Tree

Parameters:

node - the node

Returns:

the parent or the NIL value if node is the top node

childrenIterator

public RowIterator childrenIterator(int node)

Returns the iterator over the children of a node.

Specified by:

childrenIterator in interface Tree

Parameters:

node - the node

Returns:

the iterator over the children of the node

leafIterator

public infovis.tree.DefaultTree.LeafIterator leafIterator()

addNode

public int addNode(int par)

Adds a node to the tree.

Specified by:

addNode in interface Tree

Parameters:

par - the parent of the node.

Returns:

the created node.

Throws:

ArrayIndexOutOfBoundsException - DOCUMENT ME!

getNodeCount

public int getNodeCount()

Description copied from interface: Tree

Returns the number of proper nodes in the Tree. Can be different than the value returned by getRowCount if nodes have been removed.

Specified by:

getNodeCount in interface Tree

Returns:

the number of proper nodes in the Tree.

removeNode

public boolean removeNode(int node)

Description copied from interface: Tree

Removes a node from the tree.

Specified by:

removeNode in interface Tree

Parameters:

node - the node to remove

Returns:

true if the node has been removed.

nextNode

public int nextNode()

Returns the next node to be returned by addNode.

Specified by:

nextNode in interface Tree

Returns:

the next node to be returned by addNode.

reparent

public void reparent(int node,
                     int newparent)

Change the parent of a specified node, changing the structure.

Specified by:

reparent in interface Tree

Parameters:

node - the node.

newparent - the new parent.

Throws:

RuntimeException - if the node is an ancestor of the parent.

isAncestor

public boolean isAncestor(int node,
                          int par)

Returns true if the first node has the second node as ancestor.

Specified by:

isAncestor in interface Tree

Parameters:

node - the node.

par - the tested ancestor.

Returns:

true if the first node has the second node as ancestor.

getIndexOfChild

public int getIndexOfChild(int node)

getDepth

public int getDepth(int node)

Returns the depth of a node using either a depth column if it has been computed or the computeDepth method.

Specified by:

getDepth in interface Tree

Parameters:

node - the node.

Returns:

the depth of the node.

getChildCount

public int getChildCount(int node)

Returns the degree of a node using either a degree column if it has been computed or the computeDegree method.

Specified by:

getChildCount in interface Tree

Parameters:

node - the node.

Returns:

the depth of the node.

getFirstChild

public int getFirstChild(int node)

Returns the first child of a node.

Parameters:

node - the node

Returns:

the first child or NIL value if node has no child

getNextSibling

public int getNextSibling(int node)

Returns the next sibling of a node.

Parameters:

node - the node

Returns:

the next sibling or the NIL value if node is the last sibling

getLastChild

public int getLastChild(int node)

Returns the last child of a node.

Parameters:

node - the node

Returns:

the last child or the NIL value if node has no child.

computeDepth

public int computeDepth(int node)

Computes the depth of the node in the tree and return it.

Parameters:

node - the node.

Returns:

the depth of the node in the tree.

computeDegree

public int computeDegree(int node)

Returns the degree of a node, i˙e˙ the number of children.

Parameters:

node - the node

Returns:

the degree of the node

isLeaf

public boolean isLeaf(int node)

Returns true if the node is a leaf_node. Use this method rather than degree(node)==0

Specified by:

isLeaf in interface Tree

Parameters:

node - the node

Returns:

true if the node is a leaf_node.

children

public int[] children(int node)

Returns a table of children of this node.

Parameters:

node - the node.

Returns:

a table of childen of the given node or null is the node has no child.

visit

public void visit(DepthFirst.Visitor visitor)

Traverse the tree with a depth first traversal, calling the visitor at each node.

Parameters:

visitor - the DepthFirstVisitor.

visit

public void visit(DepthFirst.Visitor visitor,
                  int root)

Traverse the tree with a depth first traversal, calling the visitor at each node from a specified root.

Parameters:

visitor - the DepthFirstVisitor.

root - the starting node.

visit

public void visit(BreadthFirst.Visitor visitor)

Traverse the tree with a depth first traversal, calling the visitor at each node.

Parameters:

visitor - the DepthFirstVisitor.

getRoot

public Object getRoot()

Specified by:

getRoot in interface TreeModel

getChild

public Object getChild(Object parent,
                       int index)

Specified by:

getChild in interface TreeModel

getChildCount

public int getChildCount(Object parent)

Specified by:

getChildCount in interface TreeModel

isLeaf

public boolean isLeaf(Object node)

Specified by:

isLeaf in interface TreeModel

valueForPathChanged

public void valueForPathChanged(TreePath path,
                                Object newValue)

Specified by:

valueForPathChanged in interface TreeModel

getIndexOfChild

public int getIndexOfChild(Object parent,
                           Object child)

Specified by:

getIndexOfChild in interface TreeModel

addTreeModelListener

public void addTreeModelListener(TreeModelListener l)

Specified by:

addTreeModelListener in interface TreeModel

removeTreeModelListener

public void removeTreeModelListener(TreeModelListener l)

Specified by:

removeTreeModelListener in interface TreeModel

buildPath

public Object[] buildPath(int node)