; insert into a sorted cyclic list
(define (last-pair xs)
(if (null? (cdr xs)) xs
(last-pair (cdr xs))))
(define (cycle . xs)
(set-cdr! (last-pair xs) xs) xs)
(define (ins-cycle xs x)
(if (null? xs) (cycle x) ; possibility 1
(let loop ((prev xs) (next (cdr xs)))
(cond ((<= (car prev) x (car next)) ; possibility 2
(set-cdr! prev (cons x next)) prev)
((and (<= (car next) (car prev)) ; possibility 3
(or (<= x (car next)) (<= (car prev) x)))
(set-cdr! prev (cons x next)) prev)
((eqv? next xs) ; possibility 4
(set-cdr! prev (cons x next)) prev)
(else (loop next (cdr next)))))))
(display (ins-cycle '() 1)) (newline)
(display (ins-cycle (cycle 1) 1)) (newline)
(display (ins-cycle (cycle 1) 2)) (newline)
(display (ins-cycle (cycle 2) 1)) (newline)
(display (ins-cycle (cycle 1 3) 2)) (newline)
(display (ins-cycle (cycle 1 1) 1)) (newline)
(display (ins-cycle (cycle 1 1) 2)) (newline)
(display (ins-cycle (cycle 2 2) 1)) (newline)
(display (ins-cycle (cycle 1 2 3 5) 4)) (newline)