tree.java

一个目录树

package com.kewf.dirtree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;

/**
 * 目录树. <br/>
 * 提供由其它对象生成目录树的支持。<br/>
 * 如磁盘目录:Tree t=Tree.getTree(new java.io.File("D:/"),new FileContainer());<br/>
 * XML文件：Document doc=...<br/>
 * Tree t=Tree.getTree(doc,new DocumentContainer());<br/>
 * 如果有File或Document以外的对象要生成目录树，请实现{@link TreeNode}或{@link Container}接口。
 * 对于SQL中的表，建议字段要求id（标识）、parentId（上级目录标识），其它字段自定，然后对查询到的每一
 * 条记录生成一个实现TreeNode接口的对象。
 * 如果实现了TreeNode接口：<br/>
 *   class Group implements TreeNode{}<br/>
 *   Group[] groups=...<br/>
 *   Tree t=Tree.getTree(groups,0);//其中0为根结点的ID<br/>，并且groups不要求是同一对象，只要它们都实现了
 * 接口TreeNode，并且ID不同，这样可以在生成目录树的过程中根据对象类型自行处理。
 * <p>Copyright: Copyright (c) 2004</p>
 * <p> </p>
 * @author flyxxxxx
 * @version 1.0
 */
final public class Tree
    extends Node {
  /**
   * 结点最大标识
   */
  private static int maxId = 0;

  private Tree() {
    super(getMaxId(), null);
  }

  private Tree(int id) {
    super(id, null);
    maxId = id++;
  }

  private static int getMaxId() {
    return maxId++;
  }

  /**
   * 创建空目录树.
   * @return Tree 空目录树
   */
  public static Tree getTree() {
    return new Tree();
  }

  /**
   * 向目录树添加一个结点.
   * 目录树中所有结点的类型最好是相同的。
   * @param parent Node 父结点
   * @param value Object 结点的值
   * @return Node 添加的结点
   */
  public Node addNode(Node parent, Object value) {
    Node rs = new Node(getMaxId(), parent);
    rs.setValue(value);
    return rs;
  }

  /**
   * 创建目录树.
   * 如果对象实现了接口{@link Container}，可以通过此方法加入目录树。<br/>
   * 通过此方法创建的目录树，所有结点的ID由系统生成。obj将直接做为根结点，对根结点调用方法
   * {@link Node#getValue()}将得到obj。<br/>
   * @param obj Object 目录树的根结点
   * @param container Container 得到对象的子对象的接口
   * @return Tree 目录树
   */
  public static Tree getTree(Object obj, Container container) {
    Tree rs = new Tree();
    rs.setValue(obj);
    Object[] o = container.getChilds(obj);
    for (int i = 0; i < o.length; i++) {
      addNode(rs, o[i], container);
    }
    return rs;
  }

  private static void addNode(Node n, Object obj, Container container) {
    Node node = new Node(getMaxId(), n);
    node.setValue(obj);
    Object[] o = container.getChilds(obj);
    for (int i = 0; i < o.length; i++) {
      addNode(node, o[i], container);
    }
  }

  /**
   * 创建目录树.
   * 如果对象实现了接口{@link Container}，可以通过此方法加入目录树。<br/>
   * 通过此方法创建的目录树，所有结点的ID由系统生成，对根结点调用方法{@link Node#getValue()}
   * 将得到null。<br/>
   * obj数组中的每一个，将直接做为根结点的直接子结点。
   * @param obj Object 目录树的根结点的直接子结点.
   * @param container Container 得到对象的子对象的接口
   * @return Tree 目录树
   */
  public static Tree getTree(Object obj[], Container container) {
    Tree rs = new Tree();
    for (int i = 0; i < obj.length; i++) {
      addNode(rs, obj[i], container);
    }
    return rs;
  }

  /**
   * 创建目录树.
   * 只要一组对象实现接口{@link TreeNode}，并且每个对象的ID不同，就可以将它们加入目录树。<br/>
   * 通过此方法得到的目录树，它的根结点ID值为rootId，其它结点的值为实现接口TreeNode的对象的ID。<br/>
   * 如果treeNode中包含了根结点，根结点的值可以通过方法{@link Node#getValue()}得到，返之得到的是null。<br/>
   * treeNode可以没有顺序，但父结点的ID一定大于子结点的。
   * @param treeNode TreeNode[] 构成目录树的结点
   * @param rootId int 根结点的ID
   * @return Tree 创建目录树
   */
  public static Tree getTree(TreeNode[] treeNode, int rootId) {
    Tree rs = new Tree(rootId);
    ArrayList list = new ArrayList();
    for (int i = 0; i < treeNode.length; i++) {
      list.add(treeNode[i]);
    }
    Collections.sort(list, new Compare()); //排序
    Node last = rs;
    for (int i = 0; i < treeNode.length; i++) {
      TreeNode tnode = (TreeNode) list.get(i);
      if (i == 0 && tnode.getId() == rootId) { //是否根结点
        rs.setValue(tnode);
      }
      else {
        Node parent = null; //寻找父结点
        if ( ( (TreeNode) last.getValue()).getId() == tnode.getParentId()) {
          parent = last;
        }
        else {
          parent = rs.getNode(tnode.getParentId());
        }
        if (parent == null) { //未找到
          throw new NullPointerException("Node " + tnode.getParentId() +
                                         " not found.");
        }
        else { //找到
          Node n = new Node(tnode.getId(), parent);
          n.setValue(tnode);
          last = parent;
        }
      }
    }
    return rs;
  }

  /**
   * 从目录树中查找标识为id的结点.
   * @param id String 结点标识
   * @return Node 标识为id的结点(未找到返回null)
   */
  public Node getNode(int id) {
    if (id == getId()) {
      return this;
    }
    return getNode(getChilds(), id);
  }

  private static Node getNode(Iterator it, int id) { //查找结点
    while (it.hasNext()) {
      Node n = (Node) it.next();
      if (n.getId() == id) {
        return n;
      }
      if (n.getChildsNumber() > 0) {
        n = getNode(n.getChilds(), id);
        if (n != null) {
          return n;
        }
      }
    }
    return null;
  }

  /**
   * 对目录树进行排序
   * @param com Comparator 排序接口
   */
  public void sort(Comparator com) {
    sort(childs, com);
  }

  private void sort(ArrayList childs, Comparator com) { //对子结点排序
    Collections.sort(childs, com);
    for (int i = 0; i < childs.size(); i++) {
      Node n = (Node) childs.get(i);
      if (n.getChildsNumber() > 1) {
        sort(n.childs, com);
      }
    }
  }

  /**
   * 得到满足条件的结点列表.
   * @param filter NodeFilter 结点过滤器
   * @return Iterator 结点列表(存储Node对象)
   */
  public Iterator getNodeList(NodeFilter filter) {
    ArrayList rs = new ArrayList();
    getNodeList(childs, filter, rs);
    return rs.iterator();
  }

  private void getNodeList(ArrayList childs, NodeFilter filter,
                           ArrayList rs) { //检索满足条件的结点
    for (int i = 0; i < childs.size(); i++) {
      Node n = (Node) childs.get(i);
      if (filter.accept(n)) {
        rs.add(n);
      }
      if (n.hasChilds()) {
        getNodeList(n.childs, filter, rs);
      }
    }
  }

}

class Compare
    implements Comparator { //对结点按ID排序
  public Compare() {}

  public int compare(Object obj1, Object obj2) {
    int id1 = ( (TreeNode) obj1).getId();
    int id2 = ( (TreeNode) obj2).getId();
    return id1 - id2;
  }
}