# HG changeset patch
# User deba
# Date 1138191018 0
# Node ID e9af75c90c289a8ac907bbdcc26e0573dae6c54a
# Parent  723b2b81d900d9dc3f895be44d2fd0379c4a78fa
state setting function for heaps

If we know that which elements were in the heap then
we can clear it in better time complexity.

diff -r 723b2b81d900 -r e9af75c90c28 lemon/bin_heap.h
--- a/lemon/bin_heap.h	Tue Jan 24 16:07:38 2006 +0000
+++ b/lemon/bin_heap.h	Wed Jan 25 12:10:18 2006 +0000
@@ -267,6 +267,25 @@
       return state_enum(s);
     }
 
+    /// \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;
+      }
+    }
+
   }; // class BinHeap
 
   
diff -r 723b2b81d900 -r e9af75c90c28 lemon/concept/heap.h
--- a/lemon/concept/heap.h	Tue Jan 24 16:07:38 2006 +0000
+++ b/lemon/concept/heap.h	Wed Jan 25 12:10:18 2006 +0000
@@ -152,6 +152,15 @@
       /// \param i The item.
       state_enum state(const Item &i) const {}
 
+      /// \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) {}
+
 
       template <typename _Heap>
       struct Constraints {
diff -r 723b2b81d900 -r e9af75c90c28 lemon/fib_heap.h
--- a/lemon/fib_heap.h	Tue Jan 24 16:07:38 2006 +0000
+++ b/lemon/fib_heap.h	Wed Jan 25 12:10:18 2006 +0000
@@ -216,6 +216,25 @@
       }
       return state_enum(i);
     }    
+
+    /// \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;
+      }
+    }
     
   private:
     
diff -r 723b2b81d900 -r e9af75c90c28 lemon/linear_heap.h
--- a/lemon/linear_heap.h	Tue Jan 24 16:07:38 2006 +0000
+++ b/lemon/linear_heap.h	Wed Jan 25 12:10:18 2006 +0000
@@ -283,6 +283,25 @@
       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;
+      }
+    }
+
   private:
 
     struct LinearItem {
@@ -459,6 +478,18 @@
       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;
+      }
+    }
+
   private:
 
     struct LinearItem {
diff -r 723b2b81d900 -r e9af75c90c28 lemon/radix_heap.h
--- a/lemon/radix_heap.h	Tue Jan 24 16:07:38 2006 +0000
+++ b/lemon/radix_heap.h	Wed Jan 25 12:10:18 2006 +0000
@@ -406,6 +406,25 @@
       return state_enum(s);
     }
 
+    /// \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;
+      }
+    }
+
   }; // class RadixHeap
 
 } // namespace lemon