/* -*- C++ -*-

  * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Combinatorial Optimization Research Group, 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.

  *

  */

 #ifndef LEMON_RADIX_HEAP_H

 #define LEMON_RADIX_HEAP_H

 ///\ingroup auxdat

 ///\file

 ///\brief Radix Heap implementation.

 ///\todo It should be documented.

 #include <vector>

 #include <lemon/error.h>

 namespace lemon {

   /// \addtogroup auxdat

   /// @{

   /// A Radix Heap implementation.

   ///\todo Please document...

   ///

   ///\sa BinHeap

   ///\sa Dijkstra

   class UnderFlowPriorityException : public RuntimeError {

   public:

     virtual const char* exceptionName() const {

       return "lemon::UnderFlowPriorityException";

     }  

   };

   template <typename _Item, typename _ItemIntMap>

   class RadixHeap {

   public:

     typedef _Item Item;

     // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...

     typedef int Prio;

     typedef _ItemIntMap ItemIntMap;

     /**

      * Each Item element have a state associated to it. It may be "in heap",

      * "pre heap" or "post heap". The later two are indifferent from the

      * heap's point of view, but may be useful to the user.

      *

      * The ItemIntMap _should_ be initialized in such way, that it maps

      * PRE_HEAP (-1) to any element to be put in the heap...

      */

     ///\todo it is used nowhere

     ///

     enum state_enum {

       IN_HEAP = 0,

       PRE_HEAP = -1,

       POST_HEAP = -2

     };

   private:

     struct RadixItem {

       int prev, next, box;

       Item item;

       int prio;

       RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}

     };

     struct RadixBox {

       int first;

       int min, size;

       RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}

     };

     std::vector<RadixItem> data;

     std::vector<RadixBox> boxes;

     ItemIntMap &iim;

   public:

     ///\e

     explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {

       boxes.push_back(RadixBox(0, 1));

       boxes.push_back(RadixBox(1, 1));

     }

     ///\e

     RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {

       boxes.push_back(RadixBox(0, 1));

       boxes.push_back(RadixBox(1, 1));

       while (upper(boxes.back(), capacity)) {

 	extend();

       }

     }

     ///\e

     int size() const { return data.size(); }

     ///\e

     bool empty() const { return data.empty(); }

   private:

     bool upper(int box, Prio prio) {

       return prio < boxes[box].min;

     }

     bool lower(int box, Prio prio) {

       return prio >= boxes[box].min + boxes[box].size;

     }

     /// \brief Remove item from the box list.

     void remove(int index) {

       if (data[index].prev >= 0) {

 	data[data[index].prev].next = data[index].next;

       } else {

 	boxes[data[index].box].first = data[index].next;

       }

       if (data[index].next >= 0) {

 	data[data[index].next].prev = data[index].prev;

       }

     }

     /// \brief Insert item into the box list.

     void insert(int box, int index) {

       if (boxes[box].first == -1) {

 	boxes[box].first = index;

 	data[index].next = data[index].prev = -1;

       } else {

 	data[index].next = boxes[box].first;

 	data[boxes[box].first].prev = index;

 	data[index].prev = -1;

 	boxes[box].first = index;

       }

       data[index].box = box;

     }

     /// \brief Add a new box to the box list.

     void extend() {

       int min = boxes.back().min + boxes.back().size;

       int size = 2 * boxes.back().size;

       boxes.push_back(RadixBox(min, size));

     }

     /// \brief Move an item up into the proper box.

     void bubble_up(int index) {

       if (!lower(data[index].box, data[index].prio)) return;

       remove(index);

       int box = findUp(data[index].box, data[index].prio);

       insert(box, index);      

     }

     /// \brief Find up the proper box for the item with the given prio.

     int findUp(int start, int prio) {

       while (lower(start, prio)) {

 	if (++start == (int)boxes.size()) {

 	  extend();

 	}

       }

       return start;

     }

     /// \brief Move an item down into the proper box.

     void bubble_down(int index) {

       if (!upper(data[index].box, data[index].prio)) return;

       remove(index);

       int box = findDown(data[index].box, data[index].prio);

       insert(box, index);

     }

     /// \brief Find up the proper box for the item with the given prio.

     int findDown(int start, int prio) {

       while (upper(start, prio)) {

 	if (--start < 0) throw UnderFlowPriorityException();

       }

       return start;

     }

     /// \brief Find the first not empty box.

     int findFirst() {

       int first = 0;

       while (boxes[first].first == -1) ++first;

       return first;

     }

     /// \brief Gives back the minimal prio of the box.

     int minValue(int box) {

       int min = data[boxes[box].first].prio;

       for (int k = boxes[box].first; k != -1; k = data[k].next) {

 	if (data[k].prio < min) min = data[k].prio;

       }

       return min;

     }

     /// \brief Rearrange the items of the heap and makes the 

     /// first box not empty.

     void moveDown() {

       //      print(); printf("moveDown\n"); fflush(stdout);       

       int box = findFirst();

       if (box == 0) return;

       int min = minValue(box);

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

 	boxes[i].min = min;

 	min += boxes[i].size;

       }

       int curr = boxes[box].first, next;

       while (curr != -1) {

 	next = data[curr].next;

 	bubble_down(curr);

 	curr = next;

       }      

     }

     void relocate_last(int index) {

       if (index != (int)data.size() - 1) {

 	data[index] = data.back();

 	if (data[index].prev != -1) {

 	  data[data[index].prev].next = index;

 	} else {

 	  boxes[data[index].box].first = index;

 	}

 	if (data[index].next != -1) {

 	  data[data[index].next].prev = index;

 	}

 	iim[data[index].item] = index;

       }

       data.pop_back();

     }

   public:

     ///\e

     void push(const Item &i, const Prio &p) {

       fflush(stdout);

       int n = data.size();

       iim.set(i, n);

       data.push_back(RadixItem(i, p));

       while (lower(boxes.size() - 1, p)) {

 	extend();

       }

       int box = findDown(boxes.size() - 1, p);

       insert(box, n);

       //      printf("Push %d\n", p);

       //print();

     }

     ///\e

     Item top() const {

       //      print(); printf("top\n");  fflush(stdout);

       const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();

       return data[boxes[0].first].item;

       //      print(); printf("top_end\n");  fflush(stdout);

     }

     /// Returns the prio of the top element of the heap.

     Prio prio() const {

       //      print(); printf("prio\n"); fflush(stdout);

       const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();

       return data[boxes[0].first].prio;

      }

     ///\e

     void pop() {

       //      print(); printf("pop\n"); fflush(stdout);

       moveDown();

       int index = boxes[0].first;

       iim[data[index].item] = POST_HEAP;

       remove(index);

       relocate_last(index);

       //      printf("Pop \n");

       //print();

     }

     ///\e

     void erase(const Item &i) {

       int index = iim[i];

       iim[i] = POST_HEAP;

       remove(index);

       relocate_last(index);

    }

     ///\e

     Prio operator[](const Item &i) const {

       int idx = iim[i];

       return data[idx].prio;

     }

     ///\e

     void set(const Item &i, const Prio &p) {

       int idx = iim[i];

       if( idx < 0 ) {

 	push(i, p);

       }

       else if( p >= data[idx].prio ) {

 	data[idx].prio = p;

 	bubble_up(idx);

       } else {

 	data[idx].prio = p;

 	bubble_down(idx);

       }

     }

     ///\e

     void decrease(const Item &i, const Prio &p) {

       //      print(); printf("decrease\n"); fflush(stdout);

       int idx = iim[i];

       data[idx].prio = p;

       bubble_down(idx);

     }

     ///\e

     void increase(const Item &i, const Prio &p) {

       int idx = iim[i];

       data[idx].prio = p;

       bubble_up(idx);

     }

     ///\e

     state_enum state(const Item &i) const {

       int s = iim[i];

       if( s >= 0 ) s = 0;

       return state_enum(s);

     }

 //     void print() const {

 //       for (int i = 0; i < boxes.size(); ++i) {

 // 	printf("(%d, %d) ", boxes[i].min, boxes[i].size);

 // 	for (int k = boxes[i].first; k != -1; k = data[k].next) {

 // 	  printf("%d ", data[k].prio);

 // 	}

 // 	printf("\n");

 //       }

 //       fflush(stdout);

 //     }

   }; // class RadixHeap

   ///@}

 } // namespace lemon

 #endif // LEMON_RADIX_HEAP_H