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

#ifndef HUGO_MA_ORDER_H
#define HUGO_MA_ORDER_H

#include <vector>
#include <functional>
#include <bin_heap.h>

namespace hugo {

  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 hugo

#endif // HUGO_MA_ORDER_H