-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Efficient RRB-Vectors
--
-- An RRB-Vector is an efficient sequence data structure. It supports
-- fast indexing, iteration, concatenation and splitting.
--
--
--
-- Seq a is a container with a very similar API. RRB-Vectors are
-- generally faster for indexing and iteration, while sequences are
-- faster for access to the front/back (amortized <math>).
@package rrb-vector
@version 0.2.0.0
-- | This module contains some debug utilities. It should only be used for
-- debugging/testing purposes.
module Data.RRBVector.Internal.Debug
-- | <math>. Show the underlying tree of a vector.
showTree :: Show a => Vector a -> String
-- | <math>. Create a new unbalanced vector from a list.
--
-- Note that it is not possbible to create an invalid Vector with
-- this function.
fromListUnbalanced :: [a] -> Vector a
pattern Empty :: Vector a
pattern Root :: Int -> Shift -> Tree a -> Vector a
data Tree a
type Shift = Int
pattern Balanced :: Array (Tree a) -> Tree a
pattern Unbalanced :: Array (Tree a) -> PrimArray Int -> Tree a
pattern Leaf :: Array a -> Tree a
-- | The Vector a type is an RRB-Vector of elements of type
-- a.
--
-- This module should be imported qualified, to avoid name clashes with
-- the Prelude.
--
-- Performance
--
-- The worst case running time complexities are given, with <math>
-- referring to the number of elements in the vector (or <math>,
-- <math>, etc. for multiple vectors). Note that all logarithms are
-- base 16, so the constant factor for <math> operations is quite
-- small.
--
-- Implementation
--
-- The implementation uses Relaxed-Radix-Balanced trees, as described by
--
--
--
-- Currently, a branching factor of 16 is used. The tree is strict in its
-- spine, but lazy in its elements.
module Data.RRBVector
-- | A vector.
--
-- The instances are based on those of Seqs, which are in turn
-- based on those of lists.
data Vector a
-- | <math>. The empty vector.
--
--
-- empty = fromList []
--
empty :: Vector a
-- | <math>. A vector with a single element.
--
--
-- singleton x = fromList [x]
--
singleton :: a -> Vector a
-- | <math>. Create a new vector from a list.
fromList :: [a] -> Vector a
-- | <math>. replicate n x creates a vector of length
-- n with every element set to x.
--
--
-- >>> replicate 5 42
-- fromList [42,42,42,42,42]
--
replicate :: Int -> a -> Vector a
-- | <math>. Add an element to the left end of the vector.
--
--
-- >>> 1 <| fromList [2, 3, 4]
-- fromList [1,2,3,4]
--
(<|) :: a -> Vector a -> Vector a
infixr 5 <|
-- | <math>. Add an element to the right end of the vector.
--
--
-- >>> fromList [1, 2, 3] |> 4
-- fromList [1,2,3,4]
--
(|>) :: Vector a -> a -> Vector a
infixl 5 |>
-- | <math>. Concatenates two vectors.
--
--
-- >>> fromList [1, 2, 3] >< fromList [4, 5]
-- fromList [1,2,3,4,5]
--
(><) :: Vector a -> Vector a -> Vector a
infixr 5 ><
-- | <math>. The first element and the vector without the first
-- element, or Nothing if the vector is empty.
--
--
-- >>> viewl (fromList [1, 2, 3])
-- Just (1,fromList [2,3])
--
viewl :: Vector a -> Maybe (a, Vector a)
-- | <math>. The vector without the last element and the last
-- element, or Nothing if the vector is empty.
--
--
-- >>> viewr (fromList [1, 2, 3])
-- Just (fromList [1,2],3)
--
viewr :: Vector a -> Maybe (Vector a, a)
-- | <math>. The element at the index or Nothing if the index
-- is out of range.
lookup :: Int -> Vector a -> Maybe a
-- | <math>. The element at the index. Calls error if the
-- index is out of range.
index :: HasCallStack => Int -> Vector a -> a
-- | <math>. A flipped version of lookup.
(!?) :: Vector a -> Int -> Maybe a
-- | <math>. A flipped version of index.
(!) :: HasCallStack => Vector a -> Int -> a
-- | <math>. Update the element at the index with a new element. If
-- the index is out of range, the original vector is returned.
update :: Int -> a -> Vector a -> Vector a
-- | <math>. Adjust the element at the index by applying the function
-- to it. If the index is out of range, the original vector is returned.
adjust :: Int -> (a -> a) -> Vector a -> Vector a
-- | <math>. Like adjust, but the result of the function is
-- forced.
adjust' :: Int -> (a -> a) -> Vector a -> Vector a
-- | <math>. The first i elements of the vector. If
-- i is negative, the empty vector is returned. If the vector
-- contains less than i elements, the whole vector is returned.
take :: Int -> Vector a -> Vector a
-- | <math>. The vector without the first i elements If
-- i is negative, the whole vector is returned. If the vector
-- contains less than i elements, the empty vector is returned.
drop :: Int -> Vector a -> Vector a
-- | <math>. Split the vector at the given index.
--
--
-- splitAt n v = (take n v, drop n v)
--
splitAt :: Int -> Vector a -> (Vector a, Vector a)
-- | <math>. Insert an element at the given index.
insertAt :: Int -> a -> Vector a -> Vector a
-- | <math>. Delete the element at the given index.
deleteAt :: Int -> Vector a -> Vector a
-- | <math>. Apply the function to every element.
--
--
-- >>> map (+ 1) (fromList [1, 2, 3])
-- fromList [2,3,4]
--
map :: (a -> b) -> Vector a -> Vector b
-- | <math>. Like map, but the results of the function are
-- forced.
map' :: (a -> b) -> Vector a -> Vector b
-- | <math>. Reverse the vector.
--
--
-- >>> reverse (fromList [1, 2, 3])
-- fromList [3,2,1]
--
reverse :: Vector a -> Vector a
-- | <math>. Take two vectors and return a vector of corresponding
-- pairs. If one input is longer, excess elements are discarded from the
-- right end.
zip :: Vector a -> Vector b -> Vector (a, b)
-- | <math>. zipWith generalizes zip by zipping with
-- the function.
zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c
-- | <math>. Unzip a vector of pairs.
--
--
-- >>> unzip (fromList [(1, "a"), (2, "b"), (3, "c")])
-- (fromList [1,2,3],fromList ["a","b","c"])
--
unzip :: Vector (a, b) -> (Vector a, Vector b)
-- | <math>. Unzip a vector with a function.
--
--
-- unzipWith f = unzip . map f
--
unzipWith :: (a -> (b, c)) -> Vector a -> (Vector b, Vector c)