lemon/linear_heap.h
author deba
Mon, 27 Feb 2006 10:36:01 +0000
changeset 1986 9b56cca61e2e
parent 1906 7fa90b66ca9e
permissions -rw-r--r--
An additional simplier interface for static size graphs.
Node operator()(int) for getting node by index
int index(Node node) for getting index by node
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     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_LINEAR_HEAP_H
    20 #define LEMON_LINEAR_HEAP_H
    21 
    22 ///\ingroup auxdat
    23 ///\file
    24 ///\brief Binary Heap implementation.
    25 
    26 #include <vector>
    27 #include <utility>
    28 #include <functional>
    29 
    30 namespace lemon {
    31 
    32   /// \ingroup auxdat
    33 
    34   /// \brief A Linear Heap implementation.
    35   ///
    36   /// This class implements the \e linear \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 linear heap is very simple implementation, it can store
    40   /// only integer priorities and it stores for each priority in the [0..C]
    41   /// range a list of items. So it should be used only when the priorities
    42   /// are small. It is not intended to use as dijkstra heap.
    43   ///
    44   /// \param _Item Type of the items to be stored.  
    45   /// \param _ItemIntMap A read and writable Item int map, used internally
    46   /// to handle the cross references.
    47   /// \param minimize If the given parameter is true then the heap gives back
    48   /// the lowest priority. 
    49   template <typename _Item, typename _ItemIntMap, bool minimize = true >
    50   class LinearHeap {
    51 
    52   public:
    53     typedef _Item Item;
    54     typedef int Prio;
    55     typedef std::pair<Item, Prio> Pair;
    56     typedef _ItemIntMap ItemIntMap;
    57 
    58     /// \brief Type to represent the items states.
    59     ///
    60     /// Each Item element have a state associated to it. It may be "in heap",
    61     /// "pre heap" or "post heap". The latter two are indifferent from the
    62     /// heap's point of view, but may be useful to the user.
    63     ///
    64     /// The ItemIntMap \e should be initialized in such way that it maps
    65     /// PRE_HEAP (-1) to any element to be put in the heap...
    66     enum state_enum {
    67       IN_HEAP = 0,
    68       PRE_HEAP = -1,
    69       POST_HEAP = -2
    70     };
    71 
    72   public:
    73     /// \brief The constructor.
    74     ///
    75     /// The constructor.
    76     /// \param _index should be given to the constructor, since it is used
    77     /// internally to handle the cross references. The value of the map
    78     /// should be PRE_HEAP (-1) for each element.
    79     explicit LinearHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
    80     
    81     /// The number of items stored in the heap.
    82     ///
    83     /// \brief Returns the number of items stored in the heap.
    84     int size() const { return data.size(); }
    85     
    86     /// \brief Checks if the heap stores no items.
    87     ///
    88     /// Returns \c true if and only if the heap stores no items.
    89     bool empty() const { return data.empty(); }
    90 
    91     /// \brief Make empty this heap.
    92     /// 
    93     /// Make empty this heap.
    94     void clear() { 
    95       for (int i = 0; i < (int)data.size(); ++i) {
    96 	index[data[i].item] = -2;
    97       }
    98       data.clear(); first.clear(); minimal = 0;
    99     }
   100 
   101   private:
   102 
   103     void relocate_last(int idx) {
   104       if (idx + 1 < (int)data.size()) {
   105 	data[idx] = data.back();
   106 	if (data[idx].prev != -1) {
   107 	  data[data[idx].prev].next = idx;
   108 	} else {
   109 	  first[data[idx].value] = idx;
   110 	}
   111 	if (data[idx].next != -1) {
   112 	  data[data[idx].next].prev = idx;
   113 	}
   114 	index[data[idx].item] = idx;
   115       }
   116       data.pop_back();
   117     }
   118 
   119     void unlace(int idx) {
   120       if (data[idx].prev != -1) {
   121 	data[data[idx].prev].next = data[idx].next;
   122       } else {
   123 	first[data[idx].value] = data[idx].next;
   124       }
   125       if (data[idx].next != -1) {
   126 	data[data[idx].next].prev = data[idx].prev;
   127       }
   128     }
   129 
   130     void lace(int idx) {
   131       if ((int)first.size() <= data[idx].value) {
   132 	first.resize(data[idx].value + 1, -1);
   133       }
   134       data[idx].next = first[data[idx].value];
   135       if (data[idx].next != -1) {
   136 	data[data[idx].next].prev = idx;
   137       }
   138       first[data[idx].value] = idx;
   139       data[idx].prev = -1;
   140     }
   141 
   142   public:
   143     /// \brief Insert a pair of item and priority into the heap.
   144     ///
   145     /// Adds \c p.first to the heap with priority \c p.second.
   146     /// \param p The pair to insert.
   147     void push(const Pair& p) {
   148       push(p.first, p.second);
   149     }
   150 
   151     /// \brief Insert an item into the heap with the given priority.
   152     ///    
   153     /// Adds \c i to the heap with priority \c p. 
   154     /// \param i The item to insert.
   155     /// \param p The priority of the item.
   156     void push(const Item &i, const Prio &p) { 
   157       int idx = data.size();
   158       index[i] = idx;
   159       data.push_back(LinearItem(i, p));
   160       lace(idx);
   161       if (p < minimal) {
   162 	minimal = p;
   163       }
   164     }
   165 
   166     /// \brief Returns the item with minimum priority.
   167     ///
   168     /// This method returns the item with minimum priority.
   169     /// \pre The heap must be nonempty.  
   170     Item top() const {
   171       while (first[minimal] == -1) {
   172 	++minimal;
   173       }
   174       return data[first[minimal]].item;
   175     }
   176 
   177     /// \brief Returns the minimum priority.
   178     ///
   179     /// It returns the minimum priority.
   180     /// \pre The heap must be nonempty.
   181     Prio prio() const {
   182       while (first[minimal] == -1) {
   183 	++minimal;
   184       }
   185       return minimal;
   186     }
   187 
   188     /// \brief Deletes the item with minimum priority.
   189     ///
   190     /// This method deletes the item with minimum priority from the heap.  
   191     /// \pre The heap must be non-empty.  
   192     void pop() {
   193       while (first[minimal] == -1) {
   194 	++minimal;
   195       }
   196       int idx = first[minimal];
   197       index[data[idx].item] = -2;
   198       unlace(idx);
   199       relocate_last(idx);
   200     }
   201 
   202     /// \brief Deletes \c i from the heap.
   203     ///
   204     /// This method deletes item \c i from the heap, if \c i was
   205     /// already stored in the heap.
   206     /// \param i The item to erase. 
   207     void erase(const Item &i) {
   208       int idx = index[i];
   209       index[data[idx].item] = -2;
   210       unlace(idx);
   211       relocate_last(idx);
   212     }
   213 
   214     
   215     /// \brief Returns the priority of \c i.
   216     ///
   217     /// This function returns the priority of item \c i.  
   218     /// \pre \c i must be in the heap.
   219     /// \param i The item.
   220     Prio operator[](const Item &i) const {
   221       int idx = index[i];
   222       return data[idx].value;
   223     }
   224 
   225     /// \brief \c i gets to the heap with priority \c p independently 
   226     /// if \c i was already there.
   227     ///
   228     /// This method calls \ref push(\c i, \c p) if \c i is not stored
   229     /// in the heap and sets the priority of \c i to \c p otherwise.
   230     /// \param i The item.
   231     /// \param p The priority.
   232     void set(const Item &i, const Prio &p) {
   233       int idx = index[i];
   234       if (idx < 0) {
   235 	push(i,p);
   236       } else if (p > data[idx].value) {
   237 	increase(i, p);
   238       } else {
   239 	decrease(i, p);
   240       }
   241     }
   242 
   243     /// \brief Decreases the priority of \c i to \c p.
   244 
   245     /// This method decreases the priority of item \c i to \c p.
   246     /// \pre \c i must be stored in the heap with priority at least \c
   247     /// p relative to \c Compare.
   248     /// \param i The item.
   249     /// \param p The priority.
   250     void decrease(const Item &i, const Prio &p) {
   251       int idx = index[i];
   252       unlace(idx);
   253       data[idx].value = p;
   254       if (p < minimal) {
   255 	minimal = p;
   256       }
   257       lace(idx);
   258     }
   259     
   260     /// \brief Increases the priority of \c i to \c p.
   261     ///
   262     /// This method sets the priority of item \c i to \c p. 
   263     /// \pre \c i must be stored in the heap with priority at most \c
   264     /// p relative to \c Compare.
   265     /// \param i The item.
   266     /// \param p The priority.
   267     void increase(const Item &i, const Prio &p) {
   268       int idx = index[i];
   269       unlace(idx);
   270       data[idx].value = p;
   271       lace(idx);
   272     }
   273 
   274     /// \brief Returns if \c item is in, has already been in, or has 
   275     /// never been in the heap.
   276     ///
   277     /// This method returns PRE_HEAP if \c item has never been in the
   278     /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
   279     /// otherwise. In the latter case it is possible that \c item will
   280     /// get back to the heap again.
   281     /// \param i The item.
   282     state_enum state(const Item &i) const {
   283       int idx = index[i];
   284       if (idx >= 0) idx = 0;
   285       return state_enum(idx);
   286     }
   287 
   288     /// \brief Sets the state of the \c item in the heap.
   289     ///
   290     /// Sets the state of the \c item in the heap. It can be used to
   291     /// manually clear the heap when it is important to achive the
   292     /// better time complexity.
   293     /// \param i The item.
   294     /// \param st The state. It should not be \c IN_HEAP. 
   295     void state(const Item& i, state_enum st) {
   296       switch (st) {
   297       case POST_HEAP:
   298       case PRE_HEAP:
   299         if (state(i) == IN_HEAP) {
   300           erase(i);
   301         }
   302         index[i] = st;
   303         break;
   304       case IN_HEAP:
   305         break;
   306       }
   307     }
   308 
   309   private:
   310 
   311     struct LinearItem {
   312       LinearItem(const Item& _item, int _value) 
   313 	: item(_item), value(_value) {}
   314 
   315       Item item;
   316       int value;
   317 
   318       int prev, next;
   319     };
   320 
   321     ItemIntMap& index;
   322     std::vector<int> first;
   323     std::vector<LinearItem> data;
   324     mutable int minimal;
   325 
   326   }; // class LinearHeap
   327 
   328 
   329   template <typename _Item, typename _ItemIntMap>
   330   class LinearHeap<_Item, _ItemIntMap, false> {
   331 
   332   public:
   333     typedef _Item Item;
   334     typedef int Prio;
   335     typedef std::pair<Item, Prio> Pair;
   336     typedef _ItemIntMap ItemIntMap;
   337 
   338     enum state_enum {
   339       IN_HEAP = 0,
   340       PRE_HEAP = -1,
   341       POST_HEAP = -2
   342     };
   343 
   344   public:
   345 
   346     explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
   347 
   348     int size() const { return data.size(); }
   349     bool empty() const { return data.empty(); }
   350 
   351     void clear() { 
   352       for (int i = 0; i < (int)data.size(); ++i) {
   353 	index[data[i].item] = -2;
   354       }
   355       data.clear(); first.clear(); maximal = -1; 
   356     }
   357 
   358   private:
   359 
   360     void relocate_last(int idx) {
   361       if (idx + 1 != (int)data.size()) {
   362 	data[idx] = data.back();
   363 	if (data[idx].prev != -1) {
   364 	  data[data[idx].prev].next = idx;
   365 	} else {
   366 	  first[data[idx].value] = idx;
   367 	}
   368 	if (data[idx].next != -1) {
   369 	  data[data[idx].next].prev = idx;
   370 	}
   371 	index[data[idx].item] = idx;
   372       }
   373       data.pop_back();
   374     }
   375 
   376     void unlace(int idx) {
   377       if (data[idx].prev != -1) {
   378 	data[data[idx].prev].next = data[idx].next;
   379       } else {
   380 	first[data[idx].value] = data[idx].next;
   381       }
   382       if (data[idx].next != -1) {
   383 	data[data[idx].next].prev = data[idx].prev;
   384       }
   385     }
   386 
   387     void lace(int idx) {
   388       if ((int)first.size() <= data[idx].value) {
   389 	first.resize(data[idx].value + 1, -1);
   390       }
   391       data[idx].next = first[data[idx].value];
   392       if (data[idx].next != -1) {
   393 	data[data[idx].next].prev = idx;
   394       }
   395       first[data[idx].value] = idx;
   396       data[idx].prev = -1;
   397     }
   398 
   399   public:
   400 
   401     void push(const Pair& p) {
   402       push(p.first, p.second);
   403     }
   404 
   405     void push(const Item &i, const Prio &p) { 
   406       int idx = data.size();
   407       index[i] = idx;
   408       data.push_back(LinearItem(i, p));
   409       lace(idx);
   410       if (data[idx].value > maximal) {
   411 	maximal = data[idx].value;
   412       }
   413     }
   414 
   415     Item top() const {
   416       while (first[maximal] == -1) {
   417 	--maximal;
   418       }
   419       return data[first[maximal]].item;
   420     }
   421 
   422     Prio prio() const {
   423       while (first[maximal] == -1) {
   424 	--maximal;
   425       }
   426       return maximal;
   427     }
   428 
   429     void pop() {
   430       while (first[maximal] == -1) {
   431 	--maximal;
   432       }
   433       int idx = first[maximal];
   434       index[data[idx].item] = -2;
   435       unlace(idx);
   436       relocate_last(idx);
   437     }
   438 
   439     void erase(const Item &i) {
   440       int idx = index[i];
   441       index[data[idx].item] = -2;
   442       unlace(idx);
   443       relocate_last(idx);
   444     }
   445 
   446     Prio operator[](const Item &i) const {
   447       int idx = index[i];
   448       return data[idx].value;
   449     }
   450 
   451     void set(const Item &i, const Prio &p) {
   452       int idx = index[i];
   453       if (idx < 0) {
   454 	push(i,p);
   455       } else if (p > data[idx].value) {
   456 	decrease(i, p);
   457       } else {
   458 	increase(i, p);
   459       }
   460     }
   461 
   462     void decrease(const Item &i, const Prio &p) {
   463       int idx = index[i];
   464       unlace(idx);
   465       data[idx].value = p;
   466       if (p > maximal) {
   467 	maximal = p;
   468       }
   469       lace(idx);
   470     }
   471     
   472     void increase(const Item &i, const Prio &p) {
   473       int idx = index[i];
   474       unlace(idx);
   475       data[idx].value = p;
   476       lace(idx);
   477     }
   478 
   479     state_enum state(const Item &i) const {
   480       int idx = index[i];
   481       if (idx >= 0) idx = 0;
   482       return state_enum(idx);
   483     }
   484 
   485     void state(const Item& i, state_enum st) {
   486       switch (st) {
   487       case POST_HEAP:
   488       case PRE_HEAP:
   489         if (state(i) == IN_HEAP) {
   490           erase(i);
   491         }
   492         index[i] = st;
   493         break;
   494       case IN_HEAP:
   495         break;
   496       }
   497     }
   498 
   499   private:
   500 
   501     struct LinearItem {
   502       LinearItem(const Item& _item, int _value) 
   503 	: item(_item), value(_value) {}
   504 
   505       Item item;
   506       int value;
   507 
   508       int prev, next;
   509     };
   510 
   511     ItemIntMap& index;
   512     std::vector<int> first;
   513     std::vector<LinearItem> data;
   514     mutable int maximal;
   515 
   516   }; // class LinearHeap
   517 
   518 }
   519   
   520 #endif