[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/JRWWLoi1    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Aug 14:
; 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)


Output:
1
2
3
4
5
6
7
8
9
#0=(1 . #0#)
#0=(1 1 . #0#)
#0=(1 2 . #0#)
#0=(2 1 . #0#)
#0=(1 2 3 . #0#)
#0=(1 1 1 . #0#)
#0=(1 2 1 . #0#)
#0=(2 1 2 . #0#)
#0=(3 4 5 1 2 . #0#)


Create a new paste based on this one


Comments: