lemon/radix_heap.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 05 Nov 2009 10:01:02 +0100
changeset 779 c160bf9f18ef
parent 681 532697c9fa53
child 709 0747f332c478
permissions -rw-r--r--
Merge
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
deba@681
    22
///\ingroup auxdat
deba@681
    23
///\file
deba@681
    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
deba@681
    32
  /// \ingroup auxdata
deba@681
    33
  ///
deba@681
    34
  /// \brief A Radix Heap implementation.
deba@681
    35
  ///
deba@681
    36
  /// This class implements the \e radix \e heap data structure. A \e heap
deba@681
    37
  /// is a data structure for storing items with specified values called \e
deba@681
    38
  /// priorities in such a way that finding the item with minimum priority is
deba@681
    39
  /// efficient. This heap type can store only items with \e int priority.
deba@681
    40
  /// In a heap one can change the priority of an item, add or erase an
deba@681
    41
  /// item, but the priority cannot be decreased under the last removed
deba@681
    42
  /// item's priority.
deba@681
    43
  ///
deba@683
    44
  /// \param IM A read and writable Item int map, used internally
deba@681
    45
  /// to handle the cross references.
deba@681
    46
  ///
deba@681
    47
  /// \see BinHeap
deba@681
    48
  /// \see Dijkstra
deba@683
    49
  template <typename IM>
deba@681
    50
  class RadixHeap {
deba@681
    51
deba@681
    52
  public:
deba@683
    53
    typedef typename IM::Key Item;
deba@681
    54
    typedef int Prio;
deba@683
    55
    typedef IM ItemIntMap;
deba@681
    56
deba@681
    57
    /// \brief Exception thrown by RadixHeap.
deba@681
    58
    ///
deba@681
    59
    /// This Exception is thrown when a smaller priority
deba@681
    60
    /// is inserted into the \e RadixHeap then the last time erased.
deba@681
    61
    /// \see RadixHeap
deba@681
    62
deba@681
    63
    class UnderFlowPriorityError : public Exception {
deba@681
    64
    public:
deba@681
    65
      virtual const char* what() const throw() {
deba@681
    66
        return "lemon::RadixHeap::UnderFlowPriorityError";
deba@681
    67
      }
deba@681
    68
    };
deba@681
    69
deba@681
    70
    /// \brief Type to represent the items states.
deba@681
    71
    ///
deba@681
    72
    /// Each Item element have a state associated to it. It may be "in heap",
deba@681
    73
    /// "pre heap" or "post heap". The latter two are indifferent from the
deba@681
    74
    /// heap's point of view, but may be useful to the user.
deba@681
    75
    ///
deba@681
    76
    /// The ItemIntMap \e should be initialized in such way that it maps
deba@681
    77
    /// PRE_HEAP (-1) to any element to be put in the heap...
deba@681
    78
    enum State {
deba@681
    79
      IN_HEAP = 0,
deba@681
    80
      PRE_HEAP = -1,
deba@681
    81
      POST_HEAP = -2
deba@681
    82
    };
deba@681
    83
deba@681
    84
  private:
deba@681
    85
deba@681
    86
    struct RadixItem {
deba@681
    87
      int prev, next, box;
deba@681
    88
      Item item;
deba@681
    89
      int prio;
deba@681
    90
      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
deba@681
    91
    };
deba@681
    92
deba@681
    93
    struct RadixBox {
deba@681
    94
      int first;
deba@681
    95
      int min, size;
deba@681
    96
      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
deba@681
    97
    };
deba@681
    98
deba@681
    99
    std::vector<RadixItem> data;
deba@681
   100
    std::vector<RadixBox> boxes;
deba@681
   101
deba@683
   102
    ItemIntMap &_iim;
deba@681
   103
deba@681
   104
deba@681
   105
  public:
deba@681
   106
    /// \brief The constructor.
deba@681
   107
    ///
deba@681
   108
    /// The constructor.
deba@681
   109
    ///
deba@683
   110
    /// \param map It should be given to the constructor, since it is used
deba@681
   111
    /// internally to handle the cross references. The value of the map
deba@681
   112
    /// should be PRE_HEAP (-1) for each element.
deba@681
   113
    ///
deba@681
   114
    /// \param minimal The initial minimal value of the heap.
deba@681
   115
    /// \param capacity It determines the initial capacity of the heap.
deba@683
   116
    RadixHeap(ItemIntMap &map, int minimal = 0, int capacity = 0)
deba@683
   117
      : _iim(map) {
deba@681
   118
      boxes.push_back(RadixBox(minimal, 1));
deba@681
   119
      boxes.push_back(RadixBox(minimal + 1, 1));
deba@681
   120
      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
deba@681
   121
        extend();
deba@681
   122
      }
deba@681
   123
    }
deba@681
   124
deba@681
   125
    /// The number of items stored in the heap.
