001/*
002 * Copyright (c) 2007-2015 Concurrent, Inc. All Rights Reserved.
003 *
004 * Project and contact information: http://www.cascading.org/
005 *
006 * This file is part of the Cascading project.
007 *
008 * Licensed under the Apache License, Version 2.0 (the "License");
009 * you may not use this file except in compliance with the License.
010 * You may obtain a copy of the License at
011 *
012 *     http://www.apache.org/licenses/LICENSE-2.0
013 *
014 * Unless required by applicable law or agreed to in writing, software
015 * distributed under the License is distributed on an "AS IS" BASIS,
016 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017 * See the License for the specific language governing permissions and
018 * limitations under the License.
019 */
020
021package cascading.flow.planner.iso.finder;
022
023import java.util.Iterator;
024
025import cascading.flow.planner.graph.Extent;
026import org.jgrapht.DirectedGraph;
027import org.jgrapht.graph.EdgeReversedGraph;
028import org.jgrapht.traverse.BreadthFirstIterator;
029import org.jgrapht.traverse.DepthFirstIterator;
030import org.jgrapht.traverse.TopologicalOrderIterator;
031
032/**
033 *
034 */
035public enum SearchOrder
036  {
037    Depth, Breadth, Topological, ReverseDepth( true ), ReverseBreadth( true ), ReverseTopological( true );
038
039  final boolean isReversed;
040
041  SearchOrder()
042    {
043    isReversed = false;
044    }
045
046  SearchOrder( boolean isReversed )
047    {
048    this.isReversed = isReversed;
049    }
050
051  public boolean isReversed()
052    {
053    return isReversed;
054    }
055
056  public static <Node, Graph extends DirectedGraph> Iterator<Node> getNodeIterator( SearchOrder searchOrder, Graph graph )
057    {
058    if( searchOrder == null )
059      return new TopologicalOrderIterator( graph ); // faster than getVertexSet().iterator()
060
061    Node node = null;
062
063    if( graph.containsVertex( Extent.head ) )
064      {
065      if( !searchOrder.isReversed() )
066        node = (Node) Extent.head;
067      else
068        node = (Node) Extent.tail;
069      }
070
071    switch( searchOrder )
072      {
073      case Depth:
074        return new DepthFirstIterator( graph, node );
075      case Breadth:
076        return new BreadthFirstIterator( graph, node );
077      case Topological:
078        return new TopologicalOrderIterator( graph );
079      case ReverseDepth:
080        return new DepthFirstIterator( new EdgeReversedGraph( graph ), node );
081      case ReverseBreadth:
082        return new BreadthFirstIterator( new EdgeReversedGraph( graph ), node );
083      case ReverseTopological:
084        return new TopologicalOrderIterator( new EdgeReversedGraph( graph ) );
085      }
086
087    throw new IllegalStateException( "unknown order: " + searchOrder );
088    }
089  }