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