Mercurial > hg > Members > tatsuki > bench > jungle-core

comparison src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java @ 153:20af7f25ef32

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
miner change
author one
date Tue, 25 Nov 2014 17:52:41 +0900
parents 8a0aa8fc137c
children b8cef4b640a3
comparison
equal deleted inserted replaced
152:8a0aa8fc137c 153:20af7f25ef32
1 package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser; 1 package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser;
2 2
3 import java.util.Iterator; 3 import java.util.Iterator;
4 4
5 import fj.Ord;
6 import fj.P2;
7 import fj.data.List; 5 import fj.data.List;
8 import fj.data.Option;
9 import fj.data.TreeMap;
10 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
11 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NulIterator; 6 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NulIterator;
12 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
13 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; 7 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
14 import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair;
15 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.PathNodeIterator; 8 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.PathNodeIterator;
16 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.Query; 9 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.Query;
17 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.Index; 10 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.Index;
18 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.IndexManager; 11 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.IndexManager;
12 import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.ParentIndex;
19 13
20 public class InterfaceTraverser { 14 public class InterfaceTraverser {
21 15
22 // InterfaceTraverser traverser;
23 TreeNode node; 16 TreeNode node;
24 Index index; 17 Index index;
18 ParentIndex parentIndex;
19 boolean parentUpdateFlag;
25 IndexManager indexManager; 20 IndexManager indexManager;
26 21 boolean indexFlag;
27 public InterfaceTraverser(TreeNode _root, IndexManager indexManager) { 22
28 this.node = _root; 23 public InterfaceTraverser(TreeNode _root, Index index, ParentIndex parentIndex, IndexManager indexManager,
29 this.index = new Index(); 24 boolean indexFlag) {
30 this.indexManager = indexManager;
31 }
32
33 public InterfaceTraverser(TreeNode _root, Index index,
34 IndexManager indexManager) {
35 this.node = _root; 25 this.node = _root;
36 this.index = index; 26 this.index = index;
37 this.indexManager = indexManager; 27 this.indexManager = indexManager;
38 } 28 this.parentIndex = parentIndex;
39 29 if (parentIndex.isEmpty())
40 public void commitIndex() { 30 parentUpdateFlag = true;
41 indexManager.commit(index); 31 else
32 parentUpdateFlag = false;
33 this.indexFlag = indexFlag;
42 } 34 }
43 35
44 public Index getIndex() { 36 public Index getIndex() {
45 return index; 37 return index;
46 } 38 }
47 39
40 public void commit() {
41 parentUpdateFlag = false;
42 indexManager.commit(index, parentIndex);
43 }
44
45 public ParentIndex getParentIndex() {
46 return parentIndex;
47 }
48
48 public void setIndex(Index index) { 49 public void setIndex(Index index) {
49 this.index = index; 50 this.index = index;
51 }
52
53 public Iterator<TreeNode> emptyQuery() {
54
55 final PathNodeIterator itNode = new PathNodeIterator(node);
56 return new Iterator<TreeNode>() {
57
58 private TreeNode matchNode = nextmatch(itNode);
59
60 private TreeNode nextmatch(PathNodeIterator itNode) {
61
62 for (; itNode.hasNext();) {
63 TreeNode targetNode = itNode.next();
64 List<String> keys = targetNode.getAttributes().getKeys();
65 for (String key : keys) {
66 String value = targetNode.getAttributes().getString(key);
67 if (value != null)
68 index = index.set(key, value, targetNode);
69 if (parentUpdateFlag)
70 parentIndex = parentIndex.set(targetNode);
71 }
72 }
73 commit();
74 return null;
75 }
76
77 @Override
78 public boolean hasNext() {
79 if (matchNode == null) {
80 return false;
81 }
82 return true;
83 }
84
85 @Override
86 public TreeNode next() {
87 TreeNode currentPair = matchNode;
88 matchNode = nextmatch(itNode);
89 return currentPair;
90 }
91
92 @Override
93 public void remove() {
94 }
95
96 };
97
50 } 98 }
51 99
52 /** 100 /**
53 * subTree以下のNodeに対してKey,Valueのペアでindexを使って探索を行う 101 * subTree以下のNodeに対してKey,Valueのペアでindexを使って探索を行う
54 * 102 *
56 * @param subTree 104 * @param subTree
57 * @param key 105 * @param key
58 * @param searchValue 106 * @param searchValue
59 * @return 107 * @return
60 */ 108 */
61 public Iterator<Pair<TreeNode, NodePath>> findInSubTree(Query query, Pair<TreeNode, NodePath> subTree, String key, 109 public Iterator<TreeNode> findInSubTree(Query query, TreeNode subTree, String key, String searchValue) {
62 String searchValue) {
63 /* 110 /*
64 * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から１つずつ比較し、 111 * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から１つずつ比較し、
65 * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す 112 * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す
66 */ 113 */
67 114 List<TreeNode> nodeList = index.get(key, searchValue);
68 if (index.get(key).isSome()) { 115 if (nodeList != null) {
69 116
70 TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index.get(key).some(); 117 if (nodeList.isEmpty())
71 118 return new NulIterator<TreeNode>();// 空のIteratorを返す
72 Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue); 119
73 120 // ここでNode以下にあるか調べる
74 if (opList.isNone()) 121 List<TreeNode> filteredList = List.nil();
75 return new NulIterator<Pair<TreeNode, NodePath>>();// 空のIteratorを返す 122
76 123 for (TreeNode targetNode : nodeList) {
77 List<Pair<TreeNode, NodePath>> list = opList.some(); 124 TreeNode parent = targetNode;
78 NodePath targetNodePath = subTree.right(); 125 while (parent != null) {
79 List<Pair<TreeNode, NodePath>> filteredList = List.nil(); 126 parent = parentIndex.get(parent);
80 127 if (parent.equals(subTree))
81 for (Pair<TreeNode, NodePath> pair : list) { 128 filteredList = filteredList.cons(targetNode);
82 NodePath compareNodePath = pair.right(); 129 }
83 if (targetNodePath.compare(compareNodePath))
84 filteredList = filteredList.cons(pair);
85 } 130 }
86 131
87 return filteredList.iterator(); 132 return filteredList.iterator();
88 133
89 } else { 134 } else {
90 final PathNodeIterator itNode = new PathNodeIterator(subTree); 135 final PathNodeIterator itNode = new PathNodeIterator(subTree);
91 return new Iterator<Pair<TreeNode, NodePath>>() { 136 return new Iterator<TreeNode>() {
92 137
93 private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode); 138 private TreeNode matchNode = nextmatch(itNode);
94 139
95 private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) { 140 private TreeNode nextmatch(PathNodeIterator itNode) {
96 141
97 for (; itNode.hasNext();) { 142 for (; itNode.hasNext();) {
98 Pair<TreeNode, NodePath> pathNode = itNode.next(); 143 TreeNode targetNode = itNode.next();
99 if (query.condition(pathNode.left())) 144 if (query.condition(targetNode))
100 return pathNode; 145 return targetNode;
101 } 146 }
102 return null; 147 return null;
103 } 148 }
104 149
105 @Override 150 @Override
106 public boolean hasNext() { 151 public boolean hasNext() {
107 if (matchPair == null) { 152 if (matchNode == null) {
108 return false; 153 return false;
109 } 154 }
110 return true; 155 return true;
111 } 156 }
112 157
113 @Override 158 @Override
114 public Pair<TreeNode, NodePath> next() { 159 public TreeNode next() {
115 Pair<TreeNode, NodePath> currentPair = matchPair; 160 TreeNode currentNode = matchNode;
116 matchPair = nextmatch(itNode); 161 matchNode = nextmatch(itNode);
117 return currentPair; 162 return currentNode;
118 } 163 }
119 164
120 @Override 165 @Override
121 public void remove() { 166 public void remove() {
122 } 167 }
132 * @param subTree 177 * @param subTree
133 * @param key 178 * @param key
134 * @param searchValue 179 * @param searchValue
135 * @return 180 * @return
136 */ 181 */
137 public Iterator<Pair<TreeNode, NodePath>> findInSubTreeAllValue(Query query, Pair<TreeNode, NodePath> subTree, 182 public Iterator<TreeNode> findInSubTreeAllValue(Query query, TreeNode subTree, String key) {
138 String key) {
139 /* 183 /*
140 * indexからinnerIndexを取得 取得したinnerIndexが保有するKeyを取得 184 * indexからinnerIndexを取得 取得したinnerIndexが保有するKeyを取得
141 * そのKeyを保有するNodeとNodeのPathを取得する 185 * そのKeyを保有するNodeとNodeのPathを取得する
142 * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から１つずつ比較し、 186 * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から１つずつ比較し、
143 * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す 187 * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す
144 */ 188 */
145 189 Iterator<TreeNode> NodeIterator = index.getAll(key);
146 if (index.get(key).isSome()) { 190 if (NodeIterator != null) {
147 191 List<TreeNode> filteredList = List.nil();
148 TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index.get(key).some(); 192 for (; NodeIterator.hasNext();) {
149 List<String> searchValues = innerIndex.keys(); 193 TreeNode targetNode = NodeIterator.next();
150 List<Pair<TreeNode, NodePath>> filteredList = List.nil(); 194 TreeNode parent = targetNode;
151 NodePath targetNodePath = subTree.right(); 195 while (parent != null) {
152 196 parent = parentIndex.get(parent);
153 for (String searchValue : searchValues) { 197 if (parent.equals(subTree))
154 Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue); 198 filteredList = filteredList.cons(targetNode);
155
156 if (opList.isNone())
157 continue;
158
159 List<Pair<TreeNode, NodePath>> list = opList.some();
160 for (Pair<TreeNode, NodePath> pair : list) {
161 NodePath compareNodePath = pair.right();
162 if (targetNodePath.compare(compareNodePath))
163 filteredList = filteredList.cons(pair);
164
165 } 199 }
166 } 200 }
167 return filteredList.iterator(); 201 return filteredList.iterator();
168 202
169 } else { 203 } else {
204
170 final PathNodeIterator itNode = new PathNodeIterator(subTree); 205 final PathNodeIterator itNode = new PathNodeIterator(subTree);
171 return new Iterator<Pair<TreeNode, NodePath>>() { 206 return new Iterator<TreeNode>() {
172 207
173 private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode); 208 private TreeNode matchPair = nextmatch(itNode);
174 209
175 private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) { 210 private TreeNode nextmatch(PathNodeIterator itNode) {
176 211
177 for (; itNode.hasNext();) { 212 for (; itNode.hasNext();) {
178 Pair<TreeNode, NodePath> pathNode = itNode.next(); 213 TreeNode targetNode = itNode.next();
179 if (query.condition(pathNode.left())) 214 if (query.condition(targetNode))
180 return pathNode; 215 return targetNode;
181 } 216 }
182 return null; 217 return null;
183 } 218 }
184 219
185 @Override 220 @Override
189 } 224 }
190 return true; 225 return true;
191 } 226 }
192 227
193 @Override 228 @Override
194 public Pair<TreeNode, NodePath> next() { 229 public TreeNode next() {
195 Pair<TreeNode, NodePath> currentPair = matchPair; 230 TreeNode currentNode = matchPair;
196 matchPair = nextmatch(itNode); 231 matchPair = nextmatch(itNode);
197 return currentPair; 232 return currentNode;
198 } 233 }
199 234
200 @Override 235 @Override
201 public void remove() { 236 public void remove() {
202 } 237 }
203 238
204 }; 239 };
205 } 240 }
206 } 241 }
207 242
208 public Iterator<Pair<TreeNode, NodePath>> find(Query query, String key, String searchValue) { 243 public Iterator<TreeNode> find(Query query, String key, String searchValue) {
209 244
210 if (index.get(key).isSome()) { 245 List<TreeNode> nodeList = index.get(key, searchValue);
211 246 if (nodeList != null) {
212 TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index.get(key).some(); 247 return nodeList.iterator();
213 Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue);
214
215 if (opList.isNone())
216 return new NulIterator<Pair<TreeNode, NodePath>>();// 空のIteratorを返す
217
218 final List<Pair<TreeNode, NodePath>> list = opList.some();
219 return list.iterator();
220
221 } else { 248 } else {
222 Pair<TreeNode, NodePath> pair = new Pair<TreeNode, NodePath>(node, new DefaultNodePath()); 249
223 final PathNodeIterator itNode = new PathNodeIterator(pair); 250 final PathNodeIterator itNode = new PathNodeIterator(node);
224 return new Iterator<Pair<TreeNode, NodePath>>() { 251 return new Iterator<TreeNode>() {
225 252
226 private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode); 253 private TreeNode matchNode = nextmatch(itNode);
227 254
228 private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) { 255 private TreeNode nextmatch(PathNodeIterator itNode) {
229 256
230 for (; itNode.hasNext();) { 257 for (; itNode.hasNext();) {
231 Pair<TreeNode, NodePath> pathNode = itNode.next(); 258 TreeNode targetNode = itNode.next();
232 String value = pathNode.left().getAttributes().getString(key); 259 String value = targetNode.getAttributes().getString(key);
233 Option<TreeMap<String, List<Pair<TreeNode, NodePath>>>> innerIndexOp = index.get(key); 260 if (indexFlag) {
234 261 if (value != null)
235 if (value != null) { 262 index = index.set(key, value, targetNode);
236 if (innerIndexOp.isNone()) {
237
238 TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = TreeMap.empty(Ord.stringOrd);
239 List<Pair<TreeNode, NodePath>> list = List.nil();
240 list = list.cons(pathNode);
241 innerIndex = innerIndex.set(value, list);
242 index = index.set(key, innerIndex);
243
244 } else {
245
246 TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = innerIndexOp.some();
247 Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(value);
248
249 if (opList.isNone()) {
250
251 List<Pair<TreeNode, NodePath>> list = List.nil();
252 list = list.cons(pathNode);
253 innerIndex = innerIndex.set(value, list);
254
255 } else {
256
257 List<Pair<TreeNode, NodePath>> list = opList.some();
258 list = list.cons(pathNode);
259 innerIndex = innerIndex.set(value, list);
260
261 }
262 index = index.set(key, innerIndex);
263
264 }
265 } 263 }
266 264 if (parentUpdateFlag)
267 if (query.condition(pathNode.left())) 265 parentIndex = parentIndex.set(targetNode);
268 return pathNode; 266 if (query.condition(targetNode))
269 } 267 return targetNode;
268 }
269 commit();
270 return null; 270 return null;
271 } 271 }
272 272
273 @Override 273 @Override
274 public boolean hasNext() { 274 public boolean hasNext() {
275 if (matchPair == null) { 275 if (matchNode == null) {
276 // index = itNode.getIndex();
277 return false; 276 return false;
278 } 277 }
279 return true; 278 return true;
280 } 279 }
281 280
282 @Override 281 @Override
283 public Pair<TreeNode, NodePath> next() { 282 public TreeNode next() {
284 Pair<TreeNode, NodePath> currentPair = matchPair; 283 TreeNode currentPair = matchNode;
285 matchPair = nextmatch(itNode); 284 matchNode = nextmatch(itNode);
286 return currentPair; 285 return currentPair;
287 } 286 }
288 287
289 @Override 288 @Override
290 public void remove() { 289 public void remove() {
292 291
293 }; 292 };
294 } 293 }
295 } 294 }
296 295
297 public Iterator<Pair<TreeNode, NodePath>> findAll(Query query, String key) { 296 public Iterator<TreeNode> findAll(Query query, String key) {
298 297
299 if (index.get(key).isSome()) { 298 Iterator<TreeNode> nodeList = index.getAll(key);
300 299 if (nodeList != null) {
301 TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = this.index.get(key).some(); 300
302 List<String> searchValues = innerIndex.keys(); 301 return nodeList;
303 List<Pair<TreeNode, NodePath>> valueList = List.nil();
304
305 for (String searchValue : searchValues) {
306 Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(searchValue);
307
308 if (opList.isNone())
309 continue;
310
311 List<Pair<TreeNode, NodePath>> list = opList.some();
312 valueList = valueList.append(list);
313 }
314 return valueList.iterator();
315 302
316 } else { 303 } else {
317 Pair<TreeNode, NodePath> pair = new Pair<TreeNode, NodePath>(node, new DefaultNodePath()); 304
318 final PathNodeIterator itNode = new PathNodeIterator(pair); 305 final PathNodeIterator itNode = new PathNodeIterator(node);
319 return new Iterator<Pair<TreeNode, NodePath>>() { 306 return new Iterator<TreeNode>() {
320 307
321 private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode); 308 private TreeNode matchNode = nextmatch(itNode);
322 309
323 private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) { 310 private TreeNode nextmatch(PathNodeIterator itNode) {
324 311
325 for (; itNode.hasNext();) { 312 for (; itNode.hasNext();) {
326 Pair<TreeNode, NodePath> pathNode = itNode.next(); 313 TreeNode targetNode = itNode.next();
327 String value = pathNode.left().getAttributes().getString(key); 314 String value = targetNode.getAttributes().getString(key);
328 Option<TreeMap<String, List<Pair<TreeNode, NodePath>>>> innerIndexOp = index.get(key); 315 if (indexFlag) {
329 316 if (value != null)
330 if (value != null) { 317 index = index.set(key, value, targetNode);
331 if (innerIndexOp.isNone()) {
332
333 TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = TreeMap.empty(Ord.stringOrd);
334 List<Pair<TreeNode, NodePath>> list = List.nil();
335 list = list.cons(pathNode);
336 innerIndex = innerIndex.set(value, list);
337 index = index.set(key, innerIndex);
338
339 } else {
340
341 TreeMap<String, List<Pair<TreeNode, NodePath>>> innerIndex = innerIndexOp.some();
342 Option<List<Pair<TreeNode, NodePath>>> opList = innerIndex.get(value);
343
344 if (opList.isNone()) {
345
346 List<Pair<TreeNode, NodePath>> list = List.nil();
347 list = list.cons(pathNode);
348 innerIndex = innerIndex.set(value, list);
349
350 } else {
351
352 List<Pair<TreeNode, NodePath>> list = opList.some();
353 list = list.cons(pathNode);
354 innerIndex = innerIndex.set(value, list);
355
356 }
357 index = index.set(key, innerIndex);
358
359 }
360 } 318 }
361 319 if (parentUpdateFlag)
362 if (query.condition(pathNode.left())) 320 parentIndex = parentIndex.set(targetNode);
363 return pathNode; 321 if (query.condition(targetNode))
364 } 322 return targetNode;
323 }
324 commit();
365 return null; 325 return null;
366 } 326 }
367 327
368 @Override 328 @Override
369 public boolean hasNext() { 329 public boolean hasNext() {
370 if (matchPair == null) { 330 if (matchNode == null) {
371 // index = itNode.getIndex();
372 return false; 331 return false;
373 } 332 }
374 return true; 333 return true;
375 } 334 }
376 335
377 @Override 336 @Override
378 public Pair<TreeNode, NodePath> next() { 337 public TreeNode next() {
379 Pair<TreeNode, NodePath> currentPair = matchPair; 338 TreeNode currentPair = matchNode;
380 matchPair = nextmatch(itNode); 339 matchNode = nextmatch(itNode);
381 return currentPair; 340 return currentPair;
382 } 341 }
383 342
384 @Override 343 @Override
385 public void remove() { 344 public void remove() {