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    
016    /**
017     * This class implements miscellaneous utilities for graphs.
018     */
019    public class GraphUtilities {
020    
021      /**
022       * Return an enumeration of the nodes, or a subset of the nodes, in an
023       * acyclic graph in topological order .
024       *
025       * Note: if G is cyclic, results are undefined
026       */
027      public static GraphNodeEnumeration enumerateTopSort(Graph G) {
028        return enumerateTopSort(G, G.enumerateNodes());
029      }
030    
031      public static GraphNodeEnumeration enumerateTopSort(Graph G, GraphNodeEnumeration ie) {
032        return enumerateTopSortInternal(G, new DFSenumerateByFinish(G, ie));
033      }
034    
035      public static GraphNodeEnumeration enumerateTopSort(Graph G, GraphNodeEnumeration ie,
036                                                              GraphEdgeFilter f) {
037        return enumerateTopSortInternal(G, new FilteredDFSenumerateByFinish(G, ie, f));
038      }
039    
040      private static GraphNodeEnumeration enumerateTopSortInternal(Graph G, GraphNodeEnumeration e) {
041        final GraphNode[] elts = new GraphNode[G.numberOfNodes()];
042    
043        int i = 0;
044        while (e.hasMoreElements()) {
045          elts[i++] = e.next();
046        }
047    
048        final int i1 = i;
049    
050        return new GraphNodeEnumerator() {
051          private int top = i1;
052    
053          public boolean hasMoreElements() {
054            return top > 0;
055          }
056    
057          public GraphNode next() {
058            return elts[--top];
059          }
060        };
061      }
062    }