Tree.java
/*
* $Source$
* $Revision$
*
* Copyright (C) 2001 Myles Chippendale
*
* Part of Melati (http://melati.org), a framework for the rapid
* development of clean, maintainable web applications.
*
* Melati is free software; Permission is granted to copy, distribute
* and/or modify this software under the terms either:
*
* a) the GNU General Public License as published by the Free Software
* Foundation; either version 2 of the License, or (at your option)
* any later version,
*
* or
*
* b) any version of the Melati Software License, as published
* at http://melati.org
*
* You should have received a copy of the GNU General Public License and
* the Melati Software License along with this program;
* if not, write to the Free Software Foundation, Inc.,
* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA to obtain the
* GNU General Public License and visit http://melati.org to obtain the
* Melati Software License.
*
* Feel free to contact the Developers of Melati (http://melati.org),
* if you would like to work out a different arrangement than the options
* outlined here. It is our intention to allow Melati to be used by as
* wide an audience as possible.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* Contact details for copyright holder:
*
* Myles Chippendale <mylesc At paneris.org>
*/
package org.melati.util;
import java.util.Vector;
import org.melati.poem.util.Order;
import org.melati.poem.util.SortUtils;
import org.melati.poem.Treeable;
/**
* A whole tree.
*/
public class Tree {
private Treeable[] orig_roots;
private TreeNode[] roots;
private int depth;
/**
* Constructor from root node.
* @param node root node
*/
public Tree(Treeable node) {
orig_roots = new Treeable[1];
orig_roots[0] = node;
this.depth = 0;
roots = new TreeNode[] { new TreeNode(node, 0) };
}
/**
* Constructor from root node with anticipated depth.
* @param node root node
* @param depth the anticipated depth
*/
public Tree(Treeable node, int depth) {
orig_roots = new Treeable[1];
orig_roots[0] = node;
this.depth = depth;
roots = new TreeNode[] { new TreeNode(node, depth) };
}
/**
* Constructor for a multi-rooted tree.
* @param nodes the root nodes
*/
public Tree(Treeable[] nodes) {
orig_roots = nodes;
this.depth = 0;
roots = TreeNode.augment(nodes, 0);
}
/**
* Constructor for a multi-rooted tree with anticipated depth.
* @param nodes the root nodes
* @param depth anticipated depth
*/
public Tree(Treeable[] nodes, int depth) {
orig_roots = nodes;
this.depth = depth;
roots = TreeNode.augment(nodes, depth);
}
/**
* @return the roots
*/
public Treeable[] getTreeableRoots() {
return orig_roots;
}
/**
* @return the depth, possibly anticipated
*/
public int getDepth() {
return depth;
}
/**
* Retrieve all the nodes down to a given depth.
* @param depthP
* Only apply the function to nodes at or above this depth. A negative
* depth means apply this to all nodes in the tree
* @param depthFirst
* If true, traverse the tree depth-first, otherwise traverse it
* breadth-first
* @return all the nodes down to the given depth
*/
public Vector<TreeNode> flattened(int depthP, boolean depthFirst) {
Vector<TreeNode> results = new Vector<TreeNode>();
Vector<TreeNode> agenda = new Vector<TreeNode>();
for (int i = 0; i < roots.length; i++) {
agenda.addElement(roots[i]);
}
while (!agenda.isEmpty()) {
TreeNode current = (TreeNode)agenda.firstElement();
agenda.removeElementAt(0);
results.addElement(current);
if (depthP < 0 || current.depth < depthP) {
TreeNode[] kids = current.getChildren();
if (kids != null) {
for (int i = 0; i < kids.length; i++) {
if (depthFirst)
// Maybe not the most efficient ...?
agenda.insertElementAt(kids[i], i);
else
agenda.addElement(kids[i]);
}
}
}
}
return results;
}
/**
* Retrieve all the nodes down to a given depth, depth-first.
* @param depthP
* Only apply the function to nodes at or above this depth. A negative
* depth means apply this to all nodes in the tree
* @return all the nodes down to the given depth
*/
public Vector<TreeNode> flattened(int depthP) {
return flattened(depthP, true);
}
/**
* @return all the nodes, depth-first
*/
public Vector<TreeNode> flattened() {
return flattened(-1);
}
/**
* Apply the Function to each node in the tree.
*
* @param func the Function to apply
* @param depthP
* Only apply the function to nodes at or above this depth. A negative
* depth means apply this to all nodes in the tree
* @param depthFirst
* If true, traverse the tree depth-first, otherwise traverse it
* breadth-first
* @return a Vector nodes that have had func applied to them
*/
public Vector<TreeNode> apply(Function func, int depthP, boolean depthFirst) {
Vector<TreeNode> flattened = flattened(depthP, depthFirst);
for (int i = 0; i < flattened.size(); i++) {
flattened.setElementAt((TreeNode)func.apply(flattened.elementAt(i)), i);
}
return flattened;
}
/**
* Apply a function to all nodes, depth first.
* @param func the function to apply
* @return a vector of nodes to which the function has been applied
*/
public Vector<TreeNode> applyDepthFirst(Function func) {
return apply(func, -1, true);
}
/**
* Apply a function to all nodes to a given depth, depth first.
* @param func the function to apply
* @param depthP
* Only apply the function to nodes at or above this depth. A negative
* depth means apply this to all nodes in the tree
* @return a vector of nodes to which the function has been applied
*/
public Vector<TreeNode> applyDepthFirst(Function func, int depthP) {
return apply(func, depthP, true);
}
/**
* Apply a function to all nodes, breadth first.
* @param func the function to apply
* @return a vector of nodes to which the function has been applied
*/
public Vector<TreeNode> applyBreadthFirst(Function func) {
return apply(func, -1, false);
}
/**
* Apply a function to all nodes to a given depth, breadth first.
* @param func the function to apply
* @param depthP
* Only apply the function to nodes at or above this depth. A negative
* depth means apply this to all nodes in the tree
* @return a vector of nodes to which the function has been applied
*/
public Vector<TreeNode> applyBreadthFirst(Function func, int depthP) {
return apply(func, depthP, false);
}
/**
* Retrieve a sorted Vector of the tree's contents, down to the given depth.
* @param cmp an Ordering
* @param depthP
* Only return nodes at or above this depth. A negative
* depth means return all nodes in the tree
* @return a sorted Vector of the tree's contents, down to the given depth
*/
public Vector<TreeNode> sorted(Order cmp, int depthP) {
Vector<TreeNode> flattened = flattened(depthP);
TreeNode[] sorted = SortUtils.sorted(cmp, flattened);
System.arraycopy(sorted, 0, flattened, 0, sorted.length);
return flattened;
}
}