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 | ||
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 | ||
110348ae | 74 | SCM_DEFINE (scm_srfi1_count, "count", 2, 0, 1, |
edea856c | 75 | (SCM pred, SCM list1, SCM rest), |
110348ae KR |
76 | "Return a count of the number of times @var{pred} returns true\n" |
77 | "when called on elements from the given lists.\n" | |
78 | "\n" | |
79 | "@var{pred} is called with @var{N} parameters @code{(@var{pred}\n" | |
80 | "@var{elem1} @dots{} @var{elemN})}, each element being from the\n" | |
edea856c | 81 | "corresponding @var{list1} @dots{} @var{lstN}. The first call is\n" |
110348ae KR |
82 | "with the first element of each list, the second with the second\n" |
83 | "element from each, and so on.\n" | |
84 | "\n" | |
85 | "Counting stops when the end of the shortest list is reached.\n" | |
86 | "At least one list must be non-circular.") | |
87 | #define FUNC_NAME s_scm_srfi1_count | |
88 | { | |
89 | long count; | |
90 | SCM_VALIDATE_REST_ARGUMENT (rest); | |
91 | ||
92 | count = 0; | |
93 | ||
896df2d5 | 94 | if (scm_is_null (rest)) |
110348ae KR |
95 | { |
96 | /* one list */ | |
97 | scm_t_trampoline_1 pred_tramp; | |
98 | pred_tramp = scm_trampoline_1 (pred); | |
99 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
100 | ||
896df2d5 | 101 | for ( ; scm_is_pair (list1); list1 = SCM_CDR (list1)) |
edea856c | 102 | count += scm_is_true (pred_tramp (pred, SCM_CAR (list1))); |
110348ae KR |
103 | |
104 | end_lst1: | |
edea856c | 105 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (list1), list1, SCM_ARG2, FUNC_NAME, |
110348ae KR |
106 | "list"); |
107 | } | |
896df2d5 | 108 | else if (scm_is_pair (rest) && scm_is_null (SCM_CDR (rest))) |
110348ae KR |
109 | { |
110 | /* two lists */ | |
111 | scm_t_trampoline_2 pred_tramp; | |
edea856c | 112 | SCM list2; |
110348ae KR |
113 | |
114 | pred_tramp = scm_trampoline_2 (pred); | |
115 | SCM_ASSERT (pred_tramp, pred, SCM_ARG1, FUNC_NAME); | |
116 | ||
edea856c | 117 | list2 = SCM_CAR (rest); |
110348ae KR |
118 | for (;;) |
119 | { | |
896df2d5 | 120 | if (! scm_is_pair (list1)) |
110348ae | 121 | goto end_lst1; |
896df2d5 | 122 | if (! scm_is_pair (list2)) |
110348ae | 123 | { |
edea856c | 124 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (list2), list2, SCM_ARG3, |
110348ae KR |
125 | FUNC_NAME, "list"); |
126 | break; | |
127 | } | |
00874d5f | 128 | count += scm_is_true (pred_tramp |
edea856c SJ |
129 | (pred, SCM_CAR (list1), SCM_CAR (list2))); |
130 | list1 = SCM_CDR (list1); | |
131 | list2 = SCM_CDR (list2); | |
110348ae KR |
132 | } |
133 | } | |
134 | else | |
135 | { | |
136 | /* three or more lists */ | |
137 | SCM lstlst, args, l, a, lst; | |
138 | int argnum; | |
139 | ||
140 | /* lstlst is a list of the list arguments */ | |
edea856c | 141 | lstlst = scm_cons (list1, rest); |
110348ae KR |
142 | |
143 | /* args is the argument list to pass to pred, same length as lstlst, | |
144 | re-used for each call */ | |
145 | args = SCM_EOL; | |
896df2d5 | 146 | for (l = lstlst; scm_is_pair (l); l = SCM_CDR (l)) |
110348ae KR |
147 | args = scm_cons (SCM_BOOL_F, args); |
148 | ||
149 | for (;;) | |
150 | { | |
151 | /* first elem of each list in lstlst into args, and step those | |
152 | lstlst entries onto their next element */ | |
153 | for (l = lstlst, a = args, argnum = 2; | |
896df2d5 | 154 | scm_is_pair (l); |
110348ae KR |
155 | l = SCM_CDR (l), a = SCM_CDR (a), argnum++) |
156 | { | |
157 | lst = SCM_CAR (l); /* list argument */ | |
896df2d5 | 158 | if (! scm_is_pair (lst)) |
110348ae KR |
159 | { |
160 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, | |
161 | argnum, FUNC_NAME, "list"); | |
162 | goto done; | |
163 | } | |
164 | SCM_SETCAR (a, SCM_CAR (lst)); /* arg for pred */ | |
165 | SCM_SETCAR (l, SCM_CDR (lst)); /* keep rest of lst */ | |
166 | } | |
167 | ||
00874d5f | 168 | count += scm_is_true (scm_apply (pred, args, SCM_EOL)); |
110348ae KR |
169 | } |
170 | } | |
171 | done: | |
93ccaef0 | 172 | return scm_from_long (count); |
110348ae KR |
173 | } |
174 | #undef FUNC_NAME | |
175 | ||
176 | ||
d0a634de KR |
177 | SCM_DEFINE (scm_srfi1_delete, "delete", 2, 1, 0, |
178 | (SCM x, SCM lst, SCM pred), | |
179 | "Return a list containing the elements of @var{lst} but with\n" | |
180 | "those equal to @var{x} deleted. The returned elements will be\n" | |
181 | "in the same order as they were in @var{lst}.\n" | |
182 | "\n" | |
183 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
184 | "given. An equality call is made just once for each element,\n" | |
185 | "but the order in which the calls are made on the elements is\n" | |
186 | "unspecified.\n" | |
187 | "\n" | |
188 | "The equality calls are always @code{(pred x elem)}, ie.@: the\n" | |
189 | "given @var{x} is first. This means for instance elements\n" | |
190 | "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n" | |
191 | "\n" | |
192 | "@var{lst} is not modified, but the returned list might share a\n" | |
193 | "common tail with @var{lst}.") | |
194 | #define FUNC_NAME s_scm_srfi1_delete | |
195 | { | |
196 | scm_t_trampoline_2 equal_p; | |
197 | SCM ret, *p, keeplst; | |
198 | ||
199 | if (SCM_UNBNDP (pred)) | |
200 | return scm_delete (x, lst); | |
201 | ||
202 | equal_p = scm_trampoline_2 (pred); | |
203 | SCM_ASSERT (equal_p, pred, SCM_ARG3, FUNC_NAME); | |
204 | ||
205 | /* ret is the return list being constructed. p is where to append to it, | |
206 | initially &ret then SCM_CDRLOC of the last pair. lst progresses as | |
207 | elements are considered. | |
208 | ||
209 | Elements to be retained are not immediately copied, instead keeplst is | |
210 | the last pair in lst which is to be retained but not yet copied. When | |
211 | there's no more deletions, *p can be set to keeplst to share the | |
212 | remainder of the original lst. (The entire original lst if there's no | |
213 | deletions at all.) */ | |
214 | ||
215 | keeplst = lst; | |
216 | ret = SCM_EOL; | |
217 | p = &ret; | |
218 | ||
896df2d5 | 219 | for ( ; scm_is_pair (lst); lst = SCM_CDR (lst)) |
d0a634de | 220 | { |
00874d5f | 221 | if (scm_is_true (equal_p (pred, x, SCM_CAR (lst)))) |
d0a634de KR |
222 | { |
223 | /* delete this element, so copy from keeplst (inclusive) to lst | |
224 | (exclusive) onto ret */ | |
bc36d050 | 225 | while (! scm_is_eq (keeplst, lst)) |
d0a634de KR |
226 | { |
227 | SCM c = scm_cons (SCM_CAR (keeplst), SCM_EOL); | |
228 | *p = c; | |
229 | p = SCM_CDRLOC (c); | |
230 | keeplst = SCM_CDR (keeplst); | |
231 | } | |
232 | ||
233 | keeplst = SCM_CDR (lst); | |
234 | } | |
235 | } | |
236 | ||
237 | /* final retained elements */ | |
238 | *p = keeplst; | |
239 | ||
240 | /* demand that lst was a proper list */ | |
241 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list"); | |
242 | ||
243 | return ret; | |
244 | } | |
245 | #undef FUNC_NAME | |
246 | ||
247 | ||
248 | SCM_DEFINE (scm_srfi1_delete_x, "delete!", 2, 1, 0, | |
249 | (SCM x, SCM lst, SCM pred), | |
250 | "Return a list containing the elements of @var{lst} but with\n" | |
251 | "those equal to @var{x} deleted. The returned elements will be\n" | |
252 | "in the same order as they were in @var{lst}.\n" | |
253 | "\n" | |
254 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
255 | "given. An equality call is made just once for each element,\n" | |
256 | "but the order in which the calls are made on the elements is\n" | |
257 | "unspecified.\n" | |
258 | "\n" | |
259 | "The equality calls are always @code{(pred x elem)}, ie.@: the\n" | |
260 | "given @var{x} is first. This means for instance elements\n" | |
261 | "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n" | |
262 | "\n" | |
263 | "@var{lst} may be modified to construct the returned list.") | |
264 | #define FUNC_NAME s_scm_srfi1_delete_x | |
265 | { | |
266 | scm_t_trampoline_2 equal_p; | |
267 | SCM walk; | |
268 | SCM *prev; | |
269 | ||
270 | if (SCM_UNBNDP (pred)) | |
271 | return scm_delete_x (x, lst); | |
272 | ||
273 | equal_p = scm_trampoline_2 (pred); | |
274 | SCM_ASSERT (equal_p, pred, SCM_ARG3, FUNC_NAME); | |
275 | ||
276 | for (prev = &lst, walk = lst; | |
896df2d5 | 277 | scm_is_pair (walk); |
d0a634de KR |
278 | walk = SCM_CDR (walk)) |
279 | { | |
00874d5f | 280 | if (scm_is_true (equal_p (pred, x, SCM_CAR (walk)))) |
d0a634de KR |
281 | *prev = SCM_CDR (walk); |
282 | else | |
283 | prev = SCM_CDRLOC (walk); | |
284 | } | |
285 | ||
286 | /* demand the input was a proper list */ | |
287 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (walk), walk, SCM_ARG2, FUNC_NAME,"list"); | |
288 | return lst; | |
289 | } | |
290 | #undef FUNC_NAME | |
291 | ||
292 | ||
293 | SCM_DEFINE (scm_srfi1_delete_duplicates, "delete-duplicates", 1, 1, 0, | |
294 | (SCM lst, SCM pred), | |
295 | "Return a list containing the elements of @var{lst} but without\n" | |
296 | "duplicates.\n" | |
297 | "\n" | |
298 | "When elements are equal, only the first in @var{lst} is\n" | |
299 | "retained. Equal elements can be anywhere in @var{lst}, they\n" | |
300 | "don't have to be adjacent. The returned list will have the\n" | |
301 | "retained elements in the same order as they were in @var{lst}.\n" | |
302 | "\n" | |
303 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
304 | "given. Calls @code{(pred x y)} are made with element @var{x}\n" | |
305 | "being before @var{y} in @var{lst}. A call is made at most once\n" | |
306 | "for each combination, but the sequence of the calls across the\n" | |
307 | "elements is unspecified.\n" | |
308 | "\n" | |
309 | "@var{lst} is not modified, but the return might share a common\n" | |
310 | "tail with @var{lst}.\n" | |
311 | "\n" | |
312 | "In the worst case, this is an @math{O(N^2)} algorithm because\n" | |
313 | "it must check each element against all those preceding it. For\n" | |
314 | "long lists it is more efficient to sort and then compare only\n" | |
315 | "adjacent elements.") | |
316 | #define FUNC_NAME s_scm_srfi1_delete_duplicates | |
317 | { | |
318 | scm_t_trampoline_2 equal_p; | |
319 | SCM ret, *p, keeplst, item, l; | |
320 | ||
321 | /* ret is the new list constructed. p is where to append, initially &ret | |
322 | then SCM_CDRLOC of the last pair. lst is advanced as each element is | |
323 | considered. | |
324 | ||
325 | Elements retained are not immediately appended to ret, instead keeplst | |
326 | is the last pair in lst which is to be kept but is not yet copied. | |
327 | Initially this is the first pair of lst, since the first element is | |
328 | always retained. | |
329 | ||
330 | *p is kept set to keeplst, so ret (inclusive) to lst (exclusive) is all | |
331 | the elements retained, making the equality search loop easy. | |
332 | ||
333 | If an item must be deleted, elements from keeplst (inclusive) to lst | |
334 | (exclusive) must be copied and appended to ret. When there's no more | |
335 | deletions, *p is left set to keeplst, so ret shares structure with the | |
336 | original lst. (ret will be the entire original lst if there are no | |
337 | deletions.) */ | |
338 | ||
339 | /* skip to end if an empty list (or something invalid) */ | |
340 | ret = lst; | |
896df2d5 | 341 | if (scm_is_pair (lst)) |
d0a634de KR |
342 | { |
343 | if (SCM_UNBNDP (pred)) | |
344 | equal_p = equal_trampoline; | |
345 | else | |
346 | { | |
347 | equal_p = scm_trampoline_2 (pred); | |
348 | SCM_ASSERT (equal_p, pred, SCM_ARG2, FUNC_NAME); | |
349 | } | |
350 | ||
351 | keeplst = lst; | |
352 | p = &ret; | |
353 | ||
354 | /* loop over lst elements starting from second */ | |
355 | for (;;) | |
356 | { | |
357 | lst = SCM_CDR (lst); | |
896df2d5 | 358 | if (! scm_is_pair (lst)) |
d0a634de KR |
359 | break; |
360 | item = SCM_CAR (lst); | |
361 | ||
362 | /* loop searching ret upto lst */ | |
bc36d050 | 363 | for (l = ret; ! scm_is_eq (l, lst); l = SCM_CDR (l)) |
d0a634de | 364 | { |
00874d5f | 365 | if (scm_is_true (equal_p (pred, SCM_CAR (l), item))) |
d0a634de KR |
366 | { |
367 | /* duplicate, don't want this element, so copy keeplst | |
368 | (inclusive) to lst (exclusive) onto ret */ | |
bc36d050 | 369 | while (! scm_is_eq (keeplst, lst)) |
d0a634de KR |
370 | { |
371 | SCM c = scm_cons (SCM_CAR (keeplst), SCM_EOL); | |
372 | *p = c; | |
373 | p = SCM_CDRLOC (c); | |
374 | keeplst = SCM_CDR (keeplst); | |
375 | } | |
376 | ||
377 | keeplst = SCM_CDR (lst); /* elem after the one deleted */ | |
378 | *p = keeplst; | |
379 | break; | |
380 | } | |
381 | } | |
382 | } | |
383 | } | |
384 | ||
385 | /* demand that lst was a proper list */ | |
386 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list"); | |
387 | ||
388 | return ret; | |
389 | } | |
390 | #undef FUNC_NAME | |
391 | ||
392 | ||
393 | SCM_DEFINE (scm_srfi1_delete_duplicates_x, "delete-duplicates!", 1, 1, 0, | |
394 | (SCM lst, SCM pred), | |
395 | "Return a list containing the elements of @var{lst} but without\n" | |
396 | "duplicates.\n" | |
397 | "\n" | |
398 | "When elements are equal, only the first in @var{lst} is\n" | |
399 | "retained. Equal elements can be anywhere in @var{lst}, they\n" | |
400 | "don't have to be adjacent. The returned list will have the\n" | |
401 | "retained elements in the same order as they were in @var{lst}.\n" | |
402 | "\n" | |
403 | "Equality is determined by @var{pred}, or @code{equal?} if not\n" | |
404 | "given. Calls @code{(pred x y)} are made with element @var{x}\n" | |
405 | "being before @var{y} in @var{lst}. A call is made at most once\n" | |
406 | "for each combination, but the sequence of the calls across the\n" | |
407 | "elements is unspecified.\n" | |
408 | "\n" | |
409 | "@var{lst} may be modified to construct the returned list.\n" | |
410 | "\n" | |
411 | "In the worst case, this is an @math{O(N^2)} algorithm because\n" | |
412 | "it must check each element against all those preceding it. For\n" | |
413 | "long lists it is more efficient to sort and then compare only\n" | |
414 | "adjacent elements.") | |
415 | #define FUNC_NAME s_scm_srfi1_delete_duplicates_x | |
416 | { | |
417 | scm_t_trampoline_2 equal_p; | |
418 | SCM ret, endret, item, l; | |
419 | ||
420 | /* ret is the return list, constructed from the pairs in lst. endret is | |
421 | the last pair of ret, initially the first pair. lst is advanced as | |
422 | elements are considered. */ | |
423 | ||
424 | /* skip to end if an empty list (or something invalid) */ | |
425 | ret = lst; | |
896df2d5 | 426 | if (scm_is_pair (lst)) |
d0a634de KR |
427 | { |
428 | if (SCM_UNBNDP (pred)) | |
429 | equal_p = equal_trampoline; | |
430 | else | |
431 | { | |
432 | equal_p = scm_trampoline_2 (pred); | |
433 | SCM_ASSERT (equal_p, pred, SCM_ARG2, FUNC_NAME); | |
434 | } | |
435 | ||
436 | endret = ret; | |
437 | ||
438 | /* loop over lst elements starting from second */ | |
439 | for (;;) | |
440 | { | |
441 | lst = SCM_CDR (lst); | |
896df2d5 | 442 | if (! scm_is_pair (lst)) |
d0a634de KR |
443 | break; |
444 | item = SCM_CAR (lst); | |
445 | ||
446 | /* is item equal to any element from ret to endret (inclusive)? */ | |
447 | l = ret; | |
448 | for (;;) | |
449 | { | |
00874d5f | 450 | if (scm_is_true (equal_p (pred, SCM_CAR (l), item))) |
d0a634de KR |
451 | break; /* equal, forget this element */ |
452 | ||
bc36d050 | 453 | if (scm_is_eq (l, endret)) |
d0a634de KR |
454 | { |
455 | /* not equal to any, so append this pair */ | |
456 | SCM_SETCDR (endret, lst); | |
457 | endret = lst; | |
458 | break; | |
459 | } | |
460 | l = SCM_CDR (l); | |
461 | } | |
462 | } | |
463 | ||
464 | /* terminate, in case last element was deleted */ | |
465 | SCM_SETCDR (endret, SCM_EOL); | |
466 | } | |
467 | ||
468 | /* demand that lst was a proper list */ | |
469 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list"); | |
470 | ||
471 | return ret; | |
472 | } | |
473 | #undef FUNC_NAME | |
474 | ||
475 | ||
de51f595 KR |
476 | SCM_DEFINE (scm_srfi1_length_plus, "length+", 1, 0, 0, |
477 | (SCM lst), | |
478 | "Return the length of @var{lst}, or @code{#f} if @var{lst} is\n" | |
479 | "circular.") | |
480 | #define FUNC_NAME s_scm_srfi1_length_plus | |
481 | { | |
482 | long len = scm_ilength (lst); | |
93ccaef0 | 483 | return (len >= 0 ? SCM_I_MAKINUM (len) : SCM_BOOL_F); |
de51f595 KR |
484 | } |
485 | #undef FUNC_NAME | |
486 | ||
487 | ||
d61261f0 KR |
488 | /* This routine differs from the core list-copy in allowing improper lists. |
489 | Maybe the core could allow them similarly. */ | |
490 | ||
491 | SCM_DEFINE (scm_srfi1_list_copy, "list-copy", 1, 0, 0, | |
492 | (SCM lst), | |
493 | "Return a copy of the given list @var{lst}.\n" | |
494 | "\n" | |
495 | "@var{lst} can be a proper or improper list. And if @var{lst}\n" | |
496 | "is not a pair then it's treated as the final tail of an\n" | |
497 | "improper list and simply returned.") | |
498 | #define FUNC_NAME s_scm_srfi1_list_copy | |
499 | { | |
500 | SCM newlst; | |
501 | SCM * fill_here; | |
502 | SCM from_here; | |
503 | ||
504 | newlst = lst; | |
505 | fill_here = &newlst; | |
506 | from_here = lst; | |
507 | ||
896df2d5 | 508 | while (scm_is_pair (from_here)) |
d61261f0 KR |
509 | { |
510 | SCM c; | |
511 | c = scm_cons (SCM_CAR (from_here), SCM_CDR (from_here)); | |
512 | *fill_here = c; | |
513 | fill_here = SCM_CDRLOC (c); | |
514 | from_here = SCM_CDR (from_here); | |
515 | } | |
516 | return newlst; | |
517 | } | |
518 | #undef FUNC_NAME | |
519 | ||
520 | ||
ee6aac97 MD |
521 | /* Typechecking for multi-argument MAP and FOR-EACH. |
522 | ||
523 | Verify that each element of the vector ARGV, except for the first, | |
524 | is a list and return minimum length. Attribute errors to WHO, | |
525 | and claim that the i'th element of ARGV is WHO's i+2'th argument. */ | |
526 | static inline int | |
527 | check_map_args (SCM argv, | |
528 | long len, | |
529 | SCM gf, | |
530 | SCM proc, | |
531 | SCM args, | |
532 | const char *who) | |
533 | { | |
ee6aac97 MD |
534 | long i; |
535 | ||
3c4ce91b | 536 | for (i = SCM_SIMPLE_VECTOR_LENGTH (argv) - 1; i >= 1; i--) |
ee6aac97 | 537 | { |
3a0cf656 | 538 | SCM elt = SCM_SIMPLE_VECTOR_REF (argv, i); |
ee6aac97 MD |
539 | long elt_len; |
540 | ||
896df2d5 | 541 | if (!(scm_is_null (elt) || scm_is_pair (elt))) |
ee6aac97 MD |
542 | { |
543 | check_map_error: | |
544 | if (gf) | |
545 | scm_apply_generic (gf, scm_cons (proc, args)); | |
546 | else | |
3c4ce91b | 547 | scm_wrong_type_arg (who, i + 2, elt); |
ee6aac97 MD |
548 | } |
549 | ||
3c4ce91b | 550 | elt_len = srfi1_ilength (elt); |
ee6aac97 MD |
551 | if (elt_len < -1) |
552 | goto check_map_error; | |
553 | ||
554 | if (len < 0 || (elt_len >= 0 && elt_len < len)) | |
555 | len = elt_len; | |
556 | } | |
557 | if (len < 0) | |
558 | /* i == 0 */ | |
559 | goto check_map_error; | |
560 | ||
561 | scm_remember_upto_here_1 (argv); | |
562 | return len; | |
563 | } | |
564 | ||
565 | ||
566 | SCM_GPROC (s_srfi1_map, "map", 2, 0, 1, scm_srfi1_map, g_srfi1_map); | |
567 | ||
568 | /* Note: Currently, scm_srfi1_map applies PROC to the argument list(s) | |
569 | sequentially, starting with the first element(s). This is used in | |
570 | the Scheme procedure `map-in-order', which guarantees sequential | |
571 | behaviour, is implemented using scm_map. If the behaviour changes, | |
572 | we need to update `map-in-order'. | |
573 | */ | |
574 | ||
575 | SCM | |
576 | scm_srfi1_map (SCM proc, SCM arg1, SCM args) | |
577 | #define FUNC_NAME s_srfi1_map | |
578 | { | |
579 | long i, len; | |
580 | SCM res = SCM_EOL; | |
581 | SCM *pres = &res; | |
ee6aac97 MD |
582 | |
583 | len = srfi1_ilength (arg1); | |
896df2d5 | 584 | SCM_GASSERTn ((scm_is_null (arg1) || scm_is_pair (arg1)) && len >= -1, |
ee6aac97 MD |
585 | g_srfi1_map, |
586 | scm_cons2 (proc, arg1, args), SCM_ARG2, s_srfi1_map); | |
587 | SCM_VALIDATE_REST_ARGUMENT (args); | |
896df2d5 | 588 | if (scm_is_null (args)) |
ee6aac97 MD |
589 | { |
590 | scm_t_trampoline_1 call = scm_trampoline_1 (proc); | |
591 | SCM_GASSERT2 (call, g_srfi1_map, proc, arg1, SCM_ARG1, s_srfi1_map); | |
592 | SCM_GASSERT2 (len >= 0, g_srfi1_map, proc, arg1, SCM_ARG2, s_srfi1_map); | |
593 | while (SCM_NIMP (arg1)) | |
594 | { | |
595 | *pres = scm_list_1 (call (proc, SCM_CAR (arg1))); | |
596 | pres = SCM_CDRLOC (*pres); | |
597 | arg1 = SCM_CDR (arg1); | |
598 | } | |
599 | return res; | |
600 | } | |
896df2d5 | 601 | if (scm_is_null (SCM_CDR (args))) |
ee6aac97 MD |
602 | { |
603 | SCM arg2 = SCM_CAR (args); | |
604 | int len2 = srfi1_ilength (arg2); | |
605 | scm_t_trampoline_2 call = scm_trampoline_2 (proc); | |
606 | SCM_GASSERTn (call, g_srfi1_map, | |
607 | scm_cons2 (proc, arg1, args), SCM_ARG1, s_srfi1_map); | |
608 | if (len < 0 || (len2 >= 0 && len2 < len)) | |
609 | len = len2; | |
896df2d5 | 610 | SCM_GASSERTn ((scm_is_null (arg2) || scm_is_pair (arg2)) |
ee6aac97 MD |
611 | && len >= 0 && len2 >= -1, |
612 | g_srfi1_map, | |
613 | scm_cons2 (proc, arg1, args), | |
f9ac1c2d | 614 | len2 >= 0 ? SCM_ARG2 : SCM_ARG3, |
ee6aac97 MD |
615 | s_srfi1_map); |
616 | while (len > 0) | |
617 | { | |
618 | *pres = scm_list_1 (call (proc, SCM_CAR (arg1), SCM_CAR (arg2))); | |
619 | pres = SCM_CDRLOC (*pres); | |
620 | arg1 = SCM_CDR (arg1); | |
621 | arg2 = SCM_CDR (arg2); | |
622 | --len; | |
623 | } | |
624 | return res; | |
625 | } | |
626 | args = scm_vector (arg1 = scm_cons (arg1, args)); | |
ee6aac97 MD |
627 | len = check_map_args (args, len, g_srfi1_map, proc, arg1, s_srfi1_map); |
628 | while (len > 0) | |
629 | { | |
630 | arg1 = SCM_EOL; | |
3c4ce91b | 631 | for (i = SCM_SIMPLE_VECTOR_LENGTH (args) - 1; i >= 0; i--) |
ee6aac97 | 632 | { |
3c4ce91b MV |
633 | SCM elt = SCM_SIMPLE_VECTOR_REF (args, i); |
634 | arg1 = scm_cons (SCM_CAR (elt), arg1); | |
635 | SCM_SIMPLE_VECTOR_SET (args, i, SCM_CDR (elt)); | |
ee6aac97 MD |
636 | } |
637 | *pres = scm_list_1 (scm_apply (proc, arg1, SCM_EOL)); | |
638 | pres = SCM_CDRLOC (*pres); | |
639 | --len; | |
640 | } | |
641 | return res; | |
642 | } | |
643 | #undef FUNC_NAME | |
644 | ||
645 | SCM_REGISTER_PROC (s_srfi1_map_in_order, "map-in-order", 2, 0, 1, scm_srfi1_map); | |
646 | ||
647 | SCM_GPROC (s_srfi1_for_each, "for-each", 2, 0, 1, scm_srfi1_for_each, g_srfi1_for_each); | |
648 | ||
649 | SCM | |
650 | scm_srfi1_for_each (SCM proc, SCM arg1, SCM args) | |
651 | #define FUNC_NAME s_srfi1_for_each | |
652 | { | |
ee6aac97 MD |
653 | long i, len; |
654 | len = srfi1_ilength (arg1); | |
896df2d5 | 655 | SCM_GASSERTn ((scm_is_null (arg1) || scm_is_pair (arg1)) && len >= -1, |
ee6aac97 MD |
656 | g_srfi1_for_each, scm_cons2 (proc, arg1, args), |
657 | SCM_ARG2, s_srfi1_for_each); | |
658 | SCM_VALIDATE_REST_ARGUMENT (args); | |
896df2d5 | 659 | if (scm_is_null (args)) |
ee6aac97 MD |
660 | { |
661 | scm_t_trampoline_1 call = scm_trampoline_1 (proc); | |
662 | SCM_GASSERT2 (call, g_srfi1_for_each, proc, arg1, | |
663 | SCM_ARG1, s_srfi1_for_each); | |
664 | SCM_GASSERT2 (len >= 0, g_srfi1_for_each, proc, arg1, | |
665 | SCM_ARG2, s_srfi1_map); | |
666 | while (SCM_NIMP (arg1)) | |
667 | { | |
668 | call (proc, SCM_CAR (arg1)); | |
669 | arg1 = SCM_CDR (arg1); | |
670 | } | |
671 | return SCM_UNSPECIFIED; | |
672 | } | |
896df2d5 | 673 | if (scm_is_null (SCM_CDR (args))) |
ee6aac97 MD |
674 | { |
675 | SCM arg2 = SCM_CAR (args); | |
676 | int len2 = srfi1_ilength (arg2); | |
677 | scm_t_trampoline_2 call = scm_trampoline_2 (proc); | |
678 | SCM_GASSERTn (call, g_srfi1_for_each, | |
679 | scm_cons2 (proc, arg1, args), SCM_ARG1, s_srfi1_for_each); | |
680 | if (len < 0 || (len2 >= 0 && len2 < len)) | |
681 | len = len2; | |
896df2d5 | 682 | SCM_GASSERTn ((scm_is_null (arg2) || scm_is_pair (arg2)) |
f9ac1c2d | 683 | && len >= 0 && len2 >= -1, |
ee6aac97 MD |
684 | g_srfi1_for_each, |
685 | scm_cons2 (proc, arg1, args), | |
f9ac1c2d | 686 | len2 >= 0 ? SCM_ARG2 : SCM_ARG3, |
ee6aac97 MD |
687 | s_srfi1_for_each); |
688 | while (len > 0) | |
689 | { | |
690 | call (proc, SCM_CAR (arg1), SCM_CAR (arg2)); | |
691 | arg1 = SCM_CDR (arg1); | |
692 | arg2 = SCM_CDR (arg2); | |
693 | --len; | |
694 | } | |
695 | return SCM_UNSPECIFIED; | |
696 | } | |
697 | args = scm_vector (arg1 = scm_cons (arg1, args)); | |
ee6aac97 MD |
698 | len = check_map_args (args, len, g_srfi1_for_each, proc, arg1, |
699 | s_srfi1_for_each); | |
700 | while (len > 0) | |
701 | { | |
702 | arg1 = SCM_EOL; | |
3c4ce91b | 703 | for (i = SCM_SIMPLE_VECTOR_LENGTH (args) - 1; i >= 0; i--) |
ee6aac97 | 704 | { |
3c4ce91b MV |
705 | SCM elt = SCM_SIMPLE_VECTOR_REF (args, i); |
706 | arg1 = scm_cons (SCM_CAR (elt), arg1); | |
707 | SCM_SIMPLE_VECTOR_SET (args, i, SCM_CDR (elt)); | |
ee6aac97 MD |
708 | } |
709 | scm_apply (proc, arg1, SCM_EOL); | |
710 | --len; | |
711 | } | |
712 | return SCM_UNSPECIFIED; | |
713 | } | |
714 | #undef FUNC_NAME | |
715 | ||
716 | ||
ee6aac97 MD |
717 | SCM_DEFINE (scm_srfi1_member, "member", 2, 1, 0, |
718 | (SCM x, SCM lst, SCM pred), | |
4e3cc389 KR |
719 | "Return the first sublist of @var{lst} whose @sc{car} is equal\n" |
720 | "to @var{x}. If @var{x} does not appear in @var{lst}, return\n" | |
721 | "@code{#f}.\n" | |
722 | "\n" | |
723 | "Equality is determined by @code{equal?}, or by the equality\n" | |
724 | "predicate @var{=} if given. @var{=} is called @code{(= @var{x}\n" | |
725 | "elem)}, ie.@: with the given @var{x} first, so for example to\n" | |
726 | "find the first element greater than 5,\n" | |
727 | "\n" | |
728 | "@example\n" | |
729 | "(member 5 '(3 5 1 7 2 9) <) @result{} (7 2 9)\n" | |
730 | "@end example\n" | |
731 | "\n" | |
732 | "This version of @code{member} extends the core @code{member} by\n" | |
733 | "accepting an equality predicate.") | |
ee6aac97 MD |
734 | #define FUNC_NAME s_scm_srfi1_member |
735 | { | |
736 | scm_t_trampoline_2 equal_p; | |
737 | SCM_VALIDATE_LIST (2, lst); | |
738 | if (SCM_UNBNDP (pred)) | |
739 | equal_p = equal_trampoline; | |
740 | else | |
741 | { | |
742 | equal_p = scm_trampoline_2 (pred); | |
743 | SCM_ASSERT (equal_p, pred, 3, FUNC_NAME); | |
744 | } | |
745 | for (; !SCM_NULL_OR_NIL_P (lst); lst = SCM_CDR (lst)) | |
746 | { | |
2796304a | 747 | if (scm_is_true (equal_p (pred, x, SCM_CAR (lst)))) |
ee6aac97 MD |
748 | return lst; |
749 | } | |
750 | return SCM_BOOL_F; | |
751 | } | |
752 | #undef FUNC_NAME | |
753 | ||
7692d26b MD |
754 | SCM_DEFINE (scm_srfi1_assoc, "assoc", 2, 1, 0, |
755 | (SCM key, SCM alist, SCM pred), | |
756 | "Behaves like @code{assq} but uses third argument @var{pred?}\n" | |
757 | "for key comparison. If @var{pred?} is not supplied,\n" | |
758 | "@code{equal?} is used. (Extended from R5RS.)\n") | |
759 | #define FUNC_NAME s_scm_srfi1_assoc | |
760 | { | |
761 | SCM ls = alist; | |
762 | scm_t_trampoline_2 equal_p; | |
763 | if (SCM_UNBNDP (pred)) | |
764 | equal_p = equal_trampoline; | |
765 | else | |
766 | { | |
767 | equal_p = scm_trampoline_2 (pred); | |
768 | SCM_ASSERT (equal_p, pred, 3, FUNC_NAME); | |
769 | } | |
896df2d5 | 770 | for(; scm_is_pair (ls); ls = SCM_CDR (ls)) |
7692d26b MD |
771 | { |
772 | SCM tmp = SCM_CAR (ls); | |
896df2d5 | 773 | SCM_ASSERT_TYPE (scm_is_pair (tmp), alist, SCM_ARG2, FUNC_NAME, |
7692d26b | 774 | "association list"); |
00874d5f | 775 | if (scm_is_true (equal_p (pred, SCM_CAR (tmp), key))) |
7692d26b MD |
776 | return tmp; |
777 | } | |
778 | SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (ls), alist, SCM_ARG2, FUNC_NAME, | |
779 | "association list"); | |
780 | return SCM_BOOL_F; | |
781 | } | |
782 | #undef FUNC_NAME | |
783 | ||
65978fb2 KR |
784 | SCM_DEFINE (scm_srfi1_partition, "partition", 2, 0, 0, |
785 | (SCM pred, SCM list), | |
786 | "Partition the elements of @var{list} with predicate @var{pred}.\n" | |
787 | "Return two values: the list of elements satifying @var{pred} and\n" | |
788 | "the list of elements @emph{not} satisfying @var{pred}. The order\n" | |
789 | "of the output lists follows the order of @var{list}. @var{list}\n" | |
790 | "is not mutated. One of the output lists may share memory with @var{list}.\n") | |
791 | #define FUNC_NAME s_scm_srfi1_partition | |
792 | { | |
793 | /* In this implementation, the output lists don't share memory with | |
794 | list, because it's probably not worth the effort. */ | |
795 | scm_t_trampoline_1 call = scm_trampoline_1(pred); | |
796 | SCM kept = scm_cons(SCM_EOL, SCM_EOL); | |
797 | SCM kept_tail = kept; | |
798 | SCM dropped = scm_cons(SCM_EOL, SCM_EOL); | |
799 | SCM dropped_tail = dropped; | |
800 | ||
801 | SCM_ASSERT(call, pred, 2, FUNC_NAME); | |
802 | ||
803 | for (; !SCM_NULL_OR_NIL_P (list); list = SCM_CDR(list)) { | |
804 | SCM elt = SCM_CAR(list); | |
805 | SCM new_tail = scm_cons(SCM_CAR(list), SCM_EOL); | |
00874d5f | 806 | if (scm_is_true (call (pred, elt))) { |
65978fb2 KR |
807 | SCM_SETCDR(kept_tail, new_tail); |
808 | kept_tail = new_tail; | |
809 | } | |
810 | else { | |
811 | SCM_SETCDR(dropped_tail, new_tail); | |
812 | dropped_tail = new_tail; | |
813 | } | |
814 | } | |
815 | /* re-use the initial conses for the values list */ | |
816 | SCM_SETCAR(kept, SCM_CDR(kept)); | |
817 | SCM_SETCDR(kept, dropped); | |
818 | SCM_SETCAR(dropped, SCM_CDR(dropped)); | |
819 | SCM_SETCDR(dropped, SCM_EOL); | |
820 | return scm_values(kept); | |
821 | } | |
822 | #undef FUNC_NAME | |
823 | ||
59747b8d KR |
824 | SCM_DEFINE (scm_srfi1_remove, "remove", 2, 0, 0, |
825 | (SCM pred, SCM list), | |
826 | "Return a list containing all elements from @var{lst} which do\n" | |
827 | "not satisfy the predicate @var{pred}. The elements in the\n" | |
828 | "result list have the same order as in @var{lst}. The order in\n" | |
829 | "which @var{pred} is applied to the list elements is not\n" | |
830 | "specified.") | |
831 | #define FUNC_NAME s_scm_srfi1_remove | |
832 | { | |
833 | scm_t_trampoline_1 call = scm_trampoline_1 (pred); | |
834 | SCM walk; | |
835 | SCM *prev; | |
836 | SCM res = SCM_EOL; | |
837 | SCM_ASSERT (call, pred, 1, FUNC_NAME); | |
838 | SCM_VALIDATE_LIST (2, list); | |
839 | ||
840 | for (prev = &res, walk = list; | |
841 | scm_is_pair (walk); | |
842 | walk = SCM_CDR (walk)) | |
843 | { | |
844 | if (scm_is_false (call (pred, SCM_CAR (walk)))) | |
845 | { | |
846 | *prev = scm_cons (SCM_CAR (walk), SCM_EOL); | |
847 | prev = SCM_CDRLOC (*prev); | |
848 | } | |
849 | } | |
850 | ||
851 | return res; | |
852 | } | |
853 | #undef FUNC_NAME | |
854 | ||
ee6aac97 MD |
855 | void |
856 | scm_init_srfi_1 (void) | |
857 | { | |
a48d60b1 | 858 | SCM the_root_module = scm_lookup_closure_module (SCM_BOOL_F); |
ee6aac97 MD |
859 | #ifndef SCM_MAGIC_SNARFER |
860 | #include "srfi/srfi-1.x" | |
861 | #endif | |
a48d60b1 MD |
862 | scm_c_extend_primitive_generic |
863 | (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module, "map")), | |
864 | SCM_VARIABLE_REF (scm_c_lookup ("map"))); | |
865 | scm_c_extend_primitive_generic | |
866 | (SCM_VARIABLE_REF (scm_c_module_lookup (the_root_module, "for-each")), | |
867 | SCM_VARIABLE_REF (scm_c_lookup ("for-each"))); | |
ee6aac97 MD |
868 | } |
869 | ||
870 | /* End of srfi-1.c. */ |