Unfinished work on figure Data Types.
[clqr.git] / clqr-sequences.tex
blob7210ec51b560f6f08dd9d8c7cc4fa74a2b28468a
1 % Copyright (C) 2008, 2009 Bert Burgemeister
3 % Permission is granted to copy, distribute and/or modify this
4 % document under the terms of the GNU Free Documentation License,
5 % Version 1.2 or any later version published by the Free Software
6 % Foundation; with no Invariant Sections, no Front-Cover Texts and
7 % no Back-Cover Texts. For details see file COPYING.
10 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
11 \section{Sequences}
12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
13 \label{section:Sequences}
15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
16 \subsection[Seq.~Predicates]{Sequence Predicates}
17 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
18 \begin{LIST}{1cm}
20 \IT{(\xorGOO{\FU*{EVERY}\\
21 \FU*{NOTEVERY}}{\}} \VAR{test}
22 \RP{\VAR{sequence}})}
24 Return \retval{\NIL} or \retval{\T}, respectively, as soon as \VAR{test} on
25 any set of corresponding elements of \VAR{sequence}s returns \NIL.
28 \IT{(\xorGOO{\FU*{SOME}\\
29 \FU*{NOTANY}}{\}} \VAR{test}
30 \RP{\VAR{sequence}})}
32 Return \retval{value of \VAR{test}} or \retval{\NIL}, respectively, as soon
33 as \VAR{test} on any set of corresponding elements of
34 \VAR{sequence}s returns non-\NIL.
37 \IT{(\FU*{MISMATCH} \VAR{sequence-a} \VAR{sequence-b}
38 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
39 \xorGOO{%
40 \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
41 \kwd{:test-not} \VAR{ function}}{.}\\
42 \kwd{:start1} \VAR{ start-a}\DF{\LIT{0}}\\
43 \kwd{:start2} \VAR{ start-b}\DF{\LIT{0}}\\
44 \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
45 \kwd{:end2} \VAR{ end-b}\DF{\NIL}\\
46 \kwd{:key} \VAR{ function}}{\}})}
48 Return \retval{position in \VAR{sequence-a}} where
49 \VAR{sequence-a} and \VAR{sequence-b} begin to
50 mismatch. Return \retval{\NIL} if
51 they match entirely.
54 \end{LIST}
56 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
57 \subsection[Seq.~Functions]{Sequence Functions}
58 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
60 \begin{LIST}{1cm}
62 \IT{(\FU*{MAKE-SEQUENCE} \VAR{sequence-type} \VAR{size}
63 \Op{\kwd{:initial-element} \VAR{foo}})} % default: implementation-dependent
65 Make \retval{sequence} of \VAR{sequence-type} with \VAR{size} elements.
68 \IT{(\FU*{CONCATENATE} \VAR{type} \OPn{\VAR{sequence}})}
70 Return \retval{concatenated sequence} of \VAR{type}.
73 \IT{(\FU*{MERGE} \VAR{type} \DES{\VAR{sequence-a}} \DES{\VAR{sequence-b}}
74 \VAR{test} \Op{\kwd{:key} \VAR{function}\DF{\NIL}})}
76 Return \retval{interleaved sequence} of \VAR{type}. Merged sequence
77 will be sorted if both \VAR{sequence-a} and \VAR{sequence-b} are
78 sorted.
81 \IT{(\FU*{FILL} \DES{\VAR{sequence}} \VAR{foo}
82 \orGOO{\kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
83 \kwd{:end} \VAR{ end}\DF{\NIL}}{\}})}
85 Return \retval{\VAR{sequence}} after setting elements between \VAR{start}
86 and \VAR{end} to \VAR{foo}.
89 \IT{(\FU*{LENGTH} \VAR{sequence})}
90 {Return \retval{length of
91 \VAR{sequence}} (being value of fill pointer if applicable).
94 \IT{(\FU*{COUNT} \VAR{foo} \VAR{sequence}
95 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
96 \xorGOO{%
97 \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
98 \kwd{:test-not} \VAR{ function}}{.}\\
99 \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
100 \kwd{:end} \VAR{ end}\DF{\NIL}\\
101 \kwd{:key} \VAR{ function}}{\}})}
103 Return \retval{number of elements} in \VAR{sequence} which match
104 \VAR{foo}.
107 \IT{(\xorGOO{\FU*{COUNT-IF}\\
108 \FU*{COUNT-IF-NOT}}{\}} \VAR{test} \VAR{sequence}
109 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
110 \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
111 \kwd{:end} \VAR{ end}\DF{\NIL}\\
112 \kwd{:key} \VAR{ function}}{\}})}
114 Return \retval{number of elements} in \VAR{sequence} which satisfy
115 \VAR{test}.
118 \IT{(\FU*{ELT} \VAR{sequence} \VAR{index})}
119 {Return \retval{element of
120 \VAR{sequence}} pointed to by zero-indexed
121 \VAR{index}. \kwd{setf}able.
124 \IT{(\FU*{SUBSEQ} \VAR{sequence} \VAR{start}
125 \Op{\VAR{end}\DF{\NIL}})}
127 Return \retval{subsequence of \VAR{sequence}} between \VAR{start}
128 and \VAR{end}. \kwd{setf}able.
131 \IT{(\xorGOO{\FU*{SORT}\\
132 \FU*{STABLE-SORT}}{\}} \DES{\VAR{sequence}} \VAR{test}
133 \Op{\kwd{:key} \VAR{function}})}
135 Return \retval{\VAR{sequence} sorted}. Order
136 of elements considered equal is not guaranteed/retained, respectively.
139 \IT{\arrGOO{(\FU*{REVERSE} \VAR{ sequence})\\
140 (\FU*{NREVERSE } \DES{\VAR{sequence}})}{.}}
142 Return \retval{\VAR{sequence} in reverse order}.
145 \IT{(\xorGOO{\FU*{FIND}\\
146 \FU*{POSITION}}{\}} \VAR{foo} \VAR{sequence}
147 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
148 \xorGOO{%
149 \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
150 \kwd{:test-not} \VAR{ test}}{.}\\
151 \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
152 \kwd{:end} \VAR{ end}\DF{\NIL}\\
153 \kwd{:key} \VAR{ function}}{\}})}
155 Return \retval{first element} in \VAR{sequence} which
156 matches \VAR{foo}, or its \retval{position} relative to the begin
157 of \VAR{sequence}, respectively.
160 \IT{(\xorGOO{\FU*{FIND-IF}\\
161 \FU*{FIND-IF-NOT}\\\FU*{POSITION-IF}\\
162 \FU*{POSITION-IF-NOT}}{\}} \VAR{test} \VAR{sequence}
163 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
164 \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
165 \kwd{:end} \VAR{ end}\DF{\NIL}\\
166 \kwd{:key} \VAR{ function}}{\}})}
168 Return \retval{first element} in \VAR{sequence} which satisfies \VAR{test}, or
169 its \retval{position} relative to the begin of \VAR{sequence}, respectively.
172 \IT{(\FU*{SEARCH} \VAR{sequence-a} \VAR{sequence-b}
173 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
174 \xorGOO{%
175 \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
176 \kwd{:test-not} \VAR{ function}}{.}\\
177 \kwd{:start1} \VAR{ start-a}\DF{\LIT{0}}\\
178 \kwd{:start2} \VAR{ start-b}\DF{\LIT{0}}\\
179 \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
180 \kwd{:end2} \VAR{ end-b}\DF{\NIL}\\
181 \kwd{:key} \VAR{ function}}{\}})}
183 Search \VAR{sequence-b} for a subsequence matching
184 \VAR{sequence-a}. Return \retval{position} in \VAR{sequence-b}, or
185 \retval{\NIL}.
188 \IT{(\xorGOO{\FU*{REMOVE} \VAR{ foo } \VAR{sequence}\\
189 \FU*{DELETE} \VAR{ foo } \DES{\VAR{sequence}}}{\}}
190 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
191 \xorGOO{%
192 \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
193 \kwd{:test-not} \VAR{ function}}{.}\\
194 \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
195 \kwd{:end} \VAR{ end}\DF{\NIL}\\
196 \kwd{:key} \VAR{ function}\\
197 \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
199 Make \retval{copy of \VAR{sequence}} without elements matching
200 \VAR{foo}.
203 \IT{(\xorGOO{%
204 \arrGOO{
205 \FU*{REMOVE-IF}\\
206 \FU*{REMOVE-IF-NOT}}{\}} \VAR{ test } \VAR{sequence}\\
207 \arrGOO{
208 \FU*{DELETE-IF}\\
209 \FU*{DELETE-IF-NOT}}{\}} \VAR{ test }
210 \DES{\VAR{sequence}}\text{ }}{\}}
211 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
212 \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
213 \kwd{:end} \VAR{ end}\DF{\NIL}\\
214 \kwd{:key} \VAR{ function}\\
215 \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
217 Make \retval{copy of \VAR{sequence}} with all (or \VAR{count}) elements
218 satisfying \VAR{test} removed.
221 \IT{(\xorGOO{\FU*{REMOVE-DUPLICATES} \VAR{ sequence }\\
222 \FU*{DELETE-DUPLICATES } \DES{\VAR{sequence}}}{\}}
223 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
224 \xorGOO{%
225 \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
226 \kwd{:test-not} \VAR{ function}}{.}\\
227 \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
228 \kwd{:end} \VAR{ end}\DF{\NIL}\\
229 \kwd{:key} \VAR{ function}}{\}})}
231 Make \retval{copy of \VAR{sequence}} without duplicates.
234 \IT{(\xorGOO{%
235 \FU*{SUBSTITUTE} \VAR{ new} \VAR{ old } \VAR{sequence} \\
236 \FU*{NSUBSTITUTE} \VAR{ new} \VAR{ old } \DES{\VAR{sequence}} }{\}}
237 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
238 \xorGOO{%
239 \kwd{:test} \VAR{ function}\DF{\kwd{\#'eql}}\\
240 \kwd{:test-not} \VAR{ function}}{.}\\
241 \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
242 \kwd{:end} \VAR{ end}\DF{\NIL}\\
243 \kwd{:key} \VAR{ function}\\
244 \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
246 Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
247 \VAR{old}s replaced by \VAR{new}.
250 \IT{(\xorGOO{%
251 \arrGOO{%
252 \FU*{SUBSTITUTE-IF}\\
253 \FU*{SUBSTITUTE-IF-NOT}}{\}}
254 \VAR{ new} \VAR{ test } \VAR{sequence}\\
255 \arrGOO{%
256 \FU*{NSUBSTITUTE-IF}\\
257 \FU*{NSUBSTITUTE-IF-NOT}}{\}}
258 \VAR{ new} \VAR{ test } \DES{\VAR{sequence}}\text{ }
259 }{\}}
260 \orGOO{\kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
261 \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
262 \kwd{:end} \VAR{ end}\DF{\NIL}\\
263 \kwd{:key} \VAR{ function}\\
264 \kwd{:count} \VAR{ count}\DF{\NIL}}{\}})}
266 Make \retval{copy of \VAR{sequence}} with all (or \VAR{count})
267 elements satisfying \VAR{test} replaced by
268 \VAR{new}.
271 \IT{(\FU*{REPLACE} \DES{\VAR{sequence-a}} \VAR{sequence-b}
272 \orGOO{\kwd{:start1} \VAR{ start-a}\DF{\LIT{0}}\\
273 \kwd{:start2} \VAR{ start-b}\DF{\LIT{0}}\\
274 \kwd{:end1} \VAR{ end-a}\DF{\NIL}\\
275 \kwd{:end2} \VAR{ end-b}\DF{\NIL}}{\}})}
277 Replace elements of \retval{\VAR{sequence-a}} with elements of
278 \VAR{sequence-b}.
281 \IT{(\FU*{MAP} \VAR{type} \VAR{function} \RP{\VAR{sequence}})}
283 Apply \VAR{function} successively to corresponding elements of the
284 \VAR{sequence}s. Return values as a \retval{sequence} of
285 \VAR{type}. If \VAR{type} is \NIL, return \retval{\NIL}.
288 \IT{(\FU*{MAP-INTO} \DES{\VAR{result-sequence}} \VAR{function}
289 \OPn{\VAR{sequence}})}
291 Store into \retval{\VAR{result-sequence}} successively values of
292 \VAR{function} applied to corresponding elements of the \VAR{sequence}s.
295 \IT{(\FU*{REDUCE} \VAR{function} \VAR{sequence}
296 \orGOO{\kwd{:initial-value} \VAR{ foo}\DF{\NIL}\\
297 \kwd{:from-end} \VAR{ bool}\DF{\NIL}\\
298 \kwd{:start} \VAR{ start}\DF{\LIT{0}}\\
299 \kwd{:end} \VAR{ end}\DF{\NIL}\\
300 \kwd{:key} \VAR{ function}}{\}})}
302 Starting with the first two elements of \VAR{sequence}, apply
303 \VAR{function} successively to its last return value together with the next
304 element of \VAR{sequence}. Return \retval{last value} of {function}.
307 \IT{(\FU*{COPY-SEQ} \VAR{sequence})}
309 Return \retval{copy of \VAR{sequence}} with shared elements.
313 \end{LIST}
317 %%% Local Variables:
318 %%% mode: latex
319 %%% TeX-master: "clqr"
320 %%% End: