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