[ create a new paste ] login | about

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

programmingpraxis - Scheme, pasted on Jul 26:
; min stack

(define empty (list (list)))

(define (empty? x) (equal? empty x))

(define (push lt? x min-stack)
  (if (empty? min-stack)
      (cons (list x) (list x))
      (cons (cons x (car min-stack))
            (if (lt? x (cadr min-stack))
                (cons x (cdr min-stack))
                (cdr min-stack)))))

(define (top min-stack)
  (if (empty? min-stack)
      (error 'top "empty stack")
      (caar min-stack)))

(define (pop lt? min-stack)
  (if (empty? min-stack)
      (error 'pop "empty stack")
      (cons (cdar min-stack)
            (if (or (lt? (caar min-stack) (cadr min-stack))
                    (lt? (cadr min-stack) (caar min-stack)))
                (cdr min-stack)
                (cddr min-stack)))))

(define (minimum min-stack)
  (if (empty? min-stack)
      (error 'minimum "empty stack")
      (cadr min-stack)))


(define x empty)
(set! x (push < 3 x))
(set! x (push < 4 x))
(set! x (push < 5 x))
(display (top x)) (newline) ; 5
(display (minimum x)) (newline) ; 3
(display x) (newline) ; ((5 4 3) 3)
(set! x (push < 1 x))
(set! x (push < 2 x))
(display (top x)) (newline) ; 2
(display (minimum x)) (newline) ; 1
(display x) (newline) ; ((2 1 5 4 3) 1 3)
(set! x (pop < x))
(set! x (pop < x))
(display x) (newline) ; ((5 4 3) 3)
(set! x (pop < x))
(display (top x)) (newline) ; 4
(display (minimum x)) (newline) ; 3
(set! x (pop < x))
(set! x (pop < x))
(display (empty? x)) (newline) ; #t
(display x) (newline) ; (())


Output:
1
2
3
4
5
6
7
8
9
10
11
5
3
((5 4 3) 3)
2
1
((2 1 5 4 3) 1 3)
((5 4 3) 3)
4
3
#t
(())


Create a new paste based on this one


Comments: