Java/Collections Data Structure/Tree

A tree structure that maps inheritance hierarchies of classes

   
/*
 * The contents of this file are subject to the Sapient Public License
 * Version 1.0 (the "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at
 * http://carbon.sf.net/License.html.
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for
 * the specific language governing rights and limitations under the License.
 *
 * The Original Code is The Carbon Component Framework.
 *
 * The Initial Developer of the Original Code is Sapient Corporation
 *
 * Copyright (C) 2003 Sapient Corporation. All Rights Reserved.
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <p>This class creates a tree structure that maps inheritance hierarchies of
 * classes. A developer can place any number of classes into this object and
 * retrieve the closest super class or the class itself.</p>
 *
 *
 * Copyright 2001 Sapient
 * @since EJFW 2.7
 * @author Greg Hinkle, January 2001
 * @version $Revision: 1.4 $($Author: dvoet $ / $Date: 2003/05/05 21:21:23 $)
 */
public class ClassTree {
    protected ClassTreeNode bottom;

    /**
     * Constructs a ClassTree that represents all classes and interfaces that
     * are generalizations of the provided class. This ends up with a tree
     * structure of the inheritance hierarchy for that provided class all the
     * way up to java.lang.Object.
     * @param specificClass The class to build the tree for.
     */
    public ClassTree(Class specificClass) {
        this.bottom = ClassTreeNode.buildNode(specificClass);
    }
    public ClassTreeNode getBottom() {
        return this.bottom;
    }

    /**
     * Constructs an ordered list starting at the highest (most general) class
     * in the tree and moving down the tree, ensuring no generalization comes
     * after one of its specializations.
     * @return a list ordered as above
     */
    public List getOrderedList() {
        List list = new ArrayList();
        list.add(getBottom());
        buildList(getBottom(),list);
        Collections.sort(list);
        // Refactor list into a list of classes from a list of ClassTreeNodes
        for (int i = 0; i < list.size(); i++) {
            ClassTreeNode node = (ClassTreeNode) list.get(i);
            list.set(i,node.getObjectClass());
        }
        // Reverse the list so that the top class in the hierarchy comes first
        Collections.reverse(list);
        return list;
    }
    /**
     * <p>Build breadth first in order to maintain sudo ordering as per
     * class declarations (i.e. if A implements B, C... B is closer in the
     * chain to A than C is, because B comes first in the implements clause.</p>
     *
     * <p>Note that the list coming out here is preordered, but not natural
     * ordered. (i.e. some classes are out of order in relation to classes
     * they have direct relationships with. This is later fixed by a sort
     * on the list by natural ordering. Collecitons.sort, does preserve
     * the preordering for nodes that have no relationship.</p>
     *
     * @param node the node to be browsed.
     * @param output this list is altered to add the contents as they are
     *   browsed in breadth-first order. Start with a list containing only
     *   the bottom node.
     */
    private void buildList(ClassTreeNode node, List output) {
        for (int i = 0; i < node.getParents().size(); i++) {
            ClassTreeNode parent = (ClassTreeNode) node.getParents().get(i);
            if (!output.contains(parent)) {
                output.add(parent);
            }
        }
        List parents = node.getParents();
        for (int i = 0; i < parents.size(); i++) {
            ClassTreeNode parent = (ClassTreeNode) parents.get(i);
            buildList(parent, output);
        }
    }

    /**
     * <p>Inner class representing each node in the tree. Holds references to the
     * nodes children, parent and provides the Comparable interface for sorting
     * by inheritance hierarchy.</p>
     */
    public static class ClassTreeNode implements Comparable {
        /** The class of this node */
        protected Class objectClass;
        /** The map of children classes to their class names */
        protected List children;
        /** A reference to the parent node of this node */
        protected List parents;
        /**
         * <p>Constructs a ClassTreeNode with the given Class.</p>
         *
         * @param objectClass the Class of the node
         */
        public ClassTreeNode(Class objectClass) {
            this.children = new ArrayList();
            this.objectClass = objectClass;
            this.parents = new ArrayList();

        }
        public static ClassTreeNode buildNode(Class objectClass) {
            Map allNodes = new HashMap();
            return buildNode(objectClass, allNodes);
        }
        protected static ClassTreeNode buildNode(Class objectClass, Map allNodes) {
            ClassTreeNode node;
            if (allNodes.containsKey(objectClass)) {
                node = (ClassTreeNode) allNodes.get(objectClass);
            } else {
                node = new ClassTreeNode(objectClass);
                allNodes.put(objectClass, node);
            }
            // Add the implemented interfaces...
            Class[] superInterfaces = objectClass.getInterfaces();
            for (int i = 0; i < superInterfaces.length; i++) {
                Class superInterface = superInterfaces[i];
                ClassTreeNode parent = buildNode(superInterface);
                node.addParent(parent);
            }
            // Add the superclass after the interfaces...
            Class superClass = objectClass.getSuperclass();
            if (superClass != null) {
                ClassTreeNode parent = buildNode(superClass);
                node.addParent(parent);
            }
            return node;
        }

