1 % Copyright (C) 2008 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 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
12 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
13 \label{section:Sequences
}
15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
16 \subsection{Sequence Predicates
}
17 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
20 \IT{(
\xorGOO{\FU*
{EVERY
}\\
21 \FU*
{NOTEVERY
}}{\
}} \VAR{test
}
24 Return
\retval{\NIL} or
\retval{\T}, resp., as soon as
\VAR{test
} on
25 any set of corresponding elements of
\VAR{sequences
} returns
\NIL.
28 \IT{(
\xorGOO{\FU*
{NOTANY
}\\
\FU*
{SOME
}}{\
}} \VAR{test
}
31 Return
\retval{\NIL} or
\retval{value of
\VAR{test
}}, resp., as soon
32 as
\VAR{test
} on any set of elements of
\VAR{sequences
} returns non-
\NIL.
35 \IT{(
\FU*
{MISMATCH
} \VAR{sequence-a
} \VAR{sequence-b
}
36 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
37 \kwd{:test
} \VAR{ function
}\\
38 \kwd{:test-not
} \VAR{ function
}\\
39 \kwd{:key
} \VAR{ function
}\\
40 \kwd{:start1
} \VAR{ start-sequence-a
}\DF{0}\\
41 \kwd{:end1
} \VAR{ end-sequence-a
}\DF{\NIL}\\
42 \kwd{:start2
} \VAR{ start-sequence-b
}\DF{0}\\
43 \kwd{:end2
} \VAR{ end-sequence-b
}\DF{\NIL}}{\
}})
}
45 Return
\retval{position in
\VAR{sequence-a
}} where
46 \VAR{sequence-a
} and
\VAR{sequence-b
} begin to
47 mismatch. Return
\retval{\NIL} if
53 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54 \subsection{Sequence Functions
}
55 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
59 \IT{(
\FU*
{MAKE-SEQUENCE
} \VAR{sequence-type
} \VAR{size
}
60 \Op{\kwd{:initial-element
} \VAR{foo
}})
}
62 Make
\retval{sequence
} of
\VAR{sequence-type
} with
\VAR{size
} elements.
65 \IT{(
\FU*
{CONCATENATE
} \VAR{type
} \OPn{\VAR{sequence
}})
}
67 Return
\retval{concatenated sequence
} of
\VAR{type
}.
70 \IT{(
\FU*
{MERGE
} \VAR{type
} \VAR{sequence-a
} \VAR{sequence-b
}
71 \VAR{test
} \Op{\kwd{:key
} \VAR{function
}})
}
73 Return
\retval{interleaved sequence
} of
\VAR{type
}.
\VAR{sequence-a
}
74 and
\VAR{sequence-b
} are possibly modified. Merged sequence will be
75 sorted if both
\VAR{sequence-a
} and
\VAR{sequence-b
} are sorted.
78 \IT{(
\FU*
{FILL
} \VAR{sequence
} \VAR{foo
}
79 \orGOO{\kwd{:start
} \VAR{ start
}\DF{0}\\
80 \kwd{:end
} \VAR{ end
}\DF{\NIL}}{\
}})
}
82 Return
\retval{\VAR{sequence
}} with elements between
\VAR{start
}
83 and
\VAR{end
} set to
\VAR{foo
}.
\VAR{sequence
} is modified.
86 \IT{(
\FU*
{LENGTH
} \VAR{sequence
})
}
87 {Return
\retval{length of
88 \VAR{sequence
}} (being value of fill pointer if applicable).
91 \IT{(
\FU*
{COUNT
} \VAR{foo
} \VAR{sequence
}
92 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
93 \kwd{:test
} \VAR{ function
}\\
94 \kwd{:test-not
} \VAR{ function
}\\
95 \kwd{:start
} \VAR{ start
}\DF{0}\\
96 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
97 \kwd{:key
} \VAR{ function
}}{\
}})
}
99 Return
\retval{number of
\VAR{foo
}s in
\VAR{sequence
}} between
\VAR{start
}
100 and
\VAR{end
} satisfying tests.
103 \IT{(
\xorGOO{\FU*
{COUNT-IF
}\\
104 \FU*
{COUNT-IF-NOT
}}{\
}} \VAR{test
} \VAR{sequence
}
105 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
106 \kwd{:start
} \VAR{ start
}\DF{0}\\
107 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
108 \kwd{:key
} \VAR{ function
}}{\
}})
}
110 Return
\retval{number of elements in
\VAR{sequence
}} between
\VAR{start
}
111 and
\VAR{end
} satisfying
\VAR{test
}.
114 \IT{(
\FU*
{ELT
} \VAR{sequence
} \VAR{index
})
}
115 {Return
\retval{element of
116 \VAR{sequence
}} pointed to by
\VAR{index
}.
\kwd{setf
}able.
119 \IT{(
\FU*
{SUBSEQ
} \VAR{sequence
} \VAR{start
}
120 \Op{\VAR{end
}\DF{\NIL}})
}
122 Return
\retval{subsequence of
\VAR{sequence
}} between
\VAR{start
}
123 and
\VAR{end
}.
\kwd{setf
}able.
126 \IT{(
\xorGOO{\FU*
{SORT
}\\
\FU*
{STABLE-SORT
}}{\
}} \VAR{sequence
} \VAR{test
}
127 \Op{\kwd{:key
} \VAR{function
}})
}
129 Return
\retval{sorted sequence
}.
\VAR{sequence
} is modified. Order
130 of elements considered equal is not guaranteed/retained, resp.
133 \IT{\arrGOO{(
\FU*
{REVERSE
} \VAR{ sequence
})\\(
\FU*
{NREVERSE
} \VAR{
136 Return
\retval{\VAR{sequence
} in reverse order
}.
\VAR{sequence
} is
137 unmodified/possibly modified, resp.
140 \IT{(
\xorGOO{\FU*
{FIND
}\\
141 \FU*
{POSITION
}}{\
}} \VAR{foo
} \VAR{sequence
}
142 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
143 \kwd{:test
} \VAR{ function
}\\
144 \kwd{:test-not
} \VAR{ function
}\\
145 \kwd{:start
} \VAR{ start
}\DF{0}\\
146 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
147 \kwd{:key
} \VAR{ function
}}{\
}})
}
149 Return
\retval{first element
} found in
\VAR{sequence
}, or
150 its
\retval{position
} relative to
\VAR{sequence
}'s start, resp.,
151 between
\VAR{start
} and
\VAR{end
} satisfying tests.
154 \IT{(
\xorGOO{\FU*
{FIND-IF
}\\
\FU*
{FIND-IF-NOT
}\\
\FU*
{POSITION-IF
}\\
\FU*
{POSITION-IF-NOT
}}{\
}} \VAR{test
} \VAR{sequence
}
155 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
156 \kwd{:start
} \VAR{ start
}\DF{0}\\
157 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
158 \kwd{:key
} \VAR{ function
}}{\
}})
}
160 Return
\retval{first element in
\VAR{sequence
}}, or
161 \retval{its position
} relative to
\VAR{sequence
}'s start, resp., between
\VAR{start
}
162 and
\VAR{end
} satisfying
\VAR{test
}.
165 \IT{(
\FU*
{SEARCH
} \VAR{sequence-a
} \VAR{sequence-b
}
166 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
167 \kwd{:test
} \VAR{ function
}\\
168 \kwd{:test-not
} \VAR{ function
}\\
169 \kwd{:start1
} \VAR{ start-a
}\DF{0}\\
170 \kwd{:start2
} \VAR{ start-b
}\DF{0}\\
171 \kwd{:end1
} \VAR{ end-a
}\DF{\NIL}\\
172 \kwd{:end2
} \VAR{ end-b
}\DF{\NIL}\\
173 \kwd{:key
} \VAR{ function
}}{\
}})
}
175 Search
\VAR{sequence-b
} for a subsequence matching
176 \VAR{sequence-a
}. Return
\retval{position
} in
\VAR{sequence-b
}, or
180 \IT{(
\xorGOO{\FU*
{REMOVE
}\\
\FU*
{DELETE
}}{\
}} \VAR{foo
} \VAR{sequence
}
181 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
182 \kwd{:test
} \VAR{ function
}\\
183 \kwd{:test-not
} \VAR{ function
}\\
184 \kwd{:start
} \VAR{ start
}\DF{0}\\
185 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
186 \kwd{:key
} \VAR{ function
}\\
187 \kwd{:count
} \VAR{ count
}\DF{\NIL}}{\
}})
}
189 Make
\retval{copy of
\VAR{sequence
}} without elements matching
190 \VAR{foo
}.
\VAR{sequence
} is unmodified/possibly modified, resp.
193 \IT{(
\xorGOO{\FU*
{REMOVE-IF
}\\
\FU*
{REMOVE-IF-NOT
}\\
194 \FU*
{DELETE-IF
}\\
\FU*
{DELETE-IF-NOT
}}{\
}}
195 \VAR{test
} \VAR{sequence
}
196 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
197 \kwd{:start
} \VAR{ start
}\DF{0}\\
198 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
199 \kwd{:key
} \VAR{ function
}\\
200 \kwd{:count
} \VAR{ count
}\DF{\NIL}}{\
}})
}
202 Make
\retval{copy of
\VAR{sequence
}} with all (or
\VAR{count
}) elements
203 satisfying test or not satisfying test, resp., removed.
204 \VAR{sequence
} is unmodified/possibly modified, resp.
207 \IT{(
\xorGOO{\FU*
{REMOVE-DUPLICATES
}\\
\FU*
{DELETE-DUPLICATES
}}{\
}} \VAR{sequence
}
208 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
209 \kwd{:test
} \VAR{ function
}\\
210 \kwd{:test-not
} \VAR{ function
}\\
211 \kwd{:start
} \VAR{ start
}\DF{0}\\
212 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
213 \kwd{:key
} \VAR{ function
}}{\
}})
}
216 \VAR{sequence
}} without duplicates.
\VAR{sequence
} is unmodified/possibly
220 \IT{(
\xorGOO{\FU*
{SUBSTITUTE
}\\
\FU*
{NSUBSTITUTE
}}{\
}} \VAR{new
}
221 \VAR{old
} \VAR{foo
} \VAR{sequence
}
222 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
223 \kwd{:test
} \VAR{ function
}\\
224 \kwd{:test-not
} \VAR{ function
}\\
225 \kwd{:start
} \VAR{ start
}\DF{0}\\
226 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
227 \kwd{:key
} \VAR{ function
}\\
228 \kwd{:count
} \VAR{ count
}\DF{\NIL}}{\
}})
}
230 Make
\retval{copy of
\VAR{sequence
}} with all (or
\VAR{count
})
231 \VAR{old
}s replaced by
\VAR{new
}.
\VAR{sequence
} is
232 unmodified/possibly modified, resp.
235 \IT{(
\xorGOO{\FU*
{SUBSTITUTE-IF
}\\
\FU*
{SUBSTITUTE-IF-NOT
}\\
236 \FU*
{NSUBSTITUTE-IF
}\\
\FU*
{NSUBSTITUTE-IF-NOT
}}{\
}}
237 \VAR{new
} \VAR{test
} \VAR{sequence
}
238 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
239 \kwd{:start
} \VAR{ start
}\DF{0}\\
240 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
241 \kwd{:key
} \VAR{ function
}\\
242 \kwd{:count
} \VAR{ count
}\DF{\NIL}}{\
}})
}
244 Make
\retval{copy of
\VAR{sequence
}} with all (or
\VAR{count
})
245 elements satisfying test or not satisfying test, resp., replaced by
246 \VAR{new
}.
\VAR{sequence
} is unmodified/possibly modified, resp.
249 \IT{(
\FU*
{REPLACE
} \VAR{sequence-a
} \VAR{sequence-b
}
250 \orGOO{\kwd{:start1
} \VAR{ start-a
}\DF{0}\\
251 \kwd{:start2
} \VAR{ start-b
}\DF{0}\\
252 \kwd{:end1
} \VAR{ end-a
}\DF{\NIL}\\
253 \kwd{:end2
} \VAR{ end-b
}\DF{\NIL}}{\
}})
}
255 Destructively replace elements of
\retval{\VAR{sequence-a
}} with elements of
259 \IT{(
\FU*
{MAP
} \VAR{type
} \VAR{function
} \RP{\VAR{sequence
}})
}
261 Apply
\VAR{function
} successively to corresponding elements of the
262 \VAR{sequence
}s. Return values as a
\retval{sequence of
263 \VAR{type
}}. If
\VAR{type
} is
\NIL, return
\retval{\NIL}.
266 \IT{(
\FU*
{MAP-INTO
} \VAR{result-sequence
} \VAR{function
}
267 \RP{\VAR{sequence
}})
}
269 Modify
\retval{\VAR{result-sequence
}} successively by applying
270 \VAR{function
} to corresponding elements of the
\VAR{sequence
}s.
273 \IT{(
\FU*
{REDUCE
} \VAR{function
} \VAR{sequence
}
274 \orGOO{\kwd{:initial-value
} \VAR{ foo
}\DF{\NIL}\\
275 \kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
276 \kwd{:start
} \VAR{ start
}\DF{0}\\
277 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
278 \kwd{:key
} \VAR{ function
}}{\
}})
}
280 Starting with the first two elements of
\VAR{sequence
}, apply
281 \VAR{function
} successively to its last return value together with the next
282 element of
\VAR{sequence
}. Return
\retval{last value of
{function
}}.
285 \IT{(
\FU*
{COPY-SEQ
} \VAR{sequence
})
}
287 Return
\retval{copy of
\VAR{sequence
}} with the same elements.