deba@681
   126
    ///
deba@681
   127
    /// \brief Returns the number of items stored in the heap.
deba@681
   128
    int size() const { return data.size(); }
deba@681
   129
    /// \brief Checks if the heap stores no items.
deba@681
   130
    ///
deba@681
   131
    /// Returns \c true if and only if the heap stores no items.
deba@681
   132
    bool empty() const { return data.empty(); }
deba@681
   133
deba@681
   134
    /// \brief Make empty this heap.
deba@681
   135
    ///
deba@681
   136
    /// Make empty this heap. It does not change the cross reference
deba@681
   137
    /// map.  If you want to reuse a heap what is not surely empty you
deba@681
   138
    /// should first clear the heap and after that you should set the
deba@681
   139
    /// cross reference map for each item to \c PRE_HEAP.
deba@681
   140
    void clear(int minimal = 0, int capacity = 0) {
deba@681
   141
      data.clear(); boxes.clear();
deba@681
   142
      boxes.push_back(RadixBox(minimal, 1));
deba@681
   143
      boxes.push_back(RadixBox(minimal + 1, 1));
deba@681
   144
      while (lower(boxes.size() - 1, capacity + minimal - 1)) {
deba@681
   145
        extend();
deba@681
   146
      }
deba@681
   147
    }
deba@681
   148
deba@681
   149
  private:
deba@681
   150
deba@681
   151
    bool upper(int box, Prio pr) {
deba@681
   152
      return pr < boxes[box].min;
deba@681
   153
    }
deba@681
   154
deba@681
   155
    bool lower(int box, Prio pr) {
deba@681
   156
      return pr >= boxes[box].min + boxes[box].size;
deba@681
   157
    }
deba@681
   158
deba@681
   159
    /// \brief Remove item from the box list.
deba@681
   160
    void remove(int index) {
deba@681
   161
      if (data[index].prev >= 0) {
deba@681
   162
        data[data[index].prev].next = data[index].next;
deba@681
   163
      } else {
deba@681
   164
        boxes[data[index].box].first = data[index].next;
deba@681
   165
      }
deba@681
   166
      if (data[index].next >= 0) {
deba@681
   167
        data[data[index].next].prev = data[index].prev;
deba@681
   168
      }
deba@681
   169
    }
deba@681
   170
deba@681
   171
    /// \brief Insert item into the box list.
deba@681
   172
    void insert(int box, int index) {
deba@681
   173
      if (boxes[box].first == -1) {
deba@681
   174
        boxes[box].first = index;
deba@681
   175
        data[index].next = data[index].prev = -1;
deba@681
   176
      } else {
deba@681
   177
        data[index].next = boxes[box].first;
deba@681
   178
        data[boxes[box].first].prev = index;
deba@681
   179
        data[index].prev = -1;
deba@681
   180
        boxes[box].first = index;
deba@681
   181
      }
deba@681
   182
      data[index].box = box;
deba@681
   183
    }
deba@681
   184
deba@681
   185
    /// \brief Add a new box to the box list.
deba@681
   186
    void extend() {
deba@681
   187
      int min = boxes.back().min + boxes.back().size;
deba@681
   188
      int bs = 2 * boxes.back().size;
deba@681
   189
      boxes.push_back(RadixBox(min, bs));
deba@681
   190
    }
deba@681
   191
deba@681
   192
    /// \brief Move an item up into the proper box.
deba@681
   193
    void bubble_up(int index) {
deba@681
   194
      if (!lower(data[index].box, data[index].prio)) return;
deba@681
   195
      remove(index);
deba@681
   196
      int box = findUp(data[index].box, data[index].prio);
deba@681
   197
      insert(box, index);
deba@681
   198
    }
deba@681
   199
deba@681
   200
    /// \brief Find up the proper box for the item with the given prio.
deba@681
   201
    int findUp(int start, int pr) {
deba@681
   202
      while (lower(start, pr)) {
deba@681
   203
        if (++start == int(boxes.size())) {
deba@681
   204
          extend();
deba@681
   205
        }
deba@681
   206
      }
deba@681
   207
      return start;
deba@681
   208
    }
deba@681
   209
deba@681
   210
    /// \brief Move an item down into the proper box.
deba@681
   211
    void bubble_down(int index) {
deba@681
   212
      if (!upper(data[index].box, data[index].prio)) return;
deba@681
   213
      remove(index);
deba@681
   214
      int box = findDown(data[index].box, data[index].prio);
deba@681
   215
      insert(box, index);
deba@681
   216
    }
deba@681
   217
deba@681
   218
    /// \brief Find up the proper box for the item with the given prio.
deba@681
   219
    int findDown(int start, int pr) {
deba@681
   220
      while (upper(start, pr)) {
deba@681
   221
        if (--start < 0) throw UnderFlowPriorityError();
deba@681
   222
      }
deba@681
   223
      return start;
deba@681
   224
    }
