Commit | Line | Data |
---|---|---|
ee6aac97 MD |
1 | /* srfi-1.c --- SRFI-1 procedures for Guile |
2 | * | |
a030cb4b | 3 | * Copyright (C) 1995, 1996, 1997, 2000, 2001, 2002, 2003, 2005, 2006, 2008 |
cf9d3c47 KR |
4 | * Free Software Foundation, Inc. |
5 | * | |
73be1d9e | 6 | * This library is free software; you can redistribute it and/or |
53befeb7 NJ |
7 | * modify it under the terms of the GNU Lesser General Public License |
8 | * as published by the Free Software Foundation; either version 3 of | |
9 | * the License, or (at your option) any later version. | |
ee6aac97 | 10 | * |
53befeb7 NJ |
11 | * This library is distributed in the hope that it will be useful, but |
12 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
73be1d9e MV |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
14 | * Lesser General Public License for more details. | |
ee6aac97 | 15 | * |
73be1d9e MV |
16 | * You should have received a copy of the GNU Lesser General Public |
17 | * License along with this library; if not, write to the Free Software | |
53befeb7 NJ |
18 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
19 | * 02110-1301 USA | |
73be1d9e | 20 | */ |
ee6aac97 | 21 | |
dbb605f5 | 22 | #ifdef HAVE_CONFIG_H |
a030cb4b LC |
23 | # include <config.h> |
24 | #endif | |
25 | ||
ee6aac97 MD |
26 | #include <libguile.h> |
27 | #include <libguile/lang.h> | |
28 | ||
29 | #include "srfi-1.h" | |
30 | ||
31 | /* The intent of this file is to gradually replace those Scheme | |
32 | * procedures in srfi-1.scm which extends core primitive procedures, | |
33 | * so that using srfi-1 won't have performance penalties. | |
34 | * | |
35 | * Please feel free to contribute any new replacements! | |
36 | */ | |
37 | ||
38 | static long | |
39 | srfi1_ilength (SCM sx) | |
40 | { | |
41 | long i = 0; | |
42 | SCM tortoise = sx; | |
43 | SCM hare = sx; | |
44 | ||
45 | do { | |
46 | if (SCM_NULL_OR_NIL_P(hare)) return i; | |
896df2d5 | 47 | if (!scm_is_pair (hare)) return -2; |
ee6aac97 MD |
48 | hare = SCM_CDR(hare); |
49 | i++; | |
50 | if (SCM_NULL_OR_NIL_P(hare)) return i; | |
896df2d5 | 51 | if (!scm_is_pair (hare)) return -2; |
ee6aac97 MD |
52 | hare = SCM_CDR(hare); |
53 | i++; | |
54 | /* For every two steps the hare takes, the tortoise takes one. */ | |
55 | tortoise = SCM_CDR(tortoise); | |
56 | } | |
bc36d050 | 57 | while (! scm_is_eq (hare, tortoise)); |
ee6aac97 MD |
58 | |
59 | /* If the tortoise ever catches the hare, then the list must contain | |
60 | a cycle. */ | |
61 | return -1; | |
62 | } | |
63 | ||
d0a634de KR |
64 | static SCM |
65 | equal_trampoline (SCM proc, SCM arg1, SCM arg2) | |
66 | { | |
67 | return scm_equal_p (arg1, arg2); | |
68 | } | |
69 | ||
cf9d3c47 KR |
70 | /* list_copy_part() copies the first COUNT cells of LST, puts the result at |
71 | *dst, and returns the SCM_CDRLOC of the last cell in that new list. | |
72 | ||
73 | This function is designed to be careful about LST possibly having changed | |
74 | in between the caller deciding what to copy, and the copy actually being | |
75 | done here. The COUNT ensures we terminate if LST has become circular, | |
76 | SCM_VALIDATE_CONS guards against a cdr in the list changed to some | |
77 | non-pair object. */ | |
78 | ||
79 | #include <stdio.h> | |
80 | static SCM * | |
81 | list_copy_part (SCM lst, int count, SCM *dst) | |
82 | #define FUNC_NAME "list_copy_part" | |
83 | { | |
84 | SCM c; | |
85 | for ( ; count > 0; count--) | |
86 | { | |
87 | SCM_VALIDATE_CONS (SCM_ARGn, lst); | |
88 | c = scm_cons (SCM_CAR (lst), SCM_EOL); | |
89 | *dst = c; | |
90 | dst = SCM_CDRLOC (c); | |
91 | lst = SCM_CDR (lst); | |
92 | } | |
93 | return dst; | |
94 | } | |
95 | #undef FUNC_NAME | |
96 | ||
d0a634de | 97 | |
b1fff4e7 KR |
98 | SCM_DEFINE (scm_srfi1_alist_copy, "alist-copy", 1, 0, 0, |
99 | (SCM alist), | |
100 | "Return a copy of @var{alist}, copying both the pairs comprising\n" | |
101 | "the list and those making the associations.") | |
102 | #define FUNC_NAME s_scm_srfi1_alist_copy | |
103 | { | |
104 | SCM ret, *p, elem, c; | |
105 | ||
106 | /* ret is the list to return. p is where to append to it, initially &ret | |
107 | then SCM_CDRLOC of the last pair. */ | |
108 | ret = SCM_EOL; | |
109 | p = &ret; | |
110 | ||
111 | for ( ; scm_is_pair (alist); alist = SCM_CDR (alist)) | |
112 | { | |
113 | elem = SCM_CAR (alist); | |
114 | ||
115 | /* each element of alist must be a pair */ | |
116 | SCM_ASSERT_TYPE (scm_is_pair (elem), alist, SCM_ARG1, FUNC_NAME, | |
117 | "association list"); | |
118 | ||
119 | c = scm_cons (scm_cons (SCM_CAR (elem), SCM_CDR (elem)), SCM_EOL); | |
120 | *p = c; | |
121 | p = SCM_CDRLOC (c); | |
122 | } | |
123 | ||
124 | /* alist must be a proper list */ | |
125 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (alist), alist, SCM_ARG1, FUNC_NAME, | |
126 | "association list"); | |
127 | return ret; | |
128 | } | |
129 | #undef FUNC_NAME | |
130 | ||
131 | ||
9a993171 KR |
132 | |
133 | SCM_DEFINE (scm_srfi1_append_reverse, "append-reverse", 2, 0, 0, | |
134 | (SCM revhead, SCM tail), | |
135 | "Reverse @var{rev-head}, append @var{tail} to it, and return the\n" | |
136 | "result. This is equivalent to @code{(append (reverse\n" | |
137 | "@var{rev-head}) @var{tail})}, but its implementation is more\n" | |
138 | "efficient.\n" | |
139 | "\n" | |
140 | "@example\n" | |
141 | "(append-reverse '(1 2 3) '(4 5 6)) @result{} (3 2 1 4 5 6)\n" | |
142 | "@end example") | |
143 | #define FUNC_NAME s_scm_srfi1_append_reverse | |
144 | { | |
145 | while (scm_is_pair (revhead)) | |
146 | { | |
147 | /* copy first element of revhead onto front of tail */ | |
148 | tail = scm_cons (SCM_CAR (revhead), tail); | |
149 | revhead = SCM_CDR (revhead); | |
150 | } | |
151 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (revhead), revhead, SCM_ARG1, FUNC_NAME, | |
152 | "list"); | |
153 | return tail; | |
154 | } | |
155 | #undef FUNC_NAME | |
156 | ||
157 | ||
158 | SCM_DEFINE (scm_srfi1_append_reverse_x, "append-reverse!", 2, 0, 0, | |
159 | (SCM revhead, SCM tail), | |
160 | "Reverse @var{rev-head}, append @var{tail} to it, and return the\n" | |
161 | "result. This is equivalent to @code{(append! (reverse!\n" | |
162 | "@var{rev-head}) @var{tail})}, but its implementation is more\n" | |
163 | "efficient.\n" | |
164 | "\n" | |
165 | "@example\n" | |
166 | "(append-reverse! (list 1 2 3) '(4 5 6)) @result{} (3 2 1 4 5 6)\n" | |
167 | "@end example\n" | |
168 | "\n" | |
169 | "@var{rev-head} may be modified in order to produce the result.") | |
170 | #define FUNC_NAME s_scm_srfi1_append_reverse_x | |
171 | { | |
172 | SCM newtail; | |
173 | ||
174 | while (scm_is_pair (revhead)) | |
175 | { | |
176 | /* take the first cons cell from revhead */ | |
177 | newtail = revhead; | |
178 | revhead = SCM_CDR (revhead); | |
179 | ||
180 | /* make it the new start of tail, appending the previous */ | |
181 | SCM_SETCDR (newtail, tail); | |
182 | tail = newtail; | |
183 | } | |
184 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (revhead), revhead, SCM_ARG1, FUNC_NAME, | |
185 | "list"); | |
186 | return tail; | |
187 | } | |
188 | #undef FUNC_NAME | |
189 | ||
190 | ||
6e9f3c26 KR |
191 | SCM_DEFINE (scm_srfi1_break, "break", 2, 0, 0, |
192 | (SCM pred, SCM lst), | |
193 | "Return two values, the longest initial prefix of @var{lst}\n" | |
194 | "whose elements all fail the predicate @var{pred}, and the\n" | |
195 | "remainder of @var{lst}.\n" | |
196 | "\n" | |
197 | "Note that the name @code{break} conflicts with the @code{break}\n" | |
198 | "binding established by @code{while}. Applications wanting to\n" | |
199 | "use @code{break} from within a @code{while} loop will need to\n" | |
200 | "make a new define under a different name.") | |
201 | #define FUNC_NAME s_scm_srfi1_break | |
202 | { | |
203 | scm_t_trampoline_1 pred_tramp; | |
204 | SCM ret, *p; | |
205 | ||
206 | pred_tramp = scm_trampoline_1 (pred); | |
207 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
208 | ||
209 | ret = SCM_EOL; | |
210 | p = &ret; | |
211 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
212 | { | |
213 | SCM elem = SCM_CAR (lst); | |
214 | if (scm_is_true (pred_tramp (pred, elem))) | |
215 | goto done; | |
216 | ||
217 | /* want this elem, tack it onto the end of ret */ | |
218 | *p = scm_cons (elem, SCM_EOL); | |
219 | p = SCM_CDRLOC (*p); | |
220 | } | |
221 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
222 | ||
223 | done: | |
224 | return scm_values (scm_list_2 (ret, lst)); | |
225 | } | |
226 | #undef FUNC_NAME | |
227 | ||
228 | ||
229 | SCM_DEFINE (scm_srfi1_break_x, "break!", 2, 0, 0, | |
230 | (SCM pred, SCM lst), | |
231 | "Return two values, the longest initial prefix of @var{lst}\n" | |
232 | "whose elements all fail the predicate @var{pred}, and the\n" | |
233 | "remainder of @var{lst}. @var{lst} may be modified to form the\n" | |
234 | "return.") | |
235 | #define FUNC_NAME s_scm_srfi1_break_x | |
236 | { | |
237 | SCM upto, *p; | |
238 | scm_t_trampoline_1 pred_tramp; | |
239 | ||
240 | pred_tramp = scm_trampoline_1 (pred); | |
241 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
242 | ||
243 | p = &lst; | |
244 | for (upto = lst; scm_is_pair (upto); upto = SCM_CDR (upto)) | |
245 | { | |
246 | if (scm_is_true (pred_tramp (pred, SCM_CAR (upto)))) | |
247 | goto done; | |
248 | ||
249 | /* want this element */ | |
250 | p = SCM_CDRLOC (upto); | |
251 | } | |
252 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto), lst, SCM_ARG2, FUNC_NAME, "list"); | |
253 | ||
254 | done: | |
255 | *p = SCM_EOL; | |
256 | return scm_values (scm_list_2 (lst, upto)); | |
257 | } | |
258 | #undef FUNC_NAME | |
259 | ||
260 | ||
e556f8c3 KR |
261 | SCM_DEFINE (scm_srfi1_car_plus_cdr, "car+cdr", 1, 0, 0, |
262 | (SCM pair), | |
263 | "Return two values, the @sc{car} and the @sc{cdr} of @var{pair}.") | |
264 | #define FUNC_NAME s_scm_srfi1_car_plus_cdr | |
265 | { | |
266 | SCM_VALIDATE_CONS (SCM_ARG1, pair); | |
267 | return scm_values (scm_list_2 (SCM_CAR (pair), SCM_CDR (pair))); | |
268 | } | |
269 | #undef FUNC_NAME | |
270 | ||
271 | ||
c66c6d53 KR |
272 | SCM_DEFINE (scm_srfi1_concatenate, "concatenate", 1, 0, 0, |
273 | (SCM lstlst), | |
274 | "Construct a list by appending all lists in @var{lstlst}.\n" | |
275 | "\n" | |
276 | "@code{concatenate} is the same as @code{(apply append\n" | |
277 | "@var{lstlst})}. It exists because some Scheme implementations\n" | |
278 | "have a limit on the number of arguments a function takes, which\n" | |
279 | "the @code{apply} might exceed. In Guile there is no such\n" | |
280 | "limit.") | |
281 | #define FUNC_NAME s_scm_srfi1_concatenate | |
282 | { | |
283 | SCM_VALIDATE_LIST (SCM_ARG1, lstlst); | |
284 | return scm_append (lstlst); | |
285 | } | |
286 | #undef FUNC_NAME | |
287 | ||
47f2726f | 288 | |
c66c6d53 KR |
289 | SCM_DEFINE (scm_srfi1_concatenate_x, "concatenate!", 1, 0, 0, |
290 | (SCM lstlst), | |
291 | "Construct a list by appending all lists in @var{lstlst}. Those\n" | |
292 | "lists may be modified to produce the result.\n" | |
293 | "\n" | |
294 | "@code{concatenate!} is the same as @code{(apply append!\n" | |
295 | "@var{lstlst})}. It exists because some Scheme implementations\n" | |
296 | "have a limit on the number of arguments a function takes, which\n" | |
297 | "the @code{apply} might exceed. In Guile there is no such\n" | |
298 | "limit.") | |
299 | #define FUNC_NAME s_scm_srfi1_concatenate | |
300 | { | |
301 | SCM_VALIDATE_LIST (SCM_ARG1, lstlst); | |
302 | return scm_append_x (lstlst); | |
303 | } | |
304 | #undef FUNC_NAME | |
47f2726f KR |
305 | |
306 | ||
110348ae | 307 | SCM_DEFINE (scm_srfi1_count, "count", 2, 0, 1, |
edea856c | 308 | (SCM pred, SCM list1, SCM rest), |
110348ae KR |
309 | "Return a count of the number of times @var{pred} returns true\n" |
310 | "when called on elements from the given lists.\n" | |
311 | "\n" | |
312 | "@var{pred} is called with @var{N} parameters @code{(@var{pred}\n" | |
313 | "@var{elem1} @dots{} @var{elemN})}, each element being from the\n" | |
edea856c | 314 | "corresponding @var{list1} @dots{} @var{lstN}. The first call is\n" |
110348ae KR |
315 | "with the first element of each list, the second with the second\n" |
316 | "element from each, and so on.\n" | |
317 | "\n" | |
318 | "Counting stops when the end of the shortest list is reached.\n" | |
319 | "At least one list must be non-circular.") | |
320 | #define FUNC_NAME s_scm_srfi1_count | |
321 | { | |
322 | long count; | |
5fc743b4 KR |
323 | SCM lst; |
324 | int argnum; | |
110348ae KR |
325 | SCM_VALIDATE_REST_ARGUMENT (rest); |
326 | ||
327 | count = 0; | |
328 | ||
896df2d5 | 329 | if (scm_is_null (rest)) |
110348ae KR |
330 | { |
331 | /* one list */ | |
332 | scm_t_trampoline_1 pred_tramp; | |
333 | pred_tramp = scm_trampoline_1 (pred); | |
334 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
335 | ||
896df2d5 | 336 | for ( ; scm_is_pair (list1); list1 = SCM_CDR (list1)) |
edea856c | 337 | count += scm_is_true (pred_tramp (pred, SCM_CAR (list1))); |
110348ae | 338 | |
5fc743b4 KR |
339 | /* check below that list1 is a proper list, and done */ |
340 | end_list1: | |
341 | lst = list1; | |
342 | argnum = 2; | |
110348ae | 343 | } |
896df2d5 | 344 | else if (scm_is_pair (rest) && scm_is_null (SCM_CDR (rest))) |
110348ae KR |
345 | { |
346 | /* two lists */ | |
347 | scm_t_trampoline_2 pred_tramp; | |
edea856c | 348 | SCM list2; |
110348ae KR |
349 | |
350 | pred_tramp = scm_trampoline_2 (pred); | |
351 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
352 | ||
edea856c | 353 | list2 = SCM_CAR (rest); |
110348ae KR |
354 | for (;;) |
355 | { | |
896df2d5 | 356 | if (! scm_is_pair (list1)) |
5fc743b4 | 357 | goto end_list1; |
896df2d5 | 358 | if (! scm_is_pair (list2)) |
110348ae | 359 | { |
5fc743b4 KR |
360 | lst = list2; |
361 | argnum = 3; | |
110348ae KR |
362 | break; |
363 | } | |
00874d5f | 364 | count += scm_is_true (pred_tramp |
edea856c SJ |
365 | (pred, SCM_CAR (list1), SCM_CAR (list2))); |
366 | list1 = SCM_CDR (list1); | |
367 | list2 = SCM_CDR (list2); | |
110348ae KR |
368 | } |
369 | } | |
370 | else | |
371 | { | |
372 | /* three or more lists */ | |
eccd308a KR |
373 | SCM vec, args, a; |
374 | size_t len, i; | |
110348ae | 375 | |
eccd308a KR |
376 | /* vec is the list arguments */ |
377 | vec = scm_vector (scm_cons (list1, rest)); | |
378 | len = SCM_SIMPLE_VECTOR_LENGTH (vec); | |
110348ae | 379 | |
eccd308a | 380 | /* args is the argument list to pass to pred, same length as vec, |
110348ae | 381 | re-used for each call */ |
eccd308a | 382 | args = scm_make_list (SCM_I_MAKINUM (len), SCM_UNDEFINED); |
110348ae KR |
383 | |
384 | for (;;) | |
385 | { | |
eccd308a KR |
386 | /* first elem of each list in vec into args, and step those |
387 | vec entries onto their next element */ | |
388 | for (i = 0, a = args, argnum = 2; | |
389 | i < len; | |
390 | i++, a = SCM_CDR (a), argnum++) | |
110348ae | 391 | { |
eccd308a | 392 | lst = SCM_SIMPLE_VECTOR_REF (vec, i); /* list argument */ |
896df2d5 | 393 | if (! scm_is_pair (lst)) |
5fc743b4 | 394 | goto check_lst_and_done; |
110348ae | 395 | SCM_SETCAR (a, SCM_CAR (lst)); /* arg for pred */ |
eccd308a | 396 | SCM_SIMPLE_VECTOR_SET (vec, i, SCM_CDR (lst)); /* rest of lst */ |
110348ae KR |
397 | } |
398 | ||
00874d5f | 399 | count += scm_is_true (scm_apply (pred, args, SCM_EOL)); |
110348ae KR |
400 | } |
401 | } | |
5fc743b4 KR |
402 | |
403 | check_lst_and_done: | |
404 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list"); | |
93ccaef0 | 405 | return scm_from_long (count); |
110348ae KR |
406 | } |
407 | #undef FUNC_NAME | |
408 | ||
409 | ||
d0a634de KR |
410 | SCM_DEFINE (scm_srfi1_delete, "delete", 2, 1, 0, |
411 | (SCM x, SCM lst, SCM pred), | |
412 | "Return a list containing the elements of @var{lst} but with\n" | |
413 | "those equal to @var{x} deleted. The returned elements will be\n" | |
414 | "in the same order as they were in @var{lst}.\n" | |
415 | "\n" | |
416 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
417 | "given. An equality call is made just once for each element,\n" | |
418 | "but the order in which the calls are made on the elements is\n" | |
419 | "unspecified.\n" | |
420 | "\n" | |
421 | "The equality calls are always @code{(pred x elem)}, ie.@: the\n" | |
422 | "given @var{x} is first. This means for instance elements\n" | |
423 | "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n" | |
424 | "\n" | |
425 | "@var{lst} is not modified, but the returned list might share a\n" | |
426 | "common tail with @var{lst}.") | |
427 | #define FUNC_NAME s_scm_srfi1_delete | |
428 | { | |
429 | scm_t_trampoline_2 equal_p; | |
430 | SCM ret, *p, keeplst; | |
cf9d3c47 | 431 | int count; |
d0a634de KR |
432 | |
433 | if (SCM_UNBNDP (pred)) | |
434 | return scm_delete (x, lst); | |
435 | ||
436 | equal_p = scm_trampoline_2 (pred); | |
437 | SCM_ASSERT (equal_p, pred, SCM_ARG3, FUNC_NAME); | |
438 | ||
439 | /* ret is the return list being constructed. p is where to append to it, | |
440 | initially &ret then SCM_CDRLOC of the last pair. lst progresses as | |
441 | elements are considered. | |
442 | ||
443 | Elements to be retained are not immediately copied, instead keeplst is | |
cf9d3c47 KR |
444 | the last pair in lst which is to be retained but not yet copied, count |
445 | is how many from there are wanted. When there's no more deletions, *p | |
446 | can be set to keeplst to share the remainder of the original lst. (The | |
447 | entire original lst if there's no deletions at all.) */ | |
d0a634de KR |
448 | |
449 | keeplst = lst; | |
cf9d3c47 | 450 | count = 0; |
d0a634de KR |
451 | p = &ret; |
452 | ||
896df2d5 | 453 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) |
d0a634de | 454 | { |
00874d5f | 455 | if (scm_is_true (equal_p (pred, x, SCM_CAR (lst)))) |
d0a634de | 456 | { |
cf9d3c47 KR |
457 | /* delete this element, so copy those at keeplst */ |
458 | p = list_copy_part (keeplst, count, p); | |
d0a634de | 459 | keeplst = SCM_CDR (lst); |
cf9d3c47 KR |
460 | count = 0; |
461 | } | |
462 | else | |
463 | { | |
464 | /* keep this element */ | |
465 | count++; | |
d0a634de KR |
466 | } |
467 | } | |
468 | ||
469 | /* final retained elements */ | |
470 | *p = keeplst; | |
471 | ||
472 | /* demand that lst was a proper list */ | |
473 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
474 | ||
475 | return ret; | |
476 | } | |
477 | #undef FUNC_NAME | |
478 | ||
479 | ||
480 | SCM_DEFINE (scm_srfi1_delete_x, "delete!", 2, 1, 0, | |
481 | (SCM x, SCM lst, SCM pred), | |
482 | "Return a list containing the elements of @var{lst} but with\n" | |
483 | "those equal to @var{x} deleted. The returned elements will be\n" | |
484 | "in the same order as they were in @var{lst}.\n" | |
485 | "\n" | |
486 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
487 | "given. An equality call is made just once for each element,\n" | |
488 | "but the order in which the calls are made on the elements is\n" | |
489 | "unspecified.\n" | |
490 | "\n" | |
491 | "The equality calls are always @code{(pred x elem)}, ie.@: the\n" | |
492 | "given @var{x} is first. This means for instance elements\n" | |
493 | "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n" | |
494 | "\n" | |
495 | "@var{lst} may be modified to construct the returned list.") | |
496 | #define FUNC_NAME s_scm_srfi1_delete_x | |
497 | { | |
498 | scm_t_trampoline_2 equal_p; | |
499 | SCM walk; | |
500 | SCM *prev; | |
501 | ||
502 | if (SCM_UNBNDP (pred)) | |
503 | return scm_delete_x (x, lst); | |
504 | ||
505 | equal_p = scm_trampoline_2 (pred); | |
506 | SCM_ASSERT (equal_p, pred, SCM_ARG3, FUNC_NAME); | |
507 | ||
508 | for (prev = &lst, walk = lst; | |
896df2d5 | 509 | scm_is_pair (walk); |
d0a634de KR |
510 | walk = SCM_CDR (walk)) |
511 | { | |
00874d5f | 512 | if (scm_is_true (equal_p (pred, x, SCM_CAR (walk)))) |
d0a634de KR |
513 | *prev = SCM_CDR (walk); |
514 | else | |
515 | prev = SCM_CDRLOC (walk); | |
516 | } | |
517 | ||
518 | /* demand the input was a proper list */ | |
519 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (walk), walk, SCM_ARG2, FUNC_NAME,"list"); | |
520 | return lst; | |
521 | } | |
522 | #undef FUNC_NAME | |
523 | ||
524 | ||
525 | SCM_DEFINE (scm_srfi1_delete_duplicates, "delete-duplicates", 1, 1, 0, | |
526 | (SCM lst, SCM pred), | |
527 | "Return a list containing the elements of @var{lst} but without\n" | |
528 | "duplicates.\n" | |
529 | "\n" | |
530 | "When elements are equal, only the first in @var{lst} is\n" | |
531 | "retained. Equal elements can be anywhere in @var{lst}, they\n" | |
532 | "don't have to be adjacent. The returned list will have the\n" | |
533 | "retained elements in the same order as they were in @var{lst}.\n" | |
534 | "\n" | |
535 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
536 | "given. Calls @code{(pred x y)} are made with element @var{x}\n" | |
537 | "being before @var{y} in @var{lst}. A call is made at most once\n" | |
538 | "for each combination, but the sequence of the calls across the\n" | |
539 | "elements is unspecified.\n" | |
540 | "\n" | |
541 | "@var{lst} is not modified, but the return might share a common\n" | |
542 | "tail with @var{lst}.\n" | |
543 | "\n" | |
544 | "In the worst case, this is an @math{O(N^2)} algorithm because\n" | |
545 | "it must check each element against all those preceding it. For\n" | |
546 | "long lists it is more efficient to sort and then compare only\n" | |
547 | "adjacent elements.") | |
548 | #define FUNC_NAME s_scm_srfi1_delete_duplicates | |
549 | { | |
550 | scm_t_trampoline_2 equal_p; | |
551 | SCM ret, *p, keeplst, item, l; | |
cf9d3c47 | 552 | int count, i; |
d0a634de KR |
553 | |
554 | /* ret is the new list constructed. p is where to append, initially &ret | |
555 | then SCM_CDRLOC of the last pair. lst is advanced as each element is | |
556 | considered. | |
557 | ||
558 | Elements retained are not immediately appended to ret, instead keeplst | |
559 | is the last pair in lst which is to be kept but is not yet copied. | |
560 | Initially this is the first pair of lst, since the first element is | |
561 | always retained. | |
562 | ||
563 | *p is kept set to keeplst, so ret (inclusive) to lst (exclusive) is all | |
564 | the elements retained, making the equality search loop easy. | |
565 | ||
566 | If an item must be deleted, elements from keeplst (inclusive) to lst | |
567 | (exclusive) must be copied and appended to ret. When there's no more | |
568 | deletions, *p is left set to keeplst, so ret shares structure with the | |
569 | original lst. (ret will be the entire original lst if there are no | |
570 | deletions.) */ | |
571 | ||
572 | /* skip to end if an empty list (or something invalid) */ | |
cf9d3c47 KR |
573 | ret = SCM_EOL; |
574 | ||
575 | if (SCM_UNBNDP (pred)) | |
576 | equal_p = equal_trampoline; | |
577 | else | |
d0a634de | 578 | { |
cf9d3c47 KR |
579 | equal_p = scm_trampoline_2 (pred); |
580 | SCM_ASSERT (equal_p, pred, SCM_ARG2, FUNC_NAME); | |
581 | } | |
d0a634de | 582 | |
cf9d3c47 KR |
583 | keeplst = lst; |
584 | count = 0; | |
585 | p = &ret; | |
d0a634de | 586 | |
cf9d3c47 KR |
587 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) |
588 | { | |
589 | item = SCM_CAR (lst); | |
d0a634de | 590 | |
cf9d3c47 KR |
591 | /* look for item in "ret" list */ |
592 | for (l = ret; scm_is_pair (l); l = SCM_CDR (l)) | |
593 | { | |
594 | if (scm_is_true (equal_p (pred, SCM_CAR (l), item))) | |
d0a634de | 595 | { |
cf9d3c47 KR |
596 | /* "item" is a duplicate, so copy keeplst onto ret */ |
597 | duplicate: | |
598 | p = list_copy_part (keeplst, count, p); | |
599 | ||
600 | keeplst = SCM_CDR (lst); /* elem after the one deleted */ | |
601 | count = 0; | |
602 | goto next_elem; | |
d0a634de KR |
603 | } |
604 | } | |
d0a634de | 605 | |
cf9d3c47 KR |
606 | /* look for item in "keeplst" list |
607 | be careful traversing, in case nasty code changed the cdrs */ | |
608 | for (i = 0, l = keeplst; | |
609 | i < count && scm_is_pair (l); | |
610 | i++, l = SCM_CDR (l)) | |
611 | if (scm_is_true (equal_p (pred, SCM_CAR (l), item))) | |
612 | goto duplicate; | |
613 | ||
614 | /* keep this element */ | |
615 | count++; | |
616 | ||
617 | next_elem: | |
618 | ; | |
619 | } | |
d0a634de KR |
620 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list"); |
621 | ||
cf9d3c47 KR |
622 | /* share tail of keeplst items */ |
623 | *p = keeplst; | |
624 | ||
d0a634de KR |
625 | return ret; |
626 | } | |
627 | #undef FUNC_NAME | |
628 | ||
629 | ||
630 | SCM_DEFINE (scm_srfi1_delete_duplicates_x, "delete-duplicates!", 1, 1, 0, | |
631 | (SCM lst, SCM pred), | |
632 | "Return a list containing the elements of @var{lst} but without\n" | |
633 | "duplicates.\n" | |
634 | "\n" | |
635 | "When elements are equal, only the first in @var{lst} is\n" | |
636 | "retained. Equal elements can be anywhere in @var{lst}, they\n" | |
637 | "don't have to be adjacent. The returned list will have the\n" | |
638 | "retained elements in the same order as they were in @var{lst}.\n" | |
639 | "\n" | |
640 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
641 | "given. Calls @code{(pred x y)} are made with element @var{x}\n" | |
642 | "being before @var{y} in @var{lst}. A call is made at most once\n" | |
643 | "for each combination, but the sequence of the calls across the\n" | |
644 | "elements is unspecified.\n" | |
645 | "\n" | |
646 | "@var{lst} may be modified to construct the returned list.\n" | |
647 | "\n" | |
648 | "In the worst case, this is an @math{O(N^2)} algorithm because\n" | |
649 | "it must check each element against all those preceding it. For\n" | |
650 | "long lists it is more efficient to sort and then compare only\n" | |
651 | "adjacent elements.") | |
652 | #define FUNC_NAME s_scm_srfi1_delete_duplicates_x | |
653 | { | |
654 | scm_t_trampoline_2 equal_p; | |
655 | SCM ret, endret, item, l; | |
656 | ||
657 | /* ret is the return list, constructed from the pairs in lst. endret is | |
658 | the last pair of ret, initially the first pair. lst is advanced as | |
659 | elements are considered. */ | |
660 | ||
661 | /* skip to end if an empty list (or something invalid) */ | |
662 | ret = lst; | |
896df2d5 | 663 | if (scm_is_pair (lst)) |
d0a634de KR |
664 | { |
665 | if (SCM_UNBNDP (pred)) | |
666 | equal_p = equal_trampoline; | |
667 | else | |
668 | { | |
669 | equal_p = scm_trampoline_2 (pred); | |
670 | SCM_ASSERT (equal_p, pred, SCM_ARG2, FUNC_NAME); | |
671 | } | |
672 | ||
673 | endret = ret; | |
674 | ||
675 | /* loop over lst elements starting from second */ | |
676 | for (;;) | |
677 | { | |
678 | lst = SCM_CDR (lst); | |
896df2d5 | 679 | if (! scm_is_pair (lst)) |
d0a634de KR |
680 | break; |
681 | item = SCM_CAR (lst); | |
682 | ||
683 | /* is item equal to any element from ret to endret (inclusive)? */ | |
684 | l = ret; | |
685 | for (;;) | |
686 | { | |
00874d5f | 687 | if (scm_is_true (equal_p (pred, SCM_CAR (l), item))) |
d0a634de KR |
688 | break; /* equal, forget this element */ |
689 | ||
bc36d050 | 690 | if (scm_is_eq (l, endret)) |
d0a634de KR |
691 | { |
692 | /* not equal to any, so append this pair */ | |
693 | SCM_SETCDR (endret, lst); | |
694 | endret = lst; | |
695 | break; | |
696 | } | |
697 | l = SCM_CDR (l); | |
698 | } | |
699 | } | |
700 | ||
701 | /* terminate, in case last element was deleted */ | |
702 | SCM_SETCDR (endret, SCM_EOL); | |
703 | } | |
704 | ||
705 | /* demand that lst was a proper list */ | |
706 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list"); | |
707 | ||
708 | return ret; | |
709 | } | |
710 | #undef FUNC_NAME | |
711 | ||
712 | ||
2b077051 KR |
713 | SCM_DEFINE (scm_srfi1_drop_right, "drop-right", 2, 0, 0, |
714 | (SCM lst, SCM n), | |
715 | "Return a new list containing all except the last @var{n}\n" | |
716 | "elements of @var{lst}.") | |
717 | #define FUNC_NAME s_scm_srfi1_drop_right | |
718 | { | |
719 | SCM tail = scm_list_tail (lst, n); | |
720 | SCM ret = SCM_EOL; | |
721 | SCM *rend = &ret; | |
722 | while (scm_is_pair (tail)) | |
723 | { | |
724 | *rend = scm_cons (SCM_CAR (lst), SCM_EOL); | |
725 | rend = SCM_CDRLOC (*rend); | |
726 | ||
727 | lst = SCM_CDR (lst); | |
728 | tail = SCM_CDR (tail); | |
729 | } | |
730 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail), tail, SCM_ARG1, FUNC_NAME, "list"); | |
731 | return ret; | |
732 | } | |
733 | #undef FUNC_NAME | |
c1635946 KR |
734 | |
735 | ||
597dbd4e KR |
736 | SCM_DEFINE (scm_srfi1_drop_right_x, "drop-right!", 2, 0, 0, |
737 | (SCM lst, SCM n), | |
738 | "Return the a list containing the @var{n} last elements of\n" | |
739 | "@var{lst}. @var{lst} may be modified to build the return.") | |
740 | #define FUNC_NAME s_scm_srfi1_drop_right_x | |
741 | { | |
742 | SCM tail, *p; | |
743 | ||
744 | if (scm_is_eq (n, SCM_INUM0)) | |
745 | return lst; | |
746 | ||
747 | tail = scm_list_tail (lst, n); | |
748 | p = &lst; | |
749 | ||
750 | /* p and tail work along the list, p being the cdrloc of the cell n steps | |
751 | behind tail */ | |
752 | for ( ; scm_is_pair (tail); tail = SCM_CDR (tail)) | |
753 | p = SCM_CDRLOC (*p); | |
754 | ||
755 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail), tail, SCM_ARG1, FUNC_NAME, "list"); | |
756 | ||
757 | *p = SCM_EOL; | |
758 | return lst; | |
759 | } | |
760 | #undef FUNC_NAME | |
761 | ||
762 | ||
763 | SCM_DEFINE (scm_srfi1_drop_while, "drop-while", 2, 0, 0, | |
764 | (SCM pred, SCM lst), | |
765 | "Drop the longest initial prefix of @var{lst} whose elements all\n" | |
766 | "satisfy the predicate @var{pred}.") | |
767 | #define FUNC_NAME s_scm_srfi1_drop_while | |
768 | { | |
769 | scm_t_trampoline_1 pred_tramp = scm_trampoline_1 (pred); | |
770 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
771 | ||
772 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
773 | if (scm_is_false (pred_tramp (pred, SCM_CAR (lst)))) | |
774 | goto done; | |
775 | ||
776 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
777 | done: | |
778 | return lst; | |
779 | } | |
780 | #undef FUNC_NAME | |
781 | ||
782 | ||
03731332 KR |
783 | SCM_DEFINE (scm_srfi1_eighth, "eighth", 1, 0, 0, |
784 | (SCM lst), | |
785 | "Return the eighth element of @var{lst}.") | |
786 | #define FUNC_NAME s_scm_srfi1_eighth | |
787 | { | |
788 | return scm_list_ref (lst, SCM_I_MAKINUM (7)); | |
789 | } | |
790 | #undef FUNC_NAME | |
791 | ||
792 | ||
793 | SCM_DEFINE (scm_srfi1_fifth, "fifth", 1, 0, 0, | |
794 | (SCM lst), | |
795 | "Return the fifth element of @var{lst}.") | |
796 | #define FUNC_NAME s_scm_srfi1_fifth | |
797 | { | |
798 | return scm_list_ref (lst, SCM_I_MAKINUM (4)); | |
799 | } | |
800 | #undef FUNC_NAME | |
801 | ||
802 | ||
c1635946 KR |
803 | SCM_DEFINE (scm_srfi1_filter_map, "filter-map", 2, 0, 1, |
804 | (SCM proc, SCM list1, SCM rest), | |
805 | "Apply @var{proc} to to the elements of @var{list1} @dots{} and\n" | |
806 | "return a list of the results as per SRFI-1 @code{map}, except\n" | |
807 | "that any @code{#f} results are omitted from the list returned.") | |
808 | #define FUNC_NAME s_scm_srfi1_filter_map | |
809 | { | |
810 | SCM ret, *loc, elem, newcell, lst; | |
811 | int argnum; | |
812 | ||
813 | SCM_VALIDATE_REST_ARGUMENT (rest); | |
814 | ||
815 | ret = SCM_EOL; | |
816 | loc = &ret; | |
817 | ||
3c55f6f1 | 818 | if (scm_is_null (rest)) |
c1635946 KR |
819 | { |
820 | /* one list */ | |
821 | scm_t_trampoline_1 proc_tramp = scm_trampoline_1 (proc); | |
822 | SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME); | |
823 | ||
824 | for ( ; scm_is_pair (list1); list1 = SCM_CDR (list1)) | |
825 | { | |
826 | elem = proc_tramp (proc, SCM_CAR (list1)); | |
827 | if (scm_is_true (elem)) | |
828 | { | |
829 | newcell = scm_cons (elem, SCM_EOL); | |
830 | *loc = newcell; | |
831 | loc = SCM_CDRLOC (newcell); | |
832 | } | |
833 | } | |
834 | ||
835 | /* check below that list1 is a proper list, and done */ | |
6507b831 | 836 | end_list1: |
c1635946 KR |
837 | lst = list1; |
838 | argnum = 2; | |
839 | } | |
3c55f6f1 | 840 | else if (scm_is_null (SCM_CDR (rest))) |
c1635946 KR |
841 | { |
842 | /* two lists */ | |
843 | scm_t_trampoline_2 proc_tramp = scm_trampoline_2 (proc); | |
844 | SCM list2 = SCM_CAR (rest); | |
845 | SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME); | |
846 | ||
847 | for (;;) | |
848 | { | |
849 | if (! scm_is_pair (list1)) | |
6507b831 | 850 | goto end_list1; |
c1635946 KR |
851 | if (! scm_is_pair (list2)) |
852 | { | |
853 | lst = list2; | |
854 | argnum = 3; | |
855 | goto check_lst_and_done; | |
856 | } | |
857 | elem = proc_tramp (proc, SCM_CAR (list1), SCM_CAR (list2)); | |
858 | if (scm_is_true (elem)) | |
859 | { | |
860 | newcell = scm_cons (elem, SCM_EOL); | |
861 | *loc = newcell; | |
862 | loc = SCM_CDRLOC (newcell); | |
863 | } | |
864 | list1 = SCM_CDR (list1); | |
865 | list2 = SCM_CDR (list2); | |
866 | } | |
867 | } | |
868 | else | |
869 | { | |
870 | /* three or more lists */ | |
eccd308a KR |
871 | SCM vec, args, a; |
872 | size_t len, i; | |
c1635946 | 873 | |
eccd308a KR |
874 | /* vec is the list arguments */ |
875 | vec = scm_vector (scm_cons (list1, rest)); | |
876 | len = SCM_SIMPLE_VECTOR_LENGTH (vec); | |
c1635946 | 877 | |
eccd308a | 878 | /* args is the argument list to pass to proc, same length as vec, |
c1635946 | 879 | re-used for each call */ |
eccd308a | 880 | args = scm_make_list (SCM_I_MAKINUM (len), SCM_UNDEFINED); |
c1635946 KR |
881 | |
882 | for (;;) | |
883 | { | |
eccd308a KR |
884 | /* first elem of each list in vec into args, and step those |
885 | vec entries onto their next element */ | |
886 | for (i = 0, a = args, argnum = 2; | |
887 | i < len; | |
888 | i++, a = SCM_CDR (a), argnum++) | |
c1635946 | 889 | { |
eccd308a | 890 | lst = SCM_SIMPLE_VECTOR_REF (vec, i); /* list argument */ |
c1635946 KR |
891 | if (! scm_is_pair (lst)) |
892 | goto check_lst_and_done; | |
893 | SCM_SETCAR (a, SCM_CAR (lst)); /* arg for proc */ | |
eccd308a | 894 | SCM_SIMPLE_VECTOR_SET (vec, i, SCM_CDR (lst)); /* rest of lst */ |
c1635946 KR |
895 | } |
896 | ||
897 | elem = scm_apply (proc, args, SCM_EOL); | |
898 | if (scm_is_true (elem)) | |
899 | { | |
900 | newcell = scm_cons (elem, SCM_EOL); | |
901 | *loc = newcell; | |
902 | loc = SCM_CDRLOC (newcell); | |
903 | } | |
904 | } | |
905 | } | |
906 | ||
907 | check_lst_and_done: | |
908 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list"); | |
909 | return ret; | |
910 | } | |
911 | #undef FUNC_NAME | |
2b077051 KR |
912 | |
913 | ||
5df2ac97 KR |
914 | SCM_DEFINE (scm_srfi1_find, "find", 2, 0, 0, |
915 | (SCM pred, SCM lst), | |
916 | "Return the first element of @var{lst} which satisfies the\n" | |
917 | "predicate @var{pred}, or return @code{#f} if no such element is\n" | |
918 | "found.") | |
919 | #define FUNC_NAME s_scm_srfi1_find | |
920 | { | |
921 | scm_t_trampoline_1 pred_tramp = scm_trampoline_1 (pred); | |
922 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
923 | ||
924 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
925 | { | |
926 | SCM elem = SCM_CAR (lst); | |
927 | if (scm_is_true (pred_tramp (pred, elem))) | |
928 | return elem; | |
929 | } | |
930 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
931 | ||
932 | return SCM_BOOL_F; | |
933 | } | |
934 | #undef FUNC_NAME | |
935 | ||
936 | ||
937 | SCM_DEFINE (scm_srfi1_find_tail, "find-tail", 2, 0, 0, | |
938 | (SCM pred, SCM lst), | |
939 | "Return the first pair of @var{lst} whose @sc{car} satisfies the\n" | |
940 | "predicate @var{pred}, or return @code{#f} if no such element is\n" | |
941 | "found.") | |
942 | #define FUNC_NAME s_scm_srfi1_find_tail | |
943 | { | |
944 | scm_t_trampoline_1 pred_tramp = scm_trampoline_1 (pred); | |
945 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
946 | ||
947 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
948 | if (scm_is_true (pred_tramp (pred, SCM_CAR (lst)))) | |
949 | return lst; | |
950 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
951 | ||
952 | return SCM_BOOL_F; | |
953 | } | |
954 | #undef FUNC_NAME | |
955 | ||
956 | ||
e556f8c3 KR |
957 | SCM_DEFINE (scm_srfi1_fold, "fold", 3, 0, 1, |
958 | (SCM proc, SCM init, SCM list1, SCM rest), | |
959 | "Apply @var{proc} to the elements of @var{lst1} @dots{}\n" | |
960 | "@var{lstN} to build a result, and return that result.\n" | |
961 | "\n" | |
962 | "Each @var{proc} call is @code{(@var{proc} @var{elem1} @dots{}\n" | |
963 | "@var{elemN} @var{previous})}, where @var{elem1} is from\n" | |
964 | "@var{lst1}, through @var{elemN} from @var{lstN}.\n" | |
965 | "@var{previous} is the return from the previous call to\n" | |
966 | "@var{proc}, or the given @var{init} for the first call. If any\n" | |
967 | "list is empty, just @var{init} is returned.\n" | |
968 | "\n" | |
969 | "@code{fold} works through the list elements from first to last.\n" | |
970 | "The following shows a list reversal and the calls it makes,\n" | |
971 | "\n" | |
972 | "@example\n" | |
973 | "(fold cons '() '(1 2 3))\n" | |
974 | "\n" | |
975 | "(cons 1 '())\n" | |
976 | "(cons 2 '(1))\n" | |
977 | "(cons 3 '(2 1)\n" | |
978 | "@result{} (3 2 1)\n" | |
979 | "@end example\n" | |
980 | "\n" | |
981 | "If @var{lst1} through @var{lstN} have different lengths,\n" | |
982 | "@code{fold} stops when the end of the shortest is reached.\n" | |
983 | "Ie.@: elements past the length of the shortest are ignored in\n" | |
984 | "the other @var{lst}s. At least one @var{lst} must be\n" | |
985 | "non-circular.\n" | |
986 | "\n" | |
987 | "The way @code{fold} builds a result from iterating is quite\n" | |
988 | "general, it can do more than other iterations like say\n" | |
989 | "@code{map} or @code{filter}. The following for example removes\n" | |
990 | "adjacent duplicate elements from a list,\n" | |
991 | "\n" | |
992 | "@example\n" | |
993 | "(define (delete-adjacent-duplicates lst)\n" | |
994 | " (fold-right (lambda (elem ret)\n" | |
995 | " (if (equal? elem (first ret))\n" | |
996 | " ret\n" | |
997 | " (cons elem ret)))\n" | |
998 | " (list (last lst))\n" | |
999 | " lst))\n" | |
1000 | "(delete-adjacent-duplicates '(1 2 3 3 4 4 4 5))\n" | |
1001 | "@result{} (1 2 3 4 5)\n" | |
1002 | "@end example\n" | |
1003 | "\n" | |
1004 | "Clearly the same sort of thing can be done with a\n" | |
1005 | "@code{for-each} and a variable in which to build the result,\n" | |
1006 | "but a self-contained @var{proc} can be re-used in multiple\n" | |
1007 | "contexts, where a @code{for-each} would have to be written out\n" | |
1008 | "each time.") | |
1009 | #define FUNC_NAME s_scm_srfi1_fold | |
1010 | { | |
1011 | SCM lst; | |
1012 | int argnum; | |
1013 | SCM_VALIDATE_REST_ARGUMENT (rest); | |
1014 | ||
1015 | if (scm_is_null (rest)) | |
1016 | { | |
1017 | /* one list */ | |
1018 | scm_t_trampoline_2 proc_tramp = scm_trampoline_2 (proc); | |
1019 | SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME); | |
1020 | ||
1021 | for ( ; scm_is_pair (list1); list1 = SCM_CDR (list1)) | |
1022 | init = proc_tramp (proc, SCM_CAR (list1), init); | |
1023 | ||
1024 | /* check below that list1 is a proper list, and done */ | |
1025 | lst = list1; | |
1026 | argnum = 2; | |
1027 | } | |
1028 | else | |
1029 | { | |
1030 | /* two or more lists */ | |
1031 | SCM vec, args, a; | |
1032 | size_t len, i; | |
1033 | ||
1034 | /* vec is the list arguments */ | |
1035 | vec = scm_vector (scm_cons (list1, rest)); | |
1036 | len = SCM_SIMPLE_VECTOR_LENGTH (vec); | |
1037 | ||
1038 | /* args is the argument list to pass to proc, same length as vec, | |
1039 | re-used for each call */ | |
1040 | args = scm_make_list (SCM_I_MAKINUM (len+1), SCM_UNDEFINED); | |
1041 | ||
1042 | for (;;) | |
1043 | { | |
1044 | /* first elem of each list in vec into args, and step those | |
1045 | vec entries onto their next element */ | |
1046 | for (i = 0, a = args, argnum = 2; | |
1047 | i < len; | |
1048 | i++, a = SCM_CDR (a), argnum++) | |
1049 | { | |
1050 | lst = SCM_SIMPLE_VECTOR_REF (vec, i); /* list argument */ | |
1051 | if (! scm_is_pair (lst)) | |
1052 | goto check_lst_and_done; | |
1053 | SCM_SETCAR (a, SCM_CAR (lst)); /* arg for proc */ | |
1054 | SCM_SIMPLE_VECTOR_SET (vec, i, SCM_CDR (lst)); /* rest of lst */ | |
1055 | } | |
1056 | SCM_SETCAR (a, init); | |
1057 | ||
1058 | init = scm_apply (proc, args, SCM_EOL); | |
1059 | } | |
1060 | } | |
1061 | ||
1062 | check_lst_and_done: | |
1063 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list"); | |
1064 | return init; | |
1065 | } | |
1066 | #undef FUNC_NAME | |
1067 | ||
1068 | ||
1069 | SCM_DEFINE (scm_srfi1_last, "last", 1, 0, 0, | |
1070 | (SCM lst), | |
1071 | "Like @code{cons}, but with interchanged arguments. Useful\n" | |
1072 | "mostly when passed to higher-order procedures.") | |
1073 | #define FUNC_NAME s_scm_srfi1_last | |
1074 | { | |
1075 | SCM pair = scm_last_pair (lst); | |
1076 | /* scm_last_pair returns SCM_EOL for an empty list */ | |
1077 | SCM_VALIDATE_CONS (SCM_ARG1, pair); | |
1078 | return SCM_CAR (pair); | |
1079 | } | |
1080 | #undef FUNC_NAME | |
1081 | ||
1082 | ||
de51f595 KR |
1083 | SCM_DEFINE (scm_srfi1_length_plus, "length+", 1, 0, 0, |
1084 | (SCM lst), | |
1085 | "Return the length of @var{lst}, or @code{#f} if @var{lst} is\n" | |
1086 | "circular.") | |
1087 | #define FUNC_NAME s_scm_srfi1_length_plus | |
1088 | { | |
1089 | long len = scm_ilength (lst); | |
93ccaef0 | 1090 | return (len >= 0 ? SCM_I_MAKINUM (len) : SCM_BOOL_F); |
de51f595 KR |
1091 | } |
1092 | #undef FUNC_NAME | |
1093 | ||
1094 | ||
e556f8c3 KR |
1095 | SCM_DEFINE (scm_srfi1_list_index, "list-index", 2, 0, 1, |
1096 | (SCM pred, SCM list1, SCM rest), | |
1097 | "Return the index of the first set of elements, one from each of\n" | |
1098 | "@var{lst1}@dots{}@var{lstN}, which satisfies @var{pred}.\n" | |
1099 | "\n" | |
1100 | "@var{pred} is called as @code{(@var{pred} elem1 @dots{}\n" | |
1101 | "elemN)}. Searching stops when the end of the shortest\n" | |
1102 | "@var{lst} is reached. The return index starts from 0 for the\n" | |
1103 | "first set of elements. If no set of elements pass then the\n" | |
1104 | "return is @code{#f}.\n" | |
1105 | "\n" | |
1106 | "@example\n" | |
1107 | "(list-index odd? '(2 4 6 9)) @result{} 3\n" | |
1108 | "(list-index = '(1 2 3) '(3 1 2)) @result{} #f\n" | |
1109 | "@end example") | |
1110 | #define FUNC_NAME s_scm_srfi1_list_index | |
1111 | { | |
1112 | long n = 0; | |
1113 | SCM lst; | |
1114 | int argnum; | |
1115 | SCM_VALIDATE_REST_ARGUMENT (rest); | |
1116 | ||
1117 | if (scm_is_null (rest)) | |
1118 | { | |
1119 | /* one list */ | |
1120 | scm_t_trampoline_1 pred_tramp = scm_trampoline_1 (pred); | |
1121 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
1122 | ||
1123 | for ( ; scm_is_pair (list1); n++, list1 = SCM_CDR (list1)) | |
1124 | if (scm_is_true (pred_tramp (pred, SCM_CAR (list1)))) | |
1125 | return SCM_I_MAKINUM (n); | |
1126 | ||
1127 | /* not found, check below that list1 is a proper list */ | |
1128 | end_list1: | |
1129 | lst = list1; | |
1130 | argnum = 2; | |
1131 | } | |
1132 | else if (scm_is_pair (rest) && scm_is_null (SCM_CDR (rest))) | |
1133 | { | |
1134 | /* two lists */ | |
1135 | SCM list2 = SCM_CAR (rest); | |
1136 | scm_t_trampoline_2 pred_tramp = scm_trampoline_2 (pred); | |
1137 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
1138 | ||
1139 | for ( ; ; n++) | |
1140 | { | |
1141 | if (! scm_is_pair (list1)) | |
1142 | goto end_list1; | |
1143 | if (! scm_is_pair (list2)) | |
1144 | { | |
1145 | lst = list2; | |
1146 | argnum = 3; | |
1147 | break; | |
1148 | } | |
1149 | if (scm_is_true (pred_tramp (pred, | |
1150 | SCM_CAR (list1), SCM_CAR (list2)))) | |
1151 | return SCM_I_MAKINUM (n); | |
1152 | ||
1153 | list1 = SCM_CDR (list1); | |
1154 | list2 = SCM_CDR (list2); | |
1155 | } | |
1156 | } | |
1157 | else | |
1158 | { | |
1159 | /* three or more lists */ | |
1160 | SCM vec, args, a; | |
1161 | size_t len, i; | |
1162 | ||
1163 | /* vec is the list arguments */ | |
1164 | vec = scm_vector (scm_cons (list1, rest)); | |
1165 | len = SCM_SIMPLE_VECTOR_LENGTH (vec); | |
1166 | ||
1167 | /* args is the argument list to pass to pred, same length as vec, | |
1168 | re-used for each call */ | |
1169 | args = scm_make_list (SCM_I_MAKINUM (len), SCM_UNDEFINED); | |
1170 | ||
1171 | for ( ; ; n++) | |
1172 | { | |
1173 | /* first elem of each list in vec into args, and step those | |
1174 | vec entries onto their next element */ | |
1175 | for (i = 0, a = args, argnum = 2; | |
1176 | i < len; | |
1177 | i++, a = SCM_CDR (a), argnum++) | |
1178 | { | |
1179 | lst = SCM_SIMPLE_VECTOR_REF (vec, i); /* list argument */ | |
1180 | if (! scm_is_pair (lst)) | |
1181 | goto not_found_check_lst; | |
1182 | SCM_SETCAR (a, SCM_CAR (lst)); /* arg for pred */ | |
1183 | SCM_SIMPLE_VECTOR_SET (vec, i, SCM_CDR (lst)); /* rest of lst */ | |
1184 | } | |
1185 | ||
1186 | if (scm_is_true (scm_apply (pred, args, SCM_EOL))) | |
1187 | return SCM_I_MAKINUM (n); | |
1188 | } | |
1189 | } | |
1190 | ||
1191 | not_found_check_lst: | |
1192 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list"); | |
1193 | return SCM_BOOL_F; | |
1194 | } | |
1195 | #undef FUNC_NAME | |
1196 | ||
1197 | ||
d61261f0 KR |
1198 | /* This routine differs from the core list-copy in allowing improper lists. |
1199 | Maybe the core could allow them similarly. */ | |
1200 | ||
1201 | SCM_DEFINE (scm_srfi1_list_copy, "list-copy", 1, 0, 0, | |
1202 | (SCM lst), | |
1203 | "Return a copy of the given list @var{lst}.\n" | |
1204 | "\n" | |
1205 | "@var{lst} can be a proper or improper list. And if @var{lst}\n" | |
1206 | "is not a pair then it's treated as the final tail of an\n" | |
1207 | "improper list and simply returned.") | |
1208 | #define FUNC_NAME s_scm_srfi1_list_copy | |
1209 | { | |
1210 | SCM newlst; | |
1211 | SCM * fill_here; | |
1212 | SCM from_here; | |
1213 | ||
1214 | newlst = lst; | |
1215 | fill_here = &newlst; | |
1216 | from_here = lst; | |
1217 | ||
896df2d5 | 1218 | while (scm_is_pair (from_here)) |
d61261f0 KR |
1219 | { |
1220 | SCM c; | |
1221 | c = scm_cons (SCM_CAR (from_here), SCM_CDR (from_here)); | |
1222 | *fill_here = c; | |
1223 | fill_here = SCM_CDRLOC (c); | |
1224 | from_here = SCM_CDR (from_here); | |
1225 | } | |
1226 | return newlst; | |
1227 | } | |
1228 | #undef FUNC_NAME | |
1229 | ||
1230 | ||
e556f8c3 KR |
1231 | SCM_DEFINE (scm_srfi1_list_tabulate, "list-tabulate", 2, 0, 0, |
1232 | (SCM n, SCM proc), | |
1233 | "Return an @var{n}-element list, where each list element is\n" | |
1234 | "produced by applying the procedure @var{init-proc} to the\n" | |
1235 | "corresponding list index. The order in which @var{init-proc}\n" | |
1236 | "is applied to the indices is not specified.") | |
1237 | #define FUNC_NAME s_scm_srfi1_list_tabulate | |
1238 | { | |
1239 | long i, nn; | |
1240 | scm_t_trampoline_1 proc_tramp = scm_trampoline_1 (proc); | |
1241 | SCM ret = SCM_EOL; | |
1242 | ||
b730fbf1 | 1243 | nn = scm_to_signed_integer (n, 0, LONG_MAX); |
e556f8c3 KR |
1244 | SCM_ASSERT (proc_tramp, proc, SCM_ARG2, FUNC_NAME); |
1245 | ||
1246 | for (i = nn-1; i >= 0; i--) | |
b730fbf1 | 1247 | ret = scm_cons (proc_tramp (proc, scm_from_long (i)), ret); |
e556f8c3 KR |
1248 | |
1249 | return ret; | |
1250 | } | |
1251 | #undef FUNC_NAME | |
1252 | ||
1253 | ||
597dbd4e KR |
1254 | SCM_DEFINE (scm_srfi1_lset_adjoin, "lset-adjoin", 2, 0, 1, |
1255 | (SCM equal, SCM lst, SCM rest), | |
1256 | "Add to @var{list} any of the given @var{elem}s not already in\n" | |
1257 | "the list. @var{elem}s are @code{cons}ed onto the start of\n" | |
1258 | "@var{list} (so the return shares a common tail with\n" | |
1259 | "@var{list}), but the order they're added is unspecified.\n" | |
1260 | "\n" | |
1261 | "The given @var{=} procedure is used for comparing elements,\n" | |
1262 | "called as @code{(@var{=} listelem elem)}, ie.@: the second\n" | |
1263 | "argument is one of the given @var{elem} parameters.\n" | |
1264 | "\n" | |
1265 | "@example\n" | |
1266 | "(lset-adjoin eqv? '(1 2 3) 4 1 5) @result{} (5 4 1 2 3)\n" | |
1267 | "@end example") | |
1268 | #define FUNC_NAME s_scm_srfi1_lset_adjoin | |
1269 | { | |
1270 | scm_t_trampoline_2 equal_tramp; | |
1271 | SCM l, elem; | |
1272 | ||
1273 | equal_tramp = scm_trampoline_2 (equal); | |
1274 | SCM_ASSERT (equal_tramp, equal, SCM_ARG1, FUNC_NAME); | |
1275 | SCM_VALIDATE_REST_ARGUMENT (rest); | |
1276 | ||
1277 | /* It's not clear if duplicates among the `rest' elements are meant to be | |
1278 | cast out. The spec says `=' is called as (= list-elem rest-elem), | |
1279 | suggesting perhaps not, but the reference implementation shows the | |
1280 | "list" at each stage as including those "rest" elements already added. | |
1281 | The latter corresponds to what's described for lset-union, so that's | |
1282 | what's done here. */ | |
1283 | ||
1284 | for ( ; scm_is_pair (rest); rest = SCM_CDR (rest)) | |
1285 | { | |
1286 | elem = SCM_CAR (rest); | |
1287 | ||
1288 | for (l = lst; scm_is_pair (l); l = SCM_CDR (l)) | |
1289 | if (scm_is_true (equal_tramp (equal, SCM_CAR (l), elem))) | |
1290 | goto next_elem; /* elem already in lst, don't add */ | |
1291 | ||
1292 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(l), lst, SCM_ARG2, FUNC_NAME, "list"); | |
1293 | ||
1294 | /* elem is not equal to anything already in lst, add it */ | |
1295 | lst = scm_cons (elem, lst); | |
1296 | ||
1297 | next_elem: | |
1298 | ; | |
1299 | } | |
1300 | ||
1301 | return lst; | |
1302 | } | |
1303 | #undef FUNC_NAME | |
1304 | ||
1305 | ||
9dcee2b7 KR |
1306 | SCM_DEFINE (scm_srfi1_lset_difference_x, "lset-difference!", 2, 0, 1, |
1307 | (SCM equal, SCM lst, SCM rest), | |
1308 | "Return @var{lst} with any elements in the lists in @var{rest}\n" | |
1309 | "removed (ie.@: subtracted). For only one @var{lst} argument,\n" | |
1310 | "just that list is returned.\n" | |
1311 | "\n" | |
1312 | "The given @var{equal} procedure is used for comparing elements,\n" | |
1313 | "called as @code{(@var{equal} elem1 elemN)}. The first argument\n" | |
1314 | "is from @var{lst} and the second from one of the subsequent\n" | |
1315 | "lists. But exactly which calls are made and in what order is\n" | |
1316 | "unspecified.\n" | |
1317 | "\n" | |
1318 | "@example\n" | |
1319 | "(lset-difference! eqv? (list 'x 'y)) @result{} (x y)\n" | |
1320 | "(lset-difference! eqv? (list 1 2 3) '(3 1)) @result{} (2)\n" | |
1321 | "(lset-difference! eqv? (list 1 2 3) '(3) '(2)) @result{} (1)\n" | |
1322 | "@end example\n" | |
1323 | "\n" | |
1324 | "@code{lset-difference!} may modify @var{lst} to form its\n" | |
1325 | "result.") | |
1326 | #define FUNC_NAME s_scm_srfi1_lset_difference_x | |
1327 | { | |
1328 | scm_t_trampoline_2 equal_tramp = scm_trampoline_2 (equal); | |
1329 | SCM ret, *pos, elem, r, b; | |
1330 | int argnum; | |
1331 | ||
1332 | SCM_ASSERT (equal_tramp, equal, SCM_ARG1, FUNC_NAME); | |
1333 | SCM_VALIDATE_REST_ARGUMENT (rest); | |
1334 | ||
1335 | ret = SCM_EOL; | |
1336 | pos = &ret; | |
1337 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
1338 | { | |
1339 | elem = SCM_CAR (lst); | |
1340 | ||
1341 | for (r = rest, argnum = SCM_ARG3; | |
1342 | scm_is_pair (r); | |
1343 | r = SCM_CDR (r), argnum++) | |
1344 | { | |
1345 | for (b = SCM_CAR (r); scm_is_pair (b); b = SCM_CDR (b)) | |
1346 | if (scm_is_true (equal_tramp (equal, elem, SCM_CAR (b)))) | |
1347 | goto next_elem; /* equal to elem, so drop that elem */ | |
1348 | ||
1349 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (b), b, argnum, FUNC_NAME,"list"); | |
1350 | } | |
1351 | ||
1352 | /* elem not equal to anything in later lists, so keep it */ | |
1353 | *pos = lst; | |
1354 | pos = SCM_CDRLOC (lst); | |
1355 | ||
1356 | next_elem: | |
1357 | ; | |
1358 | } | |
1359 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
1360 | ||
1361 | *pos = SCM_EOL; | |
1362 | return ret; | |
1363 | } | |
1364 | #undef FUNC_NAME | |
1365 | ||
1366 | ||
ee6aac97 MD |
1367 | /* Typechecking for multi-argument MAP and FOR-EACH. |
1368 | ||
1369 | Verify that each element of the vector ARGV, except for the first, | |
1370 | is a list and return minimum length. Attribute errors to WHO, | |
1371 | and claim that the i'th element of ARGV is WHO's i+2'th argument. */ | |
1372 | static inline int | |
1373 | check_map_args (SCM argv, | |
1374 | long len, | |
1375 | SCM gf, | |
1376 | SCM proc, | |
1377 | SCM args, | |
1378 | const char *who) | |
1379 | { | |
ee6aac97 | 1380 | long i; |
705f4f57 | 1381 | SCM elt; |
ee6aac97 | 1382 | |
3c4ce91b | 1383 | for (i = SCM_SIMPLE_VECTOR_LENGTH (argv) - 1; i >= 1; i--) |
ee6aac97 MD |
1384 | { |
1385 | long elt_len; | |
705f4f57 | 1386 | elt = SCM_SIMPLE_VECTOR_REF (argv, i); |
ee6aac97 | 1387 | |
896df2d5 | 1388 | if (!(scm_is_null (elt) || scm_is_pair (elt))) |
705f4f57 | 1389 | goto check_map_error; |
ee6aac97 | 1390 | |
3c4ce91b | 1391 | elt_len = srfi1_ilength (elt); |
ee6aac97 MD |
1392 | if (elt_len < -1) |
1393 | goto check_map_error; | |
1394 | ||
1395 | if (len < 0 || (elt_len >= 0 && elt_len < len)) | |
1396 | len = elt_len; | |
1397 | } | |
705f4f57 | 1398 | |
ee6aac97 | 1399 | if (len < 0) |
705f4f57 MV |
1400 | { |
1401 | /* i == 0 */ | |
1402 | elt = SCM_EOL; | |
1403 | check_map_error: | |
1404 | if (gf) | |
1405 | scm_apply_generic (gf, scm_cons (proc, args)); | |
1406 | else | |
1407 | scm_wrong_type_arg (who, i + 2, elt); | |
1408 | } | |
1409 | ||
ee6aac97 MD |
1410 | scm_remember_upto_here_1 (argv); |
1411 | return len; | |
1412 | } | |
1413 | ||
1414 | ||
1415 | SCM_GPROC (s_srfi1_map, "map", 2, 0, 1, scm_srfi1_map, g_srfi1_map); | |
1416 | ||
1417 | /* Note: Currently, scm_srfi1_map applies PROC to the argument list(s) | |
1418 | sequentially, starting with the first element(s). This is used in | |
1419 | the Scheme procedure `map-in-order', which guarantees sequential | |
1420 | behaviour, is implemented using scm_map. If the behaviour changes, | |
1421 | we need to update `map-in-order'. | |
1422 | */ | |
1423 | ||
1424 | SCM | |
1425 | scm_srfi1_map (SCM proc, SCM arg1, SCM args) | |
1426 | #define FUNC_NAME s_srfi1_map | |
1427 | { | |
1428 | long i, len; | |
1429 | SCM res = SCM_EOL; | |
1430 | SCM *pres = &res; | |
ee6aac97 MD |
1431 | |
1432 | len = srfi1_ilength (arg1); | |
896df2d5 | 1433 | SCM_GASSERTn ((scm_is_null (arg1) || scm_is_pair (arg1)) && len >= -1, |
ee6aac97 MD |
1434 | g_srfi1_map, |
1435 | scm_cons2 (proc, arg1, args), SCM_ARG2, s_srfi1_map); | |
1436 | SCM_VALIDATE_REST_ARGUMENT (args); | |
896df2d5 | 1437 | if (scm_is_null (args)) |
ee6aac97 MD |
1438 | { |
1439 | scm_t_trampoline_1 call = scm_trampoline_1 (proc); | |
1440 | SCM_GASSERT2 (call, g_srfi1_map, proc, arg1, SCM_ARG1, s_srfi1_map); | |
1441 | SCM_GASSERT2 (len >= 0, g_srfi1_map, proc, arg1, SCM_ARG2, s_srfi1_map); | |
1442 | while (SCM_NIMP (arg1)) | |
1443 | { | |
1444 | *pres = scm_list_1 (call (proc, SCM_CAR (arg1))); | |
1445 | pres = SCM_CDRLOC (*pres); | |
1446 | arg1 = SCM_CDR (arg1); | |
1447 | } | |
1448 | return res; | |
1449 | } | |
896df2d5 | 1450 | if (scm_is_null (SCM_CDR (args))) |
ee6aac97 MD |
1451 | { |
1452 | SCM arg2 = SCM_CAR (args); | |
1453 | int len2 = srfi1_ilength (arg2); | |
1454 | scm_t_trampoline_2 call = scm_trampoline_2 (proc); | |
1455 | SCM_GASSERTn (call, g_srfi1_map, | |
1456 | scm_cons2 (proc, arg1, args), SCM_ARG1, s_srfi1_map); | |
1457 | if (len < 0 || (len2 >= 0 && len2 < len)) | |
1458 | len = len2; | |
896df2d5 | 1459 | SCM_GASSERTn ((scm_is_null (arg2) || scm_is_pair (arg2)) |
ee6aac97 MD |
1460 | && len >= 0 && len2 >= -1, |
1461 | g_srfi1_map, | |
1462 | scm_cons2 (proc, arg1, args), | |
f9ac1c2d | 1463 | len2 >= 0 ? SCM_ARG2 : SCM_ARG3, |
ee6aac97 MD |
1464 | s_srfi1_map); |
1465 | while (len > 0) | |
1466 | { | |
1467 | *pres = scm_list_1 (call (proc, SCM_CAR (arg1), SCM_CAR (arg2))); | |
1468 | pres = SCM_CDRLOC (*pres); | |
1469 | arg1 = SCM_CDR (arg1); | |
1470 | arg2 = SCM_CDR (arg2); | |
1471 | --len; | |
1472 | } | |
1473 | return res; | |
1474 | } | |
1475 | args = scm_vector (arg1 = scm_cons (arg1, args)); | |
ee6aac97 MD |
1476 | len = check_map_args (args, len, g_srfi1_map, proc, arg1, s_srfi1_map); |
1477 | while (len > 0) | |
1478 | { | |
1479 | arg1 = SCM_EOL; | |
3c4ce91b | 1480 | for (i = SCM_SIMPLE_VECTOR_LENGTH (args) - 1; i >= 0; i--) |
ee6aac97 | 1481 | { |
3c4ce91b MV |
1482 | SCM elt = SCM_SIMPLE_VECTOR_REF (args, i); |
1483 | arg1 = scm_cons (SCM_CAR (elt), arg1); | |
1484 | SCM_SIMPLE_VECTOR_SET (args, i, SCM_CDR (elt)); | |
ee6aac97 MD |
1485 | } |
1486 | *pres = scm_list_1 (scm_apply (proc, arg1, SCM_EOL)); | |
1487 | pres = SCM_CDRLOC (*pres); | |
1488 | --len; | |
1489 | } | |
1490 | return res; | |
1491 | } | |
1492 | #undef FUNC_NAME | |
1493 | ||
1494 | SCM_REGISTER_PROC (s_srfi1_map_in_order, "map-in-order", 2, 0, 1, scm_srfi1_map); | |
1495 | ||
1496 | SCM_GPROC (s_srfi1_for_each, "for-each", 2, 0, 1, scm_srfi1_for_each, g_srfi1_for_each); | |
1497 | ||
1498 | SCM | |
1499 | scm_srfi1_for_each (SCM proc, SCM arg1, SCM args) | |
1500 | #define FUNC_NAME s_srfi1_for_each | |
1501 | { | |
ee6aac97 MD |
1502 | long i, len; |
1503 | len = srfi1_ilength (arg1); | |
896df2d5 | 1504 | SCM_GASSERTn ((scm_is_null (arg1) || scm_is_pair (arg1)) && len >= -1, |
ee6aac97 MD |
1505 | g_srfi1_for_each, scm_cons2 (proc, arg1, args), |
1506 | SCM_ARG2, s_srfi1_for_each); | |
1507 | SCM_VALIDATE_REST_ARGUMENT (args); | |
896df2d5 | 1508 | if (scm_is_null (args)) |
ee6aac97 MD |
1509 | { |
1510 | scm_t_trampoline_1 call = scm_trampoline_1 (proc); | |
1511 | SCM_GASSERT2 (call, g_srfi1_for_each, proc, arg1, | |
1512 | SCM_ARG1, s_srfi1_for_each); | |
1513 | SCM_GASSERT2 (len >= 0, g_srfi1_for_each, proc, arg1, | |
1514 | SCM_ARG2, s_srfi1_map); | |
1515 | while (SCM_NIMP (arg1)) | |
1516 | { | |
1517 | call (proc, SCM_CAR (arg1)); | |
1518 | arg1 = SCM_CDR (arg1); | |
1519 | } | |
1520 | return SCM_UNSPECIFIED; | |
1521 | } | |
896df2d5 | 1522 | if (scm_is_null (SCM_CDR (args))) |
ee6aac97 MD |
1523 | { |
1524 | SCM arg2 = SCM_CAR (args); | |
1525 | int len2 = srfi1_ilength (arg2); | |
1526 | scm_t_trampoline_2 call = scm_trampoline_2 (proc); | |
1527 | SCM_GASSERTn (call, g_srfi1_for_each, | |
1528 | scm_cons2 (proc, arg1, args), SCM_ARG1, s_srfi1_for_each); | |
1529 | if (len < 0 || (len2 >= 0 && len2 < len)) | |
1530 | len = len2; | |
896df2d5 | 1531 | SCM_GASSERTn ((scm_is_null (arg2) || scm_is_pair (arg2)) |
f9ac1c2d | 1532 | && len >= 0 && len2 >= -1, |
ee6aac97 MD |
1533 | g_srfi1_for_each, |
1534 | scm_cons2 (proc, arg1, args), | |
f9ac1c2d | 1535 | len2 >= 0 ? SCM_ARG2 : SCM_ARG3, |
ee6aac97 MD |
1536 | s_srfi1_for_each); |
1537 | while (len > 0) | |
1538 | { | |
1539 | call (proc, SCM_CAR (arg1), SCM_CAR (arg2)); | |
1540 | arg1 = SCM_CDR (arg1); | |
1541 | arg2 = SCM_CDR (arg2); | |
1542 | --len; | |
1543 | } | |
1544 | return SCM_UNSPECIFIED; | |
1545 | } | |
1546 | args = scm_vector (arg1 = scm_cons (arg1, args)); | |
ee6aac97 MD |
1547 | len = check_map_args (args, len, g_srfi1_for_each, proc, arg1, |
1548 | s_srfi1_for_each); | |
1549 | while (len > 0) | |
1550 | { | |
1551 | arg1 = SCM_EOL; | |
3c4ce91b | 1552 | for (i = SCM_SIMPLE_VECTOR_LENGTH (args) - 1; i >= 0; i--) |
ee6aac97 | 1553 | { |
3c4ce91b MV |
1554 | SCM elt = SCM_SIMPLE_VECTOR_REF (args, i); |
1555 | arg1 = scm_cons (SCM_CAR (elt), arg1); | |
1556 | SCM_SIMPLE_VECTOR_SET (args, i, SCM_CDR (elt)); | |
ee6aac97 MD |
1557 | } |
1558 | scm_apply (proc, arg1, SCM_EOL); | |
1559 | --len; | |
1560 | } | |
1561 | return SCM_UNSPECIFIED; | |
1562 | } | |
1563 | #undef FUNC_NAME | |
1564 | ||
1565 | ||
ee6aac97 MD |
1566 | SCM_DEFINE (scm_srfi1_member, "member", 2, 1, 0, |
1567 | (SCM x, SCM lst, SCM pred), | |
4e3cc389 KR |
1568 | "Return the first sublist of @var{lst} whose @sc{car} is equal\n" |
1569 | "to @var{x}. If @var{x} does not appear in @var{lst}, return\n" | |
1570 | "@code{#f}.\n" | |
1571 | "\n" | |
1572 | "Equality is determined by @code{equal?}, or by the equality\n" | |
1573 | "predicate @var{=} if given. @var{=} is called @code{(= @var{x}\n" | |
1574 | "elem)}, ie.@: with the given @var{x} first, so for example to\n" | |
1575 | "find the first element greater than 5,\n" | |
1576 | "\n" | |
1577 | "@example\n" | |
1578 | "(member 5 '(3 5 1 7 2 9) <) @result{} (7 2 9)\n" | |
1579 | "@end example\n" | |
1580 | "\n" | |
1581 | "This version of @code{member} extends the core @code{member} by\n" | |
1582 | "accepting an equality predicate.") | |
ee6aac97 MD |
1583 | #define FUNC_NAME s_scm_srfi1_member |
1584 | { | |
1585 | scm_t_trampoline_2 equal_p; | |
1586 | SCM_VALIDATE_LIST (2, lst); | |
1587 | if (SCM_UNBNDP (pred)) | |
1588 | equal_p = equal_trampoline; | |
1589 | else | |
1590 | { | |
1591 | equal_p = scm_trampoline_2 (pred); | |
1592 | SCM_ASSERT (equal_p, pred, 3, FUNC_NAME); | |
1593 | } | |
1594 | for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst)) | |
1595 | { | |
2796304a | 1596 | if (scm_is_true (equal_p (pred, x, SCM_CAR (lst)))) |
ee6aac97 MD |
1597 | return lst; |
1598 | } | |
1599 | return SCM_BOOL_F; | |
1600 | } | |
1601 | #undef FUNC_NAME | |
1602 | ||
7692d26b MD |
1603 | SCM_DEFINE (scm_srfi1_assoc, "assoc", 2, 1, 0, |
1604 | (SCM key, SCM alist, SCM pred), | |
1605 | "Behaves like @code{assq} but uses third argument @var{pred?}\n" | |
1606 | "for key comparison. If @var{pred?} is not supplied,\n" | |
1607 | "@code{equal?} is used. (Extended from R5RS.)\n") | |
1608 | #define FUNC_NAME s_scm_srfi1_assoc | |
1609 | { | |
1610 | SCM ls = alist; | |
1611 | scm_t_trampoline_2 equal_p; | |
1612 | if (SCM_UNBNDP (pred)) | |
1613 | equal_p = equal_trampoline; | |
1614 | else | |
1615 | { | |
1616 | equal_p = scm_trampoline_2 (pred); | |
1617 | SCM_ASSERT (equal_p, pred, 3, FUNC_NAME); | |
1618 | } | |
896df2d5 | 1619 | for(; scm_is_pair (ls); ls = SCM_CDR (ls)) |
7692d26b MD |
1620 | { |
1621 | SCM tmp = SCM_CAR (ls); | |
896df2d5 | 1622 | SCM_ASSERT_TYPE (scm_is_pair (tmp), alist, SCM_ARG2, FUNC_NAME, |
7692d26b | 1623 | "association list"); |
9a993171 | 1624 | if (scm_is_true (equal_p (pred, key, SCM_CAR (tmp)))) |
7692d26b MD |
1625 | return tmp; |
1626 | } | |
1627 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (ls), alist, SCM_ARG2, FUNC_NAME, | |
1628 | "association list"); | |
1629 | return SCM_BOOL_F; | |
1630 | } | |
1631 | #undef FUNC_NAME | |
1632 | ||
03731332 KR |
1633 | |
1634 | SCM_DEFINE (scm_srfi1_ninth, "ninth", 1, 0, 0, | |
1635 | (SCM lst), | |
1636 | "Return the ninth element of @var{lst}.") | |
1637 | #define FUNC_NAME s_scm_srfi1_ninth | |
1638 | { | |
b730fbf1 | 1639 | return scm_list_ref (lst, scm_from_int (8)); |
03731332 KR |
1640 | } |
1641 | #undef FUNC_NAME | |
1642 | ||
1643 | ||
e556f8c3 KR |
1644 | SCM_DEFINE (scm_srfi1_not_pair_p, "not-pair?", 1, 0, 0, |
1645 | (SCM obj), | |
1646 | "Return @code{#t} is @var{obj} is not a pair, @code{#f}\n" | |
1647 | "otherwise.\n" | |
1648 | "\n" | |
1649 | "This is shorthand notation @code{(not (pair? @var{obj}))} and\n" | |
1650 | "is supposed to be used for end-of-list checking in contexts\n" | |
1651 | "where dotted lists are allowed.") | |
1652 | #define FUNC_NAME s_scm_srfi1_not_pair_p | |
1653 | { | |
1654 | return scm_from_bool (! scm_is_pair (obj)); | |
1655 | } | |
1656 | #undef FUNC_NAME | |
1657 | ||
1658 | ||
65978fb2 KR |
1659 | SCM_DEFINE (scm_srfi1_partition, "partition", 2, 0, 0, |
1660 | (SCM pred, SCM list), | |
1661 | "Partition the elements of @var{list} with predicate @var{pred}.\n" | |
1662 | "Return two values: the list of elements satifying @var{pred} and\n" | |
1663 | "the list of elements @emph{not} satisfying @var{pred}. The order\n" | |
1664 | "of the output lists follows the order of @var{list}. @var{list}\n" | |
1665 | "is not mutated. One of the output lists may share memory with @var{list}.\n") | |
1666 | #define FUNC_NAME s_scm_srfi1_partition | |
1667 | { | |
1668 | /* In this implementation, the output lists don't share memory with | |
1669 | list, because it's probably not worth the effort. */ | |
1670 | scm_t_trampoline_1 call = scm_trampoline_1(pred); | |
0fb11ae4 | 1671 | SCM orig_list = list; |
65978fb2 KR |
1672 | SCM kept = scm_cons(SCM_EOL, SCM_EOL); |
1673 | SCM kept_tail = kept; | |
1674 | SCM dropped = scm_cons(SCM_EOL, SCM_EOL); | |
1675 | SCM dropped_tail = dropped; | |
1676 | ||
1677 | SCM_ASSERT(call, pred, 2, FUNC_NAME); | |
1678 | ||
1679 | for (; !SCM_NULL_OR_NIL_P (list); list = SCM_CDR(list)) { | |
0fb11ae4 LC |
1680 | SCM elt, new_tail; |
1681 | ||
1682 | /* Make sure LIST is not a dotted list. */ | |
1683 | SCM_ASSERT (scm_is_pair (list), orig_list, SCM_ARG2, FUNC_NAME); | |
1684 | ||
1685 | elt = SCM_CAR (list); | |
1686 | new_tail = scm_cons (SCM_CAR (list), SCM_EOL); | |
1687 | ||
00874d5f | 1688 | if (scm_is_true (call (pred, elt))) { |
65978fb2 KR |
1689 | SCM_SETCDR(kept_tail, new_tail); |
1690 | kept_tail = new_tail; | |
1691 | } | |
1692 | else { | |
1693 | SCM_SETCDR(dropped_tail, new_tail); | |
1694 | dropped_tail = new_tail; | |
1695 | } | |
1696 | } | |
1697 | /* re-use the initial conses for the values list */ | |
1698 | SCM_SETCAR(kept, SCM_CDR(kept)); | |
1699 | SCM_SETCDR(kept, dropped); | |
1700 | SCM_SETCAR(dropped, SCM_CDR(dropped)); | |
1701 | SCM_SETCDR(dropped, SCM_EOL); | |
1702 | return scm_values(kept); | |
1703 | } | |
1704 | #undef FUNC_NAME | |
1705 | ||
2b077051 KR |
1706 | |
1707 | SCM_DEFINE (scm_srfi1_partition_x, "partition!", 2, 0, 0, | |
1708 | (SCM pred, SCM lst), | |
1709 | "Split @var{lst} into those elements which do and don't satisfy\n" | |
1710 | "the predicate @var{pred}.\n" | |
1711 | "\n" | |
1712 | "The return is two values (@pxref{Multiple Values}), the first\n" | |
1713 | "being a list of all elements from @var{lst} which satisfy\n" | |
1714 | "@var{pred}, the second a list of those which do not.\n" | |
1715 | "\n" | |
1716 | "The elements in the result lists are in the same order as in\n" | |
1717 | "@var{lst} but the order in which the calls @code{(@var{pred}\n" | |
1718 | "elem)} are made on the list elements is unspecified.\n" | |
1719 | "\n" | |
1720 | "@var{lst} may be modified to construct the return lists.") | |
1721 | #define FUNC_NAME s_scm_srfi1_partition_x | |
1722 | { | |
1723 | SCM tlst, flst, *tp, *fp; | |
1724 | scm_t_trampoline_1 pred_tramp; | |
1725 | ||
1726 | pred_tramp = scm_trampoline_1 (pred); | |
1727 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
1728 | ||
1729 | /* tlst and flst are the lists of true and false elements. tp and fp are | |
1730 | where to store to append to them, initially &tlst and &flst, then | |
1731 | SCM_CDRLOC of the last pair in the respective lists. */ | |
1732 | ||
1733 | tlst = SCM_EOL; | |
1734 | flst = SCM_EOL; | |
1735 | tp = &tlst; | |
1736 | fp = &flst; | |
1737 | ||
1738 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
1739 | { | |
1740 | if (scm_is_true (pred_tramp (pred, SCM_CAR (lst)))) | |
1741 | { | |
1742 | *tp = lst; | |
1743 | tp = SCM_CDRLOC (lst); | |
1744 | } | |
1745 | else | |
1746 | { | |
1747 | *fp = lst; | |
1748 | fp = SCM_CDRLOC (lst); | |
1749 | } | |
1750 | } | |
1751 | ||
1752 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
1753 | ||
1754 | /* terminate whichever didn't get the last element(s) */ | |
1755 | *tp = SCM_EOL; | |
1756 | *fp = SCM_EOL; | |
1757 | ||
1758 | return scm_values (scm_list_2 (tlst, flst)); | |
1759 | } | |
1760 | #undef FUNC_NAME | |
1761 | ||
1762 | ||
597dbd4e KR |
1763 | SCM_DEFINE (scm_srfi1_reduce, "reduce", 3, 0, 0, |
1764 | (SCM proc, SCM def, SCM lst), | |
1765 | "@code{reduce} is a variant of @code{fold}, where the first call\n" | |
1766 | "to @var{proc} is on two elements from @var{lst}, rather than\n" | |
1767 | "one element and a given initial value.\n" | |
1768 | "\n" | |
1769 | "If @var{lst} is empty, @code{reduce} returns @var{def} (this is\n" | |
1770 | "the only use for @var{def}). If @var{lst} has just one element\n" | |
1771 | "then that's the return value. Otherwise @var{proc} is called\n" | |
1772 | "on the elements of @var{lst}.\n" | |
1773 | "\n" | |
1774 | "Each @var{proc} call is @code{(@var{proc} @var{elem}\n" | |
1775 | "@var{previous})}, where @var{elem} is from @var{lst} (the\n" | |
1776 | "second and subsequent elements of @var{lst}), and\n" | |
1777 | "@var{previous} is the return from the previous call to\n" | |
1778 | "@var{proc}. The first element of @var{lst} is the\n" | |
1779 | "@var{previous} for the first call to @var{proc}.\n" | |
1780 | "\n" | |
1781 | "For example, the following adds a list of numbers, the calls\n" | |
1782 | "made to @code{+} are shown. (Of course @code{+} accepts\n" | |
1783 | "multiple arguments and can add a list directly, with\n" | |
1784 | "@code{apply}.)\n" | |
1785 | "\n" | |
1786 | "@example\n" | |
1787 | "(reduce + 0 '(5 6 7)) @result{} 18\n" | |
1788 | "\n" | |
1789 | "(+ 6 5) @result{} 11\n" | |
1790 | "(+ 7 11) @result{} 18\n" | |
1791 | "@end example\n" | |
1792 | "\n" | |
1793 | "@code{reduce} can be used instead of @code{fold} where the\n" | |
1794 | "@var{init} value is an ``identity'', meaning a value which\n" | |
1795 | "under @var{proc} doesn't change the result, in this case 0 is\n" | |
1796 | "an identity since @code{(+ 5 0)} is just 5. @code{reduce}\n" | |
1797 | "avoids that unnecessary call.") | |
1798 | #define FUNC_NAME s_scm_srfi1_reduce | |
1799 | { | |
1800 | scm_t_trampoline_2 proc_tramp = scm_trampoline_2 (proc); | |
1801 | SCM ret; | |
1802 | ||
1803 | SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME); | |
1804 | ||
1805 | ret = def; /* if lst is empty */ | |
1806 | if (scm_is_pair (lst)) | |
1807 | { | |
1808 | ret = SCM_CAR (lst); /* if lst has one element */ | |
1809 | ||
1810 | for (lst = SCM_CDR (lst); scm_is_pair (lst); lst = SCM_CDR (lst)) | |
1811 | ret = proc_tramp (proc, SCM_CAR (lst), ret); | |
1812 | } | |
1813 | ||
1814 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG3, FUNC_NAME, "list"); | |
1815 | return ret; | |
1816 | } | |
1817 | #undef FUNC_NAME | |
1818 | ||
1819 | ||
1820 | SCM_DEFINE (scm_srfi1_reduce_right, "reduce-right", 3, 0, 0, | |
1821 | (SCM proc, SCM def, SCM lst), | |
1822 | "@code{reduce-right} is a variant of @code{fold-right}, where\n" | |
1823 | "the first call to @var{proc} is on two elements from @var{lst},\n" | |
1824 | "rather than one element and a given initial value.\n" | |
1825 | "\n" | |
1826 | "If @var{lst} is empty, @code{reduce-right} returns @var{def}\n" | |
1827 | "(this is the only use for @var{def}). If @var{lst} has just\n" | |
1828 | "one element then that's the return value. Otherwise @var{proc}\n" | |
1829 | "is called on the elements of @var{lst}.\n" | |
1830 | "\n" | |
1831 | "Each @var{proc} call is @code{(@var{proc} @var{elem}\n" | |
1832 | "@var{previous})}, where @var{elem} is from @var{lst} (the\n" | |
1833 | "second last and then working back to the first element of\n" | |
1834 | "@var{lst}), and @var{previous} is the return from the previous\n" | |
1835 | "call to @var{proc}. The last element of @var{lst} is the\n" | |
1836 | "@var{previous} for the first call to @var{proc}.\n" | |
1837 | "\n" | |
1838 | "For example, the following adds a list of numbers, the calls\n" | |
1839 | "made to @code{+} are shown. (Of course @code{+} accepts\n" | |
1840 | "multiple arguments and can add a list directly, with\n" | |
1841 | "@code{apply}.)\n" | |
1842 | "\n" | |
1843 | "@example\n" | |
1844 | "(reduce-right + 0 '(5 6 7)) @result{} 18\n" | |
1845 | "\n" | |
1846 | "(+ 6 7) @result{} 13\n" | |
1847 | "(+ 5 13) @result{} 18\n" | |
1848 | "@end example\n" | |
1849 | "\n" | |
1850 | "@code{reduce-right} can be used instead of @code{fold-right}\n" | |
1851 | "where the @var{init} value is an ``identity'', meaning a value\n" | |
1852 | "which under @var{proc} doesn't change the result, in this case\n" | |
1853 | "0 is an identity since @code{(+ 7 0)} is just 5.\n" | |
1854 | "@code{reduce-right} avoids that unnecessary call.\n" | |
1855 | "\n" | |
1856 | "@code{reduce} should be preferred over @code{reduce-right} if\n" | |
1857 | "the order of processing doesn't matter, or can be arranged\n" | |
1858 | "either way, since @code{reduce} is a little more efficient.") | |
1859 | #define FUNC_NAME s_scm_srfi1_reduce_right | |
1860 | { | |
1861 | /* To work backwards across a list requires either repeatedly traversing | |
1862 | to get each previous element, or using some memory for a reversed or | |
1863 | random-access form. Repeated traversal might not be too terrible, but | |
1864 | is of course quadratic complexity and hence to be avoided in case LST | |
1865 | is long. A vector is preferred over a reversed list since it's more | |
1866 | compact and is less work for the gc to collect. */ | |
1867 | ||
1868 | scm_t_trampoline_2 proc_tramp = scm_trampoline_2 (proc); | |
1869 | SCM ret, vec; | |
1870 | long len, i; | |
1871 | ||
1872 | SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME); | |
1873 | ||
1874 | if (SCM_NULL_OR_NIL_P (lst)) | |
1875 | return def; | |
1876 | ||
1877 | vec = scm_vector (lst); | |
1878 | len = SCM_SIMPLE_VECTOR_LENGTH (vec); | |
1879 | ||
1880 | ret = SCM_SIMPLE_VECTOR_REF (vec, len-1); | |
1881 | for (i = len-2; i >= 0; i--) | |
1882 | ret = proc_tramp (proc, SCM_SIMPLE_VECTOR_REF (vec, i), ret); | |
1883 | ||
1884 | return ret; | |
1885 | } | |
1886 | #undef FUNC_NAME | |
1887 | ||
1888 | ||
59747b8d KR |
1889 | SCM_DEFINE (scm_srfi1_remove, "remove", 2, 0, 0, |
1890 | (SCM pred, SCM list), | |
1891 | "Return a list containing all elements from @var{lst} which do\n" | |
1892 | "not satisfy the predicate @var{pred}. The elements in the\n" | |
1893 | "result list have the same order as in @var{lst}. The order in\n" | |
1894 | "which @var{pred} is applied to the list elements is not\n" | |
1895 | "specified.") | |
1896 | #define FUNC_NAME s_scm_srfi1_remove | |
1897 | { | |
1898 | scm_t_trampoline_1 call = scm_trampoline_1 (pred); | |
1899 | SCM walk; | |
1900 | SCM *prev; | |
1901 | SCM res = SCM_EOL; | |
1902 | SCM_ASSERT (call, pred, 1, FUNC_NAME); | |
1903 | SCM_VALIDATE_LIST (2, list); | |
1904 | ||
1905 | for (prev = &res, walk = list; | |
1906 | scm_is_pair (walk); | |
1907 | walk = SCM_CDR (walk)) | |
1908 | { | |
1909 | if (scm_is_false (call (pred, SCM_CAR (walk)))) | |
1910 | { | |
1911 | *prev = scm_cons (SCM_CAR (walk), SCM_EOL); | |
1912 | prev = SCM_CDRLOC (*prev); | |
1913 | } | |
1914 | } | |
1915 | ||
1916 | return res; | |
1917 | } | |
1918 | #undef FUNC_NAME | |
1919 | ||
2b077051 KR |
1920 | |
1921 | SCM_DEFINE (scm_srfi1_remove_x, "remove!", 2, 0, 0, | |
1922 | (SCM pred, SCM list), | |
1923 | "Return a list containing all elements from @var{list} which do\n" | |
1924 | "not satisfy the predicate @var{pred}. The elements in the\n" | |
1925 | "result list have the same order as in @var{list}. The order in\n" | |
1926 | "which @var{pred} is applied to the list elements is not\n" | |
1927 | "specified. @var{list} may be modified to build the return\n" | |
1928 | "list.") | |
1929 | #define FUNC_NAME s_scm_srfi1_remove_x | |
1930 | { | |
1931 | scm_t_trampoline_1 call = scm_trampoline_1 (pred); | |
1932 | SCM walk; | |
1933 | SCM *prev; | |
1934 | SCM_ASSERT (call, pred, 1, FUNC_NAME); | |
1935 | SCM_VALIDATE_LIST (2, list); | |
1936 | ||
1937 | for (prev = &list, walk = list; | |
1938 | scm_is_pair (walk); | |
1939 | walk = SCM_CDR (walk)) | |
1940 | { | |
1941 | if (scm_is_false (call (pred, SCM_CAR (walk)))) | |
1942 | prev = SCM_CDRLOC (walk); | |
1943 | else | |
1944 | *prev = SCM_CDR (walk); | |
1945 | } | |
1946 | ||
1947 | return list; | |
1948 | } | |
1949 | #undef FUNC_NAME | |
1950 | ||
1951 | ||
03731332 KR |
1952 | SCM_DEFINE (scm_srfi1_seventh, "seventh", 1, 0, 0, |
1953 | (SCM lst), | |
1954 | "Return the seventh element of @var{lst}.") | |
1955 | #define FUNC_NAME s_scm_srfi1_seventh | |
1956 | { | |
b730fbf1 | 1957 | return scm_list_ref (lst, scm_from_int (6)); |
03731332 KR |
1958 | } |
1959 | #undef FUNC_NAME | |
1960 | ||
1961 | ||
1962 | SCM_DEFINE (scm_srfi1_sixth, "sixth", 1, 0, 0, | |
1963 | (SCM lst), | |
1964 | "Return the sixth element of @var{lst}.") | |
1965 | #define FUNC_NAME s_scm_srfi1_sixth | |
1966 | { | |
b730fbf1 | 1967 | return scm_list_ref (lst, scm_from_int (5)); |
03731332 KR |
1968 | } |
1969 | #undef FUNC_NAME | |
1970 | ||
1971 | ||
597dbd4e KR |
1972 | SCM_DEFINE (scm_srfi1_span, "span", 2, 0, 0, |
1973 | (SCM pred, SCM lst), | |
1974 | "Return two values, the longest initial prefix of @var{lst}\n" | |
1975 | "whose elements all satisfy the predicate @var{pred}, and the\n" | |
1976 | "remainder of @var{lst}.") | |
1977 | #define FUNC_NAME s_scm_srfi1_span | |
1978 | { | |
1979 | scm_t_trampoline_1 pred_tramp; | |
1980 | SCM ret, *p; | |
1981 | ||
1982 | pred_tramp = scm_trampoline_1 (pred); | |
1983 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
1984 | ||
1985 | ret = SCM_EOL; | |
1986 | p = &ret; | |
1987 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
1988 | { | |
1989 | SCM elem = SCM_CAR (lst); | |
1990 | if (scm_is_false (pred_tramp (pred, elem))) | |
1991 | goto done; | |
1992 | ||
1993 | /* want this elem, tack it onto the end of ret */ | |
1994 | *p = scm_cons (elem, SCM_EOL); | |
1995 | p = SCM_CDRLOC (*p); | |
1996 | } | |
1997 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
1998 | ||
1999 | done: | |
2000 | return scm_values (scm_list_2 (ret, lst)); | |
2001 | } | |
2002 | #undef FUNC_NAME | |
2003 | ||
2004 | ||
2005 | SCM_DEFINE (scm_srfi1_span_x, "span!", 2, 0, 0, | |
2006 | (SCM pred, SCM lst), | |
2007 | "Return two values, the longest initial prefix of @var{lst}\n" | |
2008 | "whose elements all satisfy the predicate @var{pred}, and the\n" | |
2009 | "remainder of @var{lst}. @var{lst} may be modified to form the\n" | |
2010 | "return.") | |
2011 | #define FUNC_NAME s_scm_srfi1_span_x | |
2012 | { | |
2013 | SCM upto, *p; | |
2014 | scm_t_trampoline_1 pred_tramp; | |
2015 | ||
2016 | pred_tramp = scm_trampoline_1 (pred); | |
2017 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
2018 | ||
2019 | p = &lst; | |
2020 | for (upto = lst; scm_is_pair (upto); upto = SCM_CDR (upto)) | |
2021 | { | |
2022 | if (scm_is_false (pred_tramp (pred, SCM_CAR (upto)))) | |
2023 | goto done; | |
2024 | ||
2025 | /* want this element */ | |
2026 | p = SCM_CDRLOC (upto); | |
2027 | } | |
2028 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto), lst, SCM_ARG2, FUNC_NAME, "list"); | |
2029 | ||
2030 | done: | |
2031 | *p = SCM_EOL; | |
2032 | return scm_values (scm_list_2 (lst, upto)); | |
2033 | } | |
2034 | #undef FUNC_NAME | |
2035 | ||
2036 | ||
d2f57ee0 KR |
2037 | SCM_DEFINE (scm_srfi1_split_at, "split-at", 2, 0, 0, |
2038 | (SCM lst, SCM n), | |
2039 | "Return two values (multiple values), being a list of the\n" | |
2040 | "elements before index @var{n} in @var{lst}, and a list of those\n" | |
2041 | "after.") | |
2042 | #define FUNC_NAME s_scm_srfi1_split_at | |
2043 | { | |
2044 | size_t nn; | |
2045 | /* pre is a list of elements before the i split point, loc is the CDRLOC | |
2046 | of the last cell, ie. where to store to append to it */ | |
2047 | SCM pre = SCM_EOL; | |
2048 | SCM *loc = ⪯ | |
2049 | ||
2050 | for (nn = scm_to_size_t (n); nn != 0; nn--) | |
2051 | { | |
2052 | SCM_VALIDATE_CONS (SCM_ARG1, lst); | |
2053 | ||
2054 | *loc = scm_cons (SCM_CAR (lst), SCM_EOL); | |
2055 | loc = SCM_CDRLOC (*loc); | |
2056 | lst = SCM_CDR(lst); | |
2057 | } | |
2058 | return scm_values (scm_list_2 (pre, lst)); | |
2059 | } | |
2060 | #undef FUNC_NAME | |
2061 | ||
2062 | ||
2063 | SCM_DEFINE (scm_srfi1_split_at_x, "split-at!", 2, 0, 0, | |
2064 | (SCM lst, SCM n), | |
2065 | "Return two values (multiple values), being a list of the\n" | |
2066 | "elements before index @var{n} in @var{lst}, and a list of those\n" | |
2067 | "after. @var{lst} is modified to form those values.") | |
2068 | #define FUNC_NAME s_scm_srfi1_split_at | |
2069 | { | |
2070 | size_t nn; | |
2071 | SCM upto = lst; | |
2072 | SCM *loc = &lst; | |
2073 | ||
2074 | for (nn = scm_to_size_t (n); nn != 0; nn--) | |
2075 | { | |
2076 | SCM_VALIDATE_CONS (SCM_ARG1, upto); | |
2077 | ||
2078 | loc = SCM_CDRLOC (upto); | |
2079 | upto = SCM_CDR (upto); | |
2080 | } | |
2081 | ||
2082 | *loc = SCM_EOL; | |
2083 | return scm_values (scm_list_2 (lst, upto)); | |
2084 | } | |
2085 | #undef FUNC_NAME | |
2086 | ||
2087 | ||
597dbd4e KR |
2088 | SCM_DEFINE (scm_srfi1_take_x, "take!", 2, 0, 0, |
2089 | (SCM lst, SCM n), | |
2090 | "Return a list containing the first @var{n} elements of\n" | |
2091 | "@var{lst}.") | |
2092 | #define FUNC_NAME s_scm_srfi1_take_x | |
2093 | { | |
2094 | long nn; | |
2095 | SCM pos; | |
2096 | ||
b730fbf1 | 2097 | nn = scm_to_signed_integer (n, 0, LONG_MAX); |
597dbd4e KR |
2098 | if (nn == 0) |
2099 | return SCM_EOL; | |
2100 | ||
b730fbf1 | 2101 | pos = scm_list_tail (lst, scm_from_long (nn - 1)); |
597dbd4e KR |
2102 | |
2103 | /* Must have at least one cell left, mustn't have reached the end of an | |
2104 | n-1 element list. SCM_VALIDATE_CONS here gives the same error as | |
2105 | scm_list_tail does on say an n-2 element list, though perhaps a range | |
2106 | error would make more sense (for both). */ | |
2107 | SCM_VALIDATE_CONS (SCM_ARG1, pos); | |
2108 | ||
2109 | SCM_SETCDR (pos, SCM_EOL); | |
2110 | return lst; | |
2111 | } | |
2112 | #undef FUNC_NAME | |
2113 | ||
2114 | ||
2b077051 KR |
2115 | SCM_DEFINE (scm_srfi1_take_right, "take-right", 2, 0, 0, |
2116 | (SCM lst, SCM n), | |
2117 | "Return the a list containing the @var{n} last elements of\n" | |
2118 | "@var{lst}.") | |
2119 | #define FUNC_NAME s_scm_srfi1_take_right | |
2120 | { | |
2121 | SCM tail = scm_list_tail (lst, n); | |
2122 | while (scm_is_pair (tail)) | |
2123 | { | |
2124 | lst = SCM_CDR (lst); | |
2125 | tail = SCM_CDR (tail); | |
2126 | } | |
2127 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail), tail, SCM_ARG1, FUNC_NAME, "list"); | |
2128 | return lst; | |
2129 | } | |
2130 | #undef FUNC_NAME | |
2131 | ||
2132 | ||
597dbd4e KR |
2133 | SCM_DEFINE (scm_srfi1_take_while, "take-while", 2, 0, 0, |
2134 | (SCM pred, SCM lst), | |
2135 | "Return a new list which is the longest initial prefix of\n" | |
2136 | "@var{lst} whose elements all satisfy the predicate @var{pred}.") | |
2137 | #define FUNC_NAME s_scm_srfi1_take_while | |
2138 | { | |
2139 | scm_t_trampoline_1 pred_tramp; | |
2140 | SCM ret, *p; | |
2141 | ||
2142 | pred_tramp = scm_trampoline_1 (pred); | |
2143 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
2144 | ||
2145 | ret = SCM_EOL; | |
2146 | p = &ret; | |
2147 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
2148 | { | |
2149 | SCM elem = SCM_CAR (lst); | |
2150 | if (scm_is_false (pred_tramp (pred, elem))) | |
2151 | goto done; | |
2152 | ||
2153 | /* want this elem, tack it onto the end of ret */ | |
2154 | *p = scm_cons (elem, SCM_EOL); | |
2155 | p = SCM_CDRLOC (*p); | |
2156 | } | |
2157 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
2158 | ||
2159 | done: | |
2160 | return ret; | |
2161 | } | |
2162 | #undef FUNC_NAME | |
2163 | ||
2164 | ||
2165 | SCM_DEFINE (scm_srfi1_take_while_x, "take-while!", 2, 0, 0, | |
2166 | (SCM pred, SCM lst), | |
2167 | "Return the longest initial prefix of @var{lst} whose elements\n" | |
2168 | "all satisfy the predicate @var{pred}. @var{lst} may be\n" | |
2169 | "modified to form the return.") | |
2170 | #define FUNC_NAME s_scm_srfi1_take_while_x | |
2171 | { | |
2172 | SCM upto, *p; | |
2173 | scm_t_trampoline_1 pred_tramp; | |
2174 | ||
2175 | pred_tramp = scm_trampoline_1 (pred); | |
2176 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
2177 | ||
2178 | p = &lst; | |
2179 | for (upto = lst; scm_is_pair (upto); upto = SCM_CDR (upto)) | |
2180 | { | |
2181 | if (scm_is_false (pred_tramp (pred, SCM_CAR (upto)))) | |
2182 | goto done; | |
2183 | ||
2184 | /* want this element */ | |
2185 | p = SCM_CDRLOC (upto); | |
2186 | } | |
2187 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (upto), lst, SCM_ARG2, FUNC_NAME, "list"); | |
2188 | ||
2189 | done: | |
2190 | *p = SCM_EOL; | |
2191 | return lst; | |
2192 | } | |
2193 | #undef FUNC_NAME | |
2194 | ||
2195 | ||
03731332 KR |
2196 | SCM_DEFINE (scm_srfi1_tenth, "tenth", 1, 0, 0, |
2197 | (SCM lst), | |
2198 | "Return the tenth element of @var{lst}.") | |
2199 | #define FUNC_NAME s_scm_srfi1_tenth | |
2200 | { | |
b730fbf1 | 2201 | return scm_list_ref (lst, scm_from_int (9)); |
03731332 KR |
2202 | } |
2203 | #undef FUNC_NAME | |
2204 | ||
2205 | ||
e556f8c3 KR |
2206 | SCM_DEFINE (scm_srfi1_xcons, "xcons", 2, 0, 0, |
2207 | (SCM d, SCM a), | |
2208 | "Like @code{cons}, but with interchanged arguments. Useful\n" | |
2209 | "mostly when passed to higher-order procedures.") | |
2210 | #define FUNC_NAME s_scm_srfi1_xcons | |
2211 | { | |
2212 | return scm_cons (a, d); | |
2213 | } | |
2214 | #undef FUNC_NAME | |
2215 | ||
2216 | ||
ee6aac97 MD |
2217 | void |
2218 | scm_init_srfi_1 (void) | |
2219 | { | |
a48d60b1 | 2220 | SCM the_root_module = scm_lookup_closure_module (SCM_BOOL_F); |
ee6aac97 MD |
2221 | #ifndef SCM_MAGIC_SNARFER |
2222 | #include "srfi/srfi-1.x" | |
2223 | #endif | |
a48d60b1 MD |
2224 | scm_c_extend_primitive_generic |
2225 | (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module, "map")), | |
2226 | SCM_VARIABLE_REF (scm_c_lookup ("map"))); | |
2227 | scm_c_extend_primitive_generic | |
2228 | (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module, "for-each")), | |
2229 | SCM_VARIABLE_REF (scm_c_lookup ("for-each"))); | |
ee6aac97 MD |
2230 | } |
2231 | ||
2232 | /* End of srfi-1.c. */ |