X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=ucw%2Fheap.h;h=74e8a12445c39a266b66a465c8c6d4f7b7d97454;hb=97d134124cb7f43e34a976e0d6a79622c67cb455;hp=d8ef8d5c97cd7a6f1829917c8aa4c87a8bb94e3b;hpb=0b3fa7642199922ce6c35ab9d09adcda51913f24;p=libucw.git

diff --git a/ucw/heap.h b/ucw/heap.h
index d8ef8d5c..74e8a124 100644
--- a/ucw/heap.h
+++ b/ucw/heap.h
@@ -1,8 +1,8 @@
 /*
  *	UCW Library -- Universal Heap Macros
  *
- *	(c) 2001 Martin Mares <mj@ucw.cz>
- *	(c) 2005 Tomas Valla <tom@ucw.cz>
+ *	(c) 2001--2012 Martin Mares <mj@ucw.cz>
+ *	(c) 2005--2012 Tomas Valla <tom@ucw.cz>
  *
  *	This software may be freely distributed and used according to the terms
  *	of the GNU Lesser General Public License.
@@ -36,12 +36,22 @@
  *
  * The first element `heap[1]` is always lower or equal to all other elements.
  *
+ * Position tracking
+ * -----------------
+ *
+ * As a heap does not support efficient lookup of an element by value, all functions
+ * acting on existing heap elements need to obtain the position of the element in the
+ * heap. This position has to be tracked by the caller, usually in the supplied swap
+ * callback.
+ *
+ * However, there are some caveats noted in the descriptions of individual functions.
+ *
  * [[macros]]
  * Macros
  * ------
  ***/
 
-/* For internal usage. */
+/* For internal use. */
 #define HEAP_BUBBLE_DOWN_J(heap,num,less,swap)						\
   for (;;)										\
     {											\
@@ -56,7 +66,7 @@
       _j = _l;										\
     }
 
-/* For internal usage. */
+/* For internal use. */
 #define HEAP_BUBBLE_UP_J(heap,num,less,swap)						\
   while (_j > 1)									\
     {											\
@@ -68,7 +78,10 @@
     }
 
 /**
- * Shuffle the unordered array @heap of @num elements to become a valid heap. The time complexity is linear.
+ * Shuffle the items `heap[1]`, ..., `heap[num]` to get a valid heap.
+ * This operation takes linear time.
+ *
+ * Position tracking: Position of `heap[i]` must be initialized to `i` before calling.
  **/
 #define HEAP_INIT(type,heap,num,less,swap)						\
   do {											\
@@ -84,10 +97,12 @@
   } while(0)
 
 /**
- * Delete the minimum element `heap[1]` in `O(log(n))` time.
+ * Delete the minimum element `heap[1]` in `O(log(n))` time. The @num variable is decremented.
  * The removed value is moved just after the resulting heap (`heap[num + 1]`).
+ *
+ * Position tracking: Fully automatic.
  **/
-#define HEAP_DELMIN(type,heap,num,less,swap)						\
+#define HEAP_DELETE_MIN(type,heap,num,less,swap)					\
   do {											\
     uns _j, _l;										\
     type x;										\
@@ -98,31 +113,80 @@
   } while(0)
 
 /**
- * Insert `heap[num + 1]` in `O(log(n))` time.
+ * Insert a new element @elt to the heap. The @num variable is incremented.
+ * This operation takes `O(log(n))` time.
+ *
+ * Position tracking: The position of the new element must be initialized to @num+1
+ * before calling this macro.
  **/
-#define HEAP_INSERT(type,heap,num,less,swap)						\
+#define HEAP_INSERT(type,heap,num,less,swap,elt)					\
   do {											\
     uns _j, _u;										\
     type x;										\
+    heap[++num] = elt;									\
     _j = num;										\
     HEAP_BUBBLE_UP_J(heap,num,less,swap);						\
   } while(0)
 
 /**
- * If you need to increase the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
- * Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
+ * Increase `heap[pos]` to a new value @elt (greater or equal to the previous value).
  * The time complexity is `O(log(n))`.
+ *
+ * Position tracking: Fully automatic.
  **/
-#define HEAP_INCREASE(type,heap,num,less,swap,pos)					\
+#define HEAP_INCREASE(type,heap,num,less,swap,pos,elt)					\
   do {											\
     uns _j, _l;										\
     type x;										\
+    heap[pos] = elt;									\
     _j = pos;										\
     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
   } while(0)
 
 /**
- * Delete `heap[pos]` in `O(log(n))` time.
+ * Decrease `heap[pos]` to a new value @elt (less or equal to the previous value).
+ * The time complexity is `O(log(n))`.
+ *
+ * Position tracking: Fully automatic.
+ **/
+#define HEAP_DECREASE(type,heap,num,less,swap,pos,elt)					\
+  do {											\
+    uns _j, _u;										\
+    type x;										\
+    heap[pos] = elt;									\
+    _j = pos;										\
+    HEAP_BUBBLE_UP_J(heap,num,less,swap);						\
+  } while(0)
+
+/**
+ * Change `heap[pos]` to a new value @elt. The time complexity is `O(log(n))`.
+ * If you know that the new value is always smaller or always greater, it is faster
+ * to use `HEAP_DECREASE` or `HEAP_INCREASE` respectively.
+ *
+ * Position tracking: Fully automatic.
+ **/
+#define HEAP_REPLACE(type,heap,num,less,swap,pos,elt)					\
+  do {											\
+    type _elt = elt;									\
+    if (less(heap[pos], _elt))								\
+      HEAP_INCREASE(type,heap,num,less,swap,pos,_elt);					\
+    else										\
+      HEAP_DECREASE(type,heap,num,less,swap,pos,_elt);					\
+  } while(0)
+
+/**
+ * Replace the minimum `heap[pos]` by a new value @elt. The time complexity is `O(log(n))`.
+ *
+ * Position tracking: Fully automatic.
+ **/
+#define HEAP_REPLACE_MIN(type,heap,num,less,swap,elt)					\
+  HEAP_INCREASE(type,heap,num,less,swap,1,elt)
+
+/**
+ * Delete an arbitrary element, given by its position. The @num variable is decremented.
+ * The operation takes `O(log(n))` time.
+ *
+ * Position tracking: Fully automatic.
  **/
 #define HEAP_DELETE(type,heap,num,less,swap,pos)					\
   do {											\