edu.umd.cs.fuzzyTree
Class FuzzyTreeModel

java.lang.Object
  |
  +--edu.umd.cs.fuzzyTree.FuzzyTreeModel
All Implemented Interfaces:
javax.swing.tree.TreeModel

public class FuzzyTreeModel
extends java.lang.Object
implements javax.swing.tree.TreeModel

TreeModel used by FuzzyTree to display a partial tree of an XML document. Each node in the tree is assigned a score which is a relative measure of how valuable the node is to be displayed. Expanding and collapsing subtrees are accomplished by adjusting the scores of nodes to add/remove them. Scores are assigned by the ScoreProcessor class. The class has a variety of parameters which are used in the score increase/decrease algorithms, and which can be modified to produce different behavior.


Inner Class Summary
private static class FuzzyTreeModel.UserAction
          Simple data structure, consists of affected node and an associated score change.
 
Field Summary
private  java.io.PrintWriter _actionsOutput
          Debug output; output to System.out, unless the enviroment variable actionsFilename is specified.
private  DataNode _activeNode
          Node that was last clicked on, which is highlighted.
private  java.io.PrintWriter _debugOutput
          Debug output; output to System.out, unless the environment variable debugFilename is specified
(package private)  javax.swing.event.EventListenerList _listeners
          Listeners of TreeModel events.
private  int _numDisplayedNodes
          Number of nodes currently being displayed in addition to the root.
(package private)  java.util.Comparator _preorderIndexComparator
          For sorting in ascending order of preorder index.
private  ScoreGenerator _scoreGenerator
          For creating initial sorted list from the DataGraph.
private  java.util.ArrayList _sortedNodeList
          A sorted list of all of the DataNodes in the DataGraph.
private  java.util.ArrayList _temporaryUserActionList
          List of temporary actions.
private  DisplayNode _treeRoot
          Root of the displayed tree.
private  java.util.ArrayList _userActions
          List of user actions.
private  int _userHistorySize
          Number of user history entries to maintain.
(package private) static DataGraph dataGraph
          Reference to the XML data graph.
static int debugLevel
          Debug levels (each level includes actions of lower levels).
private static float decreaseReductionFactor
          Factor by which to reduce score decreases when moving down a subtree.
private static float decreaseThresholdValue
          Threshold value at which score decreases are no longer applied.
private static float increaseReductionFactor
          Factor by which to reduce score increases when moving down a subtree.
private static float increaseThresholdValue
          Threshold value at which score increases are no longer applied.
private static int INSERT_NODE_AFTER
          Policy for nodes with the same score value
private static int INSERT_NODE_BEFORE
          Policy for nodes with the same score value
private static float maxCollapseFactor
          Maximum factor of score to decrease score when collasping.
private static float maxExpandFactor
          Maximum factor of score to increase score when expanding.
private static int minChildrenToCollapse
          Minimum number of children that should be removed when user collapses a subtree.
private static int minChildrenToExpand
          Minimum number of children that should be displayed when user expands a subtree.
private static float minCollapseFactor
          Maximum factor of score to decrease score when collasping.
private static float minExpandFactor
          Minimum factor of score to increase score when expanding.
