hwsl2-bytevector (empty) → 0.1.0.0

raw patch · 4 files changed

+229/−0 lines, 4 filesdep +basedep +bytestringdep +fingertreesetup-changed

Dependencies added: base, bytestring, fingertree, hwsl2

Files

LICENSE +22/−0
Setup.hs +2/−0
hwsl2-bytevector.cabal +25/−0
src/Data/Hash/SL2/ByteVector.hs +180/−0

+ LICENSE view

@@ -0,0 +1,22 @@+The MIT License (MIT)++Copyright (c) 2015 Sam Rijs++Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in all+copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE+SOFTWARE.+

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ hwsl2-bytevector.cabal view

@@ -0,0 +1,25 @@+name:                hwsl2-bytevector+version:             0.1.0.0+synopsis:            A hashed byte-vector based on algebraic hashes and finger trees+-- description:+homepage:            https://github.com/srijs/hwsl2-haskell-bytevector+license:             MIT+license-file:        LICENSE+author:              Sam Rijs+maintainer:          srijs@airpost.net+-- copyright:+category:            Data+build-type:          Simple+-- extra-source-files:+cabal-version:       >=1.10++library+  exposed-modules:     Data.Hash.SL2.ByteVector+  -- other-modules:+  -- other-extensions:+  build-depends:       base >=4.6 && <5,+                       hwsl2 >=0.3.2,+                       fingertree >=0.1,+                       bytestring >=0.10+  hs-source-dirs:      src+  default-language:    Haskell2010

+ src/Data/Hash/SL2/ByteVector.hs view

