# HG changeset patch
# User deba
# Date 1144172735 0
# Node ID 33db140585439ebcf3b501446bd2df2ba84f5f66
# Parent  32e4bebee6163f84b67c69381813628cd9316bd9
LinearHeap is renamed to BucketHeap which is more conform
and widely used name for this data structure

diff -r 32e4bebee616 -r 33db14058543 demo/coloring.cc
--- a/demo/coloring.cc	Tue Apr 04 17:43:23 2006 +0000
+++ b/demo/coloring.cc	Tue Apr 04 17:45:35 2006 +0000
@@ -30,7 +30,7 @@
 #include <iostream>
 
 #include <lemon/smart_graph.h>
-#include <lemon/linear_heap.h>
+#include <lemon/bucket_heap.h>
 #include <lemon/graph_reader.h>
 #include <lemon/graph_to_eps.h>
 
@@ -63,7 +63,7 @@
   Graph::NodeMap<int> color(graph, -2);
   
   Graph::NodeMap<int> heapMap(graph, -1);
-  LinearHeap<Node, Graph::NodeMap<int> > heap(heapMap);
+  BucketHeap<Node, Graph::NodeMap<int> > heap(heapMap);
   
   for (NodeIt it(graph); it != INVALID; ++it) {
     heap.push(it, countOutEdges(graph, it));
diff -r 32e4bebee616 -r 33db14058543 lemon/Makefile.am
--- a/lemon/Makefile.am	Tue Apr 04 17:43:23 2006 +0000
+++ b/lemon/Makefile.am	Tue Apr 04 17:45:35 2006 +0000
@@ -53,7 +53,7 @@
 	iterable_maps.h \
 	johnson.h \
 	kruskal.h \
-	linear_heap.h \
+	bucket_heap.h \
 	list_graph.h \
 	lp.h \
 	lp_base.h \
diff -r 32e4bebee616 -r 33db14058543 lemon/bucket_heap.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/bucket_heap.h	Tue Apr 04 17:45:35 2006 +0000
@@ -0,0 +1,520 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-2006
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_BUCKET_HEAP_H
+#define LEMON_BUCKET_HEAP_H
+
+///\ingroup auxdat
+///\file
+///\brief Bucket Heap implementation.
+
+#include <vector>
+#include <utility>
+#include <functional>
+
+namespace lemon {
+
+  /// \ingroup auxdat
+
+  /// \brief A Bucket Heap implementation.
+  ///
+  /// This class implements the \e bucket \e heap data structure. A \e heap
+  /// is a data structure for storing items with specified values called \e
+  /// priorities in such a way that finding the item with minimum priority is
+  /// efficient. The bucket heap is very simple implementation, it can store
+  /// only integer priorities and it stores for each priority in the [0..C]
+  /// range a list of items. So it should be used only when the priorities
+  /// are small. It is not intended to use as dijkstra heap.
+  ///
+  /// \param _Item Type of the items to be stored.  
+  /// \param _ItemIntMap A read and writable Item int map, used internally
+  /// to handle the cross references.
+  /// \param minimize If the given parameter is true then the heap gives back
+  /// the lowest priority. 
+  template <typename _Item, typename _ItemIntMap, bool minimize = true >
+  class BucketHeap {
+
+  public:
+    typedef _Item Item;
+    typedef int Prio;
+    typedef std::pair<Item, Prio> Pair;
+    typedef _ItemIntMap ItemIntMap;
+
+    /// \brief Type to represent the items states.
+    ///
+    /// Each Item element have a state associated to it. It may be "in heap",
+    /// "pre heap" or "post heap". The latter two are indifferent from the
+    /// heap's point of view, but may be useful to the user.
+    ///
+    /// The ItemIntMap \e should be initialized in such way that it maps
+    /// PRE_HEAP (-1) to any element to be put in the heap...
+    enum state_enum {
+      IN_HEAP = 0,
+      PRE_HEAP = -1,
+      POST_HEAP = -2
+    };
+
+  public:
+    /// \brief The constructor.
+    ///
+    /// The constructor.
+    /// \param _index should be given to the constructor, since it is used
+    /// internally to handle the cross references. The value of the map
+    /// should be PRE_HEAP (-1) for each element.
+    explicit BucketHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
+    
+    /// The number of items stored in the heap.
+    ///
+    /// \brief Returns the number of items stored in the heap.
+    int size() const { return data.size(); }
+    
+    /// \brief Checks if the heap stores no items.
+    ///
+    /// Returns \c true if and only if the heap stores no items.
+    bool empty() const { return data.empty(); }
+
+    /// \brief Make empty this heap.
+    /// 
+    /// Make empty this heap.
+    void clear() { 
+      for (int i = 0; i < (int)data.size(); ++i) {
+	index[data[i].item] = -2;
+      }
+      data.clear(); first.clear(); minimal = 0;
+    }
+
+  private:
+
+    void relocate_last(int idx) {
+      if (idx + 1 < (int)data.size()) {
+	data[idx] = data.back();
+	if (data[idx].prev != -1) {
+	  data[data[idx].prev].next = idx;
+	} else {
+	  first[data[idx].value] = idx;
+	}
+	if (data[idx].next != -1) {
+	  data[data[idx].next].prev = idx;
+	}
+	index[data[idx].item] = idx;
+      }
+      data.pop_back();
+    }
+
+    void unlace(int idx) {
+      if (data[idx].prev != -1) {
+	data[data[idx].prev].next = data[idx].next;
+      } else {
+	first[data[idx].value] = data[idx].next;
+      }
+      if (data[idx].next != -1) {
+	data[data[idx].next].prev = data[idx].prev;
+      }
+    }
+
+    void lace(int idx) {
+      if ((int)first.size() <= data[idx].value) {
+	first.resize(data[idx].value + 1, -1);
+      }
+      data[idx].next = first[data[idx].value];
+      if (data[idx].next != -1) {
+	data[data[idx].next].prev = idx;
+      }
+      first[data[idx].value] = idx;
+      data[idx].prev = -1;
+    }
+
+  public:
+    /// \brief Insert a pair of item and priority into the heap.
+    ///
+    /// Adds \c p.first to the heap with priority \c p.second.
+    /// \param p The pair to insert.
+    void push(const Pair& p) {
+      push(p.first, p.second);
+    }
+
+    /// \brief Insert an item into the heap with the given priority.
+    ///    
+    /// Adds \c i to the heap with priority \c p. 
+    /// \param i The item to insert.
+    /// \param p The priority of the item.
+    void push(const Item &i, const Prio &p) { 
+      int idx = data.size();
+      index[i] = idx;
+      data.push_back(BucketItem(i, p));
+      lace(idx);
+      if (p < minimal) {
+	minimal = p;
+      }
+    }
+
+    /// \brief Returns the item with minimum priority.
+    ///
+    /// This method returns the item with minimum priority.
+    /// \pre The heap must be nonempty.  
+    Item top() const {
+      while (first[minimal] == -1) {
+	++minimal;
+      }
+      return data[first[minimal]].item;
+    }
+
+    /// \brief Returns the minimum priority.
+    ///
+    /// It returns the minimum priority.
+    /// \pre The heap must be nonempty.
+    Prio prio() const {
+      while (first[minimal] == -1) {
+	++minimal;
+      }
+      return minimal;
+    }
+
+    /// \brief Deletes the item with minimum priority.
+    ///
+    /// This method deletes the item with minimum priority from the heap.  
+    /// \pre The heap must be non-empty.  
+    void pop() {
+      while (first[minimal] == -1) {
+	++minimal;
+      }
+      int idx = first[minimal];
+      index[data[idx].item] = -2;
+      unlace(idx);
+      relocate_last(idx);
+    }
+
+    /// \brief Deletes \c i from the heap.
+    ///
+    /// This method deletes item \c i from the heap, if \c i was
+    /// already stored in the heap.
+    /// \param i The item to erase. 
+    void erase(const Item &i) {
+      int idx = index[i];
+      index[data[idx].item] = -2;
+      unlace(idx);
+      relocate_last(idx);
+    }
+
+    
+    /// \brief Returns the priority of \c i.
+    ///
+    /// This function returns the priority of item \c i.  
+    /// \pre \c i must be in the heap.
+    /// \param i The item.
+    Prio operator[](const Item &i) const {
+      int idx = index[i];
+      return data[idx].value;
+    }
+
+    /// \brief \c i gets to the heap with priority \c p independently 
+    /// if \c i was already there.
+    ///
+    /// This method calls \ref push(\c i, \c p) if \c i is not stored
+    /// in the heap and sets the priority of \c i to \c p otherwise.
+    /// \param i The item.
+    /// \param p The priority.
+    void set(const Item &i, const Prio &p) {
+      int idx = index[i];
+      if (idx < 0) {
+	push(i,p);
+      } else if (p > data[idx].value) {
+	increase(i, p);
+      } else {
+	decrease(i, p);
+      }
+    }
+
+    /// \brief Decreases the priority of \c i to \c p.
+
+    /// This method decreases the priority of item \c i to \c p.
+    /// \pre \c i must be stored in the heap with priority at least \c
+    /// p relative to \c Compare.
+    /// \param i The item.
+    /// \param p The priority.
+    void decrease(const Item &i, const Prio &p) {
+      int idx = index[i];
+      unlace(idx);
+      data[idx].value = p;
+      if (p < minimal) {
+	minimal = p;
+      }
+      lace(idx);
+    }
+    
+    /// \brief Increases the priority of \c i to \c p.
+    ///
+    /// This method sets the priority of item \c i to \c p. 
+    /// \pre \c i must be stored in the heap with priority at most \c
+    /// p relative to \c Compare.
+    /// \param i The item.
+    /// \param p The priority.
+    void increase(const Item &i, const Prio &p) {
+      int idx = index[i];
+      unlace(idx);
+      data[idx].value = p;
+      lace(idx);
+    }
+
+    /// \brief Returns if \c item is in, has already been in, or has 
+    /// never been in the heap.
+    ///
+    /// This method returns PRE_HEAP if \c item has never been in the
+    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
+    /// otherwise. In the latter case it is possible that \c item will
+    /// get back to the heap again.
+    /// \param i The item.
+    state_enum state(const Item &i) const {
+      int idx = index[i];
+      if (idx >= 0) idx = 0;
+      return state_enum(idx);
+    }
+
+    /// \brief Sets the state of the \c item in the heap.
+    ///
+    /// Sets the state of the \c item in the heap. It can be used to
+    /// manually clear the heap when it is important to achive the
+    /// better time complexity.
+    /// \param i The item.
+    /// \param st The state. It should not be \c IN_HEAP. 
+    void state(const Item& i, state_enum st) {
+      switch (st) {
+      case POST_HEAP:
+      case PRE_HEAP:
+        if (state(i) == IN_HEAP) {
+          erase(i);
+        }
+        index[i] = st;
+        break;
+      case IN_HEAP:
+        break;
+      }
+    }
+
+  private:
+
+    struct BucketItem {
+      BucketItem(const Item& _item, int _value) 
+	: item(_item), value(_value) {}
+
+      Item item;
+      int value;
+
+      int prev, next;
+    };
+
+    ItemIntMap& index;
+    std::vector<int> first;
+    std::vector<BucketItem> data;
+    mutable int minimal;
+
+  }; // class BucketHeap
+
+
+  template <typename _Item, typename _ItemIntMap>
+  class BucketHeap<_Item, _ItemIntMap, false> {
+
+  public:
+    typedef _Item Item;
+    typedef int Prio;
+    typedef std::pair<Item, Prio> Pair;
+    typedef _ItemIntMap ItemIntMap;
+
+    enum state_enum {
+      IN_HEAP = 0,
+      PRE_HEAP = -1,
+      POST_HEAP = -2
+    };
+
+  public:
+
+    explicit BucketHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
+
+    int size() const { return data.size(); }
+    bool empty() const { return data.empty(); }
+
+    void clear() { 
+      for (int i = 0; i < (int)data.size(); ++i) {
+	index[data[i].item] = -2;
+      }
+      data.clear(); first.clear(); maximal = -1; 
+    }
+
+  private:
+
+    void relocate_last(int idx) {
+      if (idx + 1 != (int)data.size()) {
+	data[idx] = data.back();
+	if (data[idx].prev != -1) {
+	  data[data[idx].prev].next = idx;
+	} else {
+	  first[data[idx].value] = idx;
+	}
+	if (data[idx].next != -1) {
+	  data[data[idx].next].prev = idx;
+	}
+	index[data[idx].item] = idx;
+      }
+      data.pop_back();
+    }
+
+    void unlace(int idx) {
+      if (data[idx].prev != -1) {
+	data[data[idx].prev].next = data[idx].next;
+      } else {
+	first[data[idx].value] = data[idx].next;
+      }
+      if (data[idx].next != -1) {
+	data[data[idx].next].prev = data[idx].prev;
+      }
+    }
+
+    void lace(int idx) {
+      if ((int)first.size() <= data[idx].value) {
+	first.resize(data[idx].value + 1, -1);
+      }
+      data[idx].next = first[data[idx].value];
+      if (data[idx].next != -1) {
+	data[data[idx].next].prev = idx;
+      }
+      first[data[idx].value] = idx;
+      data[idx].prev = -1;
+    }
+
+  public:
+
+    void push(const Pair& p) {
+      push(p.first, p.second);
+    }
+
+    void push(const Item &i, const Prio &p) { 
+      int idx = data.size();
+      index[i] = idx;
+      data.push_back(BucketItem(i, p));
+      lace(idx);
+      if (data[idx].value > maximal) {
+	maximal = data[idx].value;
+      }
+    }
+
+    Item top() const {
+      while (first[maximal] == -1) {
+	--maximal;
+      }
+      return data[first[maximal]].item;
+    }
+
+    Prio prio() const {
+      while (first[maximal] == -1) {
+	--maximal;
+      }
+      return maximal;
+    }
+
+    void pop() {
+      while (first[maximal] == -1) {
+	--maximal;
+      }
+      int idx = first[maximal];
+      index[data[idx].item] = -2;
+      unlace(idx);
+      relocate_last(idx);
+    }
+
+    void erase(const Item &i) {
+      int idx = index[i];
+      index[data[idx].item] = -2;
+      unlace(idx);
+      relocate_last(idx);
+    }
+
+    Prio operator[](const Item &i) const {
+      int idx = index[i];
+      return data[idx].value;
+    }
+
+    void set(const Item &i, const Prio &p) {
+      int idx = index[i];
+      if (idx < 0) {
+	push(i,p);
+      } else if (p > data[idx].value) {
+	decrease(i, p);
+      } else {
+	increase(i, p);
+      }
+    }
+
+    void decrease(const Item &i, const Prio &p) {
+      int idx = index[i];
+      unlace(idx);
+      data[idx].value = p;
+      if (p > maximal) {
+	maximal = p;
+      }
+      lace(idx);
+    }
+    
+    void increase(const Item &i, const Prio &p) {
+      int idx = index[i];
+      unlace(idx);
+      data[idx].value = p;
+      lace(idx);
+    }
+
+    state_enum state(const Item &i) const {
+      int idx = index[i];
+      if (idx >= 0) idx = 0;
+      return state_enum(idx);
+    }
+
+    void state(const Item& i, state_enum st) {
+      switch (st) {
+      case POST_HEAP:
+      case PRE_HEAP:
+        if (state(i) == IN_HEAP) {
+          erase(i);
+        }
+        index[i] = st;
+        break;
+      case IN_HEAP:
+        break;
+      }
+    }
+
+  private:
+
+    struct BucketItem {
+      BucketItem(const Item& _item, int _value) 
+	: item(_item), value(_value) {}
+
+      Item item;
+      int value;
+
+      int prev, next;
+    };
+
+    ItemIntMap& index;
+    std::vector<int> first;
+    std::vector<BucketItem> data;
+    mutable int maximal;
+
+  }; // class BucketHeap
+
+}
+  
+#endif
diff -r 32e4bebee616 -r 33db14058543 lemon/linear_heap.h
--- a/lemon/linear_heap.h	Tue Apr 04 17:43:23 2006 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,520 +0,0 @@
-/* -*- C++ -*-
- *
- * This file is a part of LEMON, a generic C++ optimization library
- *
- * Copyright (C) 2003-2006
- * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
- * (Egervary Research Group on Combinatorial Optimization, EGRES).
- *
- * Permission to use, modify and distribute this software is granted
- * provided that this copyright notice appears in all copies. For
- * precise terms see the accompanying LICENSE file.
- *
- * This software is provided "AS IS" with no warranty of any kind,
- * express or implied, and with no claim as to its suitability for any
- * purpose.
- *
- */
-
-#ifndef LEMON_LINEAR_HEAP_H
-#define LEMON_LINEAR_HEAP_H
-
-///\ingroup auxdat
-///\file
-///\brief Binary Heap implementation.
-
-#include <vector>
-#include <utility>
-#include <functional>
-
-namespace lemon {
-
-  /// \ingroup auxdat
-
-  /// \brief A Linear Heap implementation.
-  ///
-  /// This class implements the \e linear \e heap data structure. A \e heap
-  /// is a data structure for storing items with specified values called \e
-  /// priorities in such a way that finding the item with minimum priority is
-  /// efficient. The linear heap is very simple implementation, it can store
-  /// only integer priorities and it stores for each priority in the [0..C]
-  /// range a list of items. So it should be used only when the priorities
-  /// are small. It is not intended to use as dijkstra heap.
-  ///
-  /// \param _Item Type of the items to be stored.  
-  /// \param _ItemIntMap A read and writable Item int map, used internally
-  /// to handle the cross references.
-  /// \param minimize If the given parameter is true then the heap gives back
-  /// the lowest priority. 
-  template <typename _Item, typename _ItemIntMap, bool minimize = true >
-  class LinearHeap {
-
-  public:
-    typedef _Item Item;
-    typedef int Prio;
-    typedef std::pair<Item, Prio> Pair;
-    typedef _ItemIntMap ItemIntMap;
-
-    /// \brief Type to represent the items states.
-    ///
-    /// Each Item element have a state associated to it. It may be "in heap",
-    /// "pre heap" or "post heap". The latter two are indifferent from the
-    /// heap's point of view, but may be useful to the user.
-    ///
-    /// The ItemIntMap \e should be initialized in such way that it maps
-    /// PRE_HEAP (-1) to any element to be put in the heap...
-    enum state_enum {
-      IN_HEAP = 0,
-      PRE_HEAP = -1,
-      POST_HEAP = -2
-    };
-
-  public:
-    /// \brief The constructor.
-    ///
-    /// The constructor.
-    /// \param _index should be given to the constructor, since it is used
-    /// internally to handle the cross references. The value of the map
-    /// should be PRE_HEAP (-1) for each element.
-    explicit LinearHeap(ItemIntMap &_index) : index(_index), minimal(0) {}
-    
-    /// The number of items stored in the heap.
-    ///
-    /// \brief Returns the number of items stored in the heap.
-    int size() const { return data.size(); }
-    
-    /// \brief Checks if the heap stores no items.
-    ///
-    /// Returns \c true if and only if the heap stores no items.
-    bool empty() const { return data.empty(); }
-
-    /// \brief Make empty this heap.
-    /// 
-    /// Make empty this heap.
-    void clear() { 
-      for (int i = 0; i < (int)data.size(); ++i) {
-	index[data[i].item] = -2;
-      }
-      data.clear(); first.clear(); minimal = 0;
-    }
-
-  private:
-
-    void relocate_last(int idx) {
-      if (idx + 1 < (int)data.size()) {
-	data[idx] = data.back();
-	if (data[idx].prev != -1) {
-	  data[data[idx].prev].next = idx;
-	} else {
-	  first[data[idx].value] = idx;
-	}
-	if (data[idx].next != -1) {
-	  data[data[idx].next].prev = idx;
-	}
-	index[data[idx].item] = idx;
-      }
-      data.pop_back();
-    }
-
-    void unlace(int idx) {
-      if (data[idx].prev != -1) {
-	data[data[idx].prev].next = data[idx].next;
-      } else {
-	first[data[idx].value] = data[idx].next;
-      }
-      if (data[idx].next != -1) {
-	data[data[idx].next].prev = data[idx].prev;
-      }
-    }
-
-    void lace(int idx) {
-      if ((int)first.size() <= data[idx].value) {
-	first.resize(data[idx].value + 1, -1);
-      }
-      data[idx].next = first[data[idx].value];
-      if (data[idx].next != -1) {
-	data[data[idx].next].prev = idx;
-      }
-      first[data[idx].value] = idx;
-      data[idx].prev = -1;
-    }
-
-  public:
-    /// \brief Insert a pair of item and priority into the heap.
-    ///
-    /// Adds \c p.first to the heap with priority \c p.second.
-    /// \param p The pair to insert.
-    void push(const Pair& p) {
-      push(p.first, p.second);
-    }
-
-    /// \brief Insert an item into the heap with the given priority.
-    ///    
-    /// Adds \c i to the heap with priority \c p. 
-    /// \param i The item to insert.
-    /// \param p The priority of the item.
-    void push(const Item &i, const Prio &p) { 
-      int idx = data.size();
-      index[i] = idx;
-      data.push_back(LinearItem(i, p));
-      lace(idx);
-      if (p < minimal) {
-	minimal = p;
-      }
-    }
-
-    /// \brief Returns the item with minimum priority.
-    ///
-    /// This method returns the item with minimum priority.
-    /// \pre The heap must be nonempty.  
-    Item top() const {
-      while (first[minimal] == -1) {
-	++minimal;
-      }
-      return data[first[minimal]].item;
-    }
-
-    /// \brief Returns the minimum priority.
-    ///
-    /// It returns the minimum priority.
-    /// \pre The heap must be nonempty.
-    Prio prio() const {
-      while (first[minimal] == -1) {
-	++minimal;
-      }
-      return minimal;
-    }
-
-    /// \brief Deletes the item with minimum priority.
-    ///
-    /// This method deletes the item with minimum priority from the heap.  
-    /// \pre The heap must be non-empty.  
-    void pop() {
-      while (first[minimal] == -1) {
-	++minimal;
-      }
-      int idx = first[minimal];
-      index[data[idx].item] = -2;
-      unlace(idx);
-      relocate_last(idx);
-    }
-
-    /// \brief Deletes \c i from the heap.
-    ///
-    /// This method deletes item \c i from the heap, if \c i was
-    /// already stored in the heap.
-    /// \param i The item to erase. 
-    void erase(const Item &i) {
-      int idx = index[i];
-      index[data[idx].item] = -2;
-      unlace(idx);
-      relocate_last(idx);
-    }
-
-    
-    /// \brief Returns the priority of \c i.
-    ///
-    /// This function returns the priority of item \c i.  
-    /// \pre \c i must be in the heap.
-    /// \param i The item.
-    Prio operator[](const Item &i) const {
-      int idx = index[i];
-      return data[idx].value;
-    }
-
-    /// \brief \c i gets to the heap with priority \c p independently 
-    /// if \c i was already there.
-    ///
-    /// This method calls \ref push(\c i, \c p) if \c i is not stored
-    /// in the heap and sets the priority of \c i to \c p otherwise.
-    /// \param i The item.
-    /// \param p The priority.
-    void set(const Item &i, const Prio &p) {
-      int idx = index[i];
-      if (idx < 0) {
-	push(i,p);
-      } else if (p > data[idx].value) {
-	increase(i, p);
-      } else {
-	decrease(i, p);
-      }
-    }
-
-    /// \brief Decreases the priority of \c i to \c p.
-
-    /// This method decreases the priority of item \c i to \c p.
-    /// \pre \c i must be stored in the heap with priority at least \c
-    /// p relative to \c Compare.
-    /// \param i The item.
-    /// \param p The priority.
-    void decrease(const Item &i, const Prio &p) {
-      int idx = index[i];
-      unlace(idx);
-      data[idx].value = p;
-      if (p < minimal) {
-	minimal = p;
-      }
-      lace(idx);
-    }
-    
-    /// \brief Increases the priority of \c i to \c p.
-    ///
-    /// This method sets the priority of item \c i to \c p. 
-    /// \pre \c i must be stored in the heap with priority at most \c
-    /// p relative to \c Compare.
-    /// \param i The item.
-    /// \param p The priority.
-    void increase(const Item &i, const Prio &p) {
-      int idx = index[i];
-      unlace(idx);
-      data[idx].value = p;
-      lace(idx);
-    }
-
-    /// \brief Returns if \c item is in, has already been in, or has 
-    /// never been in the heap.
-    ///
-    /// This method returns PRE_HEAP if \c item has never been in the
-    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
-    /// otherwise. In the latter case it is possible that \c item will
-    /// get back to the heap again.
-    /// \param i The item.
-    state_enum state(const Item &i) const {
-      int idx = index[i];
-      if (idx >= 0) idx = 0;
-      return state_enum(idx);
-    }
-
-    /// \brief Sets the state of the \c item in the heap.
-    ///
-    /// Sets the state of the \c item in the heap. It can be used to
-    /// manually clear the heap when it is important to achive the
-    /// better time complexity.
-    /// \param i The item.
-    /// \param st The state. It should not be \c IN_HEAP. 
-    void state(const Item& i, state_enum st) {
-      switch (st) {
-      case POST_HEAP:
-      case PRE_HEAP:
-        if (state(i) == IN_HEAP) {
-          erase(i);
-        }
-        index[i] = st;
-        break;
-      case IN_HEAP:
-        break;
-      }
-    }
-
-  private:
-
-    struct LinearItem {
-      LinearItem(const Item& _item, int _value) 
-	: item(_item), value(_value) {}
-
-      Item item;
-      int value;
-
-      int prev, next;
-    };
-
-    ItemIntMap& index;
-    std::vector<int> first;
-    std::vector<LinearItem> data;
-    mutable int minimal;
-
-  }; // class LinearHeap
-
-
-  template <typename _Item, typename _ItemIntMap>
-  class LinearHeap<_Item, _ItemIntMap, false> {
-
-  public:
-    typedef _Item Item;
-    typedef int Prio;
-    typedef std::pair<Item, Prio> Pair;
-    typedef _ItemIntMap ItemIntMap;
-
-    enum state_enum {
-      IN_HEAP = 0,
-      PRE_HEAP = -1,
-      POST_HEAP = -2
-    };
-
-  public:
-
-    explicit LinearHeap(ItemIntMap &_index) : index(_index), maximal(-1) {}
-
-    int size() const { return data.size(); }
-    bool empty() const { return data.empty(); }
-
-    void clear() { 
-      for (int i = 0; i < (int)data.size(); ++i) {
-	index[data[i].item] = -2;
-      }
-      data.clear(); first.clear(); maximal = -1; 
-    }
-
-  private:
-
-    void relocate_last(int idx) {
-      if (idx + 1 != (int)data.size()) {
-	data[idx] = data.back();
-	if (data[idx].prev != -1) {
-	  data[data[idx].prev].next = idx;
-	} else {
-	  first[data[idx].value] = idx;
-	}
-	if (data[idx].next != -1) {
-	  data[data[idx].next].prev = idx;
-	}
-	index[data[idx].item] = idx;
-      }
-      data.pop_back();
-    }
-
-    void unlace(int idx) {
-      if (data[idx].prev != -1) {
-	data[data[idx].prev].next = data[idx].next;
-      } else {
-	first[data[idx].value] = data[idx].next;
-      }
-      if (data[idx].next != -1) {
-	data[data[idx].next].prev = data[idx].prev;
-      }
-    }
-
-    void lace(int idx) {
-      if ((int)first.size() <= data[idx].value) {
-	first.resize(data[idx].value + 1, -1);
-      }
-      data[idx].next = first[data[idx].value];
-      if (data[idx].next != -1) {
-	data[data[idx].next].prev = idx;
-      }
-      first[data[idx].value] = idx;
-      data[idx].prev = -1;
-    }
-
-  public:
-
-    void push(const Pair& p) {
-      push(p.first, p.second);
-    }
-
-    void push(const Item &i, const Prio &p) { 
-      int idx = data.size();
-      index[i] = idx;
-      data.push_back(LinearItem(i, p));
-      lace(idx);
-      if (data[idx].value > maximal) {
-	maximal = data[idx].value;
-      }
-    }
-
-    Item top() const {
-      while (first[maximal] == -1) {
-	--maximal;
-      }
-      return data[first[maximal]].item;
-    }
-
-    Prio prio() const {
-      while (first[maximal] == -1) {
-	--maximal;
-      }
-      return maximal;
-    }
-
-    void pop() {
-      while (first[maximal] == -1) {
-	--maximal;
-      }
-      int idx = first[maximal];
-      index[data[idx].item] = -2;
-      unlace(idx);
-      relocate_last(idx);
-    }
-
-    void erase(const Item &i) {
-      int idx = index[i];
-      index[data[idx].item] = -2;
-      unlace(idx);
-      relocate_last(idx);
-    }
-
-    Prio operator[](const Item &i) const {
-      int idx = index[i];
-      return data[idx].value;
-    }
-
-    void set(const Item &i, const Prio &p) {
-      int idx = index[i];
-      if (idx < 0) {
-	push(i,p);
-      } else if (p > data[idx].value) {
-	decrease(i, p);
-      } else {
-	increase(i, p);
-      }
-    }
-
-    void decrease(const Item &i, const Prio &p) {
-      int idx = index[i];
-      unlace(idx);
-      data[idx].value = p;
-      if (p > maximal) {
-	maximal = p;
-      }
-      lace(idx);
-    }
-    
-    void increase(const Item &i, const Prio &p) {
-      int idx = index[i];
-      unlace(idx);
-      data[idx].value = p;
-      lace(idx);
-    }
-
-    state_enum state(const Item &i) const {
-      int idx = index[i];
-      if (idx >= 0) idx = 0;
-      return state_enum(idx);
-    }
-
-    void state(const Item& i, state_enum st) {
-      switch (st) {
-      case POST_HEAP:
-      case PRE_HEAP:
-        if (state(i) == IN_HEAP) {
-          erase(i);
-        }
-        index[i] = st;
-        break;
-      case IN_HEAP:
-        break;
-      }
-    }
-
-  private:
-
-    struct LinearItem {
-      LinearItem(const Item& _item, int _value) 
-	: item(_item), value(_value) {}
-
-      Item item;
-      int value;
-
-      int prev, next;
-    };
-
-    ItemIntMap& index;
-    std::vector<int> first;
-    std::vector<LinearItem> data;
-    mutable int maximal;
-
-  }; // class LinearHeap
-
-}
-  
-#endif
diff -r 32e4bebee616 -r 33db14058543 lemon/min_cut.h
--- a/lemon/min_cut.h	Tue Apr 04 17:43:23 2006 +0000
+++ b/lemon/min_cut.h	Tue Apr 04 17:45:35 2006 +0000
@@ -24,7 +24,7 @@
 
 #include <lemon/list_graph.h>
 #include <lemon/bin_heap.h>
-#include <lemon/linear_heap.h>
+#include <lemon/bucket_heap.h>
 
 #include <lemon/bits/invalid.h>
 #include <lemon/error.h>
@@ -48,7 +48,7 @@
     struct HeapSelector<ConstMap<CapacityKey, Const<int, 1> > > {
       template <typename Key, typename Value, typename Ref>
       struct Selector {
-        typedef LinearHeap<Key, Ref, false > Heap;
+        typedef BucketHeap<Key, Ref, false > Heap;
       };
     };
 
@@ -94,7 +94,7 @@
     /// maximalize the priorities. The default heap type is
     /// the \ref BinHeap, but it is specialized when the
     /// CapacityMap is ConstMap<Graph::Node, Const<int, 1> >
-    /// to LinearHeap.
+    /// to BucketHeap.
     ///
     /// \sa MaxCardinalitySearch
     typedef typename _min_cut_bits
@@ -841,7 +841,7 @@
   ///
   /// The complexity of the algorithm is O(n*e*log(n)) but with Fibonacci 
   /// heap it can be decreased to O(n*e+n^2*log(n)). When the neutral capacity 
-  /// map is used then it uses LinearHeap which results O(n*e) time complexity.
+  /// map is used then it uses BucketHeap which results O(n*e) time complexity.
 #ifdef DOXYGEN
   template <typename _Graph, typename _CapacityMap, typename _Traits>
 #else
diff -r 32e4bebee616 -r 33db14058543 lemon/topology.h
--- a/lemon/topology.h	Tue Apr 04 17:43:23 2006 +0000
+++ b/lemon/topology.h	Tue Apr 04 17:45:35 2006 +0000
@@ -30,7 +30,7 @@
 #include <lemon/concept_check.h>
 
 #include <lemon/bin_heap.h>
-#include <lemon/linear_heap.h>
+#include <lemon/bucket_heap.h>
 
 #include <stack>
 #include <functional>
diff -r 32e4bebee616 -r 33db14058543 test/heap_test.cc
--- a/test/heap_test.cc	Tue Apr 04 17:43:23 2006 +0000
+++ b/test/heap_test.cc	Tue Apr 04 17:45:35 2006 +0000
@@ -31,7 +31,7 @@
 #include <lemon/bin_heap.h>
 #include <lemon/fib_heap.h>
 #include <lemon/radix_heap.h>
-#include <lemon/linear_heap.h>
+#include <lemon/bucket_heap.h>
 
 #include "test_tools.h"
 
@@ -120,14 +120,14 @@
   }
 
   {
-    std::cerr << "Checking Linear Heap" << std::endl;
+    std::cerr << "Checking Bucket Heap" << std::endl;
 
-    typedef LinearHeap<Item, ItemIntMap> IntHeap;
+    typedef BucketHeap<Item, ItemIntMap> IntHeap;
     checkConcept<Heap<Item, Prio, ItemIntMap>, IntHeap>();
     heapSortTest<IntHeap>(100);
     heapIncreaseTest<IntHeap>(100);
 
-    typedef LinearHeap<Node, Graph::NodeMap<int> > NodeHeap;
+    typedef BucketHeap<Node, Graph::NodeMap<int> > NodeHeap;
     checkConcept<Heap<Node, Prio, Graph::NodeMap<int> >, NodeHeap>();
     Timer timer;
     dijkstraHeapTest<Graph, LengthMap, NodeHeap>(graph, length, start);