diff options
author | EuAndreh <eu@euandre.org> | 2021-09-10 09:29:30 -0300 |
---|---|---|
committer | EuAndreh <eu@euandre.org> | 2021-09-10 09:29:34 -0300 |
commit | 1f787eb6a51a4ba38f026dc2f4872a92fca1175b (patch) | |
tree | e4a28ec31dde20eb86f910a81784d27b4f468840 /_pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md | |
parent | TODOs.md: Add #task-089dca19-14e2-e1c1-6a47-9af6ab8eb42a (diff) | |
download | euandre.org-1f787eb6a51a4ba38f026dc2f4872a92fca1175b.tar.gz euandre.org-1f787eb6a51a4ba38f026dc2f4872a92fca1175b.tar.xz |
Pastebin: O(n) -> amortized O(1)
Diffstat (limited to '_pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md')
-rw-r--r-- | _pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md | 85 |
1 files changed, 85 insertions, 0 deletions
diff --git a/_pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md b/_pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md new file mode 100644 index 0000000..8cf7ea2 --- /dev/null +++ b/_pastebins/2021-09-03-sicp-persistent-amortized-o1-queue.md @@ -0,0 +1,85 @@ +--- + +title: SICP persistent amortized O(1) queue + +date: 2021-09-03 + +layout: post + +lang: en + +ref: sicp-persistent-amortized-o1-queue + +--- + +```scheme +(define (queue) + (cons '() + '())) + +(define (enqueue x q) + (cons (car q) + (cons x (cdr q)))) + +(define (flush q) + (cons (reverse (cdr q)) + '())) + +(define (dequeue q) + (if (null? (car q)) + (dequeue (flush q)) + (cons (caar q) + (cons (cdar q) + (cdr q))))) + +(define (empty? q) + (and (null? (car q)) + (null? (cdr q)))) + +(define (peek q) + (car (dequeue q))) + +(define (print-queue q) + (define (rec l leading-space?) + (when (not (null? l)) + (when leading-space? + (display " ")) + (display (car l)) + (rec (cdr l) #t))) + + (display "#q(") + (rec (car q) false) + (rec (reverse (cdr q)) (not (null? (car q)))) + (display ")") + (newline)) +``` + +Sample interactive session: +```scheme +scheme@(guile-user)> (define true #t) +scheme@(guile-user)> (define false #f) +scheme@(guile-user)> (define q (queue)) +scheme@(guile-user)> (print-queue q) +#q() +scheme@(guile-user)> (print-queue (enqueue 'a q)) +#q(a) +scheme@(guile-user)> (print-queue q) +#q() +scheme@(guile-user)> (set! q (enqueue 'a q)) +scheme@(guile-user)> (print-queue q) +#q(a) +scheme@(guile-user)> (set! q (enqueue 'e (enqueue 'd (enqueue 'c (enqueue 'b q))))) +scheme@(guile-user)> (print-queue q) +#q(e d c b a) +scheme@(guile-user)> (peek q) +$28 = a +scheme@(guile-user)> (define ret (dequeue q)) +scheme@(guile-user)> (define value (car ret)) +scheme@(guile-user)> (set! q (cdr ret)) +scheme@(guile-user)> value +$29 = a +scheme@(guile-user)> (print-queue q) +#q(b c d e) +scheme@(guile-user)> (print-queue (cdr (dequeue (cdr (dequeue (enqueue 'g (enqueue 'f q))))))) +#q(d e f g) +``` |