001    /*
002     *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003     *
004     *  This file is licensed to You under the Eclipse Public License (EPL);
005     *  You may not use this file except in compliance with the License. You
006     *  may obtain a copy of the License at
007     *
008     *      http://www.opensource.org/licenses/eclipse-1.0.php
009     *
010     *  See the COPYRIGHT.txt file distributed with this work for information
011     *  regarding copyright ownership.
012     */
013    package org.jikesrvm.compilers.opt.util;
014    
015    import java.util.Enumeration;
016    
017    
018    /**
019     * This class implements miscellaneous utilities for graphs.
020     */
021    public class GraphUtilities {
022    
023      /**
024       * Return an enumeration of the nodes, or a subset of the nodes, in an
025       * acyclic graph in topological order. <p>
026       *
027       * Note: if G is cyclic, results are undefined
028       */
029      public static Enumeration<GraphNode> enumerateTopSort(Graph G) {
030        return enumerateTopSort(G, G.enumerateNodes());
031      }
032    
033      public static Enumeration<GraphNode> enumerateTopSort(Graph G, Enumeration<GraphNode> ie) {
034        return enumerateTopSortInternal(G, new DFSenumerateByFinish(G, ie));
035      }
036    
037      public static Enumeration<GraphNode> enumerateTopSort(Graph G, Enumeration<GraphNode> ie,
038                                                              GraphEdgeFilter f) {
039        return enumerateTopSortInternal(G, new FilteredDFSenumerateByFinish(G, ie, f));
040      }
041    
042      private static Enumeration<GraphNode> enumerateTopSortInternal(Graph G, Enumeration<GraphNode> e) {
043        final GraphNode[] elts = new GraphNode[G.numberOfNodes()];
044    
045        int i = 0;
046        while (e.hasMoreElements()) {
047          elts[i++] = e.nextElement();
048        }
049    
050        final int i1 = i;
051    
052        return new GraphNodeEnumerator() {
053          private int top = i1;
054    
055          @Override
056          public boolean hasMoreElements() {
057            return top > 0;
058          }
059    
060          @Override
061          public GraphNode nextElement() {
062            return elts[--top];
063          }
064        };
065      }
066    }