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[Seq.~Predicates
]{Sequence Predicates
}
17 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
20 \IT{(
\xorGOO{\FU*
{EVERY
}\\
21 \FU*
{NOTEVERY
}}{\
}} \VAR{test
}
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
}
32 Return
\retval{value of
\VAR{test
}} or
\retval{\NIL}, respectively, as soon
33 as
\VAR{test
} on any set of elements of
\VAR{sequence
}s returns non-
\NIL.
36 \IT{(
\FU*
{MISMATCH
} \VAR{sequence-a
} \VAR{sequence-b
}
37 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
38 \kwd{:test
} \VAR{ function
}\\
39 \kwd{:test-not
} \VAR{ function
}\\
40 \kwd{:start1
} \VAR{ start-a
}\DF{\LIT{0}}\\
41 \kwd{:start2
} \VAR{ start-b
}\DF{\LIT{0}}\\
42 \kwd{:end1
} \VAR{ end-a
}\DF{\NIL}\\
43 \kwd{:end2
} \VAR{ end-b
}\DF{\NIL}\\
44 \kwd{:key
} \VAR{ function
}}{\
}})
}
46 Return
\retval{position in
\VAR{sequence-a
}} where
47 \VAR{sequence-a
} and
\VAR{sequence-b
} begin to
48 mismatch. Return
\retval{\NIL} if
54 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
55 \subsection[Seq.~Functions
]{Sequence Functions
}
56 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
60 \IT{(
\FU*
{MAKE-SEQUENCE
} \VAR{sequence-type
} \VAR{size
}
61 \Op{\kwd{:initial-element
} \VAR{foo
}})
}
63 Make
\retval{sequence
} of
\VAR{sequence-type
} with
\VAR{size
} elements.
66 \IT{(
\FU*
{CONCATENATE
} \VAR{type
} \OPn{\VAR{sequence
}})
}
68 Return
\retval{concatenated sequence
} of
\VAR{type
}.
71 \IT{(
\FU*
{MERGE
} \VAR{type
} \DES{\VAR{sequence-a
}} \DES{\VAR{sequence-b
}}
72 \VAR{test
} \Op{\kwd{:key
} \VAR{function
}})
}
74 Return
\retval{interleaved sequence
} of
\VAR{type
}. Merged sequence
75 will be sorted if both
\VAR{sequence-a
} and
\VAR{sequence-b
} are
79 \IT{(
\FU*
{FILL
} \DES{\VAR{sequence
}} \VAR{foo
}
80 \orGOO{\kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
81 \kwd{:end
} \VAR{ end
}\DF{\NIL}}{\
}})
}
83 Return
\retval{\VAR{sequence
}} after setting elements between
\VAR{start
}
84 and
\VAR{end
} to
\VAR{foo
}.
87 \IT{(
\FU*
{LENGTH
} \VAR{sequence
})
}
88 {Return
\retval{length of
89 \VAR{sequence
}} (being value of fill pointer if applicable).
92 \IT{(
\FU*
{COUNT
} \VAR{foo
} \VAR{sequence
}
93 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
94 \kwd{:test
} \VAR{ function
}\\
95 \kwd{:test-not
} \VAR{ function
}\\
96 \kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
97 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
98 \kwd{:key
} \VAR{ function
}}{\
}})
}
100 Return
\retval{number of
\VAR{foo
}s in
\VAR{sequence
}} between
\VAR{start
}
101 and
\VAR{end
} satisfying tests.
104 \IT{(
\xorGOO{\FU*
{COUNT-IF
}\\
105 \FU*
{COUNT-IF-NOT
}}{\
}} \VAR{test
} \VAR{sequence
}
106 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
107 \kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
108 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
109 \kwd{:key
} \VAR{ function
}}{\
}})
}
111 Return
\retval{number of elements in
\VAR{sequence
}} between
\VAR{start
}
112 and
\VAR{end
} satisfying
\VAR{test
}.
115 \IT{(
\FU*
{ELT
} \VAR{sequence
} \VAR{index
})
}
116 {Return
\retval{element of
117 \VAR{sequence
}} pointed to by zero-indexed
\VAR{index
}.
\kwd{setf
}able.
120 \IT{(
\FU*
{SUBSEQ
} \VAR{sequence
} \VAR{start
}
121 \Op{\VAR{end
}\DF{\NIL}})
}
123 Return
\retval{subsequence of
\VAR{sequence
}} between
\VAR{start
}
124 and
\VAR{end
}.
\kwd{setf
}able.
127 \IT{(
\xorGOO{\FU*
{SORT
}\\
128 \FU*
{STABLE-SORT
}}{\
}} \DES{\VAR{sequence
}} \VAR{test
}
129 \Op{\kwd{:key
} \VAR{function
}})
}
131 Return
\retval{\VAR{sequence
} sorted
}. Order
132 of elements considered equal is not guaranteed/retained, respectively.
135 \IT{\arrGOO{(
\FU*
{REVERSE
} \VAR{ sequence
})\\
136 (
\FU*
{NREVERSE
} \DES{\VAR{sequence
}})
}{.
}}
138 Return
\retval{\VAR{sequence
} in reverse order
}.
141 \IT{(
\xorGOO{\FU*
{FIND
}\\
142 \FU*
{POSITION
}}{\
}} \VAR{foo
} \VAR{sequence
}
143 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
144 \kwd{:test
} \VAR{ function
}\\
145 \kwd{:test-not
} \VAR{ function
}\\
146 \kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
147 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
148 \kwd{:key
} \VAR{ function
}}{\
}})
}
150 Return
\retval{first element
} found in
\VAR{sequence
}, or
151 its
\retval{position
} relative to
\VAR{sequence
}'s start, respectively,
152 between
\VAR{start
} and
\VAR{end
} satisfying tests.
155 \IT{(
\xorGOO{\FU*
{FIND-IF
}\\
\FU*
{FIND-IF-NOT
}\\
\FU*
{POSITION-IF
}\\
\FU*
{POSITION-IF-NOT
}}{\
}} \VAR{test
} \VAR{sequence
}
156 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
157 \kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
158 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
159 \kwd{:key
} \VAR{ function
}}{\
}})
}
161 Return
\retval{first element in
\VAR{sequence
}}, or
162 \retval{its position
} relative to
\VAR{sequence
}'s start, respectively, between
\VAR{start
}
163 and
\VAR{end
} satisfying
\VAR{test
}.
166 \IT{(
\FU*
{SEARCH
} \VAR{sequence-a
} \VAR{sequence-b
}
167 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
168 \kwd{:test
} \VAR{ function
}\\
169 \kwd{:test-not
} \VAR{ function
}\\
170 \kwd{:start1
} \VAR{ start-a
}\DF{\LIT{0}}\\
171 \kwd{:start2
} \VAR{ start-b
}\DF{\LIT{0}}\\
172 \kwd{:end1
} \VAR{ end-a
}\DF{\NIL}\\
173 \kwd{:end2
} \VAR{ end-b
}\DF{\NIL}\\
174 \kwd{:key
} \VAR{ function
}}{\
}})
}
176 Search
\VAR{sequence-b
} for a subsequence matching
177 \VAR{sequence-a
}. Return
\retval{position
} in
\VAR{sequence-b
}, or
181 \IT{(
\xorGOO{\FU*
{REMOVE
} \VAR{ foo
} \VAR{sequence
}\\
182 \FU*
{DELETE
} \VAR{ foo
} \DES{\VAR{sequence
}}}{\
}}
183 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
184 \kwd{:test
} \VAR{ function
}\\
185 \kwd{:test-not
} \VAR{ function
}\\
186 \kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
187 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
188 \kwd{:key
} \VAR{ function
}\\
189 \kwd{:count
} \VAR{ count
}\DF{\NIL}}{\
}})
}
191 Make
\retval{copy of
\VAR{sequence
}} without elements matching
198 \FU*
{REMOVE-IF-NOT
}}{\
}} \VAR{ test
} \VAR{sequence
}\\
201 \FU*
{DELETE-IF-NOT
}}{\
}} \VAR{ test
}
202 \DES{\VAR{sequence
}}\text{ }}{\
}}
203 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
204 \kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
205 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
206 \kwd{:key
} \VAR{ function
}\\
207 \kwd{:count
} \VAR{ count
}\DF{\NIL}}{\
}})
}
209 Make
\retval{copy of
\VAR{sequence
}} with all (or
\VAR{count
}) elements
210 satisfying
\VAR{test
} removed.
213 \IT{(
\xorGOO{\FU*
{REMOVE-DUPLICATES
} \VAR{ sequence
}\\
214 \FU*
{DELETE-DUPLICATES
} \DES{\VAR{sequence
}}}{\
}}
215 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
216 \kwd{:test
} \VAR{ function
}\\
217 \kwd{:test-not
} \VAR{ function
}\\
218 \kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
219 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
220 \kwd{:key
} \VAR{ function
}}{\
}})
}
222 Make
\retval{copy of
\VAR{sequence
}} without duplicates.
226 \FU*
{SUBSTITUTE
} \VAR{ new
} \VAR{ old
} \VAR{sequence
} \\
227 \FU*
{NSUBSTITUTE
} \VAR{ new
} \VAR{ old
} \DES{\VAR{sequence
}} }{\
}}
228 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
229 \kwd{:test
} \VAR{ function
}\\
230 \kwd{:test-not
} \VAR{ function
}\\
231 \kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
232 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
233 \kwd{:key
} \VAR{ function
}\\
234 \kwd{:count
} \VAR{ count
}\DF{\NIL}}{\
}})
}
236 Make
\retval{copy of
\VAR{sequence
}} with all (or
\VAR{count
})
237 \VAR{old
}s replaced by
\VAR{new
}.
242 \FU*
{SUBSTITUTE-IF
}\\
243 \FU*
{SUBSTITUTE-IF-NOT
}}{\
}}
244 \VAR{ new
} \VAR{ test
} \VAR{sequence
}\\
246 \FU*
{NSUBSTITUTE-IF
}\\
247 \FU*
{NSUBSTITUTE-IF-NOT
}}{\
}}
248 \VAR{ new
} \VAR{ test
} \DES{\VAR{sequence
}}\text{ }
250 \orGOO{\kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
251 \kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
252 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
253 \kwd{:key
} \VAR{ function
}\\
254 \kwd{:count
} \VAR{ count
}\DF{\NIL}}{\
}})
}
256 Make
\retval{copy of
\VAR{sequence
}} with all (or
\VAR{count
})
257 elements satisfying
\VAR{test
} replaced by
261 \IT{(
\FU*
{REPLACE
} \DES{\VAR{sequence-a
}} \VAR{sequence-b
}
262 \orGOO{\kwd{:start1
} \VAR{ start-a
}\DF{\LIT{0}}\\
263 \kwd{:start2
} \VAR{ start-b
}\DF{\LIT{0}}\\
264 \kwd{:end1
} \VAR{ end-a
}\DF{\NIL}\\
265 \kwd{:end2
} \VAR{ end-b
}\DF{\NIL}}{\
}})
}
267 Replace elements of
\retval{\VAR{sequence-a
}} with elements of
271 \IT{(
\FU*
{MAP
} \VAR{type
} \VAR{function
} \RP{\VAR{sequence
}})
}
273 Apply
\VAR{function
} successively to corresponding elements of the
274 \VAR{sequence
}s. Return values as a
\retval{sequence
} of
275 \VAR{type
}. If
\VAR{type
} is
\NIL, return
\retval{\NIL}.
278 \IT{(
\FU*
{MAP-INTO
} \DES{\VAR{result-sequence
}} \VAR{function
}
279 \RP{\VAR{sequence
}})
}
281 Store into
\retval{\VAR{result-sequence
}} successively values of
282 \VAR{function
} applied to corresponding elements of the
\VAR{sequence
}s.
285 \IT{(
\FU*
{REDUCE
} \VAR{function
} \VAR{sequence
}
286 \orGOO{\kwd{:initial-value
} \VAR{ foo
}\DF{\NIL}\\
287 \kwd{:from-end
} \VAR{ bool
}\DF{\NIL}\\
288 \kwd{:start
} \VAR{ start
}\DF{\LIT{0}}\\
289 \kwd{:end
} \VAR{ end
}\DF{\NIL}\\
290 \kwd{:key
} \VAR{ function
}}{\
}})
}
292 Starting with the first two elements of
\VAR{sequence
}, apply
293 \VAR{function
} successively to its last return value together with the next
294 element of
\VAR{sequence
}. Return
\retval{last value
} of
{function
}.
297 \IT{(
\FU*
{COPY-SEQ
} \VAR{sequence
})
}
299 Return
\retval{copy of
\VAR{sequence
}} with the same elements.