source: project/wiki/eggref/5/cis @ 36464

Last change on this file since 36464 was 36464, checked in by Ivan Raikov, 19 months ago

cis doc

File size: 3.9 KB
Line 
1[[tags:egg]]
2[[toc:]]
3
4== Compact integer sets
5
6The {{cis}} library implements compact integer sets, represented as a
7list of integer intervals. The usual set operations are provided.  The
8advantage compared to ordered lists is that when many elements are
9contiguous, the actual size of the data structure may be much smaller
10than the cardinality of the set being represented. Most set operations
11are linear w.r.t. the size, not the cardinality of the set.
12
13
14== Usage
15
16(import cis)
17
18== Documentation
19
20=== Constants
21
22 empty :: CIS
23
24The empty integer set.
25
26=== Procedures
27
28<procedure>cis? :: OBJECT -> BOOL</procedure>
29
30Returns {{#t}} if the given object is a compact integer set, {{#f}} otherwise.
31
32<procedure>empty? :: CIS -> BOOL</procedure>
33
34Returns {{#t}} if the given integer set is empty, {{#f}} otherwise.
35
36<procedure> subset? :: CIS * CIS -> BOOL </procedure>
37
38Returns {{#t}} if the first given integer set is a subset of the
39second given integer set, {{#f}} otherwise.
40
41<procedure> cardinal :: CIS -> INTEGER </procedure>
42
43Returns the cardinality of the given set.
44
45<procedure> in? :: INTEGER * CIS -> BOOL </procedure>
46
47Returns {{#t}} if the the given integer is contained in the given set, {{#f}} otherwise.
48
49<procedure> singleton :: INTEGER -> CIS </procedure>
50
51Returns an integer set consisting of the given element.
52
53<procedure> interval :: INTEGER * INTEGER -> CIS </procedure>
54
55Returns an integer set consisting of the given interval of elements.
56
57<procedure> add :: INTEGER * CIS -> CIS </procedure>
58
59Adds the given element to the given set and returns the new set.
60
61<procedure> remove :: INTEGER * CIS -> CIS  </procedure>
62
63Removes the given element from the given set and returns the new set.
64
65<procedure> shift :: INTEGER * CIS -> CIS </procedure>
66
67Adds the given integer to all elements in the set and returns the new set.
68
69<procedure> union :: CIS * CIS -> CIS </procedure>
70
71Returns the union of the two sets.
72
73<procedure> intersection :: CIS * CIS -> CIS </procedure>
74
75Returns the intersection fo the two sets.
76
77<procedure> difference :: CIS * CIS -> CIS  </procedure>
78
79Subtracts the elements of the second given set from the elements of
80the first given set, and returns the resulting set.
81
82<procedure> get-min :: CIS -> INTEGER </procedure>
83
84Returns the minumum element of the set.
85
86<procedure> get-max :: CIS -> INTEGER </procedure>
87
88Returns the maximum element of the set.
89
90<procedure> foreach :: PROCEDURE * CIS -> VOID </procedure>
91
92Applies the given procedure to every element of the set.
93
94<procedure> fold-left :: PROCEDURE * INIT * CIS -> VALUE </procedure>
95
96Left fold on the elements of the set.
97
98<procedure> fold-right :: PROCEDURE * INIT * CIS -> VALUE </procedure>
99
100Right fold on the elements of the set.
101
102<procedure> elements :: CIS -> LIST </procedure>
103
104Returns a list containing all elements of the given set.
105
106== Examples
107
108  (define a (add 4 (add 1 (add 5 empty))))
109  (define b (add 3 (add 2 (add 8 empty))))
110  (elements a)
111 ==> (5 4 1)
112  (elements b)
113 ==> (8 3 2)
114  (elements (union a b))
115 ==> (8 5 4 3 2 1)
116 
117== About this egg
118
119
120=== Author
121
122{{cis}} is based on the Ocaml {{Cis}} library by Sébastien Ferré.  The
123Chicken Scheme variant of {{cis}} is implemented by
124[[/users/ivan-raikov|Ivan Raikov]].
125
126=== Version history
127
128; 1.3 : Ported to CHICKEN 5
129; 1.2 : Bug fix in union
130; 1.1 : Updated test script to return proper exit code
131; 1.0 : Initial release
132
133=== License
134
135 Copyright 2010-2018 Ivan Raikov
136 
137 This program is free software: you can redistribute it and/or modify
138 it under the terms of the GNU General Public License as published by
139 the Free Software Foundation, either version 3 of the License, or (at
140 your option) any later version.
141 
142 This program is distributed in the hope that it will be useful, but
143 WITHOUT ANY WARRANTY; without even the implied warranty of
144 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
145 General Public License for more details.
146 
147 A full copy of the GPL license can be found at
148 <http://www.gnu.org/licenses/>.
Note: See TracBrowser for help on using the repository browser.