deba@681
   225
deba@681
   226
    /// \brief Find the first not empty box.
deba@681
   227
    int findFirst() {
deba@681
   228
      int first = 0;
deba@681
   229
      while (boxes[first].first == -1) ++first;
deba@681
   230
      return first;
deba@681
   231
    }
deba@681
   232
deba@681
   233
    /// \brief Gives back the minimal prio of the box.
deba@681
   234
    int minValue(int box) {
deba@681
   235
      int min = data[boxes[box].first].prio;
deba@681
   236
      for (int k = boxes[box].first; k != -1; k = data[k].next) {
deba@681
   237
        if (data[k].prio < min) min = data[k].prio;
deba@681
   238
      }
deba@681
   239
      return min;
deba@681
   240
    }
deba@681
   241
deba@681
   242
    /// \brief Rearrange the items of the heap and makes the
deba@681
   243
    /// first box not 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) {
deba@681
   249
        boxes[i].min = min;
deba@681
   250
        min += boxes[i].size;
deba@681
   251
      }
deba@681
   252
      int curr = boxes[box].first, next;
deba@681
   253
      while (curr != -1) {
deba@681
   254
        next = data[curr].next;
deba@681
   255
        bubble_down(curr);
deba@681
   256
        curr = next;
deba@681
   257
      }
deba@681
   258
    }
deba@681
   259
