/*
 * Copyright 2012-present Facebook, Inc.
 *
 * Licensed 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 com.facebook.buck.graph;

import com.google.common.base.Preconditions;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Sets;

import java.util.Queue;
import java.util.Set;

/**
 * Class that performs a "bottom-up" traversal of a DAG. For any given node, every node to which it
 * has an outgoing edge will be visited before the given node.
 */
public abstract class AbstractBottomUpTraversal<T, V> {

  private final TraversableGraph<T> graph;

  private final Set<T> visitedNodes;

  private final Queue<T> nodesToExplore;

  public AbstractBottomUpTraversal(TraversableGraph<T> graph) {
    this.graph = Preconditions.checkNotNull(graph);
    this.visitedNodes = Sets.newHashSet();
    this.nodesToExplore = Lists.newLinkedList();
  }

  public final void traverse() {
    Iterables.addAll(nodesToExplore, graph.getNodesWithNoOutgoingEdges());
    while (!nodesToExplore.isEmpty()) {
      T node = nodesToExplore.remove();
      if (visitedNodes.contains(node)) {
        Preconditions.checkState(false,
            "The queue of nodes to explore should not contain a node that has already been"
            + " visited.");
      }

      visit(node);
      visitedNodes.add(node);

      // Only add a node to the set of nodes to be explored if all the nodes it depends on have
      // been visited already.
      for (T exploreCandidate : graph.getIncomingNodesFor(node)) {
        boolean hasUnexploredDependency = false;
        for (T dep : graph.getOutgoingNodesFor(exploreCandidate)) {
          if (!visitedNodes.contains(dep)) {
            hasUnexploredDependency = true;
            break;
          }
        }
        if (!hasUnexploredDependency) {
          nodesToExplore.add(exploreCandidate);
        }
      }
    }
  }

  public abstract void visit(T node);

  public abstract V getResult();

  protected TraversableGraph<T> getGraph() {
    return graph;
  }
}

@@ -763,16 +763,55 @@
 .Lists;%0A
+import com.google.common.collect.Maps;%0A
 import c
@@ -842,16 +842,38 @@
 .Sets;%0A%0A
+import java.util.Map;%0A
 import j
@@ -909,16 +909,66 @@
 til.Set;
+%0Aimport java.util.concurrent.atomic.AtomicInteger;
 %0A%0A/**%0A *
@@ -1313,16 +1313,161 @@
 plore;%0A%0A
+  // AtomicInteger is used to decrement the integer value in-place.%0A  private final Map%3CT, AtomicInteger%3E effectiveOutDegreesOfExplorableNodes;%0A%0A
   public
@@ -1666,16 +1666,83 @@
 List();%0A
+    this.effectiveOutDegreesOfExplorableNodes = Maps.newHashMap();%0A
   %7D%0A%0A  p
@@ -2316,143 +2316,309 @@
 ady.
-%0A      for (T exploreCandidate : graph.getIncomingNodesFor(node)) %7B%0A        boolean hasUnexploredDependency = false;%0A        for (T dep
+ We achieve the same by keeping track of the out degrees of explorable%0A      // nodes. After visiting a node, decrement the out degree of each of its parent node. When the%0A      // out degree reaches zero, it is safe to add that node to the list of nodes to explore next.%0A      for (T exploreCandidate
  : g
@@ -2625,21 +2625,21 @@
 raph.get
-Outgo
+Incom
 ingNodes
@@ -2642,31 +2642,19 @@
 odesFor(
-exploreCandidat
+nod
 e)) %7B%0A  
@@ -2663,166 +2663,350 @@
     
- 
- 
 if (!
-visitedNodes.contains(dep)) %7B%0A            hasUnexploredDependency = true;%0A            break;%0A          %7D%0A        %7D%0A        if (!hasUnexploredDependency
+effectiveOutDegreesOfExplorableNodes.containsKey(exploreCandidate)) %7B%0A          effectiveOutDegreesOfExplorableNodes.put(exploreCandidate,%0A              new AtomicInteger(Iterables.size(graph.getOutgoingNodesFor(exploreCandidate))));%0A        %7D%0A        if (effectiveOutDegreesOfExplorableNodes.get(exploreCandidate).decrementAndGet() == 0
 ) %7B%0A

Improve time complexity of `AbstractBottomUpTraversal`.