最新在看xwork的源代码,XmlConfigurationProvider这个类,用来实现解析xwork.xml配置文件。该类使用了有向图这种数据结构,来判断是否存在<include>元素的循环包含。
有向图的实现如下:
import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; public final class DirectedGraph<T> implements Iterable<T> { private final Map<T, Set<T>> mGraph = new HashMap<T, Set<T>>(); /** * Adds a new node to the graph. If the node already exists, this function is a no-op. * * @param node * The node to add. * @return Whether or not the node was added. */ public boolean addNode(T node) { /* If the node already exists, don't do anything. */ if (mGraph.containsKey(node)) return false; /* Otherwise, add the node with an empty set of outgoing edges. */ mGraph.put(node, new HashSet<T>()); return true; } /** * Given a start node, and a destination, adds an arc from the start node to the destination. If an arc already exists, this operation is a no-op. * If either endpoint does not exist in the graph, throws a NoSuchElementException. * * @param start * The start node. * @param dest * The destination node. * @throws NoSuchElementException * If either the start or destination nodes do not exist. */ public void addEdge(T start, T dest) { /* Confirm both endpoints exist. */ if (!mGraph.containsKey(start)) { throw new NoSuchElementException("The start node does not exist in the graph."); } else if (!mGraph.containsKey(dest)) { throw new NoSuchElementException("The destination node does not exist in the graph."); } /* Add the edge. */ mGraph.get(start).add(dest); } /** * Removes the edge from start to dest from the graph. If the edge does not exist, this operation is a no-op. If either endpoint does not exist, * this throws a NoSuchElementException. * * @param start * The start node. * @param dest * The destination node. * @throws NoSuchElementException * If either node is not in the graph. */ public void removeEdge(T start, T dest) { /* Confirm both endpoints exist. */ if (!mGraph.containsKey(start)) { throw new NoSuchElementException("The start node does not exist in the graph."); } else if (!mGraph.containsKey(dest)) { throw new NoSuchElementException("The destination node does not exist in the graph."); } mGraph.get(start).remove(dest); } /** * Given two nodes in the graph, returns whether there is an edge from the first node to the second node. If either node does not exist in the * graph, throws a NoSuchElementException. * * @param start * The start node. * @param end * The destination node. * @return Whether there is an edge from start to end. * @throws NoSuchElementException * If either endpoint does not exist. */ public boolean edgeExists(T start, T end) { /* Confirm both endpoints exist. */ if (!mGraph.containsKey(start)) { throw new NoSuchElementException("The start node does not exist in the graph."); } else if (!mGraph.containsKey(end)) { throw new NoSuchElementException("The end node does not exist in the graph."); } return mGraph.get(start).contains(end); } /** * Given a node in the graph, returns an immutable view of the edges leaving that node as a set of endpoints. * * @param node * The node whose edges should be queried. * @return An immutable view of the edges leaving that node. * @throws NoSuchElementException * If the node does not exist. */ public Set<T> edgesFrom(T node) { /* Check that the node exists. */ Set<T> arcs = mGraph.get(node); if (arcs == null) throw new NoSuchElementException("Source node does not exist."); return Collections.unmodifiableSet(arcs); } /** * Returns an iterator that can traverse the nodes in the graph. * * @return An iterator that traverses the nodes in the graph. */ public Iterator<T> iterator() { return mGraph.keySet().iterator(); } /** * Returns the number of nodes in the graph. * * @return The number of nodes in the graph. */ public int size() { return mGraph.size(); } /** * Returns whether the graph is empty. * * @return Whether the graph is empty. */ public boolean isEmpty() { return mGraph.isEmpty(); } }
通过上述源码发现:xwork框架采用的是有向图的邻接表方法进行存储的。
xwork使用CycleDetector用来判断有向图是否存在循环,实现如下:
public class CycleDetector<T> { private static final String marked = "marked"; private static final String complete = "complete"; private DirectedGraph<T> graph; private Map<T, String> marks; private List<T> verticesInCycles; public CycleDetector(DirectedGraph<T> graph) { this.graph = graph; marks = new HashMap<T, String>(); verticesInCycles = new ArrayList<T>(); } public boolean containsCycle() { for (T v : graph) { // 如果v正在遍历或者遍历完成,不需要进入mark(),因为mark是一个递归调用,使用的是深度优先搜索算法; // 这是为了保证1个顶点只会遍历一次 if (!marks.containsKey(v)) { if (mark(v)) { // return true; } } } return !verticesInCycles.isEmpty(); } //DFS算法,遍历顶点vertex // @return 当前顶点是否在环上 private boolean mark(T vertex) { List<T> localCycles = new ArrayList<T>(); // 当前顶点vertex,遍历开始 marks.put(vertex, marked); for (T u : graph.edgesFrom(vertex)) { // u的遍历还没有结束,说明存在u->vertex的通路,也存在vertex->u的通路,形成了循环 if (marks.containsKey(u) && marks.get(u).equals(marked)) { localCycles.add(vertex); // return true; } else if (!marks.containsKey(u)) { if (mark(u)) { localCycles.add(vertex); // return true; } } } // 当前顶点vertex,遍历完成 marks.put(vertex, complete); verticesInCycles.addAll(localCycles); return !localCycles.isEmpty(); } public List<T> getVerticesInCycles() { return verticesInCycles; } }
相关推荐
HelloNativeTest.java 测试本地化是否成功的类文件 instanceVar.java 定义一个实例成员变量 invokeByObject.java 对象实参传递示例程序 invokeByValue.java 传值调用示例程序 invokeMethod.java 同一个类中调用...
1.1.1 Java有什么优势? 2 1.1.2 Java在哪儿? 3 1.2 准备好开始Java之旅 3 1.2.1 下载JDK 4 1.2.2 安装JDK 5 1.2.3 配置环境变量 6 1.2.4 测试环境是否安装成功 8 1.2.5 如果失败了怎么办? 9 1.3 让自己的...
1.1.1 Java有什么优势? 2 1.1.2 Java在哪儿? 3 1.2 准备好开始Java之旅 3 1.2.1 下载JDK 4 1.2.2 安装JDK 5 1.2.3 配置环境变量 6 1.2.4 测试环境是否安装成功 8 1.2.5 如果失败了怎么办? 9 1.3 让自己的...
题目:判断101-200之间有多少个素数,并输出所有素数。 1.程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 【程序3】 题目:打印出所有的"水仙...
java经典算法题例。参赛必做。 【程序14】 题目:两个乒乓球队进行比赛,各出三人。...【程序30】写一个方法,用二分查找法判断任意整数在任意整数数组里面是否存在,若存在就返回它在数组中的索引位置,不存在返回-1
本书是第II卷,以开发人员在项目开发中经常遇到的问题和必须掌握的技术为中心,介绍了应用Java进行桌面程序开发各个方面的知识和技巧,主要包括Java语法与面向对象技术、Java高级应用、窗体与控件应用、文件操作...
对战一方落子后,在该处向8个方向检测连续的同类棋子,如果检测到直线方向上存在5 个连续的同类棋子(包含本位置棋子),则判断为"连五"并结束检测循环。基于检测结 果,可以判断游戏是否结束,并根据获胜方的落子...
对战一方落子后,在该处向8个方向检测连续的同类棋子,如果检测到直线方向上存在5 个连续的同类棋子(包含本位置棋子),则判断为"连五"并结束检测循环。基于检测结 果,可以判断游戏是否结束,并根据获胜方的落子...
【基础】Java中如何实现序列化,有什么意义? 34 【WEB】session与cookie的区别与联系;session的生命周期 34 session与cookie的区别与联系 34 session的生命周期 35 【WEB】servlet 生命周期 35 【WEB】阐述JDBC...
有向图 无向图 表示方法 邻接矩阵 邻接表 遍历 深度优先搜索 广度优先搜索 哈希表 哈希函数 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 随机数法 处理...
实验报告 实践报告 课程名称: Java语言程序设计 实验、实践名称:Java语言基础、数组和字符串编程、Java面向对象程序设计、J ava异常处理 多线程编程、图形用户界面编程 实验、实践地点: 致向楼301 专业班级: ...
目前市场业务中在产品以及其他项目的认证和检测方面存在诸多不便,用户需要实地考察并频繁与检测单位沟通,填写繁琐的纸质检测报告、当面送递样品,对于检测环节中存在的问题难以及时交互并处理。市场上相应的检测...
题目:判断101-200之间有多少个素数,并输出所有素数。 程序分析:判断素数的方法:用一个数分别去除2到sqrt(这个数),如果能被整除, 则表明此数不是素数,反之是素数。 public class lianxi02 { public static ...
弥补了朴素贝叶斯算法中必须要事件独立性的缺点,利用了贝叶斯网络的DAG有向无环图,允许各个事件保留一定的依赖关系,网络结构中的每个节点代表一种属性,边代表相应的条件概率值,通过计算从而能得到精准的分类...
3、在assign(executionContext)方法里,首先会判断task属性里是否存在swimlane,如果有的话,这个taskInstance就会分配给swimlane指定的ActorId或 PooledActors;如果不存在,再去找task属性里 assignmentDelegation...
1 逻辑类问题(A类)-指设计、编码中出现的计算正确性和一致性、程序逻辑控制等方面出现的问题,在系统中起关键作用,将导致软件死机、功能正常实现等严重问题; 接口类问题(B类)-指设计、编码中出现的函数和...
• sample41.htm 判断一个对象是否是另一个对象的原型对象 • sample42.htm 判断对象的属性是否可以被枚举 • sample43.htm 监视属性值的变化情况 第10章(\代码\第10章) • sample01....