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