lemon/concepts/heap.h
changeset 912 09282720100b
parent 817 b87f0504cdbe
child 976 426a704d7483
equal deleted inserted replaced
13:72b961404845 14:27b37666b56d
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    90       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    90       /// \c PRE_HEAP (<tt>-1</tt>) for each item.
    91 #ifdef DOXYGEN
    91 #ifdef DOXYGEN
    92       explicit Heap(ItemIntMap &map) {}
    92       explicit Heap(ItemIntMap &map) {}
    93 #else
    93 #else
    94       explicit Heap(ItemIntMap&) {}
    94       explicit Heap(ItemIntMap&) {}
    95 #endif      
    95 #endif
    96 
    96 
    97       /// \brief Constructor.
    97       /// \brief Constructor.
    98       ///
    98       ///
    99       /// Constructor.
    99       /// Constructor.
   100       /// \param map A map that assigns \c int values to keys of type
   100       /// \param map A map that assigns \c int values to keys of type
   104       /// \param comp The function object used for comparing the priorities.
   104       /// \param comp The function object used for comparing the priorities.
   105 #ifdef DOXYGEN
   105 #ifdef DOXYGEN
   106       explicit Heap(ItemIntMap &map, const CMP &comp) {}
   106       explicit Heap(ItemIntMap &map, const CMP &comp) {}
   107 #else
   107 #else
   108       explicit Heap(ItemIntMap&, const CMP&) {}
   108       explicit Heap(ItemIntMap&, const CMP&) {}
   109 #endif      
   109 #endif
   110 
   110 
   111       /// \brief The number of items stored in the heap.
   111       /// \brief The number of items stored in the heap.
   112       ///
   112       ///
   113       /// This function returns the number of items stored in the heap.
   113       /// This function returns the number of items stored in the heap.
   114       int size() const { return 0; }
   114       int size() const { return 0; }
   136       /// \pre \e i must not be stored in the heap.
   136       /// \pre \e i must not be stored in the heap.
   137 #ifdef DOXYGEN
   137 #ifdef DOXYGEN
   138       void push(const Item &i, const Prio &p) {}
   138       void push(const Item &i, const Prio &p) {}
   139 #else
   139 #else
   140       void push(const Item&, const Prio&) {}
   140       void push(const Item&, const Prio&) {}
   141 #endif      
   141 #endif
   142 
   142 
   143       /// \brief Return the item having minimum priority.
   143       /// \brief Return the item having minimum priority.
   144       ///
   144       ///
   145       /// This function returns the item having minimum priority.
   145       /// This function returns the item having minimum priority.
   146       /// \pre The heap must be non-empty.
   146       /// \pre The heap must be non-empty.
   166       /// \pre \e i must be in the heap.
   166       /// \pre \e i must be in the heap.
   167 #ifdef DOXYGEN
   167 #ifdef DOXYGEN
   168       void erase(const Item &i) {}
   168       void erase(const Item &i) {}
   169 #else
   169 #else
   170       void erase(const Item&) {}
   170       void erase(const Item&) {}
   171 #endif      
   171 #endif
   172 
   172 
   173       /// \brief The priority of the given item.
   173       /// \brief The priority of the given item.
   174       ///
   174       ///
   175       /// This function returns the priority of the given item.
   175       /// This function returns the priority of the given item.
   176       /// \param i The item.
   176       /// \param i The item.
   177       /// \pre \e i must be in the heap.
   177       /// \pre \e i must be in the heap.
   178 #ifdef DOXYGEN
   178 #ifdef DOXYGEN
   179       Prio operator[](const Item &i) const {}
   179       Prio operator[](const Item &i) const {}
   180 #else
   180 #else
   181       Prio operator[](const Item&) const { return Prio(); }
   181       Prio operator[](const Item&) const { return Prio(); }
   182 #endif      
   182 #endif
   183 
   183 
   184       /// \brief Set the priority of an item or insert it, if it is
   184       /// \brief Set the priority of an item or insert it, if it is
   185       /// not stored in the heap.
   185       /// not stored in the heap.
   186       ///
   186       ///
   187       /// This method sets the priority of the given item if it is
   187       /// This method sets the priority of the given item if it is
   192       /// \param p The priority.
   192       /// \param p The priority.
   193 #ifdef DOXYGEN
   193 #ifdef DOXYGEN
   194       void set(const Item &i, const Prio &p) {}
   194       void set(const Item &i, const Prio &p) {}
   195 #else
   195 #else
   196       void set(const Item&, const Prio&) {}
   196       void set(const Item&, const Prio&) {}
   197 #endif      
   197 #endif
   198 
   198 
   199       /// \brief Decrease the priority of an item to the given value.
   199       /// \brief Decrease the priority of an item to the given value.
   200       ///
   200       ///
   201       /// This function decreases the priority of an item to the given value.
   201       /// This function decreases the priority of an item to the given value.
   202       /// \param i The item.
   202       /// \param i The item.
   204       /// \pre \e i must be stored in the heap with priority at least \e p.
   204       /// \pre \e i must be stored in the heap with priority at least \e p.
   205 #ifdef DOXYGEN
   205 #ifdef DOXYGEN
   206       void decrease(const Item &i, const Prio &p) {}
   206       void decrease(const Item &i, const Prio &p) {}
   207 #else
   207 #else
   208       void decrease(const Item&, const Prio&) {}
   208       void decrease(const Item&, const Prio&) {}
   209 #endif      
   209 #endif
   210 
   210 
   211       /// \brief Increase the priority of an item to the given value.
   211       /// \brief Increase the priority of an item to the given value.
   212       ///
   212       ///
   213       /// This function increases the priority of an item to the given value.
   213       /// This function increases the priority of an item to the given value.
   214       /// \param i The item.
   214       /// \param i The item.
   216       /// \pre \e i must be stored in the heap with priority at most \e p.
   216       /// \pre \e i must be stored in the heap with priority at most \e p.
   217 #ifdef DOXYGEN
   217 #ifdef DOXYGEN
   218       void increase(const Item &i, const Prio &p) {}
   218       void increase(const Item &i, const Prio &p) {}
   219 #else
   219 #else
   220       void increase(const Item&, const Prio&) {}
   220       void increase(const Item&, const Prio&) {}
   221 #endif      
   221 #endif
   222 
   222 
   223       /// \brief Return the state of an item.
   223       /// \brief Return the state of an item.
   224       ///
   224       ///
   225       /// This method returns \c PRE_HEAP if the given item has never
   225       /// This method returns \c PRE_HEAP if the given item has never
   226       /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   226       /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   230       /// \param i The item.
   230       /// \param i The item.
   231 #ifdef DOXYGEN
   231 #ifdef DOXYGEN
   232       State state(const Item &i) const {}
   232       State state(const Item &i) const {}
   233 #else
   233 #else
   234       State state(const Item&) const { return PRE_HEAP; }
   234       State state(const Item&) const { return PRE_HEAP; }
   235 #endif      
   235 #endif
   236 
   236 
   237       /// \brief Set the state of an item in the heap.
   237       /// \brief Set the state of an item in the heap.
   238       ///
   238       ///
   239       /// This function sets the state of the given item in the heap.
   239       /// This function sets the state of the given item in the heap.
   240       /// It can be used to manually clear the heap when it is important
   240       /// It can be used to manually clear the heap when it is important
   243       /// \param st The state. It should not be \c IN_HEAP.
   243       /// \param st The state. It should not be \c IN_HEAP.
   244 #ifdef DOXYGEN
   244 #ifdef DOXYGEN
   245       void state(const Item& i, State st) {}
   245       void state(const Item& i, State st) {}
   246 #else
   246 #else
   247       void state(const Item&, State) {}
   247       void state(const Item&, State) {}
   248 #endif      
   248 #endif
   249 
   249 
   250 
   250 
   251       template <typename _Heap>
   251       template <typename _Heap>
   252       struct Constraints {
   252       struct Constraints {
   253       public:
   253       public: