Commits

Michał Marczyk  committed 9ea8a60

0.0.3: chunked seqs, reduce-kv

  • Participants
  • Parent commits e6fb71d
  • Tags 0.0.3

Comments (0)

Files changed (4)

 
 Current TODO list:
 
- 1. features: chunked seqs, transients;
+ 1. tests;
 
- 2. performance: general perf tuning, efficient `catvec`
+ 2. benchmarks;
+
+ 3. performance: general perf tuning, efficient `catvec`
     implementation (to replace current seq-ops-based impl);
 
- 3. benchmarks;
+ 4. transients;
 
- 4. tests;
- 
  5. ClojureScript version.
 
 ## Clojure(Script) code reuse
-(defproject flexvec "0.0.2"
+(defproject flexvec "0.0.3"
   :description "RRB-Trees for Clojure(Script) -- see Bagwell & Rompf"
   :url "https://github.com/michalmarczyk/flexvec"
   :license {:name "Eclipse Public License"

File src/flexvec/rrbt.clj

                                    replace-rightmost-child
                                    fold-tail new-path index-of-nil
                                    object-am object-nm primitive-nm
-                                   pv-shift pv-root pv-tail]])
-  (:import (clojure.core ArrayManager Vec)
+                                   pv-shift pv-root pv-tail]]
+            [clojure.core.protocols :refer [IKVReduce]])
+  (:import (clojure.core ArrayManager Vec VecSeq)
            (clojure.lang Util Box PersistentVector APersistentVector$SubVector)
-           (flexvec.nodes NodeManager)))
+           (flexvec.nodes NodeManager)
+           (java.util.concurrent.atomic AtomicReference)))
 
 (def ^:const rrbt-concat-threshold 33)
 (def ^:const max-extra-search-steps 2)
           (throw (IndexOutOfBoundsException.))))
       (throw (IllegalArgumentException. "Key must be integer"))))
 
+  ;; hack to reuse gvec's chunked seqs
+  clojure.core.IVecImpl
+
   clojure.lang.Seqable
   (seq [this]
-    (iterator-seq (.iterator this)))
+    (if (zero? cnt)
+      nil
+      (VecSeq. am this (.arrayFor this 0) 0 0)))
 
   clojure.lang.Sequential
 
             (aset new-rngs 32 (unchecked-dec-int (aget new-rngs (int 32))))
             (.node nm (.edit nm root) arr))))))
 
-  (newPath [this edit shift node]
+  (newPath [this ^AtomicReference edit ^int shift node]
     (if (== (.alength am tail) (int 32))
       (let [shift (int shift)]
         (loop [s (int 0) node node]
                           val))
           (.node nm (.edit nm node) arr)))))
 
+  IKVReduce
+  (kv-reduce [this f init]
+    (loop [i (int 0)
+           j (int 0)
+           init init
+           arr  (.arrayFor this i)
+           lim  (unchecked-dec-int (.alength am arr))
+           step (unchecked-inc-int lim)]
+      (let [init (f init (unchecked-add-int i j) (.aget am arr j))]
+        (if (reduced? init)
+          @init
+          (if (< j lim)
+            (recur i (unchecked-inc-int j) init arr lim step)
+            (let [i (unchecked-add-int i step)]
+              (if (< i cnt)
+                (let [arr (.arrayFor this i)
+                      len (.alength am arr)
+                      lim (unchecked-dec-int len)]
+                  (recur i (int 0) init arr lim len))
+                init)))))))
+  
   PSliceableVector
   (slicev [this start end]
     (let [start   (int start)

File test/flexvec/core_test.clj

             [flexvec.debug :as dv])
   (:use clojure.test))
 
-(defn rangev [& args]
-  (vec (apply range args)))
-
-(defn rangevs [& args]
-  (mapv rangev args))
-
 (deftest test-slicing
   (testing "slicing"
     (is (dv/check-subvec 32000 10 29999 1234 18048 10123 10191))))
   (testing "splicing"
     (is (dv/check-catvec 1025 1025 3245 1025 32768 1025 1025 10123 1025 1025))
     (is (apply dv/check-catvec (repeat 30 33)))))
+
+(deftest test-reduce
+  (let [v1 (vec (range 128))
+        v2 (fv/vec (range 128))]
+    (testing "reduce"
+      (is (= (reduce + v1) (reduce + v2))))
+    (testing "reduce-kv"
+      (is (= (reduce-kv + 0 v1) (reduce-kv + 0 v2))))))
+
+(deftest test-seq
+  (let [v (fv/vec (range 128))
+        s (seq v)]
+    (testing "seq contents"
+      (is (= v s)))
+    (testing "chunked-seq?"
+      (is (chunked-seq? s)))
+    (testing "internal-reduce"
+      (is (satisfies? clojure.core.protocols/InternalReduce s)))))