lemon/bucket_heap.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 12 Sep 2012 17:34:01 +0200
changeset 996 b6347aae6575
parent 711 28cfac049a6a
permissions -rw-r--r--
Merge bugfix #448
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
 *
alpar@877
     5
 * Copyright (C) 2003-2010
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_BUCKET_HEAP_H
deba@681
    20
#define LEMON_BUCKET_HEAP_H
deba@681
    21
kpeter@710
    22
///\ingroup heaps
deba@681
    23
///\file
kpeter@709
    24
///\brief Bucket heap implementation.
deba@681
    25
deba@681
    26
#include <vector>
deba@681
    27
#include <utility>
deba@681
    28
#include <functional>
deba@681
    29
deba@681
    30
namespace lemon {
deba@681
    31
deba@682
    32
  namespace _bucket_heap_bits {
deba@682
    33
deba@683
    34
    template <bool MIN>
deba@682
    35
    struct DirectionTraits {
deba@682
    36
      static bool less(int left, int right) {
deba@682
    37
        return left < right;
deba@682
    38
      }
deba@682
    39
      static void increase(int& value) {
deba@682
    40
        ++value;
deba@682
    41
      }
deba@682
    42
    };
deba@682
    43
deba@682
    44
    template <>
deba@682
    45
    struct DirectionTraits<false> {
deba@682
    46
      static bool less(int left, int right) {
deba@682
    47
        return left > right;
deba@682
    48
      }
deba@682
    49
      static void increase(int& value) {
deba@682
    50
        --value;
deba@682
    51
      }
deba@682
    52
    };
deba@682
    53
deba@682
    54
  }
deba@682
    55
kpeter@710
    56
  /// \ingroup heaps
deba@681
    57
  ///
kpeter@709
    58
  /// \brief Bucket heap data structure.
deba@681
    59
  ///
kpeter@709
    60
  /// This class implements the \e bucket \e heap data structure.
kpeter@709
    61
  /// It practically conforms to the \ref concepts::Heap "heap concept",
kpeter@709
    62
  /// but it has some limitations.
deba@681
    63
  ///
kpeter@709
    64
  /// The bucket heap is a very simple structure. It can store only
kpeter@709
    65
  /// \c int priorities and it maintains a list of items for each priority
kpeter@709
    66
  /// in the range <tt>[0..C)</tt>. So it should only be used when the
kpeter@709
    67
  /// priorities are small. It is not intended to use as a Dijkstra heap.
kpeter@709
    68
  ///
kpeter@709
    69
  /// \tparam IM A read-writable item map with \c int values, used
kpeter@709
    70
  /// internally to handle the cross references.
kpeter@709
    71
  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
kpeter@709
    72
  /// The default is \e min-heap. If this parameter is set to \c false,
kpeter@709
    73
  /// then the comparison is reversed, so the top(), prio() and pop()
kpeter@709
    74
  /// functions deal with the item having maximum priority instead of the
kpeter@709
    75
  /// minimum.
kpeter@709
    76
  ///
kpeter@709
    77
  /// \sa SimpleBucketHeap
deba@683
    78
  template <typename IM, bool MIN = true>
deba@681
    79
  class BucketHeap {
deba@681
    80
deba@681
    81
  public:
kpeter@709
    82
kpeter@709
    83
    /// Type of the item-int map.
kpeter@709
    84
    typedef IM ItemIntMap;
kpeter@709
    85
    /// Type of the priorities.
deba@681
    86
    typedef int Prio;
kpeter@709
    87
    /// Type of the items stored in the heap.
kpeter@709
    88
    typedef typename ItemIntMap::Key Item;
kpeter@709
    89
    /// Type of the item-priority pairs.
kpeter@709
    90
    typedef std::pair<Item,Prio> Pair;
deba@681
    91
deba@682
    92
  private:
deba@682
    93
deba@683
    94
    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
deba@682
    95
deba@682
    96
  public:
deba@682
    97
kpeter@709
    98
    /// \brief Type to represent the states of the items.
deba@681
    99
    ///
kpeter@709
   100
    /// Each item has a state associated to it. It can be "in heap",
kpeter@709
   101
    /// "pre-heap" or "post-heap". The latter two are indifferent from the
deba@681
   102
    /// heap's point of view, but may be useful to the user.
deba@681
   103
    ///
deba@683
   104
    /// The item-int map must be initialized in such way that it assigns
deba@683
   105
    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
deba@681
   106
    enum State {
deba@683
   107
      IN_HEAP = 0,    ///< = 0.
deba@683
   108
      PRE_HEAP = -1,  ///< = -1.
deba@683
   109
      POST_HEAP = -2  ///< = -2.
deba@681
   110
    };
deba@681
   111
deba@681
   112
  public:
kpeter@709
   113
kpeter@709
   114
    /// \brief Constructor.
deba@681
   115
    ///
kpeter@709
   116
    /// Constructor.
kpeter@709
   117
    /// \param map A map that assigns \c int values to the items.
kpeter@709
   118
    /// It is used internally to handle the cross references.
kpeter@709
   119
    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
deba@683
   120
    explicit BucketHeap(ItemIntMap &map) : _iim(map), _minimum(0) {}
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.
deba@683
   125
    int size() const { return _data.size(); }
deba@681
   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.
deba@683
   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.
deba@681
   139
    void clear() {
deba@683
   140
      _data.clear(); _first.clear(); _minimum = 0;
deba@681
   141
    }
deba@681
   142
deba@681
   143
  private:
deba@681
   144
kpeter@711
   145
    void relocateLast(int idx) {
deba@683
   146
      if (idx + 1 < int(_data.size())) {
deba@683
   147
        _data[idx] = _data.back();
deba@683
   148
        if (_data[idx].prev != -1) {
deba@683
   149
          _data[_data[idx].prev].next = idx;
deba@681
   150
        } else {
deba@683
   151
          _first[_data[idx].value] = idx;
deba@681
   152
        }
deba@683
   153
        if (_data[idx].next != -1) {
deba@683
   154
          _data[_data[idx].next].prev = idx;
deba@681
   155
        }
deba@683
   156
        _iim[_data[idx].item] = idx;
deba@681
   157
      }
deba@683
   158
      _data.pop_back();
deba@681
   159
    }
deba@681
   160
deba@681
   161
    void unlace(int idx) {
deba@683
   162
      if (_data[idx].prev != -1) {
deba@683
   163
        _data[_data[idx].prev].next = _data[idx].next;
deba@681
   164
      } else {
deba@683
   165
        _first[_data[idx].value] = _data[idx].next;
deba@681
   166
      }
deba@683
   167
      if (_data[idx].next != -1) {
deba@683
   168
        _data[_data[idx].next].prev = _data[idx].prev;
deba@681
   169
      }
deba@681
   170
    }
deba@681
   171
deba@681
   172
    void lace(int idx) {
deba@683
   173
      if (int(_first.size()) <= _data[idx].value) {
deba@683
   174
        _first.resize(_data[idx].value + 1, -1);
deba@681
   175
      }
deba@683
   176
      _data[idx].next = _first[_data[idx].value];
deba@683
   177
      if (_data[idx].next != -1) {
deba@683
   178
        _data[_data[idx].next].prev = idx;
deba@681
   179
      }
deba@683
   180
      _first[_data[idx].value] = idx;
deba@683
   181
      _data[idx].prev = -1;
deba@681
   182
    }
deba@681
   183
deba@681
   184
  public:
kpeter@709
   185
deba@681
   186
    /// \brief Insert a pair of item and priority into the heap.
deba@681
   187
    ///
kpeter@709
   188
    /// This function inserts \c p.first to the heap with priority
kpeter@709
   189
    /// \c p.second.
deba@681
   190
    /// \param p The pair to insert.
kpeter@709
   191
    /// \pre \c p.first must not be stored in the heap.
deba@681
   192
    void push(const Pair& p) {
deba@681
   193
      push(p.first, p.second);
deba@681
   194
    }
deba@681
   195
deba@681
   196
    /// \brief Insert an item into the heap with the given priority.
deba@681
   197
    ///
kpeter@709
   198
    /// This function inserts the given item into the heap with the
kpeter@709
   199
    /// given priority.
deba@681
   200
    /// \param i The item to insert.
deba@681
   201
    /// \param p The priority of the item.
kpeter@709
   202
    /// \pre \e i must not be stored in the heap.
deba@681
   203
    void push(const Item &i, const Prio &p) {
deba@683
   204
      int idx = _data.size();
deba@683
   205
      _iim[i] = idx;
deba@683
   206
      _data.push_back(BucketItem(i, p));
deba@681
   207
      lace(idx);
deba@683
   208
      if (Direction::less(p, _minimum)) {
deba@683
   209
        _minimum = p;
deba@681
   210
      }
deba@681
   211
    }
deba@681
   212
kpeter@709
   213
    /// \brief Return the item having minimum priority.
deba@681
   214
    ///
kpeter@709
   215
    /// This function returns the item having minimum priority.
kpeter@709
   216
    /// \pre The heap must be non-empty.
deba@681
   217
    Item top() const {
deba@683
   218
      while (_first[_minimum] == -1) {
deba@683
   219
        Direction::increase(_minimum);
deba@681
   220
      }
deba@683
   221
      return _data[_first[_minimum]].item;
deba@681
   222
    }
deba@681
   223
kpeter@709
   224
    /// \brief The minimum priority.
deba@681
   225
    ///
kpeter@709
   226
    /// This function returns the minimum priority.
kpeter@709
   227
    /// \pre The heap must be non-empty.
deba@681
   228
    Prio prio() const {
deba@683
   229
      while (_first[_minimum] == -1) {
deba@683
   230
        Direction::increase(_minimum);
deba@681
   231
      }
deba@683
   232
      return _minimum;
deba@681
   233
    }
deba@681
   234
kpeter@709
   235
    /// \brief Remove the item having minimum priority.
deba@681
   236
    ///
kpeter@709
   237
    /// This function removes the item having minimum priority.
deba@681
   238
    /// \pre The heap must be non-empty.
deba@681
   239
    void pop() {
deba@683
   240
      while (_first[_minimum] == -1) {
deba@683
   241
        Direction::increase(_minimum);
deba@681
   242
      }
deba@683
   243
      int idx = _first[_minimum];
deba@683
   244
      _iim[_data[idx].item] = -2;
deba@681
   245
      unlace(idx);
kpeter@711
   246
      relocateLast(idx);
deba@681
   247
    }
deba@681
   248
kpeter@709
   249
    /// \brief Remove the given item from the heap.
deba@681
   250
    ///
kpeter@709
   251
    /// This function removes the given item from the heap if it is
kpeter@709
   252
    /// already stored.
kpeter@709
   253
    /// \param i The item to delete.
kpeter@709
   254
    /// \pre \e i must be in the heap.
deba@681
   255
    void erase(const Item &i) {
deba@683
   256
      int idx = _iim[i];
deba@683
   257
      _iim[_data[idx].item] = -2;
deba@681
   258
      unlace(idx);
kpeter@711
   259
      relocateLast(idx);
deba@681
   260
    }
deba@681
   261
kpeter@709
   262
    /// \brief The priority of the given item.
deba@681
   263
    ///
kpeter@709
   264
    /// This function returns the priority of the given item.
deba@681
   265
    /// \param i The item.
kpeter@709
   266
    /// \pre \e i must be in the heap.
deba@681
   267
    Prio operator[](const Item &i) const {
deba@683
   268
      int idx = _iim[i];
deba@683
   269
      return _data[idx].value;
deba@681
   270
    }
deba@681
   271
kpeter@709
   272
    /// \brief Set the priority of an item or insert it, if it is
kpeter@709
   273
    /// not stored in the heap.
deba@681
   274
    ///
kpeter@709
   275
    /// This method sets the priority of the given item if it is
kpeter@709
   276
    /// already stored in the heap. Otherwise it inserts the given
kpeter@709
   277
    /// item into the heap with the given priority.
deba@681
   278
    /// \param i The item.
deba@681
   279
    /// \param p The priority.
deba@681
   280
    void set(const Item &i, const Prio &p) {
deba@683
   281
      int idx = _iim[i];
deba@681
   282
      if (idx < 0) {
deba@682
   283
        push(i, p);
deba@683
   284
      } else if (Direction::less(p, _data[idx].value)) {
deba@682
   285
        decrease(i, p);
deba@682
   286
      } else {
deba@681
   287
        increase(i, p);
deba@681
   288
      }
deba@681
   289
    }
deba@681
   290
kpeter@709
   291
    /// \brief Decrease the priority of an item to the given value.
deba@681
   292
    ///
kpeter@709
   293
    /// This function decreases the priority of an item to the given value.
deba@681
   294
    /// \param i The item.
deba@681
   295
    /// \param p The priority.
kpeter@709
   296
    /// \pre \e i must be stored in the heap with priority at least \e p.
deba@681
   297
    void decrease(const Item &i, const Prio &p) {
deba@683
   298
      int idx = _iim[i];
deba@681
   299
      unlace(idx);
deba@683
   300
      _data[idx].value = p;
deba@683
   301
      if (Direction::less(p, _minimum)) {
deba@683
   302
        _minimum = p;
deba@681
   303
      }
deba@681
   304
      lace(idx);
deba@681
   305
    }
deba@681
   306
kpeter@709
   307
    /// \brief Increase the priority of an item to the given value.
deba@681
   308
    ///
kpeter@709
   309
    /// This function increases the priority of an item to the given value.
deba@681
   310
    /// \param i The item.
deba@681
   311
    /// \param p The priority.
kpeter@709
   312
    /// \pre \e i must be stored in the heap with priority at most \e p.
deba@681
   313
    void increase(const Item &i, const Prio &p) {
deba@683
   314
      int idx = _iim[i];
deba@681
   315
      unlace(idx);
deba@683
   316
      _data[idx].value = p;
deba@681
   317
      lace(idx);
deba@681
   318
    }
deba@681
   319
kpeter@709
   320
    /// \brief Return the state of an item.
deba@681
   321
    ///
kpeter@709
   322
    /// This method returns \c PRE_HEAP if the given item has never
kpeter@709
   323
    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
kpeter@709
   324
    /// and \c POST_HEAP otherwise.
kpeter@709
   325
    /// In the latter case it is possible that the item will get back
kpeter@709
   326
    /// to the heap again.
deba@681
   327
    /// \param i The item.
deba@681
   328
    State state(const Item &i) const {
deba@683
   329
      int idx = _iim[i];
deba@681
   330
      if (idx >= 0) idx = 0;
deba@681
   331
      return State(idx);
deba@681
   332
    }
deba@681
   333
kpeter@709
   334
    /// \brief Set the state of an item in the heap.
deba@681
   335
    ///
kpeter@709
   336
    /// This function sets the state of the given item in the heap.
kpeter@709
   337
    /// It can be used to manually clear the heap when it is important
kpeter@709
   338
    /// to achive better time complexity.
deba@681
   339
    /// \param i The item.
deba@681
   340
    /// \param st The state. It should not be \c IN_HEAP.
deba@681
   341
    void state(const Item& i, State st) {
deba@681
   342
      switch (st) {
deba@681
   343
      case POST_HEAP:
deba@681
   344
      case PRE_HEAP:
deba@681
   345
        if (state(i) == IN_HEAP) {
deba@681
   346
          erase(i);
deba@681
   347
        }
deba@683
   348
        _iim[i] = st;
deba@681
   349
        break;
deba@681
   350
      case IN_HEAP:
deba@681
   351
        break;
deba@681
   352
      }
deba@681
   353
    }
deba@681
   354
deba@681
   355
  private:
deba@681
   356
deba@681
   357
    struct BucketItem {
deba@681
   358
      BucketItem(const Item& _item, int _value)
deba@681
   359
        : item(_item), value(_value) {}
deba@681
   360
deba@681
   361
      Item item;
deba@681
   362
      int value;
deba@681
   363
deba@681
   364
      int prev, next;
deba@681
   365
    };
deba@681
   366
deba@683
   367
    ItemIntMap& _iim;
deba@683
   368
    std::vector<int> _first;
deba@683
   369
    std::vector<BucketItem> _data;
deba@683
   370
    mutable int _minimum;
deba@681
   371
deba@681
   372
  }; // class BucketHeap
deba@681
   373
kpeter@710
   374
  /// \ingroup heaps
deba@681
   375
  ///
kpeter@709
   376
  /// \brief Simplified bucket heap data structure.
deba@681
   377
  ///
deba@681
   378
  /// This class implements a simplified \e bucket \e heap data
kpeter@709
   379
  /// structure. It does not provide some functionality, but it is
kpeter@709
   380
  /// faster and simpler than BucketHeap. The main difference is
kpeter@709
   381
  /// that BucketHeap stores a doubly-linked list for each key while
kpeter@709
   382
  /// this class stores only simply-linked lists. It supports erasing
kpeter@709
   383
  /// only for the item having minimum priority and it does not support
kpeter@709
   384
  /// key increasing and decreasing.
deba@681
   385
  ///
kpeter@709
   386
  /// Note that this implementation does not conform to the
alpar@877
   387
  /// \ref concepts::Heap "heap concept" due to the lack of some
kpeter@709
   388
  /// functionality.
kpeter@709
   389
  ///
kpeter@709
   390
  /// \tparam IM A read-writable item map with \c int values, used
kpeter@709
   391
  /// internally to handle the cross references.
kpeter@709
   392
  /// \tparam MIN Indicate if the heap is a \e min-heap or a \e max-heap.
kpeter@709
   393
  /// The default is \e min-heap. If this parameter is set to \c false,
kpeter@709
   394
  /// then the comparison is reversed, so the top(), prio() and pop()
kpeter@709
   395
  /// functions deal with the item having maximum priority instead of the
kpeter@709
   396
  /// minimum.
deba@681
   397
  ///
deba@681
   398
  /// \sa BucketHeap
deba@683
   399
  template <typename IM, bool MIN = true >
deba@681
   400
  class SimpleBucketHeap {
deba@681
   401
deba@681
   402
  public:
kpeter@709
   403
kpeter@709
   404
    /// Type of the item-int map.
kpeter@709
   405
    typedef IM ItemIntMap;
kpeter@709
   406
    /// Type of the priorities.
deba@681
   407
    typedef int Prio;
kpeter@709
   408
    /// Type of the items stored in the heap.
kpeter@709
   409
    typedef typename ItemIntMap::Key Item;
kpeter@709
   410
    /// Type of the item-priority pairs.
kpeter@709
   411
    typedef std::pair<Item,Prio> Pair;
deba@681
   412
deba@682
   413
  private:
deba@682
   414
deba@683
   415
    typedef _bucket_heap_bits::DirectionTraits<MIN> Direction;
deba@682
   416
deba@682
   417
  public:
deba@682
   418
kpeter@709
   419
    /// \brief Type to represent the states of the items.
deba@681
   420
    ///
kpeter@709
   421
    /// Each item has a state associated to it. It can be "in heap",
kpeter@709
   422
    /// "pre-heap" or "post-heap". The latter two are indifferent from the
deba@681
   423
    /// heap's point of view, but may be useful to the user.
deba@681
   424
    ///
deba@683
   425
    /// The item-int map must be initialized in such way that it assigns
deba@683
   426
    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
deba@681
   427
    enum State {
deba@683
   428
      IN_HEAP = 0,    ///< = 0.
deba@683
   429
      PRE_HEAP = -1,  ///< = -1.
deba@683
   430
      POST_HEAP = -2  ///< = -2.
deba@681
   431
    };
deba@681
   432
deba@681
   433
  public:
deba@681
   434
kpeter@709
   435
    /// \brief Constructor.
deba@681
   436
    ///
kpeter@709
   437
    /// Constructor.
kpeter@709
   438
    /// \param map A map that assigns \c int values to the items.
kpeter@709
   439
    /// It is used internally to handle the cross references.
kpeter@709
   440
    /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item.
deba@683
   441
    explicit SimpleBucketHeap(ItemIntMap &map)
deba@683
   442
      : _iim(map), _free(-1), _num(0), _minimum(0) {}
deba@681
   443
kpeter@709
   444
    /// \brief The number of items stored in the heap.
deba@681
   445
    ///
kpeter@709
   446
    /// This function returns the number of items stored in the heap.
deba@683
   447
    int size() const { return _num; }
deba@681
   448
kpeter@709
   449
    /// \brief Check if the heap is empty.
deba@681
   450
    ///
kpeter@709
   451
    /// This function returns \c true if the heap is empty.
deba@683
   452
    bool empty() const { return _num == 0; }
deba@681
   453
kpeter@709
   454
    /// \brief Make the heap empty.
deba@681
   455
    ///
kpeter@709
   456
    /// This functon makes the heap empty.
kpeter@709
   457
    /// It does not change the cross reference map. If you want to reuse
kpeter@709
   458
    /// a heap that is not surely empty, you should first clear it and
kpeter@709
   459
    /// then you should set the cross reference map to \c PRE_HEAP
kpeter@709
   460
    /// for each item.
deba@681
   461
    void clear() {
deba@683
   462
      _data.clear(); _first.clear(); _free = -1; _num = 0; _minimum = 0;
deba@681
   463
    }
deba@681
   464
deba@681
   465
    /// \brief Insert a pair of item and priority into the heap.
deba@681
   466
    ///
kpeter@709
   467
    /// This function inserts \c p.first to the heap with priority
kpeter@709
   468
    /// \c p.second.
deba@681
   469
    /// \param p The pair to insert.
kpeter@709
   470
    /// \pre \c p.first must not be stored in the heap.
deba@681
   471
    void push(const Pair& p) {
deba@681
   472
      push(p.first, p.second);
deba@681
   473
    }
deba@681
   474
deba@681
   475
    /// \brief Insert an item into the heap with the given priority.
deba@681
   476
    ///
kpeter@709
   477
    /// This function inserts the given item into the heap with the
kpeter@709
   478
    /// given priority.
deba@681
   479
    /// \param i The item to insert.
deba@681
   480
    /// \param p The priority of the item.
kpeter@709
   481
    /// \pre \e i must not be stored in the heap.
deba@681
   482
    void push(const Item &i, const Prio &p) {
deba@681
   483
      int idx;
deba@683
   484
      if (_free == -1) {
deba@683
   485
        idx = _data.size();
deba@683
   486
        _data.push_back(BucketItem(i));
deba@681
   487
      } else {
deba@683
   488
        idx = _free;
deba@683
   489
        _free = _data[idx].next;
deba@683
   490
        _data[idx].item = i;
deba@681
   491
      }
deba@683
   492
      _iim[i] = idx;
deba@683
   493
      if (p >= int(_first.size())) _first.resize(p + 1, -1);
deba@683
   494
      _data[idx].next = _first[p];
deba@683
   495
      _first[p] = idx;
deba@683
   496
      if (Direction::less(p, _minimum)) {
deba@683
   497
        _minimum = p;
deba@681
   498
      }
deba@683
   499
      ++_num;
deba@681
   500
    }
deba@681
   501
kpeter@709
   502
    /// \brief Return the item having minimum priority.
deba@681
   503
    ///
kpeter@709
   504
    /// This function returns the item having minimum priority.
kpeter@709
   505
    /// \pre The heap must be non-empty.
deba@681
   506
    Item top() const {
deba@683
   507
      while (_first[_minimum] == -1) {
deba@683
   508
        Direction::increase(_minimum);
deba@681
   509
      }
deba@683
   510
      return _data[_first[_minimum]].item;
deba@681
   511
    }
deba@681
   512
kpeter@709
   513
    /// \brief The minimum priority.
deba@681
   514
    ///
kpeter@709
   515
    /// This function returns the minimum priority.
kpeter@709
   516
    /// \pre The heap must be non-empty.
deba@681
   517
    Prio prio() const {
deba@683
   518
      while (_first[_minimum] == -1) {
deba@683
   519
        Direction::increase(_minimum);
deba@681
   520
      }
deba@683
   521
      return _minimum;
deba@681
   522
    }
deba@681
   523
kpeter@709
   524
    /// \brief Remove the item having minimum priority.
deba@681
   525
    ///
kpeter@709
   526
    /// This function removes the item having minimum priority.
deba@681
   527
    /// \pre The heap must be non-empty.
deba@681
   528
    void pop() {
deba@683
   529
      while (_first[_minimum] == -1) {
deba@683
   530
        Direction::increase(_minimum);
deba@681
   531
      }
deba@683
   532
      int idx = _first[_minimum];
deba@683
   533
      _iim[_data[idx].item] = -2;
deba@683
   534
      _first[_minimum] = _data[idx].next;
deba@683
   535
      _data[idx].next = _free;
deba@683
   536
      _free = idx;
deba@683
   537
      --_num;
deba@681
   538
    }
deba@681
   539
kpeter@709
   540
    /// \brief The priority of the given item.
deba@681
   541
    ///
kpeter@709
   542
    /// This function returns the priority of the given item.
deba@681
   543
    /// \param i The item.
kpeter@709
   544
    /// \pre \e i must be in the heap.
kpeter@709
   545
    /// \warning This operator is not a constant time function because
kpeter@709
   546
    /// it scans the whole data structure to find the proper value.
deba@681
   547
    Prio operator[](const Item &i) const {
kpeter@709
   548
      for (int k = 0; k < int(_first.size()); ++k) {
deba@683
   549
        int idx = _first[k];
deba@681
   550
        while (idx != -1) {
deba@683
   551
          if (_data[idx].item == i) {
deba@681
   552
            return k;
deba@681
   553
          }
deba@683
   554
          idx = _data[idx].next;
deba@681
   555
        }
deba@681
   556
      }
deba@681
   557
      return -1;
deba@681
   558
    }
deba@681
   559
kpeter@709
   560
    /// \brief Return the state of an item.
deba@681
   561
    ///
kpeter@709
   562
    /// This method returns \c PRE_HEAP if the given item has never
kpeter@709
   563
    /// been in the heap, \c IN_HEAP if it is in the heap at the moment,
kpeter@709
   564
    /// and \c POST_HEAP otherwise.
kpeter@709
   565
    /// In the latter case it is possible that the item will get back
kpeter@709
   566
    /// to the heap again.
deba@681
   567
    /// \param i The item.
deba@681
   568
    State state(const Item &i) const {
deba@683
   569
      int idx = _iim[i];
deba@681
   570
      if (idx >= 0) idx = 0;
deba@681
   571
      return State(idx);
deba@681
   572
    }
deba@681
   573
deba@681
   574
  private:
deba@681
   575
deba@681
   576
    struct BucketItem {
deba@681
   577
      BucketItem(const Item& _item)
deba@681
   578
        : item(_item) {}
deba@681
   579
deba@681
   580
      Item item;
deba@681
   581
      int next;
deba@681
   582
    };
deba@681
   583
deba@683
   584
    ItemIntMap& _iim;
deba@683
   585
    std::vector<int> _first;
deba@683
   586
    std::vector<BucketItem> _data;
deba@683
   587
    int _free, _num;
deba@683
   588
    mutable int _minimum;
deba@681
   589
deba@681
   590
  }; // class SimpleBucketHeap
deba@681
   591
deba@681
   592
}
deba@681
   593
deba@681
   594
#endif