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