COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 113:18a7ee8fa56e in lemon-main for lemon


Ignore:
Timestamp:
03/30/08 14:27:25 (17 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improvements in the heap concept

  • Better concept checking.
  • Improved doc.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/concepts/heap.h

    r100 r113  
    1919///\ingroup concept
    2020///\file
    21 ///\brief Classes for representing heaps.
    22 ///
     21///\brief The concept of heaps.
    2322
    2423#ifndef LEMON_CONCEPT_HEAP_H
    … …  
    2827
    2928namespace lemon {
     29
    3030  namespace concepts {
     31
    3132    /// \addtogroup concept
    3233    /// @{
    3334
    34 
    35     /// \brief A concept structure describes the main interface of heaps.
     35    /// \brief The heap concept.
    3636    ///
    37     /// A concept structure describes the main interface of heaps.
    38     ///
    39     template <typename Prio, typename ItemIntMap>
     37    /// Concept class describing the main interface of heaps.
     38    template <typename Priority, typename ItemIntMap>
    4039    class Heap {
    4140    public:
    4241
    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...
     42      /// Type of the items stored in the heap.
     43      typedef typename ItemIntMap::Key Item;
     44
     45      /// Type of the priorities.
     46      typedef Priority Prio;
     47
     48      /// \brief Type to represent the states of the items.
     49      ///
     50      /// Each item has a state associated to it. It can be "in heap",
     51      /// "pre heap" or "post heap". The later two are indifferent
     52      /// from the point of view of the heap, but may be useful for
     53      /// the user.
     54      ///
     55      /// The \c ItemIntMap must be initialized in such a way, that it
     56      /// assigns \c PRE_HEAP (<tt>-1</tt>) to every item.
    5557      enum State {
    5658        IN_HEAP = 0,
    … …  
    6264      ///
    6365      /// 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) {}
     66      /// \param map A map that assigns \c int values to keys of type
     67      /// \c Item. It is used internally by the heap implementations to
     68      /// handle the cross references. The assigned value must be
     69      /// \c PRE_HEAP (<tt>-1</tt>) for every item.
     70      explicit Heap(ItemIntMap &map) {}
    6871
    6972      /// \brief The number of items stored in the heap.
    … …  
    7275      int size() const { return 0; }
    7376
    74       /// \brief Checks if the heap stores no items.
    75       ///
    76       /// Returns \c true if and only if the heap stores no items.
     77      /// \brief Checks if the heap is empty.
     78      ///
     79      /// Returns \c true if the heap is empty.
    7780      bool empty() const { return false; }
    7881
    79       /// \brief Makes empty this heap.
    80       ///
    81       /// Makes this heap empty.
     82      /// \brief Makes the heap empty.
     83      ///
     84      /// Makes the heap empty.
    8285      void clear();
    8386
    84       /// \brief Insert an item into the heap with the given heap.
     87      /// \brief Inserts an item into the heap with the given priority.
    8588      ///   
    86       /// Adds \c i to the heap with priority \c p.
     89      /// Inserts the given item into the heap with the given priority.
    8790      /// \param i The item to insert.
    8891      /// \param p The priority of the item.
    8992      void push(const Item &i, const Prio &p) {}
    9093
    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. 
     94      /// \brief Returns the item having minimum priority.
     95      ///
     96      /// Returns the item having minimum priority.
     97      /// \pre The heap must be non-empty.
    9598      Item top() const {}
    9699
    97       /// \brief Returns the minimum priority.
    98       ///
    99       /// It returns the minimum priority.
    100       /// \pre The heap must be nonempty.
     100      /// \brief The minimum priority.
     101      ///
     102      /// Returns the minimum priority.
     103      /// \pre The heap must be non-empty.
    101104      Prio prio() const {}
    102105
    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. 
     106      /// \brief Removes the item having minimum priority.
     107      ///
     108      /// Removes the item having minimum priority.
     109      /// \pre The heap must be non-empty.
    107110      void pop() {}
    108111
    109       /// \brief Deletes \c i from the heap.
    110       ///
    111       /// This method deletes item \c i from the heap, if \c i was
     112      /// \brief Removes an item from the heap.
     113      ///
     114      /// Removes the given item from the heap if it is already stored.
     115      /// \param i The item to delete.
     116      void erase(const Item &i) {}
     117
     118      /// \brief The priority of an item.
     119      ///
     120      /// Returns the priority of the given item. 
     121      /// \pre \c i must be in the heap.
     122      /// \param i The item.
     123      Prio operator[](const Item &i) const {}
     124
     125      /// \brief Sets the priority of an item or inserts it, if it is
     126      /// not stored in the heap.
     127      ///
     128      /// This method sets the priority of the given item if it is
    112129      /// 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.
     130      /// Otherwise it inserts the given item with the given priority.
     131      ///
     132      /// It may throw an \ref UnderflowPriorityException.
    129133      /// \param i The item.
    130134      /// \param p The priority.
    131135      void set(const Item &i, const Prio &p) {}
    132136     
    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.
     137      /// \brief Decreases the priority of an item to the given value.
     138      ///
     139      /// Decreases the priority of an item to the given value.
    136140      /// \pre \c i must be stored in the heap with priority at least \c p.
    137141      /// \param i The item.
    … …  
    139143      void decrease(const Item &i, const Prio &p) {}
    140144
    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.
     145      /// \brief Increases the priority of an item to the given value.
     146      ///
     147      /// Increases the priority of an item to the given value.
     148      /// \pre \c i must be stored in the heap with priority at most \c p.
    146149      /// \param i The item.
    147150      /// \param p The priority.
    148151      void increase(const Item &i, const Prio &p) {}
    149152
    150       /// \brief Returns if \c item is in, has already been in, or has
     153      /// \brief Returns if an item is in, has already been in, or has
    151154      /// never been in the heap.
    152155      ///
    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.
     156      /// This method returns \c PRE_HEAP if the given item has never
     157      /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
     158      /// and \c POST_HEAP otherwise.
     159      /// In the latter case it is possible that the item will get back
     160      /// to the heap again.
    157161      /// \param i The item.
    158162      State state(const Item &i) const {}
    159163
    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      /// \brief Sets the state of an item in the heap.
     165      ///
     166      /// Sets the state of the given item in the heap. It can be used
     167      /// to manually clear the heap when it is important to achive the
    164168      /// better time complexity.
    165169      /// \param i The item.
    166       /// \param st The state. It should not be \c IN_HEAP. 
     170      /// \param st The state. It should not be \c IN_HEAP.
    167171      void state(const Item& i, State st) {}
    168172
    … …  
    171175      struct Constraints {
    172176      public:
    173    
    174177        void constraints() {
     178          typedef typename _Heap::Item OwnItem;
     179          typedef typename _Heap::Prio OwnPrio;
     180          typedef typename _Heap::State OwnState;
     181
    175182          Item item;
    176183          Prio prio;
    177 
     184          State state;
    178185          item=Item();
    179186          prio=Prio();
    180 
    181187          ignore_unused_variable_warning(item);
    182188          ignore_unused_variable_warning(prio);
    183 
    184           typedef typename _Heap::State State;
    185           State state;
    186 
    187189          ignore_unused_variable_warning(state);
    188      
    189           _Heap heap1 = _Heap(map);
    190 
     190
     191          OwnItem own_item;
     192          OwnPrio own_prio;
     193          OwnState own_state;
     194          own_item=Item();
     195          own_prio=Prio();
     196          ignore_unused_variable_warning(own_item);
     197          ignore_unused_variable_warning(own_prio);
     198          ignore_unused_variable_warning(own_state);
     199
     200          _Heap heap1(map);
     201          _Heap heap2 = heap1;
    191202          ignore_unused_variable_warning(heap1);
    192      
    193           heap.push(item, prio);
     203          ignore_unused_variable_warning(heap2);
     204         
     205          int s = heap.size();
     206          bool e = heap.empty();
    194207
    195208          prio = heap.prio();
    196209          item = heap.top();
    197 
     210          prio = heap[item];
     211          own_prio = heap.prio();
     212          own_item = heap.top();
     213          own_prio = heap[own_item];
     214
     215          heap.push(item, prio);
     216          heap.push(own_item, own_prio);
    198217          heap.pop();
    199218
    … …  
    201220          heap.decrease(item, prio);
    202221          heap.increase(item, prio);
    203           prio = heap[item];
     222          heap.set(own_item, own_prio);
     223          heap.decrease(own_item, own_prio);
     224          heap.increase(own_item, own_prio);
    204225
    205226          heap.erase(item);
     227          heap.erase(own_item);
     228          heap.clear();
    206229
    207230          state = heap.state(item);
     231          heap.state(item, state);
     232          state = heap.state(own_item);
     233          heap.state(own_item, own_state);
    208234
    209235          state = _Heap::PRE_HEAP;
    210236          state = _Heap::IN_HEAP;
    211237          state = _Heap::POST_HEAP;
    212 
    213           heap.clear();
     238          own_state = _Heap::PRE_HEAP;
     239          own_state = _Heap::IN_HEAP;
     240          own_state = _Heap::POST_HEAP;
    214241        }
    215    
     242
    216243        _Heap& heap;
    217244        ItemIntMap& map;
    218 
    219         Constraints() : heap(0), map(0) {}
    220245      };
    221246    };
Note: See TracChangeset for help on using the changeset viewer.