@c -*-texinfo-*-
@c This is part of the XEmacs Lisp Reference Manual.
@c Copyright (C) 1996 Ben Wing.
@c See the file lispref.texi for copying conditions.
@setfilename ../../info/range-tables.info
@node Range Tables, Databases, Hash Tables, top
@chapter Range Tables
@cindex Range Tables

A range table is a table that efficiently associates values with
ranges of fixnums.

Note that range tables have a read syntax, like this:

@example
#s(range-table type start-closed-end-open data ((-3 2) foo (5 20) bar))
@end example

This maps integers in the range [-3, 2) to @code{foo} and integers
in the range [5, 20) to @code{bar}.

By default, range tables have a @var{type} of
@code{start-closed-end-open}. (@strong{NOTE}: This is a change from
21.4 and earlier, where there was no @var{type} and range tables were always
closed on both ends.) This makes them work like text properties.

@defun range-table-p object
Return non-@code{nil} if @var{object} is a range table.
@end defun

@menu
* Introduction to Range Tables:: Range tables efficiently map ranges of
                                 integers to values.
* Working With Range Tables::    Range table functions.
@end menu

@node Introduction to Range Tables
@section Introduction to Range Tables

@defun make-range-table &optional type
Make a new, empty range table.

@var{type} is a symbol indicating how ranges are assumed to function
at their ends.  It can be one of

@example
SYMBOL                                     RANGE-START         RANGE-END
------                                     -----------         ---------
`start-closed-end-open'  (the default)     closed              open
`start-closed-end-closed'                  closed              closed
`start-open-end-open'                      open                open
`start-open-end-closed'                    open                closed
@end example

A @dfn{closed} endpoint of a range means that the number at that end
is included in the range.  For an @dfn{open} endpoint, the number
would not be included.

For example, a closed-open range from 5 to 20 would be indicated as
@samp{[5, 20)} where a bracket indicates a closed end and a
parenthesis an open end, and would mean `all the numbers between 5 and
20', including 5 but not 20.  This seems a little strange at first but
is in fact extremely common in the outside world as well as in
computers and makes things work sensibly.  For example, if I say
"there are seven days between today and next week today", I'm
including today but not next week today; if I included both, there
would be eight days.  Similarly, there are 15 (= 20 - 5) elements in
the range @samp{[5, 20)}, but 16 in the range @samp{[5, 20]}.
@end defun

@defun copy-range-table range-table
This function returns a new range table which contains the same values
for the same ranges as @var{range-table}.  The values will not
themselves be copied.
@end defun

@node Working With Range Tables
@section Working With Range Tables

@defun get-range-table pos range-table &optional default
This function finds value for position @var{pos} in @var{range-table}.
If there is no corresponding value, return @var{default} (defaults to
@code{nil}).

@strong{NOTE}: If you are working with ranges that are closed at the
start and open at the end (the default), and you put a value for a
range with @var{start} equal to @var{end}, @code{get-range-table} will
@strong{not} return that value!  You would need to set @var{end} one
greater than @var{start}.
@end defun

@defun put-range-table start end value range-table
This function sets the value for range (@var{start}, @var{end}) to be
@var{value} in @var{range-table}.

@strong{NOTE}: Unless you are working with ranges that are closed at
both ends, nothing will happen if @var{start} equals @var{end}.
@end defun

@defun remove-range-table start end range-table
This function removes the value for range (@var{start}, @var{end}) in
@var{range-table}.
@end defun

@defun clear-range-table range-table
This function flushes @var{range-table}.
@end defun

@defun map-range-table function range-table
This function maps @var{function} over entries in @var{range-table},
calling it with three args, the beginning and end of the range and the
corresponding value.
@end defun