23.12 Utilities for sorted lists

Function: sorted-list-insert obj ell item>

Build a new list holding the same arguments of ell, a list sorted in increasing order, and obj inserted in such a position that the order is preserved. The returned list may share structure with ell.

item> must be a predicate accepting two arguments and returning true if the first is greater than the second. If obj is equal to one of the items in ell: obj is added before the item from ell.

Function: sorted-list-insert/uniq obj ell item< item>

Like sorted-list-insert, but if obj is equal to one of the items in ell: obj is discarded, and ell it self is returned.

Function: union-of-sorted-lists ell1 ell2 item< item>

Build a new list representing the union of the lists arguments. ell1 and ell2 are interpreted as lists sorted in increasing order, and the result of the union is a sorted list. The returned list may share structure with the list arguments.

item< and item> must be predicates accepting two arguments and returning true if the first is less than/greater than the second.

When both item< and item> return #f, the two items are considered equal; in this case all the equal items are added to the result, in such a way that the items from ell1 all come before the items from ell2.

Function: union-of-sorted-lists/uniq ell1 ell2 item< item>

Like union-of-sorted-lists, but when equal items are found only the ones from ell1 are added to the result.

(union-of-sorted-lists/uniq
  '(0 1   3     8 9 10)
  '(  1 2   4 5        11 23)
  < >)
⇒ '(0 1 2 3 4 5 8 9 10 11 23)
;;     ^
;; from ell1

(union-of-sorted-lists/uniq
  '(0 1 1   3)
  '(  1   2   4)
  < >)
⇒ '(0 1 1 2 3 4 5)
;;     ^ ^
;; both from ell1