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

}