@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999
-@c Free Software Foundation, Inc.
+@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999, 2002, 2003,
+@c 2004, 2005, 2006 Free Software Foundation, Inc.
@c See the file elisp.texi for copying conditions.
@setfilename ../info/lists
@node Lists, Sequences Arrays Vectors, Strings and Characters, Top
@menu
* Cons Cells:: How lists are made out of cons cells.
-* Lists as Boxes:: Graphical notation to explain lists.
* List-related Predicates:: Is this object a list? Comparing two lists.
* List Elements:: Extracting the pieces of a list.
* Building Lists:: Creating list structure.
* Modifying Lists:: Storing new pieces into an existing list.
* Sets And Lists:: A list can represent a finite mathematical set.
* Association Lists:: A list can represent a finite relation or mapping.
+* Rings:: Managing a fixed-size ring of objects.
@end menu
@node Cons Cells
@dfn{list structure} has come to mean any structure made out of cons
cells.
- The @sc{cdr} of any nonempty list @var{l} is a list containing all the
+ The @sc{cdr} of any nonempty true list @var{l} is a list containing all the
elements of @var{l} except the first.
-@node Lists as Boxes
-@comment node-name, next, previous, up
-@section Lists as Linked Pairs of Boxes
-@cindex box representation for lists
-@cindex lists represented as boxes
-@cindex cons cell as box
-
- A cons cell can be illustrated as a pair of boxes. The first box
-represents the @sc{car} and the second box represents the @sc{cdr}.
-Here is an illustration of the two-element list, @code{(tulip lily)},
-made from two cons cells:
-
-@example
-@group
- --------------- ---------------
-| car | cdr | | car | cdr |
-| tulip | o---------->| lily | nil |
-| | | | | |
- --------------- ---------------
-@end group
-@end example
-
- Each pair of boxes represents a cons cell. Each box ``refers to'',
-``points to'' or ``holds'' a Lisp object. (These terms are
-synonymous.) The first box, which describes the @sc{car} of the first
-cons cell, contains the symbol @code{tulip}. The arrow from the
-@sc{cdr} box of the first cons cell to the second cons cell indicates
-that the @sc{cdr} of the first cons cell is the second cons cell.
-
- The same list can be illustrated in a different sort of box notation
-like this:
-
-@example
-@group
- --- --- --- ---
- | | |--> | | |--> nil
- --- --- --- ---
- | |
- | |
- --> tulip --> lily
-@end group
-@end example
-
- Here is a more complex illustration, showing the three-element list,
-@code{((pine needles) oak maple)}, the first element of which is a
-two-element list:
-
-@example
-@group
- --- --- --- --- --- ---
- | | |--> | | |--> | | |--> nil
- --- --- --- --- --- ---
- | | |
- | | |
- | --> oak --> maple
- |
- | --- --- --- ---
- --> | | |--> | | |--> nil
- --- --- --- ---
- | |
- | |
- --> pine --> needles
-@end group
-@end example
-
- The same list represented in the first box notation looks like this:
-
-@example
-@group
- -------------- -------------- --------------
-| car | cdr | | car | cdr | | car | cdr |
-| o | o------->| oak | o------->| maple | nil |
-| | | | | | | | | |
- -- | --------- -------------- --------------
- |
- |
- | -------------- ----------------
- | | car | cdr | | car | cdr |
- ------>| pine | o------->| needles | nil |
- | | | | | |
- -------------- ----------------
-@end group
-@end example
-
@xref{Cons Cell Type}, for the read and print syntax of cons cells and
-lists, and for more ``box and arrow'' illustrations of lists.
+lists, and for ``box and arrow'' illustrations of lists.
@node List-related Predicates
@section Predicates on Lists
- The following predicates test whether a Lisp object is an atom, is a
-cons cell or is a list, or whether it is the distinguished object
-@code{nil}. (Many of these predicates can be defined in terms of the
-others, but they are used so often that it is worth having all of them.)
+ The following predicates test whether a Lisp object is an atom,
+whether it is a cons cell or is a list, or whether it is the
+distinguished object @code{nil}. (Many of these predicates can be
+defined in terms of the others, but they are used so often that it is
+worth having all of them.)
@defun consp object
This function returns @code{t} if @var{object} is a cons cell, @code{nil}
@tindex pop
@defmac pop listname
This macro is a way of examining the @sc{car} of a list,
-and taking it off the list, all at once. It is new in Emacs 21.
+and taking it off the list, all at once.
It operates on the list which is stored in the symbol @var{listname}.
It removes this element from the list by setting @var{listname}
@end example
@end defmac
-@anchor{Definition of nth}
@defun nth n list
+@anchor{Definition of nth}
This function returns the @var{n}th element of @var{list}. Elements
are numbered starting with zero, so the @sc{car} of @var{list} is
element number zero. If the length of @var{list} is @var{n} or less,
if @var{n} is bigger than @var{list}'s length.
@end defun
-@anchor{Definition of safe-length}
@defun safe-length list
+@anchor{Definition of safe-length}
This function returns the length of @var{list}, with no risk of either
an error or an infinite loop. It generally returns the number of
distinct cons cells in the list. However, for circular lists,
@defmac push newelt listname
This macro provides an alternative way to write
@code{(setq @var{listname} (cons @var{newelt} @var{listname}))}.
-It is new in Emacs 21.
@example
(setq l '(a b))
incrementing by @var{separation}, and ending at or just before
@var{to}. @var{separation} can be positive or negative and defaults
to 1. If @var{to} is @code{nil} or numerically equal to @var{from},
-the one element list @code{(from)} is returned. If @var{separation}
-is 0 and @var{to} is neither @code{nil} nor numerically equal to
-@var{from}, an error is signaled.
+the value is the one-element list @code{(@var{from})}. If @var{to} is
+less than @var{from} with a positive @var{separation}, or greater than
+@var{from} with a negative @var{separation}, the value is @code{nil}
+because those arguments specify an empty sequence.
+
+If @var{separation} is 0 and @var{to} is neither @code{nil} nor
+numerically equal to @var{from}, @code{number-sequence} signals an
+error, since those arguments specify an infinite sequence.
All arguments can be integers or floating point numbers. However,
floating point arguments can be tricky, because floating point
primitives @code{setcar} and @code{setcdr}. We call these ``destructive''
operations because they change existing list structure.
-@cindex CL note---@code{rplaca} vrs @code{setcar}
+@cindex CL note---@code{rplaca} vs @code{setcar}
@quotation
@findex rplaca
@findex rplacd
The argument @var{predicate} must be a function that accepts two
arguments. It is called with two elements of @var{list}. To get an
-increasing order sort, the @var{predicate} should return @code{t} if the
+increasing order sort, the @var{predicate} should return non-@code{nil} if the
first element is ``less than'' the second, or @code{nil} if not.
The comparison function @var{predicate} must give reliable results for
@end example
@end defun
+@defun rassq-delete-all value alist
+This function deletes from @var{alist} all the elements whose @sc{cdr}
+is @code{eq} to @var{value}. It returns the shortened alist, and
+often modifies the original list structure of @var{alist}.
+@code{rassq-delete-all} is like @code{assq-delete-all} except that it
+compares the @sc{cdr} of each @var{alist} association instead of the
+@sc{car}.
+@end defun
+
+@node Rings
+@section Managing a Fixed-Size Ring of Objects
+
+@cindex ring data structure
+ This section describes functions for operating on rings. A
+@dfn{ring} is a fixed-size data structure that supports insertion,
+deletion, rotation, and modulo-indexed reference and traversal.
+
+@defun make-ring size
+This returns a new ring capable of holding @var{size} objects.
+@var{size} should be an integer.
+@end defun
+
+@defun ring-p object
+This returns @code{t} if @var{object} is a ring, @code{nil} otherwise.
+@end defun
+
+@defun ring-size ring
+This returns the maximum capacity of the @var{ring}.
+@end defun
+
+@defun ring-length ring
+This returns the number of objects that @var{ring} currently contains.
+The value will never exceed that returned by @code{ring-size}.
+@end defun
+
+@defun ring-elements ring
+This returns a list of the objects in @var{ring}, in order, newest first.
+@end defun
+
+@defun ring-copy ring
+This returns a new ring which is a copy of @var{ring}.
+The new ring contains the same (@code{eq}) objects as @var{ring}.
+@end defun
+
+@defun ring-empty-p ring
+This returns @code{t} if @var{ring} is empty, @code{nil} otherwise.
+@end defun
+
+ The newest element in the ring always has index 0. Higher indices
+correspond to older elements. Indices are computed modulo the ring
+length. Index @minus{}1 corresponds to the oldest element, @minus{}2
+to the next-oldest, and so forth.
+
+@defun ring-ref ring index
+This returns the object in @var{ring} found at index @var{index}.
+@var{index} may be negative or greater than the ring length. If
+@var{ring} is empty, @code{ring-ref} signals an error.
+@end defun
+
+@defun ring-insert ring object
+This inserts @var{object} into @var{ring}, making it the newest
+element, and returns @var{object}.
+
+If the ring is full, insertion removes the oldest element to
+make room for the new element.
+@end defun
+
+@defun ring-remove ring &optional index
+Remove an object from @var{ring}, and return that object. The
+argument @var{index} specifies which item to remove; if it is
+@code{nil}, that means to remove the oldest item. If @var{ring} is
+empty, @code{ring-remove} signals an error.
+@end defun
+
+@defun ring-insert-at-beginning ring object
+This inserts @var{object} into @var{ring}, treating it as the oldest
+element. The return value is not significant.
+
+If the ring is full, this function removes the newest element to make
+room for the inserted element.
+@end defun
+
+@cindex fifo data structure
+ If you are careful not to exceed the ring size, you can
+use the ring as a first-in-first-out queue. For example:
+
+@lisp
+(let ((fifo (make-ring 5)))
+ (mapc (lambda (obj) (ring-insert fifo obj))
+ '(0 one "two"))
+ (list (ring-remove fifo) t
+ (ring-remove fifo) t
+ (ring-remove fifo)))
+ @result{} (0 t one t "two")
+@end lisp
+
@ignore
arch-tag: 31fb8a4e-4aa8-4a74-a206-aa00451394d4
@end ignore