/// \ingroup auxdat

   ///

   /// \brief A Simplified Bucket Heap implementation.

   ///

   /// This class implements a simplified \e bucket \e heap data

   /// structure.  It does not provide some functionality but it faster

   /// and simplier data structure than the BucketHeap. The main

   /// difference is that the BucketHeap stores for every key a double

   /// linked list while this class stores just simple lists. In the

   /// other way it does not supports erasing each elements just the

   /// minimal and it does not supports key increasing, decreasing.

   ///

   /// \param _Item Type of the items to be stored.  

   /// \param _ItemIntMap A read and writable Item int map, used internally

   /// to handle the cross references.

   /// \param minimize If the given parameter is true then the heap gives back

   /// the lowest priority.

   ///

   /// \sa BucketHeap 

   template <typename _Item, typename _ItemIntMap, bool minimize = true >

   class SimpleBucketHeap {

   public:

     typedef _Item Item;

     typedef int Prio;

     typedef std::pair<Item, Prio> Pair;

     typedef _ItemIntMap ItemIntMap;

     /// \brief Type to represent the items states.

     ///

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

     /// "pre heap" or "post heap". The latter two are indifferent from the

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

     ///

     /// The ItemIntMap \e should be initialized in such way that it maps

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

     enum state_enum {

       IN_HEAP = 0,

       PRE_HEAP = -1,

       POST_HEAP = -2

     };

   public:

     /// \brief The constructor.

     ///

     /// The constructor.

     /// \param _index should be given to the constructor, since it is used

     /// internally to handle the cross references. The value of the map

     /// should be PRE_HEAP (-1) for each element.

     explicit SimpleBucketHeap(ItemIntMap &_index) 

       : index(_index), free(-1), num(0), minimal(0) {}

     /// \brief Returns the number of items stored in the heap.

     ///

     /// The number of items stored in the heap.

     int size() const { return num; }

     /// \brief Checks if the heap stores no items.

     ///

     /// Returns \c true if and only if the heap stores no items.

     bool empty() const { return num == 0; }

     /// \brief Make empty this heap.

     /// 

     /// Make empty this heap. It does not change the cross reference

     /// map.  If you want to reuse a heap what is not surely empty you

     /// should first clear the heap and after that you should set the

     /// cross reference map for each item to \c PRE_HEAP.

     void clear() { 

       data.clear(); first.clear(); free = -1; num = 0; minimal = 0;

     }

     /// \brief Insert a pair of item and priority into the heap.

     ///

     /// Adds \c p.first to the heap with priority \c p.second.

     /// \param p The pair to insert.

     void push(const Pair& p) {

       push(p.first, p.second);

     }

     /// \brief Insert an item into the heap with the given priority.

     ///    

     /// Adds \c i to the heap with priority \c p. 

     /// \param i The item to insert.

     /// \param p The priority of the item.

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

       int idx;

       if (free == -1) {

         idx = data.size();

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

       } else {

         idx = free;

         free = data[idx].next;

         data[idx].item = i; data[idx].value = p;

       }

       index[i] = idx;

       if (p >= (int)first.size()) first.resize(p + 1, -1);

       data[idx].next = first[p];

       first[p] = idx;

       if (p < minimal) {

 	minimal = p;

       }

       ++num;

     }

     /// \brief Returns the item with minimum priority.

     ///

     /// This method returns the item with minimum priority.

     /// \pre The heap must be nonempty.  

     Item top() const {

       while (first[minimal] == -1) {

 	++minimal;

       }

       return data[first[minimal]].item;

     }

     /// \brief Returns the minimum priority.

     ///

     /// It returns the minimum priority.

     /// \pre The heap must be nonempty.

     Prio prio() const {

       while (first[minimal] == -1) {

 	++minimal;

       }

       return minimal;

     }

     /// \brief Deletes the item with minimum priority.

     ///

     /// This method deletes the item with minimum priority from the heap.  

     /// \pre The heap must be non-empty.  

     void pop() {

       while (first[minimal] == -1) {

 	++minimal;

       }

       int idx = first[minimal];

       index[data[idx].item] = -2;

       first[minimal] = data[idx].next;

       data[idx].next = free;

       free = idx;

       --num;

     }

     /// \brief Returns the priority of \c i.

     ///

     /// This function returns the priority of item \c i.  

     /// \pre \c i must be in the heap.

     /// \param i The item.

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

       int idx = index[i];

       return data[idx].value;

     }

     /// \brief Returns if \c item is in, has already been in, or has 

     /// never been in the heap.

     ///

     /// This method returns PRE_HEAP if \c item has never been in the

     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP

     /// otherwise. In the latter case it is possible that \c item will

     /// get back to the heap again.

     /// \param i The item.

     state_enum state(const Item &i) const {

       int idx = index[i];

       if (idx >= 0) idx = 0;

       return state_enum(idx);

     }

   private:

     struct BucketItem {

       BucketItem(const Item& _item, int _value) 

 	: item(_item), value(_value) {}

       Item item;

       int value;

       int next;

     };

     ItemIntMap& index;

     std::vector<int> first;

     std::vector<BucketItem> data;

     int free, num;

     mutable int minimal;

   }; // class SimpleBucketHeap

   template <typename _Item, typename _ItemIntMap>

   class SimpleBucketHeap<_Item, _ItemIntMap, false> {

   public:

     typedef _Item Item;

     typedef int Prio;

     typedef std::pair<Item, Prio> Pair;

     typedef _ItemIntMap ItemIntMap;

     enum state_enum {

       IN_HEAP = 0,

       PRE_HEAP = -1,

       POST_HEAP = -2

     };

   public:

     explicit SimpleBucketHeap(ItemIntMap &_index) 

       : index(_index), free(-1), num(0), maximal(0) {}

     int size() const { return num; }

     bool empty() const { return num == 0; }

     void clear() { 

       data.clear(); first.clear(); free = -1; num = 0; maximal = 0;

     }

     void push(const Pair& p) {

       push(p.first, p.second);

     }

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

       int idx;

       if (free == -1) {

         idx = data.size();

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

       } else {

         idx = free;

         free = data[idx].next;

         data[idx].item = i; data[idx].value = p;

       }

       index[i] = idx;

       if (p >= (int)first.size()) first.resize(p + 1, -1);

       data[idx].next = first[p];

       first[p] = idx;

       if (p > maximal) {

 	maximal = p;

       }

       ++num;

     }

     Item top() const {

       while (first[maximal] == -1) {

 	--maximal;

       }

       return data[first[maximal]].item;

     }

     Prio prio() const {

       while (first[maximal] == -1) {

 	--maximal;

       }

       return maximal;

     }

     void pop() {

       while (first[maximal] == -1) {

 	--maximal;

       }

       int idx = first[maximal];

       index[data[idx].item] = -2;

       first[maximal] = data[idx].next;

       data[idx].next = free;

       free = idx;

       --num;

     }

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

       int idx = index[i];

       return data[idx].value;

     }

     state_enum state(const Item &i) const {

       int idx = index[i];

       if (idx >= 0) idx = 0;

       return state_enum(idx);

     }

   private:

     struct BucketItem {

       BucketItem(const Item& _item, int _value) 

 	: item(_item), value(_value) {}

       Item item;

       int value;

       int next;

     };

     ItemIntMap& index;

     std::vector<int> first;

     std::vector<BucketItem> data;

     int free, num;

     mutable int maximal;

   };