sequences.texi 25.5 KB
 Glenn Morris committed Sep 06, 2007 1 2 ``````@c -*-texinfo-*- @c This is part of the GNU Emacs Lisp Reference Manual. `````` Paul Eggert committed Jan 01, 2013 3 4 ``````@c Copyright (C) 1990-1995, 1998-1999, 2001-2013 Free Software @c Foundation, Inc. `````` Glenn Morris committed Sep 06, 2007 5 ``````@c See the file elisp.texi for copying conditions. `````` Glenn Morris committed May 26, 2012 6 ``````@node Sequences Arrays Vectors `````` Glenn Morris committed Sep 06, 2007 7 8 9 ``````@chapter Sequences, Arrays, and Vectors @cindex sequence `````` Chong Yidong committed Jan 23, 2012 10 11 12 13 `````` 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. `````` Glenn Morris committed Sep 06, 2007 14 `````` `````` Chong Yidong committed Feb 22, 2009 15 16 17 `````` 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. `````` Glenn Morris committed Sep 06, 2007 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 `````` 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 @var{n}th element requires looking through @var{n} cons cells, so elements farther from the beginning of the list take longer to access. But it is possible to add elements to the list, or remove elements. The following diagram shows the relationship between these types: @example @group _____________________________________________ | | | Sequence | | ______ ________________________________ | | | | | | | | | List | | Array | | | | | | ________ ________ | | | |______| | | | | | | | | | | Vector | | String | | | | | |________| |________| | | | | ____________ _____________ | | | | | | | | | | | | | Char-table | | Bool-vector | | | | | |____________| |_____________| | | | |________________________________| | |_____________________________________________| @end group @end example @menu * Sequence Functions:: Functions that accept any kind of sequence. * Arrays:: Characteristics of arrays in Emacs Lisp. * Array Functions:: Functions specifically for arrays. * Vectors:: Special characteristics of Emacs Lisp vectors. * Vector Functions:: Functions specifically for vectors. * Char-Tables:: How to work with char-tables. * Bool-Vectors:: How to work with bool-vectors. `````` Chong Yidong committed Jan 23, 2012 56 ``````* Rings:: Managing a fixed-size ring of objects. `````` Glenn Morris committed Sep 06, 2007 57 58 59 60 61 ``````@end menu @node Sequence Functions @section Sequences `````` Chong Yidong committed Jan 23, 2012 62 `````` This section describes functions that accept any kind of sequence. `````` Glenn Morris committed Sep 06, 2007 63 64 `````` @defun sequencep object `````` Chong Yidong committed Jan 23, 2012 65 66 ``````This function returns @code{t} if @var{object} is a list, vector, string, bool-vector, or char-table, @code{nil} otherwise. `````` Glenn Morris committed Sep 06, 2007 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 ``````@end defun @defun length sequence @cindex string length @cindex list length @cindex vector length @cindex sequence length @cindex char-table length This function returns the number of elements in @var{sequence}. If @var{sequence} is a dotted list, a @code{wrong-type-argument} error is signaled. Circular lists may cause an infinite loop. For a char-table, the value returned is always one more than the maximum Emacs character code. @xref{Definition of safe-length}, for the related function @code{safe-length}. @example @group (length '(1 2 3)) @result{} 3 @end group @group (length ()) @result{} 0 @end group @group (length "foobar") @result{} 6 @end group @group (length [1 2 3]) @result{} 3 @end group @group (length (make-bool-vector 5 nil)) @result{} 5 @end group @end example @end defun @noindent See also @code{string-bytes}, in @ref{Text Representations}. `````` Eli Zaretskii committed Mar 10, 2012 110 111 112 113 114 ``````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. `````` Glenn Morris committed Sep 06, 2007 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 ``````@defun elt sequence index @cindex elements of sequences This function returns the element of @var{sequence} indexed by @var{index}. Legitimate values of @var{index} are integers ranging from 0 up to one less than the length of @var{sequence}. If @var{sequence} is a list, out-of-range values behave as for @code{nth}. @xref{Definition of nth}. Otherwise, out-of-range values trigger an @code{args-out-of-range} error. @example @group (elt [1 2 3 4] 2) @result{} 3 @end group @group (elt '(1 2 3 4) 2) @result{} 3 @end group @group ;; @r{We use @code{string} to show clearly which character @code{elt} returns.} (string (elt "1234" 2)) @result{} "3" @end group @group (elt [1 2 3 4] 4) @error{} Args out of range: [1 2 3 4], 4 @end group @group (elt [1 2 3 4] -1) @error{} Args out of range: [1 2 3 4], -1 @end group @end example This function generalizes @code{aref} (@pxref{Array Functions}) and @code{nth} (@pxref{Definition of nth}). @end defun @defun copy-sequence sequence @cindex copying sequences `````` Chong Yidong committed Jan 23, 2012 154 155 156 ``````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. `````` Glenn Morris committed Sep 06, 2007 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 `````` Storing a new element into the copy does not affect the original @var{sequence}, and vice versa. However, the elements of the new sequence are not copies; they are identical (@code{eq}) to the elements of the original. Therefore, changes made within these elements, as found via the copied sequence, are also visible in the original sequence. If the sequence is a string with text properties, the property list in the copy is itself a copy, not shared with the original's property list. However, the actual values of the properties are shared. @xref{Text Properties}. This function does not work for dotted lists. Trying to copy a circular list may cause an infinite loop. See also @code{append} in @ref{Building Lists}, @code{concat} in @ref{Creating Strings}, and @code{vconcat} in @ref{Vector Functions}, for other ways to copy sequences. @example @group (setq bar '(1 2)) @result{} (1 2) @end group @group (setq x (vector 'foo bar)) @result{} [foo (1 2)] @end group @group (setq y (copy-sequence x)) @result{} [foo (1 2)] @end group @group (eq x y) @result{} nil @end group @group (equal x y) @result{} t @end group @group (eq (elt x 1) (elt y 1)) @result{} t @end group @group ;; @r{Replacing an element of one sequence.} (aset x 0 'quux) x @result{} [quux (1 2)] y @result{} [foo (1 2)] @end group @group ;; @r{Modifying the inside of a shared element.} (setcar (aref x 1) 69) x @result{} [quux (69 2)] y @result{} [foo (69 2)] @end group @end example @end defun @node Arrays @section Arrays @cindex array An @dfn{array} object has slots that hold a number of other Lisp `````` Chong Yidong committed Feb 22, 2009 225 226 227 228 229 230 231 232 233 234 235 ``````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}. `````` Glenn Morris committed Sep 06, 2007 236 237 238 239 240 241 242 243 244 245 246 247 248 249 `````` All four kinds of array share these characteristics: @itemize @bullet @item The first element of an array has index zero, the second element has index 1, and so on. This is called @dfn{zero-origin} indexing. For example, an array of four elements has indices 0, 1, 2, @w{and 3}. @item The length of the array is fixed once you create it; you cannot change the length of an existing array. @item `````` Glenn Morris committed May 04, 2012 250 ``````For purposes of evaluation, the array is a constant---i.e., `````` Glenn Morris committed Sep 06, 2007 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 ``````it evaluates to itself. @item The elements of an array may be referenced or changed with the functions @code{aref} and @code{aset}, respectively (@pxref{Array Functions}). @end itemize When you create an array, other than a char-table, you must specify its length. You cannot specify the length of a char-table, because that is determined by the range of character codes. In principle, if you want an array of text characters, you could use either a string or a vector. In practice, we always choose strings for such applications, for four reasons: @itemize @bullet @item They occupy one-fourth the space of a vector of the same elements. @item Strings are printed in a way that shows the contents more clearly as text. @item Strings can hold text properties. @xref{Text Properties}. @item Many of the specialized editing and I/O facilities of Emacs accept only strings. For example, you cannot insert a vector of characters into a buffer the way you can insert a string. @xref{Strings and Characters}. @end itemize By contrast, for an array of keyboard input characters (such as a key sequence), a vector may be necessary, because many keyboard input characters are outside the range that will fit in a string. @xref{Key Sequence Input}. @node Array Functions @section Functions that Operate on Arrays In this section, we describe the functions that accept all types of arrays. @defun arrayp object This function returns @code{t} if @var{object} is an array (i.e., a vector, a string, a bool-vector or a char-table). @example @group (arrayp [a]) @result{} t (arrayp "asdf") @result{} t (arrayp (syntax-table)) ;; @r{A char-table.} @result{} t @end group @end example @end defun @defun aref array index @cindex array elements This function returns the @var{index}th element of @var{array}. The first element is at index zero. @example @group (setq primes [2 3 5 7 11 13]) @result{} [2 3 5 7 11 13] (aref primes 4) @result{} 11 @end group @group (aref "abcdefg" 1) @result{} 98 ; @r{@samp{b} is @acronym{ASCII} code 98.} @end group @end example See also the function @code{elt}, in @ref{Sequence Functions}. @end defun @defun aset array index object This function sets the @var{index}th element of @var{array} to be @var{object}. It returns @var{object}. @example @group (setq w [foo bar baz]) @result{} [foo bar baz] (aset w 0 'fu) @result{} fu w @result{} [fu bar baz] @end group @group (setq x "asdfasfd") @result{} "asdfasfd" (aset x 3 ?Z) @result{} 90 x @result{} "asdZasfd" @end group @end example If @var{array} is a string and @var{object} is not a character, a @code{wrong-type-argument} error results. The function converts a unibyte string to multibyte if necessary to insert a character. @end defun @defun fillarray array object This function fills the array @var{array} with @var{object}, so that each element of @var{array} is @var{object}. It returns @var{array}. @example @group (setq a [a b c d e f g]) @result{} [a b c d e f g] (fillarray a 0) @result{} [0 0 0 0 0 0 0] a @result{} [0 0 0 0 0 0 0] @end group @group (setq s "When in the course") @result{} "When in the course" (fillarray s ?-) @result{} "------------------" @end group @end example If @var{array} is a string and @var{object} is not a character, a @code{wrong-type-argument} error results. @end defun The general sequence functions @code{copy-sequence} and @code{length} are often useful for objects known to be arrays. @xref{Sequence Functions}. @node Vectors @section Vectors @cindex vector (type) `````` Chong Yidong committed Feb 22, 2009 392 393 394 395 396 397 398 `````` 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. `````` Glenn Morris committed Sep 06, 2007 399 `````` `````` Chong Yidong committed Jan 23, 2012 400 401 `````` Like other arrays, vectors use zero-origin indexing: the first element has index 0. `````` Glenn Morris committed Sep 06, 2007 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 `````` Vectors are printed with square brackets surrounding the elements. Thus, a vector whose elements are the symbols @code{a}, @code{b} and @code{a} is printed as @code{[a b a]}. You can write vectors in the same way in Lisp input. A vector, like a string or a number, is considered a constant for evaluation: the result of evaluating it is the same vector. This does not evaluate or even examine the elements of the vector. @xref{Self-Evaluating Forms}. Here are examples illustrating these principles: @example @group (setq avector [1 two '(three) "four" [five]]) @result{} [1 two (quote (three)) "four" [five]] (eval avector) @result{} [1 two (quote (three)) "four" [five]] (eq avector (eval avector)) @result{} t @end group @end example @node Vector Functions @section Functions for Vectors Here are some functions that relate to vectors: @defun vectorp object This function returns @code{t} if @var{object} is a vector. @example @group (vectorp [a]) @result{} t (vectorp "asdf") @result{} nil @end group @end example @end defun @defun vector &rest objects This function creates and returns a vector whose elements are the arguments, @var{objects}. @example @group (vector 'foo 23 [bar baz] "rats") @result{} [foo 23 [bar baz] "rats"] (vector) @result{} [] @end group @end example @end defun @defun make-vector length object This function returns a new vector consisting of @var{length} elements, each initialized to @var{object}. @example @group (setq sleepy (make-vector 9 'Z)) @result{} [Z Z Z Z Z Z Z Z Z] @end group @end example @end defun @defun vconcat &rest sequences @cindex copying vectors `````` Chong Yidong committed Feb 22, 2009 472 ``````This function returns a new vector containing all the elements of `````` Glenn Morris committed Sep 06, 2007 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 ``````@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. The value is a newly constructed vector that is not @code{eq} to any existing vector. @example @group (setq a (vconcat '(A B C) '(D E F))) @result{} [A B C D E F] (eq a (vconcat a)) @result{} nil @end group @group (vconcat) @result{} [] (vconcat [A B C] "aa" '(foo (6 7))) @result{} [A B C 97 97 foo (6 7)] @end group @end example The @code{vconcat} function also allows byte-code function objects as 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}. For other concatenation functions, see @code{mapconcat} in @ref{Mapping Functions}, @code{concat} in @ref{Creating Strings}, and @code{append} in @ref{Building Lists}. @end defun The @code{append} function also provides a way to convert a vector into a list with the same elements: @example @group (setq avector [1 two (quote (three)) "four" [five]]) @result{} [1 two (quote (three)) "four" [five]] (append avector nil) @result{} (1 two (quote (three)) "four" [five]) @end group @end example @node Char-Tables @section Char-Tables @cindex char-tables @cindex extra slots of char-table A char-table is much like a vector, except that it is indexed by character codes. Any valid character code, without modifiers, can be 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 `````` Chong Yidong committed Feb 22, 2009 526 527 528 ``````data not associated with particular character codes. Like vectors, char-tables are constants when evaluated, and can hold elements of any type. `````` Glenn Morris committed Sep 06, 2007 529 530 `````` @cindex subtype of char-table `````` Chong Yidong committed Feb 22, 2009 531 532 533 534 535 536 537 538 539 540 541 542 543 544 `````` 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 `````` Chong Yidong committed Dec 02, 2012 545 546 547 548 ``````@code{char-table-extra-slots} symbol property (@pxref{Symbol Properties}), whose value should be an integer between 0 and 10. If the subtype has no such symbol property, the char-table has no extra slots. `````` Chong Yidong committed Feb 22, 2009 549 ``````@end itemize `````` Glenn Morris committed Sep 06, 2007 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 `````` @cindex parent of char-table A char-table can have a @dfn{parent}, which is another char-table. If it does, then whenever the char-table specifies @code{nil} for a particular character @var{c}, it inherits the value specified in the parent. In other words, @code{(aref @var{char-table} @var{c})} returns the value from the parent of @var{char-table} if @var{char-table} itself specifies @code{nil}. @cindex default value of char-table A char-table can also have a @dfn{default value}. If so, then @code{(aref @var{char-table} @var{c})} returns the default value whenever the char-table does not specify any other non-@code{nil} value. @defun make-char-table subtype &optional init `````` Chong Yidong committed Feb 22, 2009 565 566 567 568 ``````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. `````` Glenn Morris committed Sep 06, 2007 569 570 571 `````` 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. `````` Chong Yidong committed Feb 22, 2009 572 573 574 575 576 `````` 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 `````` Chong Yidong committed Feb 22, 2009 577 578 ``````@code{char-table-extra-slots} symbol property (@pxref{Property Lists}), the char-table has no extra slots. `````` Glenn Morris committed Sep 06, 2007 579 580 581 ``````@end defun @defun char-table-p object `````` Chong Yidong committed Feb 22, 2009 582 583 ``````This function returns @code{t} if @var{object} is a char-table, and @code{nil} otherwise. `````` Glenn Morris committed Sep 06, 2007 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 ``````@end defun @defun char-table-subtype char-table This function returns the subtype symbol of @var{char-table}. @end defun There is no special function to access default values in a char-table. To do that, use @code{char-table-range} (see below). @defun char-table-parent char-table This function returns the parent of @var{char-table}. The parent is always either @code{nil} or another char-table. @end defun @defun set-char-table-parent char-table new-parent This function sets the parent of @var{char-table} to @var{new-parent}. @end defun @defun char-table-extra-slot char-table n This function returns the contents of extra slot @var{n} of @var{char-table}. The number of extra slots in a char-table is determined by its subtype. @end defun @defun set-char-table-extra-slot char-table n value This function stores @var{value} in extra slot @var{n} of @var{char-table}. @end defun A char-table can specify an element value for a single character code; it can also specify a value for an entire character set. @defun char-table-range char-table range This returns the value specified in @var{char-table} for a range of characters @var{range}. Here are the possibilities for @var{range}: @table @asis @item @code{nil} Refers to the default value. @item @var{char} Refers to the element for character @var{char} (supposing @var{char} is a valid character code). `````` Eli Zaretskii committed Oct 14, 2008 628 629 630 ``````@item @code{(@var{from} . @var{to})} A cons cell refers to all the characters in the inclusive range @samp{[@var{from}..@var{to}]}. `````` Glenn Morris committed Sep 06, 2007 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 ``````@end table @end defun @defun set-char-table-range char-table range value This function sets the value in @var{char-table} for a range of characters @var{range}. Here are the possibilities for @var{range}: @table @asis @item @code{nil} Refers to the default value. @item @code{t} Refers to the whole range of character codes. @item @var{char} Refers to the element for character @var{char} (supposing @var{char} is a valid character code). `````` Eli Zaretskii committed Oct 14, 2008 649 650 651 ``````@item @code{(@var{from} . @var{to})} A cons cell refers to all the characters in the inclusive range @samp{[@var{from}..@var{to}]}. `````` Glenn Morris committed Sep 06, 2007 652 653 654 655 ``````@end table @end defun @defun map-char-table function char-table `````` Eli Zaretskii committed Oct 16, 2008 656 657 658 ``````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 `````` Glenn Morris committed Sep 06, 2007 659 ``````is a possible @var{range} argument for @code{char-table-range}---either `````` Eli Zaretskii committed Oct 14, 2008 660 661 662 ``````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. `````` Glenn Morris committed Sep 06, 2007 663 664 665 666 `````` Overall, the key-value pairs passed to @var{function} describe all the values stored in @var{char-table}. `````` Eli Zaretskii committed Oct 14, 2008 667 668 669 ``````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: `````` Glenn Morris committed Sep 06, 2007 670 671 672 `````` @example (let (accumulator) `````` Eli Zaretskii committed Oct 14, 2008 673 674 `````` (map-char-table #'(lambda (key value) `````` Glenn Morris committed Jun 22, 2010 675 676 677 678 679 680 681 `````` (setq accumulator (cons (list (if (consp key) (list (car key) (cdr key)) key) value) accumulator))) `````` Eli Zaretskii committed Oct 14, 2008 682 683 `````` (syntax-table)) accumulator) `````` Glenn Morris committed Sep 06, 2007 684 ``````@result{} `````` Eli Zaretskii committed Oct 14, 2008 685 686 687 ``````(((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))) `````` Glenn Morris committed Sep 06, 2007 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 ``````@end example @end defun @node Bool-Vectors @section Bool-vectors @cindex Bool-vectors A bool-vector is much like a vector, except that it stores only the values @code{t} and @code{nil}. If you try to store any non-@code{nil} value into an element of the bool-vector, the effect is to store @code{t} there. As with all arrays, bool-vector indices start from 0, and the length cannot be changed once the bool-vector is created. Bool-vectors are constants when evaluated. There are two special functions for working with bool-vectors; aside from that, you manipulate them with same functions used for other kinds of arrays. @defun make-bool-vector length initial Return a new bool-vector of @var{length} elements, each one initialized to @var{initial}. @end defun @defun bool-vector-p object This returns @code{t} if @var{object} is a bool-vector, and @code{nil} otherwise. @end defun `````` Xue Fuqiao committed Sep 28, 2013 716 717 718 719 720 721 722 723 724 725 ``````@c FIXME: Document these functions: @c `bool-vector-exclusive-or' @c `bool-vector-union' @c `bool-vector-intersection' @c `bool-vector-set-difference' @c `bool-vector-not' @c `bool-vector-subset' @c `bool-vector-count-matches' @c `bool-vector-count-matches-at' `````` Glenn Morris committed Sep 06, 2007 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 `````` Here is an example of creating, examining, and updating a bool-vector. Note that the printed form represents up to 8 boolean values as a single character. @example (setq bv (make-bool-vector 5 t)) @result{} #&5"^_" (aref bv 1) @result{} t (aset bv 3 nil) @result{} nil bv @result{} #&5"^W" @end example @noindent These results make sense because the binary codes for control-_ and control-W are 11111 and 10111, respectively. `````` Chong Yidong committed Jan 23, 2012 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 `````` @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``````