1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/clojure/test_clojure/data_structures.clj	Sat Aug 21 06:25:44 2010 -0400
     1.3 @@ -0,0 +1,830 @@
     1.4 +;   Copyright (c) Rich Hickey. All rights reserved.
     1.5 +;   The use and distribution terms for this software are covered by the
     1.6 +;   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
     1.7 +;   which can be found in the file epl-v10.html at the root of this distribution.
     1.8 +;   By using this software in any fashion, you are agreeing to be bound by
     1.9 +;   the terms of this license.
    1.10 +;   You must not remove this notice, or any other, from this software.
    1.11 +
    1.12 +; Author: Frantisek Sodomka
    1.13 +
    1.14 +
    1.15 +(ns clojure.test-clojure.data-structures
    1.16 +  (:use clojure.test))
    1.17 +
    1.18 +
    1.19 +;; *** Helper functions ***
    1.20 +
    1.21 +(defn diff [s1 s2]
    1.22 +  (seq (reduce disj (set s1) (set s2))))
    1.23 +
    1.24 +
    1.25 +;; *** General ***
    1.26 +
    1.27 +(defstruct equality-struct :a :b)
    1.28 +
    1.29 +(deftest test-equality
    1.30 +  ; nil is not equal to any other value
    1.31 +  (are [x] (not (= nil x))
    1.32 +      true false
    1.33 +      0 0.0
    1.34 +      \space
    1.35 +      "" #""
    1.36 +      () [] #{} {}
    1.37 +      (lazy-seq nil)  ; SVN 1292: fixed (= (lazy-seq nil) nil)
    1.38 +      (lazy-seq ())
    1.39 +      (lazy-seq [])
    1.40 +      (lazy-seq {})
    1.41 +      (lazy-seq #{})
    1.42 +      (lazy-seq "")
    1.43 +      (lazy-seq (into-array []))
    1.44 +      (new Object) )
    1.45 +
    1.46 +  ; numbers equality across types (see tests below - NOT IMPLEMENTED YET)
    1.47 +
    1.48 +  ; ratios
    1.49 +  (is (= 1/2 0.5))
    1.50 +  (is (= 1/1000 0.001))
    1.51 +  (is (not= 2/3 0.6666666666666666))
    1.52 +
    1.53 +  ; vectors equal other seqs by items equality
    1.54 +  (are [x y] (= x y)
    1.55 +      '() []        ; regression fixed in r1208; was not equal
    1.56 +      '(1) [1]
    1.57 +      '(1 2) [1 2]
    1.58 +
    1.59 +      [] '()        ; same again, but vectors first
    1.60 +      [1] '(1)
    1.61 +      [1 2] '(1 2) )
    1.62 +  (is (not= [1 2] '(2 1)))  ; order of items matters
    1.63 +
    1.64 +  ; list and vector vs. set and map
    1.65 +  (are [x y] (not= x y)
    1.66 +      ; only () equals []
    1.67 +      () #{}
    1.68 +      () {}
    1.69 +      [] #{}
    1.70 +      [] {}
    1.71 +      #{} {}
    1.72 +      ; only '(1) equals [1]
    1.73 +      '(1) #{1}
    1.74 +      [1] #{1} )
    1.75 +
    1.76 +  ; sorted-map, hash-map and array-map - classes differ, but content is equal
    1.77 +  
    1.78 +;; TODO: reimplement all-are with new do-template?  
    1.79 +;;   (all-are (not= (class _1) (class _2))
    1.80 +;;       (sorted-map :a 1)
    1.81 +;;       (hash-map   :a 1)
    1.82 +;;       (array-map  :a 1))
    1.83 +;;   (all-are (= _1 _2)
    1.84 +;;       (sorted-map)
    1.85 +;;       (hash-map)
    1.86 +;;       (array-map))
    1.87 +;;   (all-are (= _1 _2)
    1.88 +;;       (sorted-map :a 1)
    1.89 +;;       (hash-map   :a 1)
    1.90 +;;       (array-map  :a 1))
    1.91 +;;   (all-are (= _1 _2)
    1.92 +;;       (sorted-map :a 1 :z 3 :c 2)
    1.93 +;;       (hash-map   :a 1 :z 3 :c 2)
    1.94 +;;       (array-map  :a 1 :z 3 :c 2))
    1.95 +
    1.96 +  ; struct-map vs. sorted-map, hash-map and array-map
    1.97 +  (are [x] (and (not= (class (struct equality-struct 1 2)) (class x))
    1.98 +                (= (struct equality-struct 1 2) x))
    1.99 +      (sorted-map-by compare :a 1 :b 2)
   1.100 +      (sorted-map :a 1 :b 2)
   1.101 +      (hash-map   :a 1 :b 2)
   1.102 +      (array-map  :a 1 :b 2))
   1.103 +
   1.104 +  ; sorted-set vs. hash-set
   1.105 +  (is (not= (class (sorted-set 1)) (class (hash-set 1))))
   1.106 +  (are [x y] (= x y)
   1.107 +      (sorted-set-by <) (hash-set)
   1.108 +      (sorted-set-by < 1) (hash-set 1)
   1.109 +      (sorted-set-by < 3 2 1) (hash-set 3 2 1)
   1.110 +      (sorted-set) (hash-set)
   1.111 +      (sorted-set 1) (hash-set 1)
   1.112 +      (sorted-set 3 2 1) (hash-set 3 2 1) ))
   1.113 +
   1.114 +
   1.115 +;; *** Collections ***
   1.116 +
   1.117 +(deftest test-count
   1.118 +  (are [x y] (= x y)
   1.119 +      (count nil) 0
   1.120 +
   1.121 +      (count ()) 0
   1.122 +      (count '(1)) 1
   1.123 +      (count '(1 2 3)) 3
   1.124 +
   1.125 +      (count []) 0
   1.126 +      (count [1]) 1
   1.127 +      (count [1 2 3]) 3
   1.128 +
   1.129 +      (count #{}) 0
   1.130 +      (count #{1}) 1
   1.131 +      (count #{1 2 3}) 3
   1.132 +
   1.133 +      (count {}) 0
   1.134 +      (count {:a 1}) 1
   1.135 +      (count {:a 1 :b 2 :c 3}) 3
   1.136 +
   1.137 +      (count "") 0
   1.138 +      (count "a") 1
   1.139 +      (count "abc") 3
   1.140 +
   1.141 +      (count (into-array [])) 0
   1.142 +      (count (into-array [1])) 1
   1.143 +      (count (into-array [1 2 3])) 3
   1.144 +
   1.145 +      (count (java.util.ArrayList. [])) 0
   1.146 +      (count (java.util.ArrayList. [1])) 1
   1.147 +      (count (java.util.ArrayList. [1 2 3])) 3
   1.148 +
   1.149 +      (count (java.util.HashMap. {})) 0
   1.150 +      (count (java.util.HashMap. {:a 1})) 1
   1.151 +      (count (java.util.HashMap. {:a 1 :b 2 :c 3})) 3 )
   1.152 +
   1.153 +  ; different types
   1.154 +  (are [x]  (= (count [x]) 1)
   1.155 +      nil true false
   1.156 +      0 0.0 "" \space
   1.157 +      () [] #{} {}  ))
   1.158 +
   1.159 +
   1.160 +(deftest test-conj
   1.161 +  ; doesn't work on strings or arrays
   1.162 +  (is (thrown? ClassCastException (conj "" \a)))
   1.163 +  (is (thrown? ClassCastException (conj (into-array []) 1)))
   1.164 +
   1.165 +  (are [x y] (= x y)
   1.166 +      (conj nil 1) '(1)
   1.167 +      (conj nil 3 2 1) '(1 2 3)
   1.168 +
   1.169 +      (conj nil nil) '(nil)
   1.170 +      (conj nil nil nil) '(nil nil)
   1.171 +      (conj nil nil nil 1) '(1 nil nil)
   1.172 +
   1.173 +      ; list -> conj puts the item at the front of the list
   1.174 +      (conj () 1) '(1)
   1.175 +      (conj () 1 2) '(2 1)
   1.176 +
   1.177 +      (conj '(2 3) 1) '(1 2 3)
   1.178 +      (conj '(2 3) 1 4 3) '(3 4 1 2 3)
   1.179 +
   1.180 +      (conj () nil) '(nil)
   1.181 +      (conj () ()) '(())
   1.182 +
   1.183 +      ; vector -> conj puts the item at the end of the vector
   1.184 +      (conj [] 1) [1]
   1.185 +      (conj [] 1 2) [1 2]
   1.186 +
   1.187 +      (conj [2 3] 1) [2 3 1]
   1.188 +      (conj [2 3] 1 4 3) [2 3 1 4 3]
   1.189 +
   1.190 +      (conj [] nil) [nil]
   1.191 +      (conj [] []) [[]]
   1.192 +
   1.193 +      ; map -> conj expects another (possibly single entry) map as the item,
   1.194 +      ;   and returns a new map which is the old map plus the entries
   1.195 +      ;   from the new, which may overwrite entries of the old.
   1.196 +      ;   conj also accepts a MapEntry or a vector of two items (key and value).
   1.197 +      (conj {} {}) {}
   1.198 +      (conj {} {:a 1}) {:a 1}
   1.199 +      (conj {} {:a 1 :b 2}) {:a 1 :b 2}
   1.200 +      (conj {} {:a 1 :b 2} {:c 3}) {:a 1 :b 2 :c 3}
   1.201 +      (conj {} {:a 1 :b 2} {:a 3 :c 4}) {:a 3 :b 2 :c 4}
   1.202 +
   1.203 +      (conj {:a 1} {:a 7}) {:a 7}
   1.204 +      (conj {:a 1} {:b 2}) {:a 1 :b 2}
   1.205 +      (conj {:a 1} {:a 7 :b 2}) {:a 7 :b 2}
   1.206 +      (conj {:a 1} {:a 7 :b 2} {:c 3}) {:a 7 :b 2 :c 3}
   1.207 +      (conj {:a 1} {:a 7 :b 2} {:b 4 :c 5}) {:a 7 :b 4 :c 5}
   1.208 +
   1.209 +      (conj {} (first {:a 1})) {:a 1}           ; MapEntry
   1.210 +      (conj {:a 1} (first {:b 2})) {:a 1 :b 2}
   1.211 +      (conj {:a 1} (first {:a 7})) {:a 7}
   1.212 +      (conj {:a 1} (first {:b 2}) (first {:a 5})) {:a 5 :b 2}
   1.213 +
   1.214 +      (conj {} [:a 1]) {:a 1}                   ; vector
   1.215 +      (conj {:a 1} [:b 2]) {:a 1 :b 2}
   1.216 +      (conj {:a 1} [:a 7]) {:a 7}
   1.217 +      (conj {:a 1} [:b 2] [:a 5]) {:a 5 :b 2}
   1.218 +
   1.219 +      (conj {} {nil {}}) {nil {}}
   1.220 +      (conj {} {{} nil}) {{} nil}
   1.221 +      (conj {} {{} {}}) {{} {}}
   1.222 +
   1.223 +      ; set
   1.224 +      (conj #{} 1) #{1}
   1.225 +      (conj #{} 1 2 3) #{1 2 3}
   1.226 +
   1.227 +      (conj #{2 3} 1) #{3 1 2}
   1.228 +      (conj #{3 2} 1) #{1 2 3}
   1.229 +
   1.230 +      (conj #{2 3} 2) #{2 3}
   1.231 +      (conj #{2 3} 2 3) #{2 3}
   1.232 +      (conj #{2 3} 4 1 2 3) #{1 2 3 4}
   1.233 +
   1.234 +      (conj #{} nil) #{nil}
   1.235 +      (conj #{} #{}) #{#{}} ))
   1.236 +
   1.237 +
   1.238 +;; *** Lists and Vectors ***
   1.239 +
   1.240 +(deftest test-peek
   1.241 +  ; doesn't work for sets and maps
   1.242 +  (is (thrown? ClassCastException (peek #{1})))
   1.243 +  (is (thrown? ClassCastException (peek {:a 1})))
   1.244 +
   1.245 +  (are [x y] (= x y)
   1.246 +      (peek nil) nil
   1.247 +
   1.248 +      ; list = first
   1.249 +      (peek ()) nil
   1.250 +      (peek '(1)) 1
   1.251 +      (peek '(1 2 3)) 1
   1.252 +
   1.253 +      (peek '(nil)) nil     ; special cases
   1.254 +      (peek '(1 nil)) 1
   1.255 +      (peek '(nil 2)) nil
   1.256 +      (peek '(())) ()
   1.257 +      (peek '(() nil)) ()
   1.258 +      (peek '(() 2 nil)) ()
   1.259 +
   1.260 +      ; vector = last
   1.261 +      (peek []) nil
   1.262 +      (peek [1]) 1
   1.263 +      (peek [1 2 3]) 3
   1.264 +
   1.265 +      (peek [nil]) nil      ; special cases
   1.266 +      (peek [1 nil]) nil
   1.267 +      (peek [nil 2]) 2
   1.268 +      (peek [[]]) []
   1.269 +      (peek [[] nil]) nil
   1.270 +      (peek [[] 2 nil]) nil ))
   1.271 +
   1.272 +
   1.273 +(deftest test-pop
   1.274 +  ; doesn't work for sets and maps
   1.275 +  (is (thrown? ClassCastException (pop #{1})))
   1.276 +  (is (thrown? ClassCastException (pop #{:a 1})))
   1.277 +
   1.278 +  ; collection cannot be empty
   1.279 +  (is (thrown? IllegalStateException (pop ())))
   1.280 +  (is (thrown? IllegalStateException (pop [])))
   1.281 +
   1.282 +  (are [x y] (= x y)
   1.283 +      (pop nil) nil
   1.284 +
   1.285 +      ; list - pop first
   1.286 +      (pop '(1)) ()
   1.287 +      (pop '(1 2 3)) '(2 3)
   1.288 +
   1.289 +      (pop '(nil)) ()
   1.290 +      (pop '(1 nil)) '(nil)
   1.291 +      (pop '(nil 2)) '(2)
   1.292 +      (pop '(())) ()
   1.293 +      (pop '(() nil)) '(nil)
   1.294 +      (pop '(() 2 nil)) '(2 nil)
   1.295 +
   1.296 +      ; vector - pop last
   1.297 +      (pop [1]) []
   1.298 +      (pop [1 2 3]) [1 2]
   1.299 +
   1.300 +      (pop [nil]) []
   1.301 +      (pop [1 nil]) [1]
   1.302 +      (pop [nil 2]) [nil]
   1.303 +      (pop [[]]) []
   1.304 +      (pop [[] nil]) [[]]
   1.305 +      (pop [[] 2 nil]) [[] 2] ))
   1.306 +
   1.307 +
   1.308 +;; *** Lists (IPersistentList) ***
   1.309 +
   1.310 +(deftest test-list
   1.311 +  (are [x]  (list? x)
   1.312 +      ()
   1.313 +      '()
   1.314 +      (list)
   1.315 +      (list 1 2 3) )
   1.316 +
   1.317 +  ; order is important
   1.318 +  (are [x y] (not (= x y))
   1.319 +      (list 1 2) (list 2 1)
   1.320 +      (list 3 1 2) (list 1 2 3) )
   1.321 +
   1.322 +  (are [x y] (= x y)
   1.323 +      '() ()
   1.324 +      (list) '()
   1.325 +      (list 1) '(1)
   1.326 +      (list 1 2) '(1 2)
   1.327 +
   1.328 +      ; nesting
   1.329 +      (list 1 (list 2 3) (list 3 (list 4 5 (list 6 (list 7)))))
   1.330 +        '(1 (2 3) (3 (4 5 (6 (7)))))
   1.331 +
   1.332 +      ; different data structures
   1.333 +      (list true false nil)
   1.334 +        '(true false nil)
   1.335 +      (list 1 2.5 2/3 "ab" \x 'cd :kw)
   1.336 +        '(1 2.5 2/3 "ab" \x cd :kw)
   1.337 +      (list (list 1 2) [3 4] {:a 1 :b 2} #{:c :d})
   1.338 +        '((1 2) [3 4] {:a 1 :b 2} #{:c :d})
   1.339 +
   1.340 +      ; evaluation
   1.341 +      (list (+ 1 2) [(+ 2 3) 'a] (list (* 2 3) 8))
   1.342 +        '(3 [5 a] (6 8))
   1.343 +
   1.344 +      ; special cases
   1.345 +      (list nil) '(nil)
   1.346 +      (list 1 nil) '(1 nil)
   1.347 +      (list nil 2) '(nil 2)
   1.348 +      (list ()) '(())
   1.349 +      (list 1 ()) '(1 ())
   1.350 +      (list () 2) '(() 2) ))
   1.351 +
   1.352 +
   1.353 +;; *** Maps (IPersistentMap) ***
   1.354 +
   1.355 +(deftest test-find
   1.356 +  (are [x y] (= x y)
   1.357 +      (find {} :a) nil
   1.358 +
   1.359 +      (find {:a 1} :a) [:a 1]
   1.360 +      (find {:a 1} :b) nil
   1.361 +
   1.362 +      (find {:a 1 :b 2} :a) [:a 1]
   1.363 +      (find {:a 1 :b 2} :b) [:b 2]
   1.364 +      (find {:a 1 :b 2} :c) nil
   1.365 +
   1.366 +      (find {} nil) nil
   1.367 +      (find {:a 1} nil) nil
   1.368 +      (find {:a 1 :b 2} nil) nil ))
   1.369 +
   1.370 +
   1.371 +(deftest test-contains?
   1.372 +  ; contains? is designed to work preferably on maps and sets
   1.373 +  (are [x y] (= x y)
   1.374 +      (contains? {} :a) false
   1.375 +      (contains? {} nil) false
   1.376 +
   1.377 +      (contains? {:a 1} :a) true
   1.378 +      (contains? {:a 1} :b) false
   1.379 +      (contains? {:a 1} nil) false
   1.380 +
   1.381 +      (contains? {:a 1 :b 2} :a) true
   1.382 +      (contains? {:a 1 :b 2} :b) true
   1.383 +      (contains? {:a 1 :b 2} :c) false
   1.384 +      (contains? {:a 1 :b 2} nil) false
   1.385 +
   1.386 +      ; sets
   1.387 +      (contains? #{} 1) false
   1.388 +      (contains? #{} nil) false
   1.389 +
   1.390 +      (contains? #{1} 1) true
   1.391 +      (contains? #{1} 2) false
   1.392 +      (contains? #{1} nil) false
   1.393 +
   1.394 +      (contains? #{1 2 3} 1) true
   1.395 +      (contains? #{1 2 3} 3) true
   1.396 +      (contains? #{1 2 3} 10) false
   1.397 +      (contains? #{1 2 3} nil) false)
   1.398 +
   1.399 +  ; numerically indexed collections (e.g. vectors and Java arrays)
   1.400 +  ; => test if the numeric key is WITHIN THE RANGE OF INDEXES
   1.401 +  (are [x y] (= x y)
   1.402 +      (contains? [] 0) false
   1.403 +      (contains? [] -1) false
   1.404 +      (contains? [] 1) false
   1.405 +
   1.406 +      (contains? [1] 0) true
   1.407 +      (contains? [1] -1) false
   1.408 +      (contains? [1] 1) false
   1.409 +
   1.410 +      (contains? [1 2 3] 0) true
   1.411 +      (contains? [1 2 3] 2) true
   1.412 +      (contains? [1 2 3] 3) false
   1.413 +      (contains? [1 2 3] -1) false
   1.414 +
   1.415 +      ; arrays
   1.416 +      (contains? (into-array []) 0) false
   1.417 +      (contains? (into-array []) -1) false
   1.418 +      (contains? (into-array []) 1) false
   1.419 +
   1.420 +      (contains? (into-array [1]) 0) true
   1.421 +      (contains? (into-array [1]) -1) false
   1.422 +      (contains? (into-array [1]) 1) false
   1.423 +
   1.424 +      (contains? (into-array [1 2 3]) 0) true
   1.425 +      (contains? (into-array [1 2 3]) 2) true
   1.426 +      (contains? (into-array [1 2 3]) 3) false
   1.427 +      (contains? (into-array [1 2 3]) -1) false)
   1.428 +
   1.429 +  ; 'contains?' operates constant or logarithmic time,
   1.430 +  ; it WILL NOT perform a linear search for a value.
   1.431 +  (are [x]  (= x false)
   1.432 +      (contains? '(1 2 3) 0)
   1.433 +      (contains? '(1 2 3) 1)
   1.434 +      (contains? '(1 2 3) 3)
   1.435 +      (contains? '(1 2 3) 10)
   1.436 +      (contains? '(1 2 3) nil)
   1.437 +      (contains? '(1 2 3) ()) ))
   1.438 +
   1.439 +
   1.440 +(deftest test-keys
   1.441 +  (are [x y] (= x y)      ; other than map data structures
   1.442 +      (keys ()) nil
   1.443 +      (keys []) nil
   1.444 +      (keys #{}) nil
   1.445 +      (keys "") nil )
   1.446 +
   1.447 +  (are [x y] (= x y)
   1.448 +      ; (class {:a 1}) => clojure.lang.PersistentArrayMap
   1.449 +      (keys {}) nil
   1.450 +      (keys {:a 1}) '(:a)
   1.451 +      (diff (keys {:a 1 :b 2}) '(:a :b)) nil              ; (keys {:a 1 :b 2}) '(:a :b)
   1.452 +
   1.453 +      ; (class (sorted-map :a 1)) => clojure.lang.PersistentTreeMap
   1.454 +      (keys (sorted-map)) nil
   1.455 +      (keys (sorted-map :a 1)) '(:a)
   1.456 +      (diff (keys (sorted-map :a 1 :b 2)) '(:a :b)) nil   ; (keys (sorted-map :a 1 :b 2)) '(:a :b)
   1.457 +
   1.458 +      ; (class (hash-map :a 1)) => clojure.lang.PersistentHashMap
   1.459 +      (keys (hash-map)) nil
   1.460 +      (keys (hash-map :a 1)) '(:a)
   1.461 +      (diff (keys (hash-map :a 1 :b 2)) '(:a :b)) nil ))  ; (keys (hash-map :a 1 :b 2)) '(:a :b)
   1.462 +
   1.463 +
   1.464 +(deftest test-vals
   1.465 +  (are [x y] (= x y)      ; other than map data structures
   1.466 +      (vals ()) nil
   1.467 +      (vals []) nil
   1.468 +      (vals #{}) nil
   1.469 +      (vals "") nil )
   1.470 +
   1.471 +  (are [x y] (= x y)
   1.472 +      ; (class {:a 1}) => clojure.lang.PersistentArrayMap
   1.473 +      (vals {}) nil
   1.474 +      (vals {:a 1}) '(1)
   1.475 +      (diff (vals {:a 1 :b 2}) '(1 2)) nil              ; (vals {:a 1 :b 2}) '(1 2)
   1.476 +
   1.477 +      ; (class (sorted-map :a 1)) => clojure.lang.PersistentTreeMap
   1.478 +      (vals (sorted-map)) nil
   1.479 +      (vals (sorted-map :a 1)) '(1)
   1.480 +      (diff (vals (sorted-map :a 1 :b 2)) '(1 2)) nil   ; (vals (sorted-map :a 1 :b 2)) '(1 2)
   1.481 +
   1.482 +      ; (class (hash-map :a 1)) => clojure.lang.PersistentHashMap
   1.483 +      (vals (hash-map)) nil
   1.484 +      (vals (hash-map :a 1)) '(1)
   1.485 +      (diff (vals (hash-map :a 1 :b 2)) '(1 2)) nil ))  ; (vals (hash-map :a 1 :b 2)) '(1 2)
   1.486 +
   1.487 +
   1.488 +(deftest test-key
   1.489 +  (are [x]  (= (key (first (hash-map x :value))) x)
   1.490 +      nil
   1.491 +      false true
   1.492 +      0 42
   1.493 +      0.0 3.14
   1.494 +      2/3
   1.495 +      0M 1M
   1.496 +      \c
   1.497 +      "" "abc"
   1.498 +      'sym
   1.499 +      :kw
   1.500 +      () '(1 2)
   1.501 +      [] [1 2]
   1.502 +      {} {:a 1 :b 2}
   1.503 +      #{} #{1 2} ))
   1.504 +
   1.505 +
   1.506 +(deftest test-val
   1.507 +  (are [x]  (= (val (first (hash-map :key x))) x)
   1.508 +      nil
   1.509 +      false true
   1.510 +      0 42
   1.511 +      0.0 3.14
   1.512 +      2/3
   1.513 +      0M 1M
   1.514 +      \c
   1.515 +      "" "abc"
   1.516 +      'sym
   1.517 +      :kw
   1.518 +      () '(1 2)
   1.519 +      [] [1 2]
   1.520 +      {} {:a 1 :b 2}
   1.521 +      #{} #{1 2} ))
   1.522 +
   1.523 +(deftest test-get
   1.524 +  (let [m {:a 1, :b 2, :c {:d 3, :e 4}, :f nil, :g false, nil {:h 5}}]
   1.525 +    (is (thrown? IllegalArgumentException (get-in {:a 1} 5)))
   1.526 +    (are [x y] (= x y)
   1.527 +         (get m :a) 1
   1.528 +         (get m :e) nil
   1.529 +         (get m :e 0) 0
   1.530 +         (get m :b 0) 2
   1.531 +         (get m :f 0) nil
   1.532 +
   1.533 +         (get-in m [:c :e]) 4
   1.534 +         (get-in m '(:c :e)) 4
   1.535 +         (get-in m [:c :x]) nil
   1.536 +         (get-in m [:f]) nil
   1.537 +         (get-in m [:g]) false
   1.538 +         (get-in m [:h]) nil
   1.539 +         (get-in m []) m
   1.540 +         (get-in m nil) m
   1.541 +
   1.542 +         (get-in m [:c :e] 0) 4
   1.543 +         (get-in m '(:c :e) 0) 4
   1.544 +         (get-in m [:c :x] 0) 0
   1.545 +         (get-in m [:b] 0) 2
   1.546 +         (get-in m [:f] 0) nil
   1.547 +         (get-in m [:g] 0) false
   1.548 +         (get-in m [:h] 0) 0
   1.549 +         (get-in m [:x :y] {:y 1}) {:y 1}
   1.550 +         (get-in m [] 0) m
   1.551 +         (get-in m nil 0) m)))
   1.552 +
   1.553 +;; *** Sets ***
   1.554 +
   1.555 +(deftest test-hash-set
   1.556 +  (are [x] (set? x)
   1.557 +      #{}
   1.558 +      #{1 2}
   1.559 +      (hash-set)
   1.560 +      (hash-set 1 2) )
   1.561 +
   1.562 +  ; order isn't important
   1.563 +  (are [x y] (= x y)
   1.564 +      #{1 2} #{2 1}
   1.565 +      #{3 1 2} #{1 2 3}
   1.566 +      (hash-set 1 2) (hash-set 2 1)
   1.567 +      (hash-set 3 1 2) (hash-set 1 2 3) )
   1.568 +
   1.569 +
   1.570 +  (are [x y] (= x y)
   1.571 +      ; equal classes
   1.572 +      (class #{}) (class (hash-set))
   1.573 +      (class #{1 2}) (class (hash-set 1 2))
   1.574 +
   1.575 +      ; creating
   1.576 +      (hash-set) #{}
   1.577 +      (hash-set 1) #{1}
   1.578 +      (hash-set 1 2) #{1 2}
   1.579 +
   1.580 +      ; nesting
   1.581 +      (hash-set 1 (hash-set 2 3) (hash-set 3 (hash-set 4 5 (hash-set 6 (hash-set 7)))))
   1.582 +        #{1 #{2 3} #{3 #{4 5 #{6 #{7}}}}}
   1.583 +
   1.584 +      ; different data structures
   1.585 +      (hash-set true false nil)
   1.586 +        #{true false nil}
   1.587 +      (hash-set 1 2.5 2/3 "ab" \x 'cd :kw)
   1.588 +        #{1 2.5 2/3 "ab" \x 'cd :kw}
   1.589 +      (hash-set (list 1 2) [3 4] {:a 1 :b 2} #{:c :d})
   1.590 +        #{'(1 2) [3 4] {:a 1 :b 2} #{:c :d}}
   1.591 +
   1.592 +      ; evaluation
   1.593 +      (hash-set (+ 1 2) [(+ 2 3) :a] (hash-set (* 2 3) 8))
   1.594 +        #{3 [5 :a] #{6 8}}
   1.595 +
   1.596 +      ; special cases
   1.597 +      (hash-set nil) #{nil}
   1.598 +      (hash-set 1 nil) #{1 nil}
   1.599 +      (hash-set nil 2) #{nil 2}
   1.600 +      (hash-set #{}) #{#{}}
   1.601 +      (hash-set 1 #{}) #{1 #{}}
   1.602 +      (hash-set #{} 2) #{#{} 2} ))
   1.603 +
   1.604 +
   1.605 +(deftest test-sorted-set
   1.606 +  ; only compatible types can be used
   1.607 +  (is (thrown? ClassCastException (sorted-set 1 "a")))
   1.608 +  (is (thrown? ClassCastException (sorted-set '(1 2) [3 4])))
   1.609 +
   1.610 +  ; creates set?
   1.611 +  (are [x] (set? x)
   1.612 +       (sorted-set)
   1.613 +       (sorted-set 1 2) )
   1.614 +
   1.615 +  ; equal and unique
   1.616 +  (are [x] (and (= (sorted-set x) #{x})
   1.617 +                (= (sorted-set x x) (sorted-set x)))
   1.618 +      nil
   1.619 +      false true
   1.620 +      0 42
   1.621 +      0.0 3.14
   1.622 +      2/3
   1.623 +      0M 1M
   1.624 +      \c
   1.625 +      "" "abc"
   1.626 +      'sym
   1.627 +      :kw
   1.628 +      ()  ; '(1 2)
   1.629 +      [] [1 2]
   1.630 +      {}  ; {:a 1 :b 2}
   1.631 +      #{} ; #{1 2}
   1.632 +  )
   1.633 +  ; cannot be cast to java.lang.Comparable
   1.634 +  (is (thrown? ClassCastException (sorted-set '(1 2) '(1 2))))
   1.635 +  (is (thrown? ClassCastException (sorted-set {:a 1 :b 2} {:a 1 :b 2})))
   1.636 +  (is (thrown? ClassCastException (sorted-set #{1 2} #{1 2})))
   1.637 +
   1.638 +  (are [x y] (= x y)
   1.639 +      ; generating
   1.640 +      (sorted-set) #{}
   1.641 +      (sorted-set 1) #{1}
   1.642 +      (sorted-set 1 2) #{1 2}
   1.643 +
   1.644 +      ; sorting
   1.645 +      (seq (sorted-set 5 4 3 2 1)) '(1 2 3 4 5)
   1.646 +
   1.647 +      ; special cases
   1.648 +      (sorted-set nil) #{nil}
   1.649 +      (sorted-set 1 nil) #{nil 1}
   1.650 +      (sorted-set nil 2) #{nil 2}
   1.651 +      (sorted-set #{}) #{#{}} ))
   1.652 +
   1.653 +
   1.654 +(deftest test-sorted-set-by
   1.655 +  ; only compatible types can be used
   1.656 +  ; NB: not a ClassCastException, but a RuntimeException is thrown,
   1.657 +  ; requires discussion on whether this should be symmetric with test-sorted-set
   1.658 +  (is (thrown? Exception (sorted-set-by < 1 "a")))
   1.659 +  (is (thrown? Exception (sorted-set-by < '(1 2) [3 4])))
   1.660 +
   1.661 +  ; creates set?
   1.662 +  (are [x] (set? x)
   1.663 +       (sorted-set-by <)
   1.664 +       (sorted-set-by < 1 2) )
   1.665 +
   1.666 +  ; equal and unique
   1.667 +  (are [x] (and (= (sorted-set-by compare x) #{x})
   1.668 +                (= (sorted-set-by compare x x) (sorted-set-by compare x)))
   1.669 +      nil
   1.670 +      false true
   1.671 +      0 42
   1.672 +      0.0 3.14
   1.673 +      2/3
   1.674 +      0M 1M
   1.675 +      \c
   1.676 +      "" "abc"
   1.677 +      'sym
   1.678 +      :kw
   1.679 +      ()  ; '(1 2)
   1.680 +      [] [1 2]
   1.681 +      {}  ; {:a 1 :b 2}
   1.682 +      #{} ; #{1 2}
   1.683 +  )
   1.684 +  ; cannot be cast to java.lang.Comparable
   1.685 +  ; NB: not a ClassCastException, but a RuntimeException is thrown,
   1.686 +  ; requires discussion on whether this should be symmetric with test-sorted-set
   1.687 +  (is (thrown? Exception (sorted-set-by compare '(1 2) '(1 2))))
   1.688 +  (is (thrown? Exception (sorted-set-by compare {:a 1 :b 2} {:a 1 :b 2})))
   1.689 +  (is (thrown? Exception (sorted-set-by compare #{1 2} #{1 2})))
   1.690 +
   1.691 +  (are [x y] (= x y)
   1.692 +      ; generating
   1.693 +      (sorted-set-by >) #{}
   1.694 +      (sorted-set-by > 1) #{1}
   1.695 +      (sorted-set-by > 1 2) #{1 2}
   1.696 +
   1.697 +      ; sorting
   1.698 +      (seq (sorted-set-by < 5 4 3 2 1)) '(1 2 3 4 5)
   1.699 +
   1.700 +      ; special cases
   1.701 +      (sorted-set-by compare nil) #{nil}
   1.702 +      (sorted-set-by compare 1 nil) #{nil 1}
   1.703 +      (sorted-set-by compare nil 2) #{nil 2}
   1.704 +      (sorted-set-by compare #{}) #{#{}} ))
   1.705 +
   1.706 +
   1.707 +(deftest test-set
   1.708 +  ; set?
   1.709 +  (are [x] (set? (set x))
   1.710 +      () '(1 2)
   1.711 +      [] [1 2]
   1.712 +      #{} #{1 2}
   1.713 +      {} {:a 1 :b 2}
   1.714 +      (into-array []) (into-array [1 2])
   1.715 +      "" "abc" )
   1.716 +
   1.717 +  ; unique
   1.718 +  (are [x] (= (set [x x]) #{x})
   1.719 +      nil
   1.720 +      false true
   1.721 +      0 42
   1.722 +      0.0 3.14
   1.723 +      2/3
   1.724 +      0M 1M
   1.725 +      \c
   1.726 +      "" "abc"
   1.727 +      'sym
   1.728 +      :kw
   1.729 +      () '(1 2)
   1.730 +      [] [1 2]
   1.731 +      {} {:a 1 :b 2}
   1.732 +      #{} #{1 2} )
   1.733 +
   1.734 +  ; conversion
   1.735 +  (are [x y] (= (set x) y)
   1.736 +      () #{}
   1.737 +      '(1 2) #{1 2}
   1.738 +
   1.739 +      [] #{}
   1.740 +      [1 2] #{1 2}
   1.741 +
   1.742 +      #{} #{}         ; identity
   1.743 +      #{1 2} #{1 2}   ; identity
   1.744 +
   1.745 +      {} #{}
   1.746 +      {:a 1 :b 2} #{[:a 1] [:b 2]}
   1.747 +
   1.748 +      (into-array []) #{}
   1.749 +      (into-array [1 2]) #{1 2}
   1.750 +
   1.751 +      "" #{}
   1.752 +      "abc" #{\a \b \c} ))
   1.753 +
   1.754 +
   1.755 +(deftest test-disj
   1.756 +  ; doesn't work on lists, vectors or maps
   1.757 +  (is (thrown? ClassCastException (disj '(1 2) 1)))
   1.758 +  (is (thrown? ClassCastException (disj [1 2] 1)))
   1.759 +  (is (thrown? ClassCastException (disj {:a 1} :a)))
   1.760 +
   1.761 +  ; identity
   1.762 +  (are [x] (= (disj x) x)
   1.763 +      nil
   1.764 +      #{}
   1.765 +      #{1 2 3}
   1.766 +      ; different data types
   1.767 +      #{nil
   1.768 +        false true
   1.769 +        0 42
   1.770 +        0.0 3.14
   1.771 +        2/3
   1.772 +        0M 1M
   1.773 +        \c
   1.774 +        "" "abc"
   1.775 +        'sym
   1.776 +        :kw
   1.777 +        [] [1 2]
   1.778 +        {} {:a 1 :b 2}
   1.779 +        #{} #{1 2}} )
   1.780 +
   1.781 +  ; type identity
   1.782 +  (are [x] (= (class (disj x)) (class x))
   1.783 +      (hash-set)
   1.784 +      (hash-set 1 2)
   1.785 +      (sorted-set)
   1.786 +      (sorted-set 1 2) )
   1.787 +
   1.788 +  (are [x y] (= x y)
   1.789 +      (disj nil :a) nil
   1.790 +      (disj nil :a :b) nil
   1.791 +
   1.792 +      (disj #{} :a) #{}
   1.793 +      (disj #{} :a :b) #{}
   1.794 +
   1.795 +      (disj #{:a} :a) #{}
   1.796 +      (disj #{:a} :a :b) #{}
   1.797 +      (disj #{:a} :c) #{:a}
   1.798 +
   1.799 +      (disj #{:a :b :c :d} :a) #{:b :c :d}
   1.800 +      (disj #{:a :b :c :d} :a :d) #{:b :c}
   1.801 +      (disj #{:a :b :c :d} :a :b :c) #{:d}
   1.802 +      (disj #{:a :b :c :d} :d :a :c :b) #{}
   1.803 +
   1.804 +      (disj #{nil} :a) #{nil}
   1.805 +      (disj #{nil} #{}) #{nil}
   1.806 +      (disj #{nil} nil) #{}
   1.807 +
   1.808 +      (disj #{#{}} nil) #{#{}}
   1.809 +      (disj #{#{}} #{}) #{}
   1.810 +      (disj #{#{nil}} #{nil}) #{} ))
   1.811 +
   1.812 +
   1.813 +;; *** Queues ***
   1.814 +
   1.815 +(deftest test-queues
   1.816 +  (let [EMPTY clojure.lang.PersistentQueue/EMPTY]
   1.817 +    (are [x y] (= x y)
   1.818 +      EMPTY EMPTY
   1.819 +      (into EMPTY (range 50)) (into EMPTY (range 50))
   1.820 +      (range 5) (into EMPTY (range 5))
   1.821 +      (range 1 6) (-> EMPTY
   1.822 +                    (into (range 6))
   1.823 +                    pop))
   1.824 +    (are [x y] (not= x y)
   1.825 +      (range 5) (into EMPTY (range 6))
   1.826 +      (range 6) (into EMPTY (range 5))
   1.827 +      (range 0 6) (-> EMPTY
   1.828 +                    (into (range 6))
   1.829 +                    pop)
   1.830 +      (range 1 6) (-> EMPTY
   1.831 +                    (into (range 7))
   1.832 +                    pop))))
   1.833 +