Copyright (C) 1991, 1992 Free Software Foundation

This manual describes Elib, the GNU emacs lisp library version 1.0.  The
functions and data types in Elib are supposed to be a common base for
all kinds of other elisp packages and are not programs, modes or
packages of their own.

GNU GENERAL PUBLIC LICENSE
**************************

                         Version 2, June 1991

     Copyright (C) 1989, 1991 Free Software Foundation, Inc.
     675 Mass Ave, Cambridge, MA 02139, USA

     Everyone is permitted to copy and distribute verbatim copies
     of this license document, but changing it is not allowed.

Preamble
========

The licenses for most software are designed to take away your freedom to
share and change it.  By contrast, the GNU General Public License is
intended to guarantee your freedom to share and change free software--to
make sure the software is free for all its users.  This General Public
License applies to most of the Free Software Foundation's software and
to any other program whose authors commit to using it.  (Some other Free
Software Foundation software is covered by the GNU Library General
Public License instead.)  You can apply it to your programs, too.

   When we speak of free software, we are referring to freedom, not
price.  Our General Public Licenses are designed to make sure that you
have the freedom to distribute copies of free software (and charge for
this service if you wish), that you receive source code or can get it if
you want it, that you can change the software or use pieces of it in new
free programs; and that you know you can do these things.

   To protect your rights, we need to make restrictions that forbid
anyone to deny you these rights or to ask you to surrender the rights.
These restrictions translate to certain responsibilities for you if you
distribute copies of the software, or if you modify it.

   For example, if you distribute copies of such a program, whether
gratis or for a fee, you must give the recipients all the rights that
you have.  You must make sure that they, too, receive or can get the
source code.  And you must show them these terms so they know their
rights.

   We protect your rights with two steps: (1) copyright the software,
and (2) offer you this license which gives you legal permission to copy,
distribute and/or modify the software.

   Also, for each author's protection and ours, we want to make certain
that everyone understands that there is no warranty for this free
software.  If the software is modified by someone else and passed on, we
want its recipients to know that what they have is not the original, so
that any problems introduced by others will not reflect on the original
authors' reputations.

   Finally, any free program is threatened constantly by software
patents.  We wish to avoid the danger that redistributors of a free
program will individually obtain patent licenses, in effect making the
program proprietary.  To prevent this, we have made it clear that any
patent must be licensed for everyone's free use or not licensed at all.

   The precise terms and conditions for copying, distribution and
