Hi all,
I am working on graph search algorithms using a priority queue which is
implemented by a sorted-set and a custom comparator.
Elements maintained by the set consist of :node (nodename) :dist (current
distance) as well as :visited (still to process). Only one element with
node x is allowed to reside in the queue. The queue is sorted by visited
(false < true), dist, node
Consider my implementation for the queue item
;;just an interface
(defprotocol PDistance
(node [this])
(dist [this])
(visited [this]))
;;implementation with equality contract
(deftype TDistance [n d v]
PDistance
(node [this] n)
(dist [this] d)
(visited [this] v)
Object
(equals [this that] (= (node this)) (node that))
(hashCode [this] (int (node this)))
(toString [this] (format ":node %s :dist %s :visited %s" (node this)
(dist this) (visited this))))
;;the actual priority queue
(sorted-set-by (fn [a b]
(let [table {false 0 true 1}
compare-a (compare (get
table (visited a)) (get table (visited b)))
compare-b (compare (dist a)
(dist b))
compare-c (compare (node a)
(node b))]
(cond
(= 0 compare-c) compare-c
(not= compare-a 0) compare-a
(not= compare-b 0) compare-b
:else compare-c)))
My question is, how would a more dense/expressive priority queue look like?
Thanks in advance
Cheers
Christian
--
--
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
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
