1 \input texinfo @c -*-texinfo-*-
3 @comment $Id: elib.texi,v 1.3 2001-12-31 09:36:02 adrian Exp $
4 @comment Documentation for the GNU Emacs lisp library, Elib
5 @comment Copyright (C) 1991, 1992 Free Software Foundation
7 @comment This file is part of the GNU Emacs lisp library, Elib.
9 @comment GNU Elib is free software; you can redistribute it and/or modify
10 @comment it under the terms of the GNU General Public License as published by
11 @comment the Free Software Foundation; either version 2, or (at your option)
12 @comment any later version.
14 @comment GNU Elib is distributed in the hope that it will be useful,
15 @comment but WITHOUT ANY WARRANTY; without even the implied warranty of
16 @comment MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 @comment GNU General Public License for more details.
19 @comment You should have received a copy of the GNU General Public License
20 @comment along with GNU Emacs; see the file COPYING. If not, write to
21 @comment the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
22 @setfilename elib.info
23 @settitle Elib - The Emacs Lisp Library
25 * Elib: (elib). The Emacs Lisp Library.
27 @c footnotestyle separate
30 @setchapternewpage odd
34 Copyright @copyright{} 1991, 1992 Free Software Foundation
37 @comment The titlepage section does not appear in the Info file.
40 @comment The title is printed in a large font.
41 @center @titlefont{User's Guide}
43 @center @titlefont{to}
45 @center @titlefont{Elib - The Emacs Lisp Library}
52 @center last updated 10 dec 1995
55 @comment The following two commands start the copyright page
56 @comment for the printed manual. This will not appear in the Info file.
58 @vskip 0pt plus 1filll
59 Copyright @copyright{} 1991, 1992 Free Software Foundation
61 Permission is granted to make and distribute verbatim copies of this
62 manual provided the copyright notice and this permission notice are
63 preserved on all copies.
65 Permission is granted to copy and distribute modified versions of this
66 manual under the conditions that the section entitled ``GNU ELIB GENERAL
67 PUBLIC LICENSE'' is included exactly as in the original, and provided
68 that the entire resulting derived work is distributed under the terms of
69 a permission notice identical to this one.
71 Permission is granted to copy and distribute translations of this manual
72 into another language under the above conditions for modified versions,
73 except that the section entitled ``GNU ELIB GENERAL PUBLIC LICENSE'' may
74 be included in a translation approved by the author instead of in the
78 @comment ================================================================
79 @comment The real text starts here
80 @comment ================================================================
83 @node Top, License information, (dir), (dir)
84 @comment node-name, next, previous, up
88 This manual describes Elib, the GNU emacs lisp library version 1.0.
90 The functions and data types in Elib are supposed to be a common
91 base for all kinds of other elisp packages and are not programs, modes
92 or packages of their own.
96 * License information:: Information about terms for copying Elib.
97 * What is Elib?:: What is Elib?
98 * Container data types:: Data types which can contain other data.
99 * Cookie package:: The Cookie package.
100 * String functions:: A number of string functions.
101 * Read functions:: Read data from the minibuffer.
103 * Future enhancements:: Future enhancements of Elib.
104 * Reporting bugs:: Where do you report a bug you have found?
106 * Node index:: Index over important all the nodes
110 @node License information, What is Elib?, Top, Top
111 @comment node-name, next, previous, up
114 @node What is Elib?, Container data types, License information, Top
115 @comment node-name, next, previous, up
116 @chapter What is Elib?
117 @cindex What is Elib?
118 @cindex Elib, introduction
119 @cindex Introduction to Elib
122 Elib, the GNU Emacs lisp library, is a collection of elisp
123 functions which you can use as parts of your own elisp programs.
124 Each file contains functions which have something in common, e.g.
125 they handle a certain data type.
127 Elib is designed to be both as efficient and as easy to use as
128 possible. Each file in Elib uses the elisp function @code{provide}
129 to tell emacs when it has been loaded. To use the functions in
130 the file @code{foo}, you just have to put a line such as:
136 into your own elisp file. This will cause emacs to load the file
137 @code{foo.elc} and evaluate the functions in it. This, of course,
138 requires that your system manager has installed Elib properly on your
142 * Contributors:: Contributors to GNU Elib.
143 * Archives:: Where can I get a copy of Elib?
146 @node Contributors, Archives, What is Elib?, What is Elib?
147 @comment node-name, next, previous, up
148 @section Contributors to Elib
152 @cindex Kremer, Sebastian
153 @cindex Sebastian Kremer
154 @cindex Bellman, Thomas
155 @cindex Thomas Bellman
156 @cindex Cederqvist, Per
157 @cindex Per Cederqvist
159 The following persons have made contributions to GNU Elib.
163 Inge Wallin wrote most of the otherwise unattributed functions in
164 Elib as well as all documentation.
167 Sebastian Kremer contributed the string functions.
170 Thomas Bellman wrote some of the code for AVL trees.
173 Per Cederqvist wrote the cookie package and the doubly linked list. The
174 first design of @file{cookie.el} was made by Inge Wallin.
178 @node Archives, , Contributors, What is Elib?
179 @comment node-name, next, previous, up
180 @section Where can I get Elib?
185 @cindex ftp.lysator.liu.se
187 There will probably be a number of sites archiving Elib.
188 Currently the latest release can always be fetched via anonymos
189 ftp from @code{ftp.lysator.liu.se}
193 @node Container data types, Cookie package, What is Elib?, Top
194 @comment node-name, next, previous, up
195 @chapter Container Data Types
196 @cindex Container Data Types
199 Container data types are data types which are used to hold and organize
200 other data. Since lisp is a dynamically typed language, any container
201 data type can hold any other data type or a mix of other data types.
202 This is contrary to the case for @code{C} or @code{C++} where all data in
203 a typical container must be of the same type.
205 As a convention do all names of the functions handling a certain
206 container data type begin in @code{<type>-}, i.e. the functions
207 implementing the container data type @code{foo} all start with
211 * Stack:: The Stack data type.
212 * Queue:: The Queue data type.
213 * Doubly Linked List:: The Doubly Linked List Data Type.
214 * Binary tree:: An ordinary binary tree.
215 * AVL tree:: A balanced binary tree (AVL tree).
218 @node Stack, Queue, Container data types, Container data types
219 @comment node-name, next, previous, up
220 @section The Stack Data Type
226 The stack data type provides a simple LIFO stack. There are two
227 implementations of a stack in Elib, one using macros and one using
228 functions. The names of the functions/macros in the two implementations
229 are the same, but the efficiency of using one or the other vary greatly
230 under different circumstances.
232 The implementation using macros should be used when you want to
233 byte-compile your own elisp program. This will be most efficient since
234 byte-compiling an elisp function using macros has the same effect as
235 using inline code in @code{C}.
237 To use the stack data type, put the line
243 in your own elisp source file if you want to use the implementation
250 if you want to use the implementation using macros. This is the only
251 difference between them, so it is easy to switch between them during
254 The following functions are provided by the stack:
259 Create a new empty stack.
261 @item (stack-p stack)
263 Return @code{t} if @var{stack} is a stack, otherwise return @code{nil}.
265 @item (stack-push stack element)
267 Push @var{element} onto @var{stack}.
269 @item (stack-pop stack)
271 Remove the topmost element from @var{stack} and return it. If
272 @var{stack} is empty, return @code{nil}.
274 @item (stack-empty stack)
276 Return @code{t} if @var{stack} is empty, otherwise return @code{nil}.
278 @item (stack-top stack)
280 Return the top element of @var{stack}, but don't remove it from the stack.
281 Return @code{nil} if @var{stack} is empty.
283 @item (stack-nth stack n)
285 Return the @var{n}th element of @var{stack} where the top stack element
286 has number 0. If @var{stack} is not that long, return @code{nil}. The
287 element is not removed from the stack.
289 @item (stack-all stack)
291 Return a list of all entries in @var{stack} with the topmost element first.
293 @item (stack-copy stack)
295 Return a copy of @var{stack}. All entries in @var{stack} are also copied.
297 @item (stack-length stack)
299 Return the number of elements in @var{stack}.
301 @item (stack-clear stack)
303 Remove all elements from @var{stack}.
308 @node Queue, Doubly Linked List, Stack, Container data types
309 @comment node-name, next, previous, up
310 @section The Queue Data Type
316 The queue data type provides a simple FIFO queue. There are two
317 implementations of a queue in Elib, one using macros and one using
318 functions. The names of the functions/macros in the two implementations
319 are the same, but the efficiency of using one or the other vary greatly
320 under different circumstances.
322 The implementation using macros should be used when you want to
323 byte-compile your own elisp program. This will be most efficient since
324 byte-compiling an elisp function using macros has the same effect as
325 using inline code in @code{C}.
327 To use the queue data type, put the line
333 in your own elisp source file if you want to use the implementation
340 if you want to use the implementation using macros. This is the only
341 difference between them, so it is easy to switch between them during
344 Not all functions in @file{queue-m.el} are implemented as macros,
345 only the short ones. This does not make it less recommendable to use
346 the macro version in your compiled code.
348 The following functions are provided by the queue:
353 Create a new empty queue.
355 @item (queue-p queue)
357 Return @code{t} if @var{queue} is a queue, otherwise return @code{nil}.
359 @item (queue-enqueue queue element)
360 @findex queue-enqueue
361 Enter @var{element} last into @var{queue}.
363 @item (queue-dequeue queue)
364 @findex queue-dequeue
365 Remove the first element from @var{queue} and return it.
367 @item (queue-empty queue)
369 Return @code{t} if @var{queue} is empty, otherwise return @code{nil}.
371 @item (queue-first queue)
373 Return the first element of @var{queue} or @code{nil} if it is empty. The
374 element is not removed from the queue.
376 @item (queue-nth queue n)
378 Return the @var{n}th element of @var{queue}, where the first element of
379 @var{queue} has number 0. If the length of @var{queue} is less than
380 @var{n}, return @code{nil}. The element is not removed from the queue.
382 @item (queue-last queue)
384 Return the last element of @var{queue} or @code{nil} if it is empty. The
385 element is not removed from the queue.
387 @item (queue-all queue)
389 Return a list of all elements in @var{queue}. Return @code{nil} if
390 @var{queue} is empty. The oldest element in the queue is the first in
393 @item (queue-copy queue)
395 Return a copy of @var{queue}. All entries in @var{queue} are also copied.
397 @item (queue-length queue)
399 Return the number of elements in @var{queue}.
401 @item (queue-clear queue)
403 Remove all elements from @var{queue}.
407 @node Doubly Linked List, Binary tree, Queue, Container data types
408 @comment node-name, next, previous, up
409 @section The Doubly Linked List Data Type
410 @cindex Doubly linked list
411 @cindex List, doubly linked
414 The doubly linked list is an efficient data structure if you need to
415 traverse the elements on the list in two directions, and maybe insert
416 new elements in the middle of the list. You can efficiently delete any
417 element, and insert new elements, anywhere on the list.
419 A doubly linked list (@dfn{dll} for short) consists of a number of
420 @dfn{nodes}, each containing exactly one @dfn{element}. Some of the
421 functions operate directly on the elements, while some manipulate nodes.
422 For instance, all of the functions that let you step forward and
423 backwards in the list handle nodes. Use the function @dfn{dll-element}
424 to extract the element of a node.
426 To use the doubly linked list provided by Elib you must put the line
432 in your elisp source file.
435 * Creating a dll:: Creating a Doubly Linked List
436 * Entering elements:: Entering elements in a dll
437 * Accessing elements:: Accessing elements of a dll
438 * Removing nodes:: Removing nodes from a dll
439 * Predicates:: Predicates on a dll
440 * Maps and Filters:: Maps and Filters on a dll
441 * Misc dll operations:: Miscellaneous dll operations
442 * Debugging dll applications:: Debugging dll applications
445 @node Creating a dll, Entering elements, Doubly Linked List, Doubly Linked List
446 @comment node-name, next, previous, up
447 @subsection Creating a Doubly Linked List
452 Create an empty doubly linked list.
454 @item (dll-create-from-list list)
455 @findex dll-create-from-list
456 Given the ordinary lisp list @var{list}, create a doubly linked list
457 with the same elements.
459 @item (dll-copy dll &optional element-copy-fnc)
461 Return a copy of the doubly linked list @var{dll}. If optional second
462 argument @var{element-copy-fnc} is non-@code{nil} it should be a
463 function that takes one argument, an element, and returns a copy of it.
464 If @var{element-copy-fnc} is not given the elements themselves are not
468 @node Entering elements, Accessing elements, Creating a dll, Doubly Linked List
469 @comment node-name, next, previous, up
470 @subsection Entering elements in a dll
473 @item (dll-enter-first dll element)
474 @findex dll-enter-first
475 Add an element first on a doubly linked list.
477 @item (dll-enter-last dll element)
478 @findex dll-enter-last
479 Add an element last on a doubly linked list.
481 @item (dll-enter-after dll node element)
482 @findex dll-enter-after
483 In the doubly linked list @var{dll}, insert a node containing
484 @var{element} after @var{node}.
486 @item (dll-enter-before dll node element)
487 @findex dll-enter-before
488 In the doubly linked list @var{dll}, insert a node containing
489 @var{element} before @var{node}.
492 @node Accessing elements, Removing nodes, Entering elements, Doubly Linked List
493 @comment node-name, next, previous, up
494 @subsection Accessing elements of a dll
497 @item (dll-element dll node)
499 Get the element of a @var{node} in a doubly linked list @var{dll}.
501 @item (dll-first dll)
503 Return the first element on the doubly linked list @var{dll}. Return
504 @code{nil} if the list is empty. The element is not removed.
506 @item (dll-nth dll n)
508 Return the @var{n}th node from the doubly linked list @var{dll}.
509 @var{n} counts from zero. If @var{dll} is not that long, @code{nil} is
510 returned. If @var{n} is negative, return the -(@var{n}+1)th last
511 element. Thus, @code{(dll-nth dll 0)} returns the first node, and
512 @code{(dll-nth dll -1)} returns the last node.
516 Return the last element on the doubly linked list @var{dll}. Return
517 @code{nil} if the list is empty. The element is not removed.
519 @item (dll-next dll node)
521 Return the last element on the doubly linked list @var{dll}. Return
522 @code{nil} if the list is empty. The element is not removed.
524 @item (dll-previous dll node)
526 Return the node before @var{node}, or @code{nil} if @var{node} is the
531 Return all elements on the double linked list @var{dll} as an ordinary list.
535 @node Removing nodes, Predicates, Accessing elements, Doubly Linked List
536 @comment node-name, next, previous, up
537 @subsection Removing nodes from a dll
540 @item (dll-delete dll node)
542 Delete @var{node} from the doubly linked list @var{dll}. Return the
543 element of @var{node}.
545 @item (dll-delete-first dll)
546 @findex dll-delete-first
547 Delete the first @var{node} from the doubly linked list @var{dll}.
548 Return the element. Returns @code{nil} if @var{dll} was empty.
550 @item (dll-delete-last dll)
551 @findex dll-delete-last
552 Delete the last @var{node} from the doubly linked list @var{dll}.
553 Return the element. Returns @code{nil} if @var{dll} was empty.
555 @item (dll-clear dll)
557 Clear the doubly linked list @var{dll}, i.e. make it completely empty.
560 @node Predicates, Maps and Filters, Removing nodes, Doubly Linked List
561 @comment node-name, next, previous, up
562 @subsection Predicates on a dll
567 Return @code{t} if @var{object} is a doubly linked list, otherwise return
570 @item (dll-empty dll)
572 Return @code{t} if the doubly linked list @var{dll} is empty, @code{nil}
576 @node Maps and Filters, Misc dll operations, Predicates, Doubly Linked List
577 @comment node-name, next, previous, up
578 @subsection Maps and Filters on a dll
581 @item (dll-map map-function dll)
583 Apply @var{map-function} to all elements in the doubly linked list @var{dll}.
584 The function is applied to the first element first.
586 @item (dll-map-reverse map-function dll)
587 @findex dll-map-reverse
588 Apply @var{map-function} to all elements in the doubly linked list
589 @var{dll}. The function is applied to the last element first.
591 @item (dll-filter dll predicate)
593 Remove all elements in the doubly linked list @var{dll} for which
594 @var{predicate} returns @code{nil}.
597 @node Misc dll operations, Debugging dll applications, Maps and Filters, Doubly Linked List
598 @comment node-name, next, previous, up
599 @subsection Miscellaneous dll operations
602 @item (dll-length dll)
604 Returns the number of elements in the doubly linked list @var{dll}.
606 @item (dll-sort dll predicate)
608 Sort the doubly linked list @var{dll}, stably, comparing elements using
609 @var{predicate}. Returns the sorted list. @var{dll} is modified by side
610 effects. @var{predicate} is called with two elements of @var{dll}, and
611 should return @code{t} if the first element is ``less'' than the second.
614 @node Debugging dll applications, , Misc dll operations, Doubly Linked List
615 @comment node-name, next, previous, up
616 @subsection Debugging dll applications
617 @cindex Debugging dll
618 @cindex Doubly linked lists, debugging
620 @cindex Circular lists
621 @cindex Error: circular lists
623 The data structure used by the dll package contains both forward and
624 backward pointers. The primitives in Emacs, such as @code{print}, know
625 nothing about dlls, so when Emacs tries to print out a dll it will think
626 that it found a circular structure. Fortunately it detects this
627 situation and gives an error message, instead of getting stuck in an
630 The error message can be quite annoying when you are developing an
631 application that uses dlls. Suppose your code has an error, and you
632 type @samp{(setq debug-on-error t)} to try to figure out exactly what
633 the error is. If any function in the backtrace has a dll as an
634 argument, Emacs will abort printing the entire backtrace and only
635 respond with a "Back at top level" message (or something similar,
636 depending on exactly what you are doing) in the echo area.
638 There are two solutions to this problem: patch your emacs so that it
639 detects circular structures (there have been patches for this floating
640 around the net) or use @file{dll-debug.el}.
642 The file @file{dll-debug.el} implements all of the functionality that
643 are present in @file{dll.el}, but it uses a normal, singly linked list
644 instead. This makes some operations, like @samp{dll-previous},
645 dreadfully slow, but it makes it possible to debug dll applications.
646 @file{dll-debug.el} also has more built-in sanity tests than
649 @strong{NOTE:} To use the debug package, you must load the library
650 @file{dll-debug} before you load any of the libraries (such as cookie)
651 or your program that use dll. You must also make sure that you don't
652 load any byte-compiled version of any file that was compiled with the
653 normal dll library. Since it contains some macros very strange results
654 will occur otherwise...
656 When the debug package is loaded, you simply run your code normally,
657 and any bugs should be easier to trace.
659 @node Binary tree, AVL tree, Doubly Linked List, Container data types
660 @comment node-name, next, previous, up
661 @section The Binary Tree Data Type
665 The binary tree is sometimes an efficient way to store data. When a
666 binary tree is created a compare function is given to the create
667 function (@code{bintree-create}). This function is used throughout
668 all data entry and deletions into and out of the tree.
670 To use the binary tree in Elib you must put the line
676 in your elisp source file.
678 The following functions are provided by the binary tree in the library:
681 @item (bintree-create compare-function)
682 @findex bintree-create
683 Create a new empty binary tree. The argument @var{compare-function} is a
684 function which compares two instances of the data type which is to be
685 entered into the tree. The call @code{(compare-function data1 data2)}
686 should return non-@code{nil} if @code{data1} is less than @code{data2},
687 and @code{nil} otherwise.
689 @item (bintree-p tree)
691 Return @code{t} if @var{tree} is an bintree, otherwise return @code{nil}.
693 @item (bintree-compare-function tree)
694 @findex bintree-compare-function
695 Return @code{compare-function} given to @code{bintree-create} when
696 @var{tree} was created.
698 @item (bintree-empty tree)
699 @findex bintree-empty
700 Return @code{t} if @var{tree} is empty, otherwise return @code{nil}.
702 @item (bintree-enter tree data)
703 @findex bintree-enter
704 Enter @var{data} into @var{tree}. If there already is a data element
705 which is considered equal to @var{data} by @code{compare-function} given
706 to @code{bintree-create}, the new element will replace the old one in
709 @item (bintree-delete tree data)
710 @findex bintree-delete
711 Delete the element which is considered equal to @var{data} by
712 @code{compare-function} given to @code{bintree-create}. If there
713 is no matching element within the tree, nothing is done to the tree.
715 @item (bintree-member tree data)
716 @findex bintree-member
717 Return the element in @var{tree} which is considered equal to @var{data} by
718 @code{compare-function} given to @code{bintree-create}. If there
719 is no such element in the tree, return @code{nil}.
721 @item (bintree-map map-function tree)
723 Apply @var{map-function} to all elements in @var{tree}. The function is applied in
724 the order in which the tree is sorted.
726 @item (bintree-first tree)
727 @findex bintree-first
728 Return the first element of @var{tree}, i.e. the one who is considered first
729 by @code{compare-function} given to @code{bintree-create}. If the
730 tree is empty, return @code{nil}.
732 @item (bintree-last tree)
734 Return the last element of @var{tree}, i.e. the one who is considered last
735 by @code{compare-function} given to @code{bintree-create}. If the
736 tree is empty, return @code{nil}.
738 @item (bintree-copy tree)
740 Return a copy of @var{tree}.
742 @item (bintree-flatten tree)
743 @findex bintree-flatten
744 Return a sorted list containing all elements of @var{tree}.
746 @item (bintree-size tree)
748 Return the number of elements in @var{tree}.
750 @item (bintree-clear tree)
751 @findex bintree-clear
752 Clear @var{tree}, i.e. make it totally empty.
757 @node AVL tree, , Binary tree, Container data types
758 @comment node-name, next, previous, up
759 @section The AVL Tree Data Type
761 @cindex Balanced binary tree
762 @cindex Binary tree, balanced
765 The AVL tree data types provides a balanced binary tree. The tree will
766 remain balanced throughout its entire life time, regardless of in which
767 order elements are entered into or deleted from the tree.
769 Although an AVL tree is not perfectly balanced, it has almost the same
770 performance as if it was. The definition of an AVL tree is that the
771 difference in depth of the two branches of a particular node is at most
772 1. This criterium is enough to make the performance of searching in an
773 AVL tree very close to a perfectly balanced tree, but will simplify the
774 entering and deleting of data significantly.
776 All data that is entered into an AVL tree should be of the same type.
777 If they are not, there are no way to compare two elements and this is
778 essential for entering and deleting data from the tree. When a tree is
779 created, a compare function is given to the create function. This
780 function is used throughout the life of the tree in all subsequent
781 insertions and deletions.
783 To use the Elib AVL tree, you must put the line
789 in your elisp source file.
791 The following functions are provided by the AVL tree in the library:
794 @item (avltree-create compare-function)
795 @findex avltree-create
796 Create a new empty AVL tree. The argument @var{compare-function} is a
797 function which compares two instances of the data type which is to be
798 entered into the tree. The call @code{(compare-function data1 data2)}
799 should return non-@code{nil} if @code{data1} is less than @code{data2},
800 and @code{nil} otherwise.
802 @item (avltree-p tree)
804 Return @code{t} if @var{tree} is an avltree, otherwise return @code{nil}.
806 @item (avltree-compare-function tree)
807 @findex avltree-compare-function
808 Return @code{compare-function} given to @code{avltree-create} when
809 @var{tree} was created.
811 @item (avltree-empty tree)
812 @findex avltree-empty
813 Return @code{t} if @var{tree} is empty, otherwise return @code{nil}.
815 @item (avltree-enter tree data)
816 @findex avltree-enter
817 Enter @var{data} into @var{tree}. If there already is a data element
818 which is considered equal to @var{data} by @code{compare-function} given to
819 @code{avltree-create}, the new element will replace the old one in the
822 @item (avltree-delete tree data)
823 @findex avltree-delete
824 Delete the element which is considered equal to @var{data} by
825 @code{compare-function} given to @code{avltree-create}. If there
826 is no matching element within the tree, nothing is done to the tree.
828 @item (avltree-member tree data)
829 @findex avltree-member
830 Return the element in @var{tree} which is considered equal to @var{data} by
831 @code{compare-function} given to @code{avltree-create}. If there
832 is no such element in the tree, return @code{nil}.
834 @item (avltree-map map-function tree)
836 Apply @var{map-function} to all elements in @var{tree}. The function is
837 applied in the order in which the tree is sorted.
839 @item (avltree-first tree)
840 @findex avltree-first
841 Return the first element of @var{tree}, i.e. the one who is considered first
842 by @code{compare-function} given to @code{avltree-create}. If the
843 tree is empty, return @code{nil}.
845 @item (avltree-last tree)
847 Return the last element of @var{tree}, i.e. the one who is considered last
848 by @code{compare-function} given to @code{avltree-create}. If the
849 tree is empty, return @code{nil}.
851 @item (avltree-copy tree)
853 Return a copy of @var{tree}.
855 @item (avltree-flatten tree)
856 @findex avltree-flatten
857 Return a sorted list containing all elements of @var{tree}.
859 @item (avltree-size tree)
861 Return the number of elements in @var{tree}.
863 @item (avltree-clear tree)
864 @findex avltree-clear
865 Clear @var{tree}, i.e. make it totally empty.
869 @node Cookie package, String functions, Container data types, Top
870 @comment node-name, next, previous, up
871 @chapter The Cookie package---nodal data in a buffer
875 If you want to have structured nodal data in a buffer, the cookie
876 package can be a help to you.
878 Cookie is a package that implements a connection between a
879 dll (a doubly linked list) and the contents of a buffer.
880 Possible uses are @code{dired} (have all files in a list, and show them),
881 @code{buffer-list}, @code{kom-prioritize} (in the LysKOM elisp client) and
882 others. The CVS control package @file{pcl-cvs.el} uses @file{cookie.el}.
885 * Cookie terminology:: Introduction to cookies.
886 * Cookie conventions:: Coding conventions used in the cookie package.
887 * Collection:: Manipulating the entire collection.
888 * Inserting cookies:: Inserting cookies in the collection.
889 * Tins and cookies:: Tins and cookies.
890 * Deleting cookies:: Deleting cookies.
891 * Collection as a DLL:: Treating the collection as a
893 * Scanning the list:: Scanning the list.
894 * In the buffer:: Operations that affect the buffer.
895 * Debugging cookie applications:: Debugging cookie applications
898 @node Cookie terminology, Cookie conventions, Cookie package, Cookie package
899 @comment node-name, next, previous, up
900 @section Introduction to cookie terminology
901 @cindex Cookie definitions
905 The cookie package uses its own terminology. Here are some important
910 A @dfn{cookie} can be any lisp object. When you use the cookie
911 package you specify a pretty-printer, a function that inserts
912 a printable representation of the cookie in the buffer.
916 A @dfn{collection} consists of a doubly linked list of
917 cookies, a header, a footer and a pretty-printer. It is
918 displayed at a certain point in a certain buffer. (The
919 buffer and point are selected when the collection is
920 created). The header and the footer are constant strings.
921 They appear before and after the cookies. (Currently,
922 once set, they can not be changed).
925 A @dfn{tin} is an object that contains one cookie. There
926 are functions in this package that given a tin extracts
927 the cookie, or gives the next or previous tin. (All tins
928 are linked together in a doubly linked list. The
929 previous tin is the one that appears before the other in
930 the buffer.) You should not do anything with a tin except
931 pass it to the functions in this package.
935 Cookie does not affect the mode of the buffer in any way.
936 It merely makes it easy to connect an underlying data
937 representation to the buffer contents.
939 A collection is a very dynamic thing. You can easily add or
940 delete cookies. You can sort all cookies in a collection (you
941 have to supply a function that compares two cookies). You can
942 apply a function to all cookies in a collection, etc, etc.
944 Remember that a cookie can be anything. Your imagination is the
945 limit! It is even possible to have another collection as a
946 cookie. In that way some kind of tree hierarchy can be created.
948 @node Cookie conventions, Collection, Cookie terminology, Cookie package
949 @comment node-name, next, previous, up
950 @section Coding conventions used in the cookie package
951 @cindex Cookie conventions
954 All functions that are intended for external use begin
955 with one of the prefixes @samp{cookie-},
956 @samp{collection-} or @samp{tin-}. The prefix
957 @samp{elib-} is used for internal functions
958 and macros. Currently, no global or buffer-local
961 Many functions operate on tins instead of cookies. For
962 most functions, the prefix used should help tell which
963 kind of object the function uses.
965 Most doc-strings contains an "Args:" line that lists the
968 @node Collection, Inserting cookies, Cookie conventions, Cookie package
969 @comment node-name, next, previous, up
970 @section Manipulating the entire collection
973 @item (collection-create buffer pretty-printer &optional header footer pos)
974 @findex collection-create
975 Create a collection that is displayed in @var{buffer}.
976 @var{buffer} may be a buffer or a buffer name. It is created if
979 @var{pretty-printer} should be a function that takes one
980 argument, a cookie, and inserts a string representing it
981 in the buffer (at point). The string @var{pretty-printer}
982 inserts may be empty or span several lines. A trailing
983 newline will always be inserted automatically. The
984 @var{pretty-printer} should use @code{insert}, and not
985 @code{insert-before-markers}.
987 Optional third argument @var{header} is a string that will
988 always be present at the top of the collection.
989 @var{header} should end with a newline. Optional fourth
990 argument @var{footer} is similar, and will always be
991 inserted at the bottom of the collection.
993 Optional fifth argument @var{pos} is a buffer position,
994 specifying where the collection will be inserted. It
995 defaults to the beginning of the buffer. @var{pos} will probably default
996 to the current value of @code{(point)} in future releases of Elib, so
997 you should not depend on this default in cases where it matters.
999 @item (collection-empty collection)
1000 @findex collection-empty
1001 Return true if there are no cookies in @var{collection}.
1003 @item (collection-length collection)
1004 @findex collection-length
1005 Return the number of cookies in @var{collection}.
1007 @item (collection-list-cookies collection)
1008 @findex collection-list-cookies
1009 Return a list of all cookies in @var{collection}.
1012 @node Inserting cookies, Tins and cookies, Collection, Cookie package
1013 @comment node-name, next, previous, up
1014 @section Inserting cookies in the collection
1016 These functions can be used to insert one or more cookies
1017 into a collection. The printed representation will
1018 immediately and automatically be updated by the cookie
1019 package. (It will call the pretty-printer that was
1020 specified to @code{collection-create}).
1023 @item (cookie-enter-first collection cookie)
1024 @findex cookie-enter-first
1025 Enter @var{cookie} first in the cookie collection @var{collection}.
1027 @item (cookie-enter-last collection cookie)
1028 @findex cookie-enter-last
1029 Enter @var{cookie} last in the cookie collection @var{collection}.
1031 @item (cookie-enter-after-tin collection tin cookie)
1032 @findex cookie-enter-after-tin
1033 Enter @var{cookie} into @var{collection}, immediately
1036 @item (cookie-enter-before-tin collection tin cookie)
1037 @findex cookie-enter-before-tin
1038 Enter @var{cookie} into @var{collection}, immediately
1041 @item (collection-append-cookies (collection cookie-list))
1042 @findex collection-append-cookies
1043 Insert all cookies in the list @var{cookie-list} last in
1047 @node Tins and cookies, Deleting cookies, Inserting cookies, Cookie package
1048 @comment node-name, next, previous, up
1049 @section Tins and cookies
1052 @item (tin-cookie collection tin)
1054 This function can be used to extract a cookie from
1055 @var{tin}. The collection that @var{tin} is present in
1056 must also be specified as @var{collection}.
1059 @node Deleting cookies, Collection as a DLL, Tins and cookies, Cookie package
1060 @comment node-name, next, previous, up
1061 @section Deleting cookies
1063 There are a couple of different ways to delete cookies
1064 from the collection.
1067 @item (tin-delete collection tin)
1069 Delete @var{tin} from @var{collection}. The cookie that is
1070 stored in @var{tin} is returned.
1072 @item (cookie-delete-first collection)
1073 @findex cookie-delete-first
1074 Delete first cookie in @var{collection} and return it.
1075 Returns @code{nil} if there are no cookies left in
1078 @item (cookie-delete-last collection)
1079 @findex cookie-delete-last
1080 Delete last cookie in @var{collection} and return it.
1081 Returns @code{nil} if there are no cookies left in
1085 The following two functions can be used to delete several
1086 cookies that fulfills certain criteria.
1089 @item (collection-filter-cookies collection predicate &rest extra-args)
1090 @findex collection-filter-cookies
1091 Remove all cookies in @var{collection} for which
1092 @var{predicate} returns nil. Note that the buffer for
1093 @var{collection} will be current-buffer when
1094 @var{predicate} is called. @var{predicate} must restore
1095 the current buffer before it returns if it changes it.
1097 The @var{predicate} is called with @var{cookie} as its
1098 first argument. If any @var{extra-args} are given to
1099 @code{collection-filter-cookies} they will be passed
1100 unmodified to @var{predicate}.
1102 @item (collection-filter-tins collection predicate &rest extra-args)
1103 @findex collection-filter-tins
1104 This is like @code{collection-filter-cookies}, but
1105 @var{predicate} is called with a tin instead of a cookie.
1108 And finally, a way to delete all cookies in one swift
1112 @item (collection-clear collection)
1113 @findex collection-clear
1114 Remove all cookies in @var{collection}.
1117 @node Collection as a DLL, Scanning the list, Deleting cookies, Cookie package
1118 @comment node-name, next, previous, up
1119 @section Collection as a Doubly linked list
1121 The functions in this section treat the collection as a
1125 @item (tin-nth collection n)
1127 Return the @var{n}th tin. @var{n} counts from zero.
1128 @code{nil} is returned if there is less than @var{n}
1129 cookies. If @var{n} is negative, return the
1130 -(@var{n}+1)th last element. Thus, @code{(tin-nth dll 0)}
1131 returns the first node, and @code{(tin-nth dll -1)}
1132 returns the last node.
1134 Use @code{tin-cookie} to extract the cookie from the tin (or use
1135 @code{cookie-nth} instead).
1137 @item (cookie-nth collection n)
1139 Like @code{tin-nth}, but the cookie is returned instead of
1142 @item (tin-next collection tin)
1144 Get the next tin. Returns nil if @var{tin} is @code{nil}
1145 or refers to the last cookie in @var{collection}.
1147 @item (tin-previous collection tin)
1148 @findex tin-previous
1149 Get the previous tin. Returns nil if @var{tin} is
1150 @code{nil} or refers to the first cookie in
1153 @item (cookie-sort collection predicate)
1155 Sort the cookies in @var{collection}, stably, comparing
1156 elements using @var{predicate}. @var{predicate} is called
1157 with two cookies, and should return @samp{t} if the first
1158 cookie is @dfn{less} than the second.
1160 The screen representaion of the collection will refreshed after the sort
1163 @item (cookie-first collection)
1164 @findex cookie-first
1165 Return the first cookie in @var{collection}. The cookie is
1168 @item (cookie-last collection)
1170 Return the last cookie in @var{collection}. The cookie is
1174 @node Scanning the list, In the buffer, Collection as a DLL, Cookie package
1175 @comment node-name, next, previous, up
1176 @section Scanning the list
1179 @item (cookie-map map-function collection &rest map-args)
1181 Apply @var{map-function} to all cookies in
1182 @var{collection}. @var{map-function} is applied to the
1183 first element first. If @var{map-function} returns
1184 non-@code{nil} the cookie will be refreshed (its
1185 pretty-printer will be called once again).
1187 Note that the buffer for @var{collection} will be current
1188 buffer when @var{map-function} is called.
1189 @var{map-function} must restore the current buffer to
1190 @var{buffer} before it returns, if it changes it.
1192 If more than two arguments are given to @code{cookie-map}, remaining
1193 arguments will be passed to @var{map-function}.
1195 @item (cookie-map-reverse map-function collection &rest map-args)
1196 @findex cookie-map-reverse
1197 Like @code{cookie-map}, but @var{map-function} will be
1198 applied to the last cookie first.
1200 @item (collection-collect-tin collection predicate &rest predicate-args)
1201 @findex collection-collect-tin
1202 Select cookies from @var{collection} using @var{predicate}.
1203 Return a list of all selected tins.
1205 @var{predicate} is a function that takes a cookie as its
1208 The tins on the returned list will appear in the same
1209 order as in the buffer. You should not rely on in which
1210 order @var{predicate} is called.
1212 Note that the buffer the @var{collection} is displayed in
1213 is current-buffer when @var{predicate} is called.
1214 @var{predicate} must restore current-buffer if it changes
1217 If more than two arguments are given to
1218 @code{collection-collect-tin} the remaining arguments will
1219 be passed to @var{predicate}.
1221 @item (collection-collect-cookie collection predicate &rest predicate-args)
1222 @findex collection-collect-cookie
1223 Like @code{collection-collect-tin}, but a list of cookies
1227 @node In the buffer, Debugging cookie applications, Scanning the list, Cookie package
1228 @comment node-name, next, previous, up
1229 @section Operations that affect the buffer
1232 @item (collection-buffer collection)
1233 @findex collection-buffer
1234 Return the buffer that @var{collection} is displayed in.
1236 @item (collection-refresh collection)
1237 @findex collection-refresh
1238 Refresh all cookies in @var{collection}.
1240 The pretty-printer that was specified when the
1241 @var{collection} was created will be called for all
1242 cookies in @var{collection}.
1244 Note that @code{tin-invalidate} is more efficient if only
1245 a small number of cookies needs to be refreshed.
1247 @item (tin-invalidate collection &rest tins)
1248 @findex tin-invalidate
1249 Refresh some cookies. The pretty-printer for
1250 @var{collection} will be called for all @var{tins}.
1252 @item (collection-set-goal-column collection goal)
1253 @findex collection-set-goal-column
1254 Set goal-column for @var{collection}. goal-column is made buffer-local.
1255 This function will be obsoleted in the next release of Elib. Instead,
1256 there is going to be a function that given a cookie will return a
1257 position where the cursor should be stored. The details are not yet
1260 @item (tin-goto-previous collection pos arg)
1261 @findex tin-goto-previous
1262 Move point to the @var{arg}th previous cookie. Don't move if we are at
1263 the first cookie, or if @var{collection} is empty. Returns the tin we
1266 @item (tin-goto-next collection pos arg)
1267 @findex tin-goto-next
1268 Like @code{tin-goto-previous}, but move towards the end of
1271 @item (tin-goto collection tin)
1273 Move point to @var{tin}.
1275 @item (tin-locate collection pos &optional guess)
1277 Return the tin that @var{pos} (a buffer position) is within.
1279 @var{pos} may be a marker or an integer. @var{guess}
1280 should be a tin that it is likely that @var{pos} is near.
1282 If @var{pos} points before the first cookie, the first
1283 cookie is returned. If @var{pos} points after the last
1284 cookie, the last cookie is returned. If @var{collection}
1285 is empty, @code{nil} is returned.
1288 @node Debugging cookie applications, , In the buffer, Cookie package
1289 @comment node-name, next, previous, up
1290 @section Debugging cookie applications
1292 Since the cookie package uses dll, cookie applications can be hard to
1293 debug. Fortunately, the same technique can be used here---just load
1294 dll-debug prior to loading cookie. @xref{Debugging dll applications}.
1296 @emph{Warning!} Don't load a byte-compiled @file{cookie.elc} that was
1297 compiled using dll (as opposed to dll-debug) when you have dll-debug in
1298 memory. Your Emacs will be seriously confused.
1300 @node String functions, Read functions, Cookie package, Top
1301 @comment node-name, next, previous, up
1302 @chapter String functions
1303 @cindex String functions
1306 To use the string functions in Elib you have to put the following line
1307 into your elisp source file:
1313 The following string functions are provided with Elib.
1316 @item (string-replace-match regexp string newtext &optional literal global)
1317 @findex string-replace-match
1319 This function tries to be a string near-equivalent to the elisp function
1320 @code{replace-match}. It returns a string with the first text matched
1321 by @var{regexp} in @var{string} replaced by @var{newtext}. If no match
1322 is found, @code{nil} is returned. If optional argument @var{global} is
1323 non-@code{nil}, all occurances matching @var{regexp} are replaced
1324 instead of only the first one.
1326 If optional argument @var{literal} is non-@code{nil}, then @var{newtext}
1327 is inserted exactly as it is. If it is @code{nil} (which is the
1328 default), then the character @kbd{\} is treated specially. If a @kbd{\}
1329 appears in @var{newtext}, it can start any one of the following sequences:
1333 @kbd{\&} stands for the entire text being replaced.
1336 @kbd{\@var{n}} stands for the @var{n}th subexpression in the original regexp.
1337 Subexpressions are those expressions grouped inside of @code{\(...\)}.
1341 @kbd{\\} stands for a single @kbd{\} in @var{newtext}.
1344 Any other character after the @key{\} will just be copied into the
1347 @item (string-split pattern string &optional limit)
1349 Split the string @var{string} on the regexp @var{pattern} and return a
1350 list of the strings between the matches. If the optional numerical
1351 argument @var{limit} is >= 1, only the first @var{limit} elements of the list are
1354 For example, the call
1357 (string-split "[ \t]+" "Elisp programming is fun.")
1360 will return @code{("Elisp" "programming" "is" "fun.")}, but the call
1363 (string-split " " "Elisp programming is fun." 3)
1366 will return @code{("Elisp" "programming" "is")}.
1370 @node Read functions, Future enhancements, String functions, Top
1371 @comment node-name, next, previous, up
1372 @chapter Read functions
1373 @cindex Read functions
1376 Elib provides a number of functions for reading data from the
1377 minibuffer. To use them in your own elisp programs, put the following
1378 line into you source file:
1384 The following functions are provided by @file{read}.
1387 @item (read-number &optional prompt default)
1389 Read a number from the minibuffer. If optional argument @var{prompt} is
1390 non-@code{nil}, the user is prompted using @var{prompt}, otherwise the
1391 prompt string @code{Enter a number:} is used. If optional argument
1392 @var{default} is non-@code{nil}, it is written within parenthesis after
1393 the prompt string. @var{default} can be either a number or of the type which
1394 @code{(interactive "P")} generates.
1396 @item (read-num-range low high &optional prompt show-range)
1397 @findex read-num-range
1398 Read a number from the minibuffer. The number returned will be forced
1399 to lie between @var{low} and @var{high}. If @var{prompt} is
1400 non-@code{nil}, the user is prompted using @var{prompt}, otherwise the
1401 prompt string @code{Enter a number:} is used. If @var{show-range} is
1402 non-@code{nil}, the prompt will show the range within parenthesis to the
1405 @item (read-silent prompt &optional showchar)
1407 Read a string in the minibuffer without echoing. The following
1408 characters are special when entering the string:
1412 Delete the last character in the input buffer.
1415 Clear the input buffer.
1418 End the reading of the string.
1425 If optional argument @var{showchar} is non-@code{nil}, one of these characters
1426 will be displayed for each character input by the user.
1428 This function is well suited to read a password from the user, but
1429 beware of the function @code{(view-lossage)} which displays the last 100
1430 keystrokes, even hidden ones.
1435 @node Future enhancements, Reporting bugs, Read functions, Top
1436 @comment node-name, next, previous, up
1437 @chapter Future enhancements
1438 @cindex Enhancements
1440 Elib needs a number of enhancements to be
1441 called complete. Here is a list of wishes of functions and data
1442 types which we would like to enter into Elib in future releases:
1446 More container data types such as Priority queues, 2-3-trees, Hash
1447 tables, Sets, etc. Much inspiration can be gotten from libg++ and the
1448 standard C++ library, STL.
1451 Other implementations of old container data types. For instance, are
1452 vector implementations of stacks and queues faster than the current ones
1456 Miscellaneous other small functions.
1459 More tests for all code in the library, especially the untested
1460 container data types. See the TODO file.
1464 @section Contributions
1466 We are grateful for all donations of code that we can receive. However,
1467 your code will be still more useful if you also provide documentation
1468 and code to test your new library functions.
1471 @node Reporting bugs, Node index, Future enhancements, Top
1472 @comment node-name, next, previous, up
1473 @chapter Reporting bugs
1474 @cindex Reporting bugs
1476 Undoubtedly there are numerous bugs remaining, both in the elisp source
1477 code and in the documentation. If you find a bug in either, please send
1478 a bug report to @code{elib-maintainers@@lysator.liu.se}. We will try to
1479 be as quick as possible in fixing the bugs and redistributing the fixes.
1482 @node Node index, , Reporting bugs, Top
1483 @comment node-name, next, previous, up
1484 @unnumbered Node index