Mercurial > hg > Members > tatsuki > bench > jungle-core
view src/main/java/jp/ac/u_ryukyu/ie/cr/shoshi/jungle/traverser/InterfaceTraverser.java @ 143:afbe19c98f53
change Index form TreeMap<String,TreeMap<String<List<Pair<TreeNode,NodePath>>>> → TreeMap<String,TreeMap<String<List<NodePath>>>
bag
author | one |
---|---|
date | Sat, 15 Nov 2014 17:48:07 +0900 |
parents | 3071b1a471fd |
children | 0854f9a9e81d |
line wrap: on
line source
package jp.ac.u_ryukyu.ie.cr.shoshi.jungle.traverser; import java.util.Iterator; import fj.Ord; import fj.P2; import fj.data.List; import fj.data.Option; import fj.data.TreeMap; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NulIterator; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Either; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Error; import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair; import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.PathNodeIterator; import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query.Query; import jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.store.index.IndexManager; public class InterfaceTraverser { // InterfaceTraverser traverser; TreeNode node; TreeMap<String, TreeMap<String, List<NodePath>>> index; IndexManager indexManager; public InterfaceTraverser(TreeNode _root, IndexManager indexManager) { this.node = _root; this.index = TreeMap.empty(Ord.stringOrd); this.indexManager = indexManager; } public InterfaceTraverser(TreeNode _root, TreeMap<String, TreeMap<String, List<NodePath>>> index, IndexManager indexManager) { this.node = _root; this.index = index; this.indexManager = indexManager; } public void commitIndex() { indexManager.commit(index); } public TreeMap<String, TreeMap<String, List<NodePath>>> getIndex() { return index; } public void setIndex(TreeMap<String, TreeMap<String, List<NodePath>>> index) { this.index = index; } /** * subTree以下のNodeに対してKey,Valueのペアでindexを使って探索を行う * * @param query * @param subTree * @param key * @param searchValue * @return */ public Iterator<Pair<TreeNode, NodePath>> findInSubTree(Query query, Pair<TreeNode, NodePath> subTree, String key, String searchValue) { /* * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から1つずつ比較し、 * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す */ if (index.get(key).isSome()) { TreeMap<String, List<NodePath>> innerIndex = this.index.get(key).some(); Option<List<NodePath>> opList = innerIndex.get(searchValue); if (opList.isNone()) return new NulIterator<Pair<TreeNode, NodePath>>();// 空のIteratorを返す List<NodePath> list = opList.some(); NodePath targetNodePath = subTree.right(); return new Iterator<Pair<TreeNode, NodePath>>() { NodePath path; List<NodePath> comparePathList = list; @Override public boolean hasNext() { for (NodePath comparePath : comparePathList) { this.path = comparePath; comparePathList = comparePathList.tail(); if (targetNodePath.compare(path)) return true; } return false; } @Override public Pair<TreeNode, NodePath> next() { TreeNode targetNode = getTarget(node, path); Pair<TreeNode, NodePath> targetPair = new Pair<TreeNode, NodePath>(targetNode, path); return targetPair; } }; } else { final PathNodeIterator itNode = new PathNodeIterator(subTree); return new Iterator<Pair<TreeNode, NodePath>>() { private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode); private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) { for (; itNode.hasNext();) { Pair<TreeNode, NodePath> pathNode = itNode.next(); if (query.condition(pathNode.left())) return pathNode; } return null; } @Override public boolean hasNext() { if (matchPair == null) { return false; } return true; } @Override public Pair<TreeNode, NodePath> next() { Pair<TreeNode, NodePath> currentPair = matchPair; matchPair = nextmatch(itNode); return currentPair; } @Override public void remove() { } }; } } /** * subTree以下のNodeに対してKeyに対応する値をindexを使って探索する * * @param query * @param subTree * @param key * @param searchValue * @return */ public Iterator<Pair<TreeNode, NodePath>> findInSubTreeAllValue(Query query, Pair<TreeNode, NodePath> subTree, String key) { /* * indexからinnerIndexを取得 取得したinnerIndexが保有するKeyを取得 * そのKeyを保有するNodeとNodeのPathを取得する * indexを使って取ってきたNodeのPathと、subTreeのPathを先頭から1つずつ比較し、 * indexから取ってきたNodeのPathが一致した場合、そのNodeを返す */ if (index.get(key).isSome()) { TreeMap<String, List<NodePath>> innerIndex = this.index.get(key).some(); Iterator<P2<String, List<NodePath>>> searchValueIterator = innerIndex.iterator(); Iterator<P2<String, List<NodePath>>> searchValueIterator2 = innerIndex.iterator(); System.out.println("start-----------------------------------------------------------------"); for (;searchValueIterator2.hasNext();) { String a = searchValueIterator2.next()._1(); System.out.println(a); } NodePath targetNodePath = subTree.right(); return new Iterator<Pair<TreeNode, NodePath>>() { List<NodePath> pathList = List.nil(); NodePath path; @Override public boolean hasNext() { if (!pathList.isEmpty()) { path = pathList.head(); pathList = pathList.tail(); if (targetNodePath.compare(path)) return true; return this.hasNext(); } if (searchValueIterator.hasNext()) { pathList = searchValueIterator.next()._2(); path = pathList.head(); pathList = pathList.tail(); if (targetNodePath.compare(path)) return true; return this.hasNext(); } return false; } @Override public Pair<TreeNode, NodePath> next() { TreeNode targetNode = getTarget(node, path); Pair<TreeNode, NodePath> targetPair = new Pair<TreeNode, NodePath>(targetNode, path); return targetPair; } }; } else { final PathNodeIterator itNode = new PathNodeIterator(subTree); return new Iterator<Pair<TreeNode, NodePath>>() { private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode); private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) { for (; itNode.hasNext();) { Pair<TreeNode, NodePath> pathNode = itNode.next(); if (query.condition(pathNode.left())) return pathNode; } return null; } @Override public boolean hasNext() { if (matchPair == null) { return false; } return true; } @Override public Pair<TreeNode, NodePath> next() { Pair<TreeNode, NodePath> currentPair = matchPair; matchPair = nextmatch(itNode); return currentPair; } @Override public void remove() { } }; } } public Iterator<Pair<TreeNode, NodePath>> find(Query query, String key, String searchValue) { if (index.get(key).isSome()) { TreeMap<String, List<NodePath>> innerIndex = this.index.get(key).some(); Option<List<NodePath>> opList = innerIndex.get(searchValue); if (opList.isNone()) return new NulIterator<Pair<TreeNode, NodePath>>();// 空のIteratorを返す final List<NodePath> list = opList.some(); return new Iterator<Pair<TreeNode, NodePath>>() { List<NodePath> pathList = list; NodePath targetPath; @Override public boolean hasNext() { if (!pathList.isEmpty()) { targetPath = pathList.head(); pathList = pathList.tail(); return true; } return false; } @Override public Pair<TreeNode, NodePath> next() { TreeNode targetNode = getTarget(node, targetPath); Pair<TreeNode, NodePath> targetPair = new Pair<TreeNode, NodePath>(targetNode, targetPath); return targetPair; } }; } else { Pair<TreeNode, NodePath> pair = new Pair<TreeNode, NodePath>(node, new DefaultNodePath()); final PathNodeIterator itNode = new PathNodeIterator(pair); return new Iterator<Pair<TreeNode, NodePath>>() { private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode); private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) { for (; itNode.hasNext();) { Pair<TreeNode, NodePath> pathNode = itNode.next(); String value = pathNode.left().getAttributes().getString(key); Option<TreeMap<String, List<NodePath>>> innerIndexOp = index.get(key); if (value != null) { if (innerIndexOp.isNone()) { TreeMap<String, List<NodePath>> innerIndex = TreeMap.empty(Ord.stringOrd); List<NodePath> list = List.nil(); list = list.cons(pathNode.right()); innerIndex = innerIndex.set(value, list); index = index.set(key, innerIndex); } else { TreeMap<String, List<NodePath>> innerIndex = innerIndexOp.some(); Option<List<NodePath>> opList = innerIndex.get(value); if (opList.isNone()) { List<NodePath> list = List.nil(); list = list.cons(pathNode.right()); innerIndex = innerIndex.set(value, list); } else { List<NodePath> list = opList.some(); list = list.cons(pathNode.right()); innerIndex = innerIndex.set(value, list); } index = index.set(key, innerIndex); } } if (query.condition(pathNode.left())) return pathNode; } return null; } @Override public boolean hasNext() { if (matchPair == null) { // index = itNode.getIndex(); return false; } return true; } @Override public Pair<TreeNode, NodePath> next() { Pair<TreeNode, NodePath> currentPair = matchPair; matchPair = nextmatch(itNode); return currentPair; } @Override public void remove() { } }; } } public Iterator<Pair<TreeNode, NodePath>> findAll(Query query, String key) { if (index.get(key).isSome()) { TreeMap<String, List<NodePath>> innerIndex = this.index.get(key).some(); Iterator<P2<String, List<NodePath>>> searchValueIterator = innerIndex.iterator(); return new Iterator<Pair<TreeNode, NodePath>>() { List<NodePath> pathList = List.nil(); NodePath targetPath; @Override public boolean hasNext() { if (!pathList.isEmpty()) { targetPath = pathList.head(); pathList = pathList.tail(); return true; } if (searchValueIterator.hasNext()) { pathList = searchValueIterator.next()._2(); targetPath = pathList.head(); pathList = pathList.tail(); return true; } return false; } @Override public Pair<TreeNode, NodePath> next() { TreeNode targetNode = getTarget(node, targetPath); Pair<TreeNode, NodePath> targetPair = new Pair<TreeNode, NodePath>(targetNode, targetPath); return targetPair; } }; } else { Pair<TreeNode, NodePath> pair = new Pair<TreeNode, NodePath>(node, new DefaultNodePath()); final PathNodeIterator itNode = new PathNodeIterator(pair); return new Iterator<Pair<TreeNode, NodePath>>() { private Pair<TreeNode, NodePath> matchPair = nextmatch(itNode); private Pair<TreeNode, NodePath> nextmatch(PathNodeIterator itNode) { for (; itNode.hasNext();) { Pair<TreeNode, NodePath> pathNode = itNode.next(); String value = pathNode.left().getAttributes().getString(key); Option<TreeMap<String, List<NodePath>>> innerIndexOp = index.get(key); if (value != null) { if (innerIndexOp.isNone()) { TreeMap<String, List<NodePath>> innerIndex = TreeMap.empty(Ord.stringOrd); List<NodePath> list = List.nil(); list = list.cons(pathNode.right()); innerIndex = innerIndex.set(value, list); index = index.set(key, innerIndex); } else { TreeMap<String, List<NodePath>> innerIndex = innerIndexOp.some(); Option<List<NodePath>> opList = innerIndex.get(value); if (opList.isNone()) { List<NodePath> list = List.nil(); list = list.cons(pathNode.right()); innerIndex = innerIndex.set(value, list); } else { List<NodePath> list = opList.some(); list = list.cons(pathNode.right()); innerIndex = innerIndex.set(value, list); } index = index.set(key, innerIndex); } } if (query.condition(pathNode.left())) return pathNode; } return null; } @Override public boolean hasNext() { if (matchPair == null) { // index = itNode.getIndex(); return false; } return true; } @Override public Pair<TreeNode, NodePath> next() { Pair<TreeNode, NodePath> currentPair = matchPair; matchPair = nextmatch(itNode); return currentPair; } @Override public void remove() { } }; } } public TreeNode getTarget(TreeNode node, NodePath path) { Pair<Integer, NodePath> removeHeadPath = path.pop(); if (removeHeadPath.left() == -1) return getTarget(node, removeHeadPath.right()); Either<Error, TreeNode> either = node.getChildren().at(removeHeadPath.left()); if (either.isA()) return node; TreeNode child = either.b(); if (removeHeadPath.right().size() == 0) return child; TreeNode target = getTarget(child, removeHeadPath.right()); return target; } }