|
0
|
1 @c -*-texinfo-*-
|
|
|
2 @c This is part of the XEmacs Lisp Reference Manual.
|
|
|
3 @c Copyright (C) 1996 Ben Wing.
|
|
|
4 @c See the file lispref.texi for copying conditions.
|
|
|
5 @setfilename ../../info/range-tables.info
|
|
|
6 @node Range Tables, Databases, Hash Tables, top
|
|
|
7 @chapter Range Tables
|
|
|
8 @cindex Range Tables
|
|
|
9
|
|
|
10 A range table is a table that efficiently associated values with
|
|
|
11 ranges of integers.
|
|
|
12
|
|
|
13 Note that range tables have a read syntax, like this:
|
|
|
14
|
|
|
15 @example
|
|
2421
|
16 #s(range-table type start-closed-end-open data ((-3 2) foo (5 20) bar))
|
|
0
|
17 @end example
|
|
|
18
|
|
2421
|
19 This maps integers in the range [-3, 2) to @code{foo} and integers
|
|
|
20 in the range [5, 20) to @code{bar}.
|
|
|
21
|
|
|
22 By default, range tables have a @var{type} of
|
|
|
23 @code{start-closed-end-open}. (@strong{NOTE}: This is a change from
|
|
|
24 21.4 and earlier, where there was no @var{type} and range tables were always
|
|
|
25 closed on both ends.) This makes them work like text properties.
|
|
0
|
26
|
|
|
27 @defun range-table-p object
|
|
|
28 Return non-@code{nil} if @var{object} is a range table.
|
|
|
29 @end defun
|
|
|
30
|
|
|
31 @menu
|
|
|
32 * Introduction to Range Tables:: Range tables efficiently map ranges of
|
|
|
33 integers to values.
|
|
|
34 * Working With Range Tables:: Range table functions.
|
|
|
35 @end menu
|
|
|
36
|
|
|
37 @node Introduction to Range Tables
|
|
|
38 @section Introduction to Range Tables
|
|
|
39
|
|
2421
|
40 @defun make-range-table &optional type
|
|
0
|
41 Make a new, empty range table.
|
|
2421
|
42
|
|
|
43 @var{type} is a symbol indicating how ranges are assumed to function
|
|
|
44 at their ends. It can be one of
|
|
|
45
|
|
|
46 @example
|
|
|
47 SYMBOL RANGE-START RANGE-END
|
|
|
48 ------ ----------- ---------
|
|
|
49 `start-closed-end-open' (the default) closed open
|
|
|
50 `start-closed-end-closed' closed closed
|
|
|
51 `start-open-end-open' open open
|
|
|
52 `start-open-end-closed' open closed
|
|
|
53 @end example
|
|
|
54
|
|
|
55 A @dfn{closed} endpoint of a range means that the number at that end
|
|
|
56 is included in the range. For an @dfn{open} endpoint, the number
|
|
|
57 would not be included.
|
|
|
58
|
|
|
59 For example, a closed-open range from 5 to 20 would be indicated as
|
|
|
60 @samp{[5, 20)} where a bracket indicates a closed end and a
|
|
|
61 parenthesis an open end, and would mean `all the numbers between 5 and
|
|
|
62 20', including 5 but not 20. This seems a little strange at first but
|
|
|
63 is in fact extremely common in the outside world as well as in
|
|
|
64 computers and makes things work sensibly. For example, if I say
|
|
|
65 "there are seven days between today and next week today", I'm
|
|
|
66 including today but not next week today; if I included both, there
|
|
|
67 would be eight days. Similarly, there are 15 (= 20 - 5) elements in
|
|
|
68 the range @samp{[5, 20)}, but 16 in the range @samp{[5, 20]}.
|
|
0
|
69 @end defun
|
|
|
70
|
|
444
|
71 @defun copy-range-table range-table
|
|
|
72 This function returns a new range table which contains the same values
|
|
|
73 for the same ranges as @var{range-table}. The values will not
|
|
|
74 themselves be copied.
|
|
0
|
75 @end defun
|
|
|
76
|
|
|
77 @node Working With Range Tables
|
|
|
78 @section Working With Range Tables
|
|
|
79
|
|
444
|
80 @defun get-range-table pos range-table &optional default
|
|
|
81 This function finds value for position @var{pos} in @var{range-table}.
|
|
|
82 If there is no corresponding value, return @var{default} (defaults to
|
|
0
|
83 @code{nil}).
|
|
2421
|
84
|
|
|
85 @strong{NOTE}: If you are working with ranges that are closed at the
|
|
|
86 start and open at the end (the default), and you put a value for a
|
|
|
87 range with @var{start} equal to @var{end}, @code{get-range-table} will
|
|
|
88 @strong{not} return that value! You would need to set @var{end} one
|
|
|
89 greater than @var{start}.
|
|
0
|
90 @end defun
|
|
|
91
|
|
444
|
92 @defun put-range-table start end value range-table
|
|
0
|
93 This function sets the value for range (@var{start}, @var{end}) to be
|
|
444
|
94 @var{value} in @var{range-table}.
|
|
2421
|
95
|
|
|
96 @strong{NOTE}: Unless you are working with ranges that are closed at
|
|
|
97 both ends, nothing will happen if @var{start} equals @var{end}.
|
|
0
|
98 @end defun
|
|
|
99
|
|
444
|
100 @defun remove-range-table start end range-table
|
|
0
|
101 This function removes the value for range (@var{start}, @var{end}) in
|
|
444
|
102 @var{range-table}.
|
|
0
|
103 @end defun
|
|
|
104
|
|
444
|
105 @defun clear-range-table range-table
|
|
|
106 This function flushes @var{range-table}.
|
|
0
|
107 @end defun
|
|
|
108
|
|
444
|
109 @defun map-range-table function range-table
|
|
|
110 This function maps @var{function} over entries in @var{range-table},
|
|
|
111 calling it with three args, the beginning and end of the range and the
|
|
0
|
112 corresponding value.
|
|
|
113 @end defun
|
|
|
114
|
