/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#include <iostream>

#include <fstream>

#include <string>

#include <vector>

#include <lemon/concept_check.h>

#include <lemon/concepts/heap.h>

#include <lemon/smart_graph.h>

#include <lemon/lgf_reader.h>

#include <lemon/dijkstra.h>

#include <lemon/maps.h>

#include <lemon/bin_heap.h>

#include "test_tools.h"

using namespace lemon;

using namespace lemon::concepts;

typedef ListDigraph Digraph;

DIGRAPH_TYPEDEFS(Digraph);

char test_lgf[] = 

  "@nodes\n" 

  "label\n"	

  "0\n"	

  "1\n"	

  "2\n"	

  "3\n"	

  "4\n"	

  "5\n"	

  "6\n"	

  "7\n"	

  "8\n"	

  "9\n"	

  "@arcs\n" 

  "		label	capacity\n"	

  "0	5	0	94\n"	

  "3	9	1	11\n"	

  "8	7	2	83\n"	

  "1	2	3	94\n"	

  "5	7	4	35\n"	

  "7	4	5	84\n"	

  "9	5	6	38\n"	

  "0	4	7	96\n"	

  "6	7	8	6\n"	

  "3	1	9	27\n"	

  "5	2	10	77\n"	

  "5	6	11	69\n"	

  "6	5	12	41\n"	

  "4	6	13	70\n"	

  "3	2	14	45\n"	

  "7	9	15	93\n"	

  "5	9	16	50\n"	

  "9	0	17	94\n"	

  "9	6	18	67\n"	

  "0	9	19	86\n"	

  "@attributes\n" 

  "source 3\n";

int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};

int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};

int test_len = sizeof(test_seq) / sizeof(test_seq[0]);

template <typename Heap>

void heapSortTest() {

  RangeMap<int> map(test_len, -1);

  Heap heap(map);

  std::vector<int> v(test_len);

  for (int i = 0; i < test_len; ++i) {

    v[i] = test_seq[i];

    heap.push(i, v[i]);

  }

  std::sort(v.begin(), v.end());

  for (int i = 0; i < test_len; ++i) {

    check(v[i] == heap.prio() ,"Wrong order in heap sort.");

    heap.pop();

  }

}

template <typename Heap>

void heapIncreaseTest() {

  RangeMap<int> map(test_len, -1);

  Heap heap(map);

  std::vector<int> v(test_len);

  for (int i = 0; i < test_len; ++i) {

    v[i] = test_seq[i];

    heap.push(i, v[i]);

  }

  for (int i = 0; i < test_len; ++i) {

    v[i] += test_inc[i];

    heap.increase(i, v[i]);

  }

  std::sort(v.begin(), v.end());

  for (int i = 0; i < test_len; ++i) {

    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");

    heap.pop();

  }

}

template <typename Heap>

void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length, 

		      Node source) {

  typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::

    Create dijkstra(digraph, length);

  dijkstra.run(source);

  for(ArcIt a(digraph); a != INVALID; ++a) {

    Node s = digraph.source(a); 

    Node t = digraph.target(a);

    if (dijkstra.reached(s)) {

      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],

      	     "Error in a shortest path tree!");

    }

  }

  for(NodeIt n(digraph); n != INVALID; ++n) {

    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {

      Arc a = dijkstra.predArc(n);

      Node s = digraph.source(a);

      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],

	     "Error in a shortest path tree!");

    }

  }

}

int main() {

  typedef int Item;

  typedef int Prio;

  typedef RangeMap<int> ItemIntMap;

  Digraph digraph;

  IntArcMap length(digraph);

  Node source;

  std::istringstream input(test_lgf);

  digraphReader(input, digraph).

    arcMap("capacity", length).

    node("source", source).

    run();  

  {

    typedef BinHeap<Prio, ItemIntMap> IntHeap;

    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();

    heapSortTest<IntHeap>();

    heapIncreaseTest<IntHeap>();

    typedef BinHeap<Prio, IntNodeMap > NodeHeap;

    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();

    dijkstraHeapTest<NodeHeap>(digraph, length, source);

  }

  return 0;

}