TestTopologicalSort.java revision 324c4644fee44b9898524c09511bd33c3f12e2df 
1/*
2 * [The "BSD license"]
3 *  Copyright (c) 2010 Terence Parr
4 *  All rights reserved.
5 *
6 *  Redistribution and use in source and binary forms, with or without
7 *  modification, are permitted provided that the following conditions
8 *  are met:
9 *  1. Redistributions of source code must retain the above copyright
10 *      notice, this list of conditions and the following disclaimer.
11 *  2. Redistributions in binary form must reproduce the above copyright
12 *      notice, this list of conditions and the following disclaimer in the
13 *      documentation and/or other materials provided with the distribution.
14 *  3. The name of the author may not be used to endorse or promote products
15 *      derived from this software without specific prior written permission.
16 *
17 *  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 *  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 *  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 *  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 *  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 *  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 *  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 *  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 *  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28package org.antlr.test;
29
30import org.antlr.misc.Graph;
31import org.junit.Test;
32
33import java.util.List;
34
35/** Test topo sort in GraphNode. */
36public class TestTopologicalSort extends BaseTest {
37    @Test
38    public void testFairlyLargeGraph() throws Exception {
39        Graph g = new Graph();
40        g.addEdge("C", "F");
41        g.addEdge("C", "G");
42        g.addEdge("C", "A");
43        g.addEdge("C", "B");
44        g.addEdge("A", "D");
45        g.addEdge("A", "E");
46        g.addEdge("B", "E");
47        g.addEdge("D", "E");
48        g.addEdge("D", "F");
49        g.addEdge("F", "H");
50        g.addEdge("E", "F");
51
52        String expecting = "[H, F, E, D, G, A, B, C]";
53        List nodes = g.sort();
54        String result = nodes.toString();
55        assertEquals(expecting, result);
56    }
57
58    @Test
59    public void testCyclicGraph() throws Exception {
60        Graph g = new Graph();
61        g.addEdge("A", "B");
62        g.addEdge("B", "C");
63        g.addEdge("C", "A");
64        g.addEdge("C", "D");
65
66        String expecting = "[D, C, B, A]";
67        List nodes = g.sort();
68        String result = nodes.toString();
69        assertEquals(expecting, result);
70    }
71
72    @Test
73    public void testRepeatedEdges() throws Exception {
74        Graph g = new Graph();
75        g.addEdge("A", "B");
76        g.addEdge("B", "C");
77        g.addEdge("A", "B"); // dup
78        g.addEdge("C", "D");
79
80        String expecting = "[D, C, B, A]";
81        List nodes = g.sort();
82        String result = nodes.toString();
83        assertEquals(expecting, result);
84    }
85
86    @Test
87    public void testSimpleTokenDependence() throws Exception {
88        Graph g = new Graph();
89        g.addEdge("Java.g", "MyJava.tokens"); // Java feeds off manual token file
90        g.addEdge("Java.tokens", "Java.g");
91        g.addEdge("Def.g", "Java.tokens");    // walkers feed off generated tokens
92        g.addEdge("Ref.g", "Java.tokens");
93
94        String expecting = "[MyJava.tokens, Java.g, Java.tokens, Ref.g, Def.g]";
95        List nodes = g.sort();
96        String result = nodes.toString();
97        assertEquals(expecting, result);
98    }
99
100    @Test
101    public void testParserLexerCombo() throws Exception {
102        Graph g = new Graph();
103        g.addEdge("JavaLexer.tokens", "JavaLexer.g");
104        g.addEdge("JavaParser.g", "JavaLexer.tokens");
105        g.addEdge("Def.g", "JavaLexer.tokens");
106        g.addEdge("Ref.g", "JavaLexer.tokens");
107
108        String expecting = "[JavaLexer.g, JavaLexer.tokens, JavaParser.g, Ref.g, Def.g]";
109        List nodes = g.sort();
110        String result = nodes.toString();
111        assertEquals(expecting, result);
112    }
113}
114