        public List getParents() {
            return this.parents;
        }
        public void addParent(ClassTreeNode node) {
            this.parents.add(node);
            node.addChild(this);
        }
        public boolean removeChild(ClassTreeNode node) {
            return this.children.remove(node);
        }
        public void addChild(ClassTreeNode node) {
            this.children.add(node);
        }
        public List getChildren() {
            return this.children;
        }
        public boolean equals(Object obj) {
            return ((ClassTreeNode)obj).getObjectClass().equals(this.objectClass);
        }
        public Class getObjectClass() {
            return this.objectClass;
        }
        public String getClassName() {
            return this.objectClass.getName();
        }

        public int hashCode() {
            return this.objectClass.hashCode();
        }
        /**
         * <p>Compares one class to another class by their inheritance tree.</p>
         *
         * @return an integer representing the comparison results as follows:<br>
         *    2  if this is a subclass of past in object<br>
         *    -2 if this is a superclass of past in object<br>
         *    0 if they are not related (and in relation to sorting, equal)<br>
         *    0  if they are the same<br>
         */
        public int compareTo(Object obj) {
            Class objClass = ((ClassTreeNode)obj).getObjectClass();
            if (objClass.equals(this.objectClass)) {
                return 0;
            } else if (this.objectClass.isAssignableFrom(objClass)) {
                return 2;
            } else if (objClass.isAssignableFrom(this.objectClass)) {
                return -2;
            } else {
                return 0;
            }
        }
    } // End of ClassTree$ClassTreeNode

}

Binary Tree

   
       /*
DEVELOPING GAME IN JAVA 
Caracteristiques
Editeur : NEW RIDERS 
Auteur : BRACKEEN 
Parution : 09 2003 
Pages : 972 
Isbn : 1-59273-005-1 
Reliure : Paperback 
Disponibilite : Disponible a la librairie 
*/
public class BinaryTreeTest {
  public static void main(String[] args) {
    new BinaryTreeTest().run();
  }
  static class Node {
    Node left;
    Node right;
    int value;
    public Node(int value) {
      this.value = value;
    }
  }
  public void run() {
    // build the simple tree from chapter 11.
    Node root = new Node(5);
    System.out.println("Binary Tree Example");
    System.out.println("Building tree with root value " + root.value);
    insert(root, 1);
    insert(root, 8);
    insert(root, 6);
    insert(root, 3);
    insert(root, 9);
    System.out.println("Traversing tree in order");
    printInOrder(root);
    System.out.println("Traversing tree front-to-back from location 7");
    printFrontToBack(root, 7);
  }
  public void insert(Node node, int value) {
    if (value < node.value) {
      if (node.left != null) {
        insert(node.left, value);
      } else {
        System.out.println("  Inserted " + value + " to left of "
            + node.value);
        node.left = new Node(value);
      }
    } else if (value > node.value) {
      if (node.right != null) {
        insert(node.right, value);
      } else {
        System.out.println("  Inserted " + value + " to right of "
            + node.value);
        node.right = new Node(value);
      }
    }
  }
  public void printInOrder(Node node) {
    if (node != null) {
      printInOrder(node.left);
      System.out.println("  Traversed " + node.value);
      printInOrder(node.right);
    }
  }
  /**
   * uses in-order traversal when the origin is less than the node"s value
   * 
   * uses reverse-order traversal when the origin is greater than the node"s
   * order
   */
  public void printFrontToBack(Node node, int camera) {
    if (node == null)
      return;
    if (node.value > camera) {
      // print in order
      printFrontToBack(node.left, camera);
      System.out.println("  Traversed " + node.value);
      printFrontToBack(node.right, camera);
    } else if (node.value < camera) {
      // print reverse order
      printFrontToBack(node.right, camera);
      System.out.println("  Traversed " + node.value);
      printFrontToBack(node.left, camera);
    } else {
      // order doesn"t matter
      printFrontToBack(node.left, camera);
      printFrontToBack(node.right, camera);
    }
  }
}

