// -*- C++ -*- //

#ifndef LEMON_MA_ORDER_H

#define LEMON_MA_ORDER_H

#include <vector>

#include <functional>

#include <bin_heap.h>

namespace lemon {

  template <typename Graph, 

	    typename Heap = BinHeap<typename Graph::Node, int, 

				    typename Graph::NodeMap<int>, 

				    std::greater<int> >,

	    typename OrderVect = std::vector<typename Graph::Node> >

  class MAOrder {

    typedef typename Graph::Node Node;

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::Edge Edge;

    typedef typename Graph::OutEdgeIt OutEdgeIt;

    typedef typename Graph::NodeMap<int> NodeMapInt;

    const Graph& G;

    OrderVect& order;

  public:

    MAOrder(const Graph& _G, OrderVect& _order) : G(_G), order(_order) {}

    void run()

    {

      Node first;

      G.first(first);

      run(first);

    }

    void run(Node first)

    {

      NodeMapInt heapMap(G, -1);

      Heap heap(heapMap);

      heap.push(first, 0);

      NodeIt n;

      G.first(n);

      while ( G.valid(n) ) {

	while(!heap.empty()) {

	  Node a = heap.top();

	  heap.pop();

	  order.push_back(a);

	  OutEdgeIt e;

	  G.first(e,a);

	  for (;G.valid(e);G.next(e)) {

	    Node v = G.head(e); // hmm

	    if (heap.state(v) == Heap::IN_HEAP ) {

	      heap.decrease(v, heap[v]+1);

	    }

	    else if (heap.state(v) == Heap::PRE_HEAP) {

	      heap.push(v, 1);

	    }

	  }

	}

	while( G.valid(n) ) {

	  if (heap.state(n) == Heap::PRE_HEAP) {

	    heap.push(n,0);

	    break;

	  }

	  G.next(n);

	}

      }

    }

  };

} // namespace lemon

#endif // LEMON_MA_ORDER_H