Anonymous avatar Anonymous committed 200667b

Inital revision

Comments (0)

Files changed (29)

+_pkg.el
+auto-autoloads.el
+elib.aux
+elib.cp
+elib.dvi
+elib.fn
+elib.info
+elib.info-1
+elib.info-2
+elib.ky
+elib.log
+elib.pg
+elib.toc
+elib.tp
+elib.vr
+Mon Dec 11 00:21:02 1995  Per Cederqvist  (ceder@lysator.liu.se)
+
+	* Released version 1.0.
+
+	* gpl.texi: New file.
+	* Makefile (OTHERS): Added gpl.texi.
+	* elib.texi: Include gpl.texi; removed gpl version 1.
+	* Makefile (install-info): Install all info files, not only the
+	directory.
+
+	* elib.texi: Lots of index entries added.
+
+	* All .el-files: Added conventional headers for emacs libraries.
+
+Sun Dec 10 21:46:38 1995  Per Cederqvist  (ceder@lysator.liu.se)
+
+	* elib-test-all.el (elib-test-all): Set load-path to ".", not to
+	"./library", when doing the tests.
+	(test-stack-f): Likewise.
+	(test-stack-m): Likewise.
+	(test-queue-f): Likewise.
+	(test-queue-m): Likewise.
+	(test-string): Likewise.
+	(test-dll): Likewise.
+	(test-dll-debug): Likewise.
+	(test-cookie): Likewise.
+
+Mon Dec 11 00:14:54 1995  Inge Wallin  <inge@lysator.liu.se>
+
+	* RELEASING: Fix a spelling error.
+
+	* elib-test.el: Require backquote explicitely since we set the
+	load-path to (".") in all the tests.
+
+	* INSTALL: Change all mentioning of elib.texinfo to elib.texi.
+
+	* All .el-files, Makefile: Changed header to contain correct
+	address of the FSF and the correct copyright notice.
+
+Sun Dec 10 23:26:21 1995  Inge Wallin  <inge@lysator.liu.se>
+
+	* elib-test.el: Now contains all tests for the library.
+	* elib-test-all.el: Removed.
+	* Makefile(OTHERS): elib-test-all.el is removed.
+
+Sun Dec 10 21:46:38 1995  Per Cederqvist  (ceder@lysator.liu.se)
+
+	* Makefile: Rewritten according to GNU Coding standards.
+	(OTHERS): Don't forget to distribute .cvsignore, RELEASING, TODO,
+	elib-test.el and elib-test-all.el.
+
+	* dist-makefile: Removed.  We now distribute our internal
+	Makefile, so that the entire world can make new releases of this
+	package.
+
+	* elib.texi: New name for former elib.texinfo.
+
+	* avltree.el, bintree.el, cookie.el, dll-debug.el, dll.el,
+ 	elib-node.el, queue-f.el, queue-m.el, read.el, stack-f.el,
+ 	stack-m.el, string.el: Moved from the library subdirectory to the
+ 	top directory.
+
+Sun Dec 10 16:30:26 1995  Inge Wallin  <inge@lysator.liu.se>
+
+	* elib.texinfo: Removed the installation chapter.
+
+	* elib.texinfo: Some minor spelling corrections.
+
+	* INSTALL: Better description of how to do it.
+	* dist-makefile: Change standard installation path.
+
+Sun Dec 10 16:10:02 1995  Per Cederqvist  (ceder@lysator.liu.se)
+
+	* Makefile (dist): Was formerly known as distribution.
+
+	* RELEASING: Translated to English.
+
+	* library/cookie.el: Renamed the prefix "icookie-" to "elib-".
+	Since these are private entities, nobody should be affected by the
+	change.
+	* elib.texinfo (Cookie conventions): Changed the documentation
+	accordingly.
+
+Sun Dec 10 16:02:58 1995  Inge Wallin  <inge@lysator.liu.se>
+
+	* README: Modernized it.
+
+	* COPYING: Use GPL version 1 to version 2.
+
+Sun Feb 19 00:42:03 1995  Inge Wallin  <inge@lysator.liu.se>
+
+	* Id 20: Error in 'make clean': now remove all .elc files.
+	dist-makefile: Call library/Makefile
+	library/Makefile: New file.
+
+Tue Jun  1 01:47:02 1993  Per Cederqvist  (ceder@lysator.liu.se)
+
+	* Released version 0.07.
+
+	* startup-template.el: Insert the Elib directory first on
+	load-path, so that our cookie.el is used even if Emacs 19 is
+	used.
+
+Sun May  2 13:52:45 1993  Per Cederqvist  (ceder@lysator.liu.se)
+
+	* cookie.el (tin-goto): Set collection->last-tin.
+	* cookie.el (icookie-delete-tin-internal): Clear
+	collection->last-tin if we are deleting it.
+	* cookie.el (tin-delete): Rely on icookie-delete-tin-internal to
+	clear collection->last-tin, and don't do it here.
+
+	* elib-test-all.el: Wrote some tests for the cookie package. A lot
+	of more tests need to be written.
+
+Tue Apr 27 00:45:22 1993  Per Cederqvist  (ceder@lysator.liu.se)
+
+	* cookie.el (collection-length, collection-refresh): Fixed fatal typos.
+
+Sun Jan 24 20:21:29 1993  Inge Wallin  (inge@ruben)
+
+	* Released version 0.06.
+
+	* elib.texinfo: Fixed a number of spelling and grammatical errors
+	  in the documentation of dlls.
+
+Sun Jan 24 15:13:24 1993  Per Cederqvist  (ceder@robin)
+
+	* elib.texinfo: Talk about debugging cookie applications.
+
+	* dll-debug.el: New file, moved here from the pcl-cvs project.
+	  Some comments updated.
+	* elib.texinfo: Documented dll-debug.  Revisited the documentation
+	  on dll.
+	* Makefile, dist-makefile, elib-compile-all.el: Updated to know
+	  about dll-debug.el.
+	* elib-test-all.el: Added test cases for dll and dll-debug.
+
+	* elib-test-all.el (elib-test-library): Load the library, don't
+	  only require it.
+	* elib-test-all.el (test-a-case): Print the test when something
+	  goes wrong.
+
+	* dll-debug.el (dll-previous, dll-last): Don't return the dummy node.
+	* dll-debug.el (dll-delete, dll-delete-fisrt, dll-delete-last):
+	  Fixed return value.
+
+Mon Jan 18 00:12:35 1993  Per Cederqvist  (ceder@mauritz)
+
+	* Release 0.05.1 (not released to the world).
+
+	* cookie.el: Require dll, not elib-dll.
+
+	* cookie.el (tin-goto-previous): Handle empty collections.
+
+	* cookie.el (icookie-abs): Fixed typo.
+
+	* string.el (string-split): Fixed typo.
+	* string.el (string-replace-match): Fix the doc string. Groups are
+	  contained inside \( \), not ( ).
+	* elib-test-all.el (string): Wrote some test cases.
+
+Sat Jan 16 16:26:53 1993  Inge Wallin  (inge@robin)
+
+	* Released version 0.05.
+
+	* elib.texinfo: Changed file name of info file to elib.info.
+
+Sat Jan 16 15:59:45 1993  Per Cederqvist  (ceder@konrad)
+
+	* cookie.el (tin-goto): New function.
+	* elib.texinfo: Document it.
+
+	* elib.texinfo: changed all references to parameters of functions
+	  to use @var{}.
+
+	* dist-makefile (ELFILES, ELCFILES): Added dll and cookie.
+
+Thu Jan 14 17:10:03 1993  Per Cederqvist  (ceder@konrad)
+
+	* elib.texinfo: Documented dll.el.
+
+	* Makefile (ELFILES): Added dll.el.
+
+Sun Jan  3 23:22:18 1993  Per Cederqvist  (ceder@konrad)
+
+	* dll.el: New file. This has been used extensively in pcl-cvs, so
+	  it might be relatively bugfree.
+	* dll.el: Provide dll, not elib-dll.
+
+Wed Dec 30 02:42:19 1992  Per Cederqvist  (ceder@konrad)
+
+	* elib.texinfo (Cookie package): Documented the cookie package.
+	  Phew.  All information from the doc-strings are included.  More
+	  examples and explanations are needed.
+
+Tue Dec 29 21:43:28 1992  Per Cederqvist  (ceder@konrad)
+
+	* cookie.el, elib.texinfo: Renamed all functions, since RMS
+	  doesn't like the prefix convention "cookie:function".  This is
+	  the list of function names before and after:
+
+cookie::abs                             -> icookie-abs
+cookie::collection->buffer              -> icookie-collection->buffer
+cookie::collection->dll                 -> icookie-collection->dll
+cookie::collection->footer              -> icookie-collection->footer
+cookie::collection->header              -> icookie-collection->header
+cookie::collection->last-tin            -> icookie-collection->last-tin
+cookie::collection->pretty-printer      -> icookie-collection->pretty-printer
+cookie::create-collection               -> icookie-create-collection
+cookie::create-wrapper                  -> icookie-create-wrapper
+cookie::create-wrapper-and-insert       -> icookie-create-wrapper-and-insert
+cookie::create-wrapper-and-pretty-print
+			-> icookie-create-wrapper-and-pretty-print
+cookie::delete-tin-internal             -> icookie-delete-tin-internal
+cookie::filter-hf                       -> icookie-filter-hf
+cookie::pos-before-middle-p             -> icookie-pos-before-middle-p
+cookie::refresh-tin                     -> icookie-refresh-tin
+cookie::set-buffer-bind-dll             -> icookie-set-buffer-bind-dll
+cookie::set-buffer-bind-dll-let*        -> icookie-set-buffer-bind-dll-let*
+cookie::set-collection->buffer          -> icookie-set-collection->buffer
+cookie::set-collection->dll             -> icookie-set-collection->dll
+cookie::set-collection->footer          -> icookie-set-collection->footer
+cookie::set-collection->header          -> icookie-set-collection->header
+cookie::set-collection->last-tin        -> icookie-set-collection->last-tin
+cookie::set-collection->pretty-printer
+			-> icookie-set-collection->pretty-printer
+cookie::wrapper->cookie                 -> icookie-wrapper->cookie
+cookie::wrapper->cookie-safe            -> icookie-wrapper->cookie-safe
+cookie::wrapper->start-marker           -> icookie-wrapper->start-marker
+cookie:all                              -> collection-list-cookies
+cookie:buffer                           -> collection-buffer
+cookie:clear                            -> collection-clear
+cookie:collect-cookies                  -> collection-collect-cookie
+cookie:collect-tins                     -> collection-collect-tin
+cookie:create                           -> collection-create
+cookie:delete-first                     -> cookie-delete-first
+cookie:delete-last                      -> cookie-delete-last
+cookie:delete-tin                       -> tin-delete
+cookie:empty                            -> collection-empty
+cookie:enter-after                      -> cookie-enter-after-tin
+cookie:enter-before                     -> cookie-enter-before-tin
+cookie:enter-cookies                    -> collection-append-cookies
+cookie:enter-first                      -> cookie-enter-first
+cookie:enter-last                       -> cookie-enter-last
+cookie:filter                           -> collection-filter-cookies
+cookie:first                            -> cookie-first
+cookie:goto-next-tin                    -> tin-goto-next
+cookie:goto-previous-tin                -> tin-goto-previous
+cookie:invalidate-tins                  -> tin-invalidate
+cookie:last                             -> cookie-last
+cookie:length                           -> collection-length
+cookie:map                              -> cookie-map
+cookie:map-reverse                      -> cookie-map-reverse
+cookie:next-tin                         -> tin-next
+cookie:nth-cookie                       -> cookie-nth
+cookie:nth-tin                          -> tin-nth
+cookie:previous-tin                     -> tin-previous
+cookie:refresh-all                      -> collection-refresh
+cookie:set-goal-column                  -> collection-set-goal-column
+cookie:sort                             -> cookie-sort
+cookie:tin->cookie                      -> tin-cookie
+cookie:tin-filter                       -> collection-filter-tins
+cookie:tin-get-selection                -> tin-locate
+
+	* Makefile (ELFILES): Added cookie.el.
+
+	* Makefile (tags): New target.
+
+Sat Aug 22 00:54:26 1992  Inge Wallin  (inge@ruben)
+
+	* string.el(string-replace-match): Fixed the doc string.
+
+	* BUGS and BUGMAILS: New files for tracking bugs with the emacs
+	  bugtrack package.
+
+Sat Aug 22 00:11:37 1992  Per Cederqvist  (ceder@maskros)
+
+	* string.el (string-replace-match, string-split): Save and restore
+	match-data.
+
+Fri Aug 21 12:50:55 1992  Per Cederqvist  (ceder@maskros)
+
+	* cookie.el: Beautified a lot of comments.
+
+	* cookie.el (cookie::abs): New function. This should exist
+	elsewhere in elib!
+
+	* cookie.el (cookie:filter, cookie:tin-filter): Allow some extra
+	args for predicate.
+
+	* cookie.el (cookie:tin-get-selection): Omit the FORCE-GUESS arg.
+	Rewrote the code that finds the best guess so that it always uses
+	collection->last-tin as a guess.
+
+	* cookie.el (tin-start-marker, tin-end-marker): Commented out.
+
+	* cookie.el (Local Variables): Added. Sets the lisp-indent-hook
+	for some functions.
+
+Thu Aug 20 05:53:59 1992  Per Cederqvist  (ceder@robin)
+
+	* cookie.el: The pretty-printer should now insert the string in
+	the buffer, not return the string.
+	* cookie.el (cookie::create-wrapper-and-pretty-print): New
+	function.
+	* cookie.el (cookie::refresh-tin, cookie::pos-before-middle-p,
+	cookie:enter-first, cookie:enter-last, cookie:enter-after,
+	cookie:enter-before, cookie:next-tin, cookie:refresh-all):
+	Updated.
+
+Wed Aug 19 03:50:11 1992  Per Cederqvist  (ceder@robert)
+
+	* Merged in some changes made by Inge Wallin:
+	* elib-compile-all.el (compile-elib): Bind load-path locally.
+
+Mon Jul 27 21:08:27 1992  Inge Wallin  (inge@lysator)
+
+	* Changed all copyright notices to read:
+	  Copyright 1991, 1992 Free Software Foundation
+
+Sun Mar 15 00:01:12 1992  Per Cederqvist  (ceder@robin)
+
+	* Added RCS Id keywords to most of the files.
+
+Thu Jul 25 18:32:21 1991  Inge Wallin  (inge at lysator)
+
+	* elib-avltree.el -> avltree.el
+
+	* elib.texinfo: Changed all function names (dropped elib- prefix).
+
+Wed Jul 24 01:10:09 1991  Inge Wallin  (inge at lysator)
+
+	* elib-bintree.el -> bintree.el
+	  elib-read.el	  -> read.el
+          elib-string.el  -> string.el
+	  elib-stack-f.el -> stack-f.el
+	  elib-stack-m.el -> stack-m.el
+          Also the functions intended for the user to call lost their
+	  elib- prefix. 
+
+	* Function silent-read -> read-silent for consistency.
+
+Sun Jun 16 02:30:08 1991  Inge Wallin  (inge at robert)
+
+	* Released version 0.03.
+
+	* elib.texinfo: Fixed the node index.
+
+	* New file: elib-compile-all. This file byte-compiles those files
+	  in elib which needs recompiling.
+
+	* New file: elib-avltree.el. Added AVL trees and documentation to
+	  the library.
+
+Tue Jun  4 21:13:33 1991  Inge Wallin  (inge at laila)
+
+	* Finished and tested all functions in elib-bintree.el.
+
+Thu May 30 23:57:12 1991  Inge Wallin  (inge at laila)
+
+	* Fixed a few errors in the documentation.
+
+Tue May 28 01:43:02 1991  Inge Wallin  (inge at lave)
+
+	* Documented the functions in elib-bintree in elib.texinfo. 
+
+Tue May 21 21:43:03 1991  Inge Wallin  (inge at lave)
+
+	* New file: elib-bintree.el containing functions for ordinary
+	  (not balanced) binary trees.
+
+	* Corrected a bug in elib-node.el
+
+Mon May 20 23:03:36 1991  Inge Wallin  (inge at laila)
+
+	* New file: elib-node.el. Contains a number of macros for creating
+	  and handling nodes for binary trees and doubly linked lists.
+
+Wed May 15 22:17:53 1991  Inge Wallin  (inge at lave)
+
+	* Made elib-stack-f.el delete elib-stack-m.el from the features
+	  variable and vice versa. Same for queue.
+
+	* Changed a few things in elib.texinfo.
+
+Sun May 12 19:31:54 1991  Inge Wallin  (inge at laila)
+
+	* Added a macro implementation of elib-queue. New file:
+	  elib-queue-m.el. The old file elib-queue.el changed name to
+	  elib-queue-f.el. Also changed Makefile.  Documented.
+
+	* Added a macro implementation of elib-stack. New file:
+	  elib-stack-m.el. The old file elib-stack.el changed name to
+	  elib-stack-f.el. Also changed dist-makefile.  Documented.
+
+	* Added the functions elib-stack-copy and elib-queue-copy to
+	  elib-stack.el and elib-queue.el, resp.
+
+Sat May 11 03:36:30 1991  Inge Wallin  (inge at laila)
+
+	* New file in the library: elib-read.el, containing a few functions
+	  for reading data from the minibuffer.  Documented them in
+	  elib.texinfo. 
+
+	* Fixed a number of bugs in the documentation reported by
+	  Sebastian Kremer.
+
+Fri May 10 03:28:04 1991  Inge Wallin  (inge at laila)
+
+	* Documented the new container type AVL tree.  Also added it to
+	  Makefile. 
+
+	* Done some small changes in elib.texinfo regarding classes in
+	  version 0.01.
+
+Thu May  9 23:07:02 1991  Inge Wallin  (inge at laila)
+
+	* version 0.01 released. Contents: 2 string functions, a stack and
+	  a queue.
+
+		    GNU GENERAL PUBLIC LICENSE
+		       Version 2, June 1991
+
+ Copyright (C) 1989, 1991 Free Software Foundation, Inc.
+ 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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.
+
+		    GNU GENERAL PUBLIC LICENSE
+   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+  0. 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.
+
+  1. 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.
+
+  2. 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.
+
+  3. 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.
+
+  4. 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.
+
+  5. 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.
+
+  6. 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.
+
+  7. 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.
+
+  8. 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.
+
+  9. 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.
+
+  10. 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
+
+  11. 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.
+
+  12. 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
+
+	Appendix: 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 a brief 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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.
+1998-10-01  SL Baur  <steve@altair.xemacs.org>
+
+	* Adapted to XEmacs.
+
+1998-08-25  Karl M. Hegbloom  <karlheg@bittersweet.inetarena.com>
+
+	* This is elib_1.0-8 from Debian GNU/Linux.
+	* Renamed ChangeLog to 0ChangeLog, installed this fresh one.
+	* Added an XEmacs packaging Makefile, moved aside original Makefile.
+	* Imported to CVS control for the XEmacs project.
+
+$Id$
+
+This file describes the installation of Elib, the GNU emacs lisp
+library.  You should install not only the library but also the on-line
+documentation so that your users will know how to use it.  You can
+also create written documentation from the file elib.texi as well
+as an on-line info file.
+
+
+I. Installation
+
+ 1) Edit the Makefile to reflect the situation at your site. The only
+    things you will have to change at this stage is the definition of
+    locallisppath and infodir.  In the locallisppath directory, a
+    subdirectory with the name `elib' will be created.  All elisp
+    files of the library will be copied there when you do the actual
+    installation (see step 2. below).
+
+    We suggest you use the directory which is intended for this in the
+    emacs distribution (usually /usr/local/share/emacs/site-lisp or
+    something similar) for this. 
+
+ 2) Type `make install' in the source directory. This will
+    byte-compile all .el-files of the library and create the
+    subdirectory `elib' in the directory you specified in step 1.
+    It will also copy both the .el and the .elc files of the library
+    there.
+
+    If you only want to create the compiled elisp files, but don't
+    want to install them,  you can type `make' instead. 
+
+ 3) Edit the file `default.el' in your emacs lisp directory (usually
+    /usr/gnu/emacs/lisp or something similar) and enter the contents
+    of the file `elib-startup.el' into it.  This file was created from
+    the file `startup_template.el' by the make in step 2. 
+
+
+II. Installation of the on-line manual.
+
+ 1) Create the info file `elib.info' from elib.texi.  This is done if
+    you use `make' or `make install'.
+
+ 2) Move the info file `elib.info' to your standard info directory.
+    Usually this is /usr/local/share/info or something similar. See
+    step I.3 above.
+
+ 3) Edit the file `dir' in the info directory and enter one line
+    containing a pointer to the info file elib.  The line can, for
+    instance, look like this:
+
+    * Elib: (elib.info).	The Emacs Lisp Library.
+
+
+III. How to make written documentation from elib.texi
+
+You can also make a typeset manual from the file elib.texi.  Just
+follow these steps:
+
+ 1) If the file texinfo.tex is not properly installed in the path
+    given by the environment variable $TEXINPUTS, get it and put it in
+    the same directory as elib.texi.  This file contains macros
+    used by the TeX formatting program to produce typeset output from
+    a texinfo file. You can get this for instance from from
+    prep.ai.mit.edu in the US or from ftp.isy.liu.se in Europe.
+
+ 2) Run TeX by typing `tex elib.texi'.  You might need to do this
+    twice to get correct cross references.
+
+ 3) Convert the resulting device independent file `elib.dvi' to a form
+    which your printer can output and print it.  If you have
+    postscript printers there is a program, dvi2ps, which can do this.
+    There is also a program which comes with TeX, dvips, which you can
+    use.
+# Makefile for XEmacs development lisp code
+
+# This file is part of XEmacs.
+
+# XEmacs 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, or (at your option) any
+# later version.
+
+# XEmacs 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 XEmacs; see the file COPYING.  If not, write to
+# the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+# Boston, MA 02111-1307, USA.
+
+# This XEmacs package contains independent single file lisp packages
+
+VERSION = 1.01
+AUTHOR_VERSION = 1.0
+MAINTAINER = XEmacs Development Team <xemacs-beta@xemacs.org>
+PACKAGE = elib
+PKG_TYPE = single-file
+REQUIRES = 
+CATEGORY = libs
+
+EXTRA_SOURCES = NEWS README
+
+INFO_FILES = $(PACKAGE).info*
+TEXI_FILES = $(PACKAGE).texi gpl.texi
+MANUAL = elib
+
+ELCS = stack-f.elc stack-m.elc queue-f.elc queue-m.elc \
+       elib-node.elc dll.elc dll-debug.elc bintree.elc \
+       avltree.elc cookie.elc string.elc read.elc
+
+include ../../XEmacs.rules
+
+all:: $(ELCS) auto-autoloads.elc elib.info
+
+srckit: srckit-std
+
+binkit: binkit-sourceinfo
+
+in-place: inplace-sourceinfo
+# $Id$
+# Makefile for the GNU Emacs lisp library, Elib
+# Copyright (C) 1991-1995 Free Software Foundation
+#
+# This file is part of the GNU Emacs lisp library, Elib.
+#
+# GNU Elib 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, or (at your option)
+# any later version.
+#
+# GNU Elib 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 GNU Emacs; see the file COPYING.  If not, write to
+# the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
+#
+
+# ================================================================
+# Change the following to reflect the situation at your site:
+
+prefix = /usr
+datadir = $(prefix)/lib
+#locallisppath = $(datadir)/emacs/site-lisp
+locallisppath= $(prefix)/share/emacs/site-lisp
+# This will fail if locallisppath is anything but a single directory.
+# That is all right, since that is the default behaviour of Emacs; those
+# that know how to change it, should know how to change this file.  And
+# if this is accepted into GNU Emacs, the files should end up inside
+# the normal lisp directory.
+ELIBDIR = $(locallisppath)/elib
+infodir = $(prefix)/info
+
+EMACS = emacs
+MAKEINFO = makeinfo
+TEXI2DVI = texi2dvi
+SHELL = /bin/sh
+INSTALL_DATA = /usr/bin/install -m 644
+INSTALL_DIR = /usr/bin/install -d
+
+# ================================================================
+# You shouldn't change anything below this line.
+#
+
+VERSION = 1.0
+
+ELFILES = stack-f.el stack-m.el queue-f.el queue-m.el \
+elib-node.el bintree.el avltree.el string.el read.el cookie.el dll.el \
+dll-debug.el
+
+ELCFILES = stack-f.elc stack-m.elc queue-f.elc queue-m.elc\
+elib-node.elc bintree.elc avltree.elc string.elc read.elc cookie.elc dll.elc \
+dll-debug.elc
+
+all: elcfiles elib-startup.el info
+
+elib-startup.el: startup-template.el Makefile
+	sed s,ELIB_PATH,\"$(ELIBDIR)\", < startup-template.el > elib-startup.el
+
+install: installdirs install-info
+	$(INSTALL_DATA) $(ELFILES) $(ELIBDIR)
+#$(INSTALL_DATA) $(ELCFILES) $(ELIBDIR)
+#@echo Please merge elib-startup.el into $(locallisppath)/default.el
+
+installdirs:
+	-$(INSTALL_DIR) $(ELIBDIR)
+
+install-info: elib.info
+	$(INSTALL_DIR) $(infodir)
+	$(INSTALL_DATA) elib.info* $(infodir)
+#if $(SHELL) -c 'install-info --version' \
+#	>/dev/null 2>&1; then \
+#	install-info --infodir=$(infodir) elib.info; \
+#else true; fi
+
+clean:
+	$(RM) *~ elib-startup.el core $(ELCFILES)
+	$(RM) -r $(DISTDIR) $(DISTDIR).tar.gz $(DISTDIR).tar.gz.uu
+	$(RM) -f elib.info*
+
+
+info: elib.info
+
+elib.info: elib.texi
+	$(MAKEINFO) elib.texi
+
+dvi: elib.dvi
+
+elib.dvi: elib.texi
+	$(TEXI2DVI) $(srcdir)/elib.texi
+
+.PHONY: elcfiles
+elcfiles:
+	$(EMACS) -batch -l elib-compile-all.el -f compile-elib
+
+TAGS tags:
+	etags $(ELFILES)
+
+# Below this point is rules for release management.
+
+OTHERS = README INSTALL COPYING ChangeLog elib.texi gpl.texi \
+	startup-template.el elib-compile-all.el Makefile \
+	.cvsignore RELEASING TODO NEWS elib-test.el
+
+
+DISTDIR = elib-$(VERSION)
+
+dist: disttree
+	rm -f $(DISTDIR).tar.gz $(DISTDIR).tar.gz.uu
+	tar cvf $(DISTDIR).tar $(DISTDIR)
+	gzip $(DISTDIR).tar
+
+disttree:
+	rm -rf $(DISTDIR) || exit 0
+	mkdir $(DISTDIR)
+	cp $(ELFILES) $(DISTDIR)
+	cp $(OTHERS) $(DISTDIR)
+
+# eof
+Elib NEWS -- history of changes.  10 Dec 1995
+Copyright (C) 1995 Free Software Foundation, Inc.
+See the end for copying conditions.
+
+* Changes in Elib 1.0.
+
+** This is a clean-up release.  No new features exists.
+
+** The Makefile and overall structure of the package has been changed
+to make it simpler and more in accordance with the GNU Coding
+Standards.  We now distribute all the files needed to make a new
+distribution.  Several files has moved or changed names; see the
+ChangeLog for details.
+
+** The library is now distributed under GPL 2, not GPL 1.
+
+** The documentation is improved.
+
+* Changes in Elib 0.07.
+
+** Some bugs in the cookie package were fixed.
+
+** Some test cases for the cooke package were added.
+
+* Changes in Elib 0.06
+
+** A number of bugs were fixed.
+
+** Debug code for the doubly linked list, dll.  Now you can use
+dll-debug while developing your code, and when finished switch to
+dll. 
+
+----------------------------------------------------------------------
+Copyright information:
+
+Copyright (C) 1995 Free Software Foundation, Inc.
+
+   Permission is granted to anyone to make or distribute verbatim copies
+   of this document as received, in any medium, provided that the
+   copyright notice and this permission notice are preserved,
+   thus giving the recipient permission to redistribute in turn.
+
+   Permission is granted to distribute modified versions
+   of this document, or of portions of it,
+   under the above conditions, provided also that they
+   carry prominent notices stating who last changed them.
+		     This is the README file for
+
+				 ELIB
+				  -
+			The Emacs Lisp Library
+
+			   Version 1.0
+
+		  Inge Wallin <inge@lysator.liu.se>
+		Per Cederqvist <ceder@lysator.liu.se>
+
+================================================================
+
+This is the source directory for the GNU emacs lisp library Elib
+version 1.0.  Elib is designed to be for Elisp programs what libg++ is
+for C++ programs:  a collection of useful routines which don't have to
+be reinvented each time a new program is written.
+
+Elib contains code for:
+ - container data structures (queues, stacks, AVL trees, etc)
+ - string handling functions missing in standard emacs
+ - minibuffer handling functions missing in standard emacs
+ - routines for handling lists of so called cookies in a buffer. 
+
+Information about how to install the library and the documentation is
+in the file INSTALL.  Licensing terms are in the file COPYING.
+Further documentation is in the Texinfo file elib.texi. 
+
+Please send bug reports, suggestions and comments to
+elib-maintainers@lysator.liu.se.  
+
+Known bugs:
+  + The documentation could be better. It lacks an index, among 
+    other things.
+  + The stack-m and stack-f should probably both (provide 'stack).
+    stack-m.el should maybe be renamed stack.el, and stack-f.el
+    should maybe only be used while debugging.  We are still 
+    thinking about this. Suggestions are welcome.
+  + The cookie package has a number of inconsistencies regarding
+    handling of (point).
+
+Enjoy!
+
+	Link�ping 10-dec-1995
+	Inge Wallin
+	Per Cederqvist
+Step-by-step instructions for how to make a release of Elib.
+
+  + Update all Copyright lines in all files.
+  + Run all testcases.
+  + Makefile: VERSION: set it correctly.
+  + Makefile: Check ELFILES and ELCFILES.
+  + elib.texi: Search for --version-- and fix it.
+  + elib.texi: Search for --site-- and fix it.
+  + elib.texi: Search for --date-- and fix it.
+  + elib-compile-all.el: Check that elib-files contains all the elisp
+    files that should be compiled.
+  + README: Update it.
+  + INSTALL: Update it.
+  + ChangeLog: Write an entry.
+  + Check in everything into CVS (which is used to maintain Elib).
+  + Do "make dist"
+  + Test unpacking and installing Elib.
+  + Run "cvs tag elib_0_04" (with the appropriate version number).
+  + Install the tar file in ftp@lysator:pub/emacs/elib-0.04.tar.Z
+		        and ftp@isy:pub/gnu/elisp-programms/
+This file lists a number of things that should be done to the library
+in the future.
+================================================================
+
+* Automated tests for the following files:
+   - elib-node.el
+   - avltree.el
+   - bintree.el
+   - string.el
+   - read.el
+   - dll.el
+   - cookie.el
+
+* Documentation of the automated test procedure
+
+* Priority queue
+
+* Debug variants of the container types which check everything on
+  run-time.  This would be very slow but could also be a great help.
+;;;; $Id$
+;;;; This file implements balanced binary trees, AVL-trees.
+
+;; Copyright (C) 1991-1995 Free Software Foundation
+
+;; Author: Inge Wallin <inge@lysator.liu.se>
+;;	Thomas Bellman <bellman@lysator.liu.se>
+;; Maintainer: elib-maintainers@lysator.liu.se
+;; Created: 10 May 1991
+;; Keywords: extensions, lisp
+
+;;;; This file is part of the GNU Emacs lisp library, Elib.
+;;;;
+;;;; GNU Elib 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, or (at your option)
+;;;; any later version.
+;;;;
+;;;; GNU Elib 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 GNU Elib; see the file COPYING.  If not, write to
+;;;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+;;;; Boston, MA 02111-1307, USA
+;;;;
+;;;; Initial author:	 Thomas Bellman	       
+;;;;			 Lysator Computer Club 
+;;;;		 	 Linkoping University  
+;;;;		 	 Sweden		       
+;;;;
+;;;; Bugfixes and completion: Inge Wallin
+;;;;
+
+
+;;; Commentary:
+;;;
+;;; An AVL tree is a nearly-perfect balanced binary tree.  A tree
+;;; consists of two cons cells, the first one holding the tag
+;;; 'AVLTREE in the car cell, and the second one having the tree
+;;; in the car and the compare function in the cdr cell.  The tree has
+;;; a dummy node as its root with the real tree in the left pointer.
+;;; 
+;;; Each node of the tree consists of one data element, one left
+;;; sub-tree and one right sub-tree.  Each node also has a balance
+;;; count, which is the difference in depth of the left and right
+;;; sub-trees. 
+;;;
+
+;;; Code:
+
+(require 'elib-node)
+(require 'stack-m)
+
+(provide 'avltree)
+
+
+;;; ================================================================
+;;;        Functions and macros handling an AVL tree node.
+
+;;
+;; The rest of the functions needed here can be found in
+;; elib-node.el.
+;;
+
+
+(defmacro elib-avl-node-create (left right data balance)
+
+  ;; Create and return an avl-tree node.
+  (` (vector (, left) (, right) (, data) (, balance))))
+
+
+(defmacro elib-avl-node-balance (node)
+
+  ;; Return the balance field of a node.
+  (` (aref (, node) 3)))
+
+
+(defmacro elib-avl-node-set-balance (node newbal)
+
+  ;; Set the balance field of a node.
+  (` (aset (, node) 3 (, newbal))))
+
+
+
+;;; ================================================================
+;;;       Internal functions for use in the AVL tree package
+
+;;;
+;;; The functions and macros in this section all start with `elib-avl-'.
+;;;
+
+
+(defmacro elib-avl-root (tree)
+
+  ;; Return the root node for an avl-tree.  INTERNAL USE ONLY.
+  (` (elib-node-left (car (cdr (, tree))))))
+
+
+(defmacro elib-avl-dummyroot (tree)
+
+  ;; Return the dummy node of an avl-tree.  INTERNAL USE ONLY.
+
+  (` (car (cdr (, tree)))))
+
+
+(defmacro elib-avl-cmpfun (tree)
+
+  ;; Return the compare function of AVL tree TREE.  INTERNAL USE ONLY.
+  (` (cdr (cdr (, tree)))))
+
+
+;; ----------------------------------------------------------------
+;;                          Deleting data
+
+
+(defun elib-avl-del-balance1 (node branch)
+
+  ;; Rebalance a tree and return t if the height of the tree has shrunk.
+  (let* ((br (elib-node-branch node branch))
+	 p1
+	 b1
+	 p2
+	 b2 
+	 result)
+    (cond
+     ((< (elib-avl-node-balance br) 0)
+      (elib-avl-node-set-balance br 0)
+      t)
+
+     ((= (elib-avl-node-balance br) 0)
+      (elib-avl-node-set-balance br +1)
+      nil)
+
+     (t					; Rebalance
+      (setq p1 (elib-node-right br)
+	    b1 (elib-avl-node-balance p1))
+      (if (>= b1 0)
+	  ;; Single RR rotation
+	  (progn
+	    (elib-node-set-right br (elib-node-left p1))
+	    (elib-node-set-left p1 br)
+	    (if (= 0 b1)
+		(progn
+		  (elib-avl-node-set-balance br +1)
+		  (elib-avl-node-set-balance p1 -1)
+		  (setq result nil))
+	      (elib-avl-node-set-balance br 0)
+	      (elib-avl-node-set-balance p1 0)
+	      (setq result t))
+	    (elib-node-set-branch node branch p1)
+	    result)
+
+	;; Double RL rotation
+	(setq p2 (elib-node-left p1)
+	      b2 (elib-avl-node-balance p2))
+	(elib-node-set-left p1 (elib-node-right p2))
+	(elib-node-set-right p2 p1)
+	(elib-node-set-right br (elib-node-left p2))
+	(elib-node-set-left p2 br)
+	(if (> b2 0)
+	    (elib-avl-node-set-balance br -1)
+	  (elib-avl-node-set-balance br 0))
+	(if (< b2 0)
+	    (elib-avl-node-set-balance p1 +1)
+	  (elib-avl-node-set-balance p1 0))
+	(elib-node-set-branch node branch p2)
+	(elib-avl-node-set-balance p2 0)
+	t)
+      ))
+    ))
+
+
+(defun elib-avl-del-balance2 (node branch)
+
+  (let* ((br (elib-node-branch node branch))
+	 p1
+	 b1
+	 p2 
+	 b2 
+	 result)
+    (cond
+     ((> (elib-avl-node-balance br) 0)
+      (elib-avl-node-set-balance br 0)
+      t)
+
+     ((= (elib-avl-node-balance br) 0)
+      (elib-avl-node-set-balance br -1)
+      nil)
+
+     (t					; Rebalance
+      (setq p1 (elib-node-left br)
+	    b1 (elib-avl-node-balance p1))
+      (if (<= b1 0)
+	  ;; Single LL rotation
+	  (progn
+	    (elib-node-set-left br (elib-node-right p1))
+	    (elib-node-set-right p1 br)
+	    (if (= 0 b1)
+		(progn
+		  (elib-avl-node-set-balance br -1)
+		  (elib-avl-node-set-balance p1 +1)
+		  (setq result nil))
+	      (elib-avl-node-set-balance br 0)
+	      (elib-avl-node-set-balance p1 0)
+	      (setq result t))
+	    (elib-node-set-branch node branch p1)
+	    result)
+
+	;; Double LR rotation
+	(setq p2 (elib-node-right p1)
+	      b2 (elib-avl-node-balance p2))
+	(elib-node-set-right p1 (elib-node-left p2))
+	(elib-node-set-left p2 p1)
+	(elib-node-set-left br (elib-node-right p2))
+	(elib-node-set-right p2 br)
+	(if (< b2 0)
+	    (elib-avl-node-set-balance br +1)
+	  (elib-avl-node-set-balance br 0))
+	(if (> b2 0)
+	    (elib-avl-node-set-balance p1 -1)
+	  (elib-avl-node-set-balance p1 0))
+	(elib-node-set-branch node branch p2)
+	(elib-avl-node-set-balance p2 0)
+	t)
+      ))
+    ))
+
+
+(defun elib-avl-do-del-internal (node branch q)
+
+  (let* ((br (elib-node-branch node branch)))
+      (if (elib-node-right br)
+	  (if (elib-avl-do-del-internal br +1 q)
+	      (elib-avl-del-balance2 node branch))
+	(elib-node-set-data q (elib-node-data br))
+	(elib-node-set-branch node branch
+			      (elib-node-left br))
+	t)))
+
+
+
+(defun elib-avl-do-delete (cmpfun root branch data)
+
+  ;; Return t if the height of the tree has shrunk.
+  (let* ((br (elib-node-branch root branch)))
+    (cond
+     ((null br)
+      nil)
+
+     ((funcall cmpfun data (elib-node-data br))
+      (if (elib-avl-do-delete cmpfun br 0 data)
+	  (elib-avl-del-balance1 root branch)))
+
+     ((funcall cmpfun (elib-node-data br) data)
+      (if (elib-avl-do-delete cmpfun br 1 data)
+	  (elib-avl-del-balance2 root branch)))
+
+     (t
+      ;; Found it.  Let's delete it.
+      (cond
+       ((null (elib-node-right br))
+	(elib-node-set-branch root branch (elib-node-left br))
+	t)
+
+       ((null (elib-node-left br))
+	(elib-node-set-branch root branch (elib-node-right br))
+	t)
+
+       (t
+	(if (elib-avl-do-del-internal br 0 br)
+	    (elib-avl-del-balance1 root branch)))))
+     )))
+
+
+;; ----------------------------------------------------------------
+;;                           Entering data
+
+
+
+(defun elib-avl-enter-balance1 (node branch)
+
+  ;; Rebalance a tree and return t if the height of the tree has grown.
+  (let* ((br (elib-node-branch node branch))
+	 p1
+	 p2
+	 b2 
+	 result)
+    (cond
+     ((< (elib-avl-node-balance br) 0)
+      (elib-avl-node-set-balance br 0)
+      nil)
+
+     ((= (elib-avl-node-balance br) 0)
+      (elib-avl-node-set-balance br +1)
+      t)
+
+     (t
+      ;; Tree has grown => Rebalance
+      (setq p1 (elib-node-right br))
+      (if (> (elib-avl-node-balance p1) 0)
+	  ;; Single RR rotation
+	  (progn
+	    (elib-node-set-right br (elib-node-left p1))
+	    (elib-node-set-left p1 br)
+	    (elib-avl-node-set-balance br 0)
+	    (elib-node-set-branch node branch p1))
+
+	;; Double RL rotation
+	(setq p2 (elib-node-left p1)
+	      b2 (elib-avl-node-balance p2))
+	(elib-node-set-left p1 (elib-node-right p2))
+	(elib-node-set-right p2 p1)
+	(elib-node-set-right br (elib-node-left p2))
+	(elib-node-set-left p2 br)
+	(if (> b2 0)
+	    (elib-avl-node-set-balance br -1)
+	  (elib-avl-node-set-balance br 0))
+	(if (< b2 0)
+	    (elib-avl-node-set-balance p1 +1)
+	  (elib-avl-node-set-balance p1 0))
+	(elib-node-set-branch node branch p2))
+      (elib-avl-node-set-balance (elib-node-branch node branch) 0)
+      nil))
+    ))
+
+
+(defun elib-avl-enter-balance2 (node branch)
+
+  ;; Return t if the tree has grown.
+  (let* ((br (elib-node-branch node branch))
+	 p1
+	 p2 
+	 b2)
+    (cond
+     ((> (elib-avl-node-balance br) 0)
+      (elib-avl-node-set-balance br 0)
+      nil)
+
+     ((= (elib-avl-node-balance br) 0)
+      (elib-avl-node-set-balance br -1)
+      t)
+
+     (t	
+      ;; Balance was -1 => Rebalance
+      (setq p1 (elib-node-left br))
+      (if (< (elib-avl-node-balance p1) 0)
+	  ;; Single LL rotation
+	  (progn
+	    (elib-node-set-left br (elib-node-right p1))
+	    (elib-node-set-right p1 br)
+	    (elib-avl-node-set-balance br 0)
+	    (elib-node-set-branch node branch p1))
+
+	;; Double LR rotation
+	(setq p2 (elib-node-right p1)
+	      b2 (elib-avl-node-balance p2))
+	(elib-node-set-right p1 (elib-node-left p2))
+	(elib-node-set-left p2 p1)
+	(elib-node-set-left br (elib-node-right p2))
+	(elib-node-set-right p2 br)
+	(if (< b2 0)
+	    (elib-avl-node-set-balance br +1)
+	  (elib-avl-node-set-balance br 0))
+	(if (> b2 0)
+	    (elib-avl-node-set-balance p1 -1)
+	  (elib-avl-node-set-balance p1 0))
+	(elib-node-set-branch node branch p2))
+      (elib-avl-node-set-balance (elib-node-branch node branch) 0)
+      nil))
+    ))
+
+
+(defun elib-avl-do-enter (cmpfun root branch data)
+
+  ;; Return t if height of tree ROOT has grown.  INTERNAL USE ONLY.
+  (let ((br (elib-node-branch root branch)))
+    (cond
+     ((null br)
+      ;; Data not in tree, insert it
+      (elib-node-set-branch root branch
+			    (elib-avl-node-create nil nil data 0))
+      t)
+
+     ((funcall cmpfun data (elib-node-data br))
+      (and (elib-avl-do-enter cmpfun
+			      br
+			      0 data)
+	   (elib-avl-enter-balance2 root branch)))
+
+     ((funcall cmpfun (elib-node-data br) data)
+      (and (elib-avl-do-enter cmpfun
+			      br
+			      1 data)
+	   (elib-avl-enter-balance1 root branch)))
+
+     (t
+      (elib-node-set-data br data)
+      nil))))
+
+
+;; ----------------------------------------------------------------
+
+
+(defun elib-avl-mapc (map-function root)
+  ;; Apply MAP-FUNCTION to all nodes in the tree starting with ROOT.
+  ;; The function is applied in-order.
+  ;;
+  ;; Note: MAP-FUNCTION is applied to the node and not to the data itself.
+  ;; INTERNAL USE ONLY.
+
+  (let ((node root)
+	(stack (elib-stack-create))
+	(go-left t))
+    (elib-stack-push stack nil)
+    (while node
+      (if (and go-left
+	       (elib-node-left node))
+	  (progn				   ; Do the left subtree first.
+	    (elib-stack-push stack node)
+	    (setq node (elib-node-left node)))
+	(funcall map-function node)		   ; Apply the function...
+	(if (elib-node-right node)		   ; and do the right subtree.
+	    (setq node (elib-node-right node)
+		  go-left t)
+	  (setq node (elib-stack-pop stack)
+		go-left nil))))))
+
+
+(defun elib-avl-do-copy (root)
+  ;; Copy the tree with ROOT as root.
+  ;; Highly recursive. INTERNAL USE ONLY.
+  (if (null root) 
+      nil
+    (elib-avl-node-create (elib-avl-do-copy (elib-node-left root))
+			  (elib-avl-do-copy (elib-node-right root))
+			  (elib-node-data root)
+			  (elib-avl-node-balance root))))
+
+
+
+;;; ================================================================
+;;;       The public functions which operate on AVL trees.
+
+
+(defun avltree-create (compare-function)
+  "Create an empty avl tree.
+COMPARE-FUNCTION is a function which takes two arguments, A and B,
+and returns non-nil if A is less than B, and nil otherwise."
+  (cons 'AVLTREE
+	(cons (elib-avl-node-create nil nil nil 0)
+	      compare-function)))
+
+
+(defun avltree-p (obj)
+  "Return t if OBJ is an avl tree, nil otherwise."
+  (eq (car-safe obj) 'AVLTREE))
+
+
+(defun avltree-compare-function (tree)
+  "Return the comparision function for the avl tree TREE."
+  (elib-avl-cmpfun tree))
+
+
+(defun avltree-empty (tree)
+  "Return t if TREE is emtpy, otherwise return nil."
+  (null (elib-avl-root tree)))
+
+
+(defun avltree-enter (tree data)
+  "In the avl tree TREE insert DATA.
+Return DATA."
+
+  (elib-avl-do-enter (elib-avl-cmpfun tree)
+		     (elib-avl-dummyroot tree)
+		     0
+		     data)
+  data)
+
+
+(defun avltree-delete (tree data)
+  "From the avl tree TREE, delete DATA.
+Return the element in TREE which matched DATA, nil if no element matched."
+
+  (elib-avl-do-delete (elib-avl-cmpfun tree)
+		      (elib-avl-dummyroot tree)
+		      0
+		      data))
+
+
+(defun avltree-member (tree data)
+  "Return the element in the avl tree TREE which matches DATA.
+Matching uses the compare function previously specified in `avltree-create'
+when TREE was created.
+
+If there is no such element in the tree, the value is nil."
+
+  (let ((node (elib-avl-root tree))
+	(compare-function (elib-avl-cmpfun tree))
+	found)
+    (while (and node 
+		(not found))
+      (cond
+       ((funcall compare-function data (elib-node-data node))
+	(setq node (elib-node-left node)))
+       ((funcall compare-function (elib-node-data node) data)
+	(setq node (elib-node-right node)))
+       (t 
+	(setq found t))))
+
+    (if node
+	(elib-node-data node)
+      nil)))
+
+
+
+(defun avltree-map (__map-function__ tree)
+  "Apply MAP-FUNCTION to all elements in the avl tree TREE."
+  (elib-avl-mapc
+   (function (lambda (node)
+	       (elib-node-set-data node
+				   (funcall __map-function__
+					    (elib-node-data node)))))
+   (elib-avl-root tree)))
+
+
+
+(defun avltree-first (tree)
+  "Return the first element in TREE, or nil if TREE is empty."
+
+  (let ((node (elib-avl-root tree)))
+    (if node
+	(progn
+	  (while (elib-node-left node)
+	    (setq node (elib-node-left node)))
+	  (elib-node-data node))
+      nil)))
+
+
+(defun avltree-last (tree)
+  "Return the last element in TREE, or nil if TREE is empty."
+  (let ((node (elib-avl-root tree)))
+    (if node
+	(progn
+	  (while (elib-node-right node)
+	    (setq node (elib-node-right node)))
+	  (elib-node-data node))
+      nil)))
+
+
+(defun avltree-copy (tree)
+  "Return a copy of the avl tree TREE."
+  (let ((new-tree (avltree-create 
+		   (elib-avl-cmpfun tree))))
+    (elib-node-set-left (elib-avl-dummyroot new-tree)
+			(elib-avl-do-copy (elib-avl-root tree)))
+    new-tree))
+
+
+(defun avltree-flatten (tree)
+  "Return a sorted list containing all elements of TREE."
+  (nreverse
+   (let ((treelist nil))
+     (elib-avl-mapc (function (lambda (node)
+				(setq treelist (cons (elib-node-data node)
+						     treelist))))
+		    (elib-avl-root tree))
+     treelist)))
+
+
+(defun avltree-size (tree)
+  "Return the number of elements in TREE."
+  (let ((treesize 0))
+    (elib-avl-mapc (function (lambda (data)
+			       (setq treesize (1+ treesize))
+			       data))
+		   (elib-avl-root tree))
+    treesize))
+
+
+(defun avltree-clear (tree)
+  "Clear the avl tree TREE."
+  (elib-node-set-left (elib-avl-dummyroot tree) nil))
+
+;;; avltree.el ends here
+;;;; $Id$
+;;; This file implements binary trees.
+
+;; Copyright (C) 1991-1995 Free Software Foundation
+
+;; Author: Inge Wallin <inge@lysator.liu.se>
+;; Maintainer: elib-maintainers@lysator.liu.se
+;; Created: 21 May 1991
+;; Keywords: extensions, lisp
+
+;;;; This file is part of the GNU Emacs lisp library, Elib.
+;;;;
+;;;; GNU Elib 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, or (at your option)
+;;;; any later version.
+;;;;
+;;;; GNU Elib 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 GNU Elib; see the file COPYING.  If not, write to
+;;;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+;;;; Boston, MA 02111-1307, USA
+;;;;
+;;;; Author:  Inge Wallin
+;;;;
+
+;;; Commentary:
+
+;;;
+;;; A binary tree consists of two cons cells, the first one holding
+;;; the tag 'BINTREE in the car cell and the second one having
+;;; the tree in the car and the compare function in the cdr cell. The
+;;; tree has a dummy node as its root with the real tree in the left
+;;; pointer.  The compare function must take two arguments of the type
+;;; which is to be stored in the tree and must return non-nil if
+;;; the first argument is "less than" the second argument and nil 
+;;; otherwise.
+;;;
+;;; For example, use
+;;;    (bintree-create '<)
+;;; if the tree is going to store integers.
+;;; 
+;;;
+;;; This package uses the macros in the file elib-node.el and
+;;; a stack from stack.el.
+;;;
+
+;;; Code:
+
+(require 'elib-node)
+(require 'stack-m)
+
+(provide 'bintree)
+
+
+;;; ================================================================
+;;;      Internal functions for use in the binary tree package
+
+
+(defmacro elib-bintree-root (tree)
+
+  ;; Return the root node for a binary tree.  INTERNAL USE ONLY.
+  (` (elib-node-left (car (cdr (, tree))))))
+
+
+(defmacro elib-bintree-dummyroot (tree)
+
+  ;; Return the dummy node of a binary tree.  INTERNAL USE ONLY.
+  (` (car (cdr (, tree)))))
+
+
+(defmacro elib-bintree-cmpfun (tree)
+
+  ;; Return the compare function of binary tree TREE.  INTERNAL USE ONLY."
+  (` (cdr (cdr (, tree)))))
+
+
+
+(defun elib-bintree-mapc (map-function root)
+
+  ;; Apply MAP-FUNCTION to all nodes in the tree starting with ROOT.
+  ;; The function is applied in-order.
+  ;;
+  ;; Note: MAP-FUNCTION is applied to the node and not to the data itself.
+  ;;
+  ;; INTERNAL USE ONLY."
+
+  (let ((node root)
+	(stack (elib-stack-create))
+	(go-left t))
+    (elib-stack-push stack nil)
+    (while node
+      (if (and go-left
+	       (elib-node-left node))
+	  (progn				   ; Do the left subtree first.
+	    (elib-stack-push stack node)
+	    (setq node (elib-node-left node)))
+	(funcall map-function node)		   ; Apply the function...
+	(if (elib-node-right node)		   ; and do the right subtree.
+	    (setq node (elib-node-right node)
+		  go-left t)
+	  (setq node (elib-stack-pop stack)
+		go-left nil))))))
+
+
+(defun elib-bintree-do-copy (root)
+
+  ;; Copy the tree with ROOT as root.  Highly recursive. INTERNAL USE ONLY.
+  (if (null root) 
+      nil
+    (elib-node-create (elib-bintree-do-copy (elib-node-left root))
+		      (elib-bintree-do-copy (elib-node-right root))
+		      (elib-node-data root))))
+
+
+;;; ================================================================
+;;;       The public functions which operate on binary trees.
+
+
+(defun bintree-create (compare-function)
+  "Create an empty binary tree using COMPARE-FUNCTION as the compare function.
+COMPARE-FUNCTION is a function which takes two arguments, A and B, and 
+returns non-nil if A is less than B, and nil otherwise."
+  
+  (cons 'BINTREE
+	(cons (elib-node-create nil nil nil)
+	      compare-function)))
+
+
+
+(defun bintree-p (obj)
+  "return t if OBJ is a binary tree, nil otherwise."
+  (eq (car-safe obj) 'BINTREE))
+
+
+
+(defun bintree-compare-function (tree)
+  "Return the comparision function for the binary tree TREE."
+  (elib-bintree-cmpfun tree))
+
+
+
+(defun bintree-empty (tree)
+  "Return t if the binary tree TREE is empty, otherwise return nil."
+  (null (elib-bintree-root tree)))
+
+
+
+(defun bintree-enter (tree data)
+  "In the binary tree TREE, insert DATA."
+
+  (let ((cmpfun (elib-bintree-cmpfun tree))
+	(node (elib-bintree-dummyroot tree))
+	(new-node (elib-node-create nil nil data)))
+    (if (null (elib-node-left node))
+	(elib-node-set-left node new-node)
+      (setq node (elib-node-left node))
+      (while node
+	(cond
+	 ((funcall cmpfun data (elib-node-data node))
+	  (if (elib-node-left node)
+	      (setq node (elib-node-left node))
+	    (elib-node-set-left node new-node)
+	    (setq node nil)))
+
+	 ((funcall cmpfun (elib-node-data node) data)
+	  (if (elib-node-right node)
+	      (setq node (elib-node-right node))
+	    (elib-node-set-right node new-node)
+	    (setq node nil)))
+
+	 (t
+	  (elib-node-set-data node data)
+	  (setq node nil)))))))
+
+
+
+(defun bintree-delete (tree data)
+  "From the binary tree TREE, delete DATA.
+Return the element in TREE which matched DATA, or nil if no element matched."
+
+  (let* ((cmpfun (elib-bintree-cmpfun tree))
+	 (upper-node (elib-bintree-dummyroot tree)) ; Start with the dummy node
+	 (branch 0)				   ; Left branch
+	 (branch-node (elib-node-left upper-node))
+	 node-data
+	 right-node)				   ; Only used while deleting,
+						   ; not while searching
+    (if (null branch-node)
+	nil
+      (while upper-node
+	(setq node-data (elib-node-data branch-node))
+	(cond 
+	 ((funcall cmpfun data node-data)	   ; data<node-data => go left
+	  (setq upper-node branch-node
+		branch-node (elib-node-left upper-node)
+		branch 0))
+	 
+	 ((funcall cmpfun node-data data)	   ; data>node-data => go right
+	  (setq upper-node branch-node
+		branch-node (elib-node-right upper-node)
+		branch 1))
+	 
+	 (t					   ; This is the node we want 
+						   ; to delete.
+	  (cond
+	   ((null (elib-node-left branch-node))	   ; Empty left node?
+	    (elib-node-set-branch upper-node branch
+				  (elib-node-right branch-node)))
+	   
+	   ((null (elib-node-right branch-node))   ; Empty right node?
+	    (elib-node-set-branch upper-node branch
+				  (elib-node-left branch-node)))
+	   
+	   (t					   ; Both branches occupied.
+
+	    ;; At this point `branch-node' points at the node we want
+	    ;; to delete.  Both the right and the left branches are
+	    ;; non-nil, so we will take the data of the rightmost node
+	    ;; of the left subtree and put into `branch-node'.
+	    (setq right-node branch-node
+		  branch 0)
+	    (while (elib-node-right (elib-node-branch right-node branch))
+	      (setq right-node (elib-node-branch right-node branch)
+		    branch 1))
+	    (elib-node-set-data branch-node 
+				(elib-node-data (elib-node-branch right-node
+								  branch)))
+	    (elib-node-set-branch right-node branch
+				  (elib-node-left
+				   (elib-node-branch right-node branch)))))
+	  (setq upper-node nil)))))))
+
+
+
+(defun bintree-member (tree data)
+  "Return the element in the binary tree TREE which matches DATA.
+Matching uses the compare function previously specified in `bintree-create'
+when TREE was created.
+
+If there is no such element in the tree, the value is nil."
+  
+  (let ((node (elib-bintree-root tree))
+	(compare-function (elib-bintree-cmpfun tree))
+	found)
+    (while (and node 
+		(not found))
+      (cond
+       ((funcall compare-function data (elib-node-data node))
+	(setq node (elib-node-left node)))
+       ((funcall compare-function (elib-node-data node) data)
+	(setq node (elib-node-right node)))
+       (t 
+	(setq found t))))
+
+    (if node
+	(elib-node-data node)
+      nil)))
+
+
+
+(defun bintree-map (__map-function__ tree)
+  "Apply MAP-FUNCTION to all elements in the binary tree TREE."
+
+  (elib-bintree-mapc
+   (function (lambda (node)
+	       (elib-node-set-data node
+				   (funcall __map-function__
+					    (elib-node-data node)))))
+   (elib-bintree-root tree)))
+
+
+
+(defun bintree-first (tree)
+  "Return the first element in the binary tree TREE, or nil if TREE is empty."
+
+  (let ((node (elib-bintree-root tree)))
+    (if node
+	(progn
+	  (while (elib-node-left node)
+	    (setq node (elib-node-left node)))
+	  (elib-node-data node))
+      nil)))
+
+
+
+(defun bintree-last (tree)
+  "Return the last element in the binary tree TREE, or nil if TREE is empty."
+
+  (let ((node (elib-bintree-root tree)))
+    (if node
+	(progn
+	  (while (elib-node-right node)
+	    (setq node (elib-node-right node)))
+	  (elib-node-data node))
+      nil)))
+
+
+
+(defun bintree-copy (tree)
+  "Return a copy of the binary tree TREE.
+
+Note: This function is recursive and might result in an 
+      `max eval depth exceeded' error."
+
+  (let ((new-tree (bintree-create 
+		   (elib-bintree-cmpfun tree))))
+    (elib-node-set-left (elib-bintree-dummyroot new-tree)
+			(elib-bintree-do-copy (elib-bintree-root tree)))
+    new-tree))
+
+  
+
+;;
+;; Not the fastest way to do this.
+;;
+(defun bintree-flatten (tree)
+  "Return a sorted list containing all elements of the binary tree TREE."
+
+  (nreverse 
+   (let ((treelist nil))
+     (elib-bintree-mapc (function (lambda (node)
+				    (setq treelist (cons (elib-node-data node)
+							 treelist))))
+			(elib-bintree-root tree))
+     treelist)))
+
+
+
+;;
+;; Not the fastest way to do this:
+;;
+(defun bintree-size (tree)
+  "Return the number of elements in the binary tree TREE."
+
+  (let ((treesize 0))
+    (elib-bintree-mapc (function (lambda (data)
+				   (setq treesize (1+ treesize))))
+		       (elib-bintree-root tree))
+    treesize))
+
+
+
+(defun bintree-clear (tree)
+  "Clear the binary tree TREE."
+
+  (elib-node-set-left (elib-bintree-dummyroot tree) nil))
+
+;;; bintree.el ends here
+;;; $Id$
+;;; cookie.el -- Utility to display cookies in buffers
+
+;; Copyright (C) 1991-1995   Free Software Foundation
+
+;; Author: Per Cederqvist <ceder@lysator.liu.se>
+;;	Inge Wallin <inge@lysator.liu.se>
+;; Maintainer: elib-maintainers@lysator.liu.se
+;; Created: 3 Aug 1992
+;; Keywords: extensions, lisp
+
+;;; 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 GNU Elib; see the file COPYING.  If not, write to
+;;; the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+;;; Boston, MA 02111-1307, USA
+;;;
+
+
+;;; Commentary:
+
+;;;     Introduction
+;;;     ============
+;;;
+;;; Cookie is a package that implements a connection between an
+;;; 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.  pcl-cvs.el uses cookie.el.
+;;;
+;;; 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.  (The
+;;; pretty-printer should use "insert" and not
+;;; "insert-before-markers").
+;;;
+;;; 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
+;;; fixed 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).
+;;;
+;;; 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 `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.
+;;;
+;;; 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, et c, et c.
+;;;
+;;; 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.
+;;;
+;;; Full documentation will, God willing, soon be available in a
+;;; Texinfo manual.
+
+
+
+;;;     Coding conventions
+;;;     ==================
+;;;
+;;; 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.  There are
+;;; currently no global or buffer-local variables used.
+;;;
+;;; Many function operate on `tins' instead of `cookies'.  To avoid
+;;; confusion most of the function names include the string "cookie"
+;;; or "tin" to show this.
+;;;
+;;; Most doc-strings contains an "Args:" line that lists the
+;;; arguments.
+;;;
+;;; The internal functions don't contain any doc-strings.  RMS thinks
+;;; this is a good way to save space.
+
+
+
+;;; INTERNAL DOCUMENTATION (Your understanding of this package might
+;;; increase if you read it, but you should not exploit the knowledge
+;;; you gain. The internal details might change without notice).
+;;;
+;;; A collection is implemented as an dll (a doubly linked list).
+;;; The first and last element on the list are always the header and
+;;; footer (as strings). Any remaining entries are `wrappers'.
+;;;
+;;; At the implementation level a `tin' is really an elib-node that
+;;; consists of
+;;;      left        Pointer to previous tin
+;;;      right       Pointer to next tin
+;;;      data        Holder of a `wrapper'.
+;;; These internals of an elib-node are in fact unknown to cookie.el.
+;;; It uses dll.el to handle everything that deals with the
+;;; doubly linked list.
+;;;
+;;; The wrapper data type contains
+;;;      start-marker    Position of the printed representation of the
+;;;                      cookie in the buffer. 
+;;;      cookie          The user-supplied cookie.
+;;;
+;;; The wrapper is not accessible to the user of this package.
+
+;;; Code:
+
+(require 'dll)
+(provide 'cookie)
+
+
+;;; ================================================================
+;;;      Internal   macros   for use in the cookie package
+
+
+(put 'elib-set-buffer-bind-dll 'lisp-indent-hook 1)
+
+(defmacro elib-set-buffer-bind-dll (collection &rest forms)
+
+  ;; Execute FORMS with collection->buffer selected as current buffer,
+  ;; and dll bound to collection->dll.
+  ;; Return value of last form in FORMS.  INTERNAL USE ONLY.
+
+  (let ((old-buffer (make-symbol "old-buffer"))
+	(hnd (make-symbol "collection")))
+    (` (let* (((, old-buffer) (current-buffer))
+	      ((, hnd) (, collection))
+	      (dll (elib-collection->dll (, hnd))))
+	 (set-buffer (elib-collection->buffer (, hnd)))
+	 (unwind-protect
+	     (progn (,@ forms))
+	   (set-buffer (, old-buffer)))))))
+
+
+(put 'elib-set-buffer-bind-dll-let* 'lisp-indent-hook 2)
+
+(defmacro elib-set-buffer-bind-dll-let* (collection varlist &rest forms)
+
+  ;; Execute FORMS with collection->buffer selected as current buffer,
+  ;; dll bound to collection->dll, and VARLIST bound as in a let*.
+  ;; dll will be bound when VARLIST is initialized, but the current
+  ;; buffer will *not* have been changed.
+  ;; Return value of last form in FORMS.  INTERNAL USE ONLY.
+
+  (let ((old-buffer (make-symbol "old-buffer"))
+	(hnd (make-symbol "collection")))
+    (` (let* (((, old-buffer) (current-buffer))
+	      ((, hnd) (, collection))
+	      (dll (elib-collection->dll (, hnd)))
+	      (,@ varlist))
+	 (set-buffer (elib-collection->buffer (, hnd)))
+	 (unwind-protect
+	     (progn (,@ forms))
+	   (set-buffer (, old-buffer)))))))
+
+
+(defmacro elib-filter-hf (collection tin)
+
+  ;; Evaluate TIN once and return it. BUT if it is
+  ;; the header or the footer in COLLECTION return nil instead.
+  ;; Args: COLLECTION TIN
+  ;; INTERNAL USE ONLY.
+
+  (let ((tempvar (make-symbol "tin"))
+	(tmpcoll (make-symbol "tmpcollection")))
+    (` (let (((, tempvar) (, tin))
+	     ((, tmpcoll) (, collection)))
+	 (if (or (eq (, tempvar) (elib-collection->header (, tmpcoll)))
+		 (eq (, tempvar) (elib-collection->footer (, tmpcoll))))
+	     nil
+	   (, tempvar))))))
+
+
+
+;;; ================================================================
+;;;      Internal   data types   for use in the cookie package
+
+;;; Yes, I know about cl.el, but I don't like it.   /ceder
+
+;;; The wrapper data type.
+
+(defun elib-create-wrapper (start-marker cookie)
+  ;; Create a wrapper.   INTERNAL USE ONLY.
+  (cons 'WRAPPER (vector start-marker cookie)))
+
+(defun elib-wrapper->start-marker (wrapper)
+  ;; Get start-marker from wrapper.    INTERNAL USE ONLY.
+  (elt (cdr wrapper) 0))
+
+(defun elib-wrapper->cookie-safe (wrapper)
+  ;; Get cookie from wrapper.   INTERNAL USE ONLY.
+  ;; Returns nil if given nil as input.
+  ;; Since (elt nil 1) returns nil in emacs version 18.57 and 18.58
+  ;; this can be defined in this way. The documentation in the info
+  ;; file says that elt should signal an error in that case. I think
+  ;; it is the documentation that is buggy. (The bug is reported).
+  (elt (cdr wrapper) 1))
+
+(defun elib-wrapper->cookie (wrapper)
+  ;; Get cookie from wrapper.   INTERNAL USE ONLY.
+  (elt (cdr wrapper) 1))
+
+
+
+;;; The collection data type
+
+(defun elib-create-collection (buffer pretty-printer 
+					 header-wrapper footer-wrapper
+					 dll)
+  ;; Create a collection. INTERNAL USE ONLY.
+  (cons 'COLLECTION
+	;; The last element is a pointer to the last tin
+	;; the cursor was at, or nil if that is unknown.  
+	(vector buffer
+		pretty-printer 
+		header-wrapper footer-wrapper
+		dll nil)))
+
+
+(defun elib-collection->buffer (collection)
+  ;; Get buffer from COLLECTION.
+  (elt (cdr collection) 0))
+
+(defun elib-collection->pretty-printer (collection)
+  ;; Get pretty-printer from COLLECTION.
+  (elt (cdr collection) 1))
+
+(defun elib-collection->header (collection)
+  ;; Get header from COLLECTION.
+  (elt (cdr collection) 2))
+
+(defun elib-collection->footer (collection)
+  ;; Get footer from COLLECTION.
+  (elt (cdr collection) 3))
+