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