// -*- 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