persistent-vector 0.1.0.0 → 0.1.0.1
raw patch · 3 files changed
+59/−14 lines, 3 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- persistent-vector.cabal +8/−2
- src/Data/Vector/Persistent.hs +43/−12
- tests/pvTests.hs +8/−0
persistent-vector.cabal view
@@ -1,5 +1,5 @@ name: persistent-vector-version: 0.1.0.0+version: 0.1.0.1 synopsis: A persistent sequence based on array mapped tries license: BSD3 license-file: LICENSE@@ -9,6 +9,8 @@ build-type: Simple cabal-version: >=1.10 extra-source-files: README.md+homepage: https://github.com/travitch/persistent-vector+bug-reports: https://github.com/travitch/persistent-vector/issues description: This package provides persistent vectors based on array mapped@@ -38,7 +40,7 @@ exposed-modules: Data.Vector.Persistent other-modules: Data.Vector.Persistent.Array Data.Vector.Persistent.Unsafe- build-depends: base ==4.5.*, deepseq+ build-depends: base ==4.*, deepseq hs-source-dirs: src ghc-options: -Wall ghc-prof-options: -auto-all@@ -67,3 +69,7 @@ containers, criterion, deepseq++source-repository head+ type: git+ location: git://github.com/travitch/persistent-vector.git
src/Data/Vector/Persistent.hs view
@@ -103,10 +103,14 @@ -- where neither input is sliced. For sliced inputs, we currently -- fall back to a list conversion. pvEq :: (Eq a) => Vector a -> Vector a -> Bool-pvEq v1 v2+pvEq EmptyVector EmptyVector = True+pvEq v1@RootNode { } v2@RootNode { } | length v1 /= length v2 = False | isNotSliced v1 && isNotSliced v2 = pvSimpleEq v1 v2 | otherwise = F.toList v1 == F.toList v2+pvEq (DataNode a1) (DataNode a2) = a1 == a2+pvEq (InternalNode a1) (InternalNode a2) = a1 == a2+pvEq _ _ = False -- | A simple equality implementation for unsliced vectors. This can -- proceed structurally.@@ -121,11 +125,21 @@ {-# INLINABLE pvCompare #-} -- | A dispatcher for comparison tests pvCompare :: (Ord a) => Vector a -> Vector a -> Ordering-pvCompare v1 v2- | length v1 /= length v2 = compare (length v1) (length v2)+pvCompare EmptyVector EmptyVector = EQ+pvCompare (DataNode a1) (DataNode a2) = compare a1 a2+pvCompare (InternalNode a1) (InternalNode a2) = compare a1 a2+pvCompare v1@RootNode { vecSize = s1 } v2@RootNode { vecSize = s2 }+ | s1 /= s2 = compare s1 s2 | isNotSliced v1 && isNotSliced v2 = pvSimpleCompare v1 v2 | otherwise = compare (F.toList v1) (F.toList v2)+pvCompare EmptyVector _ = LT+pvCompare _ EmptyVector = GT+pvCompare (DataNode _) (InternalNode _) = LT+pvCompare (InternalNode _) (DataNode _) = GT+pvCompare _ _ = error "Data.Vector.Persistent: unexpected root node" ++ pvSimpleCompare :: (Ord a) => Vector a -> Vector a -> Ordering pvSimpleCompare EmptyVector EmptyVector = EQ pvSimpleCompare (RootNode _ _ _ _ t1 v1) (RootNode _ _ _ _ t2 v2) =@@ -272,6 +286,7 @@ -- usually just return nonsense values. unsafeIndex :: Vector a -> Int -> a unsafeIndex vec userIndex+-- | tailOffset vec < vecOffset vec = L.reverse (vecTail vec) !! (userIndex .&. 0x1f) | ix >= tailOffset vec && vecCapacity vec < vecSize vec = L.reverse (vecTail vec) !! (ix .&. 0x1f) | otherwise = go (vecShift vec) vec@@ -310,14 +325,13 @@ -- | O(1) Append an element to the end of the vector. snoc :: Vector a -> a -> Vector a snoc EmptyVector elt = singleton elt-snoc v@RootNode { vecSize = sz, vecShift = sh, vecTail = t } elt+snoc v@RootNode { vecSize = sz, vecShift = sh, vecOffset = off, vecTail = t } elt -- In this case, we are operating on a slice that has free space at -- the end inside of its tree. Use 'update' to replace the formerly -- unreachable element and then make it reachable.- | vecCapacity v > sz =- let v' = update sz elt v- in v' { vecSize = vecSize v' + 1 }- -- Room in tail+ | vecCapacity v >= sz =+ let v' = v { vecSize = sz + 1 }+ in update (sz - off) elt v' | sz .&. 0x1f /= 0 = v { vecTail = elt : t, vecSize = sz + 1 } -- Overflow current root | sz `shiftR` 5 > 1 `shiftL` sh =@@ -387,9 +401,15 @@ | sz <= ix || ix < 0 = v -- Item is in tail, | ix >= toff && vecCapacity v < sz =- let tix = sz - 1 - ix- (keepHead, _:keepTail) = L.splitAt tix t- in v { vecTail = keepHead ++ (elt : keepTail) }+ case t of+ -- The tail can only be empty if this was a slice where the last+ -- array in the tree is full and the slice left no tail. This+ -- is rare but we have to handle it.+ [] -> v { vecTail = [elt] }+ _ ->+ let tix = sz - 1 - ix+ (keepHead, _:keepTail) = L.splitAt tix t+ in v { vecTail = keepHead ++ (elt : keepTail) } -- Otherwise the item to be replaced is in the tree | otherwise = v { intVecPtrs = go sh (intVecPtrs v) } where@@ -429,6 +449,15 @@ slice _ _ EmptyVector = EmptyVector slice start userLen v@RootNode { vecSize = sz, vecOffset = off, vecCapacity = cap, vecTail = t } | len <= 0 = EmptyVector+ -- All the retained data is in the tail, so zero everything else out+ | toff < start =+ let t' = L.reverse $ L.take userLen $ L.drop (start - toff) $ L.reverse t+ in v { vecOffset = 0+ , vecCapacity = 0+ , intVecPtrs = A.fromList 0 []+ , vecSize = L.length t'+ , vecTail = t'+ } -- Start was negative, so we really start at zero and retain at most -- (len + start) elements. In this case vecOffset remains the same. | start < 0 =@@ -449,6 +478,7 @@ , vecTail = L.take (L.length t' - ntake) t' } where+ toff = tailOffset v len = max 0 (min userLen (sz - start)) slice _ _ _ = error "Data.Vector.Persistent.slice: Internal node" @@ -509,11 +539,12 @@ -- Helpers tailOffset :: Vector a -> Int+tailOffset EmptyVector = 0 tailOffset v | len < 32 = 0 | otherwise = (len - 1) `shiftR` 5 `shiftL` 5 where- len = length v+ len = vecSize v isNotSliced :: Vector a -> Bool isNotSliced v = vecOffset v == 0 && vecCapacity v < vecSize v
tests/pvTests.hs view
@@ -65,6 +65,7 @@ , testProperty "mappendWorks" prop_mappendWorks , testProperty "shrink" prop_shrinkPreserves , testProperty "shrinkEq" prop_shrinkEquality+ , testProperty "appendAfterSlice" prop_appendAfterSlice ] main :: IO ()@@ -147,3 +148,10 @@ v0 == V.shrink v0 where v0 = V.slice s n (V.fromList il)++prop_appendAfterSlice :: (SliceList, Int) -> Property+prop_appendAfterSlice (SliceList il s n, elt) =+ n - s < L.length il ==> Just elt == V.index v1 (V.length v1 - 1)+ where+ v0 = V.slice s n (V.fromList il)+ v1 = V.snoc v0 elt