Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 333 lines (282 sloc) 13.503 kb
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
1 ;; A priority map is a map from items to priorities,
2 ;; offering queue-like peek/pop as well as the map-like ability to
3 ;; easily reassign priorities and other conveniences.
4 ;; by Mark Engelberg (mark.engelberg@gmail.com)
5 ;; May 20, 2011
6
7 (ns
8 ^{:author "Mark Engelberg",
9 :doc "A priority map is very similar to a sorted map, but whereas a sorted map produces a
10 sequence of the entries sorted by key, a priority map produces the entries sorted by value.
11 In addition to supporting all the functions a sorted map supports, a priority map
12 can also be thought of as a queue of [item priority] pairs. To support usage as
13 a versatile priority queue, priority maps also support conj/peek/pop operations.
14
15 The standard way to construct a priority map is with priority-map:
16 user=> (def p (priority-map :a 2 :b 1 :c 3 :d 5 :e 4 :f 3))
17 #'user/p
18 user=> p
19 {:b 1, :a 2, :c 3, :f 3, :e 4, :d 5}
20
21 So :b has priority 1, :a has priority 2, and so on.
22 Notice how the priority map prints in an order sorted by its priorities (i.e., the map's values)
23
24 We can use assoc to assign a priority to a new item:
25 user=> (assoc p :g 1)
26 {:b 1, :g 1, :a 2, :c 3, :f 3, :e 4, :d 5}
27
28 or to assign a new priority to an extant item:
29 user=> (assoc p :c 4)
30 {:b 1, :a 2, :f 3, :c 4, :e 4, :d 5}
31
32 We can remove an item from the priority map:
33 user=> (dissoc p :e)
34 {:b 1, :a 2, :c 3, :f 3, :d 5}
35
36 An alternative way to add to the priority map is to conj a [item priority] pair:
37 user=> (conj p [:g 0])
38 {:g 0, :b 1, :a 2, :c 3, :f 3, :e 4, :d 5}
39
40 or use into:
41 user=> (into p [[:g 0] [:h 1] [:i 2]])
42 {:g 0, :b 1, :h 1, :a 2, :i 2, :c 3, :f 3, :e 4, :d 5}
43
44 Priority maps are countable:
45 user=> (count p)
46 6
47
48 Like other maps, equivalence is based not on type, but on contents.
49 In other words, just as a sorted-map can be equal to a hash-map,
50 so can a priority-map.
51 user=> (= p {:b 1, :a 2, :c 3, :f 3, :e 4, :d 5})
52 true
53
54 You can test them for emptiness:
55 user=> (empty? (priority-map))
56 true
57 user=> (empty? p)
58 false
59
60 You can test whether an item is in the priority map:
61 user=> (contains? p :a)
62 true
63 user=> (contains? p :g)
64 false
65
66 It is easy to look up the priority of a given item, using any of the standard map mechanisms:
67 user=> (get p :a)
68 2
69 user=> (get p :g 10)
70 10
71 user=> (p :a)
72 2
73 user=> (:a p)
74 2
75
76 Priority maps derive much of their utility by providing priority-based seq.
77 Note that no guarantees are made about the order in which items of the same priority appear.
78 user=> (seq p)
79 ([:b 1] [:a 2] [:c 3] [:f 3] [:e 4] [:d 5])
80 Because no guarantees are made about the order of same-priority items, note that
81 rseq might not be an exact reverse of the seq. It is only guaranteed to be in
82 descending order.
83 user=> (rseq p)
84 ([:d 5] [:e 4] [:c 3] [:f 3] [:a 2] [:b 1])
85
86 This means first/rest/next/for/map/etc. all operate in priority order.
87 user=> (first p)
88 [:b 1]
89 user=> (rest p)
90 ([:a 2] [:c 3] [:f 3] [:e 4] [:d 5])
91
92 Priority maps support metadata:
93 user=> (meta (with-meta p {:extra :info}))
94 {:extra :info}
95
96 But perhaps most importantly, priority maps can also function as priority queues.
97 peek, like first, gives you the first [item priority] pair in the collection.
98 pop removes the first [item priority] from the collection.
99 (Note that unlike rest, which returns a seq, pop returns a priority map).
100
101 user=> (peek p)
102 [:b 1]
103 user=> (pop p)
104 {:a 2, :c 3, :f 3, :e 4, :d 5}
105
106 It is also possible to use a custom comparator:
107 user=> (priority-map-by (comparator >) :a 1 :b 2 :c 3)
108 {:c 3, :b 2, :a 1}
109
110 All of these operations are efficient. Generally speaking, most operations
111 are O(log n) where n is the number of distinct priorities. Some operations
112 (for example, straightforward lookup of an item's priority, or testing
113 whether a given item is in the priority map) are as efficient
114 as Clojure's built-in map.
115
116 The key to this efficiency is that internally, not only does the priority map store
117 an ordinary hash map of items to priority, but it also stores a sorted map that
118 maps priorities to sets of items with that priority.
119
120 A typical textbook priority queue data structure supports at the ability to add
121 a [item priority] pair to the queue, and to pop/peek the next [item priority] pair.
122 But many real-world applications of priority queues require more features, such
123 as the ability to test whether something is already in the queue, or to reassign
124 a priority. For example, a standard formulation of Dijkstra's algorithm requires the
125 ability to reduce the priority number associated with a given item. Once you
126 throw persistence into the mix with the desire to adjust priorities, the traditional
127 structures just don't work that well.
128
129 This particular blend of Clojure's built-in hash sets, hash maps, and sorted maps
130 proved to be a great way to implement an especially flexible persistent priority queue.
131
132 Connoisseurs of algorithms will note that this structure's peek operation is not O(1) as
133 it would be if based upon a heap data structure, but I feel this is a small concession for
134 the blend of persistence, priority reassignment, and priority-sorted seq, which can be
135 quite expensive to achieve with a heap (I did actually try this for comparison). Furthermore,
136 this peek's logarithmic behavior is quite good (on my computer I can do a million
137 peeks at a priority map with a million items in 750ms). Also, consider that peek and pop
138 usually follow one another, and even with a heap, pop is logarithmic. So the net combination
139 of peek and pop is not much different between this versatile formulation of a priority map and
140 a more limited heap-based one. In a nutshell, peek, although not O(1), is unlikely to be the
141 bottleneck in your program.
142
143 All in all, I hope you will find priority maps to be an easy-to-use and useful addition
144 to Clojure's assortment of built-in maps (hash-map and sorted-map).
145 "}
146 clojure.data.priority-map
147 (:use clojure.test)
148 (:import clojure.lang.MapEntry java.util.Map clojure.lang.PersistentTreeMap))
149
150 ; Note that the plan is to eventually support subseq, but this will require
151 ; some changes to core:
152 ;; user=> (subseq p < 3)
153 ;; ([:b 1] [:a 2])
154 ;; user=> (subseq p >= 3)
155 ;; ([:c 3] [:f 3] [:e 4] [:d 5])
156
157 (declare pm-empty)
158
159 ; A Priority Map is comprised of a sorted map that maps priorities to hash sets of items
160 ; with that priority (priority->set-of-items),
161 ; as well as a hash map that maps items to priorities (item->priority)
162 ; Priority maps may also have metadata
163
ad1bfcab »
2011-09-11 Fix metadata handling.
164 (deftype PersistentPriorityMap [priority->set-of-items item->priority _meta]
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
165 Object
166 (toString [this] (str (.seq this)))
167
168 clojure.lang.ILookup
169 ; valAt gives (get pm key) and (get pm key not-found) behavior
170 (valAt [this item] (get item->priority item))
171 (valAt [this item not-found] (get item->priority item not-found))
172
173 clojure.lang.IPersistentMap
174 (count [this] (count item->priority))
175
176 (assoc [this item priority]
177 (let [current-priority (get item->priority item nil)]
178 (if current-priority
179 ;Case 1 - item is already in priority map, so this is a reassignment
180 (if (= current-priority priority)
181 ;Subcase 1 - no change in priority, do nothing
182 this
183 (let [item-set (get priority->set-of-items current-priority)]
184 (if (= (count item-set) 1)
185 ;Subcase 2 - it was the only item of this priority
186 ;so remove old priority entirely
187 ;and conj item onto new priority's set
188 (PersistentPriorityMap.
189 (assoc (dissoc priority->set-of-items current-priority)
190 priority (conj (get priority->set-of-items priority #{}) item))
ad1bfcab »
2011-09-11 Fix metadata handling.
191 (assoc item->priority item priority)
8da82017 »
2011-09-11 Merge Tchavdar's patch which looks better than my fix.
192 (meta this))
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
193 ;Subcase 3 - there were many items associated with the item's original priority,
194 ;so remove it from the old set and conj it onto the new one.
195 (PersistentPriorityMap.
196 (assoc priority->set-of-items
197 current-priority (disj (get priority->set-of-items current-priority) item)
198 priority (conj (get priority->set-of-items priority #{}) item))
ad1bfcab »
2011-09-11 Fix metadata handling.
199 (assoc item->priority item priority)
8da82017 »
2011-09-11 Merge Tchavdar's patch which looks better than my fix.
200 (meta this)))))
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
201 ; Case 2: Item is new to the priority map, so just add it.
202 (PersistentPriorityMap.
203 (assoc priority->set-of-items
204 priority (conj (get priority->set-of-items priority #{}) item))
ad1bfcab »
2011-09-11 Fix metadata handling.
205 (assoc item->priority item priority)
8da82017 »
2011-09-11 Merge Tchavdar's patch which looks better than my fix.
206 (meta this)))))
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
207
208 (empty [this] pm-empty)
209
210 ; cons defines conj behavior
211 (cons [this e] (let [[item priority] e] (.assoc this item priority)))
212
213 ; Like sorted maps, priority maps are equal to other maps provided
214 ; their key-value pairs are the same.
215 (equiv [this o] (.equiv item->priority o))
216 (hashCode [this] (.hashCode item->priority))
217 (equals [this o] (or (identical? this o) (.equals item->priority o)))
218
219 ;containsKey implements (contains? pm k) behavior
220 (containsKey [this item] (contains? item->priority item))
221
222 (entryAt [this k]
223 (let [v (.valAt this k this)]
224 (when-not (identical? v this)
225 (MapEntry. k v))))
226
227 (seq [this]
228 (seq (for [[priority item-set] priority->set-of-items, item item-set]
229 (MapEntry. item priority))))
230
231 ;without implements (dissoc pm k) behavior
232 (without
233 [this item]
234 (let [priority (item->priority item ::not-found)]
235 (if (= priority ::not-found)
236 ;; If item is not in map, return the map unchanged.
237 this
238 (let [item-set (priority->set-of-items priority)]
239 (if (= (count item-set) 1)
240 ;;If it is the only item with this priority, remove that priority's set completely
241 (PersistentPriorityMap. (dissoc priority->set-of-items priority)
8da82017 »
2011-09-11 Merge Tchavdar's patch which looks better than my fix.
242 (dissoc item->priority item)
243 (meta this))
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
244 ;;Otherwise, just remove the item from the priority's set.
245 (PersistentPriorityMap.
246 (assoc priority->set-of-items priority (disj item-set item)),
8da82017 »
2011-09-11 Merge Tchavdar's patch which looks better than my fix.
247 (dissoc item->priority item)
248 (meta this)))))))
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
249
250 java.io.Serializable ;Serialization comes for free with the other things implemented
251 clojure.lang.MapEquivalence
252 Map ;Makes this compatible with java's map
253 (size [this] (count item->priority))
254 (isEmpty [this] (zero? (count item->priority)))
255 (containsValue [this v] (contains? (priority->set-of-items this) v))
256 (get [this k] (.valAt this k))
257 (put [this k v] (throw (UnsupportedOperationException.)))
258 (remove [this k] (throw (UnsupportedOperationException.)))
259 (putAll [this m] (throw (UnsupportedOperationException.)))
260 (clear [this] (throw (UnsupportedOperationException.)))
261 (keySet [this] (set (keys this)))
262 (values [this] (vals this))
263 (entrySet [this] (set this))
a4f0fd03 »
2012-09-09 Fix DPRIMAP-1 by implementing Iterable.
264
265 Iterable
266 (iterator [this] (clojure.lang.SeqIterator. (seq this)))
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
267
268 clojure.lang.IPersistentStack
269 (peek [this]
270 (when-not (.isEmpty this)
271 (let [f (first priority->set-of-items)]
272 (MapEntry. (first (val f)) (key f)))))
273
274 (pop [this]
275 (if (.isEmpty this) (throw (IllegalStateException. "Can't pop empty priority map"))
276 (let [f (first priority->set-of-items),
277 item-set (val f)
278 item (first item-set),
279 priority (key f)]
280 (if (= (count item-set) 1)
281 ;If the first item is the only item with its priority, remove that priority's set completely
282 (PersistentPriorityMap.
283 (dissoc priority->set-of-items priority)
8da82017 »
2011-09-11 Merge Tchavdar's patch which looks better than my fix.
284 (dissoc item->priority item)
285 (meta this))
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
286 ;Otherwise, just remove the item from the priority's set.
287 (PersistentPriorityMap.
288 (assoc priority->set-of-items priority (disj item-set item)),
8da82017 »
2011-09-11 Merge Tchavdar's patch which looks better than my fix.
289 (dissoc item->priority item)
290 (meta this))))))
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
291
292 clojure.lang.IFn
293 ;makes priority map usable as a function
294 (invoke [this k] (.valAt this k))
295 (invoke [this k not-found] (.valAt this k not-found))
296
297 clojure.lang.IObj
298 ;adds metadata support
ad1bfcab »
2011-09-11 Fix metadata handling.
299 (meta [this] _meta)
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
300 (withMeta [this m] (PersistentPriorityMap. priority->set-of-items item->priority m))
301
302 clojure.lang.Reversible
303 (rseq [this]
304 (seq (for [[priority item-set] (rseq priority->set-of-items), item item-set]
305 (MapEntry. item priority)))))
306
307 ;; clojure.lang.Sorted
308 ;; ; These methods provide support for subseq
309 ;; (comparator [this] (.comparator ^PersistentTreeMap priority->set-of-items))
310 ;; (entryKey [this entry] (val entry))
311 ;; (seqFrom [this k ascending]
312 ;; (let [sets (if ascending (subseq priority->set-of-items >= k) (rsubseq priority->set-of-items <= k))]
313 ;; (seq (for [[priority item-set] sets, item item-set]
314 ;; (MapEntry. item priority)))))
315 ;; (seq [this ascending]
316 ;; (if ascending (seq this) (rseq this))))
317
318 (def ^:private pm-empty (PersistentPriorityMap. (sorted-map) {} {}))
ad1bfcab »
2011-09-11 Fix metadata handling.
319 (defn- pm-empty-by [comparator] (PersistentPriorityMap. (sorted-map-by comparator) {} {}))
6e39f915 »
2011-08-02 first commit, copied from 1.2; doesn't work quite right with 1.3's de…
320
321 ; The main way to build priority maps
322 (defn priority-map
323 "keyval => key val
324 Returns a new priority map with supplied mappings"
325 [& keyvals]
326 (reduce conj pm-empty (partition 2 keyvals)))
327
328 (defn priority-map-by
329 "keyval => key val
330 Returns a new priority map with supplied mappings"
331 [comparator & keyvals]
332 (reduce conj (pm-empty-by comparator) (partition 2 keyvals)))
Something went wrong with that request. Please try again.