ztellman/immutable-int-map — pull request #1 by glenjamin (2014-05-08 23:09:59+00:00)
Title: Add efficient rseq support

I'm fairly new to simple-check and the protocols and data-types side of clojure, so please be as picky as you like on the review :)

Since we have a sorted map, i figure it should be easy enough to do a reverse sequence.

I note that the existing `Seq` implementation is not lazy, so i've just implemented a basic reverse iterator around this rather than walking the tree right-first - I was actually fairly surprised core clojure doesn't provide Reversible for ArrayLists already.

Below is a benchmark showing this provides very little overhead vs a forward sequence.

Would you be interested in a properly lazy implementation of Seq? I'm only about halfway through the paper that describes Patricia trees, so I'm not 100% clear if this is possible (I think yes?)

```
user=> (require '[immutable-int-map-test :as it]
#_=> '[immutable-int-map :as i]
#_=> '[criterium.core :as c])
nil
user=>

user=> (let [m (into (i/int-map) it/entries)]
#_=> (println "seq")
#_=> (c/quick-bench (seq m))
#_=> (println "rseq")
#_=> (c/quick-bench (rseq m)))
seq
WARNING: Final GC required 250.84424916979708 % of runtime
Evaluation count : 24 in 6 samples of 4 calls.
Execution time mean : 25.983582 ms
Execution time std-deviation : 933.981058 µs
Execution time lower quantile : 25.099248 ms ( 2.5%)
Execution time upper quantile : 26.978498 ms (97.5%)
Overhead used : 1.811797 ns
rseq
WARNING: Final GC required 186.5399445093766 % of runtime
Evaluation count : 24 in 6 samples of 4 calls.
Execution time mean : 26.184582 ms
Execution time std-deviation : 927.418740 µs
Execution time lower quantile : 24.723498 ms ( 2.5%)
Execution time upper quantile : 26.955748 ms (97.5%)
Overhead used : 1.811797 ns
nil
```