lemon/radix_heap.h
author Balazs Dezso <deba@inf.elte.hu>
Thu, 04 Mar 2010 15:20:59 +0100
changeset 951 41d7ac528c3a
parent 757 f1fe0ddad6f7
permissions -rw-r--r--
Uniforming primal scale to 2 (#314)
deba@728
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@728
     2
 *
deba@728
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@728
     4
 *
deba@728
     5
 * Copyright (C) 2003-2009
deba@728
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@728
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@728
     8
 *
deba@728
     9
 * Permission to use, modify and distribute this software is granted
deba@728
    10
 * provided that this copyright notice appears in all copies. For
deba@728
    11
 * precise terms see the accompanying LICENSE file.
deba@728
    12
 *
deba@728
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@728
    14
 * express or implied, and with no claim as to its suitability for any
deba@728
    15
 * purpose.
deba@728
    16
 *
deba@728
    17
 */
deba@728
    18
deba@728
    19
#ifndef LEMON_RADIX_HEAP_H
deba@728
    20
#define LEMON_RADIX_HEAP_H
deba@728
    21
kpeter@757
    22
///\ingroup heaps
deba@728
    23
///\file
kpeter@756
    24
///\brief Radix heap implementation.
deba@728
    25
deba@728
    26
#include <vector>
deba@728
    27
#include <lemon/error.h>
deba@728
    28
deba@728
    29
namespace lemon {
deba@728
    30
deba@728
    31
kpeter@757
    32
  /// \ingroup heaps
deba@728
    33
  ///
kpeter@756
    34
  /// \brief Radix heap data structure.
deba@728
    35
  ///
kpeter@756
    36
  /// This class implements the \e radix \e heap data structure.
kpeter@756
    37
  /// It practically conforms to the \ref concepts::Heap "heap concept",
kpeter@756
    38
  /// but it has some limitations due its special implementation.
kpeter@756
    39
  /// The type of the priorities must be \c int and the priority of an
kpeter@756
    40
  /// item cannot be decreased under the priority of the last removed item.
deba@728
    41
  ///
kpeter@756
    42
  /// \tparam IM A read-writable item map with \c int values, used
kpeter@756
    43
  /// internally to handle the cross references.
deba@730
    44
  template <typename IM>
deba@728
    45
  class RadixHeap {
deba@728
    46
deba@728
    47
  public:
kpeter@756
    48
kpeter@756
    49
    /// Type of the item-int map.
kpeter@756
    50
    typedef IM ItemIntMap;
kpeter@756
    51
    /// Type of the priorities.
deba@728
    52
    typedef int Prio;
kpeter@756
    53
    /// Type of the items stored in the heap.
kpeter@756
    54
    typedef typename ItemIntMap::Key Item;
deba@728
    55
deba@728
    56
    /// \brief Exception thrown by RadixHeap.
deba@728
    57
    ///
kpeter@756
    58
    /// This exception is thrown when an item is inserted into a
kpeter@756
    59
    /// RadixHeap with a priority smaller than the last erased one.
deba@728
    60
    /// \see RadixHeap
kpeter@758
    61
    class PriorityUnderflowError : public Exception {
deba@728
    62
    public:
deba@728
    63
      virtual const char* what() const throw() {
kpeter@758
    64
        return "lemon::RadixHeap::PriorityUnderflowError";
deba@728
    65
      }
deba@728
    66
    };
deba@728
    67
kpeter@756
    68
    /// \brief Type to represent the states of the items.
deba@728
    69
    ///
kpeter@756
    70
    /// Each item has a state associated to it. It can be "in heap",
kpeter@756
    71
    /// "pre-heap" or "post-heap". The latter two are indifferent from the
deba@728
    72
    /// heap's point of view, but may be useful to the user.
deba@728
    73
    ///
kpeter@756
    74
    /// The item-int map must be initialized in such way that it assigns
kpeter@756
    75
    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
deba@728
    76
    enum State {
kpeter@756
    77
      IN_HEAP = 0,    ///< = 0.
kpeter@756
    78
      PRE_HEAP = -1,  ///< = -1.
kpeter@756
    79
      POST_HEAP = -2  ///< = -2.
deba@728
    80
    };
deba@728
    81
deba@728
    82
  private:
deba@728
    83
deba@728
    84
    struct RadixItem {
deba@728
    85
      int prev, next, box;
deba@728
    86
      Item item;
deba@728
    87
      int prio;
deba@728
    88
      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
deba@728
    89
    };
deba@728
    90
deba@728
    91
    struct RadixBox {
deba@728
    92
      int first;
deba@728
    93
      int min, size;
deba@728
    94
      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
deba@728
    95
    };
deba@728
    96
kpeter@758
    97
    std::vector<RadixItem> _data;
kpeter@758
    98
    std::vector<RadixBox> _boxes;
deba@728
    99
deba@730
   100
    ItemIntMap &_iim;
deba@728
   101
kpeter@756
   102
  public:
deba@728
   103
kpeter@756
   104
    /// \brief Constructor.
deba@728
   105
    ///
kpeter@756
   106
    /// Constructor.
kpeter@756
   107
    /// \param map A map that assigns \c int values to the items.
kpeter@756
   108
    /// It is used internally to handle the cross references.
kpeter@756
   109
    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
kpeter@756
   110
    /// \param minimum The initial minimum value of the heap.
kpeter@756
   111
    /// \param capacity The initial capacity of the heap.
kpeter@756
   112
    RadixHeap(ItemIntMap &map, int minimum = 0, int capacity = 0)
kpeter@756
   113
      : _iim(map)
kpeter@756
   114
    {
kpeter@758
   115
      _boxes.push_back(RadixBox(minimum, 1));
kpeter@758
   116
      _boxes.push_back(RadixBox(minimum + 1, 1));
kpeter@758
   117
      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
deba@728
   118
        extend();
deba@728
   119
      }
deba@728
   120
    }
deba@728
   121
kpeter@756
   122
    /// \brief The number of items stored in the heap.
deba@728
   123
    ///
kpeter@756
   124
    /// This function returns the number of items stored in the heap.
kpeter@758
   125
    int size() const { return _data.size(); }
kpeter@756
   126
kpeter@756
   127
    /// \brief Check if the heap is empty.
deba@728
   128
    ///
kpeter@756
   129
    /// This function returns \c true if the heap is empty.
kpeter@758
   130
    bool empty() const { return _data.empty(); }
deba@728
   131
kpeter@756
   132
    /// \brief Make the heap empty.
deba@728
   133
    ///
kpeter@756
   134
    /// This functon makes the heap empty.
kpeter@756
   135
    /// It does not change the cross reference map. If you want to reuse
kpeter@756
   136
    /// a heap that is not surely empty, you should first clear it and
kpeter@756
   137
    /// then you should set the cross reference map to \c PRE_HEAP
kpeter@756
   138
    /// for each item.
kpeter@756
   139
    /// \param minimum The minimum value of the heap.
kpeter@756
   140
    /// \param capacity The capacity of the heap.
kpeter@756
   141
    void clear(int minimum = 0, int capacity = 0) {
kpeter@758
   142
      _data.clear(); _boxes.clear();
kpeter@758
   143
      _boxes.push_back(RadixBox(minimum, 1));
kpeter@758
   144
      _boxes.push_back(RadixBox(minimum + 1, 1));
kpeter@758
   145
      while (lower(_boxes.size() - 1, capacity + minimum - 1)) {
deba@728
   146
        extend();
deba@728
   147
      }
deba@728
   148
    }
deba@728
   149
deba@728
   150
  private:
deba@728
   151
deba@728
   152
    bool upper(int box, Prio pr) {
kpeter@758
   153
      return pr < _boxes[box].min;
deba@728
   154
    }
deba@728
   155
deba@728
   156
    bool lower(int box, Prio pr) {
kpeter@758
   157
      return pr >= _boxes[box].min + _boxes[box].size;
deba@728
   158
    }
deba@728
   159
kpeter@756
   160
    // Remove item from the box list
deba@728
   161
    void remove(int index) {
kpeter@758
   162
      if (_data[index].prev >= 0) {
kpeter@758
   163
        _data[_data[index].prev].next = _data[index].next;
deba@728
   164
      } else {
kpeter@758
   165
        _boxes[_data[index].box].first = _data[index].next;
deba@728
   166
      }
kpeter@758
   167
      if (_data[index].next >= 0) {
kpeter@758
   168
        _data[_data[index].next].prev = _data[index].prev;
deba@728
   169
      }
deba@728
   170
    }
deba@728
   171
kpeter@756
   172
    // Insert item into the box list
deba@728
   173
    void insert(int box, int index) {
kpeter@758
   174
      if (_boxes[box].first == -1) {
kpeter@758
   175
        _boxes[box].first = index;
kpeter@758
   176
        _data[index].next = _data[index].prev = -1;
deba@728
   177
      } else {
kpeter@758
   178
        _data[index].next = _boxes[box].first;
kpeter@758
   179
        _data[_boxes[box].first].prev = index;
kpeter@758
   180
        _data[index].prev = -1;
kpeter@758
   181
        _boxes[box].first = index;
deba@728
   182
      }
kpeter@758
   183
      _data[index].box = box;
deba@728
   184
    }
deba@728
   185
kpeter@756
   186
    // Add a new box to the box list
deba@728
   187
    void extend() {
kpeter@758
   188
      int min = _boxes.back().min + _boxes.back().size;
kpeter@758
   189
      int bs = 2 * _boxes.back().size;
kpeter@758
   190
      _boxes.push_back(RadixBox(min, bs));
deba@728
   191
    }
deba@728
   192
kpeter@756
   193
    // Move an item up into the proper box.
kpeter@758
   194
    void bubbleUp(int index) {
kpeter@758
   195
      if (!lower(_data[index].box, _data[index].prio)) return;
deba@728
   196
      remove(index);
kpeter@758
   197
      int box = findUp(_data[index].box, _data[index].prio);
deba@728
   198
      insert(box, index);
deba@728
   199
    }
deba@728
   200
kpeter@756
   201
    // Find up the proper box for the item with the given priority
deba@728
   202
    int findUp(int start, int pr) {
deba@728
   203
      while (lower(start, pr)) {
kpeter@758
   204
        if (++start == int(_boxes.size())) {
deba@728
   205
          extend();
deba@728
   206
        }
deba@728
   207
      }
deba@728
   208
      return start;
deba@728
   209
    }
deba@728
   210
kpeter@756
   211
    // Move an item down into the proper box
kpeter@758
   212
    void bubbleDown(int index) {
kpeter@758
   213
      if (!upper(_data[index].box, _data[index].prio)) return;
deba@728
   214
      remove(index);
kpeter@758
   215
      int box = findDown(_data[index].box, _data[index].prio);
deba@728
   216
      insert(box, index);
deba@728
   217
    }
deba@728
   218
kpeter@756
   219
    // Find down the proper box for the item with the given priority
deba@728
   220
    int findDown(int start, int pr) {
deba@728
   221
      while (upper(start, pr)) {
kpeter@758
   222
        if (--start < 0) throw PriorityUnderflowError();
deba@728
   223
      }
deba@728
   224
      return start;
deba@728
   225
    }
deba@728
   226
kpeter@756
   227
    // Find the first non-empty box
deba@728
   228
    int findFirst() {
deba@728
   229
      int first = 0;
kpeter@758
   230
      while (_boxes[first].first == -1) ++first;
deba@728
   231
      return first;
deba@728
   232
    }
deba@728
   233
kpeter@756
   234
    // Gives back the minimum priority of the given box
deba@728
   235
    int minValue(int box) {
kpeter@758
   236
      int min = _data[_boxes[box].first].prio;
kpeter@758
   237
      for (int k = _boxes[box].first; k != -1; k = _data[k].next) {
kpeter@758
   238
        if (_data[k].prio < min) min = _data[k].prio;
deba@728
   239
      }
deba@728
   240
      return min;
deba@728
   241
    }
deba@728
   242
kpeter@756
   243
    // Rearrange the items of the heap and make the first box non-empty
deba@728
   244
    void moveDown() {
deba@728
   245
      int box = findFirst();
deba@728
   246
      if (box == 0) return;
deba@728
   247
      int min = minValue(box);
deba@728
   248
      for (int i = 0; i <= box; ++i) {
kpeter@758
   249
        _boxes[i].min = min;
kpeter@758
   250
        min += _boxes[i].size;
deba@728
   251
      }
kpeter@758
   252
      int curr = _boxes[box].first, next;
deba@728
   253
      while (curr != -1) {
kpeter@758
   254
        next = _data[curr].next;
kpeter@758
   255
        bubbleDown(curr);
deba@728
   256
        curr = next;
deba@728
   257
      }
deba@728
   258
    }
deba@728
   259
kpeter@758
   260
    void relocateLast(int index) {
kpeter@758
   261
      if (index != int(_data.size()) - 1) {
kpeter@758
   262
        _data[index] = _data.back();
kpeter@758
   263
        if (_data[index].prev != -1) {
kpeter@758
   264
          _data[_data[index].prev].next = index;
deba@728
   265
        } else {
kpeter@758
   266
          _boxes[_data[index].box].first = index;
deba@728
   267
        }
kpeter@758
   268
        if (_data[index].next != -1) {
kpeter@758
   269
          _data[_data[index].next].prev = index;
deba@728
   270
        }
kpeter@758
   271
        _iim[_data[index].item] = index;
deba@728
   272
      }
kpeter@758
   273
      _data.pop_back();
deba@728
   274
    }
deba@728
   275
deba@728
   276
  public:
deba@728
   277
deba@728
   278
    /// \brief Insert an item into the heap with the given priority.
deba@728
   279
    ///
kpeter@756
   280
    /// This function inserts the given item into the heap with the
kpeter@756
   281
    /// given priority.
deba@728
   282
    /// \param i The item to insert.
deba@728
   283
    /// \param p The priority of the item.
kpeter@756
   284
    /// \pre \e i must not be stored in the heap.
kpeter@756
   285
    /// \warning This method may throw an \c UnderFlowPriorityException.
deba@728
   286
    void push(const Item &i, const Prio &p) {
kpeter@758
   287
      int n = _data.size();
deba@730
   288
      _iim.set(i, n);
kpeter@758
   289
      _data.push_back(RadixItem(i, p));
kpeter@758
   290
      while (lower(_boxes.size() - 1, p)) {
deba@728
   291
        extend();
deba@728
   292
      }
kpeter@758
   293
      int box = findDown(_boxes.size() - 1, p);
deba@728
   294
      insert(box, n);
deba@728
   295
    }
deba@728
   296
kpeter@756
   297
    /// \brief Return the item having minimum priority.
deba@728
   298
    ///
kpeter@756
   299
    /// This function returns the item having minimum priority.
kpeter@756
   300
    /// \pre The heap must be non-empty.
deba@728
   301
    Item top() const {
deba@728
   302
      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
kpeter@758
   303
      return _data[_boxes[0].first].item;
deba@728
   304
    }
deba@728
   305
kpeter@756
   306
    /// \brief The minimum priority.
deba@728
   307
    ///
kpeter@756
   308
    /// This function returns the minimum priority.
kpeter@756
   309
    /// \pre The heap must be non-empty.
deba@728
   310
    Prio prio() const {
deba@728
   311
      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
kpeter@758
   312
      return _data[_boxes[0].first].prio;
deba@728
   313
     }
deba@728
   314
kpeter@756
   315
    /// \brief Remove the item having minimum priority.
deba@728
   316
    ///
kpeter@756
   317
    /// This function removes the item having minimum priority.
deba@728
   318
    /// \pre The heap must be non-empty.
deba@728
   319
    void pop() {
deba@728
   320
      moveDown();
kpeter@758
   321
      int index = _boxes[0].first;
kpeter@758
   322
      _iim[_data[index].item] = POST_HEAP;
deba@728
   323
      remove(index);
kpeter@758
   324
      relocateLast(index);
deba@728
   325
    }
deba@728
   326
kpeter@756
   327
    /// \brief Remove the given item from the heap.
deba@728
   328
    ///
kpeter@756
   329
    /// This function removes the given item from the heap if it is
kpeter@756
   330
    /// already stored.
kpeter@756
   331
    /// \param i The item to delete.
kpeter@756
   332
    /// \pre \e i must be in the heap.
deba@728
   333
    void erase(const Item &i) {
deba@730
   334
      int index = _iim[i];
deba@730
   335
      _iim[i] = POST_HEAP;
deba@728
   336
      remove(index);
kpeter@758
   337
      relocateLast(index);
deba@728
   338
   }
deba@728
   339
kpeter@756
   340
    /// \brief The priority of the given item.
deba@728
   341
    ///
kpeter@756
   342
    /// This function returns the priority of the given item.
deba@728
   343
    /// \param i The item.
kpeter@756
   344
    /// \pre \e i must be in the heap.
deba@728
   345
    Prio operator[](const Item &i) const {
deba@730
   346
      int idx = _iim[i];
kpeter@758
   347
      return _data[idx].prio;
deba@728
   348
    }
deba@728
   349
kpeter@756
   350
    /// \brief Set the priority of an item or insert it, if it is
kpeter@756
   351
    /// not stored in the heap.
deba@728
   352
    ///
kpeter@756
   353
    /// This method sets the priority of the given item if it is
kpeter@756
   354
    /// already stored in the heap. Otherwise it inserts the given
kpeter@756
   355
    /// item into the heap with the given priority.
deba@728
   356
    /// \param i The item.
deba@728
   357
    /// \param p The priority.
kpeter@756
   358
    /// \pre \e i must be in the heap.
kpeter@756
   359
    /// \warning This method may throw an \c UnderFlowPriorityException.
deba@728
   360
    void set(const Item &i, const Prio &p) {
deba@730
   361
      int idx = _iim[i];
deba@728
   362
      if( idx < 0 ) {
deba@728
   363
        push(i, p);
deba@728
   364
      }
kpeter@758
   365
      else if( p >= _data[idx].prio ) {
kpeter@758
   366
        _data[idx].prio = p;
kpeter@758
   367
        bubbleUp(idx);
deba@728
   368
      } else {
kpeter@758
   369
        _data[idx].prio = p;
kpeter@758
   370
        bubbleDown(idx);
deba@728
   371
      }
deba@728
   372
    }
deba@728
   373
kpeter@756
   374
    /// \brief Decrease the priority of an item to the given value.
deba@728
   375
    ///
kpeter@756
   376
    /// This function decreases the priority of an item to the given value.
deba@728
   377
    /// \param i The item.
deba@728
   378
    /// \param p The priority.
kpeter@756
   379
    /// \pre \e i must be stored in the heap with priority at least \e p.
kpeter@756
   380
    /// \warning This method may throw an \c UnderFlowPriorityException.
deba@728
   381
    void decrease(const Item &i, const Prio &p) {
deba@730
   382
      int idx = _iim[i];
kpeter@758
   383
      _data[idx].prio = p;
kpeter@758
   384
      bubbleDown(idx);
deba@728
   385
    }
deba@728
   386
kpeter@756
   387
    /// \brief Increase the priority of an item to the given value.
deba@728
   388
    ///
kpeter@756
   389
    /// This function increases the priority of an item to the given value.
deba@728
   390
    /// \param i The item.
deba@728
   391
    /// \param p The priority.
kpeter@756
   392
    /// \pre \e i must be stored in the heap with priority at most \e p.
deba@728
   393
    void increase(const Item &i, const Prio &p) {
deba@730
   394
      int idx = _iim[i];
kpeter@758
   395
      _data[idx].prio = p;
kpeter@758
   396
      bubbleUp(idx);
deba@728
   397
    }
deba@728
   398
kpeter@756
   399
    /// \brief Return the state of an item.
deba@728
   400
    ///
kpeter@756
   401
    /// This method returns \c PRE_HEAP if the given item has never
kpeter@756
   402
    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
kpeter@756
   403
    /// and \c POST_HEAP otherwise.
kpeter@756
   404
    /// In the latter case it is possible that the item will get back
kpeter@756
   405
    /// to the heap again.
deba@728
   406
    /// \param i The item.
deba@728
   407
    State state(const Item &i) const {
deba@730
   408
      int s = _iim[i];
deba@728
   409
      if( s >= 0 ) s = 0;
deba@728
   410
      return State(s);
deba@728
   411
    }
deba@728
   412
kpeter@756
   413
    /// \brief Set the state of an item in the heap.
deba@728
   414
    ///
kpeter@756
   415
    /// This function sets the state of the given item in the heap.
kpeter@756
   416
    /// It can be used to manually clear the heap when it is important
kpeter@756
   417
    /// to achive better time complexity.
deba@728
   418
    /// \param i The item.
deba@728
   419
    /// \param st The state. It should not be \c IN_HEAP.
deba@728
   420
    void state(const Item& i, State st) {
deba@728
   421
      switch (st) {
deba@728
   422
      case POST_HEAP:
deba@728
   423
      case PRE_HEAP:
deba@728
   424
        if (state(i) == IN_HEAP) {
deba@728
   425
          erase(i);
deba@728
   426
        }
deba@730
   427
        _iim[i] = st;
deba@728
   428
        break;
deba@728
   429
      case IN_HEAP:
deba@728
   430
        break;
deba@728
   431
      }
deba@728
   432
    }
deba@728
   433
deba@728
   434
  }; // class RadixHeap
deba@728
   435
deba@728
   436
} // namespace lemon
deba@728
   437
deba@728
   438
#endif // LEMON_RADIX_HEAP_H