After helping tutor some students earlier in the week on the subject
of priority queues, I ended up implementing it in Clojure as a mutable
data structure. It was straight forward, but curiosity struck and I
implemented the priority queue as an immutable data structure. I'm
pretty sure that 'ffirst 'first 'count and 'rest have a constant time
complexity, but it is a little hard to wrap my mind around this code.
Is it really constant time?
;----- immutiable priority queue -----
(defn priority-cons [priority data queue]
(defstruct element :priority :data)
(let [elem (struct element priority data)
queue-first
(if (nil? queue)
nil
(queue 'ffirst))
queue-rest
(cond
(nil? queue)
nil
(nil? elem)
(queue 'rest)
(>= priority (queue-first :priority))
queue
:else
(priority-cons priority data (queue 'rest)))]
(fn [op]
(cond (= op 'count)
(cond
(nil? queue)
1
(nil? elem)
(queue 'count)
:else
(inc (queue 'count)))
(= op 'first)
(cond
(nil? queue)
data
(nil? elem)
nil
(>= priority (queue-first :priority))
data
:else
(queue-first :data))
(= op 'ffirst)
(cond
(nil? queue)
elem
(nil? elem)
nil
(>= priority (queue-first :priority))
elem
:else
queue-first)
(= op 'rest)
queue-rest
))))
;--- testing code
(defn print-priority-queue [queue]
(loop [queue queue]
(if (nil? queue)
nil
(do
(println (queue 'first))
(recur (queue 'rest))))))
(def a (priority-cons 10 "hello" nil))
(print-priority-queue a)
(a 'count)
(def b (priority-cons 20 "hello2" a))
(print-priority-queue b)
(b 'count)
(def c (priority-cons 15 "hello-m" b))
(print-priority-queue c)
(c 'count)
((c 'rest) 'count)
(((c 'rest) 'rest) 'first)
(((c 'rest) 'rest) 'count)
(((c 'rest) 'rest) 'rest)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to [email protected]
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
-~----------~----~----~----~------~----~------~--~---
