From 79b816d635673f2a195eee048473572b18b718c8 Mon Sep 17 00:00:00 2001 From: Pavel Charvat Date: Wed, 12 Nov 2008 17:12:19 +0100 Subject: [PATCH] Doc: * Documented binary heaps. * Documented binomial heaps (missing example). * Some fixes. --- ucw/binheap-node.h | 12 ++++++++ ucw/binheap.h | 70 +++++++++++++++++++++++-------------------- ucw/doc/Makefile | 2 +- ucw/doc/binheap.txt | 19 ++++++++++++ ucw/doc/binsearch.txt | 33 ++++++++------------ ucw/doc/heap.txt | 40 +++++++++++++++++++++++++ ucw/doc/index.txt | 6 ++-- ucw/heap.h | 59 ++++++++++++++++++++++++++++++++++-- 8 files changed, 180 insertions(+), 61 deletions(-) create mode 100644 ucw/doc/binheap.txt create mode 100644 ucw/doc/heap.txt diff --git a/ucw/binheap-node.h b/ucw/binheap-node.h index afbda63b..19c0105d 100644 --- a/ucw/binheap-node.h +++ b/ucw/binheap-node.h @@ -10,6 +10,15 @@ #ifndef _UCW_BINHEAP_NODE_H #define _UCW_BINHEAP_NODE_H +/*** + * [common] + * Common definitions + * ------------------ + ***/ + +/** + * Common header of binomial heap nodes. + **/ struct bh_node { struct bh_node *first_son; struct bh_node *last_son; @@ -17,6 +26,9 @@ struct bh_node { byte order; }; +/** + * A binomial heap. + **/ struct bh_heap { struct bh_node root; }; diff --git a/ucw/binheap.h b/ucw/binheap.h index bc498e41..42253e1b 100644 --- a/ucw/binheap.h +++ b/ucw/binheap.h @@ -12,49 +12,53 @@ * this file with parameters set in the corresponding preprocessor macros * as described below, it generates functions for manipulating the particular * version of the binomial heap. + */ + +/*** + * [[generator]] + * Interface to the generator + * -------------------------- * - * You need to specify: + * To use the binomial heaps, you need to specify: * - * BH_PREFIX(x) macro to add a name prefix (used on all global names - * defined by the hash table generator). All further - * names mentioned here except for macro names will be - * implicitly prefixed. + * - `BH_PREFIX(x)` -- macro to add a name prefix (used on all global names + * defined by the generator). All further names mentioned + * here except for macro names will be implicitly prefixed. * - * Then you continue by including "ucw/binheap-node.h" which defines struct bh_node - * and struct bh_root (both without prefix). The heap elements are always allocated by - * you and they must include struct bh_node which serves as a handle used for all - * the heap functions and it contains all information needed for heap-keeping. - * The heap itself is also allocated by you and it's represented by struct bh_heap. + * Then you continue by including `ucw/binheap-node.h` which defines <> + * and <> (both without prefix). The heap elements are always allocated by + * you and they must include `struct bh_node` which serves as a handle used for all + * the heap functions and it contains all information needed for heap-keeping. + * The heap itself is also allocated by you and it's represented by `struct bh_heap`. * - * When you have the declaration of heap nodes, you continue with defining: + * When you have the declaration of heap nodes, you continue with defining: * - * less(p,q) returns 1 if the key corresponding to bh_node *p - * is less than the one corresponding to *q. + * - `less(p,q)` -- returns `1` if the key corresponding to `bh_node *p` + * is less than the one corresponding to `*q`. * - * Then specify what operations you request: + * Then specify what operations you request: * - * init(heap*) -- initialize the heap. - * BH_WANT_INSERT insert(heap*, node*) -- insert the node to the heap. - * BH_WANT_FINDMIN node *findmin(heap*) -- find node with minimum key. - * BH_WANT_DELETEMIN node *deletemin(heap*) -- findmin and delete the node. + * - `init(heap\*)` -- initialize the heap (always defined). + * - `insert(heap\*, node\*)` -- insert the node to the heap (`BH_WANT_INSERT`). + * - `node\* findmin(heap\*)` -- find node with minimum key (`BH_WANT_FINDMIN`). + * - `node\* deletemin(heap\*)` -- findmin and delete the node (`BH_WANT_DELETEMIN`). * - * Then include "ucw/binheap.h" and voila, you have a binomial heap - * suiting all your needs (at least those which you've revealed :) ). + * Then include `ucw/binheap.h` and voila, you have a binomial heap + * suiting all your needs (at least those which you've revealed :) ). * - * You also get a iterator macro at no extra charge: + * You also get a iterator macro at no extra charge: * - * BH_FOR_ALL(bh_prefix, hash*, variable) - * { - * // node *variable gets declared automatically - * do_something_with_node(variable); - * // use BH_BREAK and BH_CONTINUE instead of break and continue - * // you must not alter contents of the hash table here - * } - * BH_END_FOR; + * BH_FOR_ALL(bh_prefix, heap*, variable) + * { + * // node* variable gets declared automatically + * do_something_with_node(variable); + * // use BH_BREAK and BH_CONTINUE instead of break and continue + * // you must not alter contents of the binomial heap here + * } + * BH_END_FOR; * - * After including this file, all parameter macros are automatically - * undef'd. - */ + * After including this file, all parameter macros are automatically undef'd. + ***/ #define BH_NODE struct bh_node #define BH_HEAP struct bh_heap @@ -107,7 +111,7 @@ BH_PREFIX(merge)(BH_NODE *a, BH_NODE *b) s->next_sibling = q; q = s; } - else /* otherwise put the result to the a's list */ + else /* otherwise put the result to the a's list */ { p = s->next_sibling = *pp; *pp = s; diff --git a/ucw/doc/Makefile b/ucw/doc/Makefile index 7e522578..c14ff1ec 100644 --- a/ucw/doc/Makefile +++ b/ucw/doc/Makefile @@ -2,7 +2,7 @@ DIRS+=ucw/doc -UCW_DOCS=fastbuf index config configure install basecode hash docsys conf mempool eltpool mainloop generic growbuf unaligned lists chartype unicode prime binsearch +UCW_DOCS=fastbuf index config configure install basecode hash docsys conf mempool eltpool mainloop generic growbuf unaligned lists chartype unicode prime binsearch heap binheap UCW_INDEX=$(o)/ucw/doc/def_index.html UCW_DOCS_HTML=$(addprefix $(o)/ucw/doc/,$(addsuffix .html,$(UCW_DOCS))) diff --git a/ucw/doc/binheap.txt b/ucw/doc/binheap.txt new file mode 100644 index 00000000..adc26010 --- /dev/null +++ b/ucw/doc/binheap.txt @@ -0,0 +1,19 @@ +Binomial heaps +============== + +* <> +* <> +* <> + +[[intro]] +Introduction +------------ + +Binomial heap is a data structure that supports for example efficient merge of two heaps, insertions, deletions or access to the minimum element. +All these operations are logarithimc in the worst case. If the merge is not significat, it is usually better to use simplier <>. + +They are defined in `ucw/binheap.h` as <>, some common definitions are also in `ucw/binheap-node.h`. + +!!ucw/binheap-node.h + +!!ucw/binheap.h diff --git a/ucw/doc/binsearch.txt b/ucw/doc/binsearch.txt index 6cd45fd2..211bd735 100644 --- a/ucw/doc/binsearch.txt +++ b/ucw/doc/binsearch.txt @@ -3,8 +3,6 @@ Binary search * <> * <> - - <> - - <> !!ucw/binsearch.h @@ -16,11 +14,8 @@ You can find few examples of binary search usage. Although we define only few ma for several different cases, for example to find lower elements in a (non-)decreasing array or even to find elements in a (non-)increasing array. -[[ex_num]] -Numbers -~~~~~~~ - static int inc[10] = { 1, 4, 4, 5, 6, 10, 11, 20, 25, 50 }; + static const char *str[5] = { "aaa", "abc", "bflmpsvz", "rep", "rep" }; static int dec[3] = { 5, 2, 1 }; // find the first equal element @@ -33,28 +28,24 @@ Numbers printf("%d\n", BIN_SEARCH_GE(inc, 10, 4)); // prints 1 printf("%d\n", BIN_SEARCH_GE(inc, 10, 99)); // prints 10 (not found) - // find the first greater element + // find the last equal element (or -1 if does not exist) #define CMP_LE(ary, i, x) ((ary[i]) <= (x)) + int i = BIN_SEARCH_FIRST_GE_CMP(inc, 10, 4, CMP_LE); + printf("%d\n", (i && inc[i - 1] == 4) ? i - 1 : -1); // prints 2 + + // find the first greater element printf("%d\n", BIN_SEARCH_FIRST_GE_CMP(inc, 10, 25, CMP_LE)); // prints 9 - // find the last lower or equal element (or -1 if not found) + // find the last lower or equal element (or -1 if does not exist) printf("%d\n", BIN_SEARCH_FIRST_GE_CMP(inc, 10, 25, CMP_LE) - 1); // prints 8 - // find the last lower element (or -1 if not found) + // find the last lower element (or -1 if does not exist) printf("%d\n", BIN_SEARCH_FIRST_GE(inc, 10, 25) - 1); // prints 7 + // find the first greater or equal string + #define CMP_STR(ary, i, x) (strcmp((ary[i]), (x)) < 0) + printf("%d\n", BIN_SEARCH_GE_CMP(str, 5, "bfl", CMP_STR)); // prints 2 + // find the first lower or equal element in the non-increasing array #define CMP_GT(ary, i, x) ((ary[i]) > (x)) printf("%d\n", BIN_SEARCH_FIRST_GE_CMP(dec, 3, 4, CMP_GT)); // prints 1 - - // ... - -[[ex_str]] -Strings -~~~~~~~ - - static char *str[5] = { "aaa", "abc", "bflmpsvz", "rep", "rep" }; - - #define CMP_STR(ary, i, x) (strcmp((ary[i]), (x)) < 0) - - printf("%d\n", BIN_SEARCH_GE_CMP(str, 5, "bfl", CMP_STR)); // prints 2 diff --git a/ucw/doc/heap.txt b/ucw/doc/heap.txt new file mode 100644 index 00000000..64729a17 --- /dev/null +++ b/ucw/doc/heap.txt @@ -0,0 +1,40 @@ +Binary heaps +============ + +* <> +* <> +* <> + +!!ucw/heap.h + +[[example]] +Example +------- + + static uns n; + static int heap[4]; + + // Create an empty heap + n = 0; + #define MY_CMP(x, y) ((x) < (y)) + + // Insert 20, 10, 30 + heap[n + 1] = 20; + HEAP_INSERT(int, heap, n, MY_CMP, HEAP_SWAP); + heap[n + 1] = 10; + HEAP_INSERT(int, heap, n, MY_CMP, HEAP_SWAP); + heap[n + 1] = 30; + HEAP_INSERT(int, heap, n, MY_CMP, HEAP_SWAP); + + // Remove the minimum (10) + HEAP_DELMIN(int, heap, n, MY_CMP, HEAP_SWAP); + + // Print the new minimum (20) + printf("%d", heap[1]); + + // Increase the minimum by 20 to 40 + heap[1] += 20; + HEAP_INCREASE(int, heap, n, MY_CMP, HEAP_SWAP, 1); + + // Print the new minimum (30) + printf("%d", heap[1]); diff --git a/ucw/doc/index.txt b/ucw/doc/index.txt index 1f26e541..ab7dce96 100644 --- a/ucw/doc/index.txt +++ b/ucw/doc/index.txt @@ -28,6 +28,8 @@ Modules - <> - <> - <> +- <> +- <> Other features -------------- @@ -40,10 +42,6 @@ Yet undocumented modules ------------------------ - Sorting * `sorter/` -- Heaps - * `binheap.h` - * `binheap-node.h` - * `heap.h` - Hash tables * `hashtable.h` - Trie diff --git a/ucw/heap.h b/ucw/heap.h index 4f83776f..d8ef8d5c 100644 --- a/ucw/heap.h +++ b/ucw/heap.h @@ -8,6 +8,40 @@ * of the GNU Lesser General Public License. */ +/*** + * [[intro]] + * Introduction + * ------------ + * + * Binary heap is a simple data structure, which for example supports efficient insertions, deletions + * and access to the minimal inserted item. We define several macros for such operations. + * Note that because of simplicity of heaps, we have decided to define direct macros instead + * of a <> as for several other data structures in the Libucw. + * + * A heap is represented by a number of elements and by an array of values. Beware that we + * index this array from one, not from zero as do the standard C arrays. + * + * Most macros use these parameters: + * + * - @type - the type of elements + * - @num - a variable (signed or unsigned integer) with the number of elements + * - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused + * - @less - a callback to compare two element values; `less(x, y)` shall return a non-zero value iff @x is lower than @y + * - @swap - a callback to swap two array elements; `swap(heap, i, j, t)` must swap `heap[i]` with `heap[j]` with possible help of temporary variable @t (type @type). + * + * A valid heap must follow these rules: + * + * - `num >= 0` + * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]` + * + * The first element `heap[1]` is always lower or equal to all other elements. + * + * [[macros]] + * Macros + * ------ + ***/ + +/* For internal usage. */ #define HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \ for (;;) \ { \ @@ -22,6 +56,7 @@ _j = _l; \ } +/* For internal usage. */ #define HEAP_BUBBLE_UP_J(heap,num,less,swap) \ while (_j > 1) \ { \ @@ -32,6 +67,9 @@ _j = _u; \ } +/** + * Shuffle the unordered array @heap of @num elements to become a valid heap. The time complexity is linear. + **/ #define HEAP_INIT(type,heap,num,less,swap) \ do { \ uns _i = num; \ @@ -45,16 +83,23 @@ } \ } while(0) +/** + * Delete the minimum element `heap[1]` in `O(log(n))` time. + * The removed value is moved just after the resulting heap (`heap[num + 1]`). + **/ #define HEAP_DELMIN(type,heap,num,less,swap) \ do { \ uns _j, _l; \ type x; \ swap(heap,1,num,x); \ - num--; \ + num--; \ _j = 1; \ HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ } while(0) +/** + * Insert `heap[num + 1]` in `O(log(n))` time. + **/ #define HEAP_INSERT(type,heap,num,less,swap) \ do { \ uns _j, _u; \ @@ -63,6 +108,11 @@ 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. + * The time complexity is `O(log(n))`. + **/ #define HEAP_INCREASE(type,heap,num,less,swap,pos) \ do { \ uns _j, _l; \ @@ -71,6 +121,9 @@ HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ } while(0) +/** + * Delete `heap[pos]` in `O(log(n))` time. + **/ #define HEAP_DELETE(type,heap,num,less,swap,pos) \ do { \ uns _j, _l, _u; \ @@ -84,5 +137,7 @@ HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ } while(0) -/* Default swapping macro */ +/** + * Default swapping macro. + **/ #define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t) -- 2.39.5