/* -*- mode: C++; indent-tabs-mode: nil; -*-

 /* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  *

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

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

  *

  *

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

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

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

  *

  *

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

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

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

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

       /// \c PRE_HEAP (<tt>-1</tt>) for each item.

       /// \c PRE_HEAP (<tt>-1</tt>) for each item.

 #ifdef DOXYGEN

 #ifdef DOXYGEN

       explicit Heap(ItemIntMap &map) {}

       explicit Heap(ItemIntMap &map) {}

 #else

 #else

       explicit Heap(ItemIntMap&) {}

       explicit Heap(ItemIntMap&) {}

       /// \brief Constructor.

       /// \brief Constructor.

       ///

       ///

       /// Constructor.

       /// Constructor.

       /// \param map A map that assigns \c int values to keys of type

       /// \param map A map that assigns \c int values to keys of type

       /// \param comp The function object used for comparing the priorities.

       /// \param comp The function object used for comparing the priorities.

 #ifdef DOXYGEN

 #ifdef DOXYGEN

       explicit Heap(ItemIntMap &map, const CMP &comp) {}

       explicit Heap(ItemIntMap &map, const CMP &comp) {}

 #else

 #else

       explicit Heap(ItemIntMap&, const CMP&) {}

       explicit Heap(ItemIntMap&, const CMP&) {}

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

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

       ///

       ///

       /// This function returns the number of items stored in the heap.

       /// This function returns the number of items stored in the heap.

       int size() const { return 0; }

       int size() const { return 0; }

       /// \pre \e i must not be stored in the heap.

       /// \pre \e i must not be stored in the heap.

 #ifdef DOXYGEN

 #ifdef DOXYGEN

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

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

 #else

 #else

       void push(const Item&, const Prio&) {}

       void push(const Item&, const Prio&) {}

       /// \brief Return the item having minimum priority.

       /// \brief Return the item having minimum priority.

       ///

       ///

       /// This function returns the item having minimum priority.

       /// This function returns the item having minimum priority.

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

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

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

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

 #ifdef DOXYGEN

 #ifdef DOXYGEN

       void erase(const Item &i) {}

       void erase(const Item &i) {}

 #else

 #else

       void erase(const Item&) {}

       void erase(const Item&) {}

       /// \brief The priority of the given item.

       /// \brief The priority of the given item.

       ///

       ///

       /// This function returns the priority of the given item.

       /// This function returns the priority of the given item.

       /// \param i The item.

       /// \param i The item.

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

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

 #ifdef DOXYGEN

 #ifdef DOXYGEN

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

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

 #else

 #else

       Prio operator[](const Item&) const { return Prio(); }

       Prio operator[](const Item&) const { return Prio(); }

       /// \brief Set the priority of an item or insert it, if it is

       /// \brief Set the priority of an item or insert it, if it is

       /// not stored in the heap.

       /// not stored in the heap.

       ///

       ///

       /// This method sets the priority of the given item if it is

       /// This method sets the priority of the given item if it is

       /// \param p The priority.

       /// \param p The priority.

 #ifdef DOXYGEN

 #ifdef DOXYGEN

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

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

 #else

 #else

       void set(const Item&, const Prio&) {}

       void set(const Item&, const Prio&) {}

       /// \brief Decrease the priority of an item to the given value.

       /// \brief Decrease the priority of an item to the given value.

       ///

       ///

       /// This function decreases the priority of an item to the given value.

       /// This function decreases the priority of an item to the given value.

       /// \param i The item.

       /// \param i The item.

       /// \pre \e i must be stored in the heap with priority at least \e p.

       /// \pre \e i must be stored in the heap with priority at least \e p.

 #ifdef DOXYGEN

 #ifdef DOXYGEN

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

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

 #else

 #else

       void decrease(const Item&, const Prio&) {}

       void decrease(const Item&, const Prio&) {}

       /// \brief Increase the priority of an item to the given value.

       /// \brief Increase the priority of an item to the given value.

       ///

       ///

       /// This function increases the priority of an item to the given value.

       /// This function increases the priority of an item to the given value.

       /// \param i The item.

       /// \param i The item.

       /// \pre \e i must be stored in the heap with priority at most \e p.

       /// \pre \e i must be stored in the heap with priority at most \e p.

 #ifdef DOXYGEN

 #ifdef DOXYGEN

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

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

 #else

 #else

       void increase(const Item&, const Prio&) {}

       void increase(const Item&, const Prio&) {}

       /// \brief Return the state of an item.

       /// \brief Return the state of an item.

       ///

       ///

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

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

       /// been in the heap, \c IN_HEAP if it is in the heap at the moment,

       /// been in the heap, \c IN_HEAP if it is in the heap at the moment,

       /// \param i The item.

       /// \param i The item.

 #ifdef DOXYGEN

 #ifdef DOXYGEN

       State state(const Item &i) const {}

       State state(const Item &i) const {}

 #else

 #else

       State state(const Item&) const { return PRE_HEAP; }

       State state(const Item&) const { return PRE_HEAP; }

       /// \brief Set the state of an item in the heap.

       /// \brief Set the state of an item in the heap.

       ///

       ///

       /// This function sets the state of the given item in the heap.

       /// This function sets the state of the given item in the heap.

       /// It can be used to manually clear the heap when it is important

       /// It can be used to manually clear the heap when it is important

       /// \param st The state. It should not be \c IN_HEAP.

       /// \param st The state. It should not be \c IN_HEAP.

 #ifdef DOXYGEN

 #ifdef DOXYGEN

       void state(const Item& i, State st) {}

       void state(const Item& i, State st) {}

 #else

 #else

       void state(const Item&, State) {}

       void state(const Item&, State) {}

       template <typename _Heap>

       template <typename _Heap>

       struct Constraints {

       struct Constraints {

       public:

       public: