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.misc;
29
30import java.util.*;
31
32/** A generic graph with edges; Each node as a single Object payload.
33 *  This is only used to topologically sort a list of file dependencies
34 *  at the moment.
35 */
36public class Graph {
37
38    public static class Node {
39        Object payload;
40        List<Node> edges; // points at which nodes?
41
42        public Node(Object payload) { this.payload = payload; }
43
44        public void addEdge(Node n) {
45            if ( edges==null ) edges = new ArrayList<Node>();
46            if ( !edges.contains(n) ) edges.add(n);
47        }
48
49        public String toString() { return payload.toString(); }
50    }
51
52    /** Map from node payload to node containing it */
53    protected Map<Object,Node> nodes = new HashMap<Object,Node>();
54
55    public void addEdge(Object a, Object b) {
56        //System.out.println("add edge "+a+" to "+b);
57        Node a_node = getNode(a);
58        Node b_node = getNode(b);
59        a_node.addEdge(b_node);
60    }
61
62    protected Node getNode(Object a) {
63        Node existing = nodes.get(a);
64        if ( existing!=null ) return existing;
65        Node n = new Node(a);
66        nodes.put(a, n);
67        return n;
68    }
69
70    /** DFS-based topological sort.  A valid sort is the reverse of
71     *  the post-order DFA traversal.  Amazingly simple but true.
72     *  For sorting, I'm not following convention here since ANTLR
73     *  needs the opposite.  Here's what I assume for sorting:
74     *
75     *    If there exists an edge u -> v then u depends on v and v
76     *    must happen before u.
77     *
78     *  So if this gives nonreversed postorder traversal, I get the order
79     *  I want.
80     */
81    public List<Object> sort() {
82        Set<Node> visited = new OrderedHashSet<Node>();
83        ArrayList<Object> sorted = new ArrayList<Object>();
84        while ( visited.size() < nodes.size() ) {
85            // pick any unvisited node, n
86            Node n = null;
87            for (Iterator it = nodes.values().iterator(); it.hasNext();) {
88                n = (Node)it.next();
89                if ( !visited.contains(n) ) break;
90            }
91            DFS(n, visited, sorted);
92        }
93        return sorted;
94    }
95
96    public void DFS(Node n, Set<Node> visited, ArrayList<Object> sorted) {
97        if ( visited.contains(n) ) return;
98        visited.add(n);
99        if ( n.edges!=null ) {
100            for (Iterator it = n.edges.iterator(); it.hasNext();) {
101                Node target = (Node) it.next();
102                DFS(target, visited, sorted);
103            }
104        }
105        sorted.add(n.payload);
106    }
107}