content: /*
   * Licensed to the Apache Software Foundation (ASF) under one or more
   * contributor license agreements.  See the NOTICE file distributed with
   * this work for additional information regarding copyright ownership.
   * The ASF licenses this file to you under the Apache License, Version 2.0
   * (the "License"); you may not use this file except in compliance with
   * the License.  You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  package org.apache.calcite.util.graph;
  
  import java.util.ArrayList;
  import java.util.Collection;
  import java.util.HashSet;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Set;
  
  /**
   * Iterates over the vertices in a directed graph in depth-first order.
   *
   * @param <V> Vertex type
   * @param <E> Edge type
   */
  public class DepthFirstIterator<V, E extends DefaultEdge>
      implements Iterator<V> {
    private final Iterator<V> iterator;
  
    public DepthFirstIterator(DirectedGraph<V, E> graph, V start) {
      // Dumb implementation that builds the list first.
      iterator = buildList(graph, start).iterator();
    }
  
    private static <V, E extends DefaultEdge> List<V> buildList(
        DirectedGraph<V, E> graph, V start) {
      final List<V> list = new ArrayList<>();
      buildListRecurse(list, new HashSet<>(), graph, start);
      return list;
    }
  
    /** Creates an iterable over the vertices in the given graph in a depth-first
     * iteration order. */
    public static <V, E extends DefaultEdge> Iterable<V> of(
        DirectedGraph<V, E> graph, V start) {
      // Doesn't actually return a DepthFirstIterator, but a list with the same
      // contents, which is more efficient.
      return buildList(graph, start);
    }
  
    /** Populates a collection with the nodes reachable from a given node. */
    public static <V, E extends DefaultEdge> void reachable(Collection<V> list,
        final DirectedGraph<V, E> graph, final V start) {
      buildListRecurse(list, new HashSet<>(), graph, start);
    }
  
    private static <V, E extends DefaultEdge> void buildListRecurse(
        Collection<V> list, Set<V> activeVertices, DirectedGraph<V, E> graph,
        V start) {
      if (!activeVertices.add(start)) {
        return;
      }
      list.add(start);
      List<E> edges = graph.getOutwardEdges(start);
      for (E edge : edges) {
        //noinspection unchecked
        buildListRecurse(list, activeVertices, graph, (V) edge.target);
      }
      activeVertices.remove(start);
    }
  
    @Override public boolean hasNext() {
      return iterator.hasNext();
    }
  
    @Override public V next() {
      return iterator.next();
    }
  
    @Override public void remove() {
      throw new UnsupportedOperationException();
    }
  }
  