001/* 002 * Copyright (c) 2007-2017 Xplenty, 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.rule.util; 022 023import java.util.ArrayList; 024import java.util.List; 025import java.util.Set; 026 027import cascading.flow.planner.graph.ElementGraph; 028import cascading.util.Util; 029import org.jgrapht.EdgeFactory; 030import org.jgrapht.Graphs; 031import org.jgrapht.graph.SimpleDirectedGraph; 032 033/** 034 * 035 */ 036public class ResultTree 037 { 038 private final SimpleDirectedGraph<Delegate, Path> graph; 039 040 public static class Delegate 041 { 042 ElementGraph graph; 043 044 public Delegate( ElementGraph graph ) 045 { 046 this.graph = graph; 047 } 048 049 @Override 050 public boolean equals( Object object ) 051 { 052 if( this == object ) 053 return true; 054 055 Delegate delegate = (Delegate) object; 056 057 return graph == delegate.graph; 058 } 059 060 @Override 061 public int hashCode() 062 { 063 return System.identityHashCode( graph ); 064 } 065 } 066 067 public static class Path 068 { 069 int[] ordinals; 070 071 public Path( Path prior, int ordinal ) 072 { 073 int[] priorOrdinals = prior == null ? new int[]{} : prior.ordinals; 074 075 ordinals = new int[ priorOrdinals.length + 1 ]; 076 System.arraycopy( priorOrdinals, 0, ordinals, 0, priorOrdinals.length ); 077 ordinals[ priorOrdinals.length ] = ordinal; 078 } 079 080 public Path( int... ordinals ) 081 { 082 this.ordinals = ordinals; 083 } 084 085 public int[] getOrdinals() 086 { 087 return ordinals; 088 } 089 } 090 091 private static class PathFactory implements EdgeFactory<Delegate, Path> 092 { 093 ResultTree tree; 094 095 private PathFactory() 096 { 097 } 098 099 @Override 100 public Path createEdge( Delegate sourceVertex, Delegate targetVertex ) 101 { 102 Set<Path> paths = tree.graph.incomingEdgesOf( sourceVertex ); 103 104 if( paths.size() > 1 ) 105 throw new IllegalStateException( "too many incoming edges" ); 106 107 Path path = Util.getFirst( paths ); 108 109 return new Path( path, tree.graph.outDegreeOf( sourceVertex ) ); 110 } 111 } 112 113 public ResultTree() 114 { 115 graph = new SimpleDirectedGraph<>( new PathFactory() ); 116 117 ( (PathFactory) graph.getEdgeFactory() ).tree = this; 118 } 119 120 public void setChildren( ElementGraph parent, List<? extends ElementGraph> children ) 121 { 122 Delegate parentDelegate = new Delegate( parent ); 123 124 if( !graph.addVertex( parentDelegate ) ) 125 graph.removeAllVertices( Graphs.successorListOf( graph, parentDelegate ) ); 126 127 for( ElementGraph child : children ) 128 { 129 Delegate childDelegate = new Delegate( child ); 130 graph.addVertex( childDelegate ); 131 graph.addEdge( parentDelegate, childDelegate ); 132 } 133 } 134 135 public List<? extends ElementGraph> getChildren( ElementGraph parent ) 136 { 137 List<Delegate> delegates = Graphs.successorListOf( graph, new Delegate( parent ) ); 138 List<ElementGraph> results = new ArrayList<>(); 139 140 for( Delegate delegate : delegates ) 141 results.add( delegate.graph ); 142 143 return results; 144 } 145 146 public Path getEdge( ElementGraph parent, ElementGraph child ) 147 { 148 return graph.getEdge( new Delegate( parent ), new Delegate( child ) ); 149 } 150 151 public Path getIncomingEdge( ElementGraph parent ) 152 { 153 return Util.getFirst( graph.incomingEdgesOf( new Delegate( parent ) ) ); 154 } 155 }