package com.test.me;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.concurrent.locks.ReentrantLock;
public class Tree<T> {
class TreeNode {
private TreeNode parent;
//直接new一个Set出来。这样对children就不需要用volatile了,final类型防止修改
private final Set<TreeNode> children = Collections.synchronizedSet(new HashSet<TreeNode>());
private T attachment;
public TreeNode(T attach) {
attachment = attach;
}
@Override
public int hashCode() {
return attachment.hashCode();
}
@Override
//比较Node中保存的对象attachment是不是相等
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
TreeNode other = (TreeNode) obj;
if (attachment == null) {
if (other.attachment != null)
return false;
} else if (!attachment.equals(other.attachment))
return false;
return true;
}
}
public Tree(T attach) {
this.root = new TreeNode(attach);
}
private TreeNode root;
public T getRoot() {
return root.attachment;
}
/**
* 在parent下增加一个子节点,
*
* @return 只有parent存在于树内,且将要插入的不在tree内,插入成功才返回true
*/
public boolean addchild(T parent, T attachment) {
TreeNode parentNode = findTreeNode(parent);
// 只有attachment不存的时才加入
if (parentNode != null) {
TreeNode node = new TreeNode(attachment);
node.parent = parentNode;
//children是同步Set, 可以保证线程安全
return parentNode.children.add(node);
}
return false;
}
/**
* 删除对应节点 只有当节点存在才返回true.
* 该方法暂时不提供外部使用。所有数据都要从新生成,然后获取
* @param 是否级联删除
* ,如果为true执行级连删除;false,如果有child则不执行删除
* */
protected boolean remove(T attachment, boolean cascade) {
TreeNode node = findTreeNode(attachment);
if (node != null) {
// 如果不是级联删除 ,并且 有子级节,则返回false
if (!cascade && node.children.size() > 0) {
return false;
}
TreeNode parent = node.parent;
return parent.children.remove(node);
} else {
return false;
}
}
/**
* 获取node下所有后代节点
*/
public List<T> getDescendants(T attachment) {
TreeNode node = findTreeNode(attachment);
if (node != null) {
List<T> list = new ArrayList<T>();
Stack<TreeNode> set = new Stack<TreeNode>();
if(node.children!=null && node.children.size()>0)
{
for (TreeNode children : node.children) {
set.push(children);
}
}
// 开始遍历当前结果下所有 子孙节点
while (!set.isEmpty()) {
TreeNode cur = set.pop();
list.add(cur.attachment);
if (cur.children != null && cur.children.size() > 0) {
for (TreeNode children : cur.children) {
set.push(children);
}
}
}
return list;
}
return null;
}
/**
* 查询所有父级节点。从root向下排序,第一个是root
* */
public List<T> getAncestors(T attach) {
TreeNode node = findTreeNode(attach);
if (node != null && node.parent!=null) {
List<T> list = new ArrayList<T>();
TreeNode cur = node.parent;
while (cur != root && cur != null) {
list.add(cur.attachment);
cur = cur.parent;
}
//如果是root
if (cur == root) {
list.add(root.attachment);
Collections.reverse(list);
return list;
} else {
return null;
}
} else {
return null;
}
}
/**
* 获取子树,不包含孙级节点
*/
public List<T> getChild(T attachment) {
TreeNode node = findTreeNode(attachment);
if (node != null && node.children!=null) {
List<T> list = new ArrayList<T>();
for(TreeNode child : node.children)
{
list.add(child.attachment);
}
return list;
}
return null;
}
/**
* 获得父级节点。
*/
public T getFather(T attachment) {
TreeNode node = findTreeNode(attachment);
if (node != null && node != this.root) {
return node.parent.attachment;
}
return null;
}
/**
* 查找对象,如果存在测返回对象,否则返回null
* */
private TreeNode findTreeNode(T attachment) {
Stack<TreeNode> set = new Stack<TreeNode>();
set.push(root);
// 下面开始遍历tree
TreeNode cur = root;
while ((!set.empty()) && attachment != cur.attachment && (!attachment.equals(cur.attachment))) {
cur = set.pop();
if (cur.children != null && cur.children.size() > 0) {
for (TreeNode children : cur.children) {
set.push(children);
}
}
}
if (attachment.equals(cur.attachment)) {
return cur;
} else {
return null;
}
}
}