/
ordered_set.clj
130 lines (118 loc) · 3.75 KB
/
ordered_set.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
(ns midje.util.ordered-set
"This code was copied from an earlier version of the ordered library,
`https://github.com/flatland/ordered`, because of a version conflict.
That library is covered by the Eclipse Public License, V1.0, which
you can find in Midje's root directory."
(:require [clojure.string :as s]
[midje.util.ordered-common :refer [Compactable compact change!]])
(:import (clojure.lang IPersistentSet ITransientSet IEditableCollection
IPersistentMap ITransientMap ITransientAssociative
IPersistentVector ITransientVector
Associative SeqIterator Reversible IFn IObj)
(java.util Set Collection)))
(declare transient-ordered-set)
(deftype OrderedSet [^IPersistentMap k->i
^IPersistentVector i->k]
IPersistentSet
(disjoin [this k]
(if-let [i (.valAt k->i k)]
(OrderedSet. (dissoc k->i k)
(assoc i->k i ::empty))
this))
(cons [this k]
(if-let [i (.valAt k->i k)]
this
(OrderedSet. (.assoc ^Associative k->i k (.count i->k))
(.cons i->k k))))
(seq [this]
(seq (remove #(identical? ::empty %) i->k)))
(empty [this]
(OrderedSet. {} []))
(equiv [this other]
(.equals this other))
(get [this k]
(when (.valAt k->i k) k))
(count [this]
(.count k->i))
IObj
(meta [this]
(.meta ^IObj k->i))
(withMeta [this m]
(OrderedSet. (.withMeta ^IObj k->i m)
i->k))
Compactable
(compact [this]
(OrderedSet. k->i
(vec (.seq this))))
Object
(toString [this]
(str "#{" (clojure.string/join " " (map str this)) "}"))
(hashCode [this]
(reduce + (map hash (.seq this))))
(equals [this other]
(or (identical? this other)
(and (instance? Set other)
(let [^Set s (cast Set other)]
(and (= (.size this) (.size s))
(every? #(.contains s %) (.seq this)))))))
Set
(iterator [this]
(SeqIterator. (.seq this)))
(contains [this k]
(.containsKey k->i k))
(containsAll [this ks]
(every? identity (map #(.contains this %) ks)))
(size [this]
(.count this))
(isEmpty [this]
(zero? (.count this)))
(toArray [this dest]
(reduce (fn [idx item]
(aset dest idx item)
(inc idx))
0, (.seq this))
dest)
(toArray [this]
(.toArray this (object-array (.count this))))
Reversible
(rseq [this]
(seq (remove #(identical? ::empty %) (rseq i->k))))
IEditableCollection
(asTransient [this]
(transient-ordered-set this))
IFn
(invoke [this k] (when (.contains this k) k)))
(def ^{:private true,
:tag OrderedSet} empty-ordered-set (empty (OrderedSet. nil nil)))
(defn ordered-set
([] empty-ordered-set)
([& xs] (into empty-ordered-set xs)))
(deftype TransientOrderedSet [^{:unsynchronized-mutable true
:tag ITransientMap} k->i,
^{:unsynchronized-mutable true
:tag ITransientVector} i->k]
ITransientSet
(count [this]
(.count k->i))
(get [this k]
(when (.valAt k->i k) k))
(disjoin [this k]
(let [i (.valAt k->i k)]
(when i
(change! k->i .without k)
(change! i->k .assocN i ::empty)))
this)
(conj [this k]
(let [i (.valAt k->i k)]
(when-not i
(change! ^ITransientAssociative k->i .assoc k (.count i->k))
(change! i->k conj! k)))
this)
(contains [this k]
(boolean (.valAt k->i k)))
(persistent [this]
(OrderedSet. (.persistent k->i)
(.persistent i->k))))
(defn transient-ordered-set [^OrderedSet os]
(TransientOrderedSet. (transient (.k->i os))
(transient (.i->k os))))