Created
February 10, 2010 21:55
-
-
Save richhickey/300895 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
; Copyright (c) Rich Hickey. All rights reserved. | |
; The use and distribution terms for this software are covered by the | |
; Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php) | |
; which can be found in the file epl-v10.html at the root of this distribution. | |
; By using this software in any fashion, you are agreeing to be bound by | |
; the terms of this license. | |
; You must not remove this notice, or any other, from this software. | |
(set! *warn-on-reflection* true) | |
(deftype VecNode [edit arr]) | |
(def EMPTY-NODE (VecNode nil (object-array 32))) | |
(definterface IVecImpl | |
(#^int tailoff []) | |
(arrayFor [#^int i]) | |
(pushTail [#^int level parent tailnode]) | |
(popTail [#^int level node]) | |
(newPath [edit #^int level node]) | |
(doAssoc [#^int level node #^int i val])) | |
(deftype VecSeq [#^user.IVecImpl vec #^objects anode #^int i #^int offset] | |
:as this | |
:no-print true | |
clojure.lang.ISeq | |
(first [] (aget anode offset)) | |
(next [] | |
(if (< (inc offset) (alength anode)) | |
(VecSeq. vec anode i (inc offset)) | |
(.chunkedNext this))) | |
(more [] | |
(let [s (.next this)] | |
(or s (clojure.lang.PersistentList/EMPTY)))) | |
clojure.lang.Seqable | |
(seq [] this) | |
clojure.lang.IChunkedSeq | |
(chunkedFirst [] (clojure.lang.ArrayChunk. anode offset)) | |
(chunkedNext [] | |
(let [nexti (+ i (alength anode))] | |
(when (< nexti (count vec)) | |
(VecSeq. vec (.arrayFor vec nexti) nexti 0)))) | |
(chunkedMore [] | |
(let [s (.chunkedNext this)] | |
(or s (clojure.lang.PersistentList/EMPTY))))) | |
(defmethod print-method ::VecSeq [v w] | |
((get (methods print-method) clojure.lang.ISeq) v w)) | |
(deftype Vec [#^int cnt #^int shift root #^objects tail] | |
:as this | |
:no-print true | |
Object | |
(equals [o] | |
(cond | |
(or (instance? clojure.lang.IPersistentVector o) (instance? java.util.RandomAccess o)) | |
(and (= cnt (count o)) | |
(loop [i (int 0)] | |
(cond | |
(= i cnt) true | |
(.equals (.nth this i) (nth o i)) (recur (inc i)) | |
:else false))) | |
(or (instance? clojure.lang.Sequential o) (instance? java.util.List o)) | |
(.equals (seq this) (seq o)) | |
:else false)) | |
;todo - cache | |
(hashCode [] | |
(loop [hash (int 1) i (int 0)] | |
(if (= i cnt) | |
hash | |
(let [val (.nth this i)] | |
(recur (unchecked-add (unchecked-multiply (int 31) hash) | |
(clojure.lang.Util/hash val)) | |
(inc i)))))) | |
clojure.lang.Counted | |
(count [] cnt) | |
clojure.lang.Indexed | |
(nth [i] | |
(let [a (.arrayFor this i)] | |
(aget #^objects a (bit-and i (int 0x1f))))) | |
clojure.lang.IPersistentCollection | |
(cons [val] | |
(if (< (- cnt (.tailoff this)) (int 32)) | |
(let [new-tail (object-array (inc (alength tail)))] | |
(System/arraycopy tail 0 new-tail 0 (alength tail)) | |
(aset new-tail (alength tail) val) | |
(new Vec (inc cnt) shift root new-tail (meta this) nil)) | |
(let [tail-node (VecNode (:edit root) tail)] | |
(if (> (bit-shift-right cnt (int 5)) (bit-shift-left (int 1) shift)) ;overflow root? | |
(let [new-root (VecNode (:edit root) (object-array 32))] | |
(doto (:arr new-root) | |
(aset 0 root) | |
(aset 1 (.newPath this (:edit root) shift tail-node))) | |
(Vec. (inc cnt) (+ shift (int 5)) new-root (doto (object-array 1) (aset 0 val)) (meta this) nil)) | |
(Vec. (inc cnt) shift (.pushTail this shift root tail-node) | |
(doto (object-array 1) (aset 0 val)) (meta this) nil))))) | |
(empty [] (Vec. 0 5 EMPTY-NODE (object-array 0))) | |
(equiv [o] | |
(cond | |
(or (instance? clojure.lang.IPersistentVector o) (instance? java.util.RandomAccess o)) | |
(and (= cnt (count o)) | |
(loop [i (int 0)] | |
(cond | |
(= i cnt) true | |
(= (.nth this i) (nth o i)) (recur (inc i)) | |
:else false))) | |
(or (instance? clojure.lang.Sequential o) (instance? java.util.List o)) | |
(= (seq this) (seq o)) | |
:else false)) | |
clojure.lang.IPersistentStack | |
(peek [] | |
(when (> cnt (int 0)) | |
(.nth this (dec cnt)))) | |
(pop [] | |
(cond | |
(zero? cnt) | |
(throw (IllegalStateException. "Can't pop empty vector")) | |
(= 1 cnt) | |
(Vec. 0 5 EMPTY-NODE (object-array 0) (meta this) nil) | |
(> (- cnt (.tailoff this)) 1) | |
(let [new-tail (object-array (dec (alength tail)))] | |
(System/arraycopy tail 0 new-tail 0 (alength new-tail)) | |
(Vec. (dec cnt) shift root new-tail (meta this) nil)) | |
:else | |
(let [new-tail (.arrayFor this (- cnt 2)) | |
new-root (.popTail this shift root)] | |
(cond | |
(nil? new-root) | |
(Vec. (dec cnt) shift EMPTY-NODE new-tail (meta this) nil) | |
(and (> shift 5) (nil? (aget #^objects (:arr new-root) 1))) | |
(Vec. (dec cnt) (- shift 5) (aget #^objects (:arr new-root) 0) new-tail (meta this) nil) | |
:else | |
(Vec. (dec cnt) shift new-root new-tail (meta this) nil))))) | |
clojure.lang.IPersistentVector | |
(assocN [i val] | |
(cond | |
(and (<= (int 0) i) (< i cnt)) | |
(if (>= i (.tailoff this)) | |
(let [new-tail (object-array (alength tail))] | |
(System/arraycopy tail 0 new-tail 0 (alength tail)) | |
(aset new-tail (bit-and i (int 0x1f)) val) | |
(Vec. cnt shift root new-tail (meta this) nil)) | |
(Vec. cnt shift (.doAssoc this shift root i val) tail (meta this) nil)) | |
(= i cnt) (.cons this val) | |
:else (throw (IndexOutOfBoundsException.)))) | |
clojure.lang.Associative | |
(assoc [k v] | |
(if (clojure.lang.Util/isInteger k) | |
(.assocN this k v) | |
(throw (IllegalArgumentException. "Key must be integer")))) | |
clojure.lang.ILookup | |
(valAt [k not-found] | |
(if (clojure.lang.Util/isInteger k) | |
(let [i (int k)] | |
(if (and (>= i 0) (< i cnt)) | |
(.nth this i) | |
not-found)) | |
not-found)) | |
(valAt [k] (.valAt this k nil)) | |
clojure.lang.Seqable | |
(seq [] | |
(if (zero? cnt) | |
nil | |
(VecSeq this (.arrayFor this 0) 0 0))) | |
clojure.lang.Sequential ;marker, no methods | |
user.IVecImpl | |
(tailoff [] | |
(- cnt (alength tail))) | |
(arrayFor [i] | |
(if (and (<= (int 0) i) (< i cnt)) | |
(if (>= i (.tailoff this)) | |
tail | |
(loop [node root level shift] | |
(if (zero? level) | |
(:arr node) | |
(recur (aget #^objects (:arr node) (bit-and (bit-shift-right i level) (int 0x1f))) | |
(- level (int 5)))))) | |
(throw (IndexOutOfBoundsException.)))) | |
(pushTail [level parent tailnode] | |
(let [subidx (bit-and (bit-shift-right (dec cnt) level) (int 0x1f)) | |
ret (VecNode (:edit parent) (aclone #^objects (:arr parent))) | |
node-to-insert (if (= level (int 5)) | |
tailnode | |
(let [child (aget (:arr parent) subidx)] | |
(if child | |
(.pushTail this (- level (int 5)) child tailnode) | |
(.newPath this (:edit root) (- level (int 5)) tailnode))))] | |
(aset #^objects (:arr ret) subidx node-to-insert) | |
ret)) | |
(popTail [level node] | |
(let [subidx (bit-and (bit-shift-right (- cnt 2) level) (int 0x1f))] | |
(cond | |
(> level 5) | |
(let [new-child (.popTail this (- level 5) (aget #^objects (:arr node) subidx))] | |
(if (and (nil? new-child) (zero? subidx)) | |
nil | |
(let [arr (aclone #^objects (:arr node))] | |
(aset arr subidx new-child) | |
(VecNode (:edit root) arr)))) | |
(zero? subidx) nil | |
:else (let [arr (aclone #^objects (:arr node))] | |
(aset arr subidx nil) | |
(VecNode (:edit root) arr))))) | |
(newPath [edit #^int level node] | |
(if (zero? level) | |
node | |
(let [ret (VecNode edit (object-array 32))] | |
(aset (:arr ret) 0 (.newPath this edit (- level (int 5)) node)) | |
ret))) | |
(doAssoc [level node i val] | |
(if (zero? level) | |
;on this branch, array will need val type | |
(let [arr (aclone #^objects (:arr node))] | |
(aset arr (bit-and i (int 0x1f)) val) | |
(VecNode (:edit node) arr)) | |
(let [arr (aclone #^objects (:arr node)) | |
subidx (bit-and (bit-shift-right i level) (int 0x1f))] | |
(aset arr subidx (.doAssoc this (- level (int 5)) (aget arr subidx) i val)) | |
(VecNode (:edit node) arr)))) | |
) | |
(defmethod print-method ::Vec [v w] | |
((get (methods print-method) clojure.lang.IPersistentVector) v w)) | |
(defn newvec [] (Vec 0 5 EMPTY-NODE (object-array 0))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment