src/lemon/radix_heap.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
child 1205 a9a3354b01d4
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
deba@1186
     1
/* -*- C++ -*-
deba@1186
     2
 * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library
deba@1186
     3
 *
deba@1186
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1186
     5
 * (Egervary Combinatorial Optimization Research Group, EGRES).
deba@1186
     6
 *
deba@1186
     7
 * Permission to use, modify and distribute this software is granted
deba@1186
     8
 * provided that this copyright notice appears in all copies. For
deba@1186
     9
 * precise terms see the accompanying LICENSE file.
deba@1186
    10
 *
deba@1186
    11
 * This software is provided "AS IS" with no warranty of any kind,
deba@1186
    12
 * express or implied, and with no claim as to its suitability for any
deba@1186
    13
 * purpose.
deba@1186
    14
 *
deba@1186
    15
 */
deba@1186
    16
deba@1186
    17
#ifndef LEMON_RADIX_HEAP_H
deba@1186
    18
#define LEMON_RADIX_HEAP_H
deba@1186
    19
deba@1186
    20
///\ingroup auxdat
deba@1186
    21
///\file
deba@1186
    22
///\brief Radix Heap implementation.
deba@1186
    23
///\todo It should be documented.
deba@1186
    24
deba@1186
    25
#include <vector>
deba@1186
    26
#include <lemon/error.h>
deba@1186
    27
deba@1186
    28
