lemon/bucket_heap.h
author ladanyi
Sat, 25 Aug 2007 10:12:03 +0000
changeset 2465 df09310da558
parent 2386 81b47fc5c444
child 2547 f393a8162688
permissions -rw-r--r--
Consider the CPXMIP_OPTIMAL_TOL status as OPTIMAL too.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BUCKET_HEAP_H
    20 #define LEMON_BUCKET_HEAP_H
    21 
    22 ///\ingroup auxdat
    23 ///\file
    24 ///\brief Bucket Heap implementation.
    25 
    26 #include <vector>
    27 #include <utility>
    28 #include <functional>
    29 
    30 namespace lemon {
    31 
    32   /// \ingroup auxdat
    33   ///
    34   /// \brief A Bucket Heap implementation.
    35   ///
    36   /// This class implements the \e bucket \e heap data structure. A \e heap
    37   /// is a data structure for storing items with specified values called \e
    38   /// priorities in such a way that finding the item with minimum priority is
    39   /// efficient. The bucket heap is very simple implementation, it can store
    40   /// only integer priorities and it stores for each priority in the 
    41   /// \f$ [0..C) \f$ range a list of items. So it should be used only when 
    42   /// the priorities are small. It is not intended to use as dijkstra heap.
    43   ///
    44   /// \param _ItemIntMap A read and writable Item int map, used internally
    45   /// to handle the cross references.
    46   /// \param minimize If the given parameter is true then the heap gives back
    47   /// the lowest priority. 
    48   template <typename _ItemIntMap, bool minimize = true >
    49   class BucketHeap {
    50 
    51   public:
    52     typedef typename _ItemIntMap::Key Item;
    53     typedef int Prio;
    54     typedef std::pair<Item, Prio> Pair;
    55     typedef _ItemIntMap ItemIntMap;
    56 
    57     /// \brief Type to represent the items states.
    58     ///
    59     /// Each Item element have a state associated to it. It may be "in heap",
    60     /// "pre heap" or "post heap". The latter two are indifferent from the
    61     /// heap's point of view, but may be useful to the user.
    62     ///
    63     /// The ItemIntMap \e should be initialized in such way that it maps
    64     /// PRE_HEAP (-1) to any element to be put in the heap...
    65     enum state_enum {
    66       IN_HEAP = 0,
    67       PRE_HEAP = -1,
    68       POST_HEAP = -2
    69     };
    70 
    71   public:
    72     /// \brief The constructor.
    73     ///
    74     /// The constructor.
    75     /// \param _index should be given to the constructor, since it is used
    76     /// internally to handle the cross references. The value of the map
    77     /// should be PRE_HEAP (-1) for each element.
    78     explicit BucketHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
    79     
    80     /// The number of items stored in the heap.
    81     ///
    82     /// \brief Returns the number of items stored in the heap.
    83     int size() const { return data.size(); }
    84     
    85     /// \brief Checks if the heap stores no items.
    86     ///
    87     /// Returns \c true if and only if the heap stores no items.
    88     bool empty() const { return data.empty(); }
    89 
    90     /// \brief Make empty this heap.
    91     /// 
    92     /// Make empty this heap. It does not change the cross reference
    93     /// map.  If you want to reuse a heap what is not surely empty you
    94     /// should first clear the heap and after that you should set the
    95     /// cross reference map for each item to \c PRE_HEAP.
    96     void clear() { 
    97       data.clear(); first.clear(); minimal = 0;
    98     }
    99 
   100   private:
   101 
   102     void relocate_last(int idx) {
   103       if (idx + 1 < int(data.size())) {
   104 	data[idx] = data.back();
   105 	if (data[idx].prev != -1) {
   106 	  data[data[idx].prev].next = idx;
   107 	} else {
   108 	  first[data[idx].value] = idx;
   109 	}
   110 	if (data[idx].next != -1) {
   111 	  data[data[idx].next].prev = idx;
   112 	}
   113 	index[data[idx].item] = idx;
   114       }
   115       data.pop_back();
   116     }
   117 
   118     void unlace(int idx) {
   119       if (data[idx].prev != -1) {
   120 	data[data[idx].prev].next = data[idx].next;
   121       } else {
   122 	first[data[idx].value] = data[idx].next;
   123       }
   124       if (data[idx].next != -1) {
   125 	data[data[idx].next].prev = data[idx].prev;
   126       }
   127     }
   128 
   129     void lace(int idx) {
   130       if (int(first.size()) <= data[idx].value) {
   131 	first.resize(data[idx].value + 1, -1);
   132       }
   133       data[idx].next = first[data[idx].value];
   134       if (data[idx].next != -1) {
   135 	data[data[idx].next].prev = idx;
   136       }
   137       first[data[idx].value] = idx;
   138       data[idx].prev = -1;
   139     }
   140 
   141   public:
   142     /// \brief Insert a pair of item and priority into the heap.
   143     ///
   144     /// Adds \c p.first to the heap with priority \c p.second.
   145     /// \param p The pair to insert.
   146     void push(const Pair& p) {
   147       push(p.first, p.second);
   148     }
   149 
   150     /// \brief Insert an item into the heap with the given priority.
   151     ///    
   152     /// Adds \c i to the heap with priority \c p. 
   153     /// \param i The item to insert.
   154     /// \param p The priority of the item.
   155     void push(const Item &i, const Prio &p) { 
   156       int idx = data.size();
   157       index[i] = idx;
   158       data.push_back(BucketItem(i, p));
   159       lace(idx);
   160       if (p < minimal) {
   161 	minimal = p;
   162       }
   163     }
   164 
   165     /// \brief Returns the item with minimum priority.
   166     ///
   167     /// This method returns the item with minimum priority.
   168     /// \pre The heap must be nonempty.  
   169     Item top() const {
   170       while (first[minimal] == -1) {
   171 	++minimal;
   172       }
   173       return data[first[minimal]].item;
   174     }
   175 
   176     /// \brief Returns the minimum priority.
   177     ///
   178     /// It returns the minimum priority.
   179     /// \pre The heap must be nonempty.
   180     Prio prio() const {
   181       while (first[minimal] == -1) {
   182 	++minimal;
   183       }
   184       return minimal;
   185     }
   186 
   187     /// \brief Deletes the item with minimum priority.
   188     ///
   189     /// This method deletes the item with minimum priority from the heap.  
   190     /// \pre The heap must be non-empty.  
   191     void pop() {
   192       while (first[minimal] == -1) {
   193 	++minimal;
   194       }
   195       int idx = first[minimal];
   196       index[data[idx].item] = -2;
   197       unlace(idx);
   198       relocate_last(idx);
   199     }
   200 
   201     /// \brief Deletes \c i from the heap.
   202     ///
   203     /// This method deletes item \c i from the heap, if \c i was
   204     /// already stored in the heap.
   205     /// \param i The item to erase. 
   206     void erase(const Item &i) {
   207       int idx = index[i];
   208       index[data[idx].item] = -2;
   209       unlace(idx);
   210       relocate_last(idx);
   211     }
   212 
   213     
   214     /// \brief Returns the priority of \c i.
   215     ///
   216     /// This function returns the priority of item \c i.  
   217     /// \pre \c i must be in the heap.
   218     /// \param i The item.
   219     Prio operator[](const Item &i) const {
   220       int idx = index[i];
   221       return data[idx].value;
   222     }
   223 
   224     /// \brief \c i gets to the heap with priority \c p independently 
   225     /// if \c i was already there.
   226     ///
   227     /// This method calls \ref push(\c i, \c p) if \c i is not stored
   228     /// in the heap and sets the priority of \c i to \c p otherwise.
   229     /// \param i The item.
   230     /// \param p The priority.
   231     void set(const Item &i, const Prio &p) {
   232       int idx = index[i];
   233       if (idx < 0) {
   234 	push(i,p);
   235       } else if (p > data[idx].value) {
   236 	increase(i, p);
   237       } else {
   238 	decrease(i, p);
   239       }
   240     }
   241 
   242     /// \brief Decreases the priority of \c i to \c p.
   243     ///
   244     /// This method decreases the priority of item \c i to \c p.
   245     /// \pre \c i must be stored in the heap with priority at least \c
   246     /// p relative to \c Compare.
   247     /// \param i The item.
   248     /// \param p The priority.
   249     void decrease(const Item &i, const Prio &p) {
   250       int idx = index[i];
   251       unlace(idx);
   252       data[idx].value = p;
   253       if (p < minimal) {
   254 	minimal = p;
   255       }
   256       lace(idx);
   257     }
   258     
   259     /// \brief Increases the priority of \c i to \c p.
   260     ///
   261     /// This method sets the priority of item \c i to \c p. 
   262     /// \pre \c i must be stored in the heap with priority at most \c
   263     /// p relative to \c Compare.
   264     /// \param i The item.
   265     /// \param p The priority.
   266     void increase(const Item &i, const Prio &p) {
   267       int idx = index[i];
   268       unlace(idx);
   269       data[idx].value = p;
   270       lace(idx);
   271     }
   272 
   273     /// \brief Returns if \c item is in, has already been in, or has 
   274     /// never been in the heap.
   275     ///
   276     /// This method returns PRE_HEAP if \c item has never been in the
   277     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   278     /// otherwise. In the latter case it is possible that \c item will
   279     /// get back to the heap again.
   280     /// \param i The item.
   281     state_enum state(const Item &i) const {
   282       int idx = index[i];
   283       if (idx >= 0) idx = 0;
   284       return state_enum(idx);
   285     }
   286 
   287     /// \brief Sets the state of the \c item in the heap.
   288     ///
   289     /// Sets the state of the \c item in the heap. It can be used to
   290     /// manually clear the heap when it is important to achive the
   291     /// better time complexity.
   292     /// \param i The item.
   293     /// \param st The state. It should not be \c IN_HEAP. 
   294     void state(const Item& i, state_enum st) {
   295       switch (st) {
   296       case POST_HEAP:
   297       case PRE_HEAP:
   298         if (state(i) == IN_HEAP) {
   299           erase(i);
   300         }
   301         index[i] = st;
   302         break;
   303       case IN_HEAP:
   304         break;
   305       }
   306     }
   307 
   308   private:
   309 
   310     struct BucketItem {
   311       BucketItem(const Item& _item, int _value) 
   312 	: item(_item), value(_value) {}
   313 
   314       Item item;
   315       int value;
   316 
   317       int prev, next;
   318     };
   319 
   320     ItemIntMap& index;
   321     std::vector<int> first;
   322     std::vector<BucketItem> data;
   323     mutable int minimal;
   324 
   325   }; // class BucketHeap
   326 
   327 
   328   template <typename _ItemIntMap>
   329   class BucketHeap<_ItemIntMap, false> {
   330 
   331   public:
   332     typedef typename _ItemIntMap::Key Item;
   333     typedef int Prio;
   334     typedef std::pair<Item, Prio> Pair;
   335     typedef _ItemIntMap ItemIntMap;
   336 
   337     enum state_enum {
   338       IN_HEAP = 0,
   339       PRE_HEAP = -1,
   340       POST_HEAP = -2
   341     };
   342 
   343   public:
   344 
   345     explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
   346 
   347     int size() const { return data.size(); }
   348     bool empty() const { return data.empty(); }
   349 
   350     void clear() { 
   351       data.clear(); first.clear(); maximal = -1; 
   352     }
   353 
   354   private:
   355 
   356     void relocate_last(int idx) {
   357       if (idx + 1 != int(data.size())) {
   358 	data[idx] = data.back();
   359 	if (data[idx].prev != -1) {
   360 	  data[data[idx].prev].next = idx;
   361 	} else {
   362 	  first[data[idx].value] = idx;
   363 	}
   364 	if (data[idx].next != -1) {
   365 	  data[data[idx].next].prev = idx;
   366 	}
   367 	index[data[idx].item] = idx;
   368       }
   369       data.pop_back();
   370     }
   371 
   372     void unlace(int idx) {
   373       if (data[idx].prev != -1) {
   374 	data[data[idx].prev].next = data[idx].next;
   375       } else {
   376 	first[data[idx].value] = data[idx].next;
   377       }
   378       if (data[idx].next != -1) {
   379 	data[data[idx].next].prev = data[idx].prev;
   380       }
   381     }
   382 
   383     void lace(int idx) {
   384       if (int(first.size()) <= data[idx].value) {
   385 	first.resize(data[idx].value + 1, -1);
   386       }
   387       data[idx].next = first[data[idx].value];
   388       if (data[idx].next != -1) {
   389 	data[data[idx].next].prev = idx;
   390       }
   391       first[data[idx].value] = idx;
   392       data[idx].prev = -1;
   393     }
   394 
   395   public:
   396 
   397     void push(const Pair& p) {
   398       push(p.first, p.second);
   399     }
   400 
   401     void push(const Item &i, const Prio &p) { 
   402       int idx = data.size();
   403       index[i] = idx;
   404       data.push_back(BucketItem(i, p));
   405       lace(idx);
   406       if (data[idx].value > maximal) {
   407 	maximal = data[idx].value;
   408       }
   409     }
   410 
   411     Item top() const {
   412       while (first[maximal] == -1) {
   413 	--maximal;
   414       }
   415       return data[first[maximal]].item;
   416     }
   417 
   418     Prio prio() const {
   419       while (first[maximal] == -1) {
   420 	--maximal;
   421       }
   422       return maximal;
   423     }
   424 
   425     void pop() {
   426       while (first[maximal] == -1) {
   427 	--maximal;
   428       }
   429       int idx = first[maximal];
   430       index[data[idx].item] = -2;
   431       unlace(idx);
   432       relocate_last(idx);
   433     }
   434 
   435     void erase(const Item &i) {
   436       int idx = index[i];
   437       index[data[idx].item] = -2;
   438       unlace(idx);
   439       relocate_last(idx);
   440     }
   441 
   442     Prio operator[](const Item &i) const {
   443       int idx = index[i];
   444       return data[idx].value;
   445     }
   446 
   447     void set(const Item &i, const Prio &p) {
   448       int idx = index[i];
   449       if (idx < 0) {
   450 	push(i,p);
   451       } else if (p > data[idx].value) {
   452 	decrease(i, p);
   453       } else {
   454 	increase(i, p);
   455       }
   456     }
   457 
   458     void decrease(const Item &i, const Prio &p) {
   459       int idx = index[i];
   460       unlace(idx);
   461       data[idx].value = p;
   462       if (p > maximal) {
   463 	maximal = p;
   464       }
   465       lace(idx);
   466     }
   467     
   468     void increase(const Item &i, const Prio &p) {
   469       int idx = index[i];
   470       unlace(idx);
   471       data[idx].value = p;
   472       lace(idx);
   473     }
   474 
   475     state_enum state(const Item &i) const {
   476       int idx = index[i];
   477       if (idx >= 0) idx = 0;
   478       return state_enum(idx);
   479     }
   480 
   481     void state(const Item& i, state_enum st) {
   482       switch (st) {
   483       case POST_HEAP:
   484       case PRE_HEAP:
   485         if (state(i) == IN_HEAP) {
   486           erase(i);
   487         }
   488         index[i] = st;
   489         break;
   490       case IN_HEAP:
   491         break;
   492       }
   493     }
   494 
   495   private:
   496 
   497     struct BucketItem {
   498       BucketItem(const Item& _item, int _value) 
   499 	: item(_item), value(_value) {}
   500 
   501       Item item;
   502       int value;
   503 
   504       int prev, next;
   505     };
   506 
   507     ItemIntMap& index;
   508     std::vector<int> first;
   509     std::vector<BucketItem> data;
   510     mutable int maximal;
   511 
   512   }; // class BucketHeap
   513 
   514   /// \ingroup auxdat
   515   ///
   516   /// \brief A Simplified Bucket Heap implementation.
   517   ///
   518   /// This class implements a simplified \e bucket \e heap data
   519   /// structure.  It does not provide some functionality but it faster
   520   /// and simplier data structure than the BucketHeap. The main
   521   /// difference is that the BucketHeap stores for every key a double
   522   /// linked list while this class stores just simple lists. In the
   523   /// other way it does not supports erasing each elements just the
   524   /// minimal and it does not supports key increasing, decreasing.
   525   ///
   526   /// \param _ItemIntMap A read and writable Item int map, used internally
   527   /// to handle the cross references.
   528   /// \param minimize If the given parameter is true then the heap gives back
   529   /// the lowest priority.
   530   ///
   531   /// \sa BucketHeap 
   532   template <typename _ItemIntMap, bool minimize = true >
   533   class SimpleBucketHeap {
   534 
   535   public:
   536     typedef typename _ItemIntMap::Key Item;
   537     typedef int Prio;
   538     typedef std::pair<Item, Prio> Pair;
   539     typedef _ItemIntMap ItemIntMap;
   540 
   541     /// \brief Type to represent the items states.
   542     ///
   543     /// Each Item element have a state associated to it. It may be "in heap",
   544     /// "pre heap" or "post heap". The latter two are indifferent from the
   545     /// heap's point of view, but may be useful to the user.
   546     ///
   547     /// The ItemIntMap \e should be initialized in such way that it maps
   548     /// PRE_HEAP (-1) to any element to be put in the heap...
   549     enum state_enum {
   550       IN_HEAP = 0,
   551       PRE_HEAP = -1,
   552       POST_HEAP = -2
   553     };
   554 
   555   public:
   556 
   557     /// \brief The constructor.
   558     ///
   559     /// The constructor.
   560     /// \param _index should be given to the constructor, since it is used
   561     /// internally to handle the cross references. The value of the map
   562     /// should be PRE_HEAP (-1) for each element.
   563     explicit SimpleBucketHeap(ItemIntMap &_index) 
   564       : index(_index), free(-1), num(0), minimal(0) {}
   565     
   566     /// \brief Returns the number of items stored in the heap.
   567     ///
   568     /// The number of items stored in the heap.
   569     int size() const { return num; }
   570     
   571     /// \brief Checks if the heap stores no items.
   572     ///
   573     /// Returns \c true if and only if the heap stores no items.
   574     bool empty() const { return num == 0; }
   575 
   576     /// \brief Make empty this heap.
   577     /// 
   578     /// Make empty this heap. It does not change the cross reference
   579     /// map.  If you want to reuse a heap what is not surely empty you
   580     /// should first clear the heap and after that you should set the
   581     /// cross reference map for each item to \c PRE_HEAP.
   582     void clear() { 
   583       data.clear(); first.clear(); free = -1; num = 0; minimal = 0;
   584     }
   585 
   586     /// \brief Insert a pair of item and priority into the heap.
   587     ///
   588     /// Adds \c p.first to the heap with priority \c p.second.
   589     /// \param p The pair to insert.
   590     void push(const Pair& p) {
   591       push(p.first, p.second);
   592     }
   593 
   594     /// \brief Insert an item into the heap with the given priority.
   595     ///    
   596     /// Adds \c i to the heap with priority \c p. 
   597     /// \param i The item to insert.
   598     /// \param p The priority of the item.
   599     void push(const Item &i, const Prio &p) {
   600       int idx;
   601       if (free == -1) {
   602         idx = data.size();
   603         data.push_back(BucketItem(i));
   604       } else {
   605         idx = free;
   606         free = data[idx].next;
   607         data[idx].item = i;
   608       }
   609       index[i] = idx;
   610       if (p >= int(first.size())) first.resize(p + 1, -1);
   611       data[idx].next = first[p];
   612       first[p] = idx;
   613       if (p < minimal) {
   614 	minimal = p;
   615       }
   616       ++num;
   617     }
   618 
   619     /// \brief Returns the item with minimum priority.
   620     ///
   621     /// This method returns the item with minimum priority.
   622     /// \pre The heap must be nonempty.  
   623     Item top() const {
   624       while (first[minimal] == -1) {
   625 	++minimal;
   626       }
   627       return data[first[minimal]].item;
   628     }
   629 
   630     /// \brief Returns the minimum priority.
   631     ///
   632     /// It returns the minimum priority.
   633     /// \pre The heap must be nonempty.
   634     Prio prio() const {
   635       while (first[minimal] == -1) {
   636 	++minimal;
   637       }
   638       return minimal;
   639     }
   640 
   641     /// \brief Deletes the item with minimum priority.
   642     ///
   643     /// This method deletes the item with minimum priority from the heap.  
   644     /// \pre The heap must be non-empty.  
   645     void pop() {
   646       while (first[minimal] == -1) {
   647 	++minimal;
   648       }
   649       int idx = first[minimal];
   650       index[data[idx].item] = -2;
   651       first[minimal] = data[idx].next;
   652       data[idx].next = free;
   653       free = idx;
   654       --num;
   655     }
   656     
   657     /// \brief Returns the priority of \c i.
   658     ///
   659     /// This function returns the priority of item \c i.
   660     /// \warning This operator is not a constant time function
   661     /// because it scans the whole data structure to find the proper
   662     /// value.  
   663     /// \pre \c i must be in the heap.
   664     /// \param i The item.
   665     Prio operator[](const Item &i) const {
   666       for (int k = 0; k < first.size(); ++k) {
   667         int idx = first[k];
   668         while (idx != -1) {
   669           if (data[idx].item == i) {
   670             return k;
   671           }
   672           idx = data[idx].next;
   673         }
   674       }
   675       return -1;
   676     }
   677 
   678     /// \brief Returns if \c item is in, has already been in, or has 
   679     /// never been in the heap.
   680     ///
   681     /// This method returns PRE_HEAP if \c item has never been in the
   682     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   683     /// otherwise. In the latter case it is possible that \c item will
   684     /// get back to the heap again.
   685     /// \param i The item.
   686     state_enum state(const Item &i) const {
   687       int idx = index[i];
   688       if (idx >= 0) idx = 0;
   689       return state_enum(idx);
   690     }
   691 
   692   private:
   693 
   694     struct BucketItem {
   695       BucketItem(const Item& _item) 
   696 	: item(_item) {}
   697 
   698       Item item;
   699       int next;
   700     };
   701 
   702     ItemIntMap& index;
   703     std::vector<int> first;
   704     std::vector<BucketItem> data;
   705     int free, num;
   706     mutable int minimal;
   707 
   708   }; // class SimpleBucketHeap
   709 
   710   template <typename _ItemIntMap>
   711   class SimpleBucketHeap<_ItemIntMap, false> {
   712 
   713   public:
   714     typedef typename _ItemIntMap::Key Item;
   715     typedef int Prio;
   716     typedef std::pair<Item, Prio> Pair;
   717     typedef _ItemIntMap ItemIntMap;
   718 
   719     enum state_enum {
   720       IN_HEAP = 0,
   721       PRE_HEAP = -1,
   722       POST_HEAP = -2
   723     };
   724 
   725   public:
   726 
   727     explicit SimpleBucketHeap(ItemIntMap &_index) 
   728       : index(_index), free(-1), num(0), maximal(0) {}
   729     
   730     int size() const { return num; }
   731     
   732     bool empty() const { return num == 0; }
   733 
   734     void clear() { 
   735       data.clear(); first.clear(); free = -1; num = 0; maximal = 0;
   736     }
   737 
   738     void push(const Pair& p) {
   739       push(p.first, p.second);
   740     }
   741 
   742     void push(const Item &i, const Prio &p) {
   743       int idx;
   744       if (free == -1) {
   745         idx = data.size();
   746         data.push_back(BucketItem(i));
   747       } else {
   748         idx = free;
   749         free = data[idx].next;
   750         data[idx].item = i;
   751       }
   752       index[i] = idx;
   753       if (p >= int(first.size())) first.resize(p + 1, -1);
   754       data[idx].next = first[p];
   755       first[p] = idx;
   756       if (p > maximal) {
   757 	maximal = p;
   758       }
   759       ++num;
   760     }
   761 
   762     Item top() const {
   763       while (first[maximal] == -1) {
   764 	--maximal;
   765       }
   766       return data[first[maximal]].item;
   767     }
   768 
   769     Prio prio() const {
   770       while (first[maximal] == -1) {
   771 	--maximal;
   772       }
   773       return maximal;
   774     }
   775 
   776     void pop() {
   777       while (first[maximal] == -1) {
   778 	--maximal;
   779       }
   780       int idx = first[maximal];
   781       index[data[idx].item] = -2;
   782       first[maximal] = data[idx].next;
   783       data[idx].next = free;
   784       free = idx;
   785       --num;
   786     }
   787     
   788     Prio operator[](const Item &i) const {
   789       for (int k = 0; k < first.size(); ++k) {
   790         int idx = first[k];
   791         while (idx != -1) {
   792           if (data[idx].item == i) {
   793             return k;
   794           }
   795           idx = data[idx].next;
   796         }
   797       }
   798       return -1;
   799     }
   800 
   801     state_enum state(const Item &i) const {
   802       int idx = index[i];
   803       if (idx >= 0) idx = 0;
   804       return state_enum(idx);
   805     }
   806 
   807   private:
   808 
   809     struct BucketItem {
   810       BucketItem(const Item& _item) : item(_item) {}
   811 
   812       Item item;
   813 
   814       int next;
   815     };
   816 
   817     ItemIntMap& index;
   818     std::vector<int> first;
   819     std::vector<BucketItem> data;
   820     int free, num;
   821     mutable int maximal;
   822 
   823   };
   824 
   825 }
   826   
   827 #endif