@@ -0,0 +1,180 @@+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}++module Data.Hash.SL2.ByteVector+  ( ByteVector()+    -- * Construction+  , singleton, fromList+    -- * Composition+  , empty, append+  , cons, snoc+    -- * Introspection+  , null, hash, length+    -- * Deconstruction+  , ViewL(..), viewl, viewl1+  , ViewR(..), viewr, viewr1+  , splitBefore, splitAt+    -- * Transformation+  , reverse, map+    -- * Reduction+  , foldl, foldr, foldl', foldr'+  ) where++import Prelude hiding (concat, null, reverse, map, length, foldl, foldr, splitAt)++import Data.Coerce+import qualified Data.Foldable as Foldable+import Data.Monoid++import Data.Hash.SL2 (Hash)+import qualified Data.Hash.SL2 as Hash+import Data.Hash.SL2.Chunk (Chunk(..), fromByteString)++import Data.FingerTree (FingerTree, (<|), (|>))+import qualified Data.FingerTree as FingerTree++import qualified Data.ByteString as ByteString++data Measure = Measure+  { getHash :: !Hash+  , getLength :: !Integer+  }++instance Monoid Measure where+  mempty = Measure mempty 0+  mappend a b = Measure (getHash a <> getHash b) (getLength a + getLength b)+  mconcat as = Measure (mconcat $ fmap getHash as) (sum $ fmap getLength as)++newtype MeasuredChunk = MeasuredChunk+  { getChunk :: Chunk+  } deriving (Eq, Ord)++instance FingerTree.Measured Measure MeasuredChunk where+  measure b = Measure (getChunkHash $ coerce b) (fromIntegral . ByteString.length . getChunkBytes $ coerce b)++newtype ByteVector = ByteVector+  { getTree :: FingerTree Measure MeasuredChunk+  } deriving (Monoid)++instance Eq ByteVector where+  a == b = getHash (FingerTree.measure $ getTree a) == getHash (FingerTree.measure $ getTree b)++instance Ord ByteVector where+  compare a b = compare (getHash . FingerTree.measure $ getTree a) (getHash . FingerTree.measure $ getTree b)++-- | /O(1)/ The empty vector. Alias for 'mempty'.+empty :: ByteVector+empty = ByteVector mempty++-- | /O(1)/ Creates a vector from a single chunk.+singleton :: Chunk -> ByteVector+singleton = ByteVector . FingerTree.singleton . coerce++-- | /O(n)/ Creates a vector from a list of chunks.+fromList :: [Chunk] -> ByteVector+fromList = ByteVector . FingerTree.fromList . fmap coerce++-- | /O(n)/ Concatenates two vectors together. Alias for 'mappend'.+append :: ByteVector -> ByteVector -> ByteVector+append a b = ByteVector $ getTree a <> getTree b++-- | /O(1)/ Adds a chunk to the left end of the vector.+cons :: Chunk -> ByteVector -> ByteVector+cons c v = ByteVector $ coerce c <| coerce v++-- | /O(1)/ Adds a chunk to the right end of the vector.+snoc :: ByteVector -> Chunk -> ByteVector+snoc v c = ByteVector $ coerce v |> coerce c++-- | /O(1)/ Is this the empty vector?+null :: ByteVector -> Bool+null v = getHash measure == Hash.unit && getLength measure == 0+  where measure = FingerTree.measure (getTree v)++-- | /O(1)/ Returns the hash of the vector.+hash :: ByteVector -> Hash+hash = getHash . FingerTree.measure . getTree++-- | /O(1)/ Returns the number of bytes in the vector.+length :: ByteVector -> Integer+length = getLength . FingerTree.measure . getTree++data ViewL = EmptyL | MostL Chunk ByteVector+  deriving (Eq, Ord)++-- | /O(1)/ Creates a view of the left end of the vector.+viewl :: ByteVector -> ViewL+viewl v = case FingerTree.viewl (getTree v) of+  FingerTree.EmptyL -> EmptyL+  most FingerTree.:< rest -> MostL (coerce most) (coerce rest)++-- | /O(1)/ Creates a view of the left end of the vector.+--          The single chunk is guaranteed to never be empty.+viewl1 :: ByteVector -> ViewL+viewl1 v = case viewl v of+  EmptyL -> EmptyL+  MostL most rest | mempty == most -> viewl1 rest+                  | otherwise -> MostL most rest++data ViewR = EmptyR | MostR ByteVector Chunk+  deriving (Eq, Ord)++-- | /O(1)/ Creates a view of the right end of the vector.+viewr :: ByteVector -> ViewR+viewr v = case FingerTree.viewr (getTree v) of+  FingerTree.EmptyR -> EmptyR+  rest FingerTree.:> most -> MostR (coerce rest) (coerce most)++-- | /O(1)/ Creates a view of the right end of the vector.+--          The single chunk is guaranteed to never be empty.+viewr1 :: ByteVector -> ViewR+viewr1 v = case viewr v of+  EmptyR -> EmptyR+  MostR rest most | mempty == most -> viewr1 rest+                  | otherwise -> MostR rest most++-- | /O(log(min(i,n-i)))/ Splits the vector at the chunk where the accumulated+--   length equals the provided integer /i/.+--   The resulting left side has a length smaller /i/.+splitBefore :: Integer -> ByteVector -> (ByteVector, ByteVector)+splitBefore i v = (coerce left, coerce right)+  where (left, right) = FingerTree.split (\m -> getLength m >= i) (getTree v)++-- | /O(log(min(i,n-i)))/ Splits the vector at the byte where the accumulated+--   length equals the provided integer /i/.+--   The resulting left side has a length of /min(i,n)/.+--+--   This is potentially less efficient than 'splitBefore' because it has to+--   re-hash parts of the vector.+splitAt :: Integer -> ByteVector -> (ByteVector, ByteVector)+splitAt i v = splitView (viewl right)+  where (left, right) = splitBefore i v+        splitView EmptyL = (left, right)+        splitView (MostL most rest) = (snoc left (fromByteString left'), cons (fromByteString right') rest)+          where (left', right') = ByteString.splitAt (fromIntegral $ i - length left) . getChunkBytes $ coerce most++-- | /O(n)/ Folds the vector from left to right.+foldl :: (a -> Chunk -> a) -> a -> ByteVector -> a+foldl f a v = Foldable.foldl (\a' -> f a' . getChunk) a (getTree v)++-- | /O(n)/ Folds the vector from right to left.+foldr :: (Chunk -> a -> a) -> a -> ByteVector -> a+foldr f a v = Foldable.foldr (\c a' -> f (getChunk c) a') a (getTree v)++-- | /O(n)/ Folds the vector from left to right, with strict application.+foldl' :: (a -> Chunk -> a) -> a -> ByteVector -> a+foldl' f a v = Foldable.foldl' (\a' -> f a' . getChunk) a (getTree v)++-- | /O(n)/ Folds the vector from right to left, with strict application.+foldr' :: (Chunk -> a -> a) -> a -> ByteVector -> a+foldr' f a v = Foldable.foldr' (\c a' -> f (getChunk c) a') a (getTree v)++-- | /O(n)/ Applies a function to every chunk in the vector.+map :: (Chunk -> Chunk) -> ByteVector -> ByteVector+map f v = ByteVector (FingerTree.fmap' (coerce . f . getChunk) $ coerce v)++-- | /O(n)/ Reverses the vector.+reverse :: ByteVector -> ByteVector+reverse v = ByteVector $ FingerTree.reverse $ FingerTree.fmap' (coerce . reverseChunk . coerce) (getTree v)+  where reverseChunk c = let r = ByteString.reverse (getChunkBytes c) in Chunk (Hash.hash r) r