namespace lemon {
deba@1186
    29
deba@1186
    30
  /// \addtogroup auxdat
deba@1186
    31
  /// @{
deba@1186
    32
deba@1186
    33
   /// A Binary Heap implementation.
deba@1186
    34
  
deba@1186
    35
  ///\todo Please document...
deba@1186
    36
  ///
deba@1186
    37
  ///\sa BinHeap
deba@1186
    38
  ///\sa Dijkstra
deba@1186
    39
deba@1186
    40
  class UnderFlowPriorityException : public RuntimeError {
deba@1186
    41
  public:
deba@1186
    42
    virtual const char* exceptionName() const {
deba@1186
    43
      return "lemon::UnderFlowPriorityException";
deba@1186
    44
    }  
deba@1186
    45
  };
deba@1186
    46
deba@1186
    47
  template <typename _Item, typename _ItemIntMap>
deba@1186
    48
  class RadixHeap {
deba@1186
    49
deba@1186
    50
  public:
deba@1186
    51
    typedef _Item Item;
deba@1186
    52
    // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
deba@1186
    53
    typedef int Prio;
deba@1186
    54
    typedef _ItemIntMap ItemIntMap;
deba@1186
    55
deba@1186
    56
    /**
deba@1186
    57
     * Each Item element have a state associated to it. It may be "in heap",
deba@1186
    58
     * "pre heap" or "post heap". The later two are indifferent from the
deba@1186
    59
     * heap's point of view, but may be useful to the user.
deba@1186
    60
     *
deba@1186
    61
     * The ItemIntMap _should_ be initialized in such way, that it maps
deba@1186
    62
     * PRE_HEAP (-1) to any element to be put in the heap...
deba@1186
    63
     */
deba@1186
    64
    ///\todo it is used nowhere
deba@1186
    65
    ///
deba@1186
    66
    enum state_enum {
deba@1186
    67
      IN_HEAP = 0,
deba@1186
    68
      PRE_HEAP = -1,
deba@1186
    69
      POST_HEAP = -2
deba@1186
    70
    };
deba@1186
    71
deba@1186
    72
  private:
deba@1186
    73
    
deba@1186
    74
    struct RadixItem {
deba@1186
    75
      int prev, next, box;
deba@1186
    76
      Item item;
deba@1186
    77
      int prio;
deba@1186
    78
      RadixItem(Item _item, int _prio) : item(_item), prio(_prio) {}
deba@1186
    79
    };
deba@1186
    80
deba@1186
    81
    struct RadixBox {
deba@1186
    82
      int first;
deba@1186
    83
      int min, size;
deba@1186
    84
      RadixBox(int _min, int _size) : first(-1), min(_min), size(_size) {}
deba@1186
    85
    };
deba@1186
    86
deba@1186
    87
    std::vector<RadixItem> data;
deba@1186
    88
    std::vector<RadixBox> boxes;
deba@1186
    89
deba@1186
    90
    ItemIntMap &iim;
deba@1186
    91
deba@1186
    92
deba@1186
    93
  public:
deba@1186
    94
    ///\e
deba@1186
    95
    explicit RadixHeap(ItemIntMap &_iim) : iim(_iim) {
deba@1186
    96
      boxes.push_back(RadixBox(0, 1));
deba@1186
    97
      boxes.push_back(RadixBox(1, 1));
deba@1186
    98
    }
deba@1186
    99
deba@1186
   100
    ///\e
deba@1186
   101
    RadixHeap(ItemIntMap &_iim, int capacity) : iim(_iim) {
deba@1186
   102
      boxes.push_back(RadixBox(0, 1));
deba@1186
   103
      boxes.push_back(RadixBox(1, 1));
deba@1186
   104
      while (upper(boxes.back(), capacity)) {
deba@1186
   105
	extend();
deba@1186
   106
      }
deba@1186
   107
    }
deba@1186
   108
deba@1186
   109
    ///\e
deba@1186
   110
    int size() const { return data.size(); }
deba@1186
   111
    ///\e
deba@1186
   112
    bool empty() const { return data.empty(); }
deba@1186
   113
deba@1186
   114
  private:
deba@1186
   115
deba@1186
   116
    bool upper(int box, Prio prio) {
deba@1186
   117
      return prio < boxes[box].min;
deba@1186
   118
    }
deba@1186
   119
deba@1186
   120
    bool lower(int box, Prio prio) {
deba@1186
   121
      return prio >= boxes[box].min + boxes[box].size;
deba@1186
   122
    }
deba@1186
   123
deba@1186
   124
    /// \brief Remove item from the box list.
deba@1186
   125
    void remove(int index) {
deba@1186
   126
      if (data[index].prev >= 0) {
deba@1186
   127
	data[data[index].prev].next = data[index].next;
deba@1186
   128
      } else {
deba@1186
   129
	boxes[data[index].box].first = data[index].next;
deba@1186
   130
      }
deba@1186
   131
      if (data[index].next >= 0) {
deba@1186
   132
	data[data[index].next].prev = data[index].prev;
deba@1186
   133
      }
deba@1186
   134
    }
deba@1186
   135
deba@1186
   136
    /// \brief Insert item into the box list.
deba@1186
   137
    void insert(int box, int index) {
deba@1186
   138
      if (boxes[box].first == -1) {
deba@1186
   139
	boxes[box].first = index;
deba@1186
   140
	data[index].next = data[index].prev = -1;
deba@1186
   141
      } else {
deba@1186
   142
	data[index].next = boxes[box].first;
deba@1186
   143
	data[boxes[box].first].prev = index;
deba@1186
   144
	data[index].prev = -1;
deba@1186
   145
	boxes[box].first = index;
deba@1186
   146
      }
deba@1186
   147
      data[index].box = box;
deba@1186
   148
    }
deba@1186
   149
deba@1186
   150
    /// \brief Add a new box to the box list.
deba@1186
   151
    void extend() {
deba@1186
   152
      int min = boxes.back().min + boxes.back().size;
deba@1186
   153
      int size = 2 * boxes.back().size;
deba@1186
   154
      boxes.push_back(RadixBox(min, size));
deba@1186
   155
    }
deba@1186
   156
deba@1186
   157
    /// \brief Move an item up into the proper box.
deba@1186
   158
    void bubble_up(int index) {
deba@1186
   159
      if (!lower(data[index].box, index)) return;
deba@1186
   160
      remove(index);
deba@1186
   161
      int box = findUp(data[index].box, data[index].prio);
deba@1186
   162
      insert(box, index);      
deba@1186
   163
    }
deba@1186
   164
deba@1186
   165
    /// \brief Find up the proper box for the item with the given prio.
deba@1186
   166
    int findUp(int start, int prio) {
deba@1186
   167
      while (lower(start, prio)) {
deba@1186
   168
	if (++start == (int)boxes.size()) {
deba@1186
   169
	  extend();
deba@1186
   170
	}
deba@1186
   171
      }
deba@1186
   172
      return start;
deba@1186
   173
    }
deba@1186
   174
deba@1186
   175
    /// \brief Move an item down into the proper box.
deba@1186
   176
    void bubble_down(int index) {
deba@1186
   177
      if (!upper(data[index].box, data[index].prio)) return;
deba@1186
   178
      remove(index);
deba@1186
   179
      int box = findDown(data[index].box, data[index].prio);
deba@1186
   180
      insert(box, index);
deba@1186
   181
    }
deba@1186
   182
deba@1186
   183
    /// \brief Find up the proper box for the item with the given prio.
deba@1186
   184
    int findDown(int start, int prio) {
deba@1186
   185
      while (upper(start, prio)) {
deba@1186
   186
	if (--start < 0) throw UnderFlowPriorityException();
deba@1186
   187
      }
deba@1186
   188
      return start;
deba@1186
   189
    }
deba@1186
   190
deba@1186
   191
    /// \brief Find the first not empty box.
deba@1186
   192
    int findFirst() {
deba@1186
   193
      int first = 0;
deba@1186
   194
      while (boxes[first].first == -1) ++first;
deba@1186
   195
      return first;
deba@1186
   196
    }
deba@1186
   197
deba@1186
   198
    /// \brief Gives back the minimal prio of the box.
deba@1186
   199
    int minValue(int box) {
deba@1186
   200
      int min = data[boxes[box].first].prio;
deba@1186
   201
      for (int k = boxes[box].first; k != -1; k = data[k].next) {
deba@1186
   202
	if (data[k].prio < min) min = data[k].prio;
deba@1186
   203
      }
deba@1186
   204
      return min;
deba@1186
   205
    }
deba@1186
   206
deba@1186
   207
    /// \brief Rearrange the items of the heap and makes the 
deba@1186
   208
    /// first box not empty.
deba@1186
   209
    void moveDown() {
deba@1186
   210
      //      print(); printf("moveDown\n"); fflush(stdout);       
deba@1186
   211
      int box = findFirst();
deba@1186
   212
      if (box == 0) return;
deba@1186
   213
      int min = minValue(box);
deba@1186
   214
      for (int i = 0; i <= box; ++i) {
deba@1186
   215
	boxes[i].min = min;
deba@1186
   216
	min += boxes[i].size;
deba@1186
   217
      }
deba@1186
   218
      int curr = boxes[box].first, next;
deba@1186
   219
      while (curr != -1) {
deba@1186
   220
	next = data[curr].next;
deba@1186
   221
	bubble_down(curr);
deba@1186
   222
	curr = next;
deba@1186
   223
      }      
deba@1186
   224
    }
deba@1186
   225
deba@1186
   226
    void relocate_last(int index) {
deba@1186
   227
      if (index != (int)data.size() - 1) {
deba@1186
   228
	data[index] = data.back();
deba@1186
   229
	if (data[index].prev != -1) {
deba@1186
   230
	  data[data[index].prev].next = index;
deba@1186
   231
	} else {
deba@1186
   232
	  boxes[data[index].box].first = index;
deba@1186
   233
	}
deba@1186
   234
	if (data[index].next != -1) {
deba@1186
   235
	  data[data[index].next].prev = index;
deba@1186
   236
	}
deba@1186
   237
	iim[data[index].item] = index;
deba@1186
   238
      }
deba@1186
   239
      data.pop_back();
deba@1186
   240
    }
deba@1186
   241
deba@1186
   242
  public:
deba@1186
   243
deba@1186
   244
    ///\e
deba@1186
   245
    void push(const Item &i, const Prio &p) {
deba@1186
   246
      fflush(stdout);
deba@1186
   247
      int n = data.size();
deba@1186
   248
      iim.set(i, n);
deba@1186
   249
      data.push_back(RadixItem(i, p));
deba@1186
   250
      while (lower(boxes.size() - 1, p)) {
deba@1186
   251
	extend();
deba@1186
   252
      }
deba@1186
   253
      int box = findDown(boxes.size() - 1, p);
deba@1186
   254
      insert(box, n);
deba@1186
   255
      //      printf("Push %d\n", p);
deba@1186
   256
      //print();
deba@1186
   257
    }
deba@1186
   258
deba@1186
   259
    ///\e
deba@1186
   260
    Item top() const {
deba@1186
   261
      //      print(); printf("top\n");  fflush(stdout);
deba@1186
   262
      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
deba@1186
   263
      return data[boxes[0].first].item;
deba@1186
   264
      //      print(); printf("top_end\n");  fflush(stdout);
deba@1186
   265
    }
deba@1186
   266
deba@1186
   267
    /// Returns the prio of the top element of the heap.
deba@1186
   268
    Prio prio() const {
deba@1186
   269
      //      print(); printf("prio\n"); fflush(stdout);
deba@1186
   270
      const_cast<RadixHeap<Item, ItemIntMap>*>(this)->moveDown();
deba@1186
   271
      return data[boxes[0].first].prio;
deba@1186
   272
     }
deba@1186
   273
deba@1186
   274
    ///\e
deba@1186
   275
    void pop() {
deba@1186
   276
      //      print(); printf("pop\n"); fflush(stdout);
deba@1186
   277
      moveDown();
deba@1186
   278
      int index = boxes[0].first;
deba@1186
   279
      iim[data[index].item] = POST_HEAP;
deba@1186
   280
      remove(index);
deba@1186
   281
      relocate_last(index);
deba@1186
   282
      //      printf("Pop \n");
deba@1186
   283
      //print();
deba@1186
   284
    }
deba@1186
   285
deba@1186
   286
    ///\e
deba@1186
   287
    void erase(const Item &i) {
deba@1186
   288
      int index = iim[i];
deba@1186
   289
      iim[i] = POST_HEAP;
deba@1186
   290
      remove(index);
deba@1186
   291
      relocate_last(index);
deba@1186
   292
   }
deba@1186
   293
deba@1186
   294
    ///\e
deba@1186
   295
    Prio operator[](const Item &i) const {
deba@1186
   296
      int idx = iim[i];
deba@1186
   297
      return data[idx].prio;
deba@1186
   298
    }
deba@1186
   299
deba@1186
   300
    ///\e
deba@1186
   301
    void set(const Item &i, const Prio &p) {
deba@1186
   302
      int idx = iim[i];
deba@1186
   303
      if( idx < 0 ) {
deba@1186
   304
	push(i, p);
deba@1186
   305
      }
deba@1186
   306
      else if( p >= data[idx].prio ) {
deba@1186
   307
	data[idx].prio = p;
deba@1186
   308
	bubble_up(idx);
deba@1186
   309
      } else {
deba@1186
   310
	data[idx].prio = p;
deba@1186
   311
	bubble_down(idx);
deba@1186
   312
      }
deba@1186
   313
    }
deba@1186
   314
deba@1186
   315
    ///\e
deba@1186
   316
    void decrease(const Item &i, const Prio &p) {
deba@1186
   317
      //      print(); printf("decrease\n"); fflush(stdout);
deba@1186
   318
      int idx = iim[i];
deba@1186
   319
      data[idx].prio = p;
deba@1186
   320
      bubble_down(idx);
deba@1186
   321
    }
deba@1186
   322
deba@1186
   323
    ///\e
deba@1186
   324
    void increase(const Item &i, const Prio &p) {
deba@1186
   325
      int idx = iim[i];
deba@1186
   326
      data[idx].prio = p;
deba@1186
   327
      bubble_up(idx);
deba@1186
   328
    }
deba@1186
   329
deba@1186
   330
    ///\e
deba@1186
   331
    state_enum state(const Item &i) const {
deba@1186
   332
      int s = iim[i];
deba@1186
   333
      if( s >= 0 ) s = 0;
deba@1186
   334
      return state_enum(s);
deba@1186
   335
    }
deba@1186
   336
deba@1186
   337
    void print() const {
deba@1186
   338
      for (int i = 0; i < boxes.size(); ++i) {
deba@1186
   339
	printf("(%d, %d) ", boxes[i].min, boxes[i].size);
deba@1186
   340
	for (int k = boxes[i].first; k != -1; k = data[k].next) {
deba@1186
   341
	  printf("%d ", data[k].prio);
deba@1186
   342
	}
deba@1186
   343
	printf("\n");
deba@1186
   344
      }
deba@1186
   345
      fflush(stdout);
deba@1186
   346
    }
deba@1186
   347
deba@1186
   348
  }; // class RadixHeap
deba@1186
   349
deba@1186
   350
deba@1186
   351
  ///@}
deba@1186
   352
deba@1186
   353
} // namespace lemon
deba@1186
   354
deba@1186
   355
#endif // LEMON_RADIX_HEAP_H