From 9766b406ec19b4ea1c25f13be89286bc68c4557e Mon Sep 17 00:00:00 2001 From: Andy Fingerhut Date: Sat, 8 Sep 2012 13:36:41 -0700 Subject: [PATCH] CLJ-1065: Allow duplicate set elements and map keys for all set and map constructors --- src/clj/clojure/core.clj | 30 +++++++---- src/jvm/clojure/lang/PersistentArrayMap.java | 62 +++++++++++++++++++++ test/clojure/test_clojure/data_structures.clj | 72 +++++++++++++++++++++++++ 3 files changed, 154 insertions(+), 10 deletions(-) diff --git a/src/clj/clojure/core.clj b/src/clj/clojure/core.clj index 4a6e61f..79a7d60 100644 --- a/src/clj/clojure/core.clj +++ b/src/clj/clojure/core.clj @@ -353,24 +353,27 @@ (defn hash-map "keyval => key val - Returns a new hash map with supplied mappings." + Returns a new hash map with supplied mappings. If any keys are + equal, they are handled as if by repeated uses of assoc." {:added "1.0" :static true} ([] {}) ([& keyvals] - (. clojure.lang.PersistentHashMap (createWithCheck keyvals)))) + (. clojure.lang.PersistentHashMap (create keyvals)))) (defn hash-set - "Returns a new hash set with supplied keys." + "Returns a new hash set with supplied keys. Any equal keys are + handled as if by repeated uses of conj." {:added "1.0" :static true} ([] #{}) ([& keys] - (clojure.lang.PersistentHashSet/createWithCheck keys))) + (clojure.lang.PersistentHashSet/create keys))) (defn sorted-map "keyval => key val - Returns a new sorted map with supplied mappings." + Returns a new sorted map with supplied mappings. If any keys are + equal, they are handled as if by repeated uses of assoc." {:added "1.0" :static true} ([& keyvals] @@ -378,21 +381,26 @@ (defn sorted-map-by "keyval => key val - Returns a new sorted map with supplied mappings, using the supplied comparator." + Returns a new sorted map with supplied mappings, using the supplied + comparator. If any keys are equal, they are handled as if by + repeated uses of assoc." {:added "1.0" :static true} ([comparator & keyvals] (clojure.lang.PersistentTreeMap/create comparator keyvals))) (defn sorted-set - "Returns a new sorted set with supplied keys." + "Returns a new sorted set with supplied keys. Any equal keys are + handled as if by repeated uses of conj." {:added "1.0" :static true} ([& keys] (clojure.lang.PersistentTreeSet/create keys))) (defn sorted-set-by - "Returns a new sorted set with supplied keys, using the supplied comparator." + "Returns a new sorted set with supplied keys, using the supplied + comparator. Any equal keys are handled as if by repeated uses of + conj." {:added "1.1" :static true} ([comparator & keys] @@ -3927,11 +3935,13 @@ ([env sym] (ns-resolve *ns* env sym))) (defn array-map - "Constructs an array-map." + "Constructs an array-map. If any keys are equal, they are handled as + if by repeated uses of assoc." {:added "1.0" :static true} ([] (. clojure.lang.PersistentArrayMap EMPTY)) - ([& keyvals] (clojure.lang.PersistentArrayMap/createWithCheck (to-array keyvals)))) + ([& keyvals] + (clojure.lang.PersistentArrayMap/createAsIfByAssoc (to-array keyvals)))) ;redefine let and loop with destructuring (defn destructure [bindings] diff --git a/src/jvm/clojure/lang/PersistentArrayMap.java b/src/jvm/clojure/lang/PersistentArrayMap.java index 541f4e2..67c001f 100644 --- a/src/jvm/clojure/lang/PersistentArrayMap.java +++ b/src/jvm/clojure/lang/PersistentArrayMap.java @@ -72,6 +72,68 @@ static public PersistentArrayMap createWithCheck(Object[] init){ } return new PersistentArrayMap(init); } + +static public PersistentArrayMap createAsIfByAssoc(Object[] init){ + // If this looks like it is doing busy-work, it is because it + // is achieving these goals: O(n^2) run time like + // createWithCheck(), never modify init arg, and only + // allocate memory if there are duplicate keys. + int n = 0; + for(int i=0;i< init.length;i += 2) + { + boolean duplicateKey = false; + for(int j=0;j=i; j -= 2) + { + if(equalKey(init[i],init[j])) + { + break; + } + } + nodups[m] = init[i]; + nodups[m+1] = init[j+1]; + m += 2; + } + } + if (m != n) + throw new IllegalArgumentException("Internal error: m=" + m); + init = nodups; + } + return new PersistentArrayMap(init); +} /** * This ctor captures/aliases the passed array, so do not modify later * diff --git a/test/clojure/test_clojure/data_structures.clj b/test/clojure/test_clojure/data_structures.clj index 4e13aad..0ed283b 100644 --- a/test/clojure/test_clojure/data_structures.clj +++ b/test/clojure/test_clojure/data_structures.clj @@ -868,3 +868,75 @@ (into (range 7)) pop)))) + +(deftest test-duplicates + (let [equal-sets-incl-meta (fn [s1 s2] + (and (= s1 s2) + (let [ss1 (sort s1) + ss2 (sort s2)] + (every? identity + (map #(and (= %1 %2) + (= (meta %1) (meta %2))) + ss1 ss2))))) + all-equal-sets-incl-meta (fn [& ss] + (every? (fn [[s1 s2]] + (equal-sets-incl-meta s1 s2)) + (partition 2 1 ss))) + equal-maps-incl-meta (fn [m1 m2] + (and (= m1 m2) + (equal-sets-incl-meta (set (keys m1)) + (set (keys m2))) + (every? #(= (meta (m1 %)) (meta (m2 %))) + (keys m1)))) + all-equal-maps-incl-meta (fn [& ms] + (every? (fn [[m1 m2]] + (equal-maps-incl-meta m1 m2)) + (partition 2 1 ms))) + cmp-first #(> (first %1) (first %2)) + x1 (with-meta [1] {:me "x"}) + y2 (with-meta [2] {:me "y"}) + z3a (with-meta [3] {:me "z3a"}) + z3b (with-meta [3] {:me "z3b"}) + v4a (with-meta [4] {:me "v4a"}) + v4b (with-meta [4] {:me "v4b"}) + v4c (with-meta [4] {:me "v4c"}) + w5a (with-meta [5] {:me "w5a"}) + w5b (with-meta [5] {:me "w5b"}) + w5c (with-meta [5] {:me "w5c"})] + + ;; Sets + (is (thrown? IllegalArgumentException + (read-string "#{1 2 3 4 1 5}"))) + ;; If there are duplicate items when doing (conj #{} x1 x2 ...), + ;; the behavior is that the metadata of the first item is kept. + (are [s x] (all-equal-sets-incl-meta s + (apply conj #{} x) + (set x) + (apply hash-set x) + (apply sorted-set x) + (apply sorted-set-by cmp-first x)) + #{x1 y2} [x1 y2] + #{x1 z3a} [x1 z3a z3b] + #{w5b} [w5b w5a w5c] + #{z3a x1} [z3a z3b x1]) + + ;; Maps + (is (thrown? IllegalArgumentException + (read-string "{:a 1, :b 2, :a -1, :c 3}"))) + ;; If there are duplicate keys when doing (assoc {} k1 v1 k2 v2 + ;; ...), the behavior is that the metadata of the first duplicate + ;; key is kept, but mapped to the last value with an equal key + ;; (where metadata of keys are not compared). + (are [h x] (all-equal-maps-incl-meta h + (apply assoc {} x) + (apply hash-map x) + (apply sorted-map x) + (apply sorted-map-by cmp-first x) + (apply array-map x)) + {x1 2, z3a 4} [x1 2, z3a 4] + {x1 2, z3a 5} [x1 2, z3a 4, z3b 5] + {z3a 5} [z3a 2, z3a 4, z3b 5] + {z3b 4, x1 5} [z3b 2, z3a 4, x1 5] + {z3b v4b, x1 5} [z3b v4a, z3a v4b, x1 5] + {x1 v4a, w5a v4c, v4a z3b, y2 2} [x1 v4a, w5a v4a, w5b v4b, + v4a z3a, y2 2, v4b z3b, w5c v4c]))) -- 1.7.10