127
|
1 package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query;
|
|
2
|
|
3 import java.util.Iterator;
|
|
4 import java.util.Stack;
|
|
5
|
|
6 import fj.data.List;
|
|
7 import fj.data.TreeMap;
|
|
8 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
|
|
9 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
|
|
10 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
|
|
11 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNodeChildren;
|
|
12 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair;
|
|
13
|
|
14 public class PathNodeIndexIterator implements Iterator<Pair<TreeNode, NodePath>> {
|
|
15
|
|
16 TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index;
|
|
17 NodePath path;
|
|
18 TreeNode root;
|
|
19 TreeNode node;
|
|
20 int childNumber;
|
|
21 private TreeNodeChildren children;
|
|
22 private Stack<TreeNode> nodeStack = new Stack<TreeNode>();
|
|
23 private Stack<Integer> searchStack = new Stack<Integer>();
|
|
24
|
|
25 /*
|
|
26 * get queryIndexCondition from query
|
|
27 * if already index exists, use index
|
|
28 * otherwise traverse tree and create index
|
|
29 *
|
|
30 * */
|
|
31 public PathNodeIndexIterator(TreeNode root, TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> index) {
|
|
32 this.root = root;
|
|
33 this.index = index;
|
|
34 path = new DefaultNodePath();
|
|
35 node = root;
|
|
36 }
|
|
37
|
|
38 @Override
|
|
39 public boolean hasNext() {
|
|
40 return node != null;
|
|
41 }
|
|
42
|
|
43 @Override
|
|
44 public Pair<TreeNode, NodePath> next() {
|
|
45 TreeNode now = node;
|
|
46 NodePath currentPath = path;
|
|
47 if (node.getChildren().size() > 0) { //
|
|
48 nodeStack.push(node);
|
|
49 path = path.add(0);
|
|
50 children = node.getChildren();
|
|
51 node = children.at(0).b();
|
|
52 childNumber = 1;
|
|
53 searchStack.push(childNumber);
|
|
54 } else if (node == root) {
|
|
55 node = null; // no more node
|
|
56 children = null;
|
|
57 return new Pair<TreeNode, NodePath>(now, currentPath);
|
|
58 }else if (children != null && children.size() > childNumber) {
|
|
59 childNumber = searchStack.pop();
|
|
60 node = children.at(childNumber).b();
|
|
61 path = path.tail().add(childNumber);
|
|
62 searchStack.push(++childNumber);
|
|
63 } else {
|
|
64 path = path.tail();
|
|
65 node = nodeStack.pop();
|
|
66 children = node.getChildren();
|
|
67 childNumber = searchStack.pop();
|
|
68 for (; children.size() == childNumber;) {
|
|
69 if (node == root) {
|
|
70 node = null; // no more node
|
|
71 children = null;
|
|
72 return new Pair<TreeNode, NodePath>(now, currentPath);
|
|
73 }
|
|
74 path = path.tail();
|
|
75 node = nodeStack.pop();
|
|
76 children = node.getChildren();
|
|
77 childNumber = searchStack.pop();
|
|
78 }
|
|
79 if (node != null && childNumber < children.size()) {
|
|
80 path = path.add(childNumber);
|
|
81 nodeStack.push(node);
|
|
82 node = children.at(childNumber).b();
|
|
83 searchStack.push(++childNumber);
|
|
84 }
|
|
85 }
|
|
86 System.out.println("path = " + path.toString());
|
|
87 return new Pair<TreeNode, NodePath>(now, currentPath);
|
|
88 }
|
|
89
|
|
90 @Override
|
|
91 public void remove() {
|
|
92 // TODO Auto-generated method stub
|
|
93
|
|
94 }
|
|
95
|
|
96 public TreeMap<String, TreeMap<String, List<Pair<TreeNode, NodePath>>>> getIndex() {
|
|
97 return index;
|
|
98 }
|
|
99 }
|