deba@681
   260
    void relocate_last(int index) {
deba@681
   261
      if (index != int(data.size()) - 1) {
deba@681
   262
        data[index] = data.back();
deba@681
   263
        if (data[index].prev != -1) {
deba@681
   264
          data[data[index].prev].next = index;
deba@681
   265
        } else {
deba@681
   266
          boxes[data[index].box].first = index;
deba@681
   267
        }
deba@681
   268
        if (data[index].next != -1) {
deba@681
   269
          data[data[index].next].prev = index;
deba@681
   270
        }
deba@683
   271
        _iim[data[index].item] = index;
deba@681
   272
      }
deba@681
   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
    ///
deba@681
   280
    /// Adds \c i to the heap with priority \c p.
deba@681
   281
    /// \param i The item to insert.
deba@681
   282
    /// \param p The priority of the item.
deba@681
   283
    void push(const Item &i, const Prio &p) {
deba@681
   284
      int n = data.size();
deba@683
   285
      _iim.set(i, n);
deba@681
   286
      data.push_back(RadixItem(i, p));
deba@681
   287
      while (lower(boxes.size() - 1, p)) {
deba@681
   288
        extend();
deba@681
   289
      }
deba@681
   290
      int box = findDown(boxes.size() - 1, p);
deba@681
   291
      insert(box, n);
deba@681
   292
    }
deba@681
   293
deba@681
   294
    /// \brief Returns the item with minimum priority.
deba@681
   295
    ///
deba@681
   296
    /// This method returns the item with minimum priority.
deba@681
   297
    /// \pre The heap must be nonempty.
deba@681
   298
    Item top() const {
deba@681
   299
      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
deba@681
   300
      return data[boxes[0].first].item;
deba@681
   301
    }
deba@681
   302
deba@681
   303
    /// \brief Returns the minimum priority.
deba@681
   304
    ///
deba@681
   305
    /// It returns the minimum priority.
deba@681
   306
    /// \pre The heap must be nonempty.
deba@681
   307
    Prio prio() const {
deba@681
   308
      const_cast<RadixHeap<ItemIntMap>&>(*this).moveDown();
deba@681
   309
      return data[boxes[0].first].prio;
deba@681
   310
     }
deba@681
   311
deba@681
   312
    /// \brief Deletes the item with minimum priority.
deba@681
   313
    ///
deba@681
   314
    /// This method deletes the item with minimum priority.
deba@681
   315
    /// \pre The heap must be non-empty.
deba@681
   316
    void pop() {
deba@681
   317
      moveDown();
deba@681
   318
      int index = boxes[0].first;
deba@683
   319
      _iim[data[index].item] = POST_HEAP;
deba@681
   320
      remove(index);
deba@681
   321
      relocate_last(index);
deba@681
   322
    }
deba@681
   323
deba@681
   324
    /// \brief Deletes \c i from the heap.
deba@681
   325
    ///
deba@681
   326
    /// This method deletes item \c i from the heap, if \c i was
deba@681
   327
    /// already stored in the heap.
deba@681
   328
    /// \param i The item to erase.
deba@681
   329
    void erase(const Item &i) {
deba@683
   330
      int index = _iim[i];
deba@683
   331
      _iim[i] = POST_HEAP;
deba@681
   332
      remove(index);
deba@681
   333
      relocate_last(index);
deba@681
   334
   }
deba@681
   335
deba@681
   336
    /// \brief Returns the priority of \c i.
deba@681
   337
    ///
deba@681
   338
    /// This function returns the priority of item \c i.
deba@681
   339
    /// \pre \c i must be in the heap.
deba@681
   340
    /// \param i The item.
deba@681
   341
    Prio operator[](const Item &i) const {
deba@683
   342
      int idx = _iim[i];
deba@681
   343
      return data[idx].prio;
deba@681
   344
    }
deba@681
   345
deba@681
   346
    /// \brief \c i gets to the heap with priority \c p independently
deba@681
   347
    /// if \c i was already there.
deba@681
   348
    ///
deba@681
   349
    /// This method calls \ref push(\c i, \c p) if \c i is not stored
deba@681
   350
    /// in the heap and sets the priority of \c i to \c p otherwise.
deba@681
   351
    /// It may throw an \e UnderFlowPriorityException.
deba@681
   352
    /// \param i The item.
deba@681
   353
    /// \param p The priority.
deba@681
   354
    void set(const Item &i, const Prio &p) {
deba@683
   355
      int idx = _iim[i];
deba@681
   356
      if( idx < 0 ) {
deba@681
   357
        push(i, p);
deba@681
   358
      }
deba@681
   359
      else if( p >= data[idx].prio ) {
deba@681
   360
        data[idx].prio = p;
deba@681
   361
        bubble_up(idx);
deba@681
   362
      } else {
deba@681
   363
        data[idx].prio = p;
deba@681
   364
        bubble_down(idx);
deba@681
   365
      }
deba@681
   366
    }
deba@681
   367
deba@681
   368
deba@681
   369
    /// \brief Decreases the priority of \c i to \c p.
deba@681
   370
    ///
deba@681
   371
    /// This method decreases the priority of item \c i to \c p.
deba@681
   372
    /// \pre \c i must be stored in the heap with priority at least \c p, and
deba@681
   373
    /// \c should be greater or equal to the last removed item's priority.
deba@681
   374
    /// \param i The item.
deba@681
   375
    /// \param p The priority.
deba@681
   376
    void decrease(const Item &i, const Prio &p) {
deba@683
   377
      int idx = _iim[i];
deba@681
   378
      data[idx].prio = p;
deba@681
   379
      bubble_down(idx);
deba@681
   380
    }
deba@681
   381
deba@681
   382
    /// \brief Increases the priority of \c i to \c p.
deba@681
   383
    ///
deba@681
   384
    /// This method sets the priority of item \c i to \c p.
deba@681
   385
    /// \pre \c i must be stored in the heap with priority at most \c p
deba@681
   386
    /// \param i The item.
deba@681
   387
    /// \param p The priority.
deba@681
   388
    void increase(const Item &i, const Prio &p) {
deba@683
   389
      int idx = _iim[i];
deba@681
   390
      data[idx].prio = p;
deba@681
   391
      bubble_up(idx);
deba@681
   392
    }
deba@681
   393
deba@681
   394
    /// \brief Returns if \c item is in, has already been in, or has
deba@681
   395
    /// never been in the heap.
deba@681
   396
    ///
deba@681
   397
    /// This method returns PRE_HEAP if \c item has never been in the
deba@681
   398
    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
deba@681
   399
    /// otherwise. In the latter case it is possible that \c item will
deba@681
   400
    /// get back to the heap again.
deba@681
   401
    /// \param i The item.
deba@681
   402
    State state(const Item &i) const {
deba@683
   403
      int s = _iim[i];
deba@681
   404
      if( s >= 0 ) s = 0;
deba@681
   405
      return State(s);
deba@681
   406
    }
deba@681
   407
deba@681
   408
    /// \brief Sets the state of the \c item in the heap.
deba@681
   409
    ///
deba@681
   410
    /// Sets the state of the \c item in the heap. It can be used to
deba@681
   411
    /// manually clear the heap when it is important to achive the
deba@681
   412
    /// better time complexity.
deba@681
   413
    /// \param i The item.
deba@681
   414
    /// \param st The state. It should not be \c IN_HEAP.
deba@681
   415
    void state(const Item& i, State st) {
deba@681
   416
      switch (st) {
deba@681
   417
      case POST_HEAP:
deba@681
   418
      case PRE_HEAP:
deba@681
   419
        if (state(i) == IN_HEAP) {
deba@681
   420
          erase(i);
deba@681
   421
        }
deba@683
   422
        _iim[i] = st;
deba@681
   423
        break;
deba@681
   424
      case IN_HEAP:
deba@681
   425
        break;
deba@681
   426
      }
deba@681
   427
    }
deba@681
   428
deba@681
   429
  }; // class RadixHeap
deba@681
   430
deba@681
   431
} // namespace lemon
deba@681
   432
deba@681
   433
#endif // LEMON_RADIX_HEAP_H