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