static int NODE_CLOSED
          Node is closed (none of its children are displayed
static int NODE_FULLY_OPEN
          Node is fully open (all of its children are displayed).
static int NODE_PARTIALLY_OPEN
          Node is partially open (some of its children are displayed).
 
Constructor Summary
FuzzyTreeModel(java.lang.String xmlFilename)
          Create FuzzyTreeModel from the XML file passed in.
 
Method Summary
private  void addDisplayNode(DataNode node)
          Adds node to the display tree.
private  void addDisplayNodeRange(int currentNumNodes)
          Adds _numDisplayedNodes - currentNumNodes nodes to the display tree.
 void addTreeModelListener(javax.swing.event.TreeModelListener l)
           
private  boolean addUserAction(java.util.ArrayList actionList)
          Adds a new set of user actions to the user history.
private  java.io.PrintWriter createDebugOutput(java.lang.String filenameProperty, boolean autoFlush)
          Creates a PrintWriter from a file with name specified by the environment variable filenameProperty.
private  void debugFlush(int messageLevel)
           
private  void debugPrint(int messageLevel, java.lang.String message)
          Prints the debug string message if messageLevel <= debugLevel
private  void debugPrintln(int messageLevel, java.lang.String message)
          Println the debug string message if messageLevel <= debugLevel
private  int decreaseNodeScore(DataNode dataNode, float decreaseFactor, java.util.ArrayList actionList)
          Reduces the score of dataNode by decreaseFactor.
private  int decreaseSubtreeScore(DataNode dataNode, float decreaseFactor, java.util.ArrayList actionList)
          Decreases the scores in the subtree of which dataNode is the root, by decreaseFactor.
private  void doSanityCheck()
          For debugging purposes--executes only if debugLevel >= 3.
protected  void finalize()
           
protected  void fireTreeStructureChanged()
           
 java.lang.Object getChild(java.lang.Object parent, int index)
           
 int getChildCount(java.lang.Object parent)
           
 int getIndexOfChild(java.lang.Object parent, java.lang.Object child)
           
static int getNodeState(java.lang.Object node)
          Returns the open/close state of node.
 int getNumDisplayedNodes()
          Returns number of nodes that are displayed
 FuzzyTreeParameters getParameters()
          Get parameters used in score adjusting algorithms
 java.lang.Object getRoot()
           
 int getTotalNodes()
          Returns total number of nodes in the tree.
private  int increaseNodeScore(DataNode dataNode, float increaseFactor, java.util.ArrayList actionList)
          Increases the score of dataNode by increaseFactor.
private  int increaseSubtreeScore(DataNode dataNode, float increaseFactor, java.util.ArrayList actionList)
          Increases the scores in the subtree of which dataNode is the root, by increaseFactor.
private  boolean inflateNodeScore(DataNode sourceNode, FuzzyTreeModel.UserAction temporaryUserAction)
          Inflates the score of sourceNode such that it will be the highest-scoring node in the tree.
 boolean isActiveNode(java.lang.Object node)
          Returns true if node should be highlighted.
 boolean isLeaf(java.lang.Object node)
           
static boolean isOrphan(java.lang.Object node)
          Returns true if node is not a child of its parent, but rather a child of an ancestor.
private static float loadPercentProperty(java.lang.String propertyName, int defaultValue)
          Loads a property value that is a percentage, returns the value divided by 100.
private  void moveSubtree(DataNode child, DisplayNode displayParent)
          Moves child under displayParent, if it is in the displayed tree; otherwise, any displayed descendants of child are moved to under displayParent.
private  void printDisplayedNodes(java.io.PrintWriter out)
          For debugging, executes only if debugLevel < 5.
private  void printDisplayedNodes(java.io.PrintWriter out, int numNodesToPrint)
          For debugging, executes only if debugLevel < 5.
private  void removeDisplayNode(DataNode node)
          Removes node from the display tree.
private  void removeDisplayNodeRange(int currentDisplayedNodes)
          Removes currentDisplayedNodes - _numDisplayedNodes nodes from the displayTree.
 void removeTreeModelListener(javax.swing.event.TreeModelListener l)
           
private  int repositionNodeInSortedList(DataNode node, int insertPolicy)
          Moves node from its current position in _sortedNodeList to a new location based on its current score.
 void setNumDisplayedNodes(int newValue)
          Set new value for number of displayed nodes
 void setParameters(FuzzyTreeParameters newParameters)
          Set parameters for score adjusting algorithms
private  void undoAction(java.util.ArrayList actions)
          Iterates through list of user actions and reverses the score change associated with each one.
private  void undoTemporaryAction()
          Undoes the score change associated with the last temporary action.
 void userCollapseSubtree(java.lang.Object node, boolean fullyCollapse)
          Tries to collapse the subtree that node is the root of.
 void userExpandSubtree(java.lang.Object node, boolean fullyExpand)
          Tries to expand the subtree that node is the root of.
 void valueForPathChanged(javax.swing.tree.TreePath path, java.lang.Object newValue)
          TreeModel method.
 
Methods inherited from class java.lang.Object
, clone, equals, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait
 

Field Detail

minExpandFactor

private static float minExpandFactor
Minimum factor of score to increase score when expanding.

Default is 5% (.05) Default can be changed with the environment variable minExpandPercent.


maxCollapseFactor

private static float maxCollapseFactor
Maximum factor of score to decrease score when collasping. Value is negative.

Default is -5% (-.05) Default can be changed with the environment variable maxCollapsePercent.


maxExpandFactor

private static float maxExpandFactor
Maximum factor of score to increase score when expanding.

Default is 50% (.5) Default can be changed with the environment variable maxExpandPercent.


minCollapseFactor

private static float minCollapseFactor
Maximum factor of score to decrease score when collasping. Value is negative.

Default is -50% (-.50) Default can be changed with the environment variable minCollapsePercent.


minChildrenToExpand

private static int minChildrenToExpand
Minimum number of children that should be displayed when user expands a subtree. Score increase will be applied so that at least this many nodes are displayed, as long as the factor increase is less than maxExpandFactor.

Default value is 3. Default can be changed with the environment variable childrenToExpand.


minChildrenToCollapse

private static int minChildrenToCollapse
Minimum number of children that should be removed when user collapses a subtree. Score decrease will be applied so that at least this many nodes are removed, as long as the factor decrease is greater than minCollapseFactor.

Default value is 3. Default can be changed with the environment variable childrenToCollapse.


increaseReductionFactor

private static float increaseReductionFactor
Factor by which to reduce score increases when moving down a subtree. First level children will have score increase of parentIncrease * increaseReductionPercent, and so on.

Default value is 40%. Default can be changed with the environment variable increaseReductionPercent.


decreaseReductionFactor

private static float decreaseReductionFactor
Factor by which to reduce score decreases when moving down a subtree. First level children will have score decrease of parentDecrease * decreaseReductionPercent, and so on.

Default value is 40%. Default can be changed with the environment variable decreaseReductionPercent.


increaseThresholdValue

private static float increaseThresholdValue
Threshold value at which score increases are no longer applied.

Default value is 4%. Default can be changed with the environment variable increaseThresholdPercent.


decreaseThresholdValue

private static float decreaseThresholdValue
Threshold value at which score decreases are no longer applied.

Default value is -4%. Default can be changed with the environment variable decreaseThresholdPercent.


_userHistorySize

private int _userHistorySize
Number of user history entries to maintain. When the user history is full, the oldest user history item is undone. Default value is 10, can be changed with the environment variable userHistorySize.
See Also:
_userActions

dataGraph

static DataGraph dataGraph
Reference to the XML data graph.

_scoreGenerator

private ScoreGenerator _scoreGenerator
For creating initial sorted list from the DataGraph.

_sortedNodeList

private java.util.ArrayList _sortedNodeList
A sorted list of all of the DataNodes in the DataGraph. Nodes are sorted based on the DataNode's score field.

_userActions

private java.util.ArrayList _userActions
List of user actions. Size of list is _userHistorySize

ArrayList of ArrayList of UserAction


_temporaryUserActionList

private java.util.ArrayList _temporaryUserActionList
List of temporary actions. Temporary actions are score changes that last only until the next action. Examples: increasing the score of a node that was expanded or collapsed to ensure that it will be visible for at least one action

ArrayList of UserAction.


_numDisplayedNodes

private int _numDisplayedNodes
Number of nodes currently being displayed in addition to the root. (_numDisplayNodes + 1 nodes are always displayed) Setter and getter methods do the +/- 1 adjustment. Nodes from index 0 to _numDisplayedNodes - 1 of _sortedNodeList will be displayed

_treeRoot

private DisplayNode _treeRoot
Root of the displayed tree. Is always displayed, so is not in _sortedNodeList.

_activeNode

private DataNode _activeNode
Node that was last clicked on, which is highlighted.

_debugOutput

private java.io.PrintWriter _debugOutput
Debug output; output to System.out, unless the environment variable debugFilename is specified

_actionsOutput

private java.io.PrintWriter _actionsOutput
Debug output; output to System.out, unless the enviroment variable actionsFilename is specified. If debug level is set, all user actions are outputed to this.

debugLevel

public static int debugLevel
Debug levels (each level includes actions of lower levels).

_listeners

javax.swing.event.EventListenerList _listeners
Listeners of TreeModel events.

_preorderIndexComparator

java.util.Comparator _preorderIndexComparator
For sorting in ascending order of preorder index.

NODE_FULLY_OPEN

public static final int NODE_FULLY_OPEN
Node is fully open (all of its children are displayed).

NODE_CLOSED

public static final int NODE_CLOSED
Node is closed (none of its children are displayed

NODE_PARTIALLY_OPEN

public static final int NODE_PARTIALLY_OPEN
Node is partially open (some of its children are displayed).

INSERT_NODE_BEFORE

private static final int INSERT_NODE_BEFORE
Policy for nodes with the same score value
See Also:
repositionNodeInSortedList(edu.umd.cs.fuzzyTree.DataNode, int)

INSERT_NODE_AFTER

private static final int INSERT_NODE_AFTER
Policy for nodes with the same score value
See Also:
repositionNodeInSortedList(edu.umd.cs.fuzzyTree.DataNode, int)
Constructor Detail

FuzzyTreeModel

public FuzzyTreeModel(java.lang.String xmlFilename)
               throws DataGraph.DataGraphException
Create FuzzyTreeModel from the XML file passed in.
Parameters:
xmlFilename - XML file to open and create tree from. File must be a tree (not a graph)
Throws:
DataGraph.DataGraphException - if there was an error opening/parsing the file
Method Detail

getRoot

public java.lang.Object getRoot()
Specified by:
getRoot in interface javax.swing.tree.TreeModel

getChild

public java.lang.Object getChild(java.lang.Object parent,
                                 int index)
Specified by:
getChild in interface javax.swing.tree.TreeModel

getChildCount

public int getChildCount(java.lang.Object parent)
Specified by:
getChildCount in interface javax.swing.tree.TreeModel

isLeaf

public boolean isLeaf(java.lang.Object node)
Specified by:
isLeaf in interface javax.swing.tree.TreeModel

valueForPathChanged

public void valueForPathChanged(javax.swing.tree.TreePath path,
                                java.lang.Object newValue)
TreeModel method. Not implemented.
Specified by:
valueForPathChanged in interface javax.swing.tree.TreeModel

getIndexOfChild

public int getIndexOfChild(java.lang.Object parent,
                           java.lang.Object child)
Specified by:
getIndexOfChild in interface javax.swing.tree.TreeModel

addTreeModelListener

public void addTreeModelListener(javax.swing.event.TreeModelListener l)
Specified by:
addTreeModelListener in interface javax.swing.tree.TreeModel

removeTreeModelListener

public void removeTreeModelListener(javax.swing.event.TreeModelListener l)
Specified by:
removeTreeModelListener in interface javax.swing.tree.TreeModel

isActiveNode

public boolean isActiveNode(java.lang.Object node)
Returns true if node should be highlighted.
See Also:
_activeNode

getTotalNodes

public int getTotalNodes()
Returns total number of nodes in the tree.

getParameters

public FuzzyTreeParameters getParameters()
Get parameters used in score adjusting algorithms
Returns:
parameters used by score adjusting algorithms

setParameters

public void setParameters(FuzzyTreeParameters newParameters)
Set parameters for score adjusting algorithms
Parameters:
newParameters - new parameter values

getNumDisplayedNodes

public int getNumDisplayedNodes()
Returns number of nodes that are displayed
Returns:
number of displayed nodes, including the root

setNumDisplayedNodes

public void setNumDisplayedNodes(int newValue)
Set new value for number of displayed nodes
Parameters:
newValue - new number of nodes to display

isOrphan

public static boolean isOrphan(java.lang.Object node)
Returns true if node is not a child of its parent, but rather a child of an ancestor.
See Also:
DisplayNode.isOrphan()

getNodeState

public static int getNodeState(java.lang.Object node)
Returns the open/close state of node.
Returns:
One of NODE_FULLY_OPEN, NODE_CLOSED, NODE_PARTIALLY_OPEN

userExpandSubtree

public void userExpandSubtree(java.lang.Object node,
                              boolean fullyExpand)
Tries to expand the subtree that node is the root of. Expansion is done through score changes and amount of score increase is constrained by minExpandFactor and maxExpandFactor. Score change to display childrenToExpand nodes is applied if fullyExpand is false, otherwise, score change to display all children is applied.

Applies score changes to descendants further down the tree, but the score increase is reduced at each level by increaseReductionFactor. Score change is not applied if it is less than increaseThresholdValue.


userCollapseSubtree

public void userCollapseSubtree(java.lang.Object node,
                                boolean fullyCollapse)
Tries to collapse the subtree that node is the root of. Collapsing is done through score changes and amount of score decrease is constrained by minCollapseFactor and maxCollapseFactor. Applies score change to remove childrenToCollapse nodes if fullyExpand is false, otherwise, applies score change to remove all children.

Applies score changes to descendants further down the tree, but the score decrease will is reduced at each level by decreaseReductionFactor. Score change is not applied if it is less than decreaseThresholdValue.


fireTreeStructureChanged

protected void fireTreeStructureChanged()

increaseNodeScore

private int increaseNodeScore(DataNode dataNode,
                              float increaseFactor,
                              java.util.ArrayList actionList)
Increases the score of dataNode by increaseFactor. Adds action of updating the score to actionList.
Parameters:
dataNode - the node to which to apply the score change
increaseFactor - factor score increase
actionList - list to add the action of score increase to
Returns:
the number of nodes that were added to the display tree (0 or 1)

increaseSubtreeScore

private int increaseSubtreeScore(DataNode dataNode,
                                 float increaseFactor,
                                 java.util.ArrayList actionList)
Increases the scores in the subtree of which dataNode is the root, by increaseFactor. Reduces the amount by which scores are increased at each level by increaseReductionFactor. Adds the action of updating the score to actionList.

Method is called recursively.

Parameters:
dataNode - the node to which to apply the score change
increaseFactor - factor score increase
actionList - list to add the action of score increase to
Returns:
the number of nodes that were added to the display tree

decreaseNodeScore

private int decreaseNodeScore(DataNode dataNode,
                              float decreaseFactor,
                              java.util.ArrayList actionList)
Reduces the score of dataNode by decreaseFactor. Adds action of updating the score to actionList.
Parameters:
dataNode - the node to which to apply the score change
decreaseFactor - factor score decrease
actionList - list to add the action of score decrease to
Returns:
the number of nodes that were removed from the display tree (0 or 1)

decreaseSubtreeScore

private int decreaseSubtreeScore(DataNode dataNode,
                                 float decreaseFactor,
                                 java.util.ArrayList actionList)
Decreases the scores in the subtree of which dataNode is the root, by decreaseFactor. Reduces the amount by which scores are decreased at each level by decreaseReductionFactor. Adds the action of updating the score to actionList.

Does not apply score change to nodes that are in the display tree.

Method is called recursively.

Parameters:
dataNode - the node to which to apply the score change
decreaseFactor - factor score decrease
actionList - list to add the action of score decrease to
Returns:
the number of nodes that were removed from the display tree

inflateNodeScore

private boolean inflateNodeScore(DataNode sourceNode,
                                 FuzzyTreeModel.UserAction temporaryUserAction)
Inflates the score of sourceNode such that it will be the highest-scoring node in the tree. Sets the score change amount in temporaryUserAction.
Parameters:
sourceNode - node to which to apply the score change
temporaryUserAction - user action to record the score change. actionNode field should already be set
Returns:
true if node was added to the tree as a result of score inflation; false otherwise

undoTemporaryAction

private void undoTemporaryAction()
Undoes the score change associated with the last temporary action.
See Also:
_temporaryUserActionList

addUserAction

private boolean addUserAction(java.util.ArrayList actionList)
Adds a new set of user actions to the user history. Undoes old actions if the list is full. This method should be called before score change values are calculated, as an undo will change the state of the tree.
Returns:
true if adding the action list resulted in another action being undone

undoAction

private void undoAction(java.util.ArrayList actions)
Iterates through list of user actions and reverses the score change associated with each one. Nodes are added/removed from the display tree as necessary
Parameters:
actions - list of UserActions to undo

addDisplayNodeRange

private void addDisplayNodeRange(int currentNumNodes)
Adds _numDisplayedNodes - currentNumNodes nodes to the display tree.
Parameters:
currentNumNodes - the number of nodes already displayed

addDisplayNode

private void addDisplayNode(DataNode node)
Adds node to the display tree. It is positioned under any parent already in the tree. If its parent is not in the tree, it is positioned under its closest ancestor, and it will be an orphan. Any descendants the node has that are in the display tree are positioned under it.
Parameters:
node - node to add to the display tree

removeDisplayNodeRange

private void removeDisplayNodeRange(int currentDisplayedNodes)
Removes currentDisplayedNodes - _numDisplayedNodes nodes from the displayTree.
Parameters:
currentNumNodes - the number of nodes currently displayed

removeDisplayNode

private void removeDisplayNode(DataNode node)
Removes node from the display tree. Children become the children of node's parent.
Parameters:
node - node to remove from the display tree

moveSubtree

private void moveSubtree(DataNode child,
                         DisplayNode displayParent)
Moves child under displayParent, if it is in the displayed tree; otherwise, any displayed descendants of child are moved to under displayParent.

Method is called recursively.


repositionNodeInSortedList

private int repositionNodeInSortedList(DataNode node,
                                       int insertPolicy)
Moves node from its current position in _sortedNodeList to a new location based on its current score.

If insertPolicy is INSERT_NODE_BEFORE, the node is inserted before all other nodes with the same score; if it is INSERT_NODE_AFTER node is inserted after all other nodes with the same score.

Parameters:
node - node to be repositioned in _sortedNodeList
insertPolicy - one of INSERT_NODE_BEFORE, INSERT_NODE_AFTER
Returns:
the new index of node

finalize

protected void finalize()
Overrides:
finalize in class java.lang.Object

doSanityCheck

private void doSanityCheck()
For debugging purposes--executes only if debugLevel >= 3. Checks to ensure that only numDisplayedNodes - 1 of _sortedNodeList are displayed. Otherwise, prints a message to System.out.

loadPercentProperty

private static float loadPercentProperty(java.lang.String propertyName,
                                         int defaultValue)
Loads a property value that is a percentage, returns the value divided by 100.

debugPrintln

private void debugPrintln(int messageLevel,
                          java.lang.String message)
Println the debug string message if messageLevel <= debugLevel

debugPrint

private void debugPrint(int messageLevel,
                        java.lang.String message)
Prints the debug string message if messageLevel <= debugLevel

debugFlush

private void debugFlush(int messageLevel)

createDebugOutput

private java.io.PrintWriter createDebugOutput(java.lang.String filenameProperty,
                                              boolean autoFlush)
Creates a PrintWriter from a file with name specified by the environment variable filenameProperty. If file cannot be created, System.out is returned.

printDisplayedNodes

private void printDisplayedNodes(java.io.PrintWriter out,
                                 int numNodesToPrint)
For debugging, executes only if debugLevel < 5.

printDisplayedNodes

private void printDisplayedNodes(java.io.PrintWriter out)
For debugging, executes only if debugLevel < 5.


Web Accessibility