package com.humpic.helper.tree;

import java.util.*;

import org.apache.commons.lang.StringUtils;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

public?abstract?class Tree {
??? protected?static Log log = LogFactory.getLog(Tree.class);

??? private Map treeNodeMaps =?new Hashtable();
??? private TreeNode root;

??? /**
???? * root if it's parent is empty
???? */
??? protected?void reload(List nodes) {
??????? log.info("tree will start reload all data");
???????
??????? synchronized (this) {
??????????? // initialize
??????????? treeNodeMaps.clear();
??????????? root =?null;

??????????? List treeNodes =?new Vector(nodes.size());
??????????? for (int i =?0; i < nodes.size(); i++) {
??????????????? TreeNode node =?this.transform(nodes.get(i)); // transform
??????????????? treeNodes.add(node);
??????????????? node.setTree(this);
??????????????? treeNodeMaps.put(node.getNodeId(), node);
??????????? }
???????????
??????????? for (int i =?0; i < treeNodes.size(); i++) {
??????????????? TreeNode node = (TreeNode) treeNodes.get(i);
??????????????? String parentId = node.getParentId();
??????????????? if (this.isRootNode(node)) {
??????????????????? if (root ==?null) {
??????????????????????? root = node;
??????????????????? } else {
??????????????????????? log.error("find more then one root node. ignore.");
??????????????????? }
??????????????? } else {
??????????????????? TreeNode parent = (TreeNode) treeNodeMaps.get(parentId);
??????????????????? if (parent !=?null) {
??????????????????????? parent.addChild(node);
??????????????????????? node.setParent(parent);
??????????????????? } else {
??????????????????????? log.warn("node [id="?+ node.getNodeId() +?"]: missing parent node.");
??????????????????? }
??????????????? }
??????????? }
??????? }

??????? if (root ==?null) {
??????????? log.error("the root node is not be defined");
??????? }
??? }

??? protected boolean isRootNode(TreeNode node) {
??????? return?StringUtils.isBlank(node.getParentId());
??? }

??? public TreeNode getRootNode() {
??????? return root;
??? }

??? public TreeNode getTreeNode(String nodeId) {
??????? return (TreeNode) treeNodeMaps.get(nodeId);
??? }

??? public?void addTreeNode(TreeNode node) {
??????? synchronized (this) {
??????????? treeNodeMaps.put(node.getNodeId(), node);

??????????? String parentId = node.getParentId();
??????????? if (StringUtils.isNotBlank(parentId)) {
??????????????? TreeNode parent = getTreeNode(parentId);
??????????????? if (parent !=?null) {
??????????????????? parent.addChild(node);
??????????????????? node.setParent(parent);
??????????????? } else {
??????????????????? log.error("parent cannot be found: "?+ node.getParentId());
??????????????? }
??????????? } else {
??????????????? if (root ==?null) {
??????????????????? root = node;
??????????????? } else {
??????????????????? log.error("find more then one root node. ignore.");
??????????????? }
??????????? }
??????? }
??? }

??? public?void deleteTreeNode(String nodeId) {
??????? synchronized (this) {
??????????? TreeNode node = getTreeNode(nodeId);
??????????? if (node ==?null)
??????????????? throw?new IllegalArgumentException(nodeId +?" cannot be found.");

??????????? if (node.getParent() ==?null) {
??????????????? root =?null;
??????????????? treeNodeMaps.clear();
??????????????? log.warn("the root node has been removed.");
??????????? } else {
??????????????? node.getParent().getChildren().remove(node);

??????????????? treeNodeMaps.remove(nodeId);
??????????????? List children = node.getAllChildren();
??????????????? for (int i =?0; i < children.size(); i++) {
??????????????????? TreeNode n = (TreeNode) children.get(i);
??????????????????? treeNodeMaps.remove(n.getNodeId());
??????????????? }
??????????? }
??????? }
??? }

??? /**
???? * <pre>
???? * Usage: Office -&gt;
???? *
???? * public TreeNode transform(Object info) {
???? *???? OfficeInfo office_info = (OfficeInfo) info;
???? *???? TreeNode node = new TreeNode();
???? *???? node.setNodeId(office_info.getOfficeId());
???? *???? node.setParentId(office_info.getParentId());
???? *???? node.setBindData(office_info);
???? *???? return node;
???? * }
???? * </pre>
???? */
??? protected?abstract TreeNode transform(Object info);
}

