//級(jí)聯(lián)數(shù)據(jù)的樹(shù)狀存儲(chǔ)結(jié)構(gòu)HashMap實(shí)現(xiàn)
/**
*
*/
package test;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
/**
* @author Daniel Cao
* @date 2007-4-26
* @time 上午12:20:44
*
*/
public class TestSortGroup {
/**
* @param args
*/
public static void main(String[] args) {
TestSortGroup test = new TestSortGroup();
Map<Long, GroupNode> map = test.getGroupList1();
System.out.println("ok");
}
private List<Group> makeList() {
List<Group> totalList = new ArrayList<Group>();
Group g1 = new Group();
g1.setId(1L);
g1.setName("a1");
g1.setParentId(0L);
totalList.add(g1);
Group g2 = new Group();
g2.setId(2L);
g2.setName("a2");
g2.setParentId(1L);
totalList.add(g2);
Group g3 = new Group();
g3.setId(3L);
g3.setName("a3");
g3.setParentId(0L);
totalList.add(g3);
Group g4 = new Group();
g4.setId(4L);
g4.setName("a4");
g4.setParentId(1L);
totalList.add(g4);
Group g5 = new Group();
g5.setId(5L);
g5.setName("a5");
g5.setParentId(2L);
totalList.add(g5);
Group g6 = new Group();
g6.setId(6L);
g6.setName("a6");
g6.setParentId(2L);
totalList.add(g6);
Group g7 = new Group();
g7.setId(7L);
g7.setName("a7");
g7.setParentId(3L);
totalList.add(g7);
return totalList;
}
public Map<Long, GroupNode> getGroupList() {//針對(duì)3層
List<Group> totalList = makeList();
// 第1層
Map<Long, GroupNode> lvl1Map = new HashMap<Long, GroupNode>();
for (Group group : totalList) {
Long id = group.getId();
Long pId = group.getParentId();
if (pId == 0) {
GroupNode gn = new GroupNode();
gn.setId(id);
gn.setMember(group);
lvl1Map.put(id, gn);
}
}
// 第2層
Map<Long, GroupNode> lvl2Map = new HashMap<Long, GroupNode>();
for (Group group : totalList) {
Long id = group.getId();
Long pId = group.getParentId();
if (lvl1Map.containsKey(pId)) {
GroupNode gn = new GroupNode();
gn.setId(id);
gn.setMember(group);
lvl2Map.put(id, gn);
}
}
// 第3層
Map<Long, GroupNode> lvl3Map = new HashMap<Long, GroupNode>();
for (Group group : totalList) {
Long id = group.getId();
Long pId = group.getParentId();
if (lvl2Map.containsKey(pId)) {
GroupNode gn = new GroupNode();
gn.setId(id);
gn.setMember(group);
lvl3Map.put(id, gn);
}
}
// 先把2、3層拼起來(lái)
for (Entry<Long, GroupNode> entry : lvl3Map.entrySet()) {
Long id = entry.getKey();
GroupNode node = entry.getValue();
Long pId = node.getMember().getParentId();
if (lvl2Map.containsKey(pId)) {
GroupNode parent = lvl2Map.get(pId);
Map<Long, GroupNode> son = parent.getSon();
if (son == null) {
son = new HashMap<Long, GroupNode>();
}
son.put(id, node);
parent.setSon(son);
lvl2Map.put(pId, parent);
}
}
// 再把1、2層拼起來(lái)
for (Entry<Long, GroupNode> entry : lvl2Map.entrySet()) {
Long id = entry.getKey();
GroupNode node = entry.getValue();
Long pId = node.getMember().getParentId();
if (lvl1Map.containsKey(pId)) {
GroupNode parent = lvl1Map.get(pId);
Map<Long, GroupNode> son = parent.getSon();
if (son == null) {
son = new HashMap<Long, GroupNode>();
}
son.put(id, node);
parent.setSon(son);
lvl1Map.put(pId, parent);
}
}
return lvl1Map;
}
public Map<Long, GroupNode> getGroupList1() {//無(wú)限層的實(shí)現(xiàn)
List<Group> totalList = makeList();
//保存所有層數(shù)據(jù)
List<Map<Long, GroupNode>> lvlList = new ArrayList<Map<Long, GroupNode>>();
//前一層
Map<Long, GroupNode> lastLlvlMap = null;
while (totalList!= null && !totalList.isEmpty()) {
//當(dāng)前層數(shù)據(jù)
Map<Long, GroupNode> lvlMap = new HashMap<Long, GroupNode>();
List<Group> tmpList = new ArrayList<Group>();
for (Group group : totalList) {
Long id = group.getId();
Long pId = group.getParentId();
if (pId == 0) {
GroupNode gn = new GroupNode();
gn.setId(id);
gn.setMember(group);
lvlMap.put(id, gn);
tmpList.add(group);
} else if (lastLlvlMap != null && lastLlvlMap.containsKey(pId)) {
GroupNode gn = new GroupNode();
gn.setId(id);
gn.setMember(group);
lvlMap.put(id, gn);
tmpList.add(group);
}
}
totalList.removeAll(tmpList);
lvlList.add(lvlMap);
lastLlvlMap = lvlMap;
}
int size = lvlList.size();
if (size == 0){
return new HashMap<Long, GroupNode>();
}
if (size == 1){
return lvlList.get(0);
}
//從最后一層向前歸并
Map<Long, GroupNode> lastLvlMap = lvlList.get(size - 1);
for (int i = size-2; i >= 0; i --){
Map<Long, GroupNode> currentLvlMap = lvlList.get(i);
for (Entry<Long, GroupNode> entry : lastLvlMap.entrySet()) {
Long id = entry.getKey();
GroupNode node = entry.getValue();
Long pId = node.getMember().getParentId();
if (currentLvlMap.containsKey(pId)) {
GroupNode parent = currentLvlMap.get(pId);
Map<Long, GroupNode> son = parent.getSon();
if (son == null) {
son = new HashMap<Long, GroupNode>();
}
son.put(id, node);
parent.setSon(son);
currentLvlMap.put(pId, parent);
}
}
lastLvlMap = currentLvlMap;
}
System.out.println(lastLvlMap.size());
return lastLvlMap;
}
}