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
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
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
134
136
137 This program is free software: you can redistribute it and/or modify