infovis.tree
Class DefaultTree

java.lang.Object
  extended by infovis.utils.ChangeManager
      extended by infovis.column.AbstractColumn
          extended by infovis.column.BasicColumn
              extended by infovis.column.BasicObjectColumn
                  extended by infovis.column.ColumnColumn
                      extended by infovis.table.DefaultTable
                          extended by infovis.table.DefaultDynamicTable
                              extended by 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)


Copyright 2005 by Jean-Daniel Fekete and INRIA, France All rights reserved.