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 }