lemon/concepts/heap.h
changeset 102 81563e019fa4
child 113 18a7ee8fa56e
equal deleted inserted replaced
-1:000000000000 0:79b525502e1c
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2008
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
       
    19 ///\ingroup concept
       
    20 ///\file
       
    21 ///\brief Classes for representing heaps.
       
    22 ///
       
    23 
       
    24 #ifndef LEMON_CONCEPT_HEAP_H
       
    25 #define LEMON_CONCEPT_HEAP_H
       
    26 
       
    27 #include <lemon/bits/invalid.h>
       
    28 
       
    29 namespace lemon {
       
    30   namespace concepts {
       
    31     /// \addtogroup concept
       
    32     /// @{
       
    33 
       
    34 
       
    35     /// \brief A concept structure describes the main interface of heaps.
       
    36     ///
       
    37     /// A concept structure describes the main interface of heaps.
       
    38     ///
       
    39     template <typename Prio, typename ItemIntMap>
       
    40     class Heap {
       
    41     public:
       
    42 
       
    43       ///\brief Type of the items stored in the heap.
       
    44       typedef typename ItemIntMap::Key  Item;
       
    45   
       
    46 
       
    47       /// \brief Type to represent the items states.
       
    48       ///
       
    49       /// Each Item element have a state associated to it. It may be "in heap",
       
    50       /// "pre heap" or "post heap". The later two are indifferent from the
       
    51       /// heap's point of view, but may be useful to the user.
       
    52       ///
       
    53       /// The ItemIntMap _should_ be initialized in such way, that it maps
       
    54       /// PRE_HEAP (-1) to any element to be put in the heap...
       
    55       enum State {
       
    56 	IN_HEAP = 0,
       
    57 	PRE_HEAP = -1,
       
    58 	POST_HEAP = -2
       
    59       };
       
    60       
       
    61       /// \brief The constructor.
       
    62       ///
       
    63       /// The constructor.
       
    64       /// \param _iim should be given to the constructor, since it is used
       
    65       /// internally to handle the cross references. The value of the map
       
    66       /// should be PRE_HEAP (-1) for each element.
       
    67       explicit Heap(ItemIntMap &_iim) {}
       
    68 
       
    69       /// \brief The number of items stored in the heap.
       
    70       ///
       
    71       /// Returns the number of items stored in the heap.
       
    72       int size() const { return 0; }
       
    73 
       
    74       /// \brief Checks if the heap stores no items.
       
    75       ///
       
    76       /// Returns \c true if and only if the heap stores no items.
       
    77       bool empty() const { return false; }
       
    78 
       
    79       /// \brief Makes empty this heap.
       
    80       ///
       
    81       /// Makes this heap empty.
       
    82       void clear();
       
    83 
       
    84       /// \brief Insert an item into the heap with the given heap.
       
    85       ///    
       
    86       /// Adds \c i to the heap with priority \c p. 
       
    87       /// \param i The item to insert.
       
    88       /// \param p The priority of the item.
       
    89       void push(const Item &i, const Prio &p) {}
       
    90 
       
    91       /// \brief Returns the item with minimum priority.
       
    92       ///
       
    93       /// This method returns the item with minimum priority.  
       
    94       /// \pre The heap must be nonempty.  
       
    95       Item top() const {}
       
    96 
       
    97       /// \brief Returns the minimum priority.
       
    98       ///
       
    99       /// It returns the minimum priority.
       
   100       /// \pre The heap must be nonempty.
       
   101       Prio prio() const {}
       
   102 
       
   103       /// \brief Deletes the item with minimum priority.
       
   104       ///
       
   105       /// This method deletes the item with minimum priority.
       
   106       /// \pre The heap must be non-empty.  
       
   107       void pop() {}
       
   108 
       
   109       /// \brief Deletes \c i from the heap.
       
   110       ///
       
   111       /// This method deletes item \c i from the heap, if \c i was
       
   112       /// already stored in the heap.
       
   113       /// \param i The item to erase. 
       
   114       void erase(const Item &i) {}
       
   115 
       
   116       /// \brief Returns the priority of \c i.
       
   117       ///
       
   118       /// This function returns the priority of item \c i.  
       
   119       /// \pre \c i must be in the heap.
       
   120       /// \param i The item.
       
   121       Prio operator[](const Item &i) const {}
       
   122 
       
   123       /// \brief \c i gets to the heap with priority \c p independently 
       
   124       /// if \c i was already there.
       
   125       ///
       
   126       /// This method calls \ref push(\c i, \c p) if \c i is not stored
       
   127       /// in the heap and sets the priority of \c i to \c p otherwise.
       
   128       /// It may throw an \e UnderFlowPriorityException. 
       
   129       /// \param i The item.
       
   130       /// \param p The priority.
       
   131       void set(const Item &i, const Prio &p) {}
       
   132       
       
   133       /// \brief Decreases the priority of \c i to \c p.
       
   134       ///
       
   135       /// This method decreases the priority of item \c i to \c p.
       
   136       /// \pre \c i must be stored in the heap with priority at least \c p.
       
   137       /// \param i The item.
       
   138       /// \param p The priority.
       
   139       void decrease(const Item &i, const Prio &p) {}
       
   140 
       
   141       /// \brief Increases the priority of \c i to \c p.
       
   142       ///
       
   143       /// This method sets the priority of item \c i to \c p. 
       
   144       /// \pre \c i must be stored in the heap with priority at most \c
       
   145       /// p relative to \c Compare.
       
   146       /// \param i The item.
       
   147       /// \param p The priority.
       
   148       void increase(const Item &i, const Prio &p) {}
       
   149 
       
   150       /// \brief Returns if \c item is in, has already been in, or has 
       
   151       /// never been in the heap.
       
   152       ///
       
   153       /// This method returns PRE_HEAP if \c item has never been in the
       
   154       /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
       
   155       /// otherwise. In the latter case it is possible that \c item will
       
   156       /// get back to the heap again.
       
   157       /// \param i The item.
       
   158       State state(const Item &i) const {}
       
   159 
       
   160       /// \brief Sets the state of the \c item in the heap.
       
   161       ///
       
   162       /// Sets the state of the \c item in the heap. It can be used to
       
   163       /// manually clear the heap when it is important to achive the
       
   164       /// better time complexity.
       
   165       /// \param i The item.
       
   166       /// \param st The state. It should not be \c IN_HEAP. 
       
   167       void state(const Item& i, State st) {}
       
   168 
       
   169 
       
   170       template <typename _Heap>
       
   171       struct Constraints {
       
   172       public:
       
   173     
       
   174 	void constraints() {
       
   175 	  Item item;
       
   176 	  Prio prio;
       
   177 
       
   178 	  item=Item();
       
   179 	  prio=Prio();
       
   180 
       
   181 	  ignore_unused_variable_warning(item);
       
   182 	  ignore_unused_variable_warning(prio);
       
   183 
       
   184 	  typedef typename _Heap::State State;
       
   185 	  State state;
       
   186 
       
   187 	  ignore_unused_variable_warning(state);
       
   188       
       
   189 	  _Heap heap1 = _Heap(map);
       
   190 
       
   191 	  ignore_unused_variable_warning(heap1);
       
   192       
       
   193 	  heap.push(item, prio);
       
   194 
       
   195 	  prio = heap.prio();
       
   196 	  item = heap.top();
       
   197 
       
   198 	  heap.pop();
       
   199 
       
   200 	  heap.set(item, prio);
       
   201 	  heap.decrease(item, prio);
       
   202 	  heap.increase(item, prio);
       
   203 	  prio = heap[item];
       
   204 
       
   205 	  heap.erase(item);
       
   206 
       
   207 	  state = heap.state(item);
       
   208 
       
   209 	  state = _Heap::PRE_HEAP;
       
   210 	  state = _Heap::IN_HEAP;
       
   211 	  state = _Heap::POST_HEAP;
       
   212 
       
   213 	  heap.clear();
       
   214 	}
       
   215     
       
   216 	_Heap& heap;
       
   217 	ItemIntMap& map;
       
   218 
       
   219 	Constraints() : heap(0), map(0) {}
       
   220       };
       
   221     };
       
   222 
       
   223     /// @}
       
   224   } // namespace lemon
       
   225 }
       
   226 #endif // LEMON_CONCEPT_PATH_H