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