Commit | Line | Data |
---|---|---|
ee6aac97 MD |
1 | /* srfi-1.c --- SRFI-1 procedures for Guile |
2 | * | |
d0a634de KR |
3 | * Copyright (C) 1995, 1996, 1997, 2000, 2001, 2002, 2003 Free Software |
4 | * Foundation, Inc. | |
ee6aac97 | 5 | * |
73be1d9e MV |
6 | * This library is free software; you can redistribute it and/or |
7 | * modify it under the terms of the GNU Lesser General Public | |
8 | * License as published by the Free Software Foundation; either | |
9 | * version 2.1 of the License, or (at your option) any later version. | |
ee6aac97 | 10 | * |
73be1d9e MV |
11 | * This library is distributed in the hope that it will be useful, |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
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 | |
18 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
19 | */ | |
ee6aac97 MD |
20 | |
21 | #include <libguile.h> | |
22 | #include <libguile/lang.h> | |
23 | ||
24 | #include "srfi-1.h" | |
25 | ||
26 | /* The intent of this file is to gradually replace those Scheme | |
27 | * procedures in srfi-1.scm which extends core primitive procedures, | |
28 | * so that using srfi-1 won't have performance penalties. | |
29 | * | |
30 | * Please feel free to contribute any new replacements! | |
31 | */ | |
32 | ||
33 | static long | |
34 | srfi1_ilength (SCM sx) | |
35 | { | |
36 | long i = 0; | |
37 | SCM tortoise = sx; | |
38 | SCM hare = sx; | |
39 | ||
40 | do { | |
41 | if (SCM_NULL_OR_NIL_P(hare)) return i; | |
896df2d5 | 42 | if (!scm_is_pair (hare)) return -2; |
ee6aac97 MD |
43 | hare = SCM_CDR(hare); |
44 | i++; | |
45 | if (SCM_NULL_OR_NIL_P(hare)) return i; | |
896df2d5 | 46 | if (!scm_is_pair (hare)) return -2; |
ee6aac97 MD |
47 | hare = SCM_CDR(hare); |
48 | i++; | |
49 | /* For every two steps the hare takes, the tortoise takes one. */ | |
50 | tortoise = SCM_CDR(tortoise); | |
51 | } | |
bc36d050 | 52 | while (! scm_is_eq (hare, tortoise)); |
ee6aac97 MD |
53 | |
54 | /* If the tortoise ever catches the hare, then the list must contain | |
55 | a cycle. */ | |
56 | return -1; | |
57 | } | |
58 | ||
d0a634de KR |
59 | static SCM |
60 | equal_trampoline (SCM proc, SCM arg1, SCM arg2) | |
61 | { | |
62 | return scm_equal_p (arg1, arg2); | |
63 | } | |
64 | ||
65 | ||
b1fff4e7 KR |
66 | SCM_DEFINE (scm_srfi1_alist_copy, "alist-copy", 1, 0, 0, |
67 | (SCM alist), | |
68 | "Return a copy of @var{alist}, copying both the pairs comprising\n" | |
69 | "the list and those making the associations.") | |
70 | #define FUNC_NAME s_scm_srfi1_alist_copy | |
71 | { | |
72 | SCM ret, *p, elem, c; | |
73 | ||
74 | /* ret is the list to return. p is where to append to it, initially &ret | |
75 | then SCM_CDRLOC of the last pair. */ | |
76 | ret = SCM_EOL; | |
77 | p = &ret; | |
78 | ||
79 | for ( ; scm_is_pair (alist); alist = SCM_CDR (alist)) | |
80 | { | |
81 | elem = SCM_CAR (alist); | |
82 | ||
83 | /* each element of alist must be a pair */ | |
84 | SCM_ASSERT_TYPE (scm_is_pair (elem), alist, SCM_ARG1, FUNC_NAME, | |
85 | "association list"); | |
86 | ||
87 | c = scm_cons (scm_cons (SCM_CAR (elem), SCM_CDR (elem)), SCM_EOL); | |
88 | *p = c; | |
89 | p = SCM_CDRLOC (c); | |
90 | } | |
91 | ||
92 | /* alist must be a proper list */ | |
93 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (alist), alist, SCM_ARG1, FUNC_NAME, | |
94 | "association list"); | |
95 | return ret; | |
96 | } | |
97 | #undef FUNC_NAME | |
98 | ||
99 | ||
47f2726f KR |
100 | /* scm_append and scm_append_x don't modify their list argument (only the |
101 | lists within that list in the case of scm_append_x), hence making them | |
102 | suitable for direct use for concatentate. */ | |
103 | ||
104 | SCM_REGISTER_PROC (s_srfi1_concatenate, "concatenate", 1, 0, 0, scm_append); | |
105 | SCM_REGISTER_PROC (s_srfi1_concatenate_x, "concatenate!", 1, 0, 0, scm_append_x); | |
106 | ||
107 | ||
110348ae | 108 | SCM_DEFINE (scm_srfi1_count, "count", 2, 0, 1, |
edea856c | 109 | (SCM pred, SCM list1, SCM rest), |
110348ae KR |
110 | "Return a count of the number of times @var{pred} returns true\n" |
111 | "when called on elements from the given lists.\n" | |
112 | "\n" | |
113 | "@var{pred} is called with @var{N} parameters @code{(@var{pred}\n" | |
114 | "@var{elem1} @dots{} @var{elemN})}, each element being from the\n" | |
edea856c | 115 | "corresponding @var{list1} @dots{} @var{lstN}. The first call is\n" |
110348ae KR |
116 | "with the first element of each list, the second with the second\n" |
117 | "element from each, and so on.\n" | |
118 | "\n" | |
119 | "Counting stops when the end of the shortest list is reached.\n" | |
120 | "At least one list must be non-circular.") | |
121 | #define FUNC_NAME s_scm_srfi1_count | |
122 | { | |
123 | long count; | |
5fc743b4 KR |
124 | SCM lst; |
125 | int argnum; | |
110348ae KR |
126 | SCM_VALIDATE_REST_ARGUMENT (rest); |
127 | ||
128 | count = 0; | |
129 | ||
896df2d5 | 130 | if (scm_is_null (rest)) |
110348ae KR |
131 | { |
132 | /* one list */ | |
133 | scm_t_trampoline_1 pred_tramp; | |
134 | pred_tramp = scm_trampoline_1 (pred); | |
135 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
136 | ||
896df2d5 | 137 | for ( ; scm_is_pair (list1); list1 = SCM_CDR (list1)) |
edea856c | 138 | count += scm_is_true (pred_tramp (pred, SCM_CAR (list1))); |
110348ae | 139 | |
5fc743b4 KR |
140 | /* check below that list1 is a proper list, and done */ |
141 | end_list1: | |
142 | lst = list1; | |
143 | argnum = 2; | |
110348ae | 144 | } |
896df2d5 | 145 | else if (scm_is_pair (rest) && scm_is_null (SCM_CDR (rest))) |
110348ae KR |
146 | { |
147 | /* two lists */ | |
148 | scm_t_trampoline_2 pred_tramp; | |
edea856c | 149 | SCM list2; |
110348ae KR |
150 | |
151 | pred_tramp = scm_trampoline_2 (pred); | |
152 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
153 | ||
edea856c | 154 | list2 = SCM_CAR (rest); |
110348ae KR |
155 | for (;;) |
156 | { | |
896df2d5 | 157 | if (! scm_is_pair (list1)) |
5fc743b4 | 158 | goto end_list1; |
896df2d5 | 159 | if (! scm_is_pair (list2)) |
110348ae | 160 | { |
5fc743b4 KR |
161 | lst = list2; |
162 | argnum = 3; | |
110348ae KR |
163 | break; |
164 | } | |
00874d5f | 165 | count += scm_is_true (pred_tramp |
edea856c SJ |
166 | (pred, SCM_CAR (list1), SCM_CAR (list2))); |
167 | list1 = SCM_CDR (list1); | |
168 | list2 = SCM_CDR (list2); | |
110348ae KR |
169 | } |
170 | } | |
171 | else | |
172 | { | |
173 | /* three or more lists */ | |
5fc743b4 | 174 | SCM lstlst, args, l, a; |
110348ae KR |
175 | |
176 | /* lstlst is a list of the list arguments */ | |
edea856c | 177 | lstlst = scm_cons (list1, rest); |
110348ae KR |
178 | |
179 | /* args is the argument list to pass to pred, same length as lstlst, | |
180 | re-used for each call */ | |
5fc743b4 | 181 | args = scm_list_copy (lstlst); |
110348ae KR |
182 | |
183 | for (;;) | |
184 | { | |
185 | /* first elem of each list in lstlst into args, and step those | |
186 | lstlst entries onto their next element */ | |
187 | for (l = lstlst, a = args, argnum = 2; | |
896df2d5 | 188 | scm_is_pair (l); |
110348ae KR |
189 | l = SCM_CDR (l), a = SCM_CDR (a), argnum++) |
190 | { | |
191 | lst = SCM_CAR (l); /* list argument */ | |
896df2d5 | 192 | if (! scm_is_pair (lst)) |
5fc743b4 | 193 | goto check_lst_and_done; |
110348ae KR |
194 | SCM_SETCAR (a, SCM_CAR (lst)); /* arg for pred */ |
195 | SCM_SETCAR (l, SCM_CDR (lst)); /* keep rest of lst */ | |
196 | } | |
197 | ||
00874d5f | 198 | count += scm_is_true (scm_apply (pred, args, SCM_EOL)); |
110348ae KR |
199 | } |
200 | } | |
5fc743b4 KR |
201 | |
202 | check_lst_and_done: | |
203 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list"); | |
93ccaef0 | 204 | return scm_from_long (count); |
110348ae KR |
205 | } |
206 | #undef FUNC_NAME | |
207 | ||
208 | ||
d0a634de KR |
209 | SCM_DEFINE (scm_srfi1_delete, "delete", 2, 1, 0, |
210 | (SCM x, SCM lst, SCM pred), | |
211 | "Return a list containing the elements of @var{lst} but with\n" | |
212 | "those equal to @var{x} deleted. The returned elements will be\n" | |
213 | "in the same order as they were in @var{lst}.\n" | |
214 | "\n" | |
215 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
216 | "given. An equality call is made just once for each element,\n" | |
217 | "but the order in which the calls are made on the elements is\n" | |
218 | "unspecified.\n" | |
219 | "\n" | |
220 | "The equality calls are always @code{(pred x elem)}, ie.@: the\n" | |
221 | "given @var{x} is first. This means for instance elements\n" | |
222 | "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n" | |
223 | "\n" | |
224 | "@var{lst} is not modified, but the returned list might share a\n" | |
225 | "common tail with @var{lst}.") | |
226 | #define FUNC_NAME s_scm_srfi1_delete | |
227 | { | |
228 | scm_t_trampoline_2 equal_p; | |
229 | SCM ret, *p, keeplst; | |
230 | ||
231 | if (SCM_UNBNDP (pred)) | |
232 | return scm_delete (x, lst); | |
233 | ||
234 | equal_p = scm_trampoline_2 (pred); | |
235 | SCM_ASSERT (equal_p, pred, SCM_ARG3, FUNC_NAME); | |
236 | ||
237 | /* ret is the return list being constructed. p is where to append to it, | |
238 | initially &ret then SCM_CDRLOC of the last pair. lst progresses as | |
239 | elements are considered. | |
240 | ||
241 | Elements to be retained are not immediately copied, instead keeplst is | |
242 | the last pair in lst which is to be retained but not yet copied. When | |
243 | there's no more deletions, *p can be set to keeplst to share the | |
244 | remainder of the original lst. (The entire original lst if there's no | |
245 | deletions at all.) */ | |
246 | ||
247 | keeplst = lst; | |
248 | ret = SCM_EOL; | |
249 | p = &ret; | |
250 | ||
896df2d5 | 251 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) |
d0a634de | 252 | { |
00874d5f | 253 | if (scm_is_true (equal_p (pred, x, SCM_CAR (lst)))) |
d0a634de KR |
254 | { |
255 | /* delete this element, so copy from keeplst (inclusive) to lst | |
256 | (exclusive) onto ret */ | |
bc36d050 | 257 | while (! scm_is_eq (keeplst, lst)) |
d0a634de KR |
258 | { |
259 | SCM c = scm_cons (SCM_CAR (keeplst), SCM_EOL); | |
260 | *p = c; | |
261 | p = SCM_CDRLOC (c); | |
262 | keeplst = SCM_CDR (keeplst); | |
263 | } | |
264 | ||
265 | keeplst = SCM_CDR (lst); | |
266 | } | |
267 | } | |
268 | ||
269 | /* final retained elements */ | |
270 | *p = keeplst; | |
271 | ||
272 | /* demand that lst was a proper list */ | |
273 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
274 | ||
275 | return ret; | |
276 | } | |
277 | #undef FUNC_NAME | |
278 | ||
279 | ||
280 | SCM_DEFINE (scm_srfi1_delete_x, "delete!", 2, 1, 0, | |
281 | (SCM x, SCM lst, SCM pred), | |
282 | "Return a list containing the elements of @var{lst} but with\n" | |
283 | "those equal to @var{x} deleted. The returned elements will be\n" | |
284 | "in the same order as they were in @var{lst}.\n" | |
285 | "\n" | |
286 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
287 | "given. An equality call is made just once for each element,\n" | |
288 | "but the order in which the calls are made on the elements is\n" | |
289 | "unspecified.\n" | |
290 | "\n" | |
291 | "The equality calls are always @code{(pred x elem)}, ie.@: the\n" | |
292 | "given @var{x} is first. This means for instance elements\n" | |
293 | "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n" | |
294 | "\n" | |
295 | "@var{lst} may be modified to construct the returned list.") | |
296 | #define FUNC_NAME s_scm_srfi1_delete_x | |
297 | { | |
298 | scm_t_trampoline_2 equal_p; | |
299 | SCM walk; | |
300 | SCM *prev; | |
301 | ||
302 | if (SCM_UNBNDP (pred)) | |
303 | return scm_delete_x (x, lst); | |
304 | ||
305 | equal_p = scm_trampoline_2 (pred); | |
306 | SCM_ASSERT (equal_p, pred, SCM_ARG3, FUNC_NAME); | |
307 | ||
308 | for (prev = &lst, walk = lst; | |
896df2d5 | 309 | scm_is_pair (walk); |
d0a634de KR |
310 | walk = SCM_CDR (walk)) |
311 | { | |
00874d5f | 312 | if (scm_is_true (equal_p (pred, x, SCM_CAR (walk)))) |
d0a634de KR |
313 | *prev = SCM_CDR (walk); |
314 | else | |
315 | prev = SCM_CDRLOC (walk); | |
316 | } | |
317 | ||
318 | /* demand the input was a proper list */ | |
319 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (walk), walk, SCM_ARG2, FUNC_NAME,"list"); | |
320 | return lst; | |
321 | } | |
322 | #undef FUNC_NAME | |
323 | ||
324 | ||
325 | SCM_DEFINE (scm_srfi1_delete_duplicates, "delete-duplicates", 1, 1, 0, | |
326 | (SCM lst, SCM pred), | |
327 | "Return a list containing the elements of @var{lst} but without\n" | |
328 | "duplicates.\n" | |
329 | "\n" | |
330 | "When elements are equal, only the first in @var{lst} is\n" | |
331 | "retained. Equal elements can be anywhere in @var{lst}, they\n" | |
332 | "don't have to be adjacent. The returned list will have the\n" | |
333 | "retained elements in the same order as they were in @var{lst}.\n" | |
334 | "\n" | |
335 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
336 | "given. Calls @code{(pred x y)} are made with element @var{x}\n" | |
337 | "being before @var{y} in @var{lst}. A call is made at most once\n" | |
338 | "for each combination, but the sequence of the calls across the\n" | |
339 | "elements is unspecified.\n" | |
340 | "\n" | |
341 | "@var{lst} is not modified, but the return might share a common\n" | |
342 | "tail with @var{lst}.\n" | |
343 | "\n" | |
344 | "In the worst case, this is an @math{O(N^2)} algorithm because\n" | |
345 | "it must check each element against all those preceding it. For\n" | |
346 | "long lists it is more efficient to sort and then compare only\n" | |
347 | "adjacent elements.") | |
348 | #define FUNC_NAME s_scm_srfi1_delete_duplicates | |
349 | { | |
350 | scm_t_trampoline_2 equal_p; | |
351 | SCM ret, *p, keeplst, item, l; | |
352 | ||
353 | /* ret is the new list constructed. p is where to append, initially &ret | |
354 | then SCM_CDRLOC of the last pair. lst is advanced as each element is | |
355 | considered. | |
356 | ||
357 | Elements retained are not immediately appended to ret, instead keeplst | |
358 | is the last pair in lst which is to be kept but is not yet copied. | |
359 | Initially this is the first pair of lst, since the first element is | |
360 | always retained. | |
361 | ||
362 | *p is kept set to keeplst, so ret (inclusive) to lst (exclusive) is all | |
363 | the elements retained, making the equality search loop easy. | |
364 | ||
365 | If an item must be deleted, elements from keeplst (inclusive) to lst | |
366 | (exclusive) must be copied and appended to ret. When there's no more | |
367 | deletions, *p is left set to keeplst, so ret shares structure with the | |
368 | original lst. (ret will be the entire original lst if there are no | |
369 | deletions.) */ | |
370 | ||
371 | /* skip to end if an empty list (or something invalid) */ | |
372 | ret = lst; | |
896df2d5 | 373 | if (scm_is_pair (lst)) |
d0a634de KR |
374 | { |
375 | if (SCM_UNBNDP (pred)) | |
376 | equal_p = equal_trampoline; | |
377 | else | |
378 | { | |
379 | equal_p = scm_trampoline_2 (pred); | |
380 | SCM_ASSERT (equal_p, pred, SCM_ARG2, FUNC_NAME); | |
381 | } | |
382 | ||
383 | keeplst = lst; | |
384 | p = &ret; | |
385 | ||
386 | /* loop over lst elements starting from second */ | |
387 | for (;;) | |
388 | { | |
389 | lst = SCM_CDR (lst); | |
896df2d5 | 390 | if (! scm_is_pair (lst)) |
d0a634de KR |
391 | break; |
392 | item = SCM_CAR (lst); | |
393 | ||
394 | /* loop searching ret upto lst */ | |
bc36d050 | 395 | for (l = ret; ! scm_is_eq (l, lst); l = SCM_CDR (l)) |
d0a634de | 396 | { |
00874d5f | 397 | if (scm_is_true (equal_p (pred, SCM_CAR (l), item))) |
d0a634de KR |
398 | { |
399 | /* duplicate, don't want this element, so copy keeplst | |
400 | (inclusive) to lst (exclusive) onto ret */ | |
bc36d050 | 401 | while (! scm_is_eq (keeplst, lst)) |
d0a634de KR |
402 | { |
403 | SCM c = scm_cons (SCM_CAR (keeplst), SCM_EOL); | |
404 | *p = c; | |
405 | p = SCM_CDRLOC (c); | |
406 | keeplst = SCM_CDR (keeplst); | |
407 | } | |
408 | ||
409 | keeplst = SCM_CDR (lst); /* elem after the one deleted */ | |
410 | *p = keeplst; | |
411 | break; | |
412 | } | |
413 | } | |
414 | } | |
415 | } | |
416 | ||
417 | /* demand that lst was a proper list */ | |
418 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list"); | |
419 | ||
420 | return ret; | |
421 | } | |
422 | #undef FUNC_NAME | |
423 | ||
424 | ||
425 | SCM_DEFINE (scm_srfi1_delete_duplicates_x, "delete-duplicates!", 1, 1, 0, | |
426 | (SCM lst, SCM pred), | |
427 | "Return a list containing the elements of @var{lst} but without\n" | |
428 | "duplicates.\n" | |
429 | "\n" | |
430 | "When elements are equal, only the first in @var{lst} is\n" | |
431 | "retained. Equal elements can be anywhere in @var{lst}, they\n" | |
432 | "don't have to be adjacent. The returned list will have the\n" | |
433 | "retained elements in the same order as they were in @var{lst}.\n" | |
434 | "\n" | |
435 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
436 | "given. Calls @code{(pred x y)} are made with element @var{x}\n" | |
437 | "being before @var{y} in @var{lst}. A call is made at most once\n" | |
438 | "for each combination, but the sequence of the calls across the\n" | |
439 | "elements is unspecified.\n" | |
440 | "\n" | |
441 | "@var{lst} may be modified to construct the returned list.\n" | |
442 | "\n" | |
443 | "In the worst case, this is an @math{O(N^2)} algorithm because\n" | |
444 | "it must check each element against all those preceding it. For\n" | |
445 | "long lists it is more efficient to sort and then compare only\n" | |
446 | "adjacent elements.") | |
447 | #define FUNC_NAME s_scm_srfi1_delete_duplicates_x | |
448 | { | |
449 | scm_t_trampoline_2 equal_p; | |
450 | SCM ret, endret, item, l; | |
451 | ||
452 | /* ret is the return list, constructed from the pairs in lst. endret is | |
453 | the last pair of ret, initially the first pair. lst is advanced as | |
454 | elements are considered. */ | |
455 | ||
456 | /* skip to end if an empty list (or something invalid) */ | |
457 | ret = lst; | |
896df2d5 | 458 | if (scm_is_pair (lst)) |
d0a634de KR |
459 | { |
460 | if (SCM_UNBNDP (pred)) | |
461 | equal_p = equal_trampoline; | |
462 | else | |
463 | { | |
464 | equal_p = scm_trampoline_2 (pred); | |
465 | SCM_ASSERT (equal_p, pred, SCM_ARG2, FUNC_NAME); | |
466 | } | |
467 | ||
468 | endret = ret; | |
469 | ||
470 | /* loop over lst elements starting from second */ | |
471 | for (;;) | |
472 | { | |
473 | lst = SCM_CDR (lst); | |
896df2d5 | 474 | if (! scm_is_pair (lst)) |
d0a634de KR |
475 | break; |
476 | item = SCM_CAR (lst); | |
477 | ||
478 | /* is item equal to any element from ret to endret (inclusive)? */ | |
479 | l = ret; | |
480 | for (;;) | |
481 | { | |
00874d5f | 482 | if (scm_is_true (equal_p (pred, SCM_CAR (l), item))) |
d0a634de KR |
483 | break; /* equal, forget this element */ |
484 | ||
bc36d050 | 485 | if (scm_is_eq (l, endret)) |
d0a634de KR |
486 | { |
487 | /* not equal to any, so append this pair */ | |
488 | SCM_SETCDR (endret, lst); | |
489 | endret = lst; | |
490 | break; | |
491 | } | |
492 | l = SCM_CDR (l); | |
493 | } | |
494 | } | |
495 | ||
496 | /* terminate, in case last element was deleted */ | |
497 | SCM_SETCDR (endret, SCM_EOL); | |
498 | } | |
499 | ||
500 | /* demand that lst was a proper list */ | |
501 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list"); | |
502 | ||
503 | return ret; | |
504 | } | |
505 | #undef FUNC_NAME | |
506 | ||
507 | ||
2b077051 KR |
508 | SCM_DEFINE (scm_srfi1_drop_right, "drop-right", 2, 0, 0, |
509 | (SCM lst, SCM n), | |
510 | "Return a new list containing all except the last @var{n}\n" | |
511 | "elements of @var{lst}.") | |
512 | #define FUNC_NAME s_scm_srfi1_drop_right | |
513 | { | |
514 | SCM tail = scm_list_tail (lst, n); | |
515 | SCM ret = SCM_EOL; | |
516 | SCM *rend = &ret; | |
517 | while (scm_is_pair (tail)) | |
518 | { | |
519 | *rend = scm_cons (SCM_CAR (lst), SCM_EOL); | |
520 | rend = SCM_CDRLOC (*rend); | |
521 | ||
522 | lst = SCM_CDR (lst); | |
523 | tail = SCM_CDR (tail); | |
524 | } | |
525 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail), tail, SCM_ARG1, FUNC_NAME, "list"); | |
526 | return ret; | |
527 | } | |
528 | #undef FUNC_NAME | |
c1635946 KR |
529 | |
530 | ||
531 | SCM_DEFINE (scm_srfi1_filter_map, "filter-map", 2, 0, 1, | |
532 | (SCM proc, SCM list1, SCM rest), | |
533 | "Apply @var{proc} to to the elements of @var{list1} @dots{} and\n" | |
534 | "return a list of the results as per SRFI-1 @code{map}, except\n" | |
535 | "that any @code{#f} results are omitted from the list returned.") | |
536 | #define FUNC_NAME s_scm_srfi1_filter_map | |
537 | { | |
538 | SCM ret, *loc, elem, newcell, lst; | |
539 | int argnum; | |
540 | ||
541 | SCM_VALIDATE_REST_ARGUMENT (rest); | |
542 | ||
543 | ret = SCM_EOL; | |
544 | loc = &ret; | |
545 | ||
546 | if (SCM_NULLP (rest)) | |
547 | { | |
548 | /* one list */ | |
549 | scm_t_trampoline_1 proc_tramp = scm_trampoline_1 (proc); | |
550 | SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME); | |
551 | ||
552 | for ( ; scm_is_pair (list1); list1 = SCM_CDR (list1)) | |
553 | { | |
554 | elem = proc_tramp (proc, SCM_CAR (list1)); | |
555 | if (scm_is_true (elem)) | |
556 | { | |
557 | newcell = scm_cons (elem, SCM_EOL); | |
558 | *loc = newcell; | |
559 | loc = SCM_CDRLOC (newcell); | |
560 | } | |
561 | } | |
562 | ||
563 | /* check below that list1 is a proper list, and done */ | |
6507b831 | 564 | end_list1: |
c1635946 KR |
565 | lst = list1; |
566 | argnum = 2; | |
567 | } | |
568 | else if (SCM_NULLP (SCM_CDR (rest))) | |
569 | { | |
570 | /* two lists */ | |
571 | scm_t_trampoline_2 proc_tramp = scm_trampoline_2 (proc); | |
572 | SCM list2 = SCM_CAR (rest); | |
573 | SCM_ASSERT (proc_tramp, proc, SCM_ARG1, FUNC_NAME); | |
574 | ||
575 | for (;;) | |
576 | { | |
577 | if (! scm_is_pair (list1)) | |
6507b831 | 578 | goto end_list1; |
c1635946 KR |
579 | if (! scm_is_pair (list2)) |
580 | { | |
581 | lst = list2; | |
582 | argnum = 3; | |
583 | goto check_lst_and_done; | |
584 | } | |
585 | elem = proc_tramp (proc, SCM_CAR (list1), SCM_CAR (list2)); | |
586 | if (scm_is_true (elem)) | |
587 | { | |
588 | newcell = scm_cons (elem, SCM_EOL); | |
589 | *loc = newcell; | |
590 | loc = SCM_CDRLOC (newcell); | |
591 | } | |
592 | list1 = SCM_CDR (list1); | |
593 | list2 = SCM_CDR (list2); | |
594 | } | |
595 | } | |
596 | else | |
597 | { | |
598 | /* three or more lists */ | |
599 | SCM lstlst, args, l, a; | |
600 | ||
601 | /* lstlst is a list of the list arguments */ | |
602 | lstlst = scm_cons (list1, rest); | |
603 | ||
604 | /* args is the argument list to pass to proc, same length as lstlst, | |
605 | re-used for each call */ | |
606 | args = scm_list_copy (lstlst); | |
607 | ||
608 | for (;;) | |
609 | { | |
610 | /* first elem of each list in lstlst into args, and step those | |
611 | lstlst entries onto their next element */ | |
612 | for (l = lstlst, a = args, argnum = 2; | |
613 | scm_is_pair (l); | |
614 | l = SCM_CDR (l), a = SCM_CDR (a), argnum++) | |
615 | { | |
616 | lst = SCM_CAR (l); /* list argument */ | |
617 | if (! scm_is_pair (lst)) | |
618 | goto check_lst_and_done; | |
619 | SCM_SETCAR (a, SCM_CAR (lst)); /* arg for proc */ | |
620 | SCM_SETCAR (l, SCM_CDR (lst)); /* keep rest of lst */ | |
621 | } | |
622 | ||
623 | elem = scm_apply (proc, args, SCM_EOL); | |
624 | if (scm_is_true (elem)) | |
625 | { | |
626 | newcell = scm_cons (elem, SCM_EOL); | |
627 | *loc = newcell; | |
628 | loc = SCM_CDRLOC (newcell); | |
629 | } | |
630 | } | |
631 | } | |
632 | ||
633 | check_lst_and_done: | |
634 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list"); | |
635 | return ret; | |
636 | } | |
637 | #undef FUNC_NAME | |
2b077051 KR |
638 | |
639 | ||
5df2ac97 KR |
640 | SCM_DEFINE (scm_srfi1_find, "find", 2, 0, 0, |
641 | (SCM pred, SCM lst), | |
642 | "Return the first element of @var{lst} which satisfies the\n" | |
643 | "predicate @var{pred}, or return @code{#f} if no such element is\n" | |
644 | "found.") | |
645 | #define FUNC_NAME s_scm_srfi1_find | |
646 | { | |
647 | scm_t_trampoline_1 pred_tramp = scm_trampoline_1 (pred); | |
648 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
649 | ||
650 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
651 | { | |
652 | SCM elem = SCM_CAR (lst); | |
653 | if (scm_is_true (pred_tramp (pred, elem))) | |
654 | return elem; | |
655 | } | |
656 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
657 | ||
658 | return SCM_BOOL_F; | |
659 | } | |
660 | #undef FUNC_NAME | |
661 | ||
662 | ||
663 | SCM_DEFINE (scm_srfi1_find_tail, "find-tail", 2, 0, 0, | |
664 | (SCM pred, SCM lst), | |
665 | "Return the first pair of @var{lst} whose @sc{car} satisfies the\n" | |
666 | "predicate @var{pred}, or return @code{#f} if no such element is\n" | |
667 | "found.") | |
668 | #define FUNC_NAME s_scm_srfi1_find_tail | |
669 | { | |
670 | scm_t_trampoline_1 pred_tramp = scm_trampoline_1 (pred); | |
671 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
672 | ||
673 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
674 | if (scm_is_true (pred_tramp (pred, SCM_CAR (lst)))) | |
675 | return lst; | |
676 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
677 | ||
678 | return SCM_BOOL_F; | |
679 | } | |
680 | #undef FUNC_NAME | |
681 | ||
682 | ||
de51f595 KR |
683 | SCM_DEFINE (scm_srfi1_length_plus, "length+", 1, 0, 0, |
684 | (SCM lst), | |
685 | "Return the length of @var{lst}, or @code{#f} if @var{lst} is\n" | |
686 | "circular.") | |
687 | #define FUNC_NAME s_scm_srfi1_length_plus | |
688 | { | |
689 | long len = scm_ilength (lst); | |
93ccaef0 | 690 | return (len >= 0 ? SCM_I_MAKINUM (len) : SCM_BOOL_F); |
de51f595 KR |
691 | } |
692 | #undef FUNC_NAME | |
693 | ||
694 | ||
d61261f0 KR |
695 | /* This routine differs from the core list-copy in allowing improper lists. |
696 | Maybe the core could allow them similarly. */ | |
697 | ||
698 | SCM_DEFINE (scm_srfi1_list_copy, "list-copy", 1, 0, 0, | |
699 | (SCM lst), | |
700 | "Return a copy of the given list @var{lst}.\n" | |
701 | "\n" | |
702 | "@var{lst} can be a proper or improper list. And if @var{lst}\n" | |
703 | "is not a pair then it's treated as the final tail of an\n" | |
704 | "improper list and simply returned.") | |
705 | #define FUNC_NAME s_scm_srfi1_list_copy | |
706 | { | |
707 | SCM newlst; | |
708 | SCM * fill_here; | |
709 | SCM from_here; | |
710 | ||
711 | newlst = lst; | |
712 | fill_here = &newlst; | |
713 | from_here = lst; | |
714 | ||
896df2d5 | 715 | while (scm_is_pair (from_here)) |
d61261f0 KR |
716 | { |
717 | SCM c; | |
718 | c = scm_cons (SCM_CAR (from_here), SCM_CDR (from_here)); | |
719 | *fill_here = c; | |
720 | fill_here = SCM_CDRLOC (c); | |
721 | from_here = SCM_CDR (from_here); | |
722 | } | |
723 | return newlst; | |
724 | } | |
725 | #undef FUNC_NAME | |
726 | ||
727 | ||
ee6aac97 MD |
728 | /* Typechecking for multi-argument MAP and FOR-EACH. |
729 | ||
730 | Verify that each element of the vector ARGV, except for the first, | |
731 | is a list and return minimum length. Attribute errors to WHO, | |
732 | and claim that the i'th element of ARGV is WHO's i+2'th argument. */ | |
733 | static inline int | |
734 | check_map_args (SCM argv, | |
735 | long len, | |
736 | SCM gf, | |
737 | SCM proc, | |
738 | SCM args, | |
739 | const char *who) | |
740 | { | |
ee6aac97 MD |
741 | long i; |
742 | ||
3c4ce91b | 743 | for (i = SCM_SIMPLE_VECTOR_LENGTH (argv) - 1; i >= 1; i--) |
ee6aac97 | 744 | { |
3a0cf656 | 745 | SCM elt = SCM_SIMPLE_VECTOR_REF (argv, i); |
ee6aac97 MD |
746 | long elt_len; |
747 | ||
896df2d5 | 748 | if (!(scm_is_null (elt) || scm_is_pair (elt))) |
ee6aac97 MD |
749 | { |
750 | check_map_error: | |
751 | if (gf) | |
752 | scm_apply_generic (gf, scm_cons (proc, args)); | |
753 | else | |
3c4ce91b | 754 | scm_wrong_type_arg (who, i + 2, elt); |
ee6aac97 MD |
755 | } |
756 | ||
3c4ce91b | 757 | elt_len = srfi1_ilength (elt); |
ee6aac97 MD |
758 | if (elt_len < -1) |
759 | goto check_map_error; | |
760 | ||
761 | if (len < 0 || (elt_len >= 0 && elt_len < len)) | |
762 | len = elt_len; | |
763 | } | |
764 | if (len < 0) | |
765 | /* i == 0 */ | |
766 | goto check_map_error; | |
767 | ||
768 | scm_remember_upto_here_1 (argv); | |
769 | return len; | |
770 | } | |
771 | ||
772 | ||
773 | SCM_GPROC (s_srfi1_map, "map", 2, 0, 1, scm_srfi1_map, g_srfi1_map); | |
774 | ||
775 | /* Note: Currently, scm_srfi1_map applies PROC to the argument list(s) | |
776 | sequentially, starting with the first element(s). This is used in | |
777 | the Scheme procedure `map-in-order', which guarantees sequential | |
778 | behaviour, is implemented using scm_map. If the behaviour changes, | |
779 | we need to update `map-in-order'. | |
780 | */ | |
781 | ||
782 | SCM | |
783 | scm_srfi1_map (SCM proc, SCM arg1, SCM args) | |
784 | #define FUNC_NAME s_srfi1_map | |
785 | { | |
786 | long i, len; | |
787 | SCM res = SCM_EOL; | |
788 | SCM *pres = &res; | |
ee6aac97 MD |
789 | |
790 | len = srfi1_ilength (arg1); | |
896df2d5 | 791 | SCM_GASSERTn ((scm_is_null (arg1) || scm_is_pair (arg1)) && len >= -1, |
ee6aac97 MD |
792 | g_srfi1_map, |
793 | scm_cons2 (proc, arg1, args), SCM_ARG2, s_srfi1_map); | |
794 | SCM_VALIDATE_REST_ARGUMENT (args); | |
896df2d5 | 795 | if (scm_is_null (args)) |
ee6aac97 MD |
796 | { |
797 | scm_t_trampoline_1 call = scm_trampoline_1 (proc); | |
798 | SCM_GASSERT2 (call, g_srfi1_map, proc, arg1, SCM_ARG1, s_srfi1_map); | |
799 | SCM_GASSERT2 (len >= 0, g_srfi1_map, proc, arg1, SCM_ARG2, s_srfi1_map); | |
800 | while (SCM_NIMP (arg1)) | |
801 | { | |
802 | *pres = scm_list_1 (call (proc, SCM_CAR (arg1))); | |
803 | pres = SCM_CDRLOC (*pres); | |
804 | arg1 = SCM_CDR (arg1); | |
805 | } | |
806 | return res; | |
807 | } | |
896df2d5 | 808 | if (scm_is_null (SCM_CDR (args))) |
ee6aac97 MD |
809 | { |
810 | SCM arg2 = SCM_CAR (args); | |
811 | int len2 = srfi1_ilength (arg2); | |
812 | scm_t_trampoline_2 call = scm_trampoline_2 (proc); | |
813 | SCM_GASSERTn (call, g_srfi1_map, | |
814 | scm_cons2 (proc, arg1, args), SCM_ARG1, s_srfi1_map); | |
815 | if (len < 0 || (len2 >= 0 && len2 < len)) | |
816 | len = len2; | |
896df2d5 | 817 | SCM_GASSERTn ((scm_is_null (arg2) || scm_is_pair (arg2)) |
ee6aac97 MD |
818 | && len >= 0 && len2 >= -1, |
819 | g_srfi1_map, | |
820 | scm_cons2 (proc, arg1, args), | |
f9ac1c2d | 821 | len2 >= 0 ? SCM_ARG2 : SCM_ARG3, |
ee6aac97 MD |
822 | s_srfi1_map); |
823 | while (len > 0) | |
824 | { | |
825 | *pres = scm_list_1 (call (proc, SCM_CAR (arg1), SCM_CAR (arg2))); | |
826 | pres = SCM_CDRLOC (*pres); | |
827 | arg1 = SCM_CDR (arg1); | |
828 | arg2 = SCM_CDR (arg2); | |
829 | --len; | |
830 | } | |
831 | return res; | |
832 | } | |
833 | args = scm_vector (arg1 = scm_cons (arg1, args)); | |
ee6aac97 MD |
834 | len = check_map_args (args, len, g_srfi1_map, proc, arg1, s_srfi1_map); |
835 | while (len > 0) | |
836 | { | |
837 | arg1 = SCM_EOL; | |
3c4ce91b | 838 | for (i = SCM_SIMPLE_VECTOR_LENGTH (args) - 1; i >= 0; i--) |
ee6aac97 | 839 | { |
3c4ce91b MV |
840 | SCM elt = SCM_SIMPLE_VECTOR_REF (args, i); |
841 | arg1 = scm_cons (SCM_CAR (elt), arg1); | |
842 | SCM_SIMPLE_VECTOR_SET (args, i, SCM_CDR (elt)); | |
ee6aac97 MD |
843 | } |
844 | *pres = scm_list_1 (scm_apply (proc, arg1, SCM_EOL)); | |
845 | pres = SCM_CDRLOC (*pres); | |
846 | --len; | |
847 | } | |
848 | return res; | |
849 | } | |
850 | #undef FUNC_NAME | |
851 | ||
852 | SCM_REGISTER_PROC (s_srfi1_map_in_order, "map-in-order", 2, 0, 1, scm_srfi1_map); | |
853 | ||
854 | SCM_GPROC (s_srfi1_for_each, "for-each", 2, 0, 1, scm_srfi1_for_each, g_srfi1_for_each); | |
855 | ||
856 | SCM | |
857 | scm_srfi1_for_each (SCM proc, SCM arg1, SCM args) | |
858 | #define FUNC_NAME s_srfi1_for_each | |
859 | { | |
ee6aac97 MD |
860 | long i, len; |
861 | len = srfi1_ilength (arg1); | |
896df2d5 | 862 | SCM_GASSERTn ((scm_is_null (arg1) || scm_is_pair (arg1)) && len >= -1, |
ee6aac97 MD |
863 | g_srfi1_for_each, scm_cons2 (proc, arg1, args), |
864 | SCM_ARG2, s_srfi1_for_each); | |
865 | SCM_VALIDATE_REST_ARGUMENT (args); | |
896df2d5 | 866 | if (scm_is_null (args)) |
ee6aac97 MD |
867 | { |
868 | scm_t_trampoline_1 call = scm_trampoline_1 (proc); | |
869 | SCM_GASSERT2 (call, g_srfi1_for_each, proc, arg1, | |
870 | SCM_ARG1, s_srfi1_for_each); | |
871 | SCM_GASSERT2 (len >= 0, g_srfi1_for_each, proc, arg1, | |
872 | SCM_ARG2, s_srfi1_map); | |
873 | while (SCM_NIMP (arg1)) | |
874 | { | |
875 | call (proc, SCM_CAR (arg1)); | |
876 | arg1 = SCM_CDR (arg1); | |
877 | } | |
878 | return SCM_UNSPECIFIED; | |
879 | } | |
896df2d5 | 880 | if (scm_is_null (SCM_CDR (args))) |
ee6aac97 MD |
881 | { |
882 | SCM arg2 = SCM_CAR (args); | |
883 | int len2 = srfi1_ilength (arg2); | |
884 | scm_t_trampoline_2 call = scm_trampoline_2 (proc); | |
885 | SCM_GASSERTn (call, g_srfi1_for_each, | |
886 | scm_cons2 (proc, arg1, args), SCM_ARG1, s_srfi1_for_each); | |
887 | if (len < 0 || (len2 >= 0 && len2 < len)) | |
888 | len = len2; | |
896df2d5 | 889 | SCM_GASSERTn ((scm_is_null (arg2) || scm_is_pair (arg2)) |
f9ac1c2d | 890 | && len >= 0 && len2 >= -1, |
ee6aac97 MD |
891 | g_srfi1_for_each, |
892 | scm_cons2 (proc, arg1, args), | |
f9ac1c2d | 893 | len2 >= 0 ? SCM_ARG2 : SCM_ARG3, |
ee6aac97 MD |
894 | s_srfi1_for_each); |
895 | while (len > 0) | |
896 | { | |
897 | call (proc, SCM_CAR (arg1), SCM_CAR (arg2)); | |
898 | arg1 = SCM_CDR (arg1); | |
899 | arg2 = SCM_CDR (arg2); | |
900 | --len; | |
901 | } | |
902 | return SCM_UNSPECIFIED; | |
903 | } | |
904 | args = scm_vector (arg1 = scm_cons (arg1, args)); | |
ee6aac97 MD |
905 | len = check_map_args (args, len, g_srfi1_for_each, proc, arg1, |
906 | s_srfi1_for_each); | |
907 | while (len > 0) | |
908 | { | |
909 | arg1 = SCM_EOL; | |
3c4ce91b | 910 | for (i = SCM_SIMPLE_VECTOR_LENGTH (args) - 1; i >= 0; i--) |
ee6aac97 | 911 | { |
3c4ce91b MV |
912 | SCM elt = SCM_SIMPLE_VECTOR_REF (args, i); |
913 | arg1 = scm_cons (SCM_CAR (elt), arg1); | |
914 | SCM_SIMPLE_VECTOR_SET (args, i, SCM_CDR (elt)); | |
ee6aac97 MD |
915 | } |
916 | scm_apply (proc, arg1, SCM_EOL); | |
917 | --len; | |
918 | } | |
919 | return SCM_UNSPECIFIED; | |
920 | } | |
921 | #undef FUNC_NAME | |
922 | ||
923 | ||
ee6aac97 MD |
924 | SCM_DEFINE (scm_srfi1_member, "member", 2, 1, 0, |
925 | (SCM x, SCM lst, SCM pred), | |
4e3cc389 KR |
926 | "Return the first sublist of @var{lst} whose @sc{car} is equal\n" |
927 | "to @var{x}. If @var{x} does not appear in @var{lst}, return\n" | |
928 | "@code{#f}.\n" | |
929 | "\n" | |
930 | "Equality is determined by @code{equal?}, or by the equality\n" | |
931 | "predicate @var{=} if given. @var{=} is called @code{(= @var{x}\n" | |
932 | "elem)}, ie.@: with the given @var{x} first, so for example to\n" | |
933 | "find the first element greater than 5,\n" | |
934 | "\n" | |
935 | "@example\n" | |
936 | "(member 5 '(3 5 1 7 2 9) <) @result{} (7 2 9)\n" | |
937 | "@end example\n" | |
938 | "\n" | |
939 | "This version of @code{member} extends the core @code{member} by\n" | |
940 | "accepting an equality predicate.") | |
ee6aac97 MD |
941 | #define FUNC_NAME s_scm_srfi1_member |
942 | { | |
943 | scm_t_trampoline_2 equal_p; | |
944 | SCM_VALIDATE_LIST (2, lst); | |
945 | if (SCM_UNBNDP (pred)) | |
946 | equal_p = equal_trampoline; | |
947 | else | |
948 | { | |
949 | equal_p = scm_trampoline_2 (pred); | |
950 | SCM_ASSERT (equal_p, pred, 3, FUNC_NAME); | |
951 | } | |
952 | for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst)) | |
953 | { | |
2796304a | 954 | if (scm_is_true (equal_p (pred, x, SCM_CAR (lst)))) |
ee6aac97 MD |
955 | return lst; |
956 | } | |
957 | return SCM_BOOL_F; | |
958 | } | |
959 | #undef FUNC_NAME | |
960 | ||
7692d26b MD |
961 | SCM_DEFINE (scm_srfi1_assoc, "assoc", 2, 1, 0, |
962 | (SCM key, SCM alist, SCM pred), | |
963 | "Behaves like @code{assq} but uses third argument @var{pred?}\n" | |
964 | "for key comparison. If @var{pred?} is not supplied,\n" | |
965 | "@code{equal?} is used. (Extended from R5RS.)\n") | |
966 | #define FUNC_NAME s_scm_srfi1_assoc | |
967 | { | |
968 | SCM ls = alist; | |
969 | scm_t_trampoline_2 equal_p; | |
970 | if (SCM_UNBNDP (pred)) | |
971 | equal_p = equal_trampoline; | |
972 | else | |
973 | { | |
974 | equal_p = scm_trampoline_2 (pred); | |
975 | SCM_ASSERT (equal_p, pred, 3, FUNC_NAME); | |
976 | } | |
896df2d5 | 977 | for(; scm_is_pair (ls); ls = SCM_CDR (ls)) |
7692d26b MD |
978 | { |
979 | SCM tmp = SCM_CAR (ls); | |
896df2d5 | 980 | SCM_ASSERT_TYPE (scm_is_pair (tmp), alist, SCM_ARG2, FUNC_NAME, |
7692d26b | 981 | "association list"); |
00874d5f | 982 | if (scm_is_true (equal_p (pred, SCM_CAR (tmp), key))) |
7692d26b MD |
983 | return tmp; |
984 | } | |
985 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (ls), alist, SCM_ARG2, FUNC_NAME, | |
986 | "association list"); | |
987 | return SCM_BOOL_F; | |
988 | } | |
989 | #undef FUNC_NAME | |
990 | ||
65978fb2 KR |
991 | SCM_DEFINE (scm_srfi1_partition, "partition", 2, 0, 0, |
992 | (SCM pred, SCM list), | |
993 | "Partition the elements of @var{list} with predicate @var{pred}.\n" | |
994 | "Return two values: the list of elements satifying @var{pred} and\n" | |
995 | "the list of elements @emph{not} satisfying @var{pred}. The order\n" | |
996 | "of the output lists follows the order of @var{list}. @var{list}\n" | |
997 | "is not mutated. One of the output lists may share memory with @var{list}.\n") | |
998 | #define FUNC_NAME s_scm_srfi1_partition | |
999 | { | |
1000 | /* In this implementation, the output lists don't share memory with | |
1001 | list, because it's probably not worth the effort. */ | |
1002 | scm_t_trampoline_1 call = scm_trampoline_1(pred); | |
1003 | SCM kept = scm_cons(SCM_EOL, SCM_EOL); | |
1004 | SCM kept_tail = kept; | |
1005 | SCM dropped = scm_cons(SCM_EOL, SCM_EOL); | |
1006 | SCM dropped_tail = dropped; | |
1007 | ||
1008 | SCM_ASSERT(call, pred, 2, FUNC_NAME); | |
1009 | ||
1010 | for (; !SCM_NULL_OR_NIL_P (list); list = SCM_CDR(list)) { | |
1011 | SCM elt = SCM_CAR(list); | |
1012 | SCM new_tail = scm_cons(SCM_CAR(list), SCM_EOL); | |
00874d5f | 1013 | if (scm_is_true (call (pred, elt))) { |
65978fb2 KR |
1014 | SCM_SETCDR(kept_tail, new_tail); |
1015 | kept_tail = new_tail; | |
1016 | } | |
1017 | else { | |
1018 | SCM_SETCDR(dropped_tail, new_tail); | |
1019 | dropped_tail = new_tail; | |
1020 | } | |
1021 | } | |
1022 | /* re-use the initial conses for the values list */ | |
1023 | SCM_SETCAR(kept, SCM_CDR(kept)); | |
1024 | SCM_SETCDR(kept, dropped); | |
1025 | SCM_SETCAR(dropped, SCM_CDR(dropped)); | |
1026 | SCM_SETCDR(dropped, SCM_EOL); | |
1027 | return scm_values(kept); | |
1028 | } | |
1029 | #undef FUNC_NAME | |
1030 | ||
2b077051 KR |
1031 | |
1032 | SCM_DEFINE (scm_srfi1_partition_x, "partition!", 2, 0, 0, | |
1033 | (SCM pred, SCM lst), | |
1034 | "Split @var{lst} into those elements which do and don't satisfy\n" | |
1035 | "the predicate @var{pred}.\n" | |
1036 | "\n" | |
1037 | "The return is two values (@pxref{Multiple Values}), the first\n" | |
1038 | "being a list of all elements from @var{lst} which satisfy\n" | |
1039 | "@var{pred}, the second a list of those which do not.\n" | |
1040 | "\n" | |
1041 | "The elements in the result lists are in the same order as in\n" | |
1042 | "@var{lst} but the order in which the calls @code{(@var{pred}\n" | |
1043 | "elem)} are made on the list elements is unspecified.\n" | |
1044 | "\n" | |
1045 | "@var{lst} may be modified to construct the return lists.") | |
1046 | #define FUNC_NAME s_scm_srfi1_partition_x | |
1047 | { | |
1048 | SCM tlst, flst, *tp, *fp; | |
1049 | scm_t_trampoline_1 pred_tramp; | |
1050 | ||
1051 | pred_tramp = scm_trampoline_1 (pred); | |
1052 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
1053 | ||
1054 | /* tlst and flst are the lists of true and false elements. tp and fp are | |
1055 | where to store to append to them, initially &tlst and &flst, then | |
1056 | SCM_CDRLOC of the last pair in the respective lists. */ | |
1057 | ||
1058 | tlst = SCM_EOL; | |
1059 | flst = SCM_EOL; | |
1060 | tp = &tlst; | |
1061 | fp = &flst; | |
1062 | ||
1063 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) | |
1064 | { | |
1065 | if (scm_is_true (pred_tramp (pred, SCM_CAR (lst)))) | |
1066 | { | |
1067 | *tp = lst; | |
1068 | tp = SCM_CDRLOC (lst); | |
1069 | } | |
1070 | else | |
1071 | { | |
1072 | *fp = lst; | |
1073 | fp = SCM_CDRLOC (lst); | |
1074 | } | |
1075 | } | |
1076 | ||
1077 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
1078 | ||
1079 | /* terminate whichever didn't get the last element(s) */ | |
1080 | *tp = SCM_EOL; | |
1081 | *fp = SCM_EOL; | |
1082 | ||
1083 | return scm_values (scm_list_2 (tlst, flst)); | |
1084 | } | |
1085 | #undef FUNC_NAME | |
1086 | ||
1087 | ||
59747b8d KR |
1088 | SCM_DEFINE (scm_srfi1_remove, "remove", 2, 0, 0, |
1089 | (SCM pred, SCM list), | |
1090 | "Return a list containing all elements from @var{lst} which do\n" | |
1091 | "not satisfy the predicate @var{pred}. The elements in the\n" | |
1092 | "result list have the same order as in @var{lst}. The order in\n" | |
1093 | "which @var{pred} is applied to the list elements is not\n" | |
1094 | "specified.") | |
1095 | #define FUNC_NAME s_scm_srfi1_remove | |
1096 | { | |
1097 | scm_t_trampoline_1 call = scm_trampoline_1 (pred); | |
1098 | SCM walk; | |
1099 | SCM *prev; | |
1100 | SCM res = SCM_EOL; | |
1101 | SCM_ASSERT (call, pred, 1, FUNC_NAME); | |
1102 | SCM_VALIDATE_LIST (2, list); | |
1103 | ||
1104 | for (prev = &res, walk = list; | |
1105 | scm_is_pair (walk); | |
1106 | walk = SCM_CDR (walk)) | |
1107 | { | |
1108 | if (scm_is_false (call (pred, SCM_CAR (walk)))) | |
1109 | { | |
1110 | *prev = scm_cons (SCM_CAR (walk), SCM_EOL); | |
1111 | prev = SCM_CDRLOC (*prev); | |
1112 | } | |
1113 | } | |
1114 | ||
1115 | return res; | |
1116 | } | |
1117 | #undef FUNC_NAME | |
1118 | ||
2b077051 KR |
1119 | |
1120 | SCM_DEFINE (scm_srfi1_remove_x, "remove!", 2, 0, 0, | |
1121 | (SCM pred, SCM list), | |
1122 | "Return a list containing all elements from @var{list} which do\n" | |
1123 | "not satisfy the predicate @var{pred}. The elements in the\n" | |
1124 | "result list have the same order as in @var{list}. The order in\n" | |
1125 | "which @var{pred} is applied to the list elements is not\n" | |
1126 | "specified. @var{list} may be modified to build the return\n" | |
1127 | "list.") | |
1128 | #define FUNC_NAME s_scm_srfi1_remove_x | |
1129 | { | |
1130 | scm_t_trampoline_1 call = scm_trampoline_1 (pred); | |
1131 | SCM walk; | |
1132 | SCM *prev; | |
1133 | SCM_ASSERT (call, pred, 1, FUNC_NAME); | |
1134 | SCM_VALIDATE_LIST (2, list); | |
1135 | ||
1136 | for (prev = &list, walk = list; | |
1137 | scm_is_pair (walk); | |
1138 | walk = SCM_CDR (walk)) | |
1139 | { | |
1140 | if (scm_is_false (call (pred, SCM_CAR (walk)))) | |
1141 | prev = SCM_CDRLOC (walk); | |
1142 | else | |
1143 | *prev = SCM_CDR (walk); | |
1144 | } | |
1145 | ||
1146 | return list; | |
1147 | } | |
1148 | #undef FUNC_NAME | |
1149 | ||
1150 | ||
d2f57ee0 KR |
1151 | SCM_DEFINE (scm_srfi1_split_at, "split-at", 2, 0, 0, |
1152 | (SCM lst, SCM n), | |
1153 | "Return two values (multiple values), being a list of the\n" | |
1154 | "elements before index @var{n} in @var{lst}, and a list of those\n" | |
1155 | "after.") | |
1156 | #define FUNC_NAME s_scm_srfi1_split_at | |
1157 | { | |
1158 | size_t nn; | |
1159 | /* pre is a list of elements before the i split point, loc is the CDRLOC | |
1160 | of the last cell, ie. where to store to append to it */ | |
1161 | SCM pre = SCM_EOL; | |
1162 | SCM *loc = ⪯ | |
1163 | ||
1164 | for (nn = scm_to_size_t (n); nn != 0; nn--) | |
1165 | { | |
1166 | SCM_VALIDATE_CONS (SCM_ARG1, lst); | |
1167 | ||
1168 | *loc = scm_cons (SCM_CAR (lst), SCM_EOL); | |
1169 | loc = SCM_CDRLOC (*loc); | |
1170 | lst = SCM_CDR(lst); | |
1171 | } | |
1172 | return scm_values (scm_list_2 (pre, lst)); | |
1173 | } | |
1174 | #undef FUNC_NAME | |
1175 | ||
1176 | ||
1177 | SCM_DEFINE (scm_srfi1_split_at_x, "split-at!", 2, 0, 0, | |
1178 | (SCM lst, SCM n), | |
1179 | "Return two values (multiple values), being a list of the\n" | |
1180 | "elements before index @var{n} in @var{lst}, and a list of those\n" | |
1181 | "after. @var{lst} is modified to form those values.") | |
1182 | #define FUNC_NAME s_scm_srfi1_split_at | |
1183 | { | |
1184 | size_t nn; | |
1185 | SCM upto = lst; | |
1186 | SCM *loc = &lst; | |
1187 | ||
1188 | for (nn = scm_to_size_t (n); nn != 0; nn--) | |
1189 | { | |
1190 | SCM_VALIDATE_CONS (SCM_ARG1, upto); | |
1191 | ||
1192 | loc = SCM_CDRLOC (upto); | |
1193 | upto = SCM_CDR (upto); | |
1194 | } | |
1195 | ||
1196 | *loc = SCM_EOL; | |
1197 | return scm_values (scm_list_2 (lst, upto)); | |
1198 | } | |
1199 | #undef FUNC_NAME | |
1200 | ||
1201 | ||
2b077051 KR |
1202 | SCM_DEFINE (scm_srfi1_take_right, "take-right", 2, 0, 0, |
1203 | (SCM lst, SCM n), | |
1204 | "Return the a list containing the @var{n} last elements of\n" | |
1205 | "@var{lst}.") | |
1206 | #define FUNC_NAME s_scm_srfi1_take_right | |
1207 | { | |
1208 | SCM tail = scm_list_tail (lst, n); | |
1209 | while (scm_is_pair (tail)) | |
1210 | { | |
1211 | lst = SCM_CDR (lst); | |
1212 | tail = SCM_CDR (tail); | |
1213 | } | |
1214 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P(tail), tail, SCM_ARG1, FUNC_NAME, "list"); | |
1215 | return lst; | |
1216 | } | |
1217 | #undef FUNC_NAME | |
1218 | ||
1219 | ||
ee6aac97 MD |
1220 | void |
1221 | scm_init_srfi_1 (void) | |
1222 | { | |
a48d60b1 | 1223 | SCM the_root_module = scm_lookup_closure_module (SCM_BOOL_F); |
ee6aac97 MD |
1224 | #ifndef SCM_MAGIC_SNARFER |
1225 | #include "srfi/srfi-1.x" | |
1226 | #endif | |
a48d60b1 MD |
1227 | scm_c_extend_primitive_generic |
1228 | (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module, "map")), | |
1229 | SCM_VARIABLE_REF (scm_c_lookup ("map"))); | |
1230 | scm_c_extend_primitive_generic | |
1231 | (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module, "for-each")), | |
1232 | SCM_VARIABLE_REF (scm_c_lookup ("for-each"))); | |
ee6aac97 MD |
1233 | } |
1234 | ||
1235 | /* End of srfi-1.c. */ |