You don't need an extra element in the vector to distinguish between
empty and full. You can store (start, size) instead of (start, end).
On Feb 3, 12:57 pm, Ken Wesson <kwess...@gmail.com> wrote:
> 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