modification follow.

    TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

  1. This License applies to any program or other work which contains a
     notice placed by the copyright holder saying it may be distributed
     under the terms of this General Public License.  The "Program",
     below, refers to any such program or work, and a "work based on the
     Program" means either the Program or any derivative work under
     copyright law: that is to say, a work containing the Program or a
     portion of it, either verbatim or with modifications and/or
     translated into another language.  (Hereinafter, translation is
     included without limitation in the term "modification".)  Each
     licensee is addressed as "you".

     Activities other than copying, distribution and modification are
     not covered by this License; they are outside its scope.  The act
     of running the Program is not restricted, and the output from the
     Program is covered only if its contents constitute a work based on
     the Program (independent of having been made by running the
     Program).  Whether that is true depends on what the Program does.

  2. You may copy and distribute verbatim copies of the Program's source
     code as you receive it, in any medium, provided that you
     conspicuously and appropriately publish on each copy an appropriate
     copyright notice and disclaimer of warranty; keep intact all the
     notices that refer to this License and to the absence of any
     warranty; and give any other recipients of the Program a copy of
     this License along with the Program.

     You may charge a fee for the physical act of transferring a copy,
     and you may at your option offer warranty protection in exchange
     for a fee.

  3. You may modify your copy or copies of the Program or any portion of
     it, thus forming a work based on the Program, and copy and
     distribute such modifications or work under the terms of Section 1
     above, provided that you also meet all of these conditions:

       a. You must cause the modified files to carry prominent notices
          stating that you changed the files and the date of any change.

       b. You must cause any work that you distribute or publish, that
          in whole or in part contains or is derived from the Program or
          any part thereof, to be licensed as a whole at no charge to
          all third parties under the terms of this License.

       c. If the modified program normally reads commands interactively
          when run, you must cause it, when started running for such
          interactive use in the most ordinary way, to print or display
          an announcement including an appropriate copyright notice and
          a notice that there is no warranty (or else, saying that you
          provide a warranty) and that users may redistribute the
          program under these conditions, and telling the user how to
          view a copy of this License.  (Exception: if the Program
          itself is interactive but does not normally print such an
          announcement, your work based on the Program is not required
          to print an announcement.)

     These requirements apply to the modified work as a whole.  If
     identifiable sections of that work are not derived from the
     Program, and can be reasonably considered independent and separate
     works in themselves, then this License, and its terms, do not apply
     to those sections when you distribute them as separate works.  But
     when you distribute the same sections as part of a whole which is a
     work based on the Program, the distribution of the whole must be on
     the terms of this License, whose permissions for other licensees
     extend to the entire whole, and thus to each and every part
     regardless of who wrote it.

     Thus, it is not the intent of this section to claim rights or
     contest your rights to work written entirely by you; rather, the
     intent is to exercise the right to control the distribution of
     derivative or collective works based on the Program.

     In addition, mere aggregation of another work not based on the
     Program with the Program (or with a work based on the Program) on a
     volume of a storage or distribution medium does not bring the other
     work under the scope of this License.

  4. You may copy and distribute the Program (or a work based on it,
     under Section 2) in object code or executable form under the terms
     of Sections 1 and 2 above provided that you also do one of the
     following:

       a. Accompany it with the complete corresponding machine-readable
          source code, which must be distributed under the terms of
          Sections 1 and 2 above on a medium customarily used for
          software interchange; or,

       b. Accompany it with a written offer, valid for at least three
          years, to give any third party, for a charge no more than your
          cost of physically performing source distribution, a complete
          machine-readable copy of the corresponding source code, to be
          distributed under the terms of Sections 1 and 2 above on a
          medium customarily used for software interchange; or,

       c. Accompany it with the information you received as to the offer
          to distribute corresponding source code.  (This alternative is
          allowed only for noncommercial distribution and only if you
          received the program in object code or executable form with
          such an offer, in accord with Subsection b above.)

     The source code for a work means the preferred form of the work for
     making modifications to it.  For an executable work, complete
     source code means all the source code for all modules it contains,
     plus any associated interface definition files, plus the scripts
     used to control compilation and installation of the executable.
     However, as a special exception, the source code distributed need
     not include anything that is normally distributed (in either source
     or binary form) with the major components (compiler, kernel, and so
     on) of the operating system on which the executable runs, unless
     that component itself accompanies the executable.

     If distribution of executable or object code is made by offering
     access to copy from a designated place, then offering equivalent
     access to copy the source code from the same place counts as
     distribution of the source code, even though third parties are not
     compelled to copy the source along with the object code.

  5. You may not copy, modify, sublicense, or distribute the Program
     except as expressly provided under this License.  Any attempt
     otherwise to copy, modify, sublicense or distribute the Program is
     void, and will automatically terminate your rights under this
     License.  However, parties who have received copies, or rights,
     from you under this License will not have their licenses terminated
     so long as such parties remain in full compliance.

  6. You are not required to accept this License, since you have not
     signed it.  However, nothing else grants you permission to modify
     or distribute the Program or its derivative works.  These actions
     are prohibited by law if you do not accept this License.
     Therefore, by modifying or distributing the Program (or any work
     based on the Program), you indicate your acceptance of this License
     to do so, and all its terms and conditions for copying,
     distributing or modifying the Program or works based on it.

  7. Each time you redistribute the Program (or any work based on the
     Program), the recipient automatically receives a license from the
     original licensor to copy, distribute or modify the Program subject
     to these terms and conditions.  You may not impose any further
     restrictions on the recipients' exercise of the rights granted
     herein.  You are not responsible for enforcing compliance by third
     parties to this License.

  8. If, as a consequence of a court judgment or allegation of patent
     infringement or for any other reason (not limited to patent
     issues), conditions are imposed on you (whether by court order,
     agreement or otherwise) that contradict the conditions of this
     License, they do not excuse you from the conditions of this
     License.  If you cannot distribute so as to satisfy simultaneously
     your obligations under this License and any other pertinent
     obligations, then as a consequence you may not distribute the
     Program at all.  For example, if a patent license would not permit
     royalty-free redistribution of the Program by all those who receive
     copies directly or indirectly through you, then the only way you
     could satisfy both it and this License would be to refrain entirely
     from distribution of the Program.

     If any portion of this section is held invalid or unenforceable
     under any particular circumstance, the balance of the section is
     intended to apply and the section as a whole is intended to apply
     in other circumstances.

     It is not the purpose of this section to induce you to infringe any
     patents or other property right claims or to contest validity of
     any such claims; this section has the sole purpose of protecting
     the integrity of the free software distribution system, which is
     implemented by public license practices.  Many people have made
     generous contributions to the wide range of software distributed
     through that system in reliance on consistent application of that
     system; it is up to the author/donor to decide if he or she is
     willing to distribute software through any other system and a
     licensee cannot impose that choice.

     This section is intended to make thoroughly clear what is believed
     to be a consequence of the rest of this License.

  9. If the distribution and/or use of the Program is restricted in
     certain countries either by patents or by copyrighted interfaces,
     the original copyright holder who places the Program under this
     License may add an explicit geographical distribution limitation
     excluding those countries, so that distribution is permitted only
     in or among countries not thus excluded.  In such case, this
     License incorporates the limitation as if written in the body of
     this License.

  10. The Free Software Foundation may publish revised and/or new
     versions of the General Public License from time to time.  Such new
     versions will be similar in spirit to the present version, but may
     differ in detail to address new problems or concerns.

     Each version is given a distinguishing version number.  If the
     Program specifies a version number of this License which applies to
     it and "any later version", you have the option of following the
     terms and conditions either of that version or of any later version
     published by the Free Software Foundation.  If the Program does not
     specify a version number of this License, you may choose any
     version ever published by the Free Software Foundation.

  11. If you wish to incorporate parts of the Program into other free
     programs whose distribution conditions are different, write to the
     author to ask for permission.  For software which is copyrighted by
     the Free Software Foundation, write to the Free Software
     Foundation; we sometimes make exceptions for this.  Our decision
     will be guided by the two goals of preserving the free status of
     all derivatives of our free software and of promoting the sharing
     and reuse of software generally.

                              NO WARRANTY

  12. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO
     WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE
     LAW. EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS
     AND/OR OTHER PARTIES PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY
     OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT
     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
     FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND
     PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE PROGRAM PROVE
     DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR
     OR CORRECTION.

  13. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN
     WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY
     MODIFY AND/OR REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE
     LIABLE TO YOU FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL,
     INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR
     INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED TO LOSS OF
     DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU
     OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY
     OTHER PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN
     ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.

                      END OF TERMS AND CONDITIONS

How to Apply These Terms to Your New Programs
=============================================

If you develop a new program, and you want it to be of the greatest
possible use to the public, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.

   To do so, attach the following notices to the program.  It is safest
