Improvements in the heap concept
authorPeter Kovacs <kpeter@inf.elte.hu>
Sun, 30 Mar 2008 14:27:25 +0200
changeset 11318a7ee8fa56e
parent 112 d2ee5e7f00ef
child 114 c837d1e449dc
Improvements in the heap concept
- Better concept checking.
- Improved doc.
lemon/concepts/heap.h
     1.1 --- a/lemon/concepts/heap.h	Thu Mar 27 13:26:16 2008 +0100
     1.2 +++ b/lemon/concepts/heap.h	Sun Mar 30 14:27:25 2008 +0200
     1.3 @@ -18,8 +18,7 @@
     1.4  
     1.5  ///\ingroup concept
     1.6  ///\file
     1.7 -///\brief Classes for representing heaps.
     1.8 -///
     1.9 +///\brief The concept of heaps.
    1.10  
    1.11  #ifndef LEMON_CONCEPT_HEAP_H
    1.12  #define LEMON_CONCEPT_HEAP_H
    1.13 @@ -27,31 +26,34 @@
    1.14  #include <lemon/bits/invalid.h>
    1.15  
    1.16  namespace lemon {
    1.17 +
    1.18    namespace concepts {
    1.19 +
    1.20      /// \addtogroup concept
    1.21      /// @{
    1.22  
    1.23 -
    1.24 -    /// \brief A concept structure describes the main interface of heaps.
    1.25 +    /// \brief The heap concept.
    1.26      ///
    1.27 -    /// A concept structure describes the main interface of heaps.
    1.28 -    ///
    1.29 -    template <typename Prio, typename ItemIntMap>
    1.30 +    /// Concept class describing the main interface of heaps.
    1.31 +    template <typename Priority, typename ItemIntMap>
    1.32      class Heap {
    1.33      public:
    1.34  
    1.35 -      ///\brief Type of the items stored in the heap.
    1.36 -      typedef typename ItemIntMap::Key  Item;
    1.37 -  
    1.38 +      /// Type of the items stored in the heap.
    1.39 +      typedef typename ItemIntMap::Key Item;
    1.40  
    1.41 -      /// \brief Type to represent the items states.
    1.42 +      /// Type of the priorities.
    1.43 +      typedef Priority Prio;
    1.44 +
    1.45 +      /// \brief Type to represent the states of the items.
    1.46        ///
    1.47 -      /// Each Item element have a state associated to it. It may be "in heap",
    1.48 -      /// "pre heap" or "post heap". The later two are indifferent from the
    1.49 -      /// heap's point of view, but may be useful to the user.
    1.50 +      /// Each item has a state associated to it. It can be "in heap",
    1.51 +      /// "pre heap" or "post heap". The later two are indifferent
    1.52 +      /// from the point of view of the heap, but may be useful for
    1.53 +      /// the user.
    1.54        ///
    1.55 -      /// The ItemIntMap _should_ be initialized in such way, that it maps
    1.56 -      /// PRE_HEAP (-1) to any element to be put in the heap...
    1.57 +      /// The \c ItemIntMap must be initialized in such a way, that it 
    1.58 +      /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
    1.59        enum State {
    1.60  	IN_HEAP = 0,
    1.61  	PRE_HEAP = -1,
    1.62 @@ -61,162 +63,185 @@
    1.63        /// \brief The constructor.
    1.64        ///
    1.65        /// The constructor.
    1.66 -      /// \param _iim should be given to the constructor, since it is used
    1.67 -      /// internally to handle the cross references. The value of the map
    1.68 -      /// should be PRE_HEAP (-1) for each element.
    1.69 -      explicit Heap(ItemIntMap &_iim) {}
    1.70 +      /// \param map A map that assigns \c int values to keys of type
    1.71 +      /// \c Item. It is used internally by the heap implementations to
    1.72 +      /// handle the cross references. The assigned value must be
    1.73 +      /// \c PRE_HEAP (<tt>-1</tt>) for every item.
    1.74 +      explicit Heap(ItemIntMap &map) {}
    1.75  
    1.76        /// \brief The number of items stored in the heap.
    1.77        ///
    1.78        /// Returns the number of items stored in the heap.
    1.79        int size() const { return 0; }
    1.80  
    1.81 -      /// \brief Checks if the heap stores no items.
    1.82 +      /// \brief Checks if the heap is empty.
    1.83        ///
    1.84 -      /// Returns \c true if and only if the heap stores no items.
    1.85 +      /// Returns \c true if the heap is empty.
    1.86        bool empty() const { return false; }
    1.87  
    1.88 -      /// \brief Makes empty this heap.
    1.89 +      /// \brief Makes the heap empty.
    1.90        ///
    1.91 -      /// Makes this heap empty.
    1.92 +      /// Makes the heap empty.
    1.93        void clear();
    1.94  
    1.95 -      /// \brief Insert an item into the heap with the given heap.
    1.96 +      /// \brief Inserts an item into the heap with the given priority.
    1.97        ///    
    1.98 -      /// Adds \c i to the heap with priority \c p. 
    1.99 +      /// Inserts the given item into the heap with the given priority. 
   1.100        /// \param i The item to insert.
   1.101        /// \param p The priority of the item.
   1.102        void push(const Item &i, const Prio &p) {}
   1.103  
   1.104 -      /// \brief Returns the item with minimum priority.
   1.105 +      /// \brief Returns the item having minimum priority.
   1.106        ///
   1.107 -      /// This method returns the item with minimum priority.  
   1.108 -      /// \pre The heap must be nonempty.  
   1.109 +      /// Returns the item having minimum priority.
   1.110 +      /// \pre The heap must be non-empty.
   1.111        Item top() const {}
   1.112  
   1.113 -      /// \brief Returns the minimum priority.
   1.114 +      /// \brief The minimum priority.
   1.115        ///
   1.116 -      /// It returns the minimum priority.
   1.117 -      /// \pre The heap must be nonempty.
   1.118 +      /// Returns the minimum priority.
   1.119 +      /// \pre The heap must be non-empty.
   1.120        Prio prio() const {}
   1.121  
   1.122 -      /// \brief Deletes the item with minimum priority.
   1.123 +      /// \brief Removes the item having minimum priority.
   1.124        ///
   1.125 -      /// This method deletes the item with minimum priority.
   1.126 -      /// \pre The heap must be non-empty.  
   1.127 +      /// Removes the item having minimum priority.
   1.128 +      /// \pre The heap must be non-empty.
   1.129        void pop() {}
   1.130  
   1.131 -      /// \brief Deletes \c i from the heap.
   1.132 +      /// \brief Removes an item from the heap.
   1.133        ///
   1.134 -      /// This method deletes item \c i from the heap, if \c i was
   1.135 -      /// already stored in the heap.
   1.136 -      /// \param i The item to erase. 
   1.137 +      /// Removes the given item from the heap if it is already stored.
   1.138 +      /// \param i The item to delete. 
   1.139        void erase(const Item &i) {}
   1.140  
   1.141 -      /// \brief Returns the priority of \c i.
   1.142 +      /// \brief The priority of an item.
   1.143        ///
   1.144 -      /// This function returns the priority of item \c i.  
   1.145 +      /// Returns the priority of the given item.  
   1.146        /// \pre \c i must be in the heap.
   1.147        /// \param i The item.
   1.148        Prio operator[](const Item &i) const {}
   1.149  
   1.150 -      /// \brief \c i gets to the heap with priority \c p independently 
   1.151 -      /// if \c i was already there.
   1.152 +      /// \brief Sets the priority of an item or inserts it, if it is
   1.153 +      /// not stored in the heap.
   1.154        ///
   1.155 -      /// This method calls \ref push(\c i, \c p) if \c i is not stored
   1.156 -      /// in the heap and sets the priority of \c i to \c p otherwise.
   1.157 -      /// It may throw an \e UnderFlowPriorityException. 
   1.158 +      /// This method sets the priority of the given item if it is
   1.159 +      /// already stored in the heap.
   1.160 +      /// Otherwise it inserts the given item with the given priority.
   1.161 +      ///
   1.162 +      /// It may throw an \ref UnderflowPriorityException.
   1.163        /// \param i The item.
   1.164        /// \param p The priority.
   1.165        void set(const Item &i, const Prio &p) {}
   1.166        
   1.167 -      /// \brief Decreases the priority of \c i to \c p.
   1.168 +      /// \brief Decreases the priority of an item to the given value.
   1.169        ///
   1.170 -      /// This method decreases the priority of item \c i to \c p.
   1.171 +      /// Decreases the priority of an item to the given value.
   1.172        /// \pre \c i must be stored in the heap with priority at least \c p.
   1.173        /// \param i The item.
   1.174        /// \param p The priority.
   1.175        void decrease(const Item &i, const Prio &p) {}
   1.176  
   1.177 -      /// \brief Increases the priority of \c i to \c p.
   1.178 +      /// \brief Increases the priority of an item to the given value.
   1.179        ///
   1.180 -      /// This method sets the priority of item \c i to \c p. 
   1.181 -      /// \pre \c i must be stored in the heap with priority at most \c
   1.182 -      /// p relative to \c Compare.
   1.183 +      /// Increases the priority of an item to the given value.
   1.184 +      /// \pre \c i must be stored in the heap with priority at most \c p.
   1.185        /// \param i The item.
   1.186        /// \param p The priority.
   1.187        void increase(const Item &i, const Prio &p) {}
   1.188  
   1.189 -      /// \brief Returns if \c item is in, has already been in, or has 
   1.190 +      /// \brief Returns if an item is in, has already been in, or has
   1.191        /// never been in the heap.
   1.192        ///
   1.193 -      /// This method returns PRE_HEAP if \c item has never been in the
   1.194 -      /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   1.195 -      /// otherwise. In the latter case it is possible that \c item will
   1.196 -      /// get back to the heap again.
   1.197 +      /// This method returns \c PRE_HEAP if the given item has never
   1.198 +      /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
   1.199 +      /// and \c POST_HEAP otherwise.
   1.200 +      /// In the latter case it is possible that the item will get back
   1.201 +      /// to the heap again.
   1.202        /// \param i The item.
   1.203        State state(const Item &i) const {}
   1.204  
   1.205 -      /// \brief Sets the state of the \c item in the heap.
   1.206 +      /// \brief Sets the state of an item in the heap.
   1.207        ///
   1.208 -      /// Sets the state of the \c item in the heap. It can be used to
   1.209 -      /// manually clear the heap when it is important to achive the
   1.210 +      /// Sets the state of the given item in the heap. It can be used
   1.211 +      /// to manually clear the heap when it is important to achive the
   1.212        /// better time complexity.
   1.213        /// \param i The item.
   1.214 -      /// \param st The state. It should not be \c IN_HEAP. 
   1.215 +      /// \param st The state. It should not be \c IN_HEAP.
   1.216        void state(const Item& i, State st) {}
   1.217  
   1.218  
   1.219        template <typename _Heap>
   1.220        struct Constraints {
   1.221        public:
   1.222 -    
   1.223  	void constraints() {
   1.224 +	  typedef typename _Heap::Item OwnItem;
   1.225 +	  typedef typename _Heap::Prio OwnPrio;
   1.226 +	  typedef typename _Heap::State OwnState;
   1.227 +
   1.228  	  Item item;
   1.229  	  Prio prio;
   1.230 -
   1.231 +	  State state;
   1.232  	  item=Item();
   1.233  	  prio=Prio();
   1.234 -
   1.235  	  ignore_unused_variable_warning(item);
   1.236  	  ignore_unused_variable_warning(prio);
   1.237 +	  ignore_unused_variable_warning(state);
   1.238  
   1.239 -	  typedef typename _Heap::State State;
   1.240 -	  State state;
   1.241 +	  OwnItem own_item;
   1.242 +	  OwnPrio own_prio;
   1.243 +	  OwnState own_state;
   1.244 +	  own_item=Item();
   1.245 +	  own_prio=Prio();
   1.246 +	  ignore_unused_variable_warning(own_item);
   1.247 +	  ignore_unused_variable_warning(own_prio);
   1.248 +	  ignore_unused_variable_warning(own_state);
   1.249  
   1.250 -	  ignore_unused_variable_warning(state);
   1.251 -      
   1.252 -	  _Heap heap1 = _Heap(map);
   1.253 -
   1.254 +	  _Heap heap1(map);
   1.255 +	  _Heap heap2 = heap1;
   1.256  	  ignore_unused_variable_warning(heap1);
   1.257 -      
   1.258 -	  heap.push(item, prio);
   1.259 +	  ignore_unused_variable_warning(heap2);
   1.260 +	  
   1.261 +	  int s = heap.size();
   1.262 +	  bool e = heap.empty();
   1.263  
   1.264  	  prio = heap.prio();
   1.265  	  item = heap.top();
   1.266 +	  prio = heap[item];
   1.267 +	  own_prio = heap.prio();
   1.268 +	  own_item = heap.top();
   1.269 +	  own_prio = heap[own_item];
   1.270  
   1.271 +	  heap.push(item, prio);
   1.272 +	  heap.push(own_item, own_prio);
   1.273  	  heap.pop();
   1.274  
   1.275  	  heap.set(item, prio);
   1.276  	  heap.decrease(item, prio);
   1.277  	  heap.increase(item, prio);
   1.278 -	  prio = heap[item];
   1.279 +	  heap.set(own_item, own_prio);
   1.280 +	  heap.decrease(own_item, own_prio);
   1.281 +	  heap.increase(own_item, own_prio);
   1.282  
   1.283  	  heap.erase(item);
   1.284 +	  heap.erase(own_item);
   1.285 +	  heap.clear();
   1.286  
   1.287  	  state = heap.state(item);
   1.288 +	  heap.state(item, state);
   1.289 +	  state = heap.state(own_item);
   1.290 +	  heap.state(own_item, own_state);
   1.291  
   1.292  	  state = _Heap::PRE_HEAP;
   1.293  	  state = _Heap::IN_HEAP;
   1.294  	  state = _Heap::POST_HEAP;
   1.295 +	  own_state = _Heap::PRE_HEAP;
   1.296 +	  own_state = _Heap::IN_HEAP;
   1.297 +	  own_state = _Heap::POST_HEAP;
   1.298 +	}
   1.299  
   1.300 -	  heap.clear();
   1.301 -	}
   1.302 -    
   1.303  	_Heap& heap;
   1.304  	ItemIntMap& map;
   1.305 -
   1.306 -	Constraints() : heap(0), map(0) {}
   1.307        };
   1.308      };
   1.309