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; | |
1685446c | 42 | if (!SCM_CONSP (hare)) return -2; |
ee6aac97 MD |
43 | hare = SCM_CDR(hare); |
44 | i++; | |
45 | if (SCM_NULL_OR_NIL_P(hare)) return i; | |
1685446c | 46 | if (!SCM_CONSP (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 | } | |
52 | while (! SCM_EQ_P (hare, tortoise)); | |
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 | ||
47f2726f KR |
66 | /* scm_append and scm_append_x don't modify their list argument (only the |
67 | lists within that list in the case of scm_append_x), hence making them | |
68 | suitable for direct use for concatentate. */ | |
69 | ||
70 | SCM_REGISTER_PROC (s_srfi1_concatenate, "concatenate", 1, 0, 0, scm_append); | |
71 | SCM_REGISTER_PROC (s_srfi1_concatenate_x, "concatenate!", 1, 0, 0, scm_append_x); | |
72 | ||
73 | ||
d0a634de KR |
74 | SCM_DEFINE (scm_srfi1_delete, "delete", 2, 1, 0, |
75 | (SCM x, SCM lst, SCM pred), | |
76 | "Return a list containing the elements of @var{lst} but with\n" | |
77 | "those equal to @var{x} deleted. The returned elements will be\n" | |
78 | "in the same order as they were in @var{lst}.\n" | |
79 | "\n" | |
80 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
81 | "given. An equality call is made just once for each element,\n" | |
82 | "but the order in which the calls are made on the elements is\n" | |
83 | "unspecified.\n" | |
84 | "\n" | |
85 | "The equality calls are always @code{(pred x elem)}, ie.@: the\n" | |
86 | "given @var{x} is first. This means for instance elements\n" | |
87 | "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n" | |
88 | "\n" | |
89 | "@var{lst} is not modified, but the returned list might share a\n" | |
90 | "common tail with @var{lst}.") | |
91 | #define FUNC_NAME s_scm_srfi1_delete | |
92 | { | |
93 | scm_t_trampoline_2 equal_p; | |
94 | SCM ret, *p, keeplst; | |
95 | ||
96 | if (SCM_UNBNDP (pred)) | |
97 | return scm_delete (x, lst); | |
98 | ||
99 | equal_p = scm_trampoline_2 (pred); | |
100 | SCM_ASSERT (equal_p, pred, SCM_ARG3, FUNC_NAME); | |
101 | ||
102 | /* ret is the return list being constructed. p is where to append to it, | |
103 | initially &ret then SCM_CDRLOC of the last pair. lst progresses as | |
104 | elements are considered. | |
105 | ||
106 | Elements to be retained are not immediately copied, instead keeplst is | |
107 | the last pair in lst which is to be retained but not yet copied. When | |
108 | there's no more deletions, *p can be set to keeplst to share the | |
109 | remainder of the original lst. (The entire original lst if there's no | |
110 | deletions at all.) */ | |
111 | ||
112 | keeplst = lst; | |
113 | ret = SCM_EOL; | |
114 | p = &ret; | |
115 | ||
116 | for ( ; SCM_CONSP (lst); lst = SCM_CDR (lst)) | |
117 | { | |
118 | if (! SCM_FALSEP (equal_p (pred, x, SCM_CAR (lst)))) | |
119 | { | |
120 | /* delete this element, so copy from keeplst (inclusive) to lst | |
121 | (exclusive) onto ret */ | |
122 | while (! SCM_EQ_P (keeplst, lst)) | |
123 | { | |
124 | SCM c = scm_cons (SCM_CAR (keeplst), SCM_EOL); | |
125 | *p = c; | |
126 | p = SCM_CDRLOC (c); | |
127 | keeplst = SCM_CDR (keeplst); | |
128 | } | |
129 | ||
130 | keeplst = SCM_CDR (lst); | |
131 | } | |
132 | } | |
133 | ||
134 | /* final retained elements */ | |
135 | *p = keeplst; | |
136 | ||
137 | /* demand that lst was a proper list */ | |
138 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
139 | ||
140 | return ret; | |
141 | } | |
142 | #undef FUNC_NAME | |
143 | ||
144 | ||
145 | SCM_DEFINE (scm_srfi1_delete_x, "delete!", 2, 1, 0, | |
146 | (SCM x, SCM lst, SCM pred), | |
147 | "Return a list containing the elements of @var{lst} but with\n" | |
148 | "those equal to @var{x} deleted. The returned elements will be\n" | |
149 | "in the same order as they were in @var{lst}.\n" | |
150 | "\n" | |
151 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
152 | "given. An equality call is made just once for each element,\n" | |
153 | "but the order in which the calls are made on the elements is\n" | |
154 | "unspecified.\n" | |
155 | "\n" | |
156 | "The equality calls are always @code{(pred x elem)}, ie.@: the\n" | |
157 | "given @var{x} is first. This means for instance elements\n" | |
158 | "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n" | |
159 | "\n" | |
160 | "@var{lst} may be modified to construct the returned list.") | |
161 | #define FUNC_NAME s_scm_srfi1_delete_x | |
162 | { | |
163 | scm_t_trampoline_2 equal_p; | |
164 | SCM walk; | |
165 | SCM *prev; | |
166 | ||
167 | if (SCM_UNBNDP (pred)) | |
168 | return scm_delete_x (x, lst); | |
169 | ||
170 | equal_p = scm_trampoline_2 (pred); | |
171 | SCM_ASSERT (equal_p, pred, SCM_ARG3, FUNC_NAME); | |
172 | ||
173 | for (prev = &lst, walk = lst; | |
174 | SCM_CONSP (walk); | |
175 | walk = SCM_CDR (walk)) | |
176 | { | |
177 | if (! SCM_FALSEP (equal_p (pred, x, SCM_CAR (walk)))) | |
178 | *prev = SCM_CDR (walk); | |
179 | else | |
180 | prev = SCM_CDRLOC (walk); | |
181 | } | |
182 | ||
183 | /* demand the input was a proper list */ | |
184 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (walk), walk, SCM_ARG2, FUNC_NAME,"list"); | |
185 | return lst; | |
186 | } | |
187 | #undef FUNC_NAME | |
188 | ||
189 | ||
190 | SCM_DEFINE (scm_srfi1_delete_duplicates, "delete-duplicates", 1, 1, 0, | |
191 | (SCM lst, SCM pred), | |
192 | "Return a list containing the elements of @var{lst} but without\n" | |
193 | "duplicates.\n" | |
194 | "\n" | |
195 | "When elements are equal, only the first in @var{lst} is\n" | |
196 | "retained. Equal elements can be anywhere in @var{lst}, they\n" | |
197 | "don't have to be adjacent. The returned list will have the\n" | |
198 | "retained elements in the same order as they were in @var{lst}.\n" | |
199 | "\n" | |
200 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
201 | "given. Calls @code{(pred x y)} are made with element @var{x}\n" | |
202 | "being before @var{y} in @var{lst}. A call is made at most once\n" | |
203 | "for each combination, but the sequence of the calls across the\n" | |
204 | "elements is unspecified.\n" | |
205 | "\n" | |
206 | "@var{lst} is not modified, but the return might share a common\n" | |
207 | "tail with @var{lst}.\n" | |
208 | "\n" | |
209 | "In the worst case, this is an @math{O(N^2)} algorithm because\n" | |
210 | "it must check each element against all those preceding it. For\n" | |
211 | "long lists it is more efficient to sort and then compare only\n" | |
212 | "adjacent elements.") | |
213 | #define FUNC_NAME s_scm_srfi1_delete_duplicates | |
214 | { | |
215 | scm_t_trampoline_2 equal_p; | |
216 | SCM ret, *p, keeplst, item, l; | |
217 | ||
218 | /* ret is the new list constructed. p is where to append, initially &ret | |
219 | then SCM_CDRLOC of the last pair. lst is advanced as each element is | |
220 | considered. | |
221 | ||
222 | Elements retained are not immediately appended to ret, instead keeplst | |
223 | is the last pair in lst which is to be kept but is not yet copied. | |
224 | Initially this is the first pair of lst, since the first element is | |
225 | always retained. | |
226 | ||
227 | *p is kept set to keeplst, so ret (inclusive) to lst (exclusive) is all | |
228 | the elements retained, making the equality search loop easy. | |
229 | ||
230 | If an item must be deleted, elements from keeplst (inclusive) to lst | |
231 | (exclusive) must be copied and appended to ret. When there's no more | |
232 | deletions, *p is left set to keeplst, so ret shares structure with the | |
233 | original lst. (ret will be the entire original lst if there are no | |
234 | deletions.) */ | |
235 | ||
236 | /* skip to end if an empty list (or something invalid) */ | |
237 | ret = lst; | |
238 | if (SCM_CONSP (lst)) | |
239 | { | |
240 | if (SCM_UNBNDP (pred)) | |
241 | equal_p = equal_trampoline; | |
242 | else | |
243 | { | |
244 | equal_p = scm_trampoline_2 (pred); | |
245 | SCM_ASSERT (equal_p, pred, SCM_ARG2, FUNC_NAME); | |
246 | } | |
247 | ||
248 | keeplst = lst; | |
249 | p = &ret; | |
250 | ||
251 | /* loop over lst elements starting from second */ | |
252 | for (;;) | |
253 | { | |
254 | lst = SCM_CDR (lst); | |
255 | if (! SCM_CONSP (lst)) | |
256 | break; | |
257 | item = SCM_CAR (lst); | |
258 | ||
259 | /* loop searching ret upto lst */ | |
260 | for (l = ret; ! SCM_EQ_P (l, lst); l = SCM_CDR (l)) | |
261 | { | |
262 | if (! SCM_FALSEP (equal_p (pred, SCM_CAR (l), item))) | |
263 | { | |
264 | /* duplicate, don't want this element, so copy keeplst | |
265 | (inclusive) to lst (exclusive) onto ret */ | |
266 | while (! SCM_EQ_P (keeplst, lst)) | |
267 | { | |
268 | SCM c = scm_cons (SCM_CAR (keeplst), SCM_EOL); | |
269 | *p = c; | |
270 | p = SCM_CDRLOC (c); | |
271 | keeplst = SCM_CDR (keeplst); | |
272 | } | |
273 | ||
274 | keeplst = SCM_CDR (lst); /* elem after the one deleted */ | |
275 | *p = keeplst; | |
276 | break; | |
277 | } | |
278 | } | |
279 | } | |
280 | } | |
281 | ||
282 | /* demand that lst was a proper list */ | |
283 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list"); | |
284 | ||
285 | return ret; | |
286 | } | |
287 | #undef FUNC_NAME | |
288 | ||
289 | ||
290 | SCM_DEFINE (scm_srfi1_delete_duplicates_x, "delete-duplicates!", 1, 1, 0, | |
291 | (SCM lst, SCM pred), | |
292 | "Return a list containing the elements of @var{lst} but without\n" | |
293 | "duplicates.\n" | |
294 | "\n" | |
295 | "When elements are equal, only the first in @var{lst} is\n" | |
296 | "retained. Equal elements can be anywhere in @var{lst}, they\n" | |
297 | "don't have to be adjacent. The returned list will have the\n" | |
298 | "retained elements in the same order as they were in @var{lst}.\n" | |
299 | "\n" | |
300 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
301 | "given. Calls @code{(pred x y)} are made with element @var{x}\n" | |
302 | "being before @var{y} in @var{lst}. A call is made at most once\n" | |
303 | "for each combination, but the sequence of the calls across the\n" | |
304 | "elements is unspecified.\n" | |
305 | "\n" | |
306 | "@var{lst} may be modified to construct the returned list.\n" | |
307 | "\n" | |
308 | "In the worst case, this is an @math{O(N^2)} algorithm because\n" | |
309 | "it must check each element against all those preceding it. For\n" | |
310 | "long lists it is more efficient to sort and then compare only\n" | |
311 | "adjacent elements.") | |
312 | #define FUNC_NAME s_scm_srfi1_delete_duplicates_x | |
313 | { | |
314 | scm_t_trampoline_2 equal_p; | |
315 | SCM ret, endret, item, l; | |
316 | ||
317 | /* ret is the return list, constructed from the pairs in lst. endret is | |
318 | the last pair of ret, initially the first pair. lst is advanced as | |
319 | elements are considered. */ | |
320 | ||
321 | /* skip to end if an empty list (or something invalid) */ | |
322 | ret = lst; | |
323 | if (SCM_CONSP (lst)) | |
324 | { | |
325 | if (SCM_UNBNDP (pred)) | |
326 | equal_p = equal_trampoline; | |
327 | else | |
328 | { | |
329 | equal_p = scm_trampoline_2 (pred); | |
330 | SCM_ASSERT (equal_p, pred, SCM_ARG2, FUNC_NAME); | |
331 | } | |
332 | ||
333 | endret = ret; | |
334 | ||
335 | /* loop over lst elements starting from second */ | |
336 | for (;;) | |
337 | { | |
338 | lst = SCM_CDR (lst); | |
339 | if (! SCM_CONSP (lst)) | |
340 | break; | |
341 | item = SCM_CAR (lst); | |
342 | ||
343 | /* is item equal to any element from ret to endret (inclusive)? */ | |
344 | l = ret; | |
345 | for (;;) | |
346 | { | |
347 | if (! SCM_FALSEP (equal_p (pred, SCM_CAR (l), item))) | |
348 | break; /* equal, forget this element */ | |
349 | ||
350 | if (SCM_EQ_P (l, endret)) | |
351 | { | |
352 | /* not equal to any, so append this pair */ | |
353 | SCM_SETCDR (endret, lst); | |
354 | endret = lst; | |
355 | break; | |
356 | } | |
357 | l = SCM_CDR (l); | |
358 | } | |
359 | } | |
360 | ||
361 | /* terminate, in case last element was deleted */ | |
362 | SCM_SETCDR (endret, SCM_EOL); | |
363 | } | |
364 | ||
365 | /* demand that lst was a proper list */ | |
366 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list"); | |
367 | ||
368 | return ret; | |
369 | } | |
370 | #undef FUNC_NAME | |
371 | ||
372 | ||
de51f595 KR |
373 | SCM_DEFINE (scm_srfi1_length_plus, "length+", 1, 0, 0, |
374 | (SCM lst), | |
375 | "Return the length of @var{lst}, or @code{#f} if @var{lst} is\n" | |
376 | "circular.") | |
377 | #define FUNC_NAME s_scm_srfi1_length_plus | |
378 | { | |
379 | long len = scm_ilength (lst); | |
380 | return (len >= 0 ? SCM_MAKINUM (len) : SCM_BOOL_F); | |
381 | } | |
382 | #undef FUNC_NAME | |
383 | ||
384 | ||
ee6aac97 MD |
385 | /* Typechecking for multi-argument MAP and FOR-EACH. |
386 | ||
387 | Verify that each element of the vector ARGV, except for the first, | |
388 | is a list and return minimum length. Attribute errors to WHO, | |
389 | and claim that the i'th element of ARGV is WHO's i+2'th argument. */ | |
390 | static inline int | |
391 | check_map_args (SCM argv, | |
392 | long len, | |
393 | SCM gf, | |
394 | SCM proc, | |
395 | SCM args, | |
396 | const char *who) | |
397 | { | |
398 | SCM const *ve = SCM_VELTS (argv); | |
399 | long i; | |
400 | ||
401 | for (i = SCM_VECTOR_LENGTH (argv) - 1; i >= 1; i--) | |
402 | { | |
403 | long elt_len; | |
404 | ||
405 | if (!(SCM_NULLP (ve[i]) || SCM_CONSP (ve[i]))) | |
406 | { | |
407 | check_map_error: | |
408 | if (gf) | |
409 | scm_apply_generic (gf, scm_cons (proc, args)); | |
410 | else | |
411 | scm_wrong_type_arg (who, i + 2, ve[i]); | |
412 | } | |
413 | ||
414 | elt_len = srfi1_ilength (ve[i]); | |
415 | if (elt_len < -1) | |
416 | goto check_map_error; | |
417 | ||
418 | if (len < 0 || (elt_len >= 0 && elt_len < len)) | |
419 | len = elt_len; | |
420 | } | |
421 | if (len < 0) | |
422 | /* i == 0 */ | |
423 | goto check_map_error; | |
424 | ||
425 | scm_remember_upto_here_1 (argv); | |
426 | return len; | |
427 | } | |
428 | ||
429 | ||
430 | SCM_GPROC (s_srfi1_map, "map", 2, 0, 1, scm_srfi1_map, g_srfi1_map); | |
431 | ||
432 | /* Note: Currently, scm_srfi1_map applies PROC to the argument list(s) | |
433 | sequentially, starting with the first element(s). This is used in | |
434 | the Scheme procedure `map-in-order', which guarantees sequential | |
435 | behaviour, is implemented using scm_map. If the behaviour changes, | |
436 | we need to update `map-in-order'. | |
437 | */ | |
438 | ||
439 | SCM | |
440 | scm_srfi1_map (SCM proc, SCM arg1, SCM args) | |
441 | #define FUNC_NAME s_srfi1_map | |
442 | { | |
443 | long i, len; | |
444 | SCM res = SCM_EOL; | |
445 | SCM *pres = &res; | |
446 | SCM const *ve = &args; /* Keep args from being optimized away. */ | |
447 | ||
448 | len = srfi1_ilength (arg1); | |
449 | SCM_GASSERTn ((SCM_NULLP (arg1) || SCM_CONSP (arg1)) && len >= -1, | |
450 | g_srfi1_map, | |
451 | scm_cons2 (proc, arg1, args), SCM_ARG2, s_srfi1_map); | |
452 | SCM_VALIDATE_REST_ARGUMENT (args); | |
453 | if (SCM_NULLP (args)) | |
454 | { | |
455 | scm_t_trampoline_1 call = scm_trampoline_1 (proc); | |
456 | SCM_GASSERT2 (call, g_srfi1_map, proc, arg1, SCM_ARG1, s_srfi1_map); | |
457 | SCM_GASSERT2 (len >= 0, g_srfi1_map, proc, arg1, SCM_ARG2, s_srfi1_map); | |
458 | while (SCM_NIMP (arg1)) | |
459 | { | |
460 | *pres = scm_list_1 (call (proc, SCM_CAR (arg1))); | |
461 | pres = SCM_CDRLOC (*pres); | |
462 | arg1 = SCM_CDR (arg1); | |
463 | } | |
464 | return res; | |
465 | } | |
466 | if (SCM_NULLP (SCM_CDR (args))) | |
467 | { | |
468 | SCM arg2 = SCM_CAR (args); | |
469 | int len2 = srfi1_ilength (arg2); | |
470 | scm_t_trampoline_2 call = scm_trampoline_2 (proc); | |
471 | SCM_GASSERTn (call, g_srfi1_map, | |
472 | scm_cons2 (proc, arg1, args), SCM_ARG1, s_srfi1_map); | |
473 | if (len < 0 || (len2 >= 0 && len2 < len)) | |
474 | len = len2; | |
475 | SCM_GASSERTn ((SCM_NULLP (arg2) || SCM_CONSP (arg2)) | |
476 | && len >= 0 && len2 >= -1, | |
477 | g_srfi1_map, | |
478 | scm_cons2 (proc, arg1, args), | |
f9ac1c2d | 479 | len2 >= 0 ? SCM_ARG2 : SCM_ARG3, |
ee6aac97 MD |
480 | s_srfi1_map); |
481 | while (len > 0) | |
482 | { | |
483 | *pres = scm_list_1 (call (proc, SCM_CAR (arg1), SCM_CAR (arg2))); | |
484 | pres = SCM_CDRLOC (*pres); | |
485 | arg1 = SCM_CDR (arg1); | |
486 | arg2 = SCM_CDR (arg2); | |
487 | --len; | |
488 | } | |
489 | return res; | |
490 | } | |
491 | args = scm_vector (arg1 = scm_cons (arg1, args)); | |
492 | ve = SCM_VELTS (args); | |
493 | len = check_map_args (args, len, g_srfi1_map, proc, arg1, s_srfi1_map); | |
494 | while (len > 0) | |
495 | { | |
496 | arg1 = SCM_EOL; | |
497 | for (i = SCM_VECTOR_LENGTH (args) - 1; i >= 0; i--) | |
498 | { | |
499 | arg1 = scm_cons (SCM_CAR (ve[i]), arg1); | |
500 | SCM_VECTOR_SET (args, i, SCM_CDR (ve[i])); | |
501 | } | |
502 | *pres = scm_list_1 (scm_apply (proc, arg1, SCM_EOL)); | |
503 | pres = SCM_CDRLOC (*pres); | |
504 | --len; | |
505 | } | |
506 | return res; | |
507 | } | |
508 | #undef FUNC_NAME | |
509 | ||
510 | SCM_REGISTER_PROC (s_srfi1_map_in_order, "map-in-order", 2, 0, 1, scm_srfi1_map); | |
511 | ||
512 | SCM_GPROC (s_srfi1_for_each, "for-each", 2, 0, 1, scm_srfi1_for_each, g_srfi1_for_each); | |
513 | ||
514 | SCM | |
515 | scm_srfi1_for_each (SCM proc, SCM arg1, SCM args) | |
516 | #define FUNC_NAME s_srfi1_for_each | |
517 | { | |
518 | SCM const *ve = &args; /* Keep args from being optimized away. */ | |
519 | long i, len; | |
520 | len = srfi1_ilength (arg1); | |
521 | SCM_GASSERTn ((SCM_NULLP (arg1) || SCM_CONSP (arg1)) && len >= -1, | |
522 | g_srfi1_for_each, scm_cons2 (proc, arg1, args), | |
523 | SCM_ARG2, s_srfi1_for_each); | |
524 | SCM_VALIDATE_REST_ARGUMENT (args); | |
525 | if (SCM_NULLP (args)) | |
526 | { | |
527 | scm_t_trampoline_1 call = scm_trampoline_1 (proc); | |
528 | SCM_GASSERT2 (call, g_srfi1_for_each, proc, arg1, | |
529 | SCM_ARG1, s_srfi1_for_each); | |
530 | SCM_GASSERT2 (len >= 0, g_srfi1_for_each, proc, arg1, | |
531 | SCM_ARG2, s_srfi1_map); | |
532 | while (SCM_NIMP (arg1)) | |
533 | { | |
534 | call (proc, SCM_CAR (arg1)); | |
535 | arg1 = SCM_CDR (arg1); | |
536 | } | |
537 | return SCM_UNSPECIFIED; | |
538 | } | |
539 | if (SCM_NULLP (SCM_CDR (args))) | |
540 | { | |
541 | SCM arg2 = SCM_CAR (args); | |
542 | int len2 = srfi1_ilength (arg2); | |
543 | scm_t_trampoline_2 call = scm_trampoline_2 (proc); | |
544 | SCM_GASSERTn (call, g_srfi1_for_each, | |
545 | scm_cons2 (proc, arg1, args), SCM_ARG1, s_srfi1_for_each); | |
546 | if (len < 0 || (len2 >= 0 && len2 < len)) | |
547 | len = len2; | |
548 | SCM_GASSERTn ((SCM_NULLP (arg2) || SCM_CONSP (arg2)) | |
f9ac1c2d | 549 | && len >= 0 && len2 >= -1, |
ee6aac97 MD |
550 | g_srfi1_for_each, |
551 | scm_cons2 (proc, arg1, args), | |
f9ac1c2d | 552 | len2 >= 0 ? SCM_ARG2 : SCM_ARG3, |
ee6aac97 MD |
553 | s_srfi1_for_each); |
554 | while (len > 0) | |
555 | { | |
556 | call (proc, SCM_CAR (arg1), SCM_CAR (arg2)); | |
557 | arg1 = SCM_CDR (arg1); | |
558 | arg2 = SCM_CDR (arg2); | |
559 | --len; | |
560 | } | |
561 | return SCM_UNSPECIFIED; | |
562 | } | |
563 | args = scm_vector (arg1 = scm_cons (arg1, args)); | |
564 | ve = SCM_VELTS (args); | |
565 | len = check_map_args (args, len, g_srfi1_for_each, proc, arg1, | |
566 | s_srfi1_for_each); | |
567 | while (len > 0) | |
568 | { | |
569 | arg1 = SCM_EOL; | |
570 | for (i = SCM_VECTOR_LENGTH (args) - 1; i >= 0; i--) | |
571 | { | |
572 | arg1 = scm_cons (SCM_CAR (ve[i]), arg1); | |
573 | SCM_VECTOR_SET (args, i, SCM_CDR (ve[i])); | |
574 | } | |
575 | scm_apply (proc, arg1, SCM_EOL); | |
576 | --len; | |
577 | } | |
578 | return SCM_UNSPECIFIED; | |
579 | } | |
580 | #undef FUNC_NAME | |
581 | ||
582 | ||
ee6aac97 MD |
583 | SCM_DEFINE (scm_srfi1_member, "member", 2, 1, 0, |
584 | (SCM x, SCM lst, SCM pred), | |
585 | "Return the first sublist of @var{lst} whose car is\n" | |
7692d26b | 586 | "@var{equal?} to @var{x} where the sublists of @var{lst} are\n" |
ee6aac97 MD |
587 | "the non-empty lists returned by @code{(list-tail @var{lst}\n" |
588 | "@var{k})} for @var{k} less than the length of @var{lst}. If\n" | |
589 | "@var{x} does not occur in @var{lst}, then @code{#f} (not the\n" | |
7692d26b MD |
590 | "empty list) is returned. If optional third argument @var{equal?}\n" |
591 | "isn't given, @code{equal?} is used for comparison.\n" | |
592 | "(Extended from R5RS.)\n") | |
ee6aac97 MD |
593 | #define FUNC_NAME s_scm_srfi1_member |
594 | { | |
595 | scm_t_trampoline_2 equal_p; | |
596 | SCM_VALIDATE_LIST (2, lst); | |
597 | if (SCM_UNBNDP (pred)) | |
598 | equal_p = equal_trampoline; | |
599 | else | |
600 | { | |
601 | equal_p = scm_trampoline_2 (pred); | |
602 | SCM_ASSERT (equal_p, pred, 3, FUNC_NAME); | |
603 | } | |
604 | for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst)) | |
605 | { | |
606 | if (!SCM_FALSEP (equal_p (pred, SCM_CAR (lst), x))) | |
607 | return lst; | |
608 | } | |
609 | return SCM_BOOL_F; | |
610 | } | |
611 | #undef FUNC_NAME | |
612 | ||
7692d26b MD |
613 | SCM_DEFINE (scm_srfi1_assoc, "assoc", 2, 1, 0, |
614 | (SCM key, SCM alist, SCM pred), | |
615 | "Behaves like @code{assq} but uses third argument @var{pred?}\n" | |
616 | "for key comparison. If @var{pred?} is not supplied,\n" | |
617 | "@code{equal?} is used. (Extended from R5RS.)\n") | |
618 | #define FUNC_NAME s_scm_srfi1_assoc | |
619 | { | |
620 | SCM ls = alist; | |
621 | scm_t_trampoline_2 equal_p; | |
622 | if (SCM_UNBNDP (pred)) | |
623 | equal_p = equal_trampoline; | |
624 | else | |
625 | { | |
626 | equal_p = scm_trampoline_2 (pred); | |
627 | SCM_ASSERT (equal_p, pred, 3, FUNC_NAME); | |
628 | } | |
629 | for(; SCM_CONSP (ls); ls = SCM_CDR (ls)) | |
630 | { | |
631 | SCM tmp = SCM_CAR (ls); | |
632 | SCM_ASSERT_TYPE (SCM_CONSP (tmp), alist, SCM_ARG2, FUNC_NAME, | |
633 | "association list"); | |
634 | if (SCM_NFALSEP (equal_p (pred, SCM_CAR (tmp), key))) | |
635 | return tmp; | |
636 | } | |
637 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (ls), alist, SCM_ARG2, FUNC_NAME, | |
638 | "association list"); | |
639 | return SCM_BOOL_F; | |
640 | } | |
641 | #undef FUNC_NAME | |
642 | ||
65978fb2 KR |
643 | SCM_DEFINE (scm_srfi1_partition, "partition", 2, 0, 0, |
644 | (SCM pred, SCM list), | |
645 | "Partition the elements of @var{list} with predicate @var{pred}.\n" | |
646 | "Return two values: the list of elements satifying @var{pred} and\n" | |
647 | "the list of elements @emph{not} satisfying @var{pred}. The order\n" | |
648 | "of the output lists follows the order of @var{list}. @var{list}\n" | |
649 | "is not mutated. One of the output lists may share memory with @var{list}.\n") | |
650 | #define FUNC_NAME s_scm_srfi1_partition | |
651 | { | |
652 | /* In this implementation, the output lists don't share memory with | |
653 | list, because it's probably not worth the effort. */ | |
654 | scm_t_trampoline_1 call = scm_trampoline_1(pred); | |
655 | SCM kept = scm_cons(SCM_EOL, SCM_EOL); | |
656 | SCM kept_tail = kept; | |
657 | SCM dropped = scm_cons(SCM_EOL, SCM_EOL); | |
658 | SCM dropped_tail = dropped; | |
659 | ||
660 | SCM_ASSERT(call, pred, 2, FUNC_NAME); | |
661 | ||
662 | for (; !SCM_NULL_OR_NIL_P (list); list = SCM_CDR(list)) { | |
663 | SCM elt = SCM_CAR(list); | |
664 | SCM new_tail = scm_cons(SCM_CAR(list), SCM_EOL); | |
665 | if (SCM_NFALSEP(call(pred, elt))) { | |
666 | SCM_SETCDR(kept_tail, new_tail); | |
667 | kept_tail = new_tail; | |
668 | } | |
669 | else { | |
670 | SCM_SETCDR(dropped_tail, new_tail); | |
671 | dropped_tail = new_tail; | |
672 | } | |
673 | } | |
674 | /* re-use the initial conses for the values list */ | |
675 | SCM_SETCAR(kept, SCM_CDR(kept)); | |
676 | SCM_SETCDR(kept, dropped); | |
677 | SCM_SETCAR(dropped, SCM_CDR(dropped)); | |
678 | SCM_SETCDR(dropped, SCM_EOL); | |
679 | return scm_values(kept); | |
680 | } | |
681 | #undef FUNC_NAME | |
682 | ||
ee6aac97 MD |
683 | void |
684 | scm_init_srfi_1 (void) | |
685 | { | |
a48d60b1 | 686 | SCM the_root_module = scm_lookup_closure_module (SCM_BOOL_F); |
ee6aac97 MD |
687 | #ifndef SCM_MAGIC_SNARFER |
688 | #include "srfi/srfi-1.x" | |
689 | #endif | |
a48d60b1 MD |
690 | scm_c_extend_primitive_generic |
691 | (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module, "map")), | |
692 | SCM_VARIABLE_REF (scm_c_lookup ("map"))); | |
693 | scm_c_extend_primitive_generic | |
694 | (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module, "for-each")), | |
695 | SCM_VARIABLE_REF (scm_c_lookup ("for-each"))); | |
ee6aac97 MD |
696 | } |
697 | ||
698 | /* End of srfi-1.c. */ |