@@ 1,11 1,11 @@
-;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Copyright 2019 Linus Björnstam
;;
;; Permission to use, copy, modify, and/or distribute this software for any
;; purpose with or without fee is hereby granted, provided that the above
;; copyright notice and this permission notice appear in all source copies.
;; The software is provided "as is", without any express or implied warranties.
-;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Yall should check out the following srfis before deciding to use this:
;; srfi-134 (ideques): a generalisation of fifo/lifo that is persistent.
@@ 15,8 15,11 @@
;; srfi-117 (list-queues): a mutable general queue. Could be both fifo and lifo.
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
-;;; A persistent fifo. Enqueue operations are O(1), while dequeue is amortized O(1)
-;; worst case being O(n), which entails a reverse of all enqueued items.
+;;; A persistent fifo. Enqueue operations are O(1), while dequeue is amortized O(1).
+;; It is a simple system of 2 lists, one of items available for dequeue with the next
+;; element to dequeue in it's car. The second list contains enqueued items where the
+;; car being the most recently enqueued. The worst case for a dequeue is then O(n)
+;; which entails a reverse of the enqueued items.
;;
;; pfifo-length, pfifo-merge, pfifo-fold, pfifo-map and pfifo-filter are all O(n)-ish
;; as they just transverse the deq and (reverse enq).
@@ 25,7 28,8 @@
;; homophobes".
(define-module (persistent-fifo)
- #:use-module (srfi srfi-1)
+ #:use-module ((srfi srfi-1)
+ #:select (fold))
#:use-module (srfi srfi-8)
#:use-module (srfi srfi-9)
#:export (pfifo
@@ 34,6 38,8 @@
pfifo-enqueue
pfifo-dequeue
pfifo-dequeue/pair
+ pfifo->list
+ pfifo-merge
pfifo-fold
pfifo-map
pfifo-filter))
@@ 51,6 57,7 @@
(define (pfifo-empty? pfifo)
(and (null? (pfifo-get-deq pfifo)) (null? (pfifo-get-enq pfifo))))
+;; Helper function so that I don't have to do (when (pfifo-empty? pf) ...)
(define (check-pfifo pf)
(when (pfifo-empty? pf)
(error "Pfifo is empty" pf)))
@@ 66,32 73,40 @@
(define new-enq (fold cons enq items))
(%make-pfifo new-enq (pfifo-get-deq pfifo)))
+;; Dequeues an element from the pfifo.
+;; returns 2 values: a new pfifo, the dequeued element.
(define (pfifo-dequeue pfifo)
- (if (pfifo-empty? pfifo)
- (values #f #f)
- (receive (enq deq)
- (if (null? (pfifo-get-deq pfifo))
- (values '() (reverse (pfifo-get-enq pfifo)))
- (values (pfifo-get-enq pfifo) (pfifo-get-deq pfifo)))
- (values (%make-pfifo enq (cdr deq)) (car deq)))))
+ (check-pfifo pfifo)
+ (receive (enq deq)
+ (if (null? (pfifo-get-deq pfifo))
+ (values '() (reverse (pfifo-get-enq pfifo)))
+ (values (pfifo-get-enq pfifo) (pfifo-get-deq pfifo)))
+ (values (%make-pfifo enq (cdr deq)) (car deq))))
(define (pfifo-dequeue/pair pfifo)
(call-with-values (lambda () (pfifo-dequeue pfifo)) cons))
+
+(define (pfifo->list pf)
+ (append (pfifo-get-deq pf) (reverse (pfifo-get-enq pf))))
+
;; Merges the content of p2 into p1, by putting all of the elements in both p1 and p2
;; in a new pfifo's deq. o(n)-ish.
(define (pfifo-merge p1 p2)
(%make-pfifo '() (append (pfifo-get-deq p1) (reverse (pfifo-get-enq p1))
(pfifo-get-deq p2) (reverse (pfifo-get-deq p2)))))
+
(define (pfifo-fold proc identity pf)
(define first-round (fold proc identity (pfifo-get-deq pf)))
(fold proc first-round (reverse (pfifo-get-enq pf))))
+
(define (pfifo-map proc pf)
(check-pfifo pf)
(%make-pfifo '() (reverse (pfifo-fold (lambda (x acc) (cons (proc x) acc)) '() pf))))
+
(define (pfifo-filter pred pf)
(check-pfifo pf)
(%make-pfifo '() (reverse (pfifo-fold (lambda (x acc) (if (pred x) (cons x acc) acc)) '() pf))))