From dd1d31f3e9b115b3e5a35d18243880ebc41990f2 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Fri, 16 Mar 2001 22:04:59 +0000
Subject: [PATCH] Moved generic heap macros to heap.h.

---
 lib/heap.h | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)
 create mode 100644 lib/heap.h

diff --git a/lib/heap.h b/lib/heap.h
new file mode 100644
index 00000000..268cc257
--- /dev/null
+++ b/lib/heap.h
@@ -0,0 +1,81 @@
+/*
+ *	Sherlock Library -- Universal Heap Macros
+ *
+ *	(c) 2001 Martin Mares <mj@ucw.cz>
+ */
+
+#define HEAP_BUBBLE_DOWN_J(heap,num,less,swap)						\
+  for (;;)										\
+    {											\
+      l = 2*j;										\
+      if (l > num)									\
+	break;										\
+      if (less(heap[j],heap[l]) && (l == num || less(heap[j],heap[l+1])))		\
+	break;										\
+      if (l != num && less(heap[l+1],heap[l]))						\
+	l++;										\
+      swap(heap,j,l,x);									\
+      j = l;										\
+    }
+
+#define HEAP_BUBBLE_UP_J(heap,num,less,swap)						\
+  while (j > 1)										\
+    {											\
+      u = j/2;										\
+      if (less(heap[u], heap[j]))							\
+	break;										\
+      swap(heap,u,j,x);									\
+      j = u;										\
+    }
+
+#define HEAP_INIT(type,heap,num,less,swap)						\
+  do {											\
+    uns i = num;									\
+    uns j, l;										\
+    type x;										\
+    while (i >= 1)									\
+      {											\
+	j = i;										\
+        HEAP_BUBBLE_DOWN_J(heap,num,less,swap)						\
+	i--;										\
+      }											\
+  } while(0)
+
+#define HEAP_DELMIN(type,heap,num,less,swap)						\
+  do {											\
+    uns j, l;										\
+    type x;										\
+    swap(heap,1,num,x);									\
+    num--; 										\
+    j = 1;										\
+    HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
+  } while(0)
+
+#define HEAP_INSERT(type,heap,num,less,swap)						\
+  do {											\
+    uns j, u;										\
+    type x;										\
+    j = num;										\
+    HEAP_BUBBLE_UP_J(heap,num,less,swap);						\
+  } while(0)
+
+#define HEAP_INCREASE(type,heap,num,less,swap)						\
+  do {											\
+    uns j, l;										\
+    type x;										\
+    j = 1;										\
+    HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
+  } while(0)
+
+#define HEAP_DELETE(type,heap,num,less,swap,pos)					\
+  do {											\
+    uns j, l, u;									\
+    type x;										\
+    swap(heap,pos,num,x);								\
+    num--;										\
+    j = pos;										\
+    if (less(heap[j], heap[num+1]))							\
+      HEAP_BUBBLE_UP_J(heap,num,less,swap)						\
+    else										\
+      HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
+  } while(0)
-- 
2.39.2