// -*- c++ -*-

 #include <iostream>

 #include <fstream>

 #include <vector>

 #include <lemon/concept_check.h>

 #include <lemon/bin_heap.h>

 #include <lemon/fib_heap.h>

 #include <lemon/radix_heap.h>

 #include <lemon/dimacs.h>

 #include "test_tools.h"

 #include "heap_test.h"

 #include "map_test.h"

 using namespace lemon;

 template <typename Item, typename Prio, typename ItemIntMap>

 class HeapConcept {

 public:  

   template <typename _Heap>

   struct Constraints {

   public:

     void constraints() {

       Item item;

       Prio prio;

       typedef typename _Heap::state_enum state_enum;

       state_enum state;

       _Heap heap1 = _Heap(map);

       heap.push(item, prio);

       prio = heap.prio();

       item = heap.top();

       heap.pop();

       heap.set(item, prio);

       heap.decrease(item, prio);

       heap.increase(item, prio);

       prio = heap[item];

       heap.erase(item);

       state = heap.state(item);

       state = _Heap::PRE_HEAP;

       state = _Heap::IN_HEAP;

       state = _Heap::POST_HEAP;

     }

     _Heap& heap;

     ItemIntMap& map;

   };

 };

 int main() {

   typedef int Item;

   typedef int Prio;

   typedef IntIntMap ItemIntMap;

   typedef ListGraph Graph;

   typedef Graph::Edge Edge;

   typedef Graph::Node Node;

   typedef Graph::EdgeIt EdgeIt;

   typedef Graph::NodeIt NodeIt;

   typedef Graph::EdgeMap<int> LengthMap;

   Graph graph;

   LengthMap length(graph);

   Node start;

   std::ifstream input("preflow_graph.dim");

   readDimacs(input, graph, length, start);  

   {

     std::cerr << "Checking Bin Heap" << std::endl;

     typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;

     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();

     heapSortTest<IntHeap>(20);

     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;

     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();

     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);

   }

   {

     std::cerr << "Checking Fib Heap" << std::endl;

     typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;

     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();

     heapSortTest<IntHeap>(20);

     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;

     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();

     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);

   }

   {

     std::cerr << "Checking Radix Heap" << std::endl;

     typedef RadixHeap<Item, ItemIntMap> IntHeap;

     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();

     heapSortTest<IntHeap>(20);

     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;

     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();

     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);

   }

   std::cout << __FILE__ ": All tests passed.\n";

   return 0;

 }