+++ /dev/null
-/*--------------------------------------------------------------------------\r
- * Copyright 2004 Taro L. Saito\r
- *\r
- * Licensed under the Apache License, Version 2.0 (the "License");\r
- * you may not use this file except in compliance with the License.\r
- * You may obtain a copy of the License at\r
- *\r
- * http://www.apache.org/licenses/LICENSE-2.0\r
- *\r
- * Unless required by applicable law or agreed to in writing, software\r
- * distributed under the License is distributed on an "AS IS" BASIS,\r
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
- * See the License for the specific language governing permissions and\r
- * limitations under the License.\r
- *--------------------------------------------------------------------------*/\r
-//--------------------------------------\r
-// XerialJ Project\r
-//\r
-// InvertedPathTree.java\r
-// Since: 2005/06/02\r
-//\r
-// $URL: http://www.xerial.org/svn/project/XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/xml/index/InvertedPathTree.java $ \r
-// $Author: leo $\r
-//--------------------------------------\r
-package org.xerial.util.xml.index;\r
-\r
-import static org.xmlpull.v1.XmlPullParser.*;\r
-\r
-import java.io.BufferedReader;\r
-import java.io.FileNotFoundException;\r
-import java.io.FileReader;\r
-import java.io.IOException;\r
-import java.io.OutputStream;\r
-import java.io.Reader;\r
-import java.util.Collection;\r
-\r
-import org.xerial.core.XerialException;\r
-import org.xerial.util.graph.AdjacencyList;\r
-import org.xerial.util.graph.Edge;\r
-import org.xerial.util.graph.Graph;\r
-import org.xerial.util.graph.GraphvizHelper;\r
-import org.xerial.util.opt.Argument;\r
-import org.xerial.util.opt.Option;\r
-import org.xerial.util.opt.OptionParser;\r
-import org.xerial.util.opt.OptionParserException;\r
-import org.xerial.util.xml.XMLErrorCode;\r
-import org.xerial.util.xml.XMLException;\r
-import org.xerial.util.xml.pullparser.PullParserUtil;\r
-import org.xmlpull.v1.XmlPullParser;\r
-import org.xmlpull.v1.XmlPullParserException;\r
-\r
-/**\r
- * Inverted path tree is a set of inverted paths represented with a graph\r
- * \r
- * @author leo\r
- * \r
- */\r
-public class InvertedPathTree {\r
- private Graph<InvertedPath, String> _pathTree = new AdjacencyList<InvertedPath, String>();\r
- // TreeMap<InvertedPath, Integer> _path2idMap = new TreeMap<InvertedPath, Integer>();\r
- // TreeMap<Integer, InvertedPath> _id2pathMap = new TreeMap<Integer, InvertedPath>();\r
- InvertedPath _currentInvertedPath = new InvertedPath();\r
- int _rootID;\r
-\r
- /**\r
- * \r
- */\r
- public InvertedPathTree() {\r
- super();\r
- InvertedPath rootPath = new InvertedPath();\r
- _rootID = _pathTree.addNode(rootPath);\r
- }\r
-\r
- public void generateFrom(String xmlFile) throws XMLException, FileNotFoundException,\r
- IOException {\r
- generateFrom(new BufferedReader(new FileReader(xmlFile)));\r
- }\r
-\r
- public void generateFrom(Reader xmlReader) throws IOException, XMLException {\r
- XmlPullParser parser = PullParserUtil.newParser(xmlReader);\r
-\r
- try {\r
- int state;\r
- while ((state = parser.next()) != END_DOCUMENT) {\r
- switch (state) {\r
- case START_TAG:\r
- _currentInvertedPath.addChild(parser.getName());\r
- for (int i = 0; i < parser.getAttributeCount(); i++) {\r
- _currentInvertedPath.addChild("@" + parser.getAttributeName(i));\r
- updateInvertedPathTree();\r
- _currentInvertedPath.removeFirstChild();\r
- }\r
- break;\r
- case END_TAG:\r
- updateInvertedPathTree();\r
- _currentInvertedPath.removeFirstChild();\r
- break;\r
- }\r
- }\r
-\r
- }\r
- catch (XmlPullParserException e) {\r
- throw new XMLException(XMLErrorCode.PARSE_ERROR, e);\r
- }\r
- }\r
-\r
- /**\r
- * add nodes and edges corresponding to the current path\r
- */\r
- private void updateInvertedPathTree() {\r
- int cursor = _rootID;\r
- InvertedPath cursorPath = new InvertedPath();\r
- for (String tag : _currentInvertedPath) {\r
- cursorPath.addParent(tag);\r
- Collection<Integer> destNodeID = _pathTree.getDestNodeIDSetOf(cursor);\r
- int pathID = getPathID(cursorPath);\r
- if (!destNodeID.contains(pathID)) {\r
- // create an edge from the cursor node to the pathID node\r
- _pathTree.addEdge(new Edge(cursor, pathID), "edge");\r
- }\r
- cursor = pathID;\r
- }\r
- }\r
-\r
- private int getPathID(InvertedPath path) {\r
- int pathID = _pathTree.getNodeID(path);\r
- if (pathID == -1) {\r
- InvertedPath clonePath = new InvertedPath(path);\r
- pathID = _pathTree.addNode(clonePath);\r
- }\r
- return pathID;\r
- }\r
-\r
- public void outputGraphviz(OutputStream os) {\r
- GraphvizHelper gout = new GraphvizHelper(os);\r
- gout.beginDigraph("G");\r
-\r
- // output node labels\r
- for (int pathID : _pathTree.getNodeIDSet()) {\r
- InvertedPath path = _pathTree.getNodeLabel(pathID);\r
- assert path != null;\r
- gout.node(pathID, path.getLastParent());\r
- }\r
-\r
- // output edges\r
- outputGraphvizEdges(gout, _rootID);\r
-\r
- gout.endDigraph();\r
- gout.endOutput();\r
- }\r
-\r
- private void outputGraphvizEdges(GraphvizHelper gout, int currentNodeID) {\r
- for (int dest : _pathTree.getDestNodeIDSetOf(currentNodeID)) {\r
- gout.edge(currentNodeID, dest);\r
- outputGraphvizEdges(gout, dest); // recursion\r
- }\r
- }\r
-\r
- @Option(symbol = "h", longName = "help", description = "display help messsage")\r
- private boolean displayHelp = false;\r
-\r
- @Argument(index = 0, required = false)\r
- private String xmlFile = null;\r
-\r
- public static void main(String[] args) throws OptionParserException {\r
- InvertedPathTree ipt = new InvertedPathTree();\r
- OptionParser opt = new OptionParser(ipt);\r
-\r
- opt.parse(args);\r
- if (ipt.displayHelp || ipt.xmlFile == null) {\r
- printHelpMessage(opt);\r
- return;\r
- }\r
-\r
- try {\r
- ipt.generateFrom(ipt.xmlFile);\r
- ipt.outputGraphviz(System.out);\r
- }\r
- catch (XerialException e) {\r
- System.err.println(e.getMessage());\r
- }\r
- catch (IOException e) {\r
- System.err.println(e.getMessage());\r
- }\r
- }\r
-\r
- private static void printHelpMessage(OptionParser opt) {\r
- opt.printUsage();\r
- }\r
-}\r
OSDN Git Service