Data structure that mantains data in a ordered binary tree; each node is greater (smaller) or equal than its 2 sub-nodes, for all the hierarchy.

   
/*
 * JBoss, Home of Professional Open Source
 * Copyright 2005, JBoss Inc., and individual contributors as indicated
 * by the @authors tag. See the copyright.txt in the distribution for a
 * full listing of individual contributors.
 *
 * This is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * This software 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this software; if not, write to the Free
 * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
 */
import java.util.ruparator;
/**
 * Data structure that mantains data in a ordered binary tree; each node is
 * greater (smaller) or equal than its 2 sub-nodes, for all the hierarchy.
 * <p>
 * Elements of this data structure should either implement Comparable, or a
 * Comparator should be given as argument to the constructor.
 * 
 * @author 
 * @version $Revision: 2787 $
 */
@SuppressWarnings("unchecked")
public class Heap {
  private Comparator m_comparator;
  private int m_count;
  private Object[] m_nodes;
  /**
   * Creates a new Heap whose elements inserted implement the {@link Comparable}
   * interface.
   */
  public Heap() {
    this(null);
  }
  /**
   * Creates a new Heap whose elements are compared using the given
   * {@link Comparator}.
   * 
   * @param comparator
   */
  public Heap(Comparator comparator) {
    m_comparator = comparator;
    clear();
  }
  /**
   * Inserts the given element in this heap.
   * 
   * @param obj
   * 
   * @see #extract
   */
  public void insert(Object obj) {
    int length = m_nodes.length;
    // Expand if necessary
    if (m_count == length) {
      Object[] newNodes = new Object[length + length];
      System.arraycopy(m_nodes, 0, newNodes, 0, length);
      m_nodes = newNodes;
    }
    // Be cur_slot the first unused slot index; be par_slot its parent index.
    // Start from cur_slot and walk up the tree comparing the object to
    // insert with the object at par_slot; if it"s smaller move down the object
    // at par_slot,
    // otherwise cur_slot is the index where insert the object. If not done,
    // shift up the tree so that now cur_slot is the old par_slot and
    // par_slot is the parent index of the new cur_slot (so the grand-parent
    // index of the old cur_slot) and compare again.
    int k = m_count;
    while (k > 0) {
      int par = parent(k);
      if (compare(obj, m_nodes[par]) < 0) {
        m_nodes[k] = m_nodes[par];
        k = par;
      } else
        break;
    }
    m_nodes[k] = obj;
    ++m_count;
  }
  /**
   * Removes and returns the least element of this heap.
   * 
   * @return the extracted object
   * 
   * @see #insert
   * @see #peek
   */
  public Object extract() {
    if (m_count < 1) {
      return null;
    } else {
      int length = m_nodes.length >> 1;
      // Shrink if necessary
      if (length > 5 && m_count < (length >> 1)) {
        Object[] newNodes = new Object[length];
        System.arraycopy(m_nodes, 0, newNodes, 0, length);
        m_nodes = newNodes;
      }
      //
      int k = 0;
      Object ret = m_nodes[k];
      --m_count;
      Object last = m_nodes[m_count];
      for (;;) {
        int l = left(k);
        if (l >= m_count) {
          break;
        } else {
          int r = right(k);
          int child = (r >= m_count || compare(m_nodes[l], m_nodes[r]) < 0) ? l : r;
          if (compare(last, m_nodes[child]) > 0) {
            m_nodes[k] = m_nodes[child];
            k = child;
          } else {
            break;
          }
        }
      }
      m_nodes[k] = last;
      m_nodes[m_count] = null;
      return ret;
    }
  }
  /**
   * @return without removing it, the least element of this heap.
   * 
   * @see #extract
   */
  public Object peek() {
    if (m_count < 1) {
      return null;
    } else {
      return m_nodes[0];
    }
  }
  /**
   * Empties this heap
   */
  public void clear() {
    m_count = 0;
    m_nodes = new Object[10];
  }
  protected int compare(Object o1, Object o2) {
    if (m_comparator != null) {
      return m_comparator.rupare(o1, o2);
    } else {
      if (o1 == null) {
        if (o2 == null) {
          return 0;
        } else {
          return -((Comparable) o2).rupareTo(o1);
        }
      } else {
        return ((Comparable) o1).rupareTo(o2);
      }
    }
  }
  /**
   * @return the parent index of <code>index</code>.
   * @param index
   */
  protected int parent(int index) {
    return (index - 1) >> 1;
  }
  /**
   * @param index
   * @return the left child index of <code>index</code>.
   */
  protected int left(int index) {
    return index + index + 1;
  }
  /**
   * @param index
   * @return the right child index of <code>index</code>.
   */
  protected int right(int index) {
    return index + index + 2;
  }
}

