Tracking the bounding box of a map

Question

Context

I have a bunch of data points that look roughly like this:

(defn rand-key []
  (into [] (repeatedly 3 #(- (rand-int 19) 9))))

(defn rand-val []
  (rand-nth [:foo :bar :baz :qux]))

(def data (into {} (repeatedly 10 (fn [] [(rand-key) (rand-val)]))))

Obviously the actual coordinates would have a much greater range, the actual values would hold some sort of information, and the actual number of data points would be far greater, but you get the idea.

This data structure is going to be evolving over time (so I'll probably store it in an atom or something like that), and as it evolves, I want to be able to quickly find the bounding box for the points it contains in its current state.

The easiest way to do that for an n-dimensional dataset is to keep n independent sets of its keys, each one sorted in one dimension. Since I can't be bothered to write a proper comparator in Clojure, though, I'm going to replace each of those sets with a sorted map from a coordinate in a particular dimension to the number of data points that have that coordinate in that dimension:

(def keymaps (mapv (fn [dimension]
                     (->> (keys data)
                          (map #(get % dimension))
                          frequencies
                          (into (sorted-map))))
                   (range 3)))

With this, it's trivial to find the bounding box of the dataset:

(def bounds (mapv (juxt (comp key first) (comp key first rseq)) keymaps))

Problem

Now, no matter what I do, I have to update my data and my keymaps together. Maybe, like I suggested above, I have an atom that stores some current state, and in that case that atom would look like this:

(def state (atom {:data data :keymaps keymaps}))

Any time I update state, I can't just use the built-in Clojure functions to update the :data because that would cause the :keymaps to become outdated. I could write my own functions to replace assoc and dissoc that would keep the two in sync, but then I wouldn't be able to make use of all the great higher-level functions (such as merge) that are built on top of the original, polymorphic assoc and dissoc.

Solution

So I decided to take the most painful approach possible: build a custom map type that allows efficient bounding box queries using the scheme detailed above. First things first, some protocols:

(defprotocol Space
  (dimension [this]))

(defprotocol Bounded
  (bounds [this]))

Since I need to store extra data alongside an existing map, I can't just use extend-type on the PersistentHashMap class. No, I need a far more powerful tool: deftype! I'll have one field for the underlying data map and another for the vector of keymaps.

In most cases, I could get away with just implementing the map abstraction directly, but I don't want to tie myself to a particular implementation for the wrapped map. What if later I decide that I want to use a quadtree or an octree for the underlying map, to allow for efficient queries of subspaces? To prevent myself from having to extend more protocols to my bounded map type than I need to, I'll just provide a way to get the wrapped map and query that:

(defprotocol Wrapper
  (wrapped [this]))

And here's the deftype itself. Prepare for boilerplate:

(import (clojure.lang Associative
                      Counted
                      ILookup
                      IPersistentCollection
                      IPersistentMap
                      Seqable))

(declare ->BoundedMap)

(deftype BoundedMap [m keymaps]
  Seqable
  (seq [_] (seq m))

  IPersistentCollection
  (cons [this [k v]] (assoc this k v))
  (empty [_] (->BoundedMap (empty m) (mapv empty keymaps)))
  (equiv [_ x] (= m x))

  ILookup
  (valAt [_ k] (get m k))
  (valAt [_ k not-found] (get m k not-found))

  Associative
  (containsKey [_ k] (contains? m k))
  (entryAt [_ k] (find m k))

  Counted
  (count [_] (count m))

  IPersistentMap
  (assoc [_ k v]
    (->BoundedMap (assoc m k v)
                  (if (contains? m k)
                    keymaps
                    (mapv #(update %1 %2 (fnil inc 0)) keymaps k))))
  (without [_ k]
    (->BoundedMap (dissoc m k)
                  (if (contains? m k)
                    (mapv #(if (< 1 (get %1 %2))
                             (update %1 %2 dec)
                             (dissoc %1 %2))
                          keymaps k)
                    keymaps)))

  Wrapper
  (wrapped [_] m)

  Space
  (dimension [_] (count keymaps))

  Bounded
  (bounds [_]
    (mapv (fn [keymap] (mapv #(key (first (% keymap))) [seq rseq])) keymaps)))

And of course, what data structure would be complete without a nifty little constructor function?

(defn bounded-map [dimension m]
  (->> (keys m)
       (iterate (partial map rest))
       (take dimension)
       (mapv #(into (sorted-map) (frequencies (map first %))))
       (->BoundedMap m)))

Now I can define my atom like this instead of what I had before:

(def state (atom (bounded-map 3 data)))

Pretty much all of the Clojure tools for maps will work properly, I can get bounding boxes at my leisure, and if I ever switch to a more featured map implementation for the data itself, I can always compose those extra functions with wrapped.

Questions

• Is this the right approach?
• Is there a way to make = work properly without implementing java.util.Map (yuck)?
• Can this code be improved in any other way?

Answer 1

I don't know Clojure but it looks like the keys are vectors and that the (mapped) values don't matter for the question/answer. I may be mistaken, but if I'm not, the question is just about keeping track of the bounding box of a vector set.

Let D be the number of dimensions and introduce Vᵢ (1 ≤ i ≤ D) where Vᵢ = the list of the current vectors sorted according to their iᵗʰ component. Then the bounding box along the iᵗʰ axis is given by [Vᵢ(first)..Vᵢ(last)] That defines the D-dimensional bounding box and it can be computed in O(D) time. Keeping it in a variable makes retrieving it O(1).

Adding/deleting a vector is easy: just insert/delete it into/from each Vᵢ which can be done in O(log N). The total cost is O(D log N). The cost of next updating the variable that holds the bounding box can be done in O(D) for those operations (PS: so the variable doesn't actually make a lot of sense since its value can also be computed from scratch at the same costs; depending on context improvements can be made by using by using a cache and cache invalidation... But never mind, it doesn't matter for the algorithm).

Hence an O(D log N) algorithm is feasible.

I don't know Clojure so I can't comment on correctness/elegance of your code. The parts I did grasp suggest that your ideas implement the above algorithm, so - disregarding any silly bugs there might be - the code seems fine.