(deftype Queue [chunk1 chunk2 size metadata]
clojure.lang.IObj
(withMeta [this m] (Queue. chunk1 chunk2 size m))
(meta [this] metadata)
clojure.lang.IPersistentStack
(cons [this object] (Queue. chunk1 (conj chunk2 object) (inc size) metadata))
(count [this] size)
(empty [this] (Queue. nil [] 0 metadata))
(equiv [this other] (.equiv (seq this) other))
(seq [this] (seq (lazy-cat chunk1 chunk2)))
(peek [this] (if chunk1 (first chunk1) (first chunk2)))
(pop [this]
(if chunk1
(Queue. (next chunk1) chunk2 (dec size) metadata)
(if-let [nc1 (next chunk2)]
(Queue. nc1 [] (dec size) metadata)
(throw (IllegalStateException.
"Can't pop empty queue")))))
java.lang.Object
(toString [this] (str (seq this))))
(defn queue [& things]
(Queue. (seq things) [] (count things) {}))
The queue stores a seq and a vector; the queue's items are those of
the seq, followed by those of the vector. New items are conjed onto
the vector, which is efficient. Peek looks at the start of the seq,
then if empty the start of the vector, which is efficient. Pop pops
off the seq, if that's not empty. If it is, but the vector isn't, then
it produces a queue whose seq is (next the-old-vector) and whose
vector is empty. This is also O(1).
Essentially, it starts out empty. New items are added to a vector of
newer-stuff. Pop removes from a seq of older-stuff. If the older-stuff
runs out, the current newer-stuff becomes the older-stuff and a new,
empty newer-stuff is started. Items thus move in to the newer-stuff
vector, then into the older-stuff seq, and then get dropped; vectors
get created, populated with new items, and eventually converted into
seqs to be consumed at the other end.
And with that done, a more efficient priority queue, with O(1) pop:
(deftype PriorityQueue [q size]
clojure.lang.IObj
(withMeta [this meta] (PriorityQueue. (with-meta q meta) size))
(meta [this] (meta q))
clojure.lang.IPersistentStack
(cons [this [v pri]]
(PriorityQueue.
(merge-with #(conj %1 (first %2)) q {pri (queue v)})
(inc size)))
(count [this] size)
(empty [this] (PriorityQueue. (sorted-map) 0))
(equiv [this other] (.equiv (seq this) other))
(seq [this] (mapcat val q))
(peek [this] (first (second (first q))))
(pop [this]
(if-let [[pri vq] (first q)]
(let [new-vq (pop vq)]
(if (empty? new-vq)
(PriorityQueue. (dissoc q pri) (dec size))
(PriorityQueue. (assoc q pri new-vq) (dec size))))
(throw (IllegalStateException.
"Can't pop empty priority queue"))))
java.lang.Object
(toString [this] (.toString q)))
(defn priority-queue [& pvs]
(apply conj (PriorityQueue. (sorted-map) 0) (partition 2 pvs)))
For convenience, since priority queue conj expects a vector of [item priority]:
(defn ppush [pri-q item priority & more]
(apply conj pri-q (cons [item priority] (partition 2 more))))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