Tree Node for the for a general tree of Objects

   
/*
 * 
 * This software is subject to the terms of the Common Public License
 * Agreement, available at the following URL:
 *   http://www.opensource.org/licenses/cpl.html .
 * Copyright (C) 2003-2004 TONBELLER AG.
 * All Rights Reserved.
 * You must accept the terms of that agreement to use this software.
 * 
 *
 * 
 */

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
 * Tree Node for the for a general tree of Objects
 */
public class TreeNode {
  private TreeNode parent = null;
  private List children = null;
  private Object reference;
  /**
   * cTtor
   * @param obj referenced object
   */
  public TreeNode(Object obj) {
    this.parent = null;
    this.reference = obj;
    this.children = new ArrayList();
  }
  /**
   * remove node from tree
   */
  public void remove() {
    if (parent != null) {
      parent.removeChild(this);
    }
  }
  /**
   * remove child node
   * @param child
   */
  private void removeChild(TreeNode child) {
    if (children.contains(child))
      children.remove(child);
  }
  /**
   * add child node
   * @param child node to be added
   */
  public void addChildNode(TreeNode child) {
    child.parent = this;
    if (!children.contains(child))
      children.add(child);
  }
  /**
   * deep copy (clone)
   * @return copy of TreeNode
   */
  public TreeNode deepCopy() {
    TreeNode newNode = new TreeNode(reference);
    for (Iterator iter = children.iterator(); iter.hasNext();) {
      TreeNode child = (TreeNode) iter.next();
      newNode.addChildNode(child.deepCopy());
    }
    return newNode;
  }
  /**
   * deep copy (clone) and prune 
   * @param depth - number of child levels to be copied
   * @return copy of TreeNode
   */
  public TreeNode deepCopyPrune(int depth) {
    if (depth < 0)
      throw new IllegalArgumentException("Depth is negative");
    TreeNode newNode = new TreeNode(reference);
    if (depth == 0)
      return newNode;
    for (Iterator iter = children.iterator(); iter.hasNext();) {
      TreeNode child = (TreeNode) iter.next();
      newNode.addChildNode(child.deepCopyPrune(depth - 1));
    }
    return newNode;
  }
  /**
   * @return level = distance from root
   */
  public int getLevel() {
    int level = 0;
    TreeNode p = parent;
    while (p != null) {
      ++level;
      p = p.parent;
    }
    return level;
  }
  /**
   * walk through subtree of this node
   * @param callbackHandler function called on iteration 
   */
  public int walkTree(TreeNodeCallback callbackHandler) {
    int code = 0;
    code = callbackHandler.handleTreeNode(this);
    if (code != TreeNodeCallback.CONTINUE)
      return code;
    ChildLoop: for (Iterator iter = children.iterator(); iter.hasNext();) {
      TreeNode child = (TreeNode) iter.next();
      code = child.walkTree(callbackHandler);
      if (code >= TreeNodeCallback.CONTINUE_PARENT)
        return code;
    }
    return code;
  }
  /**
   * walk through children subtrees of this node
   * @param callbackHandler function called on iteration 
   */
  public int walkChildren(TreeNodeCallback callbackHandler) {
    int code = 0;
    ChildLoop: for (Iterator iter = children.iterator(); iter.hasNext();) {
      TreeNode child = (TreeNode) iter.next();
      code = callbackHandler.handleTreeNode(child);
      if (code >= TreeNodeCallback.CONTINUE_PARENT)
        return code;
      if (code == TreeNodeCallback.CONTINUE) {
        code = child.walkChildren(callbackHandler);
        if (code > TreeNodeCallback.CONTINUE_PARENT)
          return code;
      }
    }
    return code;
  }
  /**
   * @return List of children
   */
  public List getChildren() {
    return children;
  }
  /**
   * @return parent node
   */
  public TreeNode getParent() {
    return parent;
  }
  /**
   * @return reference object
   */
  public Object getReference() {
    return reference;
  }
  /**
   * set reference object
   * @param object reference
   */
  public void setReference(Object object) {
    reference = object;
  }
} // TreeNode
/*
 * 
 * This software is subject to the terms of the Common Public License
 * Agreement, available at the following URL:
 *   http://www.opensource.org/licenses/cpl.html .
 * Copyright (C) 2003-2004 TONBELLER AG.
 * All Rights Reserved.
 * You must accept the terms of that agreement to use this software.
 * 
 *
 * 
 */
