source: lemon-0.x/src/test/heap_test.cc @ 1206:9c398137c2cb

// -*- c++ -*-

#include <iostream>
#include <fstream>
#include <vector>

#include <lemon/concept_check.h>

#include <lemon/smart_graph.h>

#include <lemon/graph_reader.h>

#include <lemon/bin_heap.h>
#include <lemon/fib_heap.h>
#include <lemon/radix_heap.h>

#include "test_tools.h"

#include "heap_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;

      ignore_unused_variable_warning(item);
      ignore_unused_variable_warning(prio);

      typedef typename _Heap::state_enum state_enum;
      state_enum state;

      ignore_unused_variable_warning(state);
      
      _Heap heap1 = _Heap(map);

      ignore_unused_variable_warning(heap1);
      
      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;

  /// \todo create own test graph
  std::ifstream input("dijkstra_test.lemon");
  readGraph(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>(100);
    heapIncreaseTest<IntHeap>(100);
    
    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>(100);
    heapIncreaseTest<IntHeap>(100);

    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>(100);
    heapIncreaseTest<IntHeap>(100);

    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;
}