# source:project/wiki/eggref/4/iset@13306

Last change on this file since 13306 was 13306, checked in by felix winkelmann, 12 years ago

File size: 8.4 KB
Line
1[[tags: egg]]
2
3== iset
4
5[[toc:]]
6
7=== Description
8
9Integer sets.
10
11=== Author
12
13[[Alex Shinn]]
14
15=== Requirements
16
17None
18
19=== Documentation
20
21==== Bit-vectors
22
23Bit-vectors provide an abstract interface to bitwise operations
24typically done with integers.  They may in fact be implemented as
25integers on implementations with bignums, or they may be implemented
26by other means such as vectors which may be more efficient.  These
27vectors are meant to be used as flags and sets, not integer values,
28and thus are operations are ones-complement (there are no negative
29bit-vectors).
30
31===== Creating bit-vectors
32
33<procedure>(make-bit-vector size)</procedure>
34
35A 'zero' bit-vector, with a hint that we wish to use {{SIZE}} bits.
36
37<procedure>(make-bit-vector size #t)</procedure>
38
39Same as above but initialize the all bit elements to {{#t}} (= the integer
402^SIZE-1)
41
42<procedure>(integer->bit-vector n)</procedure>
43
44Create a bit-vector with bits initialized to the corresponds bits in
45fixnum N
46
47<procedure>(bit-vector-copy bv)</procedure>
48
49Make a copy of the bit-vector BV
50
51===== Bit-vector predicates
52
53<procedure>(bit-vector? obj)</procedure>
54
55{{#t}} iff OBJ is a valid bit-vector, which is not necessarily a disjoint
56type
57
58<procedure>(bit-vector-empty? bv)</procedure>
59
60{{#t}} iff BV has no bits set (the bit-vector equivalent of the ZERO?
61procedure)
62
63<procedure>(bit-vector-full? bv to)</procedure>
64
65{{#t}} iff BV has all bits lower than TO set (the low end is 2^i-1)
66
67The individual bits in the vector are accessed and set as boolean
68values:
69
70===== Accessing bit-vector elements
71
72<procedure>(bit-vector-ref bv i)</procedure>
73
74{{#t}} if the I-th bit in BV is set, else {{#f}}
75
76<procedure>(bit-vector-set bv i x)</procedure>
77
78Return a new copy of BV with the I-th bit set to boolean x (off iff X
79is {{#f}})
80
81<procedure>(bit-vector-set! bv i x)</procedure>
82
83In-place update version of the above, is allowed but not required to
84mutate BV
85
86===== Bitwise operations on bit-vectors
87
88The following procedures are direct analogues of the corresponding
89SRFI-33 bitwise operations:
90
91<procedure>(bit-vector-length bv)</procedure>
92
93{{integer-length}}: the index of the largest bit set in BV
94
95<procedure>(bit-vector-count bv)</procedure>
96
97{{bit-count}}: the number of set bits in BV
98
99<procedure>(bit-vector-shift bv n)</procedure>
100
101{{arithmetic-shift}}
102
103<procedure>(bit-vector-and bv ...)</procedure>
104
105{{bitwise-and}}
106
107<procedure>(bit-vector-ior bv ...)</procedure>
108
109{{bitwise-ior}}
110
111<procedure>(bit-vector-xor bv ...)</procedure>
112
113{{bitwise-xor}}
114
115<procedure>(bit-vector-eqv bv ...)</procedure>
116
117{{bitwise-eqv}}
118
119<procedure>(bit-vector-nand bv ...)</procedure>
120
121{{bitwise-nand}}
122
123<procedure>(bit-vector-nor bv ...)</procedure>
124
125{{bitwise-nor}}
126
127The following in-place update equivalents are also available, which
128are allowed, but not required, to mutate their first argument only:
129
130<procedure>(bit-vector-shift! bv n)</procedure>
131<procedure>(bit-vector-and! bv ...)</procedure>
132<procedure>(bit-vector-ior! bv ...)</procedure>
133<procedure>(bit-vector-xor! bv ...)</procedure>
134<procedure>(bit-vector-eqv! bv ...)</procedure>
135<procedure>(bit-vector-nand! bv ...)</procedure>
136<procedure>(bit-vector-nor! bv ...)</procedure>
137
138==== Integer sets
139
140An integer set is a set of exact integers optimized for minimal space
141usage and fast membership lookup.  General set operations are provided
142based on the character set operations found in SRFI-14.
143
144===== Creating isets
145
146<procedure>(make-iset)</procedure>
147
148An empty integer set.
149
150<procedure>(make-iset n)</procedure>
151
152A set of the single integer N.
153
154<procedure>(make-iset n m)</procedure>
155
156A set of the range of all integers from N-M inclusive.
157
158===== SRFI-14 analogues
159
160The following procedures are provided as direct analogs of the SRFI-14
161procedures, accepting and returning isets and integers in place of
162char-sets and characters:
163
164<procedure>(iset-copy is)</procedure>
165
166A new copy of IS
167
168<procedure>(iset n ...)</procedure>
169
170An iset containing the elements N...
171
172<procedure>(list->iset ls [base-is])</procedure>
173
174An iset containing all the integers in list LS, union BASE-IS if
175provided
176
177<procedure>(list->iset! ls base-is)</procedure>
178
179Same as above, allowed but not required to modify base-is
180
181<procedure>(iset-size is)</procedure>
182
183Return the # of elements in IS
184
185<procedure>(iset-contains? is n)</procedure>
186
187Test N for membership in IS
188
189<procedure>(iset->list is)</procedure>
190
191Returns a list of all integers in IS
192
193<procedure>(iset-any pred is)</procedure>
194
195Apply PRED to every element of IS, returning the first element it
196finds (order unspecified)
197
198<procedure>(iset-every pred is)</procedure>
199
200Returns {{#t}} if every element of IS satisfies the predicate PRED (order
201unspecified)
202
203<procedure>(iset? obj)</procedure>
204
205{{#t}} iff obj is an integer set.
206
207<procedure>(iset= is ...)</procedure>
208
209{{#t}} iff all arguments are equivalent integer sets.
210
211<procedure>(iset<= is ...)</procedure>
212
213{{#t}} iff the arguments are monotonically increasing sets.
214
215<procedure>(iset>= is ...)</procedure>
216
217{{#t}} iff the arguments are monotonically decreasing sets.
218
219<procedure>(iset-fold kons knil is)</procedure>
220
221{{char-set-fold}}
222
223<procedure>(iset-unfold f p g [base-is])</procedure>
224
225{{char-set-unfold}}
226
227<procedure>(iset-unfold! f p g base-is)</procedure>
228
229{{char-set-unfold!}}
230
231<procedure>(iset-for-each proc is)</procedure>
232
233{{char-set-for-each}}
234
235<procedure>(iset-map proc is)</procedure>
236
237{{char-set-map}}
238
239<procedure>(iset-filter pred is [bas-is])</procedure>
240
241{{char-set-filter}}
242
243<procedure>(iset-filter! pred is base-is)</procedure>
244
245{{char-set-filter!}}
246
247<procedure>(iset-cursor iset)</procedure>
248<procedure>(iset-ref iset cursor)</procedure>
249<procedure>(iset-cursor-next iset cursor)</procedure>
250<procedure>(end-of-iset? iset)</procedure>
251
252Cursor-based traversal of isets.
253
255
257
258<procedure>(iset-delete is n ...)</procedure>
259
260{{char-set-delete}}
261
263
265
266<procedure>(iset-delete! is n ...)</procedure>
267
268{{char-set-delete!}}
269
270<procedure>(iset-union is1 ...)</procedure>
271
272{{char-set-union}}
273
274<procedure>(iset-intersection is1 ...)</procedure>
275
276{{char-set-intersection}}
277
278<procedure>(iset-difference is1 is2 ...)</procedure>
279
280{{char-set-difference}}
281
282<procedure>(iset-xor is1 ...)</procedure>
283
284{{char-set-xor}}
285
286<procedure>(iset-diff+intersection is1 is2 ...)</procedure>
287
288{{char-set-diff+intersection}}
289
290<procedure>(iset-union! is1 ...)</procedure>
291
292{{char-set-union!}}
293
294<procedure>(iset-intersection! is1 ...)</procedure>
295
296{{char-set-intersection!}}
297
298<procedure>(iset-difference! is1 is2 ...)</procedure>
299
300{{char-set-difference!}}
301
302<procedure>(iset-xor! is1 ...)</procedure>
303
304{{char-set-xor!}}
305
306<procedure>(iset-diff+intersection! is1 is2 ...)</procedure>
307
308{{char-set-diff+intersection!}}
309
310=== Changelog
311
312* 1.5 Port to hygienic chicken, fix overflow bug in bit-vector-full? [Peter Bex]
313* 1.4 Workaround in {{bit-vector-copy}} for zero-length vectors.
314* 1.3 Fixed {{bit-vector-copy}} export but no define [by Kon Lovett]
315* 1.2 Added {{iset-optimize}} and {{iset-balance}}, fixed some bugs
317* 1.0 Initial release
318
320
321  Copyright (c) 2004-2006, Alex Shinn
323
324  Redistribution and use in source and binary forms, with or without
325  modification, are permitted provided that the following conditions
326  are met:
327  1. Redistributions of source code must retain the above copyright
328     notice, this list of conditions and the following disclaimer.
329  2. Redistributions in binary form must reproduce the above copyright
330     notice, this list of conditions and the following disclaimer in the
331     documentation and/or other materials provided with the distribution.
332  3. The name of the author may not be used to endorse or promote products
333     derived from this software without specific prior written permission.
334
335  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
336  IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
337  OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
338  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
339  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
340  NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
341  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
342  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
343  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
344  THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Note: See TracBrowser for help on using the repository browser.