package fly.tools.tree;

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 ( last.getValue()!=null&&( (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;
  }
}