@c -*-texinfo-*-
@c This is part of the GNU Emacs Lisp Reference Manual.
-@c Copyright (C) 1990, 1991, 1992, 1993, 1994, 1995, 1998, 1999, 2001,
-@c 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
+@c Copyright (C) 1990-1995, 1998-1999, 2001-2012
+@c Free Software Foundation, Inc.
@c See the file elisp.texi for copying conditions.
@setfilename ../../info/sequences
@node Sequences Arrays Vectors, Hash Tables, Lists, Top
@chapter Sequences, Arrays, and Vectors
@cindex sequence
- Recall that the @dfn{sequence} type is the union of two other Lisp
-types: lists and arrays. In other words, any list is a sequence, and
-any array is a sequence. The common property that all sequences have is
-that each is an ordered collection of elements.
+ The @dfn{sequence} type is the union of two other Lisp types: lists
+and arrays. In other words, any list is a sequence, and any array is
+a sequence. The common property that all sequences have is that each
+is an ordered collection of elements.
- An @dfn{array} is a single primitive object that has a slot for each
-of its elements. All the elements are accessible in constant time, but
-the length of an existing array cannot be changed. Strings, vectors,
-char-tables and bool-vectors are the four types of arrays.
+ An @dfn{array} is a fixed-length object with a slot for each of its
+elements. All the elements are accessible in constant time. The four
+types of arrays are strings, vectors, char-tables and bool-vectors.
A list is a sequence of elements, but it is not a single primitive
object; it is made of cons cells, one cell per element. Finding the
@end group
@end example
- The elements of vectors and lists may be any Lisp objects. The
-elements of strings are all characters.
-
@menu
* Sequence Functions:: Functions that accept any kind of sequence.
* Arrays:: Characteristics of arrays in Emacs Lisp.
* Vector Functions:: Functions specifically for vectors.
* Char-Tables:: How to work with char-tables.
* Bool-Vectors:: How to work with bool-vectors.
+* Rings:: Managing a fixed-size ring of objects.
@end menu
@node Sequence Functions
@section Sequences
- In Emacs Lisp, a @dfn{sequence} is either a list or an array. The
-common property of all sequences is that they are ordered collections of
-elements. This section describes functions that accept any kind of
-sequence.
+ This section describes functions that accept any kind of sequence.
@defun sequencep object
-Returns @code{t} if @var{object} is a list, vector, string,
-bool-vector, or char-table, @code{nil} otherwise.
+This function returns @code{t} if @var{object} is a list, vector,
+string, bool-vector, or char-table, @code{nil} otherwise.
@end defun
@defun length sequence
@noindent
See also @code{string-bytes}, in @ref{Text Representations}.
+If you need to compute the width of a string on display, you should
+use @code{string-width} (@pxref{Width}), not @code{length}, since
+@code{length} only counts the number of characters, but does not
+account for the display width of each character.
+
@defun elt sequence index
@cindex elements of sequences
This function returns the element of @var{sequence} indexed by
@defun copy-sequence sequence
@cindex copying sequences
-Returns a copy of @var{sequence}. The copy is the same type of object
-as the original sequence, and it has the same elements in the same order.
+This function returns a copy of @var{sequence}. The copy is the same
+type of object as the original sequence, and it has the same elements
+in the same order.
Storing a new element into the copy does not affect the original
@var{sequence}, and vice versa. However, the elements of the new
@cindex array
An @dfn{array} object has slots that hold a number of other Lisp
-objects, called the elements of the array. Any element of an array may
-be accessed in constant time. In contrast, an element of a list
-requires access time that is proportional to the position of the element
-in the list.
-
- Emacs defines four types of array, all one-dimensional: @dfn{strings},
-@dfn{vectors}, @dfn{bool-vectors} and @dfn{char-tables}. A vector is a
-general array; its elements can be any Lisp objects. A string is a
-specialized array; its elements must be characters. Each type of array
-has its own read syntax.
-@xref{String Type}, and @ref{Vector Type}.
+objects, called the elements of the array. Any element of an array
+may be accessed in constant time. In contrast, the time to access an
+element of a list is proportional to the position of that element in
+the list.
+
+ Emacs defines four types of array, all one-dimensional:
+@dfn{strings} (@pxref{String Type}), @dfn{vectors} (@pxref{Vector
+Type}), @dfn{bool-vectors} (@pxref{Bool-Vector Type}), and
+@dfn{char-tables} (@pxref{Char-Table Type}). Vectors and char-tables
+can hold elements of any type, but strings can only hold characters,
+and bool-vectors can only hold @code{t} and @code{nil}.
All four kinds of array share these characteristics:
change the length of an existing array.
@item
-For purposes of evaluation, the array is a constant---in other words,
+For purposes of evaluation, the array is a constant---i.e.,
it evaluates to itself.
@item
@section Vectors
@cindex vector (type)
- Arrays in Lisp, like arrays in most languages, are blocks of memory
-whose elements can be accessed in constant time. A @dfn{vector} is a
-general-purpose array of specified length; its elements can be any Lisp
-objects. (By contrast, a string can hold only characters as elements.)
-Vectors in Emacs are used for obarrays (vectors of symbols), and as part
-of keymaps (vectors of commands). They are also used internally as part
-of the representation of a byte-compiled function; if you print such a
-function, you will see a vector in it.
+ A @dfn{vector} is a general-purpose array whose elements can be any
+Lisp objects. (By contrast, the elements of a string can only be
+characters. @xref{Strings and Characters}.) Vectors are used in
+Emacs for many purposes: as key sequences (@pxref{Key Sequences}), as
+symbol-lookup tables (@pxref{Creating Symbols}), as part of the
+representation of a byte-compiled function (@pxref{Byte Compilation}),
+and more.
- In Emacs Lisp, the indices of the elements of a vector start from zero
-and count up from there.
+ Like other arrays, vectors use zero-origin indexing: the first
+element has index 0.
Vectors are printed with square brackets surrounding the elements.
Thus, a vector whose elements are the symbols @code{a}, @code{b} and
@defun vconcat &rest sequences
@cindex copying vectors
-This function returns a new vector containing all the elements of the
+This function returns a new vector containing all the elements of
@var{sequences}. The arguments @var{sequences} may be true lists,
vectors, strings or bool-vectors. If no @var{sequences} are given, an
empty vector is returned.
arguments. This is a special feature to make it easy to access the entire
contents of a byte-code function object. @xref{Byte-Code Objects}.
-In Emacs versions before 21, the @code{vconcat} function allowed
-integers as arguments, converting them to strings of digits, but that
-feature has been eliminated. The proper way to convert an integer to
-a decimal number in this way is with @code{format} (@pxref{Formatting
-Strings}) or @code{number-to-string} (@pxref{String Conversion}).
-
For other concatenation functions, see @code{mapconcat} in @ref{Mapping
Functions}, @code{concat} in @ref{Creating Strings}, and @code{append}
in @ref{Building Lists}.
used as an index in a char-table. You can access a char-table's
elements with @code{aref} and @code{aset}, as with any array. In
addition, a char-table can have @dfn{extra slots} to hold additional
-data not associated with particular character codes. Char-tables are
-constants when evaluated.
+data not associated with particular character codes. Like vectors,
+char-tables are constants when evaluated, and can hold elements of any
+type.
@cindex subtype of char-table
- Each char-table has a @dfn{subtype} which is a symbol. The subtype
-has two purposes: to distinguish char-tables meant for different uses,
-and to control the number of extra slots. For example, display tables
-are char-tables with @code{display-table} as the subtype, and syntax
-tables are char-tables with @code{syntax-table} as the subtype. A valid
-subtype must have a @code{char-table-extra-slots} property which is an
-integer between 0 and 10. This integer specifies the number of
-@dfn{extra slots} in the char-table.
+ Each char-table has a @dfn{subtype}, a symbol, which serves two
+purposes:
+
+@itemize @bullet
+@item
+The subtype provides an easy way to tell what the char-table is for.
+For instance, display tables are char-tables with @code{display-table}
+as the subtype, and syntax tables are char-tables with
+@code{syntax-table} as the subtype. The subtype can be queried using
+the function @code{char-table-subtype}, described below.
+
+@item
+The subtype controls the number of @dfn{extra slots} in the
+char-table. This number is specified by the subtype's
+@code{char-table-extra-slots} symbol property, which should be an
+integer between 0 and 10. If the subtype has no such symbol property,
+the char-table has no extra slots. @xref{Property Lists}, for
+information about symbol properties.
+@end itemize
@cindex parent of char-table
A char-table can have a @dfn{parent}, which is another char-table. If
whenever the char-table does not specify any other non-@code{nil} value.
@defun make-char-table subtype &optional init
-Return a newly created char-table, with subtype @var{subtype}. Each
-element is initialized to @var{init}, which defaults to @code{nil}. You
-cannot alter the subtype of a char-table after the char-table is
-created.
+Return a newly-created char-table, with subtype @var{subtype} (a
+symbol). Each element is initialized to @var{init}, which defaults to
+@code{nil}. You cannot alter the subtype of a char-table after the
+char-table is created.
There is no argument to specify the length of the char-table, because
all char-tables have room for any valid character code as an index.
+
+If @var{subtype} has the @code{char-table-extra-slots} symbol
+property, that specifies the number of extra slots in the char-table.
+This should be an integer between 0 and 10; otherwise,
+@code{make-char-table} raises an error. If @var{subtype} has no
+@code{char-table-extra-slots} symbol property (@pxref{Property
+Lists}), the char-table has no extra slots.
@end defun
@defun char-table-p object
-This function returns @code{t} if @var{object} is a char-table,
-otherwise @code{nil}.
+This function returns @code{t} if @var{object} is a char-table, and
+@code{nil} otherwise.
@end defun
@defun char-table-subtype char-table
This function returns the subtype symbol of @var{char-table}.
@end defun
-@defun set-char-table-default char-table char new-default
-This function sets the default value of generic character @var{char}
-in @var{char-table} to @var{new-default}.
-
There is no special function to access default values in a char-table.
To do that, use @code{char-table-range} (see below).
-@end defun
@defun char-table-parent char-table
This function returns the parent of @var{char-table}. The parent is
Refers to the element for character @var{char}
(supposing @var{char} is a valid character code).
-@item @var{charset}
-Refers to the value specified for the whole character set
-@var{charset} (@pxref{Character Sets}).
-
-@item @var{generic-char}
-A generic character stands for a character set, or a row of a
-character set; specifying the generic character as argument is
-equivalent to specifying the character set name. @xref{Splitting
-Characters}, for a description of generic characters.
+@item @code{(@var{from} . @var{to})}
+A cons cell refers to all the characters in the inclusive range
+@samp{[@var{from}..@var{to}]}.
@end table
@end defun
Refers to the element for character @var{char}
(supposing @var{char} is a valid character code).
-@item @var{charset}
-Refers to the value specified for the whole character set
-@var{charset} (@pxref{Character Sets}).
-
-@item @var{generic-char}
-A generic character stands for a character set; specifying the generic
-character as argument is equivalent to specifying the character set
-name. @xref{Splitting Characters}, for a description of generic characters.
+@item @code{(@var{from} . @var{to})}
+A cons cell refers to all the characters in the inclusive range
+@samp{[@var{from}..@var{to}]}.
@end table
@end defun
@defun map-char-table function char-table
-This function calls @var{function} for each element of @var{char-table}.
-@var{function} is called with two arguments, a key and a value. The key
+This function calls its argument @var{function} for each element of
+@var{char-table} that has a non-@code{nil} value. The call to
+@var{function} is with two arguments, a key and a value. The key
is a possible @var{range} argument for @code{char-table-range}---either
-a valid character or a generic character---and the value is
-@code{(char-table-range @var{char-table} @var{key})}.
+a valid character or a cons cell @code{(@var{from} . @var{to})},
+specifying a range of characters that share the same value. The value is
+what @code{(char-table-range @var{char-table} @var{key})} returns.
Overall, the key-value pairs passed to @var{function} describe all the
values stored in @var{char-table}.
-The return value is always @code{nil}; to make this function useful,
-@var{function} should have side effects. For example,
-here is how to examine each element of the syntax table:
+The return value is always @code{nil}; to make calls to
+@code{map-char-table} useful, @var{function} should have side effects.
+For example, here is how to examine the elements of the syntax table:
@example
(let (accumulator)
- (map-char-table
- #'(lambda (key value)
- (setq accumulator
- (cons (list key value) accumulator)))
- (syntax-table))
- accumulator)
+ (map-char-table
+ #'(lambda (key value)
+ (setq accumulator
+ (cons (list
+ (if (consp key)
+ (list (car key) (cdr key))
+ key)
+ value)
+ accumulator)))
+ (syntax-table))
+ accumulator)
@result{}
-((475008 nil) (474880 nil) (474752 nil) (474624 nil)
- ... (5 (3)) (4 (3)) (3 (3)) (2 (3)) (1 (3)) (0 (3)))
+(((2597602 4194303) (2)) ((2597523 2597601) (3))
+ ... (65379 (5 . 65378)) (65378 (4 . 65379)) (65377 (1))
+ ... (12 (0)) (11 (3)) (10 (12)) (9 (0)) ((0 8) (3)))
@end example
@end defun
These results make sense because the binary codes for control-_ and
control-W are 11111 and 10111, respectively.
-@ignore
- arch-tag: fcf1084a-cd29-4adc-9f16-68586935b386
-@end ignore
+@node Rings
+@section Managing a Fixed-Size Ring of Objects
+
+@cindex ring data structure
+ A @dfn{ring} is a fixed-size data structure that supports insertion,
+deletion, rotation, and modulo-indexed reference and traversal. An
+efficient ring data structure is implemented by the @code{ring}
+package. It provides the functions listed in this section.
+
+ Note that several ``rings'' in Emacs, like the kill ring and the
+mark ring, are actually implemented as simple lists, @emph{not} using
+the @code{ring} package; thus the following functions won't work on
+them.
+
+@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
HCoop / bpt / emacs.git / blobdiff