From d01c657430d2787fd0f9d4692632ee1c9e51d70d Mon Sep 17 00:00:00 2001
From: Pavel Charvat <pchar@ucw.cz>
Date: Mon, 10 Nov 2008 15:48:24 +0100
Subject: [PATCH] Doc: Described binsearch.h.

---
 ucw/binsearch.h       | 22 ++++++++++++++++
 ucw/doc/Makefile      |  2 +-
 ucw/doc/binsearch.txt | 60 +++++++++++++++++++++++++++++++++++++++++++
 ucw/doc/index.txt     |  3 +--
 4 files changed, 84 insertions(+), 3 deletions(-)
 create mode 100644 ucw/doc/binsearch.txt

diff --git a/ucw/binsearch.h b/ucw/binsearch.h
index 67419563..f625c2ae 100644
--- a/ucw/binsearch.h
+++ b/ucw/binsearch.h
@@ -7,6 +7,17 @@
  *	of the GNU Lesser General Public License.
  */
 
+/***
+ * [[defs]]
+ * Definitions
+ * -----------
+ ***/
+
+/**
+ * Find the first element not lower than @x in the sorted array @ary of @N elements (non-decreasing order).
+ * Returns the index of the found element or @N if no exists. Uses `ary_lt_x(ary,i,x)` to compare the @i'th element with @x.
+ * The time complexity is `O(log(N))`.
+ **/
 #define BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ary_lt_x)  ({		\
   uns l = 0, r = (N);						\
   while (l < r)							\
@@ -20,7 +31,18 @@
   l;								\
 })
 
+/**
+ * The default comparision macro for @BIN_SEARCH_FIRST_GE_CMP().
+ **/
 #define ARY_LT_NUM(ary,i,x) (ary)[i] < (x)
 
+/**
+ * Same as @BIN_SEARCH_FIRST_GE_CMP(), but uses the default `<` operator for comparisions.
+ **/
 #define BIN_SEARCH_FIRST_GE(ary,N,x) BIN_SEARCH_FIRST_GE_CMP(ary,N,x,ARY_LT_NUM)
+
+/**
+ * Search the sorted array @ary of @N elements (non-decreasing) for the first occurence of @x.
+ * Returns the index or -1 if no such element exists. Uses the `<` operator for comparisions.
+ **/
 #define BIN_SEARCH_EQ(ary,N,x) ({ int i = BIN_SEARCH_FIRST_GE(ary,N,x); if (i >= (N) || (ary)[i] != (x)) i=-1; i; })
diff --git a/ucw/doc/Makefile b/ucw/doc/Makefile
index 253bd3d2..7e522578 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
+UCW_DOCS=fastbuf index config configure install basecode hash docsys conf mempool eltpool mainloop generic growbuf unaligned lists chartype unicode prime binsearch
 UCW_INDEX=$(o)/ucw/doc/def_index.html
 UCW_DOCS_HTML=$(addprefix $(o)/ucw/doc/,$(addsuffix .html,$(UCW_DOCS)))
 
diff --git a/ucw/doc/binsearch.txt b/ucw/doc/binsearch.txt
new file mode 100644
index 00000000..6cd45fd2
--- /dev/null
+++ b/ucw/doc/binsearch.txt
@@ -0,0 +1,60 @@
+Binary search
+=============
+
+* <<defs,Definitions>>
+* <<examples,Examples>>
+  - <<ex_numbers,Numbers>>
+  - <<ex_strings,Strings>>
+
+!!ucw/binsearch.h
+
+[[examples]]
+Examples
+--------
+
+You can find few examples of binary search usage. Although we define only few macros, they can be used
+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 int dec[3] = { 5, 2, 1 };
+
+  // find the first equal element
+  printf("%d\n", BIN_SEARCH_EQ(inc, 10, 4));				// prints 1
+  printf("%d\n", BIN_SEARCH_EQ(inc, 10, 15));				// prints -1 (not found)
+
+  // find the first greater or equal element
+  printf("%d\n", BIN_SEARCH_GE(inc, 10, 9));				// prints 5
+  printf("%d\n", BIN_SEARCH_GE(inc, 10, 10));				// prints 5
+  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
+  #define CMP_LE(ary, i, x) ((ary[i]) <= (x))
+  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)
+  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)
+  printf("%d\n", BIN_SEARCH_FIRST_GE(inc, 10, 25) - 1);			// prints 7
+
+  // 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/index.txt b/ucw/doc/index.txt
index 60e2b93e..1f26e541 100644
--- a/ucw/doc/index.txt
+++ b/ucw/doc/index.txt
@@ -27,6 +27,7 @@ Modules
 - <<chartype:,Single-byte characters>>
 - <<unicode:,Multi-byte characters>>
 - <<prime:,Prime numbers>>
+- <<binsearch:,Binary search>>
 
 Other features
 --------------
@@ -39,8 +40,6 @@ Yet undocumented modules
 ------------------------
 - Sorting
   * `sorter/`
-- Binary search
-  * `binsearch.h`
 - Heaps
   * `binheap.h`
   * `binheap-node.h`
-- 
2.39.2