deba@1187: // -*- c++ -*-
deba@1187: 
deba@1187: #include <iostream>
deba@1187: #include <fstream>
deba@1187: #include <vector>
deba@1187: 
deba@1187: #include <lemon/concept_check.h>
deba@1187: 
deba@1187: #include <lemon/bin_heap.h>
deba@1187: #include <lemon/fib_heap.h>
deba@1187: #include <lemon/radix_heap.h>
deba@1187: 
deba@1187: #include <lemon/dimacs.h>
deba@1187: 
deba@1187: #include "test_tools.h"
deba@1187: #include "heap_test.h"
deba@1187: #include "map_test.h"
deba@1187: 
deba@1187: 
deba@1187: using namespace lemon;
deba@1187: 
deba@1187: template <typename Item, typename Prio, typename ItemIntMap>
deba@1187: class HeapConcept {
deba@1187: public:  
deba@1187: 
deba@1187:   template <typename _Heap>
deba@1187:   struct Constraints {
deba@1187:   public:
deba@1187:     
deba@1187:     void constraints() {
deba@1187:       Item item;
deba@1187:       Prio prio;
deba@1187: 
deba@1187:       typedef typename _Heap::state_enum state_enum;
deba@1187:       state_enum state;
deba@1187:       
deba@1187:       _Heap heap1 = _Heap(map);
deba@1187:       
deba@1187:       heap.push(item, prio);
deba@1187: 
deba@1187:       prio = heap.prio();
deba@1187:       item = heap.top();
deba@1187: 
deba@1187:       heap.pop();
deba@1187: 
deba@1187:       heap.set(item, prio);
deba@1187:       heap.decrease(item, prio);
deba@1187:       heap.increase(item, prio);
deba@1187:       prio = heap[item];
deba@1187: 
deba@1187:       heap.erase(item);
deba@1187: 
deba@1187:       state = heap.state(item);
deba@1187: 
deba@1187:       state = _Heap::PRE_HEAP;
deba@1187:       state = _Heap::IN_HEAP;
deba@1187:       state = _Heap::POST_HEAP;
deba@1187:     }
deba@1187:     
deba@1187:     _Heap& heap;
deba@1187:     ItemIntMap& map;
deba@1187:   };
deba@1187: };
deba@1187: 
deba@1187: int main() {
deba@1187: 
deba@1187:   typedef int Item;
deba@1187:   typedef int Prio;
deba@1187:   typedef IntIntMap ItemIntMap;
deba@1187: 
deba@1187:   typedef ListGraph Graph;
deba@1187: 
deba@1187:   typedef Graph::Edge Edge;
deba@1187:   typedef Graph::Node Node;
deba@1187:   typedef Graph::EdgeIt EdgeIt;
deba@1187:   typedef Graph::NodeIt NodeIt;
deba@1187:   typedef Graph::EdgeMap<int> LengthMap;
deba@1187: 
deba@1187:   Graph graph;
deba@1187:   LengthMap length(graph);
deba@1187:   Node start;
deba@1187: 
deba@1187:   std::ifstream input("preflow_graph.dim");
deba@1187:   readDimacs(input, graph, length, start);  
deba@1187:  
deba@1187:   {
deba@1187:     std::cerr << "Checking Bin Heap" << std::endl;
deba@1187: 
deba@1187:     typedef BinHeap<Item, Prio, ItemIntMap> IntHeap;
deba@1187:     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
deba@1187:     heapSortTest<IntHeap>(20);
deba@1187:     
deba@1187:     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
deba@1187:     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1187:     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1187:   }
deba@1187:   {
deba@1187:     std::cerr << "Checking Fib Heap" << std::endl;
deba@1187: 
deba@1187:     typedef FibHeap<Item, Prio, ItemIntMap> IntHeap;
deba@1187:     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
deba@1187:     heapSortTest<IntHeap>(20);
deba@1187: 
deba@1187:     typedef FibHeap<Node, Prio, Graph::NodeMap<int> > NodeHeap;
deba@1187:     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1187:     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1187:   }
deba@1187:   {
deba@1187:     std::cerr << "Checking Radix Heap" << std::endl;
deba@1187: 
deba@1187:     typedef RadixHeap<Item, ItemIntMap> IntHeap;
deba@1187:     checkConcept<HeapConcept<Item, Prio, ItemIntMap>, IntHeap>();
deba@1187:     heapSortTest<IntHeap>(20);
deba@1187: 
deba@1187:     typedef RadixHeap<Node, Graph::NodeMap<int> > NodeHeap;
deba@1187:     checkConcept<HeapConcept<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
deba@1187:     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);
deba@1187:   }
deba@1187: 
deba@1187:   std::cout << __FILE__ ": All tests passed.\n";
deba@1187: 
deba@1187:   return 0;
deba@1187: }