/
map.clj
214 lines (194 loc) · 7.22 KB
/
map.clj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
(ns com.walmartlabs.lacinia.vendor.ordered.map
(:use [com.walmartlabs.lacinia.vendor.ordered.common :only [change! Compactable compact]]
[com.walmartlabs.lacinia.vendor.ordered.set :only [ordered-set]]
[com.walmartlabs.lacinia.vendor.useful.experimental.delegate :only [delegating-deftype]])
(:require [clojure.string :as s])
(:import (clojure.lang APersistentMap
IPersistentMap
IPersistentCollection
IPersistentVector
IEditableCollection
ITransientMap
ITransientVector
IHashEq
IObj
IFn
Seqable
MapEquivalence
Reversible
MapEntry
;; Indexed, maybe add later?
;; Sorted almost certainly not accurate
)
(java.util Map Map$Entry)))
;; We could use compile-if technique here, but hoping to avoid
;; an AOT issue using this way instead.
(def hasheq-ordered-map
(or (resolve 'clojure.core/hash-unordered-coll)
(fn old-hasheq-ordered-map [^Seqable m]
(reduce (fn [acc ^MapEntry e]
(let [k (.key e), v (.val e)]
(unchecked-add ^Integer acc ^Integer (bit-xor (hash k) (hash v)))))
0 (.seq m)))))
(defn entry [k v i]
(MapEntry. k (MapEntry. i v)))
(declare transient-ordered-map)
(delegating-deftype OrderedMap [^IPersistentMap backing-map
^IPersistentVector order]
{backing-map {IPersistentMap [(count [])]
Map [(size [])
(containsKey [k])
(isEmpty [])
(keySet [])]}}
;; tagging interfaces
MapEquivalence
IPersistentMap
(equiv [this other]
(and (instance? Map other)
(= (.count this) (.size ^Map other))
(every? (fn [^MapEntry e]
(let [k (.key e)]
(and (.containsKey ^Map other k)
(= (.val e) (.get ^Map other k)))))
(.seq this))))
(entryAt [this k]
(let [v (get this k ::not-found)]
(when (not= v ::not-found)
(MapEntry. k v))))
(valAt [this k]
(.valAt this k nil))
(valAt [this k not-found]
(if-let [^MapEntry e (.get ^Map backing-map k)]
(.val e)
not-found))
IFn
(invoke [this k]
(.valAt this k))
(invoke [this k not-found]
(.valAt this k not-found))
Map
(get [this k]
(.valAt this k))
(containsValue [this v]
(boolean (seq (filter #(= % v) (.values this)))))
(values [this]
(map (comp val val) (.seq this)))
Object
(toString [this]
(str "{" (s/join ", " (for [[k v] this] (str k " " v))) "}"))
(equals [this other]
(.equiv this other))
(hashCode [this]
(APersistentMap/mapHash this))
IHashEq
(hasheq [this]
(hasheq-ordered-map this))
IPersistentMap
(empty [this]
(OrderedMap. (-> {} (with-meta (meta backing-map))) []))
(cons [this obj]
(condp instance? obj
Map$Entry (let [^Map$Entry e obj]
(.assoc this (.getKey e) (.getValue e)))
IPersistentVector (if (= 2 (count obj))
(.assoc this (nth obj 0) (nth obj 1))
(throw (IllegalArgumentException.
"Vector arg to map conj must be a pair")))
(persistent! (reduce (fn [^ITransientMap m ^Map$Entry e]
(.assoc m (.getKey e) (.getValue e)))
(transient this)
obj))))
(assoc [this k v]
(if-let [^MapEntry e (.get ^Map backing-map k)]
(let [old-v (.val e)]
(if (identical? old-v v)
this
(let [i (.key e)]
(OrderedMap. (.cons backing-map (entry k v i))
(.assoc order i (MapEntry. k v))))))
(OrderedMap. (.cons backing-map (entry k v (.count order)))
(.cons order (MapEntry. k v)))))
(without [this k]
(if-let [^MapEntry e (.get ^Map backing-map k)]
(OrderedMap. (.without backing-map k)
(.assoc order (.key e) nil))
this))
(seq [this]
(seq (keep identity order)))
(iterator [this]
(clojure.lang.SeqIterator. (.seq this)))
(entrySet [this]
;; not performant, but i'm not going to implement another whole java interface from scratch just
;; because rich won't let us inherit from AbstractSet
(apply ordered-set this))
IObj
(meta [this]
(.meta ^IObj backing-map))
(withMeta [this m]
(OrderedMap. (.withMeta ^IObj backing-map m) order))
IEditableCollection
(asTransient [this]
(transient-ordered-map this))
Reversible
(rseq [this]
(seq (keep identity (rseq order))))
Compactable
(compact [this]
(into (empty this) this)))
(def ^{:private true,
:tag OrderedMap} empty-ordered-map (empty (OrderedMap. nil nil)))
(defn ordered-map
"Return a map with the given keys and values, whose entries are
sorted in the order that keys are added. assoc'ing a key that is
already in an ordered map leaves its order unchanged. dissoc'ing a
key and then later assoc'ing it puts it at the end, as if it were
assoc'ed for the first time. Supports transient."
([] empty-ordered-map)
([coll]
(into empty-ordered-map coll))
([k v & more]
(apply assoc empty-ordered-map k v more)))
;; contains? is broken for transients. we could define a closure around a gensym
;; to use as the not-found argument to a get, but deftype can't be a closure.
;; instead, we pass `this` as the not-found argument and hope nobody makes a
;; transient contain itself.
(delegating-deftype TransientOrderedMap [^{:unsynchronized-mutable true, :tag ITransientMap} backing-map,
^{:unsynchronized-mutable true, :tag ITransientVector} order]
{backing-map {ITransientMap [(count [])]}}
ITransientMap
(valAt [this k]
(.valAt this k nil))
(valAt [this k not-found]
(if-let [^MapEntry e (.valAt backing-map k)]
(.val e)
not-found))
(assoc [this k v]
(let [^MapEntry e (.valAt backing-map k this)
vector-entry (MapEntry. k v)
i (if (identical? e this)
(do (change! order .conj vector-entry)
(dec (.count order)))
(let [idx (.key e)]
(change! order .assoc idx vector-entry)
idx))]
(change! backing-map .conj (entry k v i))
this))
(conj [this e]
(let [[k v] e]
(.assoc this k v)))
(without [this k]
(let [^MapEntry e (.valAt backing-map k this)]
(when-not (identical? e this)
(let [i (.key e)]
(change! backing-map dissoc! k)
(change! order assoc! i nil)))
this))
(persistent [this]
(OrderedMap. (.persistent backing-map)
(.persistent order))))
(defn transient-ordered-map [^OrderedMap om]
(TransientOrderedMap. (.asTransient ^IEditableCollection (.backing-map om))
(.asTransient ^IEditableCollection (.order om))))
(defmethod print-method OrderedMap [o ^java.io.Writer w]
(.write w "#ordered/map ")
(print-method (seq o) w))