(deftype PriorityQueue [queue]
clojure.lang.IObj
(withMeta [this meta] (PriorityQueue. (with-meta queue meta)))
(meta [this] (meta queue))
clojure.lang.IPersistentStack
(cons [this object]
(let [[v pri] object]
(PriorityQueue.
(merge-with #(conj %1 (first %2)) queue {pri [v]}))))
(count [this] (reduce + (map (comp count val) queue)))
(empty [this] (PriorityQueue. (sorted-map)))
(equiv [this other] (.equiv (seq this) other))
(seq [this] (mapcat val queue))
(peek [this] (first (second (first queue))))
(pop [this]
(if-let [[pri vs] (first queue)]
(let [new-vs (vec (rest vs))]
(if (empty? new-vs)
(PriorityQueue. (dissoc queue pri))
(PriorityQueue. (assoc queue pri new-vs))))
(throw (IllegalStateException.
"Can't pop empty priority queue"))))
java.lang.Object
(toString [this] (.toString queue)))
(defn priority-queue [& pvs]
(reduce conj (PriorityQueue. (sorted-map)) (partition 2 pvs)))
(defmacro pri-consumer [[item] & body]
`[(agent (priority-queue))
(fn [~item] ~@body)])
(defmacro def-pri-consumer [name item & body]
`(def ~name (pri-consumer ~item ~@body)))
(defn pri-feed [[ag consume-fn] & vps]
(doseq [vp (partition 2 vps)]
(send ag conj vp))
(send-off ag
(fn dojob [queue]
(if-let [item (peek queue)]
(do
(consume-fn item)
(send-off ag dojob)
(pop queue))
queue)))
[ag consume-fn])
This is a lot longer than nine lines, but it does include a whole
priority queue implementation that works with seq, conj, pop, and
peek.
user=> (def-pri-consumer xyzzy [item] (println item))
#'user/xyzzy
user=> (pri-feed xyzzy "foo" 1 "bar" 2 "xyzzy" 1 "baz" 3 "quux" 2 "mumble" 42)
[#<Agent #<PriorityQueue {}>>
#<user$fn__1923 user$fn__1923@1560b81>]
out has:
foo
xyzzy
bar
quux
baz
mumble
user=> (pri-feed xyzzy "frotz" 17)
[#<Agent #<PriorityQueue {}>>
#<user$fn__1923 user$fn__1923@1560b81>]
out now also has:
frotz
This might be interesting as a demonstration of both some of the
tricks you can do with agents, and how you can implement your own
persistent collection that will work seamlessly with Clojure's seq and
collection functions, support metadata, and the like. The one thing
that bugs me is the priority queue implementation has a linear
operation that feels like it "ought" to be possible to do in constant
time. Specifically, it uses a sorted-map with priorities as keys and
vectors of items as values. To have the generally-desired behavior
that same-priority items are handled on a first-come, first-serve
basis requires that pop consume from the start of the vector of the
top-priority items. This means (vec (rest items)) and is linear in the
number of items at that priority. Doing it better would seem to
require an IPersistentQueue or IPersistentDeque, though.
--
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
