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