On Thu, Feb 3, 2011 at 2:03 PM, Alan <a...@malloys.org> wrote:
> Or use a fixed-size vector as a ring, with start and end "pointers",
> and a couple functions to abstract over the handling thereof. But
> unless you really really care about performance, this is likely to be
> overkill, and Ken's suggestion to just use a vector or a seq and
> accept the O(n) behavior.
A ring buffer. I considered using one to implement a deque, but
resizing it presented severe technical difficulties so I shelved that
approach. But for a fixed-size one it's perfect.
Below is a persistent immutable ring buffer implementation using
deftype. It behaves as a vector that accepts lpeek, lpop, and lconj
acting on the left as well as peek, pop, and conj acting on the right
and has a maximum capacity. Adding at either end when it is at
capacity causes it to drop an element at the other end. The assoc,
nth, and so forth functions work, but the index of a given element
changes if elements are dropped or added at the left end; assoc
accepts index -1 which adds at the left end, as well as index count
which adds at the right, an extension of how assoc can be used to grow
a vector at the right.
Create one with (ringbuffer capacity item item item ...), or just
(ringbuffer capacity) to get an empty one. The empty function produces
an empty ringbuffer with the same capacity as the argument ringbuffer,
so the capacity of (empty (ringbuffer 5 1 2 3 4 5)) will be 5.
I've tested it somewhat and it seems to work correctly. Let me know if
you use it, and especially if you run into any bugs.
Implementation note: internally there is a vector with a size one
greater than capacity (otherwise, start=end wouldn't distinguish an
empty from a full one!) and cap is one greater than capacity (it's the
modulus used for all the pointer arithmetic). The various "mutating"
methods ensure that removed objects are replaced with nil in the
vector (in particular, the "gap" between the last and first element is
always nil) so that things lost from the ring buffer may be promptly
eligible for garbage collection if nowhere else referenced.
(defprotocol LPop
(lpeek [this])
(lpop [this])
(lconj [this object]))
(defn +mod [a b m]
(mod (+ a b) m))
(defn incmod [a m]
(+mod a 1 m))
(defn -mod [a b m]
(mod (- a b) m))
(defn decmod [a m]
(-mod a 1 m))
(deftype RingBuffer [content cap start end]
clojure.lang.IObj
(withMeta [this m] (RingBuffer. (with-meta content m) cap start end))
(meta [this] (meta content))
clojure.lang.IPersistentVector
(cons [this object]
(let [e (incmod end cap)
s (if (== start e) (incmod start cap) start)]
(RingBuffer.
(assoc (assoc content end object) e nil)
cap s e)))
(count [this] (-mod (+ end cap) start cap))
(empty [this] (RingBuffer. (vec (repeat cap nil)) cap 0 0))
(equiv [this other] (= (seq this) other))
(seq [this]
(when-not (== end start)
(seq
(if (> end start)
(subvec content start end)
(lazy-cat (subvec content start) (subvec content 0 end))))))
(peek [this]
(when-not (== start end)
(nth content (decmod end cap))))
(pop [this]
(if (== start end)
(throw (IllegalStateException. "Can't pop empty ringbuffer"))
(let [e (decmod end cap)]
(RingBuffer.
(assoc content e nil)
cap start e))))
(containsKey [this object]
(and
(integer? object)
(>= object 0)
(< object (count this))))
(assoc [this key val]
(if (integer? key)
(if (= key -1)
(lconj this val)
(if (or (< key 0) (> key (count this)))
(throw (IndexOutOfBoundsException.))
(let [n (+mod key start cap)]
(if (= n end)
(conj this val)
(RingBuffer. (assoc content n val) cap start end)))))
(throw (IllegalArgumentException. "key must be an ingeger"))))
(entryAt [this key]
(if (.containsKey this key)
(first {key (content (+mod key start cap))})))
(valAt [this key]
(.valAt this key nil))
(valAt [this key not-found]
(if (.containsKey this key)
(content (+mod key start cap))
not-found))
(nth [this key]
(if (.containsKey this key)
(.valAt this key)
(throw (IndexOutOfBoundsException.))))
(nth [this key not-found]
(.valAt this key not-found))
(rseq [this]
(if (> end start)
(rseq (subvec content start end))
(lazy-cat (rseq (subvec content 0 end)) (rseq (subvec content start)))))
LPop
(lpeek [this]
(when-not (== start end)
(nth content start)))
(lpop [this]
(if (== start end)
(throw (IllegalStateException. "Can't pop empty ringbuffer"))
(RingBuffer.
(assoc content start nil)
cap (incmod start cap) end)))
(lconj [this object]
(let [s (decmod start cap)
ss (decmod s cap)
e (if (== s end) ss end)]
(RingBuffer.
(assoc (assoc content ss nil) s object)
cap s e)))
clojure.lang.IFn
(invoke [this]
(throw (IllegalArgumentException.
"Wrong number of args (0) passed to: RingBuffer")))
(invoke [this key]
(.nth this key))
(invoke [this key not-found]
(.nth this key not-found))
(invoke [this _ _ _]
(throw (IllegalArgumentException.
"Wrong number of args (3) passed to: RingBuffer")))
(invoke [this _ _ _ _]
(throw (IllegalArgumentException.
"Wrong number of args (4) passed to: RingBuffer")))
(invoke [this _ _ _ _ _]
(throw (IllegalArgumentException.
"Wrong number of args (5) passed to: RingBuffer"))))
(defn ringbuffer [capacity & things]
(assert (> capacity 0))
(let [content (vec (take capacity things))
end (count content)
cap (inc capacity)
nils (repeat (- cap end) nil)]
(RingBuffer. (apply conj content nils) cap 0 end)))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