to attach them to the start of each source file to most effectively
convey the exclusion of warranty; and each file should have at least the
"copyright" line and a pointer to where the full notice is found.

     ONE LINE TO GIVE THE PROGRAM'S NAME AND AN IDEA OF WHAT IT DOES.
     Copyright (C) 19YY  NAME OF AUTHOR

     This program is free software; you can redistribute it and/or
     modify it under the terms of the GNU General Public License
     as published by the Free Software Foundation; either version 2
     of the License, or (at your option) any later version.

     This program is distributed in the hope that it will be useful,
     but WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     GNU General Public License for more details.

     You should have received a copy of the GNU General Public License
     along with this program; if not, write to the Free Software
     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

   Also add information on how to contact you by electronic and paper
mail.

   If the program is interactive, make it output a short notice like
this when it starts in an interactive mode:

     Gnomovision version 69, Copyright (C) 19YY NAME OF AUTHOR
     Gnomovision comes with ABSOLUTELY NO WARRANTY; for details
     type `show w'.  This is free software, and you are welcome
     to redistribute it under certain conditions; type `show c'
     for details.

   The hypothetical commands 'show w' and 'show c' should show the
appropriate parts of the General Public License.  Of course, the
commands you use may be called something other than 'show w' and 'show
c'; they could even be mouse-clicks or menu items--whatever suits your
program.

   You should also get your employer (if you work as a programmer) or
