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 }