/**
 * handle call back for position tree
 */
interface TreeNodeCallback {
  public static final int CONTINUE = 0;
  public static final int CONTINUE_SIBLING = 1;
  public static final int CONTINUE_PARENT = 2;
  public static final int BREAK = 3;
  /**
   * @param node the current node to handle
   * @return 0 continue tree walk
   *         1 break this node (continue sibling)
   *         2 break this level (continue parent level)
   *         3 break tree walk 
   */
  int handleTreeNode(TreeNode node);
} // TreeNodeCallback

Your own tree with generic user object

    
/*
 * Copyright 2007 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
/**
 * @author ycoppel@google.ru (Yohann Coppel)
 * 
 * @param <T>
 *          Object"s type in the tree.
 */
public class Tree<T> {
  private T head;
  private ArrayList<Tree<T>> leafs = new ArrayList<Tree<T>>();
  private Tree<T> parent = null;
  private HashMap<T, Tree<T>> locate = new HashMap<T, Tree<T>>();
  public Tree(T head) {
    this.head = head;
    locate.put(head, this);
  }
  public void addLeaf(T root, T leaf) {
    if (locate.containsKey(root)) {
      locate.get(root).addLeaf(leaf);
    } else {
      addLeaf(root).addLeaf(leaf);
    }
  }
  public Tree<T> addLeaf(T leaf) {
    Tree<T> t = new Tree<T>(leaf);
    leafs.add(t);
    t.parent = this;
    t.locate = this.locate;
    locate.put(leaf, t);
    return t;
  }
  public Tree<T> setAsParent(T parentRoot) {
    Tree<T> t = new Tree<T>(parentRoot);
    t.leafs.add(this);
    this.parent = t;
    t.locate = this.locate;
    t.locate.put(head, this);
    t.locate.put(parentRoot, t);
    return t;
  }
  public T getHead() {
    return head;
  }
  public Tree<T> getTree(T element) {
    return locate.get(element);
  }
  public Tree<T> getParent() {
    return parent;
  }
  public Collection<T> getSuccessors(T root) {
    Collection<T> successors = new ArrayList<T>();
    Tree<T> tree = getTree(root);
    if (null != tree) {
      for (Tree<T> leaf : tree.leafs) {
        successors.add(leaf.head);
      }
    }
    return successors;
  }
  public Collection<Tree<T>> getSubTrees() {
    return leafs;
  }
  public static <T> Collection<T> getSuccessors(T of, Collection<Tree<T>> in) {
    for (Tree<T> tree : in) {
      if (tree.locate.containsKey(of)) {
        return tree.getSuccessors(of);
      }
    }
    return new ArrayList<T>();
  }
  @Override
  public String toString() {
    return printTree(0);
  }
  private static final int indent = 2;
  private String printTree(int increment) {
    String s = "";
    String inc = "";
    for (int i = 0; i < increment; ++i) {
      inc = inc + " ";
    }
    s = inc + head;
    for (Tree<T> child : leafs) {
      s += "\n" + child.printTree(increment + indent);
    }
    return s;
  }
}