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  }