srfi-1.c 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886
  1. /* srfi-1.c --- SRFI-1 procedures for Guile
  2. Copyright 1995-1997,2000-2003,2005-2006,2008-2011,2013-2014,2018,2020
  3. Free Software Foundation, Inc.
  4. This file is part of Guile.
  5. Guile is free software: you can redistribute it and/or modify it
  6. under the terms of the GNU Lesser General Public License as published
  7. by the Free Software Foundation, either version 3 of the License, or
  8. (at your option) any later version.
  9. Guile is distributed in the hope that it will be useful, but WITHOUT
  10. ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11. FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
  12. License for more details.
  13. You should have received a copy of the GNU Lesser General Public
  14. License along with Guile. If not, see
  15. <https://www.gnu.org/licenses/>. */
  16. #ifdef HAVE_CONFIG_H
  17. # include <config.h>
  18. #endif
  19. #include <stdarg.h>
  20. #include "boolean.h"
  21. #include "eq.h"
  22. #include "eval.h"
  23. #include "extensions.h"
  24. #include "gsubr.h"
  25. #include "list.h"
  26. #include "pairs.h"
  27. #include "procs.h"
  28. #include "values.h"
  29. #include "vectors.h"
  30. #include "version.h"
  31. #include "srfi-1.h"
  32. /* The intent of this file was to gradually replace those Scheme
  33. * procedures in srfi-1.scm that extend core primitive procedures,
  34. * so that using srfi-1 wouldn't have performance penalties.
  35. *
  36. * However, we now prefer to write these procedures in Scheme, let the compiler
  37. * optimize them, and have the VM execute them efficiently.
  38. */
  39. static SCM
  40. equal_trampoline (SCM proc, SCM arg1, SCM arg2)
  41. {
  42. return scm_equal_p (arg1, arg2);
  43. }
  44. /* list_copy_part() copies the first COUNT cells of LST, puts the result at
  45. *dst, and returns the SCM_CDRLOC of the last cell in that new list.
  46. This function is designed to be careful about LST possibly having changed
  47. in between the caller deciding what to copy, and the copy actually being
  48. done here. The COUNT ensures we terminate if LST has become circular,
  49. SCM_VALIDATE_CONS guards against a cdr in the list changed to some
  50. non-pair object. */
  51. #include <stdio.h>
  52. static SCM *
  53. list_copy_part (SCM lst, int count, SCM *dst)
  54. #define FUNC_NAME "list_copy_part"
  55. {
  56. SCM c;
  57. for ( ; count > 0; count--)
  58. {
  59. SCM_VALIDATE_CONS (SCM_ARGn, lst);
  60. c = scm_cons (SCM_CAR (lst), SCM_EOL);
  61. *dst = c;
  62. dst = SCM_CDRLOC (c);
  63. lst = SCM_CDR (lst);
  64. }
  65. return dst;
  66. }
  67. #undef FUNC_NAME
  68. SCM_DEFINE (scm_srfi1_append_reverse, "append-reverse", 2, 0, 0,
  69. (SCM revhead, SCM tail),
  70. "Reverse @var{rev-head}, append @var{tail} to it, and return the\n"
  71. "result. This is equivalent to @code{(append (reverse\n"
  72. "@var{rev-head}) @var{tail})}, but its implementation is more\n"
  73. "efficient.\n"
  74. "\n"
  75. "@example\n"
  76. "(append-reverse '(1 2 3) '(4 5 6)) @result{} (3 2 1 4 5 6)\n"
  77. "@end example")
  78. #define FUNC_NAME s_scm_srfi1_append_reverse
  79. {
  80. while (scm_is_pair (revhead))
  81. {
  82. /* copy first element of revhead onto front of tail */
  83. tail = scm_cons (SCM_CAR (revhead), tail);
  84. revhead = SCM_CDR (revhead);
  85. }
  86. SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (revhead), revhead, SCM_ARG1, FUNC_NAME,
  87. "list");
  88. return tail;
  89. }
  90. #undef FUNC_NAME
  91. SCM_DEFINE (scm_srfi1_append_reverse_x, "append-reverse!", 2, 0, 0,
  92. (SCM revhead, SCM tail),
  93. "Reverse @var{rev-head}, append @var{tail} to it, and return the\n"
  94. "result. This is equivalent to @code{(append! (reverse!\n"
  95. "@var{rev-head}) @var{tail})}, but its implementation is more\n"
  96. "efficient.\n"
  97. "\n"
  98. "@example\n"
  99. "(append-reverse! (list 1 2 3) '(4 5 6)) @result{} (3 2 1 4 5 6)\n"
  100. "@end example\n"
  101. "\n"
  102. "@var{rev-head} may be modified in order to produce the result.")
  103. #define FUNC_NAME s_scm_srfi1_append_reverse_x
  104. {
  105. SCM newtail;
  106. while (scm_is_mutable_pair (revhead))
  107. {
  108. /* take the first cons cell from revhead */
  109. newtail = revhead;
  110. revhead = SCM_CDR (revhead);
  111. /* make it the new start of tail, appending the previous */
  112. SCM_SETCDR (newtail, tail);
  113. tail = newtail;
  114. }
  115. SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (revhead), revhead, SCM_ARG1, FUNC_NAME,
  116. "list");
  117. return tail;
  118. }
  119. #undef FUNC_NAME
  120. SCM_DEFINE (scm_srfi1_concatenate, "concatenate", 1, 0, 0,
  121. (SCM lstlst),
  122. "Construct a list by appending all lists in @var{lstlst}.\n"
  123. "\n"
  124. "@code{concatenate} is the same as @code{(apply append\n"
  125. "@var{lstlst})}. It exists because some Scheme implementations\n"
  126. "have a limit on the number of arguments a function takes, which\n"
  127. "the @code{apply} might exceed. In Guile there is no such\n"
  128. "limit.")
  129. #define FUNC_NAME s_scm_srfi1_concatenate
  130. {
  131. SCM_VALIDATE_LIST (SCM_ARG1, lstlst);
  132. return scm_append (lstlst);
  133. }
  134. #undef FUNC_NAME
  135. SCM_DEFINE (scm_srfi1_concatenate_x, "concatenate!", 1, 0, 0,
  136. (SCM lstlst),
  137. "Construct a list by appending all lists in @var{lstlst}. Those\n"
  138. "lists may be modified to produce the result.\n"
  139. "\n"
  140. "@code{concatenate!} is the same as @code{(apply append!\n"
  141. "@var{lstlst})}. It exists because some Scheme implementations\n"
  142. "have a limit on the number of arguments a function takes, which\n"
  143. "the @code{apply} might exceed. In Guile there is no such\n"
  144. "limit.")
  145. #define FUNC_NAME s_scm_srfi1_concatenate_x
  146. {
  147. SCM_VALIDATE_LIST (SCM_ARG1, lstlst);
  148. return scm_append_x (lstlst);
  149. }
  150. #undef FUNC_NAME
  151. SCM_DEFINE (scm_srfi1_count, "count", 2, 0, 1,
  152. (SCM pred, SCM list1, SCM rest),
  153. "Return a count of the number of times @var{pred} returns true\n"
  154. "when called on elements from the given lists.\n"
  155. "\n"
  156. "@var{pred} is called with @var{N} parameters @code{(@var{pred}\n"
  157. "@var{elem1} @dots{} @var{elemN})}, each element being from the\n"
  158. "corresponding @var{list1} @dots{} @var{lstN}. The first call is\n"
  159. "with the first element of each list, the second with the second\n"
  160. "element from each, and so on.\n"
  161. "\n"
  162. "Counting stops when the end of the shortest list is reached.\n"
  163. "At least one list must be non-circular.")
  164. #define FUNC_NAME s_scm_srfi1_count
  165. {
  166. long count;
  167. SCM lst;
  168. int argnum;
  169. SCM_VALIDATE_REST_ARGUMENT (rest);
  170. count = 0;
  171. if (scm_is_null (rest))
  172. {
  173. /* one list */
  174. SCM_ASSERT (scm_is_true (scm_procedure_p (pred)), pred, SCM_ARG1, FUNC_NAME);
  175. for ( ; scm_is_pair (list1); list1 = SCM_CDR (list1))
  176. count += scm_is_true (scm_call_1 (pred, SCM_CAR (list1)));
  177. /* check below that list1 is a proper list, and done */
  178. end_list1:
  179. lst = list1;
  180. argnum = 2;
  181. }
  182. else if (scm_is_pair (rest) && scm_is_null (SCM_CDR (rest)))
  183. {
  184. /* two lists */
  185. SCM list2;
  186. SCM_ASSERT (scm_is_true (scm_procedure_p (pred)), pred, SCM_ARG1, FUNC_NAME);
  187. list2 = SCM_CAR (rest);
  188. for (;;)
  189. {
  190. if (! scm_is_pair (list1))
  191. goto end_list1;
  192. if (! scm_is_pair (list2))
  193. {
  194. lst = list2;
  195. argnum = 3;
  196. break;
  197. }
  198. count += scm_is_true (scm_call_2
  199. (pred, SCM_CAR (list1), SCM_CAR (list2)));
  200. list1 = SCM_CDR (list1);
  201. list2 = SCM_CDR (list2);
  202. }
  203. }
  204. else
  205. {
  206. /* three or more lists */
  207. SCM vec, args, a;
  208. size_t len, i;
  209. /* vec is the list arguments */
  210. vec = scm_vector (scm_cons (list1, rest));
  211. len = SCM_SIMPLE_VECTOR_LENGTH (vec);
  212. /* args is the argument list to pass to pred, same length as vec,
  213. re-used for each call */
  214. args = scm_make_list (SCM_I_MAKINUM (len), SCM_UNDEFINED);
  215. for (;;)
  216. {
  217. /* first elem of each list in vec into args, and step those
  218. vec entries onto their next element */
  219. for (i = 0, a = args, argnum = 2;
  220. i < len;
  221. i++, a = SCM_CDR (a), argnum++)
  222. {
  223. lst = SCM_SIMPLE_VECTOR_REF (vec, i); /* list argument */
  224. if (! scm_is_pair (lst))
  225. goto check_lst_and_done;
  226. SCM_SETCAR (a, SCM_CAR (lst)); /* arg for pred */
  227. SCM_SIMPLE_VECTOR_SET (vec, i, SCM_CDR (lst)); /* rest of lst */
  228. }
  229. count += scm_is_true (scm_apply_0 (pred, args));
  230. }
  231. }
  232. check_lst_and_done:
  233. SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, argnum, FUNC_NAME, "list");
  234. return scm_from_long (count);
  235. }
  236. #undef FUNC_NAME
  237. SCM_DEFINE (scm_srfi1_delete, "delete", 2, 1, 0,
  238. (SCM x, SCM lst, SCM pred),
  239. "Return a list containing the elements of @var{lst} but with\n"
  240. "those equal to @var{x} deleted. The returned elements will be\n"
  241. "in the same order as they were in @var{lst}.\n"
  242. "\n"
  243. "Equality is determined by @var{pred}, or @code{equal?} if not\n"
  244. "given. An equality call is made just once for each element,\n"
  245. "but the order in which the calls are made on the elements is\n"
  246. "unspecified.\n"
  247. "\n"
  248. "The equality calls are always @code{(pred x elem)}, ie.@: the\n"
  249. "given @var{x} is first. This means for instance elements\n"
  250. "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n"
  251. "\n"
  252. "@var{lst} is not modified, but the returned list might share a\n"
  253. "common tail with @var{lst}.")
  254. #define FUNC_NAME s_scm_srfi1_delete
  255. {
  256. SCM ret, *p, keeplst;
  257. int count;
  258. if (SCM_UNBNDP (pred))
  259. return scm_delete (x, lst);
  260. SCM_ASSERT (scm_is_true (scm_procedure_p (pred)), pred, SCM_ARG3, FUNC_NAME);
  261. /* ret is the return list being constructed. p is where to append to it,
  262. initially &ret then SCM_CDRLOC of the last pair. lst progresses as
  263. elements are considered.
  264. Elements to be retained are not immediately copied, instead keeplst is
  265. the last pair in lst which is to be retained but not yet copied, count
  266. is how many from there are wanted. When there's no more deletions, *p
  267. can be set to keeplst to share the remainder of the original lst. (The
  268. entire original lst if there's no deletions at all.) */
  269. keeplst = lst;
  270. count = 0;
  271. p = &ret;
  272. for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
  273. {
  274. if (scm_is_true (scm_call_2 (pred, x, SCM_CAR (lst))))
  275. {
  276. /* delete this element, so copy those at keeplst */
  277. p = list_copy_part (keeplst, count, p);
  278. keeplst = SCM_CDR (lst);
  279. count = 0;
  280. }
  281. else
  282. {
  283. /* keep this element */
  284. count++;
  285. }
  286. }
  287. /* final retained elements */
  288. *p = keeplst;
  289. /* demand that lst was a proper list */
  290. SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
  291. return ret;
  292. }
  293. #undef FUNC_NAME
  294. SCM_DEFINE (scm_srfi1_delete_x, "delete!", 2, 1, 0,
  295. (SCM x, SCM lst, SCM pred),
  296. "Return a list containing the elements of @var{lst} but with\n"
  297. "those equal to @var{x} deleted. The returned elements will be\n"
  298. "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. An equality call is made just once for each element,\n"
  302. "but the order in which the calls are made on the elements is\n"
  303. "unspecified.\n"
  304. "\n"
  305. "The equality calls are always @code{(pred x elem)}, ie.@: the\n"
  306. "given @var{x} is first. This means for instance elements\n"
  307. "greater than 5 can be deleted with @code{(delete 5 lst <)}.\n"
  308. "\n"
  309. "@var{lst} may be modified to construct the returned list.")
  310. #define FUNC_NAME s_scm_srfi1_delete_x
  311. {
  312. SCM walk;
  313. SCM *prev;
  314. if (SCM_UNBNDP (pred))
  315. return scm_delete_x (x, lst);
  316. SCM_ASSERT (scm_is_true (scm_procedure_p (pred)), pred, SCM_ARG3, FUNC_NAME);
  317. for (prev = &lst, walk = lst;
  318. scm_is_pair (walk);
  319. walk = SCM_CDR (walk))
  320. {
  321. if (scm_is_true (scm_call_2 (pred, x, SCM_CAR (walk))))
  322. *prev = SCM_CDR (walk);
  323. else
  324. prev = SCM_CDRLOC (walk);
  325. }
  326. /* demand the input was a proper list */
  327. SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (walk), walk, SCM_ARG2, FUNC_NAME,"list");
  328. return lst;
  329. }
  330. #undef FUNC_NAME
  331. SCM_DEFINE (scm_srfi1_delete_duplicates, "delete-duplicates", 1, 1, 0,
  332. (SCM lst, SCM pred),
  333. "Return a list containing the elements of @var{lst} but without\n"
  334. "duplicates.\n"
  335. "\n"
  336. "When elements are equal, only the first in @var{lst} is\n"
  337. "retained. Equal elements can be anywhere in @var{lst}, they\n"
  338. "don't have to be adjacent. The returned list will have the\n"
  339. "retained elements in the same order as they were in @var{lst}.\n"
  340. "\n"
  341. "Equality is determined by @var{pred}, or @code{equal?} if not\n"
  342. "given. Calls @code{(pred x y)} are made with element @var{x}\n"
  343. "being before @var{y} in @var{lst}. A call is made at most once\n"
  344. "for each combination, but the sequence of the calls across the\n"
  345. "elements is unspecified.\n"
  346. "\n"
  347. "@var{lst} is not modified, but the return might share a common\n"
  348. "tail with @var{lst}.\n"
  349. "\n"
  350. "In the worst case, this is an @math{O(N^2)} algorithm because\n"
  351. "it must check each element against all those preceding it. For\n"
  352. "long lists it is more efficient to sort and then compare only\n"
  353. "adjacent elements.")
  354. #define FUNC_NAME s_scm_srfi1_delete_duplicates
  355. {
  356. scm_t_trampoline_2 equal_p;
  357. SCM ret, *p, keeplst, item, l;
  358. int count, i;
  359. /* ret is the new list constructed. p is where to append, initially &ret
  360. then SCM_CDRLOC of the last pair. lst is advanced as each element is
  361. considered.
  362. Elements retained are not immediately appended to ret, instead keeplst
  363. is the last pair in lst which is to be kept but is not yet copied.
  364. Initially this is the first pair of lst, since the first element is
  365. always retained.
  366. *p is kept set to keeplst, so ret (inclusive) to lst (exclusive) is all
  367. the elements retained, making the equality search loop easy.
  368. If an item must be deleted, elements from keeplst (inclusive) to lst
  369. (exclusive) must be copied and appended to ret. When there's no more
  370. deletions, *p is left set to keeplst, so ret shares structure with the
  371. original lst. (ret will be the entire original lst if there are no
  372. deletions.) */
  373. /* skip to end if an empty list (or something invalid) */
  374. ret = SCM_EOL;
  375. if (SCM_UNBNDP (pred))
  376. equal_p = equal_trampoline;
  377. else
  378. {
  379. SCM_VALIDATE_PROC (SCM_ARG2, pred);
  380. equal_p = scm_call_2;
  381. }
  382. keeplst = lst;
  383. count = 0;
  384. p = &ret;
  385. for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
  386. {
  387. item = SCM_CAR (lst);
  388. /* look for item in "ret" list */
  389. for (l = ret; scm_is_pair (l); l = SCM_CDR (l))
  390. {
  391. if (scm_is_true (equal_p (pred, SCM_CAR (l), item)))
  392. {
  393. /* "item" is a duplicate, so copy keeplst onto ret */
  394. duplicate:
  395. p = list_copy_part (keeplst, count, p);
  396. keeplst = SCM_CDR (lst); /* elem after the one deleted */
  397. count = 0;
  398. goto next_elem;
  399. }
  400. }
  401. /* look for item in "keeplst" list
  402. be careful traversing, in case nasty code changed the cdrs */
  403. for (i = 0, l = keeplst;
  404. i < count && scm_is_pair (l);
  405. i++, l = SCM_CDR (l))
  406. if (scm_is_true (equal_p (pred, SCM_CAR (l), item)))
  407. goto duplicate;
  408. /* keep this element */
  409. count++;
  410. next_elem:
  411. ;
  412. }
  413. SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list");
  414. /* share tail of keeplst items */
  415. *p = keeplst;
  416. return ret;
  417. }
  418. #undef FUNC_NAME
  419. SCM_DEFINE (scm_srfi1_delete_duplicates_x, "delete-duplicates!", 1, 1, 0,
  420. (SCM lst, SCM pred),
  421. "Return a list containing the elements of @var{lst} but without\n"
  422. "duplicates.\n"
  423. "\n"
  424. "When elements are equal, only the first in @var{lst} is\n"
  425. "retained. Equal elements can be anywhere in @var{lst}, they\n"
  426. "don't have to be adjacent. The returned list will have the\n"
  427. "retained elements in the same order as they were in @var{lst}.\n"
  428. "\n"
  429. "Equality is determined by @var{pred}, or @code{equal?} if not\n"
  430. "given. Calls @code{(pred x y)} are made with element @var{x}\n"
  431. "being before @var{y} in @var{lst}. A call is made at most once\n"
  432. "for each combination, but the sequence of the calls across the\n"
  433. "elements is unspecified.\n"
  434. "\n"
  435. "@var{lst} may be modified to construct the returned list.\n"
  436. "\n"
  437. "In the worst case, this is an @math{O(N^2)} algorithm because\n"
  438. "it must check each element against all those preceding it. For\n"
  439. "long lists it is more efficient to sort and then compare only\n"
  440. "adjacent elements.")
  441. #define FUNC_NAME s_scm_srfi1_delete_duplicates_x
  442. {
  443. scm_t_trampoline_2 equal_p;
  444. SCM ret, endret, item, l;
  445. /* ret is the return list, constructed from the pairs in lst. endret is
  446. the last pair of ret, initially the first pair. lst is advanced as
  447. elements are considered. */
  448. /* skip to end if an empty list (or something invalid) */
  449. ret = lst;
  450. if (scm_is_pair (lst))
  451. {
  452. if (SCM_UNBNDP (pred))
  453. equal_p = equal_trampoline;
  454. else
  455. {
  456. SCM_VALIDATE_PROC (SCM_ARG2, pred);
  457. equal_p = scm_call_2;
  458. }
  459. endret = ret;
  460. /* loop over lst elements starting from second */
  461. for (;;)
  462. {
  463. lst = SCM_CDR (lst);
  464. if (! scm_is_pair (lst))
  465. break;
  466. item = SCM_CAR (lst);
  467. /* is item equal to any element from ret to endret (inclusive)? */
  468. l = ret;
  469. for (;;)
  470. {
  471. if (scm_is_true (equal_p (pred, SCM_CAR (l), item)))
  472. break; /* equal, forget this element */
  473. if (scm_is_eq (l, endret))
  474. {
  475. /* not equal to any, so append this pair */
  476. scm_set_cdr_x (endret, lst);
  477. endret = lst;
  478. break;
  479. }
  480. l = SCM_CDR (l);
  481. }
  482. }
  483. /* terminate, in case last element was deleted */
  484. scm_set_cdr_x (endret, SCM_EOL);
  485. }
  486. /* demand that lst was a proper list */
  487. SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG1, FUNC_NAME, "list");
  488. return ret;
  489. }
  490. #undef FUNC_NAME
  491. SCM_DEFINE (scm_srfi1_length_plus, "length+", 1, 0, 0,
  492. (SCM lst),
  493. "Return the length of @var{lst}, or @code{#f} if @var{lst} is\n"
  494. "circular.")
  495. #define FUNC_NAME s_scm_srfi1_length_plus
  496. {
  497. size_t i = 0;
  498. SCM tortoise = lst;
  499. SCM hare = lst;
  500. do
  501. {
  502. if (!scm_is_pair (hare))
  503. {
  504. if (SCM_NULL_OR_NIL_P (hare))
  505. return scm_from_size_t (i);
  506. else
  507. scm_wrong_type_arg_msg (FUNC_NAME, 1, lst,
  508. "proper or circular list");
  509. }
  510. hare = SCM_CDR (hare);
  511. i++;
  512. if (!scm_is_pair (hare))
  513. {
  514. if (SCM_NULL_OR_NIL_P (hare))
  515. return scm_from_size_t (i);
  516. else
  517. scm_wrong_type_arg_msg (FUNC_NAME, 1, lst,
  518. "proper or circular list");
  519. }
  520. hare = SCM_CDR (hare);
  521. i++;
  522. /* For every two steps the hare takes, the tortoise takes one. */
  523. tortoise = SCM_CDR (tortoise);
  524. }
  525. while (!scm_is_eq (hare, tortoise));
  526. /* If the tortoise ever catches the hare, then the list must contain
  527. a cycle. */
  528. return SCM_BOOL_F;
  529. }
  530. #undef FUNC_NAME
  531. /* This routine differs from the core list-copy in allowing improper lists.
  532. Maybe the core could allow them similarly. */
  533. SCM_DEFINE (scm_srfi1_list_copy, "list-copy", 1, 0, 0,
  534. (SCM lst),
  535. "Return a copy of the given list @var{lst}.\n"
  536. "\n"
  537. "@var{lst} can be a proper or improper list. And if @var{lst}\n"
  538. "is not a pair then it's treated as the final tail of an\n"
  539. "improper list and simply returned.")
  540. #define FUNC_NAME s_scm_srfi1_list_copy
  541. {
  542. SCM newlst;
  543. SCM * fill_here;
  544. SCM from_here;
  545. newlst = lst;
  546. fill_here = &newlst;
  547. from_here = lst;
  548. while (scm_is_pair (from_here))
  549. {
  550. SCM c;
  551. c = scm_cons (SCM_CAR (from_here), SCM_CDR (from_here));
  552. *fill_here = c;
  553. fill_here = SCM_CDRLOC (c);
  554. from_here = SCM_CDR (from_here);
  555. }
  556. return newlst;
  557. }
  558. #undef FUNC_NAME
  559. SCM_DEFINE (scm_srfi1_lset_difference_x, "lset-difference!", 2, 0, 1,
  560. (SCM equal, SCM lst, SCM rest),
  561. "Return @var{lst} with any elements in the lists in @var{rest}\n"
  562. "removed (ie.@: subtracted). For only one @var{lst} argument,\n"
  563. "just that list is returned.\n"
  564. "\n"
  565. "The given @var{equal} procedure is used for comparing elements,\n"
  566. "called as @code{(@var{equal} elem1 elemN)}. The first argument\n"
  567. "is from @var{lst} and the second from one of the subsequent\n"
  568. "lists. But exactly which calls are made and in what order is\n"
  569. "unspecified.\n"
  570. "\n"
  571. "@example\n"
  572. "(lset-difference! eqv? (list 'x 'y)) @result{} (x y)\n"
  573. "(lset-difference! eqv? (list 1 2 3) '(3 1)) @result{} (2)\n"
  574. "(lset-difference! eqv? (list 1 2 3) '(3) '(2)) @result{} (1)\n"
  575. "@end example\n"
  576. "\n"
  577. "@code{lset-difference!} may modify @var{lst} to form its\n"
  578. "result.")
  579. #define FUNC_NAME s_scm_srfi1_lset_difference_x
  580. {
  581. SCM ret, *pos, elem, r, b;
  582. int argnum;
  583. SCM_VALIDATE_PROC (SCM_ARG1, equal);
  584. SCM_VALIDATE_REST_ARGUMENT (rest);
  585. ret = SCM_EOL;
  586. pos = &ret;
  587. for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
  588. {
  589. elem = SCM_CAR (lst);
  590. for (r = rest, argnum = SCM_ARG3;
  591. scm_is_pair (r);
  592. r = SCM_CDR (r), argnum++)
  593. {
  594. for (b = SCM_CAR (r); scm_is_pair (b); b = SCM_CDR (b))
  595. if (scm_is_true (scm_call_2 (equal, elem, SCM_CAR (b))))
  596. goto next_elem; /* equal to elem, so drop that elem */
  597. SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (b), b, argnum, FUNC_NAME,"list");
  598. }
  599. /* elem not equal to anything in later lists, so keep it */
  600. *pos = lst;
  601. pos = SCM_CDRLOC (lst);
  602. next_elem:
  603. ;
  604. }
  605. SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
  606. *pos = SCM_EOL;
  607. return ret;
  608. }
  609. #undef FUNC_NAME
  610. SCM_DEFINE (scm_srfi1_partition, "partition", 2, 0, 0,
  611. (SCM pred, SCM list),
  612. "Partition the elements of @var{list} with predicate @var{pred}.\n"
  613. "Return two values: the list of elements satisfying @var{pred} and\n"
  614. "the list of elements @emph{not} satisfying @var{pred}. The order\n"
  615. "of the output lists follows the order of @var{list}. @var{list}\n"
  616. "is not mutated. One of the output lists may share memory with @var{list}.\n")
  617. #define FUNC_NAME s_scm_srfi1_partition
  618. {
  619. /* In this implementation, the output lists don't share memory with
  620. list, because it's probably not worth the effort. */
  621. SCM orig_list = list;
  622. SCM kept = scm_cons(SCM_EOL, SCM_EOL);
  623. SCM kept_tail = kept;
  624. SCM dropped = scm_cons(SCM_EOL, SCM_EOL);
  625. SCM dropped_tail = dropped;
  626. SCM_VALIDATE_PROC (SCM_ARG1, pred);
  627. for (; !SCM_NULL_OR_NIL_P (list); list = SCM_CDR(list)) {
  628. SCM elt, new_tail;
  629. /* Make sure LIST is not a dotted list. */
  630. SCM_ASSERT (scm_is_pair (list), orig_list, SCM_ARG2, FUNC_NAME);
  631. elt = SCM_CAR (list);
  632. new_tail = scm_cons (SCM_CAR (list), SCM_EOL);
  633. if (scm_is_true (scm_call_1 (pred, elt))) {
  634. SCM_SETCDR(kept_tail, new_tail);
  635. kept_tail = new_tail;
  636. }
  637. else {
  638. SCM_SETCDR(dropped_tail, new_tail);
  639. dropped_tail = new_tail;
  640. }
  641. }
  642. return scm_values_2 (SCM_CDR (kept), SCM_CDR (dropped));
  643. }
  644. #undef FUNC_NAME
  645. SCM_DEFINE (scm_srfi1_partition_x, "partition!", 2, 0, 0,
  646. (SCM pred, SCM lst),
  647. "Split @var{lst} into those elements which do and don't satisfy\n"
  648. "the predicate @var{pred}.\n"
  649. "\n"
  650. "The return is two values (@pxref{Multiple Values}), the first\n"
  651. "being a list of all elements from @var{lst} which satisfy\n"
  652. "@var{pred}, the second a list of those which do not.\n"
  653. "\n"
  654. "The elements in the result lists are in the same order as in\n"
  655. "@var{lst} but the order in which the calls @code{(@var{pred}\n"
  656. "elem)} are made on the list elements is unspecified.\n"
  657. "\n"
  658. "@var{lst} may be modified to construct the return lists.")
  659. #define FUNC_NAME s_scm_srfi1_partition_x
  660. {
  661. SCM tlst, flst, *tp, *fp;
  662. SCM_ASSERT (scm_is_true (scm_procedure_p (pred)), pred, SCM_ARG1, FUNC_NAME);
  663. /* tlst and flst are the lists of true and false elements. tp and fp are
  664. where to store to append to them, initially &tlst and &flst, then
  665. SCM_CDRLOC of the last pair in the respective lists. */
  666. tlst = SCM_EOL;
  667. flst = SCM_EOL;
  668. tp = &tlst;
  669. fp = &flst;
  670. for ( ; scm_is_pair (lst); lst = SCM_CDR (lst))
  671. {
  672. if (scm_is_true (scm_call_1 (pred, SCM_CAR (lst))))
  673. {
  674. *tp = lst;
  675. tp = SCM_CDRLOC (lst);
  676. }
  677. else
  678. {
  679. *fp = lst;
  680. fp = SCM_CDRLOC (lst);
  681. }
  682. }
  683. SCM_ASSERT_TYPE (SCM_NULL_OR_NIL_P (lst), lst, SCM_ARG2, FUNC_NAME, "list");
  684. /* terminate whichever didn't get the last element(s) */
  685. *tp = SCM_EOL;
  686. *fp = SCM_EOL;
  687. return scm_values_2 (tlst, flst);
  688. }
  689. #undef FUNC_NAME
  690. SCM_DEFINE (scm_srfi1_remove, "remove", 2, 0, 0,
  691. (SCM pred, SCM list),
  692. "Return a list containing all elements from @var{list} which do\n"
  693. "not satisfy the predicate @var{pred}. The elements in the\n"
  694. "result list have the same order as in @var{list}. The order in\n"
  695. "which @var{pred} is applied to the list elements is not\n"
  696. "specified.")
  697. #define FUNC_NAME s_scm_srfi1_remove
  698. {
  699. SCM walk;
  700. SCM *prev;
  701. SCM res = SCM_EOL;
  702. SCM_VALIDATE_PROC (SCM_ARG1, pred);
  703. SCM_VALIDATE_LIST (2, list);
  704. for (prev = &res, walk = list;
  705. scm_is_pair (walk);
  706. walk = SCM_CDR (walk))
  707. {
  708. if (scm_is_false (scm_call_1 (pred, SCM_CAR (walk))))
  709. {
  710. *prev = scm_cons (SCM_CAR (walk), SCM_EOL);
  711. prev = SCM_CDRLOC (*prev);
  712. }
  713. }
  714. return res;
  715. }
  716. #undef FUNC_NAME
  717. SCM_DEFINE (scm_srfi1_remove_x, "remove!", 2, 0, 0,
  718. (SCM pred, SCM list),
  719. "Return a list containing all elements from @var{list} which do\n"
  720. "not satisfy the predicate @var{pred}. The elements in the\n"
  721. "result list have the same order as in @var{list}. The order in\n"
  722. "which @var{pred} is applied to the list elements is not\n"
  723. "specified. @var{list} may be modified to build the return\n"
  724. "list.")
  725. #define FUNC_NAME s_scm_srfi1_remove_x
  726. {
  727. SCM walk;
  728. SCM *prev;
  729. SCM_VALIDATE_PROC (SCM_ARG1, pred);
  730. SCM_VALIDATE_LIST (2, list);
  731. for (prev = &list, walk = list;
  732. scm_is_pair (walk);
  733. walk = SCM_CDR (walk))
  734. {
  735. if (scm_is_false (scm_call_1 (pred, SCM_CAR (walk))))
  736. prev = SCM_CDRLOC (walk);
  737. else
  738. *prev = SCM_CDR (walk);
  739. }
  740. return list;
  741. }
  742. #undef FUNC_NAME
  743. void
  744. scm_register_srfi_1 (void)
  745. {
  746. scm_c_register_extension ("libguile-" SCM_EFFECTIVE_VERSION,
  747. "scm_init_srfi_1",
  748. (scm_t_extension_init_func)scm_init_srfi_1, NULL);
  749. }
  750. void
  751. scm_init_srfi_1 (void)
  752. {
  753. #ifndef SCM_MAGIC_SNARFER
  754. #include "srfi-1.x"
  755. #endif
  756. }
  757. /* End of srfi-1.c. */