97
|
1 package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser;
|
|
2
|
98
|
3 import java.util.Iterator;
|
184
|
4 import java.util.Optional;
|
174
|
5
|
|
6 import fj.Ord;
|
183
|
7 import fj.data.List;
|
184
|
8 import jp.ac.u_ryukyu.ie.cr.tatsuki.TreeMap.TreeMap;
|
174
|
9 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NulIterator;
|
97
|
10 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
|
99
|
11 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.PathNodeIterator;
|
110
|
12 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.Query;
|
169
|
13 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.IndexCreater;
|
153
|
14 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.ParentIndex;
|
97
|
15
|
100
|
16 public class InterfaceTraverser {
|
124
|
17
|
183
|
18 TreeNode root;
|
|
19 TreeMap<String, TreeMap<String, List<TreeNode>>> indexList;
|
|
20 ParentIndex parentIndex;
|
|
21 boolean parentUpdateFlag;
|
|
22 boolean useIndex;
|
154
|
23
|
183
|
24 public InterfaceTraverser(TreeNode root, boolean indexFlag) {
|
184
|
25 this(root, new TreeMap<>(), new ParentIndex(), indexFlag);
|
183
|
26 }
|
139
|
27
|
183
|
28 public InterfaceTraverser(TreeNode root, TreeMap<String, TreeMap<String, List<TreeNode>>> index,
|
|
29 ParentIndex parentIndex, boolean useIndex) {
|
|
30 this.root = root;
|
|
31 this.indexList = index;
|
|
32 this.parentIndex = parentIndex;
|
|
33 if (parentIndex.isEmpty())
|
|
34 parentUpdateFlag = true;
|
|
35 else
|
|
36 parentUpdateFlag = false;
|
|
37 this.useIndex = useIndex;
|
|
38 }
|
127
|
39
|
183
|
40 public TreeMap<String, TreeMap<String, List<TreeNode>>> getIndex() {
|
|
41 return indexList;
|
|
42 }
|
153
|
43
|
183
|
44 public void commit() {
|
|
45 parentUpdateFlag = false;
|
|
46 }
|
|
47
|
|
48 public ParentIndex getParentIndex() {
|
|
49 return parentIndex;
|
|
50 }
|
127
|
51
|
183
|
52 public void createIndex() {
|
|
53 // long t1 = System.currentTimeMillis();
|
|
54 IndexCreater creater = new IndexCreater(root);
|
|
55 // long t2 = System.currentTimeMillis();
|
|
56 // System.out.println("createIndex time = " + (t2 - t1));
|
|
57 indexList = creater.getIndex();
|
|
58 parentIndex = creater.getParentIndex();
|
|
59 }
|
153
|
60
|
183
|
61 /**
|
|
62 * subTree以下のNodeに対してKey,Valueのペアでindexを使って探索を行う
|
|
63 *
|
|
64 * @param query
|
|
65 * @param subTree
|
|
66 * @param key
|
|
67 * @param searchValue
|
|
68 * @return
|
|
69 */
|
|
70 // public Iterator<TreeNode> findInSubTree(final Query query, TreeNode
|
|
71 // subTree, String key, String searchValue) {
|
|
72 // /*
|
|
73 // * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から1つずつ比較し、
|
|
74 // * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す
|
|
75 // */
|
|
76 // Iterator<TreeNode> nodeIterator = index.get(key, searchValue);
|
|
77 // if (nodeIterator.hasNext() && useIndex) {
|
|
78 //
|
|
79 // // ここでNode以下にあるか調べる
|
|
80 // List<TreeNode> filteredList = List.nil();
|
|
81 //
|
|
82 // for (;nodeIterator.hasNext();) {
|
|
83 // TreeNode targetNode = nodeIterator.next();
|
|
84 // TreeNode parent = targetNode;
|
|
85 // while (parent != null) {
|
|
86 // parent = parentIndex.get(parent);
|
|
87 // if (parent.equals(subTree))
|
|
88 // filteredList = filteredList.cons(targetNode);
|
|
89 // }
|
|
90 // }
|
|
91 //
|
|
92 // return filteredList.iterator();
|
|
93 //
|
|
94 // } else {
|
|
95 // final PathNodeIterator itNode = new PathNodeIterator(subTree);
|
|
96 // return new Iterator<TreeNode>() {
|
|
97 //
|
|
98 // private TreeNode matchNode = nextmatch(itNode);
|
|
99 //
|
|
100 // private TreeNode nextmatch(PathNodeIterator itNode) {
|
|
101 //
|
|
102 // for (; itNode.hasNext();) {
|
|
103 // TreeNode targetNode = itNode.next();
|
|
104 // if (query.condition(targetNode))
|
|
105 // return targetNode;
|
|
106 // }
|
|
107 // return null;
|
|
108 // }
|
|
109 //
|
|
110 // @Override
|
|
111 // public boolean hasNext() {
|
|
112 // if (matchNode == null) {
|
|
113 // return false;
|
|
114 // }
|
|
115 // return true;
|
|
116 // }
|
|
117 //
|
|
118 // @Override
|
|
119 // public TreeNode next() {
|
|
120 // TreeNode currentNode = matchNode;
|
|
121 // matchNode = nextmatch(itNode);
|
|
122 // return currentNode;
|
|
123 // }
|
|
124 //
|
|
125 // @Override
|
|
126 // public void remove() {
|
|
127 // }
|
|
128 //
|
|
129 // };
|
|
130 // }
|
|
131 // }
|
137
|
132
|
183
|
133 /**
|
|
134 * subTree以下のNodeに対してKeyに対応する値をindexを使って探索する
|
|
135 */
|
|
136 // public Iterator<TreeNode> findInSubTreeAllValue(final Query query, TreeNode
|
|
137 // subTree, String key) {
|
|
138 // /*
|
|
139 // * indexからinnerIndexを取得 取得したinnerIndexが保有するKeyを取得
|
|
140 // * そのKeyを保有するNodeとNodeのPathを取得する
|
|
141 // * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から1つずつ比較し、
|
|
142 // * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す
|
|
143 // */
|
|
144 // Iterator<TreeNode> NodeIterator = index.getAll(key);
|
|
145 // if (NodeIterator != null && useIndex) {
|
|
146 // List<TreeNode> filteredList = List.nil();
|
|
147 // for (; NodeIterator.hasNext();) {
|
|
148 // TreeNode targetNode = NodeIterator.next();
|
|
149 // TreeNode parent = targetNode;
|
|
150 // while (parent != null) {
|
|
151 // parent = parentIndex.get(parent);
|
|
152 // if (parent.equals(subTree))
|
|
153 // filteredList = filteredList.cons(targetNode);
|
|
154 // }
|
|
155 // }
|
|
156 // return filteredList.iterator();
|
|
157 //
|
|
158 // } else {
|
|
159 //
|
|
160 // final PathNodeIterator itNode = new PathNodeIterator(subTree);
|
|
161 // return new Iterator<TreeNode>() {
|
|
162 //
|
|
163 // private TreeNode matchPair = nextmatch(itNode);
|
|
164 //
|
|
165 // private TreeNode nextmatch(PathNodeIterator itNode) {
|
|
166 //
|
|
167 // for (; itNode.hasNext();) {
|
|
168 // TreeNode targetNode = itNode.next();
|
|
169 // if (query.condition(targetNode))
|
|
170 // return targetNode;
|
|
171 // }
|
|
172 // return null;
|
|
173 // }
|
|
174 //
|
|
175 // @Override
|
|
176 // public boolean hasNext() {
|
|
177 // if (matchPair == null) {
|
|
178 // return false;
|
|
179 // }
|
|
180 // return true;
|
|
181 // }
|
|
182 //
|
|
183 // @Override
|
|
184 // public TreeNode next() {
|
|
185 // TreeNode currentNode = matchPair;
|
|
186 // matchPair = nextmatch(itNode);
|
|
187 // return currentNode;
|
|
188 // }
|
|
189 //
|
|
190 // @Override
|
|
191 // public void remove() {
|
|
192 // }
|
|
193 //
|
|
194 // };
|
|
195 // }
|
|
196 // }
|
|
197 public Iterator<TreeNode> find(final Query query, final String key, String searchValue) {
|
137
|
198
|
183
|
199 Iterator<TreeNode> nodeIterator = get(key, searchValue);
|
|
200 if (nodeIterator != null && useIndex) {
|
|
201 return nodeIterator;
|
|
202 } else {
|
153
|
203
|
183
|
204 final PathNodeIterator itNode = new PathNodeIterator(root);
|
|
205 return new Iterator<TreeNode>() {
|
|
206
|
|
207 private TreeNode matchNode = nextmatch(itNode);
|
|
208
|
|
209 private TreeNode nextmatch(PathNodeIterator itNode) {
|
153
|
210
|
183
|
211 for (; itNode.hasNext(); ) {
|
|
212 TreeNode targetNode = itNode.next();
|
|
213 String value = targetNode.getAttributes().getString(key);
|
|
214 if (useIndex) {
|
|
215 if (value != null)
|
|
216 ;
|
|
217 // index = index.set(key, value, targetNode);
|
|
218 }
|
|
219 if (parentUpdateFlag)
|
|
220 ;
|
|
221 // parentIndex = parentIndex.set(targetNode);
|
|
222 if (query.condition(targetNode))
|
|
223 return targetNode;
|
|
224 }
|
|
225 if (useIndex || parentUpdateFlag)
|
|
226 commit();
|
|
227 return null;
|
|
228 }
|
153
|
229
|
183
|
230 @Override
|
|
231 public boolean hasNext() {
|
|
232 if (matchNode == null) {
|
|
233 return false;
|
|
234 }
|
|
235 return true;
|
|
236 }
|
139
|
237
|
183
|
238 @Override
|
|
239 public TreeNode next() {
|
|
240 TreeNode currentPair = matchNode;
|
|
241 matchNode = nextmatch(itNode);
|
|
242 return currentPair;
|
|
243 }
|
139
|
244
|
183
|
245 @Override
|
|
246 public void remove() {
|
|
247 }
|
|
248
|
|
249 };
|
|
250 }
|
139
|
251 }
|
|
252
|
183
|
253 // public Iterator<TreeNode> findAll(final Query query, final String key) {
|
|
254 //
|
|
255 // Iterator<TreeNode> nodeList = index.getAll(key);
|
|
256 // if (nodeList != null && useIndex) {
|
|
257 //
|
|
258 // return nodeList;
|
|
259 //
|
|
260 // } else {
|
|
261 //
|
|
262 // final PathNodeIterator itNode = new PathNodeIterator(node);
|
|
263 // return new Iterator<TreeNode>() {
|
|
264 //
|
|
265 // private TreeNode matchNode = nextmatch(itNode);
|
|
266 //
|
|
267 // private TreeNode nextmatch(PathNodeIterator itNode) {
|
|
268 //
|
|
269 // for (; itNode.hasNext();) {
|
|
270 // TreeNode targetNode = itNode.next();
|
|
271 // String value = targetNode.getAttributes().getString(key);
|
|
272 // if (useIndex) {
|
|
273 // if (value != null)
|
|
274 // index = index.set(key, value, targetNode);
|
|
275 // }
|
|
276 // if (parentUpdateFlag);
|
|
277 // // parentIndex = parentIndex.set(targetNode);
|
|
278 // if (query.condition(targetNode))
|
|
279 // return targetNode;
|
|
280 // }
|
|
281 // if (useIndex || parentUpdateFlag)
|
|
282 // commit();
|
|
283 // return null;
|
|
284 // }
|
|
285 //
|
|
286 // @Override
|
|
287 // public boolean hasNext() {
|
|
288 // if (matchNode == null) {
|
|
289 // return false;
|
|
290 // }
|
|
291 // return true;
|
|
292 // }
|
|
293 //
|
|
294 // @Override
|
|
295 // public TreeNode next() {
|
|
296 // TreeNode currentPair = matchNode;
|
|
297 // matchNode = nextmatch(itNode);
|
|
298 // return currentPair;
|
|
299 // }
|
|
300 //
|
|
301 // @Override
|
|
302 // public void remove() {
|
|
303 // }
|
|
304 //
|
|
305 // };
|
|
306 // }
|
|
307 // }
|
139
|
308
|
183
|
309 public Iterator<TreeNode> get(String key, String value) {
|
184
|
310 Optional<TreeMap<String, List<TreeNode>>> indexOp = indexList.getLoop(key);
|
|
311 if (!indexOp.isPresent())
|
183
|
312 return null;
|
136
|
313
|
184
|
314 Optional<List<TreeNode>> nodeListOp = indexOp.get().getLoop(value);
|
|
315 if (!nodeListOp.isPresent())
|
183
|
316 return new NulIterator<TreeNode>();
|
184
|
317
|
|
318 return nodeListOp.get().iterator();
|
183
|
319 }
|
97
|
320 }
|