; array manipulation (define (min-gt x xs) (let ((gt (filter (lambda (n) (< x n)) xs))) (if (null? gt) -1 (apply min gt)))) (define (repl-min-gt xs) (if (null? xs) (list) (cons (min-gt (car xs) (cdr xs)) (repl-min-gt (cdr xs))))) (display (repl-min-gt '(8 58 71 18 31 32 63 92 43 3 91 93 25 80 28))) (newline) (define (tree key lkid rkid) (vector key lkid rkid)) (define (key tree) (vector-ref tree 0)) (define (lkid tree) (vector-ref tree 1)) (define (rkid tree) (vector-ref tree 2)) (define nil (vector 'nil 'nil 'nil)) (vector-set! nil 1 nil) (vector-set! nil 2 nil) (define (nil? tree) (eqv? tree nil)) (define (insert lt? t k) (cond ((nil? t) (tree k nil nil)) ((lt? k (key t)) (tree (key t) (insert lt? (lkid t) k) (rkid t))) ((lt? (key t) k) (tree (key t) (lkid t) (insert lt? (rkid t) k))) (else t))) (define (minimum t) (cond ((nil? t) #f) ((nil? (lkid t)) (key t)) (else (minimum (lkid t))))) (define (maximum t) (cond ((nil? t) #f) ((nil? (rkid t)) (key t)) (else (maximum (rkid t))))) (define (pred lt? t k) (define (return t) (if (nil? t) #f (key t))) (let loop ((t t) (prev nil)) (cond ((nil? t) (return prev)) ((lt? (key t) k) (loop (rkid t) t)) ((lt? k (key t)) (loop (lkid t) prev)) ((nil? (lkid t)) (return prev)) (else (maximum (lkid t)))))) (define (succ lt? t k) (define (return t) (if (nil? t) #f (key t))) (let loop ((t t) (next nil)) (cond ((nil? t) (return next)) ((lt? k (key t)) (loop (lkid t) t)) ((lt? (key t) k) (loop (rkid t) next)) ((nil? (rkid t)) (return next)) (else (minimum (rkid t)))))) (define (repl-min-gt xs) (let loop ((xs (reverse xs)) (t nil) (zs (list))) (cond ((null? xs) zs) ((succ < t (car xs)) => (lambda (x) (loop (cdr xs) (insert < t (car xs)) (cons x zs)))) (else (loop (cdr xs) (insert < t (car xs)) (cons -1 zs)))))) (display (repl-min-gt '(8 58 71 18 31 32 63 92 43 3 91 93 25 80 28))) (newline)