Section for bisect module.

1 files changed, 55 insertions, 0 deletions

diff --git a/Doc/lib/libbisect.tex b/Doc/lib/libbisect.tex
new file mode 100644
index 0000000..81cb550
--- /dev/null
+++ b/Doc/lib/libbisect.tex
@@ -0,0 +1,55 @@
+% LaTeX produced by Fred L. Drake, Jr. <fdrake@acm.org>, with an
+% example based on the PyModules FAQ entry by Aaron Watters
+% <arw@pythonpros.com>.
+
+\section{Standard Module \module{bisect}}
+\stmodindex{bisect}
+\label{module-bisect}
+
+
+This module provides support for maintaining a list in sorted order
+without having to sort the list after each insertion.  For long lists
+of items with expensive comparison operations, this can be an
+improvement over the more common approach.  The module is called
+\module{bisect} because it uses a basic bisection algorithm to do its
+work.  The source code may be used a useful reference for a working
+example of the algorithm (i.e., the boundary conditions are already
+right!).
+
+The following functions are provided:
+
+\begin{funcdesc}{bisect}{list, item\optional{, lo\optional{, hi}}}
+Locate the proper insertion point for \var{item} in \var{list} to
+maintain sorted order.  The parameters \var{lo} and \var{hi} may be
+used to specify a subset of the list which should be considered.  The
+return value is suitable for use as the first parameter to
+\code{\var{list}.insert()}.
+\end{funcdesc}
+
+\begin{funcdesc}{insort}{list, item\optional{, lo\optional{, hi}}}
+Insert \var{item} in \var{list} in sorted order.  This is equivalent
+to \code{\var{list}.insert(bisect.bisect(\var{list}, \var{item},
+\var{lo}, \var{hi}), \var{item})}.
+\end{funcdesc}
+
+
+\subsection{Example}
+\nodename{bisect-example}
+
+The \function{bisect()} function is generally useful for categorizing
+numeric data.  This example uses \function{bisect()} to look up a
+letter grade for an exam total (say) based on a set of ordered numeric
+breakpoints: 85 and up is an `A', 75..84 is a `B', etc.
+
+\begin{verbatim}
+>>> grades = "FEDCBA"
+>>> breakpoints = [30, 44, 66, 75, 85]
+>>> from bisect import bisect
+>>> def grade(total):
+...           return grades[bisect(breakpoints, total)]
+...
+>>> grade(66)
+'C'
+>>> map(grade, [33, 99, 77, 44, 12, 88])
+['E', 'A', 'B', 'D', 'F', 'A']
+\end{verbatim}