package?com.humpic.helper.tree;

import java.util.List;
import java.util.Vector;

import org.apache.commons.collections.Predicate;
import org.apache.commons.lang.ObjectUtils;

public?class TreeNode {

??? private Tree tree;
??? private TreeNode parent;
??? private List children =?new Vector();
??? private List childrenGroup =?new Vector();
??? private String nodeId;
??? private String parentId;
??? private Object bindData;

??? public String getNodeId() {
??????? return nodeId;
??? }

??? public?void setNodeId(String nodeId) {
??????? this.nodeId = nodeId;
??? }

??? public String getParentId() {
??????? return parentId;
??? }

??? public?void setParentId(String parentId) {
??????? this.parentId = parentId;
??? }

??? public Object getBindData() {
??????? return bindData;
??? }

??? public?void setBindData(Object bindData) {
??????? this.bindData = bindData;
??? }

??? public Tree getTree() {
??????? return tree;
??? }

??? public?void setTree(Tree tree) {
??????? this.tree = tree;
??? }

??? public?void setParent(TreeNode parent) {
??????? this.parent = parent;
??? }

??? public TreeNode getParent() {
??????? return?this.parent;
??? }

??? public List getChildren() {
??????? return?this.children;
??? }

??? public?void addChild(TreeNode node) {
??????? children.add(node);
??? }

??? /**
???? * get all children, and chilren's children
???? */
??? public List getAllChildren() {
??????? if (this.childrenGroup.isEmpty()) {
??????????? synchronized (this.tree) {
??????????????? for (int i =?0; i <?this.children.size(); i++) {
??????????????????? TreeNode node = (TreeNode) this.children.get(i);
??????????????????? this.childrenGroup.add(node);
??????????????????? this.childrenGroup.addAll(node.getAllChildren());
??????????????? }
??????????? }
??????? }
??????? return?this.childrenGroup;
??? }

??? /**
???? * get all children, and chilren's children
???? */
?? ?public?List getAllChildren(Predicate predicate) {
??????? List groups =?new Vector();
??????? fillAllChildren(groups, predicate);
??????? return groups;
??? }

??? private?void fillAllChildren(List groups, Predicate predicate) {
??????? for (int i =?0; i <?this.children.size(); i++) {
??????????? TreeNode node = (TreeNode) this.children.get(i);
??????????? if (predicate.evaluate(node)) {
??????????????? groups.add(node);
??????????????? node.fillAllChildren(groups, predicate);
??????????? }
??????? }
??? }

??? /**
???? * get all parents, and parent's parent
??? */
??? public List getParents() {
?? ??? ?List results = new Vector();
??? ??? TreeNode parent = this.getParent();
??? ??? while (parent != null) {
??? ??? ??? results.add(parent);
??? ??? ??? parent = parent.getParent();
??? ??? }
??? ??? return results;
??? }

??? /**
???? * A.isMyParent(B) == B is A' parent ? <br>
???? * root.isMyParent(null) == true; <br>
???? * root.isMyParent(*) == false <br>
???? * *.isMyParent(null) == false
???? */
??? public?boolean isMyParent(String nodeId) {
??????? TreeNode target = tree.getTreeNode(nodeId);
??????? TreeNode parent =?this.getParent();
??????? if (parent ==?null) {
??????????? return target ==?null;
??????? } else {
??????????? return parent.equals(target);
??????? }
??? }

??? /**
???? * A.isMyAncestor(B) == B is A' ancestor ? <br>
???? * *.isMyAncestor(null) == true;
???? */
??? public?boolean isMyAncestor(String nodeId) {
??????? TreeNode target = tree.getTreeNode(nodeId);
??????? if (target ==?null)
??????????? return?true;

??????? return target.getAllChildren().contains(this);
??? }

??? /**
???? * A.isMyBrother(B) == B is A' brother ? <br>
???? * *.isMyBrother(null) == false
???? */
??? public?boolean isMyBrother(String nodeId) {
??????? TreeNode target = tree.getTreeNode(nodeId);
??????? if (target ==?null)
??????????? return?false;

??????? TreeNode p1 =?this.getParent();
??????? TreeNode p2 = target.getParent();
??????? return ObjectUtils.equals(p1, p2);
??? }

}