How do I use a treemap for a 2 dimensional keys?

Question

I want to map a large number of tuples. My map looks something like:

{[1 2] :thing}

Except there may be a few million of them. I have a feeling that a tree-map might be a good thing to test so I'm trying to get it working. I can't seem to get the comparison function right though.

(defn compare 
  [[x y] [xx yy]]
  (cond
   (and (= x xx) (= y yy)) 0
   (and (<= x xx) (<= y yy)) -1
   (and (<= x xx) (> y yy)) -1
   (and (> x xx) (<= y yy)) 1
   (and (> x xx) (> y yy)) 1))

Some trivial inputs seem to work

user=> (compare [1 1] [1 1])
0
user=> (compare [1 1] [2 2])
-1
user=> (compare [1 2] [2 1])
-1
user=> (compare [2 1] [1 2])
1

But if I create inputs that cover all combinations, the map should consider them all different.

(def inputs
    "All tuples of [0-4, 5-10]."
    (clojure.math.combinatorics/cartesian-product
      (range 0 4) 
      (range 5 10)))

(def input-pairs
     "All possible pairs of tuples"
     (clojure.math.combinatorics/cartesian-product inputs inputs))

If I test the comparison function, it returns zero only when the two vectors are structurally identical.

user=> (doseq [[a b] input-pairs]
  #_=>   (when (zero? (compare a b)) (prn a b)))
(0 5) (0 5)
(0 6) (0 6)
(0 7) (0 7)
(0 8) (0 8)
(0 9) (0 9)
(1 5) (1 5)
etc

So I think my compare function is correct. Using it in the treemap, however, gives some strange results:

(def inputs-kvs
    "Inputs in the format that the hash-map and sorted-map constructor understand"
    (mapcat #(vector % (apply str %))
            (clojure.math.combinatorics/cartesian-product
              (range 0 4) 
              (range 5 10))))

Putting these in a hashmap gives the correct answer

(count (apply assoc (hash-map) inputs-kvs))
=> 20

But putting them in the treemap with the given comparison:

(def structure (sorted-map-by compare))
(count (apply assoc structure inputs-kvs))
=> 4

(apply assoc structure inputs-kvs)
=> {(0 5) "25", (1 6) "36", (2 7) "37", (3 5) "39"}

"25" has been stored in the (0 5) slot. But the compare function doesn't say that (0 5) and (2 5) are the same:

=> (compare [0 5] [2 5])
-1

What am I doing wrong? Can I make this work? Is it even meaningful to project a 2-dimensional space onto a 1-dimensional one?

(To head off a question you may have, yes I've tried a 2-dimensional structure, e.g. (sorted-map 1 (sorted-map 2 :value)), but I'm trying to find alternatives with better performance)

Answer 1

Clojure already comes with it's own compare:

user=> (doc compare)
-------------------------
clojure.core/compare
([x y])
  Comparator. Returns a negative number, zero, or a positive number
  when x is logically 'less than', 'equal to', or 'greater than'
  y. Same as Java x.compareTo(y) except it also works for nil, and
  compares numbers and collections in a type-independent manner. x
  must implement Comparable

Which behaves the same as OPs own function, but most likely is more efficient:

user=> (compare [1 1] [1 1])
0
user=> (compare [1 1] [2 2])
-1
user=> (compare [2 1] [1 2])
1

The behaviour is documented in the Section about Vectors (IPersistentVector) in the Data Structures docs:

Vectors are compared first by length, then each element is compared in order.

So you can just use sorted-map-by compare from core, or since that's the default anyway just sorted-map for your data structure:

user=> (def m (into {} (let [r #(- (rand-int 10) (rand-int 10))] (for [a (range -1 2) b (range -1 2)] [[(r) (r)] (str a b)]))))
#'user/m
user=> (>pprint m)
{[-7 -4] "10",
 [-3 5] "01",
 [-5 -7] "00",
 [5 2] "11",
 [-3 1] "-10",
 [7 -4] "-11",
 [0 -6] "0-1",
 [3 1] "-1-1",
 [-8 -1] "1-1"}
nil
user=> (>pprint (into (sorted-map-by compare) m))
{[-8 -1] "1-1",
 [-7 -4] "10",
 [-5 -7] "00",
 [-3 1] "-10",
 [-3 5] "01",
 [0 -6] "0-1",
 [3 1] "-1-1",
 [5 2] "11",
 [7 -4] "-11"}
nil
user=> (>pprint (into (sorted-map) m))
{[-8 -1] "1-1",
 [-7 -4] "10",
 [-5 -7] "00",
 [-3 1] "-10",
 [-3 5] "01",
 [0 -6] "0-1",
 [3 1] "-1-1",
 [5 2] "11",
 [7 -4] "-11"}
nil
user=> (assert (= (into (sorted-map-by compare) m) (into (sorted-map) m)))
nil

Answer 2

I just added (vec %) to keep the tuples vectors - should not change anything.

As you can see it works here.

Might it be you have a some older REPL stuff laying around - especially since you alias clojure.core/compare ?

; using your compare function
(def inp (mapcat #(vector (vec %) (apply str %)) 
  (clojure.math.combinatorics/cartesian-product (range 0 4) (range 5 10))))
; => ([0 5] "05" [0 6] "06" [0 7] "07" [0 8] "08" ...
(count inp) 
; => 40 
(apply assoc structure inp)
; => {[0 9] "09", [0 8] "08", [0 7] "07", [0 6] "06", ....
(count (apply assoc structure inp))
; => 20