your school, if any, to sign a "copyright disclaimer" for the program,
if necessary.  Here is a sample; alter the names:

     Yoyodyne, Inc., hereby disclaims all copyright
     interest in the program `Gnomovision'
     (which makes passes at compilers) written
     by James Hacker.

     SIGNATURE OF TY COON, 1 April 1989
     Ty Coon, President of Vice

   This General Public License does not permit incorporating your
program into proprietary programs.  If your program is a subroutine
library, you may consider it more useful to permit linking proprietary
applications with the library.  If this is what you want to do, use the
GNU Library General Public License instead of this License.

1 What is Elib?
***************

Elib, the GNU Emacs lisp library, is a collection of elisp functions
which you can use as parts of your own elisp programs.  Each file
contains functions which have something in common, e.g.  they handle a
certain data type.

   Elib is designed to be both as efficient and as easy to use as
possible.  Each file in Elib uses the elisp function 'provide' to tell
emacs when it has been loaded.  To use the functions in the file 'foo',
you just have to put a line such as:

     (require 'foo)

   into your own elisp file.  This will cause emacs to load the file
'foo.elc' and evaluate the functions in it.  This, of course, requires
that your system manager has installed Elib properly on your system.

1.1 Contributors to Elib
========================

The following persons have made contributions to GNU Elib.

   * Inge Wallin wrote most of the otherwise unattributed functions in
     Elib as well as all documentation.

   * Sebastian Kremer contributed the string functions.

   * Thomas Bellman wrote some of the code for AVL trees.

   * Per Cederqvist wrote the cookie package and the doubly linked list.
     The first design of 'cookie.el' was made by Inge Wallin.

1.2 Where can I get Elib?
=========================

There will probably be a number of sites archiving Elib.  Currently the
latest release can always be fetched via anonymos ftp from
'ftp.lysator.liu.se' in 'pub/emacs'.

2 Container Data Types
**********************

Container data types are data types which are used to hold and organize
other data.  Since lisp is a dynamically typed language, any container
data type can hold any other data type or a mix of other data types.
This is contrary to the case for 'C' or 'C++' where all data in a
typical container must be of the same type.

   As a convention do all names of the functions handling a certain
container data type begin in '<type>-', i.e.  the functions implementing
the container data type 'foo' all start with 'foo-'.

2.1 The Stack Data Type
=======================

The stack data type provides a simple LIFO stack.  There are two
implementations of a stack in Elib, one using macros and one using
functions.  The names of the functions/macros in the two implementations
are the same, but the efficiency of using one or the other vary greatly
under different circumstances.

   The implementation using macros should be used when you want to
byte-compile your own elisp program.  This will be most efficient since
byte-compiling an elisp function using macros has the same effect as
using inline code in 'C'.

   To use the stack data type, put the line

     (require 'stack-f)

   in your own elisp source file if you want to use the implementation
using functions or

     (require 'stack-m)

   if you want to use the implementation using macros.  This is the only
difference between them, so it is easy to switch between them during
debugging.

   The following functions are provided by the stack:

'(stack-create)'
     Create a new empty stack.

'(stack-p stack)'
     Return 't' if STACK is a stack, otherwise return 'nil'.

'(stack-push stack element)'
     Push ELEMENT onto STACK.

'(stack-pop stack)'
     Remove the topmost element from STACK and return it.  If STACK is
     empty, return 'nil'.

'(stack-empty stack)'
     Return 't' if STACK is empty, otherwise return 'nil'.

'(stack-top stack)'
     Return the top element of STACK, but don't remove it from the
     stack.  Return 'nil' if STACK is empty.

'(stack-nth stack n)'
     Return the Nth element of STACK where the top stack element has
     number 0.  If STACK is not that long, return 'nil'.  The element is
     not removed from the stack.

'(stack-all stack)'
     Return a list of all entries in STACK with the topmost element
     first.

'(stack-copy stack)'
     Return a copy of STACK.  All entries in STACK are also copied.

'(stack-length stack)'
     Return the number of elements in STACK.

'(stack-clear stack)'
     Remove all elements from STACK.

2.2 The Queue Data Type
=======================

The queue data type provides a simple FIFO queue.  There are two
implementations of a queue in Elib, one using macros and one using
functions.  The names of the functions/macros in the two implementations
are the same, but the efficiency of using one or the other vary greatly
under different circumstances.

   The implementation using macros should be used when you want to
byte-compile your own elisp program.  This will be most efficient since
byte-compiling an elisp function using macros has the same effect as
using inline code in 'C'.

   To use the queue data type, put the line

     (require 'queue-f)

   in your own elisp source file if you want to use the implementation
using functions or

     (require 'queue-m)

   if you want to use the implementation using macros.  This is the only
difference between them, so it is easy to switch between them during
debugging.

   Not all functions in 'queue-m.el' are implemented as macros, only the
short ones.  This does not make it less recommendable to use the macro
version in your compiled code.

   The following functions are provided by the queue:

'(queue-create)'
     Create a new empty queue.

'(queue-p queue)'
     Return 't' if QUEUE is a queue, otherwise return 'nil'.

'(queue-enqueue queue element)'
     Enter ELEMENT last into QUEUE.

'(queue-dequeue queue)'
     Remove the first element from QUEUE and return it.

'(queue-empty queue)'
     Return 't' if QUEUE is empty, otherwise return 'nil'.

'(queue-first queue)'
     Return the first element of QUEUE or 'nil' if it is empty.  The
     element is not removed from the queue.

'(queue-nth queue n)'
     Return the Nth element of QUEUE, where the first element of QUEUE
     has number 0.  If the length of QUEUE is less than N, return 'nil'.
     The element is not removed from the queue.

'(queue-last queue)'
     Return the last element of QUEUE or 'nil' if it is empty.  The
     element is not removed from the queue.

'(queue-all queue)'
     Return a list of all elements in QUEUE.  Return 'nil' if QUEUE is
     empty.  The oldest element in the queue is the first in the list.

'(queue-copy queue)'
     Return a copy of QUEUE.  All entries in QUEUE are also copied.

'(queue-length queue)'
     Return the number of elements in QUEUE.

'(queue-clear queue)'
     Remove all elements from QUEUE.

2.3 The Doubly Linked List Data Type
====================================

The doubly linked list is an efficient data structure if you need to
traverse the elements on the list in two directions, and maybe insert
new elements in the middle of the list.  You can efficiently delete any
element, and insert new elements, anywhere on the list.

   A doubly linked list ("dll" for short) consists of a number of
"nodes", each containing exactly one "element".  Some of the functions
operate directly on the elements, while some manipulate nodes.  For
instance, all of the functions that let you step forward and backwards
in the list handle nodes.  Use the function "dll-element" to extract the
element of a node.

   To use the doubly linked list provided by Elib you must put the line

     (require 'dll)

   in your elisp source file.

2.3.1 Creating a Doubly Linked List
-----------------------------------

'(dll-create)'
     Create an empty doubly linked list.

'(dll-create-from-list list)'
     Given the ordinary lisp list LIST, create a doubly linked list with
     the same elements.

'(dll-copy dll &optional element-copy-fnc)'
     Return a copy of the doubly linked list DLL.  If optional second
     argument ELEMENT-COPY-FNC is non-'nil' it should be a function that
     takes one argument, an element, and returns a copy of it.  If
     ELEMENT-COPY-FNC is not given the elements themselves are not
     copied.

2.3.2 Entering elements in a dll
--------------------------------

'(dll-enter-first dll element)'
     Add an element first on a doubly linked list.

'(dll-enter-last dll element)'
     Add an element last on a doubly linked list.

'(dll-enter-after dll node element)'
     In the doubly linked list DLL, insert a node containing ELEMENT
     after NODE.

'(dll-enter-before dll node element)'
     In the doubly linked list DLL, insert a node containing ELEMENT
     before NODE.

2.3.3 Accessing elements of a dll
---------------------------------

'(dll-element dll node)'
     Get the element of a NODE in a doubly linked list DLL.

'(dll-first dll)'
     Return the first element on the doubly linked list DLL.  Return
     'nil' if the list is empty.  The element is not removed.

'(dll-nth dll n)'
     Return the Nth node from the doubly linked list DLL.  N counts from
     zero.  If DLL is not that long, 'nil' is returned.  If N is
     negative, return the -(N+1)th last element.  Thus, '(dll-nth dll
     0)' returns the first node, and '(dll-nth dll -1)' returns the last
     node.

'(dll-last dll)'
     Return the last element on the doubly linked list DLL.  Return
     'nil' if the list is empty.  The element is not removed.

'(dll-next dll node)'
     Return the last element on the doubly linked list DLL.  Return
     'nil' if the list is empty.  The element is not removed.

'(dll-previous dll node)'
     Return the node before NODE, or 'nil' if NODE is the first node.

'(dll-all dll)'
     Return all elements on the double linked list DLL as an ordinary
     list.

2.3.4 Removing nodes from a dll
-------------------------------

'(dll-delete dll node)'
     Delete NODE from the doubly linked list DLL.  Return the element of
     NODE.

'(dll-delete-first dll)'
     Delete the first NODE from the doubly linked list DLL.  Return the
     element.  Returns 'nil' if DLL was empty.

'(dll-delete-last dll)'
     Delete the last NODE from the doubly linked list DLL.  Return the
     element.  Returns 'nil' if DLL was empty.

'(dll-clear dll)'
     Clear the doubly linked list DLL, i.e.  make it completely empty.

2.3.5 Predicates on a dll
-------------------------

'(dll-p object)'
     Return 't' if OBJECT is a doubly linked list, otherwise return
     'nil'.

'(dll-empty dll)'
     Return 't' if the doubly linked list DLL is empty, 'nil' otherwise.

2.3.6 Maps and Filters on a dll
-------------------------------

'(dll-map map-function dll)'
     Apply MAP-FUNCTION to all elements in the doubly linked list DLL.
     The function is applied to the first element first.

'(dll-map-reverse map-function dll)'
     Apply MAP-FUNCTION to all elements in the doubly linked list DLL.
     The function is applied to the last element first.

'(dll-filter dll predicate)'
     Remove all elements in the doubly linked list DLL for which
     PREDICATE returns 'nil'.

2.3.7 Miscellaneous dll operations
----------------------------------

'(dll-length dll)'
     Returns the number of elements in the doubly linked list DLL.

'(dll-sort dll predicate)'
     Sort the doubly linked list DLL, stably, comparing elements using
     PREDICATE.  Returns the sorted list.  DLL is modified by side
     effects.  PREDICATE is called with two elements of DLL, and should
     return 't' if the first element is "less" than the second.

2.3.8 Debugging dll applications
--------------------------------

The data structure used by the dll package contains both forward and
backward pointers.  The primitives in Emacs, such as 'print', know
nothing about dlls, so when Emacs tries to print out a dll it will think
that it found a circular structure.  Fortunately it detects this
situation and gives an error message, instead of getting stuck in an
eternal loop.

   The error message can be quite annoying when you are developing an
application that uses dlls.  Suppose your code has an error, and you
type '(setq debug-on-error t)' to try to figure out exactly what the
error is.  If any function in the backtrace has a dll as an argument,
Emacs will abort printing the entire backtrace and only respond with a
"Back at top level" message (or something similar, depending on exactly
what you are doing) in the echo area.

   There are two solutions to this problem: patch your emacs so that it
detects circular structures (there have been patches for this floating
around the net) or use 'dll-debug.el'.

   The file 'dll-debug.el' implements all of the functionality that are
present in 'dll.el', but it uses a normal, singly linked list instead.
This makes some operations, like 'dll-previous', dreadfully slow, but it
makes it possible to debug dll applications.  'dll-debug.el' also has
more built-in sanity tests than 'dll.el'.

   *NOTE:* To use the debug package, you must load the library
'dll-debug' before you load any of the libraries (such as cookie) or
your program that use dll.  You must also make sure that you don't load
any byte-compiled version of any file that was compiled with the normal
dll library.  Since it contains some macros very strange results will
occur otherwise...

   When the debug package is loaded, you simply run your code normally,
and any bugs should be easier to trace.

2.4 The Binary Tree Data Type
=============================

The binary tree is sometimes an efficient way to store data.  When a
binary tree is created a compare function is given to the create
function ('bintree-create').  This function is used throughout all data
entry and deletions into and out of the tree.

   To use the binary tree in Elib you must put the line

     (require 'bintree)

   in your elisp source file.

   The following functions are provided by the binary tree in the
library:

'(bintree-create compare-function)'
     Create a new empty binary tree.  The argument COMPARE-FUNCTION is a
     function which compares two instances of the data type which is to
     be entered into the tree.  The call '(compare-function data1
     data2)' should return non-'nil' if 'data1' is less than 'data2',
     and 'nil' otherwise.

'(bintree-p tree)'
     Return 't' if TREE is an bintree, otherwise return 'nil'.

'(bintree-compare-function tree)'
     Return 'compare-function' given to 'bintree-create' when TREE was
     created.

'(bintree-empty tree)'
     Return 't' if TREE is empty, otherwise return 'nil'.

'(bintree-enter tree data)'
     Enter DATA into TREE.  If there already is a data element which is
     considered equal to DATA by 'compare-function' given to
     'bintree-create', the new element will replace the old one in the
     tree.

'(bintree-delete tree data)'
     Delete the element which is considered equal to DATA by
     'compare-function' given to 'bintree-create'.  If there is no
     matching element within the tree, nothing is done to the tree.

'(bintree-member tree data)'
     Return the element in TREE which is considered equal to DATA by
     'compare-function' given to 'bintree-create'.  If there is no such
     element in the tree, return 'nil'.

'(bintree-map map-function tree)'
     Apply MAP-FUNCTION to all elements in TREE.  The function is
     applied in the order in which the tree is sorted.

'(bintree-first tree)'
     Return the first element of TREE, i.e.  the one who is considered
     first by 'compare-function' given to 'bintree-create'.  If the tree
     is empty, return 'nil'.

'(bintree-last tree)'
     Return the last element of TREE, i.e.  the one who is considered
     last by 'compare-function' given to 'bintree-create'.  If the tree
     is empty, return 'nil'.

'(bintree-copy tree)'
     Return a copy of TREE.

'(bintree-flatten tree)'
     Return a sorted list containing all elements of TREE.

'(bintree-size tree)'
     Return the number of elements in TREE.

'(bintree-clear tree)'
     Clear TREE, i.e.  make it totally empty.

2.5 The AVL Tree Data Type
==========================

The AVL tree data types provides a balanced binary tree.  The tree will
remain balanced throughout its entire life time, regardless of in which
order elements are entered into or deleted from the tree.

   Although an AVL tree is not perfectly balanced, it has almost the
same performance as if it was.  The definition of an AVL tree is that
the difference in depth of the two branches of a particular node is at
most 1.  This criterium is enough to make the performance of searching
in an AVL tree very close to a perfectly balanced tree, but will
simplify the entering and deleting of data significantly.

   All data that is entered into an AVL tree should be of the same type.
If they are not, there are no way to compare two elements and this is
essential for entering and deleting data from the tree.  When a tree is
created, a compare function is given to the create function.  This
function is used throughout the life of the tree in all subsequent
insertions and deletions.

   To use the Elib AVL tree, you must put the line

     (require 'avltree)

   in your elisp source file.

   The following functions are provided by the AVL tree in the library:

'(avltree-create compare-function)'
     Create a new empty AVL tree.  The argument COMPARE-FUNCTION is a
     function which compares two instances of the data type which is to
     be entered into the tree.  The call '(compare-function data1
     data2)' should return non-'nil' if 'data1' is less than 'data2',
     and 'nil' otherwise.

'(avltree-p tree)'
     Return 't' if TREE is an avltree, otherwise return 'nil'.

'(avltree-compare-function tree)'
     Return 'compare-function' given to 'avltree-create' when TREE was
     created.

'(avltree-empty tree)'
     Return 't' if TREE is empty, otherwise return 'nil'.

'(avltree-enter tree data)'
     Enter DATA into TREE.  If there already is a data element which is
     considered equal to DATA by 'compare-function' given to
     'avltree-create', the new element will replace the old one in the
     tree.

'(avltree-delete tree data)'
     Delete the element which is considered equal to DATA by
     'compare-function' given to 'avltree-create'.  If there is no
     matching element within the tree, nothing is done to the tree.

'(avltree-member tree data)'
     Return the element in TREE which is considered equal to DATA by
     'compare-function' given to 'avltree-create'.  If there is no such
     element in the tree, return 'nil'.

'(avltree-map map-function tree)'
     Apply MAP-FUNCTION to all elements in TREE.  The function is
     applied in the order in which the tree is sorted.

'(avltree-first tree)'
     Return the first element of TREE, i.e.  the one who is considered
     first by 'compare-function' given to 'avltree-create'.  If the tree
     is empty, return 'nil'.

'(avltree-last tree)'
     Return the last element of TREE, i.e.  the one who is considered
     last by 'compare-function' given to 'avltree-create'.  If the tree
     is empty, return 'nil'.

'(avltree-copy tree)'
     Return a copy of TREE.

'(avltree-flatten tree)'
     Return a sorted list containing all elements of TREE.

'(avltree-size tree)'
     Return the number of elements in TREE.

'(avltree-clear tree)'
     Clear TREE, i.e.  make it totally empty.

3 The Cookie package--nodal data in a buffer
********************************************

If you want to have structured nodal data in a buffer, the cookie
package can be a help to you.

   Cookie is a package that implements a connection between a dll (a
doubly linked list) and the contents of a buffer.  Possible uses are
'dired' (have all files in a list, and show them), 'buffer-list',
'kom-prioritize' (in the LysKOM elisp client) and others.  The CVS
control package 'pcl-cvs.el' uses 'cookie.el'.

3.1 Introduction to cookie terminology
======================================

The cookie package uses its own terminology.  Here are some important
definitions.

"cookie"
     A "cookie" can be any lisp object.  When you use the cookie package
     you specify a pretty-printer, a function that inserts a printable
     representation of the cookie in the buffer.

"collection"

     A "collection" consists of a doubly linked list of cookies, a
     header, a footer and a pretty-printer.  It is displayed at a
     certain point in a certain buffer.  (The buffer and point are
     selected when the collection is created).  The header and the
     footer are constant strings.  They appear before and after the
     cookies.  (Currently, once set, they can not be changed).

"tin"
     A "tin" is an object that contains one cookie.  There are functions
     in this package that given a tin extracts the cookie, or gives the
     next or previous tin.  (All tins are linked together in a doubly
     linked list.  The previous tin is the one that appears before the
     other in the buffer.)  You should not do anything with a tin except
     pass it to the functions in this package.

   Cookie does not affect the mode of the buffer in any way.  It merely
makes it easy to connect an underlying data representation to the buffer
contents.

   A collection is a very dynamic thing.  You can easily add or delete
cookies.  You can sort all cookies in a collection (you have to supply a
function that compares two cookies).  You can apply a function to all
cookies in a collection, etc, etc.

   Remember that a cookie can be anything.  Your imagination is the
limit!  It is even possible to have another collection as a cookie.  In
that way some kind of tree hierarchy can be created.

3.2 Coding conventions used in the cookie package
=================================================

All functions that are intended for external use begin with one of the
prefixes 'cookie-', 'collection-' or 'tin-'.  The prefix 'elib-' is used
for internal functions and macros.  Currently, no global or buffer-local
variables are used.

   Many functions operate on tins instead of cookies.  For most
functions, the prefix used should help tell which kind of object the
function uses.

   Most doc-strings contains an "Args:" line that lists the arguments.

3.3 Manipulating the entire collection
======================================

'(collection-create buffer pretty-printer &optional header footer pos)'
     Create a collection that is displayed in BUFFER.  BUFFER may be a
     buffer or a buffer name.  It is created if it does not exist.

     PRETTY-PRINTER should be a function that takes one argument, a
     cookie, and inserts a string representing it in the buffer (at
     point).  The string PRETTY-PRINTER inserts may be empty or span
     several lines.  A trailing newline will always be inserted
     automatically.  The PRETTY-PRINTER should use 'insert', and not
     'insert-before-markers'.

     Optional third argument HEADER is a string that will always be
     present at the top of the collection.  HEADER should end with a
     newline.  Optional fourth argument FOOTER is similar, and will
     always be inserted at the bottom of the collection.

     Optional fifth argument POS is a buffer position, specifying where
     the collection will be inserted.  It defaults to the beginning of
     the buffer.  POS will probably default to the current value of
     '(point)' in future releases of Elib, so you should not depend on
     this default in cases where it matters.

'(collection-empty collection)'
     Return true if there are no cookies in COLLECTION.

'(collection-length collection)'
     Return the number of cookies in COLLECTION.

'(collection-list-cookies collection)'
     Return a list of all cookies in COLLECTION.

3.4 Inserting cookies in the collection
=======================================

These functions can be used to insert one or more cookies into a
collection.  The printed representation will immediately and
automatically be updated by the cookie package.  (It will call the
pretty-printer that was specified to 'collection-create').

'(cookie-enter-first collection cookie)'
     Enter COOKIE first in the cookie collection COLLECTION.

'(cookie-enter-last collection cookie)'
     Enter COOKIE last in the cookie collection COLLECTION.

'(cookie-enter-after-tin collection tin cookie)'
     Enter COOKIE into COLLECTION, immediately after TIN.

'(cookie-enter-before-tin collection tin cookie)'
     Enter COOKIE into COLLECTION, immediately before TIN.

'(collection-append-cookies (collection cookie-list))'
     Insert all cookies in the list COOKIE-LIST last in COLLECTION.

3.5 Tins and cookies
====================

'(tin-cookie collection tin)'
     This function can be used to extract a cookie from TIN.  The
     collection that TIN is present in must also be specified as
     COLLECTION.

3.6 Deleting cookies
====================

There are a couple of different ways to delete cookies from the
collection.

'(tin-delete collection tin)'
     Delete TIN from COLLECTION.  The cookie that is stored in TIN is
     returned.

'(cookie-delete-first collection)'
     Delete first cookie in COLLECTION and return it.  Returns 'nil' if
     there are no cookies left in COLLECTION.

'(cookie-delete-last collection)'
     Delete last cookie in COLLECTION and return it.  Returns 'nil' if
     there are no cookies left in COLLECTION.

   The following two functions can be used to delete several cookies
that fulfills certain criteria.

'(collection-filter-cookies collection predicate &rest extra-args)'
     Remove all cookies in COLLECTION for which PREDICATE returns nil.
     Note that the buffer for COLLECTION will be current-buffer when
     PREDICATE is called.  PREDICATE must restore the current buffer
     before it returns if it changes it.

     The PREDICATE is called with COOKIE as its first argument.  If any
     EXTRA-ARGS are given to 'collection-filter-cookies' they will be
     passed unmodified to PREDICATE.

'(collection-filter-tins collection predicate &rest extra-args)'
     This is like 'collection-filter-cookies', but PREDICATE is called
     with a tin instead of a cookie.

   And finally, a way to delete all cookies in one swift function call:

'(collection-clear collection)'
     Remove all cookies in COLLECTION.

3.7 Collection as a Doubly linked list
======================================

The functions in this section treat the collection as a doubly linked
list.

'(tin-nth collection n)'
     Return the Nth tin.  N counts from zero.  'nil' is returned if
     there is less than N cookies.  If N is negative, return the
     -(N+1)th last element.  Thus, '(tin-nth dll 0)' returns the first
     node, and '(tin-nth dll -1)' returns the last node.

     Use 'tin-cookie' to extract the cookie from the tin (or use
     'cookie-nth' instead).

'(cookie-nth collection n)'
     Like 'tin-nth', but the cookie is returned instead of the tin.

'(tin-next collection tin)'
     Get the next tin.  Returns nil if TIN is 'nil' or refers to the
     last cookie in COLLECTION.

'(tin-previous collection tin)'
     Get the previous tin.  Returns nil if TIN is 'nil' or refers to the
     first cookie in COLLECTION.

'(cookie-sort collection predicate)'
     Sort the cookies in COLLECTION, stably, comparing elements using
     PREDICATE.  PREDICATE is called with two cookies, and should return
     't' if the first cookie is "less" than the second.

     The screen representaion of the collection will refreshed after the
     sort is complete.

'(cookie-first collection)'
     Return the first cookie in COLLECTION.  The cookie is not removed.

'(cookie-last collection)'
     Return the last cookie in COLLECTION.  The cookie is not removed.

3.8 Scanning the list
=====================

'(cookie-map map-function collection &rest map-args)'
     Apply MAP-FUNCTION to all cookies in COLLECTION.  MAP-FUNCTION is
     applied to the first element first.  If MAP-FUNCTION returns
     non-'nil' the cookie will be refreshed (its pretty-printer will be
     called once again).

     Note that the buffer for COLLECTION will be current buffer when
     MAP-FUNCTION is called.  MAP-FUNCTION must restore the current
     buffer to BUFFER before it returns, if it changes it.

     If more than two arguments are given to 'cookie-map', remaining
     arguments will be passed to MAP-FUNCTION.

'(cookie-map-reverse map-function collection &rest map-args)'
     Like 'cookie-map', but MAP-FUNCTION will be applied to the last
     cookie first.

'(collection-collect-tin collection predicate &rest predicate-args)'
     Select cookies from COLLECTION using PREDICATE.  Return a list of
     all selected tins.

     PREDICATE is a function that takes a cookie as its first argument.

     The tins on the returned list will appear in the same order as in
     the buffer.  You should not rely on in which order PREDICATE is
     called.

     Note that the buffer the COLLECTION is displayed in is
     current-buffer when PREDICATE is called.  PREDICATE must restore
     current-buffer if it changes it.

     If more than two arguments are given to 'collection-collect-tin'
     the remaining arguments will be passed to PREDICATE.

'(collection-collect-cookie collection predicate &rest predicate-args)'
     Like 'collection-collect-tin', but a list of cookies is returned.

3.9 Operations that affect the buffer
=====================================

'(collection-buffer collection)'
     Return the buffer that COLLECTION is displayed in.

'(collection-refresh collection)'
     Refresh all cookies in COLLECTION.

     The pretty-printer that was specified when the COLLECTION was
     created will be called for all cookies in COLLECTION.

     Note that 'tin-invalidate' is more efficient if only a small number
     of cookies needs to be refreshed.

'(tin-invalidate collection &rest tins)'
     Refresh some cookies.  The pretty-printer for COLLECTION will be
     called for all TINS.

'(collection-set-goal-column collection goal)'
     Set goal-column for COLLECTION.  goal-column is made buffer-local.
     This function will be obsoleted in the next release of Elib.
     Instead, there is going to be a function that given a cookie will
     return a position where the cursor should be stored.  The details
     are not yet decided.

'(tin-goto-previous collection pos arg)'
     Move point to the ARGth previous cookie.  Don't move if we are at
     the first cookie, or if COLLECTION is empty.  Returns the tin we
     move to.

'(tin-goto-next collection pos arg)'
     Like 'tin-goto-previous', but move towards the end of the buffer
     instead.

'(tin-goto collection tin)'
     Move point to TIN.

'(tin-locate collection pos &optional guess)'
     Return the tin that POS (a buffer position) is within.

     POS may be a marker or an integer.  GUESS should be a tin that it
     is likely that POS is near.

     If POS points before the first cookie, the first cookie is
     returned.  If POS points after the last cookie, the last cookie is
     returned.  If COLLECTION is empty, 'nil' is returned.

3.10 Debugging cookie applications
==================================

Since the cookie package uses dll, cookie applications can be hard to
debug.  Fortunately, the same technique can be used here--just load
dll-debug prior to loading cookie.  See Debugging dll applications.

   _Warning!_  Don't load a byte-compiled 'cookie.elc' that was compiled
using dll (as opposed to dll-debug) when you have dll-debug in memory.
Your Emacs will be seriously confused.

4 String functions
******************

To use the string functions in Elib you have to put the following line
into your elisp source file:

     (require 'string)

   The following string functions are provided with Elib.

'(string-replace-match regexp string newtext &optional literal global)'

     This function tries to be a string near-equivalent to the elisp
     function 'replace-match'.  It returns a string with the first text
     matched by REGEXP in STRING replaced by NEWTEXT.  If no match is
     found, 'nil' is returned.  If optional argument GLOBAL is
     non-'nil', all occurances matching REGEXP are replaced instead of
     only the first one.

     If optional argument LITERAL is non-'nil', then NEWTEXT is inserted
     exactly as it is.  If it is 'nil' (which is the default), then the
     character '\' is treated specially.  If a '\' appears in NEWTEXT,
     it can start any one of the following sequences:

     '\&'
          '\&' stands for the entire text being replaced.

     '\N'
          '\N' stands for the Nth subexpression in the original regexp.
          Subexpressions are those expressions grouped inside of
          '\(...\)'.  N is a digit.

     '\\'
          '\\' stands for a single '\' in NEWTEXT.

     Any other character after the <\> will just be copied into the
     string.

'(string-split pattern string &optional limit)'

     Split the string STRING on the regexp PATTERN and return a list of
     the strings between the matches.  If the optional numerical
     argument LIMIT is >= 1, only the first LIMIT elements of the list
     are returned.

     For example, the call

          (string-split "[ \t]+" "Elisp programming is fun.")

     will return '("Elisp" "programming" "is" "fun.")', but the call

          (string-split " " "Elisp programming is fun." 3)

     will return '("Elisp" "programming" "is")'.

5 Read functions
****************

Elib provides a number of functions for reading data from the
minibuffer.  To use them in your own elisp programs, put the following
line into you source file:

     (require 'read)

   The following functions are provided by 'read'.

'(read-number &optional prompt default)'
     Read a number from the minibuffer.  If optional argument PROMPT is
     non-'nil', the user is prompted using PROMPT, otherwise the prompt
     string 'Enter a number:' is used.  If optional argument DEFAULT is
     non-'nil', it is written within parenthesis after the prompt
     string.  DEFAULT can be either a number or of the type which
     '(interactive "P")' generates.

'(read-num-range low high &optional prompt show-range)'
     Read a number from the minibuffer.  The number returned will be
     forced to lie between LOW and HIGH.  If PROMPT is non-'nil', the
     user is prompted using PROMPT, otherwise the prompt string 'Enter a
     number:' is used.  If SHOW-RANGE is non-'nil', the prompt will show
     the range within parenthesis to the user.

'(read-silent prompt &optional showchar)'
     Read a string in the minibuffer without echoing.  The following
     characters are special when entering the string:

     'DEL'
          Delete the last character in the input buffer.

     'C-u'
          Clear the input buffer.

     'RET'
          End the reading of the string.

     'Newline'
          Same as 'RET'.

     If optional argument SHOWCHAR is non-'nil', one of these characters
     will be displayed for each character input by the user.

     This function is well suited to read a password from the user, but
     beware of the function '(view-lossage)' which displays the last 100
     keystrokes, even hidden ones.

6 Future enhancements
*********************

Elib needs a number of enhancements to be called complete.  Here is a
list of wishes of functions and data types which we would like to enter
into Elib in future releases:

   * More container data types such as Priority queues, 2-3-trees, Hash
     tables, Sets, etc.  Much inspiration can be gotten from libg++ and
     the standard C++ library, STL.

   * Other implementations of old container data types.  For instance,
     are vector implementations of stacks and queues faster than the
     current ones using cons cells?

   * Miscellaneous other small functions.

   * More tests for all code in the library, especially the untested
     container data types.  See the TODO file.

6.1 Contributions
=================

We are grateful for all donations of code that we can receive.  However,
your code will be still more useful if you also provide documentation
and code to test your new library functions.

7 Reporting bugs
****************

Undoubtedly there are numerous bugs remaining, both in the elisp source
code and in the documentation.  If you find a bug in either, please send
a bug report to 'elib-maintainers@lysator.liu.se'.  We will try to be as
quick as possible in fixing the bugs and redistributing the fixes.