There's a possibility I may need a binary heap in the near future,

[sgt/library] / bheap.h

diff --git a/bheap.h b/bheap.h
new file mode 100644 (file)
index 0000000..8e3d92c
--- /dev/null
+++ b/bheap.h
@@ -0,0 +1,59 @@
+/*
+ * Header file for bheap.c.
+ */
+
+#ifndef BHEAP_H
+#define BHEAP_H
+
+typedef struct bheap bheap;
+
+typedef int (*bheap_cmpfn_t)(void *ctx, const void *x, const void *y);
+
+/*
+ * Create a new binary heap, of maximum size `maxelts'. `eltsize'
+ * is the size of each element (use `sizeof'). `compare' is the
+ * function that determines the ordering between elements;
+ * `compare_ctx' is passed as its first argument.
+ * 
+ * If `direction' is +1, the heap sorts the largest things to the
+ * top, so it can return the largest element easily. If it's -1,
+ * the heap sorts the smallest things to the top.
+ */
+bheap *bheap_new(int maxelts, int eltsize, int direction,
+                bheap_cmpfn_t compare, void *compare_ctx);
+
+/*
+ * Add an element to the heap. Returns `elt', or NULL if the heap
+ * is full.
+ */
+void *bheap_add(bheap *bh, void *elt);
+
+/*
+ * Non-destructively read the topmost element in the heap and store
+ * it at `elt'. Returns `elt', or NULL if the heap is empty.
+ */
+void *bheap_topmost(bheap *bh, void *elt);
+
+/*
+ * Remove, and optionally also read, the topmost element in the
+ * heap. Stores it at `elt' if `elt' is not itself NULL.
+ * 
+ * Returns `elt', or NULL if the heap is empty. Note that if you
+ * pass elt==NULL the two cases can therefore not be distinguished!
+ */
+void *bheap_remove(bheap *bh, void *elt);
+
+/*
+ * Count the number of elements currently in the heap.
+ */
+int bheap_count(bheap *bh);
+
+/*
+ * Destroy a heap. If the elements in the heap need freeing, you'd
+ * better make sure there aren't any left before calling this
+ * function, because the heap code won't know about it and won't do
+ * anything.
+ */
+void bheap_free(bheap *bh);
+
+#endif /* BHEAP_H */