hybrid-vectors (empty) → 0.1

raw patch · 13 files changed

+3847/−0 lines, 13 filesdep +basedep +deepseqdep +primitivesetup-changed

Dependencies added: base, deepseq, primitive, vector

Files

• .ghci +1/−0
• .gitignore +13/−0
• .travis.yml +8/−0
• .vim.custom +31/−0
• LICENSE +26/−0
• Setup.lhs +7/−0
• hybrid-vectors.cabal +46/−0
• src/Data/Vector/Hybrid.hs +1213/−0
• src/Data/Vector/Hybrid/Internal.hs +174/−0
• src/Data/Vector/Hybrid/Mutable.hs +286/−0
• src/Data/Vector/Mixed.hs +1483/−0
• src/Data/Vector/Mixed/Internal.hs +283/−0
• src/Data/Vector/Mixed/Mutable.hs +276/−0

@@ -0,0 +1,1 @@+:set -isrc -idist/build/autogen -optP-include -optPdist/build/autogen/cabal_macros.h

@@ -0,0 +1,13 @@+dist+docs+wiki+TAGS+tags+wip+.DS_Store+.*.swp+.*.swo+*.o+*.hi+*~+*#

@@ -0,0 +1,8 @@+language: haskell+notifications:+  irc:+    channels:+      - "irc.freenode.org#haskell-lens"+    skip_join: true+    template:+      - "\x0313hybrid-vectors\x03/\x0306%{branch}\x03 \x0314%{commit}\x03 %{build_url} %{message}"

@@ -0,0 +1,31 @@+" Add the following to your .vimrc to automatically load this on startup++" if filereadable(".vim.custom")+"     so .vim.custom+" endif++function StripTrailingWhitespace()+  let myline=line(".")+  let mycolumn = col(".")+  silent %s/  *$//+  call cursor(myline, mycolumn)+endfunction++" enable syntax highlighting+syntax on++" search for the tags file anywhere between here and /+set tags=TAGS;/++" highlight tabs and trailing spaces+set listchars=tab:‗‗,trail:‗+set list++" f2 runs hasktags+map <F2> :exec ":!hasktags -x -c --ignore src"<CR><CR>++" strip trailing whitespace before saving+" au BufWritePre *.hs,*.markdown silent! cal StripTrailingWhitespace()++" rebuild hasktags after saving+au BufWritePost *.hs silent! :exec ":!hasktags -x -c --ignore src"

@@ -0,0 +1,26 @@+Copyright 2013 Edward Kmett++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions+are met:++1. Redistributions of source code must retain the above copyright+   notice, this list of conditions and the following disclaimer.++2. Redistributions in binary form must reproduce the above copyright+   notice, this list of conditions and the following disclaimer in the+   documentation and/or other materials provided with the distribution.++THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR+IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE+DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL+DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS+OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,+STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN+ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE+POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,7 @@+#!/usr/bin/runhaskell+> module Main (main) where++> import Distribution.Simple++> main :: IO ()+> main = defaultMain

@@ -0,0 +1,46 @@+name:          hybrid-vectors+category:      Data, Vector+version:       0.1+license:       BSD3+cabal-version: >= 1.6+license-file:  LICENSE+author:        Edward A. Kmett+maintainer:    Edward A. Kmett <ekmett@gmail.com>+stability:     experimental+homepage:      http://github.com/ekmett/hybrid-vectors+bug-reports:   http://github.com/ekmett/hybrid-vectors/issues+copyright:     Copyright (C) 2013 Edward A. Kmett+build-type:    Simple+synopsis:      Hybrid vectors e.g. Mixed Boxed/Unboxed vectors+extra-source-files:+  .ghci+  .travis.yml+  .gitignore+  .vim.custom+description:++source-repository head+  type: git+  location: git://github.com/ekmett/hybrid-vectors.git++library+  build-depends:+    base          >= 4       && < 5,+    deepseq       >= 1.1     && < 1.4,+    primitive     >= 0.5     && < 0.6,+    vector        >= 0.10    && < 0.11++  hs-source-dirs: src++  exposed-modules:+    Data.Vector.Hybrid+    Data.Vector.Hybrid.Internal+    Data.Vector.Hybrid.Mutable+    Data.Vector.Mixed+    Data.Vector.Mixed.Internal+    Data.Vector.Mixed.Mutable++  ghc-options: -Wall -O2++  if impl(ghc<6.13)+    Ghc-Options: -finline-if-enough-args -fno-method-sharing

@@ -0,0 +1,1213 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE GADTs #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE Rank2Types #-}+-----------------------------------------------------------------------------+-- |+-- Copyright   :  (C) 2011 Edward Kmett,+-- License     :  BSD-style (see the file LICENSE)+--+-- Maintainer  :  Edward Kmett <ekmett@gmail.com>+-- Stability   :  experimental+-- Portability :  non-portable+--+-- A hybrid 'Vector' lets you make a 'Vector' which is 'partially unboxed', by+-- making a 'Vector' out of two other 'Vector' types and using each for its+-- corresponding side of a 'Vector' of pairs.+--+-- This enables you to work with a mixture of boxed and unboxed data when+-- you go to use something @like vector-algorithms@+-----------------------------------------------------------------------------+module Data.Vector.Hybrid+  ( Vector, MVector++  -- * Accessors++  -- ** Length information+  , length, null++  -- ** Indexing+  , (!), (!?), head, last+  , unsafeIndex, unsafeHead, unsafeLast++  -- ** Monadic indexing+  , indexM, headM, lastM+  , unsafeIndexM, unsafeHeadM, unsafeLastM++  -- ** Extracting subvectors (slicing)+  , slice, init, tail, take, drop, splitAt+  , unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop++  -- * Construction++  -- ** Initialisation+  , empty, singleton, replicate, generate, iterateN++  -- ** Monadic initialisation+  , replicateM, generateM, create++  -- ** Unfolding+  , unfoldr, unfoldrN+  , constructN, constructrN++  -- -- ** Enumeration+  -- , enumFromN, enumFromStepN, enumFromTo, enumFromThenTo++  -- ** Concatenation+  , cons, snoc, (++), concat++  -- ** Restricting memory usage+  , force++  -- * Modifying vectors++  -- ** Bulk updates+  , (//)+  , unsafeUpd+  -- , update_, unsafeUpdate_++  -- ** Accumulations+  , accum, unsafeAccum+  -- , accumulate_, unsafeAccumulate_++  -- ** Permutations+  , reverse+  -- , backpermute, unsafeBackpermute++  -- ** Safe destructive updates+  , modify++  -- * Elementwise operations++  -- ** Mapping+  , map, imap, concatMap++  -- ** Monadic mapping+  , mapM, mapM_, forM, forM_++  -- ** Zipping+  , zipWith, zipWith3, zipWith4, zipWith5, zipWith6+  , izipWith, izipWith3, izipWith4, izipWith5, izipWith6++  -- ** Monadic zipping+  , zipWithM, zipWithM_++  -- * Working with predicates++  -- ** Filtering+  , filter, ifilter, filterM+  , takeWhile, dropWhile++  -- ** Partitioning+  , partition, unstablePartition, span, break++  -- ** Searching+  , elem, notElem, find, findIndex+  , elemIndex+  -- , findIndices, elemIndices++  -- * Folding+  , foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1'+  , ifoldl, ifoldl', ifoldr, ifoldr'++  -- ** Specialised folds+  , all, any+  -- , sum, product+  , maximum, maximumBy, minimum, minimumBy+  , minIndex, minIndexBy, maxIndex, maxIndexBy++  -- ** Monadic folds+  , foldM, foldM', fold1M, fold1M'+  , foldM_, foldM'_, fold1M_, fold1M'_++  -- * Prefix sums (scans)+  , prescanl, prescanl'+  , postscanl, postscanl'+  , scanl, scanl', scanl1, scanl1'+  , prescanr, prescanr'+  , postscanr, postscanr'+  , scanr, scanr', scanr1, scanr1'++  -- * Conversions+  , projectFst+  , projectSnd+  , unsafeZip++  -- ** Lists+  , toList, fromList, fromListN++  -- ** Other vector types+  , G.convert++  -- ** Mutable vectors+  , freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy+  ) where++import Control.Monad.Primitive+import Control.Monad.ST+import Data.Vector.Hybrid.Internal+import qualified Data.Vector.Generic as G+import Prelude hiding ( length, null,+                        replicate, (++), concat,+                        head, last,+                        init, tail, take, drop, splitAt, reverse,+                        map, concatMap,+                        zipWith, zipWith3, zip, zip3, unzip, unzip3,+                        filter, takeWhile, dropWhile, span, break,+                        elem, notElem,+                        foldl, foldl1, foldr, foldr1,+                        all, any, sum, product, minimum, maximum,+                        scanl, scanl1, scanr, scanr1,+                        enumFromTo, enumFromThenTo,+                        mapM, mapM_ )+++-- Length+-- ------++-- | /O(1)/ Yield the length of the vector.+length :: G.Vector u a => Vector u v (a, b) -> Int+length (V ks _) = G.length ks+{-# INLINE length #-}++-- | /O(1)/ Test whether a vector if empty+null :: G.Vector u a => Vector u v (a, b) -> Bool+null (V ks _) = G.null ks+{-# INLINE null #-}+++-- Indexing+-- --------++-- | O(1) Indexing+(!) :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> Int -> (a, b)+(!) = (G.!)+{-# INLINE (!) #-}++-- | O(1) Safe indexing+(!?) :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> Int -> Maybe (a, b)+(!?) = (G.!?)+{-# INLINE (!?) #-}++-- | /O(1)/ First element+head :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> (a, b)+head = G.head+{-# INLINE head #-}++-- | /O(1)/ Last element+last :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> (a, b)+last = G.last+{-# INLINE last #-}+++-- | /O(1)/ Unsafe indexing without bounds checking+unsafeIndex :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> Int -> (a, b)+{-# INLINE unsafeIndex #-}+unsafeIndex = G.unsafeIndex++-- | /O(1)/ First element without checking if the vector is empty+unsafeHead :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> (a, b)+{-# INLINE unsafeHead #-}+unsafeHead = G.unsafeHead++-- | /O(1)/ Last element without checking if the vector is empty+unsafeLast :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> (a, b)+{-# INLINE unsafeLast #-}+unsafeLast = G.unsafeLast++-- Monadic indexing+-- ----------------++-- | /O(1)/ Indexing in a monad.+--+-- The monad allows operations to be strict in the vector when necessary.+-- Suppose vector copying is implemented like this:+--+-- > copy mv v = ... write mv i (v ! i) ...+--+-- For lazy vectors, @v ! i@ would not be evaluated which means that @mv@+-- would unnecessarily retain a reference to @v@ in each element written.+--+-- With 'indexM', copying can be implemented like this instead:+--+-- > copy mv v = ... do+-- >                   x <- indexM v i+-- >                   write mv i x+--+-- Here, no references to @v@ are retained because indexing (but /not/ the+-- elements) is evaluated eagerly.+--+indexM :: (G.Vector u a, G.Vector v b, Monad m) => Vector u v (a, b) -> Int -> m (a, b)+indexM = G.indexM+{-# INLINE indexM #-}++-- | /O(1)/ First element of a vector in a monad. See 'indexM' for an+-- explanation of why this is useful.+headM :: (G.Vector u a, G.Vector v b, Monad m) => Vector u v (a, b) -> m (a, b)+headM = G.headM+{-# INLINE headM #-}++-- | /O(1)/ Last element of a vector in a monad. See 'indexM' for an+-- explanation of why this is useful.+lastM :: (G.Vector u a, G.Vector v b, Monad m) => Vector u v (a, b) -> m (a, b)+lastM = G.lastM+{-# INLINE lastM #-}++-- | /O(1)/ Indexing in a monad without bounds checks. See 'indexM' for an+-- explanation of why this is useful.+unsafeIndexM :: (G.Vector u a, G.Vector v b, Monad m) => Vector u v (a, b) -> Int -> m (a, b)+unsafeIndexM = G.unsafeIndexM+{-# INLINE unsafeIndexM #-}++-- | /O(1)/ First element in a monad without checking for empty vectors.+-- See 'indexM' for an explanation of why this is useful.+unsafeHeadM :: (G.Vector u a, G.Vector v b, Monad m) => Vector u v (a, b) -> m (a, b)+unsafeHeadM = G.unsafeHeadM+{-# INLINE unsafeHeadM #-}++-- | /O(1)/ Last element in a monad without checking for empty vectors.+-- See 'indexM' for an explanation of why this is useful.+unsafeLastM :: (G.Vector u a, G.Vector v b, Monad m) => Vector u v (a, b) -> m (a, b)+unsafeLastM = G.unsafeLastM+{-# INLINE unsafeLastM #-}++-- Extracting subvectors (slicing)+-- -------------------------------++-- | /O(1)/ Yield a slice of the vector without copying it. The vector must+-- contain at least @i+n@ elements.+slice :: (G.Vector u a, G.Vector v b)+      => Int   -- ^ @i@ starting index+      -> Int   -- ^ @n@ length+      -> Vector u v (a, b)+      -> Vector u v (a, b)+slice = G.slice+{-# INLINE slice #-}++-- | /O(1)/ Yield all but the last element without copying. The vector may not+-- be empty.+init :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> Vector u v (a, b)+init = G.init+{-# INLINE init #-}++-- | /O(1)/ Yield all but the first element without copying. The vector may not+-- be empty.+tail :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> Vector u v (a, b)+tail = G.tail+{-# INLINE tail #-}++-- | /O(1)/ Yield at the first @n@ elements without copying. The vector may+-- contain less than @n@ elements in which case it is returned unchanged.+take :: (G.Vector u a, G.Vector v b) => Int -> Vector u v (a, b) -> Vector u v (a, b)+take = G.take+{-# INLINE take #-}++-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector may+-- contain less than @n@ elements in which case an empty vector is returned.+drop :: (G.Vector u a, G.Vector v b) => Int -> Vector u v (a, b) -> Vector u v (a, b)+drop = G.drop+{-# INLINE drop #-}++-- | /O(1)/ Yield the first @n@ elements paired with the remainder without copying.+--+-- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@+-- but slightly more efficient.+splitAt :: (G.Vector u a, G.Vector v b) => Int -> Vector u v (a, b) -> (Vector u v (a, b), Vector u v (a, b))+splitAt = G.splitAt+{-# INLINE splitAt #-}++-- | /O(1)/ Yield a slice of the vector without copying. The vector must+-- contain at least @i+n@ elements but this is not checked.+unsafeSlice :: (G.Vector u a, G.Vector v b) => Int   -- ^ @i@ starting index+                       -> Int   -- ^ @n@ length+                       -> Vector u v (a, b)+                       -> Vector u v (a, b)+unsafeSlice = G.unsafeSlice+{-# INLINE unsafeSlice #-}++-- | /O(1)/ Yield all but the last element without copying. The vector may not+-- be empty but this is not checked.+unsafeInit :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> Vector u v (a, b)+unsafeInit = G.unsafeInit+{-# INLINE unsafeInit #-}++-- | /O(1)/ Yield all but the first element without copying. The vector may not+-- be empty but this is not checked.+unsafeTail :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> Vector u v (a, b)+unsafeTail = G.unsafeTail+{-# INLINE unsafeTail #-}++-- | /O(1)/ Yield the first @n@ elements without copying. The vector must+-- contain at least @n@ elements but this is not checked.+unsafeTake :: (G.Vector u a, G.Vector v b) => Int -> Vector u v (a, b) -> Vector u v (a, b)+unsafeTake = G.unsafeTake+{-# INLINE unsafeTake #-}++-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector+-- must contain at least @n@ elements but this is not checked.+unsafeDrop :: (G.Vector u a, G.Vector v b) => Int -> Vector u v (a, b) -> Vector u v (a, b)+unsafeDrop = G.unsafeDrop+{-# INLINE unsafeDrop #-}++-- Initialisation+-- --------------++-- | /O(1)/ Empty vector+empty :: (G.Vector u a, G.Vector v b) => Vector u v (a, b)+empty = G.empty+{-# INLINE empty #-}++-- | /O(1)/ Vector with exactly one element+singleton :: (G.Vector u a, G.Vector v b) => (a, b) -> Vector u v (a, b)+singleton = G.singleton+{-# INLINE singleton #-}++-- | /O(n)/ Vector of the given length with the same value in each position+replicate :: (G.Vector u a, G.Vector v b) => Int -> (a, b) -> Vector u v (a, b)+replicate = G.replicate+{-# INLINE replicate #-}++-- | /O(n)/ Construct a vector of the given length by applying the function to+-- each index+generate :: (G.Vector u a, G.Vector v b) => Int -> (Int -> (a, b)) -> Vector u v (a, b)+generate = G.generate+{-# INLINE generate #-}++-- | /O(n)/ Apply function n times to value. Zeroth element is original value.+iterateN :: (G.Vector u a, G.Vector v b) => Int -> ((a, b) -> (a, b)) -> (a, b) -> Vector u v (a, b)+iterateN = G.iterateN+{-# INLINE iterateN #-}++-- Unfolding+-- ---------++-- | /O(n)/ Construct a vector by repeatedly applying the generator function+-- to a seed. The generator function yields 'Just' the next element and the+-- new seed or 'Nothing' if there are no more elements.+--+-- > unfoldr (\n -> if n == 0 then Nothing else Just (n,n-1)) 10+-- >  = <10,9,8,7,6,5,4,3,2,1>+unfoldr :: (G.Vector u a, G.Vector v b) => (c -> Maybe ((a, b), c)) -> c -> Vector u v (a, b)+unfoldr = G.unfoldr+{-# INLINE unfoldr #-}++-- | /O(n)/ Construct a vector with at most @n@ by repeatedly applying the+-- generator function to the a seed. The generator function yields 'Just' the+-- next element and the new seed or 'Nothing' if there are no more elements.+--+-- > unfoldrN 3 (\n -> Just (n,n-1)) 10 = <10,9,8>+unfoldrN :: (G.Vector u a, G.Vector v b) => Int -> (c -> Maybe ((a, b), c)) -> c -> Vector u v (a, b)+unfoldrN = G.unfoldrN+{-# INLINE unfoldrN #-}++-- | /O(n)/ Construct a vector with @n@ elements by repeatedly applying the+-- generator function to the already constructed part of the vector.+--+-- > constructN 3 f = let a = f <> ; b = f <a> ; c = f <a,b> in f <a,b,c>+--+constructN :: (G.Vector u a, G.Vector v b) => Int -> (Vector u v (a, b) -> (a, b)) -> Vector u v (a, b)+constructN = G.constructN+{-# INLINE constructN #-}++-- | /O(n)/ Construct a vector with @n@ elements from right to left by+-- repeatedly applying the generator function to the already constructed part+-- of the vector.+--+-- > constructrN 3 f = let a = f <> ; b = f<a> ; c = f <b,a> in f <c,b,a>+--+constructrN :: (G.Vector u a, G.Vector v b) => Int -> (Vector u v (a, b) -> (a, b)) -> Vector u v (a, b)+constructrN = G.constructrN+{-# INLINE constructrN #-}++-- Concatenation+-- -------------++-- | /O(n)/ Prepend an element+cons :: (G.Vector u a, G.Vector v b) => (a, b) -> Vector u v (a, b) -> Vector u v (a, b)+{-# INLINE cons #-}+cons = G.cons++-- | /O(n)/ Append an element+snoc :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> (a, b) -> Vector u v (a, b)+{-# INLINE snoc #-}+snoc = G.snoc++infixr 5 +++-- | /O(m+n)/ Concatenate two vectors+(++) :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> Vector u v (a, b) -> Vector u v (a, b)+{-# INLINE (++) #-}+(++) = (G.++)++-- | /O(n)/ Concatenate all vectors in the list+concat :: (G.Vector u a, G.Vector v b) => [Vector u v (a, b)] -> Vector u v (a, b)+{-# INLINE concat #-}+concat = G.concat++-- Monadic initialisation+-- ----------------------++-- | /O(n)/ Execute the monadic action the given number of times and store the+-- results in a vector.+replicateM :: (Monad m, G.Vector u a, G.Vector v b) => Int -> m (a, b) -> m (Vector u v (a, b))+replicateM = G.replicateM+{-# INLINE replicateM #-}++-- | /O(n)/ Construct a vector of the given length by applying the monadic+-- action to each index+generateM :: (Monad m, G.Vector u a, G.Vector v b) => Int -> (Int -> m (a, b)) -> m (Vector u v (a, b))+generateM = G.generateM+{-# INLINE generateM #-}++-- | Execute the monadic action and freeze the resulting vector.+--+-- @+-- create (do { v \<- new 2; write v 0 \'a\'; write v 1 \'b\'; return v }) = \<'a','b'\>+-- @+create :: (G.Vector u a, G.Vector v b) => (forall s. ST s (G.Mutable (Vector u v) s (a, b))) -> Vector u v (a, b)+-- NOTE: eta-expanded due to http://hackage.haskell.org/trac/ghc/ticket/4120+create p = G.create p+{-# INLINE create #-}++-- Restricting memory usage+-- ------------------------++-- | /O(n)/ Yield the argument but force it not to retain any extra memory,+-- possibly by copying it.+--+-- This is especially useful when dealing with slices. For example:+--+-- > force (slice 0 2 <huge vector>)+--+-- Here, the slice retains a reference to the huge vector. Forcing it creates+-- a copy of just the elements that belong to the slice and allows the huge+-- vector to be garbage collected.+force :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> Vector u v (a, b)+force = G.force+{-# INLINE force #-}++-- Bulk updates+-- ------------++-- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector+-- element at position @i@ by @a@.+--+-- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>+--+(//) :: (G.Vector u a, G.Vector v b) => Vector u v (a, b)   -- ^ initial vector (of length @m@)+                -> [(Int, (a, b))]                          -- ^ list of index/value pairs (of length @n@)+                -> Vector u v (a, b)+(//) = (G.//)+{-# INLINE (//) #-}++-- | Same as ('//') but without bounds checking.+unsafeUpd :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> [(Int, (a, b))] -> Vector u v (a, b)+unsafeUpd = G.unsafeUpd+{-# INLINE unsafeUpd #-}++-- Accumulations+-- -------------++-- | /O(m+n)/ For each pair @(i,c)@ from the list, replace the vector element+-- @a@ at position @i@ by @f a c@.+--+-- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4>+accum :: (G.Vector u a, G.Vector v b)+      => ((a, b) -> c -> (a, b)) -- ^ accumulating function @f@+      -> Vector u v (a, b)       -- ^ initial vector (of length @m@)+      -> [(Int,c)]               -- ^ list of index/value pairs (of length @n@)+      -> Vector u v (a, b)+accum = G.accum+{-# INLINE accum #-}++-- | Same as 'accum' but without bounds checking.+unsafeAccum :: (G.Vector u a, G.Vector v b) => ((a, b) -> c -> (a, b)) -> Vector u v (a, b) -> [(Int,c)] -> Vector u v (a, b)+unsafeAccum = G.unsafeAccum+{-# INLINE unsafeAccum #-}+++-- Permutations+-- ------------++-- | /O(n)/ Reverse a vector+reverse :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> Vector u v (a, b)+{-# INLINE reverse #-}+reverse = G.reverse++-- Safe destructive updates+-- ------------------------++-- | Apply a destructive operation to a vector. The operation will be+-- performed in place if it is safe to do so and will modify a copy of the+-- vector otherwise.+--+-- @+-- modify (\\v -> write v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>+-- @+modify :: (G.Vector u a, G.Vector v b)+       => (forall s. G.Mutable (Vector u v) s (a, b) -> ST s ())+       -> Vector u v (a, b) -> Vector u v (a, b)+{-# INLINE modify #-}+modify p = G.modify p++-- Mapping+-- -------++-- | /O(n)/ Map a function over a vector+map :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d)+    => ((a, b) -> (c, d)) -> Vector u v (a, b) -> Vector u v (c, d)+map = G.map+{-# INLINE map #-}++-- | /O(n)/ Apply a function to every element of a vector and its index+imap :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d)+     => (Int -> (a, b) -> (c, d))+     -> Vector u v (a, b) -> Vector u v (c, d)+imap = G.imap+{-# INLINE imap #-}++-- | Map a function over a vector and concatenate the results.+concatMap :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d)+          => ((a, b) -> Vector u v (c, d)) -> Vector u v (a, b) -> Vector u v (c, d)+concatMap = G.concatMap+{-# INLINE concatMap #-}++-- Monadic mapping+-- ---------------++-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a+-- vector of results+mapM :: (Monad m, G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> m (c, d)) -> Vector u v (a, b) -> m (Vector u v (c, d))+mapM = G.mapM+{-# INLINE mapM #-}++-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the+-- results+mapM_ :: (Monad m, G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> m (c, d)) -> Vector u v (a, b) -> m ()+mapM_ = G.mapM_+{-# INLINE mapM_ #-}++-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a+-- vector of results. Equvalent to @flip 'mapM'@.+forM :: (Monad m, G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => Vector u v (a, b) -> ((a, b) -> m (c, d)) -> m (Vector u v (c, d))+forM = G.forM+{-# INLINE forM #-}++-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the+-- results. Equivalent to @flip 'mapM_'@.+forM_ :: (Monad m, G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => Vector u v (a, b) -> ((a, b) -> m (c, d)) -> m ()+forM_ = G.forM_+{-# INLINE forM_ #-}++-- Zipping+-- -------++-- | /O(min(m,n))/ Zip two vectors with the given function.+zipWith :: ( G.Vector u a, G.Vector v a'+           , G.Vector u b, G.Vector v b'+           , G.Vector u c, G.Vector v c'+           ) => ((a,a') -> (b,b') -> (c,c'))+             -> Vector u v (a,a') -> Vector u v (b,b') -> Vector u v (c,c')+zipWith = G.zipWith+{-# INLINE zipWith #-}++-- | Zip three vectors with the given function.++zipWith3 :: ( G.Vector u a, G.Vector v a'+            , G.Vector u b, G.Vector v b'+            , G.Vector u c, G.Vector v c'+            , G.Vector u d, G.Vector v d'+            ) => ((a,a') -> (b,b') -> (c,c') -> (d, d'))+              -> Vector u v (a,a') -> Vector u v (b,b') -> Vector u v (c,c') -> Vector u v (d,d')+zipWith3 = G.zipWith3+{-# INLINE zipWith3 #-}++zipWith4 :: ( G.Vector u a, G.Vector v a'+            , G.Vector u b, G.Vector v b'+            , G.Vector u c, G.Vector v c'+            , G.Vector u d, G.Vector v d'+            , G.Vector u e, G.Vector v e'+            ) => ((a,a') -> (b,b') -> (c,c') -> (d, d') -> (e,e'))+              -> Vector u v (a,a') -> Vector u v (b,b') -> Vector u v (c,c') -> Vector u v (d,d') -> Vector u v (e,e')+zipWith4 = G.zipWith4+{-# INLINE zipWith4 #-}++zipWith5 :: ( G.Vector u a, G.Vector v a'+            , G.Vector u b, G.Vector v b'+            , G.Vector u c, G.Vector v c'+            , G.Vector u d, G.Vector v d'+            , G.Vector u e, G.Vector v e'+            , G.Vector u f, G.Vector v f'+            ) => ((a,a') -> (b,b') -> (c,c') -> (d, d') -> (e,e') -> (f,f'))+              -> Vector u v (a,a') -> Vector u v (b,b') -> Vector u v (c,c') -> Vector u v (d,d') -> Vector u v (e,e') -> Vector u v (f,f')+zipWith5 = G.zipWith5+{-# INLINE zipWith5 #-}++zipWith6 :: ( G.Vector u a, G.Vector v a'+            , G.Vector u b, G.Vector v b'+            , G.Vector u c, G.Vector v c'+            , G.Vector u d, G.Vector v d'+            , G.Vector u e, G.Vector v e'+            , G.Vector u f, G.Vector v f'+            , G.Vector u g, G.Vector v g'+            ) => ((a,a') -> (b,b') -> (c,c') -> (d, d') -> (e,e') -> (f,f') -> (g,g'))+              -> Vector u v (a,a') -> Vector u v (b,b') -> Vector u v (c,c') -> Vector u v (d,d') -> Vector u v (e,e') -> Vector u v (f,f') -> Vector u v (g,g')+zipWith6 = G.zipWith6+{-# INLINE zipWith6 #-}++-- | /O(min(m,n))/ Zip two vectors with a function that also takes the+-- elements' indices.+izipWith :: ( G.Vector u a, G.Vector v a'+            , G.Vector u b, G.Vector v b'+            , G.Vector u c, G.Vector v c'+            ) => (Int -> (a,a') -> (b,b') -> (c,c'))+              -> Vector u v (a,a') -> Vector u v (b,b') -> Vector u v (c,c')+izipWith = G.izipWith+{-# INLINE izipWith #-}++-- | Zip three vectors and their indices with the given function.+izipWith3 :: ( G.Vector u a, G.Vector v a'+            , G.Vector u b, G.Vector v b'+            , G.Vector u c, G.Vector v c'+            , G.Vector u d, G.Vector v d'+            ) => (Int -> (a,a') -> (b,b') -> (c,c') -> (d, d'))+              -> Vector u v (a,a') -> Vector u v (b,b') -> Vector u v (c,c') -> Vector u v (d,d')+izipWith3 = G.izipWith3+{-# INLINE izipWith3 #-}++izipWith4 :: ( G.Vector u a, G.Vector v a'+            , G.Vector u b, G.Vector v b'+            , G.Vector u c, G.Vector v c'+            , G.Vector u d, G.Vector v d'+            , G.Vector u e, G.Vector v e'+            ) => (Int -> (a,a') -> (b,b') -> (c,c') -> (d, d') -> (e,e'))+              -> Vector u v (a,a') -> Vector u v (b,b') -> Vector u v (c,c') -> Vector u v (d,d') -> Vector u v (e,e')+izipWith4 = G.izipWith4+{-# INLINE izipWith4 #-}++izipWith5 :: ( G.Vector u a, G.Vector v a'+            , G.Vector u b, G.Vector v b'+            , G.Vector u c, G.Vector v c'+            , G.Vector u d, G.Vector v d'+            , G.Vector u e, G.Vector v e'+            , G.Vector u f, G.Vector v f'+            ) => (Int -> (a,a') -> (b,b') -> (c,c') -> (d, d') -> (e,e') -> (f,f'))+              -> Vector u v (a,a') -> Vector u v (b,b') -> Vector u v (c,c') -> Vector u v (d,d') -> Vector u v (e,e') -> Vector u v (f,f')+izipWith5 = G.izipWith5+{-# INLINE izipWith5 #-}++izipWith6 :: ( G.Vector u a, G.Vector v a'+            , G.Vector u b, G.Vector v b'+            , G.Vector u c, G.Vector v c'+            , G.Vector u d, G.Vector v d'+            , G.Vector u e, G.Vector v e'+            , G.Vector u f, G.Vector v f'+            , G.Vector u g, G.Vector v g'+            ) => (Int -> (a,a') -> (b,b') -> (c,c') -> (d, d') -> (e,e') -> (f,f') -> (g,g'))+              -> Vector u v (a,a') -> Vector u v (b,b') -> Vector u v (c,c') -> Vector u v (d,d') -> Vector u v (e,e') -> Vector u v (f,f') -> Vector u v (g,g')+izipWith6 = G.izipWith6+{-# INLINE izipWith6 #-}++-- Monadic zipping+-- ---------------++-- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a+-- vector of results+zipWithM :: (Monad m, G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d, G.Vector u e, G.Vector v f)+         => ((a, b) -> (c, d) -> m (e,f)) -> Vector u v (a, b) -> Vector u v (c, d) -> m (Vector u v (e,f))+zipWithM = G.zipWithM+{-# INLINE zipWithM #-}++-- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the+-- results+zipWithM_ :: (Monad m, G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d)+          => ((a, b) -> (c, d) -> m e) -> Vector u v (a, b) -> Vector u v (c, d) -> m ()+zipWithM_ = G.zipWithM_+{-# INLINE zipWithM_ #-}++-- Filtering+-- ---------++-- | /O(n)/ Drop elements that do not satisfy the predicate+filter :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> Vector u v (a, b)+filter = G.filter+{-# INLINE filter #-}++-- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to+-- values and their indices+ifilter :: (G.Vector u a, G.Vector v b) => (Int -> (a, b) -> Bool) -> Vector u v (a, b) -> Vector u v (a, b)+ifilter = G.ifilter+{-# INLINE ifilter #-}++-- | /O(n)/ Drop elements that do not satisfy the monadic predicate+filterM :: (Monad m, G.Vector u a, G.Vector v b) => ((a, b) -> m Bool) -> Vector u v (a, b) -> m (Vector u v (a, b))+filterM = G.filterM+{-# INLINE filterM #-}++-- | /O(n)/ Yield the longest prefix of elements satisfying the predicate+-- without copying.+takeWhile :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> Vector u v (a, b)+takeWhile = G.takeWhile+{-# INLINE takeWhile #-}++-- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate+-- without copying.+dropWhile :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> Vector u v (a, b)+dropWhile = G.dropWhile+{-# INLINE dropWhile #-}+++-- Parititioning+-- -------------++-- | /O(n)/ Split the vector in two parts, the first one containing those+-- elements that satisfy the predicate and the second one those that don't. The+-- relative order of the elements is preserved at the cost of a sometimes+-- reduced performance compared to 'unstablePartition'.+partition :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> (Vector u v (a, b), Vector u v (a, b))+{-# INLINE partition #-}+partition = G.partition++-- | /O(n)/ Split the vector in two parts, the first one containing those+-- elements that satisfy the predicate and the second one those that don't.+-- The order of the elements is not preserved but the operation is often+-- faster than 'partition'.+unstablePartition :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> (Vector u v (a, b), Vector u v (a, b))+{-# INLINE unstablePartition #-}+unstablePartition = G.unstablePartition++-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy+-- the predicate and the rest without copying.+span :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> (Vector u v (a, b), Vector u v (a, b))+{-# INLINE span #-}+span = G.span++-- | /O(n)/ Split the vector into the longest prefix of elements that do not+-- satisfy the predicate and the rest without copying.+break :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> (Vector u v (a, b), Vector u v (a, b))+{-# INLINE break #-}+break = G.break++-- Searching+-- ---------++infix 4 `elem`+-- | /O(n)/ Check if the vector contains an element+elem :: (G.Vector u a, G.Vector v b, Eq a, Eq b) => (a, b) -> Vector u v (a, b) -> Bool+elem = G.elem+{-# INLINE elem #-}++infix 4 `notElem`+-- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')+notElem :: (G.Vector u a, G.Vector v b, Eq a, Eq b) => (a, b) -> Vector u v (a, b) -> Bool+notElem = G.notElem+{-# INLINE notElem #-}++-- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'+-- if no such element exists.+find :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> Maybe (a, b)+find = G.find+{-# INLINE find #-}++-- | /O(n)/ Yield 'Just' the index of the first element matching the predicate+-- or 'Nothing' if no such element exists.+findIndex :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> Maybe Int+findIndex = G.findIndex+{-# INLINE findIndex #-}++{-+-- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending+-- order.+findIndices :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> Vector u v Int+findIndices = G.findIndices+{-# INLINE findIndices #-}+-}++-- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or+-- 'Nothing' if the vector does not contain the element. This is a specialised+-- version of 'findIndex'.+elemIndex :: (G.Vector u a, G.Vector v b, Eq a, Eq b) => (a, b) -> Vector u v (a, b) -> Maybe Int+elemIndex = G.elemIndex+{-# INLINE elemIndex #-}++{-+-- | /O(n)/ Yield the indices of all occurences of the given element in+-- ascending order. This is a specialised version of 'findIndices'.+elemIndices :: (G.Vector u a, G.Vector v b, Eq a, Eq b) => (a, b) -> Vector u v (a, b) -> Vector Int+elemIndices = G.elemIndices+{-# INLINE elemIndices #-}+-}++-- Folding+-- -------++-- | /O(n)/ Left fold+foldl :: (G.Vector u a, G.Vector v b) => (r -> (a, b) -> r) -> r -> Vector u v (a, b) -> r+foldl = G.foldl+{-# INLINE foldl #-}++-- | /O(n)/ Left fold on non-empty vectors+foldl1 :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> (a, b)) -> Vector u v (a, b) -> (a, b)+foldl1 = G.foldl1+{-# INLINE foldl1 #-}++-- | /O(n)/ Left fold with strict accumulator+foldl' :: (G.Vector u a, G.Vector v b) => (r -> (a, b) -> r) -> r -> Vector u v (a, b) -> r+foldl' = G.foldl'+{-# INLINE foldl' #-}++-- | /O(n)/ Left fold on non-empty vectors with strict accumulator+foldl1' :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> (a, b)) -> Vector u v (a, b) -> (a, b)+foldl1' = G.foldl1'+{-# INLINE foldl1' #-}++-- | /O(n)/ Right fold+foldr :: (G.Vector u a, G.Vector v b) => ((a, b) -> r -> r) -> r -> Vector u v (a, b) -> r+foldr = G.foldr+{-# INLINE foldr #-}++-- | /O(n)/ Right fold on non-empty vectors+foldr1 :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> (a, b)) -> Vector u v (a, b) -> (a, b)+foldr1 = G.foldr1+{-# INLINE foldr1 #-}++-- | /O(n)/ Right fold with a strict accumulator+foldr' :: (G.Vector u a, G.Vector v b) => ((a, b) -> r -> r) -> r -> Vector u v (a, b) -> r+foldr' = G.foldr'+{-# INLINE foldr' #-}++-- | /O(n)/ Right fold on non-empty vectors with strict accumulator+foldr1' :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> (a, b)) -> Vector u v (a, b) -> (a, b)+foldr1' = G.foldr1'+{-# INLINE foldr1' #-}++-- | /O(n)/ Left fold (function applied to each element and its index)+ifoldl :: (G.Vector u a, G.Vector v b) => (r -> Int -> (a, b) -> r) -> r -> Vector u v (a, b) -> r+ifoldl = G.ifoldl+{-# INLINE ifoldl #-}++-- | /O(n)/ Left fold with strict accumulator (function applied to each element+-- and its index)+ifoldl' :: (G.Vector u a, G.Vector v b) => (r -> Int -> (a, b) -> r) -> r -> Vector u v (a, b) -> r+ifoldl' = G.ifoldl'+{-# INLINE ifoldl' #-}++-- | /O(n)/ Right fold (function applied to each element and its index)+ifoldr :: (G.Vector u a, G.Vector v b) => (Int -> (a, b) -> r -> r) -> r -> Vector u v (a, b) -> r+ifoldr = G.ifoldr+{-# INLINE ifoldr #-}++-- | /O(n)/ Right fold with strict accumulator (function applied to each+-- element and its index)+ifoldr' :: (G.Vector u a, G.Vector v b) => (Int -> (a, b) -> r -> r) -> r -> Vector u v (a, b) -> r+ifoldr' = G.ifoldr'+{-# INLINE ifoldr' #-}++-- Specialised folds+-- -----------------++-- | /O(n)/ Check if all elements satisfy the predicate.+all :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> Bool+{-# INLINE all #-}+all = G.all++-- | /O(n)/ Check if any element satisfies the predicate.+any :: (G.Vector u a, G.Vector v b) => ((a, b) -> Bool) -> Vector u v (a, b) -> Bool+{-# INLINE any #-}+any = G.any++{-+-- | /O(n)/ Compute the sum of the elements+sum :: (G.Vector u a, G.Vector v b, Num a) => Vector u v (a, b) -> (a, b)+{-# INLINE sum #-}+sum = G.sum++-- | /O(n)/ Compute the product of the elements+product :: ((G.Vector u a, G.Vector v b), Num a) => Vector u v (a, b) -> (a, b)+{-# INLINE product #-}+product = G.product+-}++-- | /O(n)/ Yield the maximum element of the vector. The vector may not be+-- empty.+maximum :: (G.Vector u a, G.Vector v b, Ord a, Ord b) => Vector u v (a, b) -> (a, b)+{-# INLINE maximum #-}+maximum = G.maximum++-- | /O(n)/ Yield the maximum element of the vector according to the given+-- comparison function. The vector may not be empty.+maximumBy :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> Ordering) -> Vector u v (a, b) -> (a, b)+{-# INLINE maximumBy #-}+maximumBy = G.maximumBy++-- | /O(n)/ Yield the minimum element of the vector. The vector may not be+-- empty.+minimum :: (G.Vector u a, G.Vector v b, Ord a, Ord b) => Vector u v (a, b) -> (a, b)+{-# INLINE minimum #-}+minimum = G.minimum++-- | /O(n)/ Yield the minimum element of the vector according to the given+-- comparison function. The vector may not be empty.+minimumBy :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> Ordering) -> Vector u v (a, b) -> (a, b)+{-# INLINE minimumBy #-}+minimumBy = G.minimumBy++-- | /O(n)/ Yield the index of the maximum element of the vector. The vector+-- may not be empty.+maxIndex :: (G.Vector u a, G.Vector v b, Ord a, Ord b) => Vector u v (a, b) -> Int+{-# INLINE maxIndex #-}+maxIndex = G.maxIndex++-- | /O(n)/ Yield the index of the maximum element of the vector according to+-- the given comparison function. The vector may not be empty.+maxIndexBy :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> Ordering) -> Vector u v (a, b) -> Int+{-# INLINE maxIndexBy #-}+maxIndexBy = G.maxIndexBy++-- | /O(n)/ Yield the index of the minimum element of the vector. The vector+-- may not be empty.+minIndex :: (G.Vector u a, G.Vector v b, Ord a, Ord b) => Vector u v (a, b) -> Int+{-# INLINE minIndex #-}+minIndex = G.minIndex++-- | /O(n)/ Yield the index of the minimum element of the vector according to+-- the given comparison function. The vector may not be empty.+minIndexBy :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> Ordering) -> Vector u v (a, b) -> Int+{-# INLINE minIndexBy #-}+minIndexBy = G.minIndexBy++-- Monadic folds+-- -------------++-- | /O(n)/ Monadic fold+foldM :: (Monad m, G.Vector u a, G.Vector v b) => (r -> (a, b) -> m r) -> r -> Vector u v (a, b) -> m r+foldM = G.foldM+{-# INLINE foldM #-}++-- | /O(n)/ Monadic fold over non-empty vectors+fold1M :: (Monad m, G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> m (a, b)) -> Vector u v (a, b) -> m (a, b)+{-# INLINE fold1M #-}+fold1M = G.fold1M++-- | /O(n)/ Monadic fold with strict accumulator+foldM' :: (Monad m, G.Vector u a, G.Vector v b) => (r -> (a, b) -> m r) -> r -> Vector u v (a, b) -> m r+{-# INLINE foldM' #-}+foldM' = G.foldM'++-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator+fold1M' :: (Monad m, G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> m (a, b)) -> Vector u v (a, b) -> m (a, b)+{-# INLINE fold1M' #-}+fold1M' = G.fold1M'++-- | /O(n)/ Monadic fold that discards the result+foldM_ :: (Monad m, G.Vector u a, G.Vector v b) => (r -> (a, b) -> m r) -> r -> Vector u v (a, b) -> m ()+{-# INLINE foldM_ #-}+foldM_ = G.foldM_++-- | /O(n)/ Monadic fold over non-empty vectors that discards the result+fold1M_ :: (Monad m, G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> m (a, b)) -> Vector u v (a, b) -> m ()+{-# INLINE fold1M_ #-}+fold1M_ = G.fold1M_++-- | /O(n)/ Monadic fold with strict accumulator that discards the result+foldM'_ :: (Monad m, G.Vector u a, G.Vector v b) => (r -> (a, b) -> m r) -> r -> Vector u v (a, b) -> m ()+{-# INLINE foldM'_ #-}+foldM'_ = G.foldM'_++-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator+-- that discards the result+fold1M'_ :: (Monad m, G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> m (a, b)) -> Vector u v (a, b) -> m ()+{-# INLINE fold1M'_ #-}+fold1M'_ = G.fold1M'_+++-- Prefix sums (scans)+-- -------------------++-- | /O(n)/ Prescan+--+-- @+-- prescanl f z = 'init' . 'scanl' f z+-- @+--+-- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@+--+prescanl :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (a, b)) -> (a, b) -> Vector u v (c, d) -> Vector u v (a, b)+prescanl = G.prescanl+{-# INLINE prescanl #-}++-- | /O(n)/ Prescan with strict accumulator+prescanl' :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (a, b)) -> (a, b) -> Vector u v (c, d) -> Vector u v (a, b)+prescanl' = G.prescanl'+{-# INLINE prescanl' #-}++-- | /O(n)/ Scan+--+-- @+-- postscanl f z = 'tail' . 'scanl' f z+-- @+--+-- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@+--+postscanl :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (a, b)) -> (a, b) -> Vector u v (c, d) -> Vector u v (a, b)+postscanl = G.postscanl+{-# INLINE postscanl #-}++-- | /O(n)/ Scan with strict accumulator+postscanl' :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (a, b)) -> (a, b) -> Vector u v (c, d) -> Vector u v (a, b)+postscanl' = G.postscanl'+{-# INLINE postscanl' #-}++-- | /O(n)/ Haskell-style scan+--+-- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>+-- >   where y1 = z+-- >         yi = f y(i-1) x(i-1)+--+-- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@+--+scanl :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (a, b)) -> (a, b) -> Vector u v (c, d) -> Vector u v (a, b)+scanl = G.scanl+{-# INLINE scanl #-}++-- | /O(n)/ Haskell-style scan with strict accumulator+scanl' :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (a, b)) -> (a, b) -> Vector u v (c, d) -> Vector u v (a, b)+scanl' = G.scanl'+{-# INLINE scanl' #-}++-- | /O(n)/ Scan over a non-empty vector+--+-- > scanl f <x1,...,xn> = <y1,...,yn>+-- >   where y1 = x1+-- >         yi = f y(i-1) xi+--+scanl1 :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> (a, b)) -> Vector u v (a, b) -> Vector u v (a, b)+scanl1 = G.scanl1+{-# INLINE scanl1 #-}++-- | /O(n)/ Scan over a non-empty vector with a strict accumulator+scanl1' :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> (a, b)) -> Vector u v (a, b) -> Vector u v (a, b)+scanl1' = G.scanl1'+{-# INLINE scanl1' #-}++-- | /O(n)/ Right-to-left prescan+--+-- @+-- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'+-- @+--+prescanr :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (c, d)) -> (c, d) -> Vector u v (a, b) -> Vector u v (c, d)+{-# INLINE prescanr #-}+prescanr = G.prescanr++-- | /O(n)/ Right-to-left prescan with strict accumulator+prescanr' :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (c, d)) -> (c, d) -> Vector u v (a, b) -> Vector u v (c, d)+prescanr' = G.prescanr'+{-# INLINE prescanr' #-}++-- | /O(n)/ Right-to-left scan+postscanr :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (c, d)) -> (c, d) -> Vector u v (a, b) -> Vector u v (c, d)+postscanr = G.postscanr+{-# INLINE postscanr #-}++-- | /O(n)/ Right-to-left scan with strict accumulator+postscanr' :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (c, d)) -> (c, d) -> Vector u v (a, b) -> Vector u v (c, d)+postscanr' = G.postscanr'+{-# INLINE postscanr' #-}++-- | /O(n)/ Right-to-left Haskell-style scan+scanr :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (c, d)) -> (c, d) -> Vector u v (a, b) -> Vector u v (c, d)+scanr = G.scanr+{-# INLINE scanr #-}++-- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator+scanr' :: (G.Vector u a, G.Vector v b, G.Vector u c, G.Vector v d) => ((a, b) -> (c, d) -> (c, d)) -> (c, d) -> Vector u v (a, b) -> Vector u v (c, d)+scanr' = G.scanr'+{-# INLINE scanr' #-}++-- | /O(n)/ Right-to-left scan over a non-empty vector+scanr1 :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> (a, b)) -> Vector u v (a, b) -> Vector u v (a, b)+{-# INLINE scanr1 #-}+scanr1 = G.scanr1++-- | /O(n)/ Right-to-left scan over a non-empty vector with a strict+-- accumulator+scanr1' :: (G.Vector u a, G.Vector v b) => ((a, b) -> (a, b) -> (a, b)) -> Vector u v (a, b) -> Vector u v (a, b)+{-# INLINE scanr1' #-}+scanr1' = G.scanr1'++-- Conversions - Lists+-- ------------------------++projectFst :: Vector u v (a, b) -> u a+projectFst (V as _) = as+{-# INLINE projectFst #-}++projectSnd :: Vector u v (a, b) -> v b+projectSnd (V _ bs) = bs+{-# INLINE projectSnd #-}++-- | Warning: The vectors are assumed to have the same length. This is not checked!+unsafeZip :: u a -> v b -> Vector u v (a, b)+unsafeZip = V+{-# INLINE unsafeZip #-}++-- | /O(n)/ Convert a vector to a list+toList :: (G.Vector u a, G.Vector v b) => Vector u v (a, b) -> [(a, b)]+toList = G.toList+{-# INLINE toList #-}++-- | /O(n)/ Convert a list to a vector+fromList :: (G.Vector u a, G.Vector v b) => [(a, b)] -> Vector u v (a, b)+fromList = G.fromList+{-# INLINE fromList #-}++-- | /O(n)/ Convert the first @n@ elements of a list to a vector+--+-- @+-- fromListN n xs = 'fromList' ('take' n xs)+-- @+fromListN :: (G.Vector u a, G.Vector v b) => Int -> [(a, b)] -> Vector u v (a, b)+fromListN = G.fromListN+{-# INLINE fromListN #-}++-- Conversions - Mutable vectors+-- -----------------------------++-- | /O(1)/ Unsafe convert a mutable vector to an immutable one without+-- copying. The mutable vector may not be used after this operation.+unsafeFreeze :: (G.Vector u a, G.Vector v b, PrimMonad m) => G.Mutable (Vector u v) (PrimState m) (a, b) -> m (Vector u v (a, b))+unsafeFreeze = G.unsafeFreeze+{-# INLINE unsafeFreeze #-}++-- | /O(1)/ Unsafely convert an immutable vector to a mutable one without+-- copying. The immutable vector may not be used after this operation.+unsafeThaw :: (G.Vector u a, G.Vector v b, PrimMonad m) => Vector u v (a, b) -> m (G.Mutable (Vector u v) (PrimState m) (a, b))+unsafeThaw = G.unsafeThaw+{-# INLINE unsafeThaw #-}++-- | /O(n)/ Yield a mutable copy of the immutable vector.+thaw :: (G.Vector u a, G.Vector v b, PrimMonad m) => Vector u v (a, b) -> m (G.Mutable (Vector u v) (PrimState m) (a, b))+thaw = G.thaw+{-# INLINE thaw #-}++-- | /O(n)/ Yield an immutable copy of the mutable vector.+freeze :: (G.Vector u a, G.Vector v b, PrimMonad m) => G.Mutable (Vector u v) (PrimState m) (a, b) -> m (Vector u v (a, b))+freeze = G.freeze+{-# INLINE freeze #-}++-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must+-- have the same length. This is not checked.+unsafeCopy+  :: (G.Vector u a, G.Vector v b, PrimMonad m) => G.Mutable (Vector u v) (PrimState m) (a, b) -> Vector u v (a, b) -> m ()+unsafeCopy = G.unsafeCopy+{-# INLINE unsafeCopy #-}++-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must+-- have the same length.+copy :: (G.Vector u a, G.Vector v b, PrimMonad m) => G.Mutable (Vector u v) (PrimState m) (a, b) -> Vector u v (a, b) -> m ()+copy = G.copy+{-# INLINE copy #-}

@@ -0,0 +1,174 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE GADTs #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE ScopedTypeVariables #-}++#ifndef MIN_VERSION_base+#define MIN_VERSION_base(x,y,z) 1+#endif++module Data.Vector.Hybrid.Internal+  ( MVector(..)+  , Vector(..)+  ) where++import Control.Monad+import Data.Monoid+import qualified Data.Vector.Generic.Mutable as GM+import qualified Data.Vector.Generic as G+import Data.Vector.Fusion.Stream as Stream+import Data.Data+import Prelude hiding ( length, null, replicate, reverse, map, read, take, drop, init, tail )+import Text.Read++data MVector :: (* -> * -> *) -> (* -> * -> *) -> * -> * -> * where+  MV :: !(u s a) -> !(v s b) -> MVector u v s (a, b)++#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 707+ deriving Typeable+#else++-- custom Typeable+instance (Typeable2 u, Typeable2 v) => Typeable2 (MVector u v) where+  typeOf2 (_ :: MVector u v s ab) = mkTyConApp mvectorTyCon [typeOf2 (undefined :: u s a), typeOf2 (undefined :: v s b)]++mvectorTyCon :: TyCon+#if MIN_VERSION_base(4,4,0)+mvectorTyCon = mkTyCon3 "hybrid-vectors" "Data.Vector.Hybrid.Internal" "MVector"+#else+mvectorTyCon = mkTyCon "Data.Vector.Hybrid.Internal.MVector"+#endif++#endif++instance (GM.MVector u a, GM.MVector v b) => GM.MVector (MVector u v) (a, b) where+  basicLength (MV ks _) = GM.basicLength ks+  {-# INLINE basicLength #-}+  basicUnsafeSlice s e (MV ks vs) = MV (GM.basicUnsafeSlice s e ks) (GM.basicUnsafeSlice s e vs)+  {-# INLINE basicUnsafeSlice #-}+  basicOverlaps (MV ks vs) (MV ks' vs') = GM.basicOverlaps ks ks' || GM.basicOverlaps vs vs'+  {-# INLINE basicOverlaps #-}+  basicUnsafeNew n = liftM2 MV (GM.basicUnsafeNew n) (GM.basicUnsafeNew n)+  {-# INLINE basicUnsafeNew #-}+  basicUnsafeReplicate n (k,v) = liftM2 MV (GM.basicUnsafeReplicate n k) (GM.basicUnsafeReplicate n v)+  {-# INLINE basicUnsafeReplicate #-}+  basicUnsafeRead (MV ks vs) n = liftM2 (,) (GM.basicUnsafeRead ks n) (GM.basicUnsafeRead vs n)+  {-# INLINE basicUnsafeRead #-}+  basicUnsafeWrite (MV ks vs) n (k,v) = do+    GM.basicUnsafeWrite ks n k+    GM.basicUnsafeWrite vs n v+  {-# INLINE basicUnsafeWrite #-}+  basicClear (MV ks vs) = do+    GM.basicClear ks+    GM.basicClear vs+  {-# INLINE basicClear #-}+  basicSet (MV ks vs) (k,v) = do+    GM.basicSet ks k+    GM.basicSet vs v+  {-# INLINE basicSet #-}+  basicUnsafeCopy (MV ks vs) (MV ks' vs') = do+    GM.basicUnsafeCopy ks ks'+    GM.basicUnsafeCopy vs vs'+  {-# INLINE basicUnsafeCopy #-}+  basicUnsafeMove (MV ks vs) (MV ks' vs') = do+    GM.basicUnsafeMove ks ks'+    GM.basicUnsafeMove vs vs'+  {-# INLINE basicUnsafeMove #-}+  basicUnsafeGrow (MV ks vs) n = liftM2 MV (GM.basicUnsafeGrow ks n) (GM.basicUnsafeGrow vs n)+  {-# INLINE basicUnsafeGrow #-}++-- hybrid vectors+data Vector :: (* -> *) -> (* -> *) -> * -> * where+  V :: !(u a) -> !(v b) -> Vector u v (a, b)++#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 707+ deriving Typeable+#else++-- custom Typeable+instance (Typeable1 u, Typeable1 v) => Typeable1 (Vector u v) where+  typeOf1 (_ :: Vector u v ab) = mkTyConApp vectorTyCon [typeOf1 (undefined :: u a), typeOf1 (undefined :: v b)]++vectorTyCon :: TyCon+#if MIN_VERSION_base(4,4,0)+vectorTyCon = mkTyCon3 "hybrid-vectors" "Data.Vector.Hybrid.Internal" "Vector"+#else+vectorTyCon = mkTyCon "Data.Vector.Hybrid.Internal.Vector"+#endif++#endif++type instance G.Mutable (Vector u v) = MVector (G.Mutable u) (G.Mutable v)++instance (G.Vector u a, G.Vector v b) => G.Vector (Vector u v) (a, b) where+  basicUnsafeFreeze (MV ks vs) = liftM2 V (G.basicUnsafeFreeze ks) (G.basicUnsafeFreeze vs)+  {-# INLINE basicUnsafeFreeze #-}+  basicUnsafeThaw (V ks vs) = liftM2 MV (G.basicUnsafeThaw ks) (G.basicUnsafeThaw vs)+  {-# INLINE basicUnsafeThaw #-}+  basicLength (V ks _) = G.basicLength ks+  {-# INLINE basicLength #-}+  basicUnsafeSlice i j (V ks vs) = V (G.basicUnsafeSlice i j ks) (G.basicUnsafeSlice i j vs)+  {-# INLINE basicUnsafeSlice #-}+  basicUnsafeIndexM (V ks vs) n = liftM2 (,) (G.basicUnsafeIndexM ks n) (G.basicUnsafeIndexM vs n)+  {-# INLINE basicUnsafeIndexM #-}+  basicUnsafeCopy (MV ks vs) (V ks' vs') = do+    G.basicUnsafeCopy ks ks'+    G.basicUnsafeCopy vs vs'+  {-# INLINE basicUnsafeCopy #-}+  elemseq (V ks vs) (k,v) b = G.elemseq ks k (G.elemseq vs v b)+  {-# INLINE elemseq #-}++instance (G.Vector u a, G.Vector v b, c ~ (a, b)) => Monoid (Vector u v c) where+  mappend = (G.++)+  {-# INLINE mappend #-}+  mempty = G.empty+  {-# INLINE mempty #-}+  mconcat = G.concat+  {-# INLINE mconcat #-}++instance (G.Vector u a, G.Vector v b, Show a, Show b, c ~ (a, b)) => Show (Vector u v c) where+  showsPrec = G.showsPrec++instance (G.Vector u a, G.Vector v b, Read a, Read b, c ~ (a, b)) => Read (Vector u v c) where+  readPrec = G.readPrec+  readListPrec = readListPrecDefault++instance (Data a, Data b, Typeable1 u, Typeable1 v, G.Vector u a, G.Vector v b, c ~ (a, b)) => Data (Vector u v c) where+  gfoldl       = G.gfoldl+  toConstr _   = error "toConstr" -- TODO: virtual constructor+  gunfold _ _  = error "gunfold"  -- TODO: virtual constructor+  dataTypeOf _ = G.mkType "Data.Vector.Hybrid.Vector"+  dataCast1    = G.dataCast+++instance (G.Vector u a, G.Vector v b, Eq a, Eq b, c ~ (a, b)) => Eq (Vector u v c) where+  xs == ys = Stream.eq (G.stream xs) (G.stream ys)+  {-# INLINE (==) #-}++  xs /= ys = not (Stream.eq (G.stream xs) (G.stream ys))+  {-# INLINE (/=) #-}+++-- See http://trac.haskell.org/vector/ticket/12+instance (G.Vector u a, G.Vector v b, Ord a, Ord b, c ~ (a, b)) => Ord (Vector u v c) where+  {-# INLINE compare #-}+  compare xs ys = Stream.cmp (G.stream xs) (G.stream ys)++  {-# INLINE (<) #-}+  xs < ys = Stream.cmp (G.stream xs) (G.stream ys) == LT++  {-# INLINE (<=) #-}+  xs <= ys = Stream.cmp (G.stream xs) (G.stream ys) /= GT++  {-# INLINE (>) #-}+  xs > ys = Stream.cmp (G.stream xs) (G.stream ys) == GT++  {-# INLINE (>=) #-}+  xs >= ys = Stream.cmp (G.stream xs) (G.stream ys) /= LT+

@@ -0,0 +1,286 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE GADTs #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE ScopedTypeVariables #-}++#ifndef MIN_VERSION_base+#define MIN_VERSION_base(x,y,z) 1+#endif++module Data.Vector.Hybrid.Mutable+  ( MVector+  , IOVector+  , STVector++  -- * Accessors++  -- ** Length information+  , length, null++  -- ** Extracting subvectors+  , slice, init, tail, take, drop+  , unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop++  -- ** Overlapping+  , overlaps++  -- * Construction++  -- ** Initialisation+  , new, unsafeNew, replicate, clone++  -- ** Growing+  , grow, unsafeGrow++  -- ** Restricting memory usage+  , clear++  -- * Accessing individual elements+  , read, write, swap+  , unsafeRead, unsafeWrite, unsafeSwap++  -- * Modifying vectors++  -- ** Filling and copying+  , set, copy, unsafeCopy++  -- * Unsafe Construction and deconstruction+  , unsafeZip, projectFst, projectSnd++  -- * Deprecated operations+  , newWith, unsafeNewWith+  ) where++import Control.Monad.Primitive+import qualified Data.Vector.Generic.Mutable as G+import Data.Vector.Hybrid.Internal+import Prelude hiding ( length, null, replicate, reverse, map, read, take, drop, init, tail )++type IOVector u v = MVector u v RealWorld++type STVector = MVector++-- Length information+-- ------------------++-- | Length of the mutable vector.+length :: G.MVector u a => MVector u v s (a, b) -> Int+length (MV ks _) = G.length ks+{-# INLINE length #-}++-- | Check whether the vector is empty+null :: G.MVector u a => MVector u v s (a, b) -> Bool+null (MV ks _) = G.null ks+{-# INLINE null #-}++-- Extracting subvectors+-- ---------------------++-- | Yield a part of the mutable vector without copying it.+slice :: (G.MVector u a, G.MVector v b) => Int -> Int -> MVector u v s (a, b) -> MVector u v s (a, b)+slice = G.slice+{-# INLINE slice #-}++take :: (G.MVector u a, G.MVector v b) => Int -> MVector u v s (a, b) -> MVector u v s (a, b)+take = G.take+{-# INLINE take #-}++drop :: (G.MVector u a, G.MVector v b) => Int -> MVector u v s (a, b) -> MVector u v s (a, b)+drop = G.drop+{-# INLINE drop #-}++init :: (G.MVector u a, G.MVector v b) => MVector u v s (a, b) -> MVector u v s (a, b)+init = G.init+{-# INLINE init #-}++tail :: (G.MVector u a, G.MVector v b) => MVector u v s (a, b) -> MVector u v s (a, b)+tail = G.tail+{-# INLINE tail #-}++-- | Yield a part of the mutable vector without copying it. No bounds checks+-- are performed.+unsafeSlice :: (G.MVector u a, G.MVector v b)+            => Int  -- ^ starting index+            -> Int  -- ^ length of the slice+            -> MVector u v s (a, b)+            -> MVector u v s (a, b)+unsafeSlice = G.unsafeSlice+{-# INLINE unsafeSlice #-}++unsafeTake :: (G.MVector u a, G.MVector v b) => Int -> MVector u v s (a, b) -> MVector u v s (a, b)+unsafeTake = G.unsafeTake+{-# INLINE unsafeTake #-}++unsafeDrop :: (G.MVector u a, G.MVector v b) => Int -> MVector u v s (a, b) -> MVector u v s (a, b)+unsafeDrop = G.unsafeDrop+{-# INLINE unsafeDrop #-}++unsafeInit :: (G.MVector u a, G.MVector v b) => MVector u v s (a, b) -> MVector u v s (a, b)+unsafeInit = G.unsafeInit+{-# INLINE unsafeInit #-}++unsafeTail :: (G.MVector u a, G.MVector v b) => MVector u v s (a, b) -> MVector u v s (a, b)+unsafeTail = G.unsafeTail+{-# INLINE unsafeTail #-}++-- Overlapping+-- -----------++-- Check whether two vectors overlap.+overlaps :: (G.MVector u a, G.MVector v b) => MVector u v s (a, b) -> MVector u v s (a, b) -> Bool+overlaps = G.overlaps+{-# INLINE overlaps #-}++-- Initialisation+-- --------------++-- | Create a mutable vector of the given length.+new :: (PrimMonad m, G.MVector u a, G.MVector v b) => Int -> m (MVector u v (PrimState m) (a, b))+new = G.new+{-# INLINE new #-}++-- | Create a mutable vector of the given length. The length is not checked.+unsafeNew :: (PrimMonad m, G.MVector u a, G.MVector v b) => Int -> m (MVector u v (PrimState m) (a, b))+unsafeNew = G.unsafeNew+{-# INLINE unsafeNew #-}++-- | Create a mutable vector of the given length (0 if the length is negative)+-- and fill it with an initial value.+replicate :: (PrimMonad m, G.MVector u a, G.MVector v b) => Int -> (a, b) -> m (MVector u v (PrimState m) (a, b))+replicate = G.replicate+{-# INLINE replicate #-}++-- | Create a copy of a mutable vector.+clone :: (PrimMonad m, G.MVector u a, G.MVector v b)+      => MVector u v (PrimState m) (a, b) -> m (MVector u v (PrimState m) (a, b))+clone = G.clone+{-# INLINE clone #-}++-- Growing+-- -------++-- | Grow a vector by the given number of elements. The number must be+-- positive.+grow :: (PrimMonad m, G.MVector u a, G.MVector v b)+     => MVector u v (PrimState m) (a, b) -> Int -> m (MVector u v (PrimState m) (a, b))+grow = G.grow+{-# INLINE grow #-}++-- | Grow a vector by the given number of elements. The number must be+-- positive but this is not checked.+unsafeGrow :: (PrimMonad m, G.MVector u a, G.MVector v b)+               => MVector u v (PrimState m) (a, b) -> Int -> m (MVector u v (PrimState m) (a, b))+unsafeGrow = G.unsafeGrow+{-# INLINE unsafeGrow #-}++-- Restricting memory usage+-- ------------------------++-- | Reset all elements of the vector to some undefined value, clearing all+-- references to external objects. This is usually a noop for unboxed vectors. +clear :: (PrimMonad m, G.MVector u a, G.MVector v b) => MVector u v (PrimState m) (a, b) -> m ()+clear = G.clear+{-# INLINE clear #-}++-- Accessing individual elements+-- -----------------------------++-- | Yield the element at the given position.+read :: (PrimMonad m, G.MVector u a, G.MVector v b)+     => MVector u v (PrimState m) (a, b) -> Int -> m (a, b)+read = G.read+{-# INLINE read #-}++-- | Replace the element at the given position.+write :: (PrimMonad m, G.MVector u a, G.MVector v b)+      => MVector u v (PrimState m) (a, b) -> Int -> (a, b) -> m ()+write = G.write+{-# INLINE write #-}++-- | Swap the elements at the given positions.+swap :: (PrimMonad m, G.MVector u a, G.MVector v b)+     => MVector u v (PrimState m) (a, b) -> Int -> Int -> m ()+swap = G.swap+{-# INLINE swap #-}+++-- | Yield the element at the given position. No bounds checks are performed.+unsafeRead :: (PrimMonad m, G.MVector u a, G.MVector v b)+           => MVector u v (PrimState m) (a, b) -> Int -> m (a, b)+unsafeRead = G.unsafeRead+{-# INLINE unsafeRead #-}++-- | Replace the element at the given position. No bounds checks are performed.+unsafeWrite :: (PrimMonad m, G.MVector u a, G.MVector v b)+            =>  MVector u v (PrimState m) (a, b) -> Int -> (a, b) -> m ()+unsafeWrite = G.unsafeWrite+{-# INLINE unsafeWrite #-}++-- | Swap the elements at the given positions. No bounds checks are performed.+unsafeSwap+    :: (PrimMonad m, G.MVector u a, G.MVector v b)+    => MVector u v (PrimState m) (a, b) -> Int -> Int -> m ()+unsafeSwap = G.unsafeSwap+{-# INLINE unsafeSwap #-}++-- Filling and copying+-- -------------------++-- | Set all elements of the vector to the given value.+set :: (PrimMonad m, G.MVector u a, G.MVector v b)+    => MVector u v (PrimState m) (a, b) -> (a, b) -> m ()+set = G.set+{-# INLINE set #-}++-- | Copy a vector. The two vectors must have the same length and may not+-- overlap.+copy :: (PrimMonad m, G.MVector u a, G.MVector v b)+     => MVector u v (PrimState m) (a, b) -> MVector u v (PrimState m) (a, b) -> m ()+copy = G.copy+{-# INLINE copy #-}++-- | Copy a vector. The two vectors must have the same length and may not+-- overlap. This is not checked.+unsafeCopy :: (PrimMonad m, G.MVector u a, G.MVector v b)+           => MVector u v (PrimState m) (a, b)   -- ^ target+           -> MVector u v (PrimState m) (a, b)   -- ^ source+           -> m ()+{-# INLINE unsafeCopy #-}+unsafeCopy = G.unsafeCopy++-- Unsafe composition and decomposition+-- ------------------------------------++-- | The mutable vectors are assumed to be of the same length and to not overlap. This is not checked.+unsafeZip :: u s a -> v s b -> MVector u v s (a, b)+unsafeZip = MV+{-# INLINE unsafeZip #-}++projectFst :: MVector u v s (a, b) -> u s a+projectFst (MV ks _) = ks+{-# INLINE projectFst #-}++projectSnd :: MVector u v s (a, b) -> v s b+projectSnd (MV _ vs) = vs+{-# INLINE projectSnd #-}++-- Deprecated functions+-- --------------------++-- | /DEPRECATED/ Use 'replicate' instead+newWith :: (PrimMonad m, G.MVector u a, G.MVector v b) => Int -> (a, b) -> m (MVector u v (PrimState m) (a, b))+newWith = G.replicate+{-# INLINE newWith #-}++-- | /DEPRECATED/ Use 'replicate' instead+unsafeNewWith :: (PrimMonad m, G.MVector u a, G.MVector v b) => Int -> (a, b) -> m (MVector u v (PrimState m) (a, b))+unsafeNewWith = G.replicate+{-# INLINE unsafeNewWith #-}++{-# DEPRECATED newWith, unsafeNewWith "Use replicate instead" #-}

@@ -0,0 +1,1483 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE Rank2Types #-}+{-# LANGUAGE BangPatterns #-}+-----------------------------------------------------------------------------+-- |+-- Copyright   :  (C) 2013 Edward Kmett,+-- License     :  BSD-style (see the file LICENSE)+--+-- Maintainer  :  Edward Kmett <ekmett@gmail.com>+-- Stability   :  experimental+-- Portability :  non-portable+--+-- A mixed 'Vector' lets you make a 'Vector' out of any other vector type+-- you have lying around, and all of the combinators are defined to allow+-- you to freely mix input vector type wherever possible.+--+-- This enables you to work with a mixture of boxed and unboxed data.+-----------------------------------------------------------------------------+module Data.Vector.Mixed+  (+  -- * Mixed vectors+    Vector, MVector, Mixed(..)++  -- * Accessors++  -- ** Length information+  , length+  , null++  -- ** Indexing+  , (!), (!?), head, last+  , unsafeIndex, unsafeHead, unsafeLast++  -- ** Monadic indexing+  , indexM, headM, lastM+  , unsafeIndexM, unsafeHeadM, unsafeLastM++  -- ** Extracting subvectors (slicing)+  , slice, init, tail, take, drop, splitAt+  , unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop++  -- * Construction++  -- ** Initialisation+  , empty, singleton, replicate, generate, iterateN++  -- ** Monadic initialisation+  , replicateM, generateM, create++  -- ** Unfolding+  , unfoldr, unfoldrN+  , constructN, constructrN++  -- ** Enumeration+  , enumFromN, enumFromStepN, enumFromTo, enumFromThenTo++  -- ** Concatenation+  , cons, snoc, (++), concat++  -- ** Restricting memory usage+  , force++  -- * Modifying vectors++  -- ** Bulk updates+  , (//), update, update_+  , unsafeUpd, unsafeUpdate, unsafeUpdate_++  -- ** Accumulations+  , accum, accumulate, accumulate_+  , unsafeAccum, unsafeAccumulate, unsafeAccumulate_++  -- ** Permutations+  , reverse, backpermute, unsafeBackpermute++  -- ** Safe destructive updates+  , modify++  -- * Elementwise operations++  -- ** Indexing+  , indexed++  -- ** Mapping+  , map, imap, concatMap++  -- ** Monadic mapping+  , mapM, mapM_, forM, forM_++  -- ** Zipping+  , zipWith, zipWith3, zipWith4, zipWith5, zipWith6+  , izipWith, izipWith3, izipWith4, izipWith5, izipWith6+  , zip, zip3, zip4, zip5, zip6++  -- ** Monadic zipping+  , zipWithM, zipWithM_++  -- ** Unzipping+  , unzip, unzip3, unzip4, unzip5, unzip6++  -- * Working with predicates++  -- ** Filtering+  , filter, ifilter, filterM+  , takeWhile, dropWhile++  -- ** Partitioning+  , partition, unstablePartition, span, break++  -- ** Searching+  , elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices++  -- * Folding+  , foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1'+  , ifoldl, ifoldl', ifoldr, ifoldr'++  -- ** Specialised folds+  , all, any, and, or+  , sum, product+  , maximum, maximumBy, minimum, minimumBy+  , minIndex, minIndexBy, maxIndex, maxIndexBy++  -- ** Monadic folds+  , foldM, foldM', fold1M, fold1M'+  , foldM_, foldM'_, fold1M_, fold1M'_++  -- ** Monadic sequencing+  , sequence, sequence_++  -- * Prefix sums (scans)+  , prescanl, prescanl'+  , postscanl, postscanl'+  , scanl, scanl', scanl1, scanl1'+  , prescanr, prescanr'+  , postscanr, postscanr'+  , scanr, scanr', scanr1, scanr1'++  -- * Conversions++  -- ** Lists+  , toList, fromList, fromListN++  -- ** Other vector types+  , G.convert++  -- ** Mutable vectors+  , freeze, thaw, copy, unsafeFreeze, unsafeThaw, unsafeCopy+  ) where+++-- import qualified Data.Vector.Hybrid.Internal as H+import qualified Data.Vector.Generic as G+import qualified Data.Vector.Generic.Mutable as GM+import qualified Data.Vector.Generic.New as New+import Data.Vector.Mixed.Internal+import Data.Vector.Internal.Check as Ck+import qualified Data.Vector.Fusion.Stream as Stream+import           Data.Vector.Fusion.Stream (MStream, Stream)+import qualified Data.Vector.Fusion.Stream.Monadic as MStream++-- import Control.DeepSeq ( NFData, rnf )+import Control.Monad ( liftM )+import Control.Monad.ST ( ST )+import Control.Monad.Primitive++import Prelude hiding ( length, null,+                        replicate, (++), concat,+                        head, last,+                        init, tail, take, drop, splitAt, reverse,+                        map, concatMap,+                        zipWith, zipWith3, zip, zip3, unzip, unzip3,+                        filter, takeWhile, dropWhile, span, break,+                        elem, notElem,+                        foldl, foldl1, foldr, foldr1,+                        all, any, and, or, sum, product, minimum, maximum,+                        scanl, scanl1, scanr, scanr1,+                        enumFromTo, enumFromThenTo,+                        mapM, mapM_, sequence, sequence_ )++import qualified Prelude++#define BOUNDS_CHECK(f) (Ck.f __FILE__ __LINE__ Ck.Bounds)+#define UNSAFE_CHECK(f) (Ck.f __FILE__ __LINE__ Ck.Unsafe)++-- import Data.Typeable ( Typeable )+-- import Data.Data     ( Data(..) )+-- import Text.Read     ( Read(..), readListPrecDefault )++-- import Data.Monoid   ( Monoid(..) )+-- import qualified Control.Applicative as Applicative+-- import qualified Data.Foldable as Foldable+-- import qualified Data.Traversable as Traversable++-- Length information+-- ------------------++-- | /O(1)/ Yield the length of the vector.+length :: G.Vector v a => v a -> Int+length = G.length+{-# INLINE length #-}++-- | /O(1)/ Test whether a vector if empty+null :: G.Vector v a => v a -> Bool+null = G.null+{-# INLINE null #-}++-- Indexing+-- --------++-- | O(1) Indexing+(!) :: G.Vector v a => v a -> Int -> a+(!) = (G.!)+{-# INLINE (!) #-}++-- | O(1) Safe indexing+(!?) :: G.Vector v a => v a -> Int -> Maybe a+(!?) = (G.!?)+{-# INLINE (!?) #-}++-- | /O(1)/ First element+head :: G.Vector v a => v a -> a+head = G.head+{-# INLINE head #-}++-- | /O(1)/ Last element+last :: G.Vector v a => v a -> a+last = G.last+{-# INLINE last #-}++-- | /O(1)/ Unsafe indexing without bounds checking+unsafeIndex :: G.Vector v a => v a -> Int -> a+unsafeIndex = G.unsafeIndex+{-# INLINE unsafeIndex #-}++-- | /O(1)/ First element without checking if the vector is empty+unsafeHead :: G.Vector v a => v a -> a+unsafeHead = G.unsafeHead+{-# INLINE unsafeHead #-}++-- | /O(1)/ Last element without checking if the vector is empty+unsafeLast :: G.Vector v a => v a -> a+unsafeLast = G.unsafeLast+{-# INLINE unsafeLast #-}++-- Monadic indexing+-- ----------------++-- | /O(1)/ Indexing in a monad.+--+-- The monad allows operations to be strict in the vector when necessary.+-- Suppose vector copying is implemented like this:+--+-- > copy mv v = ... write mv i (v ! i) ...+--+-- For lazy vectors, @v ! i@ would not be evaluated which means that @mv@+-- would unnecessarily retain a reference to @v@ in each element written.+--+-- With 'indexM', copying can be implemented like this instead:+--+-- > copy mv v = ... do+-- >                   x <- indexM v i+-- >                   write mv i x+--+-- Here, no references to @v@ are retained because indexing (but /not/ the+-- elements) is evaluated eagerly.+--+indexM :: (Monad m, G.Vector v a) => v a -> Int -> m a+indexM = G.indexM+{-# INLINE indexM #-}++-- | /O(1)/ First element of a vector in a monad. See 'indexM' for an+-- explanation of why this is useful.+headM :: (Monad m, G.Vector v a) => v a -> m a+headM = G.headM+{-# INLINE headM #-}++-- | /O(1)/ Last element of a vector in a monad. See 'indexM' for an+-- explanation of why this is useful.+lastM :: (Monad m, G.Vector v a) => v a -> m a+lastM = G.lastM+{-# INLINE lastM #-}++-- | /O(1)/ Indexing in a monad without bounds checks. See 'indexM' for an+-- explanation of why this is useful.+unsafeIndexM :: (Monad m, G.Vector v a) => v a -> Int -> m a+unsafeIndexM = G.unsafeIndexM+{-# INLINE unsafeIndexM #-}++-- | /O(1)/ First element in a monad without checking for empty vectors.+-- See 'indexM' for an explanation of why this is useful.+unsafeHeadM :: (Monad m, G.Vector v a) => v a -> m a+unsafeHeadM = G.unsafeHeadM+{-# INLINE unsafeHeadM #-}++-- | /O(1)/ Last element in a monad without checking for empty vectors.+-- See 'indexM' for an explanation of why this is useful.+unsafeLastM :: (Monad m, G.Vector v a) => v a -> m a+unsafeLastM = G.unsafeLastM+{-# INLINE unsafeLastM #-}++-- Extracting subvectors (slicing)+-- -------------------------------++-- | /O(1)/ Yield a slice of the vector without copying it. The vector must+-- contain at least @i+n@ elements.+slice :: Mixed u v a => Int   -- ^ @i@ starting index+                 -> Int   -- ^ @n@ length+                 -> v a+                 -> Vector a+slice i j m = mix (G.slice i j m)+{-# INLINE slice #-}++-- | /O(1)/ Yield all but the last element without copying. The vector may not+-- be empty.+init :: Mixed u v a => v a -> Vector a+init m = mix (G.init m)+{-# INLINE init #-}++-- | /O(1)/ Yield all but the first element without copying. The vector may not+-- be empty.+tail :: Mixed u v a => v a -> Vector a+tail m = mix (G.tail m)+{-# INLINE tail #-}++-- | /O(1)/ Yield at the first @n@ elements without copying. The vector may+-- contain less than @n@ elements in which case it is returned unchanged.+take :: Mixed u v a => Int -> v a -> Vector a+take i m = mix (G.take i m)+{-# INLINE take #-}++-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector may+-- contain less than @n@ elements in which case an empty vector is returned.+drop :: Mixed u v a => Int -> v a -> Vector a+drop i m = mix (G.drop i m)+{-# INLINE drop #-}++-- | /O(1)/ Yield the first @n@ elements paired with the remainder without copying.+--+-- Note that @'splitAt' n v@ is equivalent to @('take' n v, 'drop' n v)@+-- but slightly more efficient.+splitAt :: Mixed u v a => Int -> v a -> (Vector a, Vector a)+splitAt i m = case G.splitAt i m of+  (xs, ys) -> (mix xs, mix ys)+{-# INLINE splitAt #-}++-- | /O(1)/ Yield a slice of the vector without copying. The vector must+-- contain at least @i+n@ elements but this is not checked.+unsafeSlice :: Mixed u v a => Int   -- ^ @i@ starting index+                       -> Int   -- ^ @n@ length+                       -> v a+                       -> Vector a+unsafeSlice i j m = mix (G.unsafeSlice i j m)+{-# INLINE unsafeSlice #-}++-- | /O(1)/ Yield all but the last element without copying. The vector may not+-- be empty but this is not checked.+unsafeInit :: Mixed u v a => v a -> Vector a+unsafeInit m = mix (G.unsafeInit m)+{-# INLINE unsafeInit #-}++-- | /O(1)/ Yield all but the first element without copying. The vector may not+-- be empty but this is not checked.+unsafeTail :: Mixed u v a => v a -> Vector a+unsafeTail m = mix (G.unsafeTail m)+{-# INLINE unsafeTail #-}++-- | /O(1)/ Yield the first @n@ elements without copying. The vector must+-- contain at least @n@ elements but this is not checked.+unsafeTake :: Mixed u v a => Int -> v a -> Vector a+unsafeTake i m = mix (G.unsafeTake i m)+{-# INLINE unsafeTake #-}++-- | /O(1)/ Yield all but the first @n@ elements without copying. The vector+-- must contain at least @n@ elements but this is not checked.+unsafeDrop :: Mixed u v a => Int -> v a -> Vector a+unsafeDrop i m = mix (G.unsafeDrop i m)+{-# INLINE unsafeDrop #-}++-- Initialisation+-- --------------++-- | /O(1)/ Empty vector+empty :: Vector a+empty = G.empty+{-# INLINE empty #-}++-- | /O(1)/ Vector with exactly one element+singleton :: a -> Vector a+singleton = G.singleton+{-# INLINE singleton #-}++-- | /O(n)/ Vector of the given length with the same value in each position+replicate :: Int -> a -> Vector a+replicate = G.replicate+{-# INLINE replicate #-}++-- | /O(n)/ Construct a vector of the given length by applying the function to+-- each index+generate :: Int -> (Int -> a) -> Vector a+generate = G.generate+{-# INLINE generate #-}++-- | /O(n)/ Apply function n times to value. Zeroth element is original value.+iterateN :: Int -> (a -> a) -> a -> Vector a+iterateN = G.iterateN+{-# INLINE iterateN #-}++-- Unfolding+-- ---------++-- | /O(n)/ Construct a vector by repeatedly applying the generator function+-- to a seed. The generator function yields 'Just' the next element and the+-- new seed or 'Nothing' if there are no more elements.+--+-- > unfoldr (\n -> if n == 0 then Nothing else Just (n,n-1)) 10+-- >  = <10,9,8,7,6,5,4,3,2,1>+unfoldr :: (b -> Maybe (a, b)) -> b -> Vector a+unfoldr = G.unfoldr+{-# INLINE unfoldr #-}++-- | /O(n)/ Construct a vector with at most @n@ by repeatedly applying the+-- generator function to the a seed. The generator function yields 'Just' the+-- next element and the new seed or 'Nothing' if there are no more elements.+--+-- > unfoldrN 3 (\n -> Just (n,n-1)) 10 = <10,9,8>+unfoldrN :: Int -> (b -> Maybe (a, b)) -> b -> Vector a+unfoldrN = G.unfoldrN+{-# INLINE unfoldrN #-}++-- | /O(n)/ Construct a vector with @n@ elements by repeatedly applying the+-- generator function to the already constructed part of the vector.+--+-- > constructN 3 f = let a = f <> ; b = f <a> ; c = f <a,b> in f <a,b,c>+--+constructN :: Int -> (Vector a -> a) -> Vector a+constructN = G.constructN+{-# INLINE constructN #-}++-- | /O(n)/ Construct a vector with @n@ elements from right to left by+-- repeatedly applying the generator function to the already constructed part+-- of the vector.+--+-- > constructrN 3 f = let a = f <> ; b = f<a> ; c = f <b,a> in f <c,b,a>+--+constructrN :: Int -> (Vector a -> a) -> Vector a+constructrN = G.constructrN+{-# INLINE constructrN #-}++-- Enumeration+-- -----------++-- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+1@+-- etc. This operation is usually more efficient than 'enumFromTo'.+--+-- > enumFromN 5 3 = <5,6,7>+enumFromN :: Num a => a -> Int -> Vector a+enumFromN = G.enumFromN+{-# INLINE enumFromN #-}++-- | /O(n)/ Yield a vector of the given length containing the values @x@, @x+y@,+-- @x+y+y@ etc. This operations is usually more efficient than 'enumFromThenTo'.+--+-- > enumFromStepN 1 0.1 5 = <1,1.1,1.2,1.3,1.4>+enumFromStepN :: Num a => a -> a -> Int -> Vector a+enumFromStepN = G.enumFromStepN+{-# INLINE enumFromStepN #-}++-- | /O(n)/ Enumerate values from @x@ to @y@.+--+-- /WARNING:/ This operation can be very inefficient. If at all possible, use+-- 'enumFromN' instead.+enumFromTo :: Enum a => a -> a -> Vector a+enumFromTo = G.enumFromTo+{-# INLINE enumFromTo #-}++-- | /O(n)/ Enumerate values from @x@ to @y@ with a specific step @z@.+--+-- /WARNING:/ This operation can be very inefficient. If at all possible, use+-- 'enumFromStepN' instead.+enumFromThenTo :: Enum a => a -> a -> a -> Vector a+enumFromThenTo = G.enumFromThenTo+{-# INLINE enumFromThenTo #-}++-- Concatenation+-- -------------++-- | /O(n)/ Prepend an element+cons :: Mixed u v a => a -> v a -> Vector a+cons a as = mix (G.cons a as)+{-# INLINE cons #-}++-- | /O(n)/ Append an element+snoc :: Mixed u v a => v a -> a -> Vector a+snoc as a = mix (G.snoc as a)+{-# INLINE snoc #-}++infixr 5 +++-- | /O(m+n)/ Concatenate two vectors+(++) :: (Mixed u v a, Mixed u' v' a) => v a -> v' a -> Vector a+m ++ n = mix m G.++ mix n+{-# INLINE (++) #-}++-- | /O(n)/ Concatenate all vectors in the list+concat :: Mixed u v a => [v a] -> Vector a+concat xs = mix (G.concat xs)+{-# INLINE concat #-}++-- Monadic initialisation+-- ----------------------++-- | /O(n)/ Execute the monadic action the given number of times and store the+-- results in a vector.+replicateM :: Monad m => Int -> m a -> m (Vector a)+replicateM = G.replicateM+{-# INLINE replicateM #-}++-- | /O(n)/ Construct a vector of the given length by applying the monadic+-- action to each index+generateM :: Monad m => Int -> (Int -> m a) -> m (Vector a)+generateM = G.generateM+{-# INLINE generateM #-}++-- | Execute the monadic action and freeze the resulting vector.+--+-- @+-- create (do { v \<- new 2; write v 0 \'a\'; write v 1 \'b\'; return v }) = \<'a','b'\>+-- @+create :: Mixed u v a => (forall s. ST s (u s a)) -> Vector a+-- NOTE: eta-expanded due to http://hackage.haskell.org/trac/ghc/ticket/4120+create p = mix (G.create p)+{-# INLINE create #-}++-- Restricting memory usage+-- ------------------------++-- | /O(n)/ Yield the argument but force it not to retain any extra memory,+-- possibly by copying it.+--+-- This is especially useful when dealing with slices. For example:+--+-- > force (slice 0 2 <huge vector>)+--+-- Here, the slice retains a reference to the huge vector. Forcing it creates+-- a copy of just the elements that belong to the slice and allows the huge+-- vector to be garbage collected.+force :: Mixed u v a => v a -> Vector a+force m = mix (G.force m)+{-# INLINE force #-}++-- Bulk updates+-- ------------++-- | /O(m+n)/ For each pair @(i,a)@ from the list, replace the vector+-- element at position @i@ by @a@.+--+-- > <5,9,2,7> // [(2,1),(0,3),(2,8)] = <3,9,8,7>+--+(//) :: Mixed u v a => v a   -- ^ initial vector (of length @m@)+                -> [(Int, a)] -- ^ list of index/value pairs (of length @n@)+                -> Vector a+m // xs = mix (m G.// xs)+{-# INLINE (//) #-}++update_stream :: G.Vector v a => v a -> Stream (Int,a) -> v a+update_stream = modifyWithStream GM.update+{-# INLINE update_stream #-}++-- | /O(m+n)/ For each pair @(i,a)@ from the vector of index/value pairs,+-- replace the vector element at position @i@ by @a@.+--+-- > update <5,9,2,7> <(2,1),(0,3),(2,8)> = <3,9,8,7>+--+update :: (Mixed u v a, G.Vector v' (Int, a)) => v a -- ^ initial vector (of length @m@)+       -> v' (Int, a) -- ^ vector of index/value pairs (of length @n@)+       -> Vector a+update v w = mix (update_stream v (G.stream w))+{-# INLINE update #-}++-- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the+-- corresponding value @a@ from the value vector, replace the element of the+-- initial vector at position @i@ by @a@.+--+-- > update_ <5,9,2,7>  <2,0,2> <1,3,8> = <3,9,8,7>+--+-- The function 'update' provides the same functionality and is usually more+-- convenient.+--+-- @+-- update_ xs is ys = 'update' xs ('zip' is ys)+-- @+update_ ::+  ( Mixed u v a, G.Vector v' Int, G.Vector v'' a+  ) => v a   -- ^ initial vector (of length @m@)+    -> v' Int -- ^ index vector (of length @n1@)+    -> v'' a   -- ^ value vector (of length @n2@)+    -> Vector a+update_ v is w = mix (update_stream v (Stream.zipWith (,) (G.stream is) (G.stream w)))+{-# INLINE update_ #-}++-- | Same as ('//') but without bounds checking.+unsafeUpd :: Mixed u v a => v a -> [(Int, a)] -> Vector a+unsafeUpd v us = mix (unsafeUpdate_stream v (Stream.fromList us))+{-# INLINE unsafeUpd #-}++unsafeUpdate_stream :: G.Vector v a => v a -> Stream (Int,a) -> v a+unsafeUpdate_stream = modifyWithStream GM.unsafeUpdate+{-# INLINE unsafeUpdate_stream #-}++-- | Same as 'update' but without bounds checking.+unsafeUpdate :: (Mixed u v a, G.Vector v' (Int, a)) => v a -> v' (Int, a) -> Vector a+unsafeUpdate v w = mix (unsafeUpdate_stream v (G.stream w))+{-# INLINE unsafeUpdate #-}++-- | Same as 'update_' but without bounds checking.+unsafeUpdate_ :: ( Mixed u v a, G.Vector v' Int, G.Vector v'' a+  ) => v a -> v' Int -> v'' a -> Vector a+unsafeUpdate_ v is w = mix (unsafeUpdate_stream v (Stream.zipWith (,) (G.stream is) (G.stream w)))+{-# INLINE unsafeUpdate_ #-}++-- Accumulations+-- -------------++-- | /O(m+n)/ For each pair @(i,b)@ from the list, replace the vector element+-- @a@ at position @i@ by @f a b@.+--+-- > accum (+) <5,9,2> [(2,4),(1,6),(0,3),(1,7)] = <5+3, 9+6+7, 2+4>+accum :: Mixed u v a => (a -> b -> a) -- ^ accumulating function @f@+      -> v a      -- ^ initial vector (of length @m@)+      -> [(Int,b)]     -- ^ list of index/value pairs (of length @n@)+      -> Vector a+accum f v us = mix (accum_stream f v (Stream.fromList us))+{-# INLINE accum #-}++-- | /O(m+n)/ For each pair @(i,b)@ from the vector of pairs, replace the vector+-- element @a@ at position @i@ by @f a b@.+--+-- > accumulate (+) <5,9,2> <(2,4),(1,6),(0,3),(1,7)> = <5+3, 9+6+7, 2+4>+accumulate :: (Mixed u v a, G.Vector v' (Int, b))+           => (a -> b -> a)  -- ^ accumulating function @f@+           -> v a       -- ^ initial vector (of length @m@)+           -> v' (Int,b) -- ^ vector of index/value pairs (of length @n@)+           -> Vector a+accumulate f v us = mix (accum_stream f v (G.stream us))+{-# INLINE accumulate #-}++-- | /O(m+min(n1,n2))/ For each index @i@ from the index vector and the+-- corresponding value @b@ from the the value vector,+-- replace the element of the initial vector at+-- position @i@ by @f a b@.+--+-- > accumulate_ (+) <5,9,2> <2,1,0,1> <4,6,3,7> = <5+3, 9+6+7, 2+4>+--+-- The function 'accumulate' provides the same functionality and is usually more+-- convenient.+--+-- @+-- accumulate_ f as is bs = 'accumulate' f as ('zip' is bs)+-- @+accumulate_+  :: (Mixed u v a, G.Vector v' Int, G.Vector v'' b)+  => (a -> b -> a) -- ^ accumulating function @f@+  -> v a      -- ^ initial vector (of length @m@)+  -> v' Int    -- ^ index vector (of length @n1@)+  -> v'' b      -- ^ value vector (of length @n2@)+  -> Vector a+accumulate_ f v is xs = mix (accum_stream f v (Stream.zipWith (,) (G.stream is) (G.stream xs)))+{-# INLINE accumulate_ #-}++accum_stream :: G.Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a+accum_stream f = modifyWithStream (GM.accum f)+{-# INLINE accum_stream #-}++-- | Same as 'accum' but without bounds checking.+unsafeAccum :: Mixed u v a => (a -> b -> a) -> v a -> [(Int,b)] -> Vector a+unsafeAccum f v us = mix (unsafeAccum_stream f v (Stream.fromList us))++{-# INLINE unsafeAccum #-}++-- | Same as 'accumulate' but without bounds checking.+unsafeAccumulate :: (Mixed u v a, G.Vector v' (Int, b)) => (a -> b -> a) -> v a -> v' (Int,b) -> Vector a+unsafeAccumulate f v us = mix (unsafeAccum_stream f v (G.stream us))+{-# INLINE unsafeAccumulate #-}++-- | Same as 'accumulate_' but without bounds checking.+unsafeAccumulate_+  :: (Mixed u v a, G.Vector v' Int, G.Vector v'' b)+  => (a -> b -> a) -> v a -> v' Int -> v'' b -> Vector a+unsafeAccumulate_ f v is xs = mix (unsafeAccum_stream f v (Stream.zipWith (,) (G.stream is) (G.stream xs)))+{-# INLINE unsafeAccumulate_ #-}++unsafeAccum_stream :: G.Vector v a => (a -> b -> a) -> v a -> Stream (Int,b) -> v a+unsafeAccum_stream f = modifyWithStream (GM.unsafeAccum f)+{-# INLINE unsafeAccum_stream #-}++-- Permutations+-- ------------++-- | /O(n)/ Reverse a vector+reverse :: Mixed u v a => v a -> Vector a+reverse m = mix (G.reverse m)+{-# INLINE reverse #-}++-- | /O(n)/ Yield the vector obtained by replacing each element @i@ of the+-- index vector by @xs'!'i@. This is equivalent to @'map' (xs'!') is@ but is+-- often much more efficient.+--+-- > backpermute <a,b,c,d> <0,3,2,3,1,0> = <a,d,c,d,b,a>+backpermute :: (Mixed u v a, G.Vector v' Int) => v a -> v' Int -> Vector a+-- backpermute m n = G.backpermute (mix m) (mix n)+-- {-# INLINE backpermute #-}++-- This somewhat non-intuitive definition ensures that the resulting vector+-- does not retain references to the original one even if it is lazy in its+-- elements. This would not be the case if we simply used map (v!)+backpermute v is = mix+                 $ (`asTypeOf` v)+                 $ seq v+                 $ seq n+                 $ G.unstream+                 $ Stream.unbox+                 $ Stream.map index+                 $ G.stream is+  where+    n = length v++    {-# INLINE index #-}+    -- NOTE: we do it this way to avoid triggering LiberateCase on n in+    -- polymorphic code+    index i = BOUNDS_CHECK(checkIndex) "backpermute" i n+            $ G.basicUnsafeIndexM v i++-- | Same as 'backpermute' but without bounds checking.+unsafeBackpermute :: (Mixed u v a, G.Vector v' Int) => v a -> v' Int -> Vector a+unsafeBackpermute v is = mix+                       $ (`asTypeOf` v)+                       $ seq v+                       $ seq n+                       $ G.unstream+                       $ Stream.unbox+                       $ Stream.map index+                       $ G.stream is+  where+    n = length v++    {-# INLINE index #-}+    -- NOTE: we do it this way to avoid triggering LiberateCase on n in+    -- polymorphic code+    index i = UNSAFE_CHECK(checkIndex) "unsafeBackpermute" i n+            $ G.basicUnsafeIndexM v i++{-# INLINE unsafeBackpermute #-}++-- Safe destructive updates+-- ------------------------++-- | Apply a destructive operation to a vector. The operation will be+-- performed in place if it is safe to do so and will modify a copy of the+-- vector otherwise.+--+-- @+-- modify (\\v -> write v 0 \'x\') ('replicate' 3 \'a\') = \<\'x\',\'a\',\'a\'\>+-- @+modify :: Mixed u v a => (forall s. u s a -> ST s ()) -> v a -> Vector a+modify p v = mix (G.modify p v)+{-# INLINE modify #-}++-- Indexing+-- --------++-- | /O(n)/ Pair each element in a vector with its index+indexed :: (G.Vector v a, Mixed u v (Int, a)) => v a -> Vector (Int,a)+indexed m = mix (G.indexed m)+{-# INLINE indexed #-}++-- Mapping+-- -------++-- | /O(n)/ Map a function over a vector+map :: G.Vector v a => (a -> b) -> v a -> Vector b+map f = boxed . G.unstream . Stream.inplace (MStream.map f) . G.stream+++{-# INLINE map #-}++-- | /O(n)/ Apply a function to every element of a vector and its index+imap :: G.Vector v a => (Int -> a -> b) -> v a -> Vector b+-- imap f m = mix (G.imap f m)+imap f = boxed . G.unstream . Stream.inplace (MStream.map (uncurry f) . MStream.indexed) . G.stream+{-# INLINE imap #-}++-- | Map a function over a vector and concatenate the results.+concatMap :: (Mixed u v b, G.Vector v' a) => (a -> v b) -> v' a -> Vector b+concatMap f = mix . G.concat . Stream.toList . Stream.map f . G.stream+{-# INLINE concatMap #-}++-- Monadic mapping+-- ---------------++-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a+-- vector of results+mapM :: (Monad m, G.Vector v a) => (a -> m b) -> v a -> m (Vector b)+mapM f = unstreamM . Stream.mapM f . G.stream+{-# INLINE mapM #-}++-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the+-- results+mapM_ :: (Monad m, G.Vector v a) => (a -> m b) -> v a -> m ()+mapM_ f = Stream.mapM_ f . G.stream+{-# INLINE mapM_ #-}++-- | /O(n)/ Apply the monadic action to all elements of the vector, yielding a+-- vector of results. Equvalent to @flip 'mapM'@.+forM :: (Monad m, G.Vector v a) => v a -> (a -> m b) -> m (Vector b)+forM as f = mapM f as+{-# INLINE forM #-}++-- | /O(n)/ Apply the monadic action to all elements of a vector and ignore the+-- results. Equivalent to @flip 'mapM_'@.+forM_ :: (Monad m, G.Vector v a) => v a -> (a -> m b) -> m ()+forM_ as f = mapM_ f as+{-# INLINE forM_ #-}++-- Zipping+-- -------++-- | /O(min(m,n))/ Zip two vectors with the given function.+zipWith :: (G.Vector va a, G.Vector vb b)+        => (a -> b -> c) -> va a -> vb b -> Vector c+zipWith k a b = boxed (G.unstream (Stream.zipWith k (G.stream a) (G.stream b)))+{-# INLINE zipWith #-}++-- | Zip three vectors with the given function.+zipWith3 :: (G.Vector va a, G.Vector vb b, G.Vector vc c)+         => (a -> b -> c -> d) -> va a -> vb b -> vc c -> Vector d+zipWith3 k a b c = boxed (G.unstream (Stream.zipWith3 k (G.stream a) (G.stream b) (G.stream c)))+{-# INLINE zipWith3 #-}++zipWith4 :: (G.Vector va a, G.Vector vb b, G.Vector vc c, G.Vector vd d)+         => (a -> b -> c -> d -> e) -> va a -> vb b -> vc c -> vd d -> Vector e+zipWith4 k a b c d = boxed (G.unstream (Stream.zipWith4 k (G.stream a) (G.stream b) (G.stream c) (G.stream d)))+{-# INLINE zipWith4 #-}++zipWith5 :: (G.Vector va a, G.Vector vb b, G.Vector vc c, G.Vector vd d, G.Vector ve e)+         => (a -> b -> c -> d -> e -> f) -> va a -> vb b -> vc c -> vd d -> ve e -> Vector f+zipWith5 k a b c d e = boxed (G.unstream (Stream.zipWith5 k (G.stream a) (G.stream b) (G.stream c) (G.stream d) (G.stream e)))+{-# INLINE zipWith5 #-}++zipWith6 :: (G.Vector va a, G.Vector vb b, G.Vector vc c, G.Vector vd d, G.Vector ve e, G.Vector vf f)+         => (a -> b -> c -> d -> e -> f -> g) -> va a -> vb b -> vc c -> vd d -> ve e -> vf f -> Vector g+zipWith6 k a b c d e f = boxed (G.unstream (Stream.zipWith6 k (G.stream a) (G.stream b) (G.stream c) (G.stream d) (G.stream e) (G.stream f)))+{-# INLINE zipWith6 #-}+++-- | /O(min(m,n))/ Zip two vectors with a function that also takes the+-- elements' indices.++izipWith :: (G.Vector va a, G.Vector vb b)+        => (Int -> a -> b -> c) -> va a -> vb b -> Vector c+izipWith f xs ys = boxed $ G.unstream $+   Stream.zipWith (uncurry f) (Stream.indexed (G.stream xs)) (G.stream ys)++{-# INLINE izipWith #-}++-- | Zip three vectors and their indices with the given function.+izipWith3 :: (G.Vector va a, G.Vector vb b, G.Vector vc c)+         => (Int -> a -> b -> c -> d) -> va a -> vb b -> vc c -> Vector d+izipWith3 f xs ys zs = boxed $ G.unstream $+   Stream.zipWith3 (uncurry f) (Stream.indexed (G.stream xs)) (G.stream ys) (G.stream zs)+{-# INLINE izipWith3 #-}++izipWith4 :: (G.Vector va a, G.Vector vb b, G.Vector vc c, G.Vector vd d)+         => (Int -> a -> b -> c -> d -> e) -> va a -> vb b -> vc c -> vd d -> Vector e+izipWith4 f xs ys zs ws = boxed $ G.unstream $+   Stream.zipWith4 (uncurry f) (Stream.indexed (G.stream xs)) (G.stream ys) (G.stream zs) (G.stream ws)+{-# INLINE izipWith4 #-}++izipWith5 :: (G.Vector va a, G.Vector vb b, G.Vector vc c, G.Vector vd d, G.Vector ve e)+         => (Int -> a -> b -> c -> d -> e -> f) -> va a -> vb b -> vc c -> vd d -> ve e -> Vector f+izipWith5 k a b c d e = boxed (G.unstream (Stream.zipWith5 (uncurry k) (Stream.indexed (G.stream a)) (G.stream b) (G.stream c) (G.stream d) (G.stream e)))+{-# INLINE izipWith5 #-}++izipWith6 :: (G.Vector va a, G.Vector vb b, G.Vector vc c, G.Vector vd d, G.Vector ve e, G.Vector vf f)+         => (Int -> a -> b -> c -> d -> e -> f -> g) -> va a -> vb b -> vc c -> vd d -> ve e -> vf f -> Vector g+izipWith6 k a b c d e f = boxed (G.unstream (Stream.zipWith6 (uncurry k) (Stream.indexed (G.stream a)) (G.stream b) (G.stream c) (G.stream d) (G.stream e) (G.stream f)))+{-# INLINE izipWith6 #-}++-- | Elementwise pairing of array elements.+zip :: (G.Vector va a, G.Vector vb b)+    => va a -> vb b -> Vector (a, b)+-- zip a b = mix (H.V a b) -- we would need to trim appropriately, and this would likely interfere with streaming. TODO: fix up and benchmark?+zip = zipWith (,)+{-# INLINE zip #-}++-- | zip together three vectors into a vector of triples+zip3 :: (G.Vector va a, G.Vector vb b, G.Vector vc c)+     => va  a -> vb b -> vc c -> Vector (a, b, c)+zip3 = zipWith3 (,,)+{-# INLINE zip3 #-}++zip4 :: (G.Vector va a, G.Vector vb b, G.Vector vc c, G.Vector vd d)+     => va a -> vb b -> vc c -> vd d -> Vector (a, b, c, d)+zip4 = zipWith4 (,,,)+{-# INLINE zip4 #-}++zip5 :: (G.Vector va a, G.Vector vb b, G.Vector vc c, G.Vector vd d, G.Vector ve e)+     => va a -> vb b -> vc c -> vd d -> ve e -> Vector (a, b, c, d, e)+zip5 = zipWith5 (,,,,)+{-# INLINE zip5 #-}++zip6 :: (G.Vector va a, G.Vector vb b, G.Vector vc c, G.Vector vd d, G.Vector ve e, G.Vector vf f)+     => va a -> vb b -> vc c -> vd d -> ve e -> vf f -> Vector (a, b, c, d, e, f)+zip6 = zipWith6 (,,,,,)+{-# INLINE zip6 #-}++-- Unzipping+-- ---------++-- | /O(min(m,n))/ Unzip a vector of pairs.+unzip :: G.Vector v (a, b) => v (a, b) -> (Vector a, Vector b)+unzip v = (map fst v, map snd v)+{-# INLINE unzip #-}++unzip3 :: G.Vector v (a, b, c) => v (a, b, c) -> (Vector a, Vector b, Vector c)+unzip3 xs = (map (\(a, _, _) -> a) xs,+             map (\(_, b, _) -> b) xs,+             map (\(_, _, c) -> c) xs)+{-# INLINE unzip3 #-}++unzip4 :: G.Vector v (a, b, c, d) => v (a, b, c, d) -> (Vector a, Vector b, Vector c, Vector d)+unzip4 xs = (map (\(a, _, _, _) -> a) xs,+             map (\(_, b, _, _) -> b) xs,+             map (\(_, _, c, _) -> c) xs,+             map (\(_, _, _, d) -> d) xs)+{-# INLINE unzip4 #-}++unzip5 :: G.Vector v (a, b, c, d, e) => v (a, b, c, d, e) -> (Vector a, Vector b, Vector c, Vector d, Vector e)+unzip5 xs = (map (\(a, _, _, _, _) -> a) xs,+             map (\(_, b, _, _, _) -> b) xs,+             map (\(_, _, c, _, _) -> c) xs,+             map (\(_, _, _, d, _) -> d) xs,+             map (\(_, _, _, _, e) -> e) xs)+{-# INLINE unzip5 #-}++unzip6 :: G.Vector v (a, b, c, d, e, f) => v (a, b, c, d, e, f) -> (Vector a, Vector b, Vector c, Vector d, Vector e, Vector f)+unzip6 xs = (map (\(a, _, _, _, _, _) -> a) xs,+             map (\(_, b, _, _, _, _) -> b) xs,+             map (\(_, _, c, _, _, _) -> c) xs,+             map (\(_, _, _, d, _, _) -> d) xs,+             map (\(_, _, _, _, e, _) -> e) xs,+             map (\(_, _, _, _, _, f) -> f) xs)+{-# INLINE unzip6 #-}++-- Monadic zipping+-- ---------------++-- | /O(min(m,n))/ Zip the two vectors with the monadic action and yield a+-- vector of results+zipWithM :: (Monad m, G.Vector va a, G.Vector vb b) => (a -> b -> m c) -> va a -> vb b -> m (Vector c)+zipWithM f as bs = unstreamM $ Stream.zipWithM f (G.stream as) (G.stream bs)+{-# INLINE zipWithM #-}+++-- | /O(min(m,n))/ Zip the two vectors with the monadic action and ignore the+-- results+zipWithM_ :: (Monad m, G.Vector va a, G.Vector vb b) => (a -> b -> m c) -> va a -> vb b -> m ()+zipWithM_ f as bs = Stream.zipWithM_ f (G.stream as) (G.stream bs)+{-# INLINE zipWithM_ #-}++-- Filtering+-- ---------++-- | /O(n)/ Drop elements that do not satisfy the predicate+filter :: Mixed u v a => (a -> Bool) -> v a -> Vector a+{-# INLINE filter #-}+filter f = mix . G.filter f++-- | /O(n)/ Drop elements that do not satisfy the predicate which is applied to+-- values and their indices+ifilter :: Mixed u v a => (Int -> a -> Bool) -> v a -> Vector a+ifilter f = mix . G.ifilter f+{-# INLINE ifilter #-}++-- | /O(n)/ Drop elements that do not satisfy the monadic predicate+filterM :: (Monad m, Mixed u v a) => (a -> m Bool) -> v a -> m (Vector a)+filterM f = liftM mix . G.filterM f+{-# INLINE filterM #-}++-- | /O(n)/ Yield the longest prefix of elements satisfying the predicate+-- without copying.+takeWhile :: Mixed u v a => (a -> Bool) -> v a -> Vector a+takeWhile f = mix . G.takeWhile f+{-# INLINE takeWhile #-}++-- | /O(n)/ Drop the longest prefix of elements that satisfy the predicate+-- without copying.+dropWhile :: Mixed u v a => (a -> Bool) -> v a -> Vector a+dropWhile f = mix . G.dropWhile f+{-# INLINE dropWhile #-}++-- Parititioning+-- -------------++-- | /O(n)/ Split the vector in two parts, the first one containing those+-- elements that satisfy the predicate and the second one those that don't. The+-- relative order of the elements is preserved at the cost of a sometimes+-- reduced performance compared to 'unstablePartition'.+partition :: Mixed u v a => (a -> Bool) -> v a -> (Vector a, Vector a)+partition f as = case G.partition f as of+  (l,r) -> (mix l, mix r)+{-# INLINE partition #-}++-- | /O(n)/ Split the vector in two parts, the first one containing those+-- elements that satisfy the predicate and the second one those that don't.+-- The order of the elements is not preserved but the operation is often+-- faster than 'partition'.+unstablePartition :: Mixed u v a => (a -> Bool) -> v a -> (Vector a, Vector a)+unstablePartition f as = case G.unstablePartition f as of+  (l,r) -> (mix l, mix r)+{-# INLINE unstablePartition #-}++-- | /O(n)/ Split the vector into the longest prefix of elements that satisfy+-- the predicate and the rest without copying.+span :: Mixed u v a => (a -> Bool) -> v a -> (Vector a, Vector a)+span f as = case G.span f as of+  (l,r) -> (mix l, mix r)+{-# INLINE span #-}++-- | /O(n)/ Split the vector into the longest prefix of elements that do not+-- satisfy the predicate and the rest without copying.+break :: (a -> Bool) -> Vector a -> (Vector a, Vector a)+break f as = case G.break f as of+  (l,r) -> (mix l, mix r)+{-# INLINE break #-}++-- Searching+-- ---------++infix 4 `elem`+-- | /O(n)/ Check if the vector contains an element+elem :: (G.Vector v a, Eq a) => a -> v a -> Bool+elem = G.elem+{-# INLINE elem #-}++infix 4 `notElem`+-- | /O(n)/ Check if the vector does not contain an element (inverse of 'elem')+notElem :: (G.Vector v a, Eq a) => a -> Vector a -> Bool+notElem = G.notElem+{-# INLINE notElem #-}++-- | /O(n)/ Yield 'Just' the first element matching the predicate or 'Nothing'+-- if no such element exists.+find :: (G.Vector v a) => (a -> Bool) -> v a -> Maybe a+find = G.find+{-# INLINE find #-}++-- | /O(n)/ Yield 'Just' the index of the first element matching the predicate+-- or 'Nothing' if no such element exists.+findIndex :: G.Vector v a => (a -> Bool) -> v a -> Maybe Int+findIndex = G.findIndex+{-# INLINE findIndex #-}++-- | /O(n)/ Yield the indices of elements satisfying the predicate in ascending+-- order.+findIndices :: G.Vector v a => (a -> Bool) -> v a -> Vector Int+findIndices f = unboxed . G.unstream+              . Stream.inplace (MStream.map fst . MStream.filter (f . snd) . MStream.indexed)+              . G.stream+{-# INLINE findIndices #-}++-- | /O(n)/ Yield 'Just' the index of the first occurence of the given element or+-- 'Nothing' if the vector does not contain the element. This is a specialised+-- version of 'findIndex'.+elemIndex :: (G.Vector v a, Eq a) => a -> v a -> Maybe Int+elemIndex = G.elemIndex+{-# INLINE elemIndex #-}++-- | /O(n)/ Yield the indices of all occurences of the given element in+-- ascending order. This is a specialised version of 'findIndices'.+elemIndices :: (G.Vector v a, Eq a) => a -> v a -> Vector Int+elemIndices x = findIndices (x==)+{-# INLINE elemIndices #-}++-- Folding+-- -------++-- | /O(n)/ Left fold+foldl :: G.Vector v b => (a -> b -> a) -> a -> v b -> a+foldl = G.foldl+{-# INLINE foldl #-}++-- | /O(n)/ Left fold on non-empty vectors+foldl1 :: G.Vector v a => (a -> a -> a) -> v a -> a+foldl1 = G.foldl1+{-# INLINE foldl1 #-}++-- | /O(n)/ Left fold with strict accumulator+foldl' :: G.Vector v b => (a -> b -> a) -> a -> v b -> a+foldl' = G.foldl'+{-# INLINE foldl' #-}++-- | /O(n)/ Left fold on non-empty vectors with strict accumulator+foldl1' :: G.Vector v a => (a -> a -> a) -> v a -> a+foldl1' = G.foldl1'+{-# INLINE foldl1' #-}++-- | /O(n)/ Right fold+foldr :: G.Vector v a => (a -> b -> b) -> b -> v a -> b+foldr = G.foldr+{-# INLINE foldr #-}++-- | /O(n)/ Right fold on non-empty vectors+foldr1 :: G.Vector v a => (a -> a -> a) -> v a -> a+foldr1 = G.foldr1+{-# INLINE foldr1 #-}++-- | /O(n)/ Right fold with a strict accumulator+foldr' :: G.Vector v a => (a -> b -> b) -> b -> v a -> b+foldr' = G.foldr'+{-# INLINE foldr' #-}++-- | /O(n)/ Right fold on non-empty vectors with strict accumulator+foldr1' :: G.Vector v a => (a -> a -> a) -> v a -> a+foldr1' = G.foldr1'+{-# INLINE foldr1' #-}++-- | /O(n)/ Left fold (function applied to each element and its index)+ifoldl :: G.Vector v b => (a -> Int -> b -> a) -> a -> v b -> a+ifoldl = G.ifoldl+{-# INLINE ifoldl #-}++-- | /O(n)/ Left fold with strict accumulator (function applied to each element+-- and its index)+ifoldl' :: G.Vector v b => (a -> Int -> b -> a) -> a -> v b -> a+ifoldl' = G.ifoldl'+{-# INLINE ifoldl' #-}++-- | /O(n)/ Right fold (function applied to each element and its index)+ifoldr :: G.Vector v a => (Int -> a -> b -> b) -> b -> v a -> b+ifoldr = G.ifoldr+{-# INLINE ifoldr #-}++-- | /O(n)/ Right fold with strict accumulator (function applied to each+-- element and its index)+ifoldr' :: G.Vector v a => (Int -> a -> b -> b) -> b -> v a -> b+ifoldr' = G.ifoldr'+{-# INLINE ifoldr' #-}++-- Specialised folds+-- -----------------++-- | /O(n)/ Check if all elements satisfy the predicate.+all :: G.Vector v a => (a -> Bool) -> v a -> Bool+all = G.all+{-# INLINE all #-}++-- | /O(n)/ Check if any element satisfies the predicate.+any :: G.Vector v a => (a -> Bool) -> v a -> Bool+{-# INLINE any #-}+any = G.any++-- | /O(n)/ Check if all elements are 'True'+and :: G.Vector v Bool => v Bool -> Bool+and = G.and+{-# INLINE and #-}++-- | /O(n)/ Check if any element is 'True'+or :: G.Vector v Bool => v Bool -> Bool+{-# INLINE or #-}+or = G.or++-- | /O(n)/ Compute the sum of the elements+sum :: (G.Vector v a, Num a) => v a -> a+sum = G.sum+{-# INLINE sum #-}++-- | /O(n)/ Compute the produce of the elements+product :: (G.Vector v a, Num a) => v a -> a+product = G.product+{-# INLINE product #-}++-- | /O(n)/ Yield the maximum element of the vector. The vector may not be+-- empty.+maximum :: (G.Vector v a, Ord a) => v a -> a+maximum = G.maximum+{-# INLINE maximum #-}++-- | /O(n)/ Yield the maximum element of the vector according to the given+-- comparison function. The vector may not be empty.+maximumBy :: G.Vector v a => (a -> a -> Ordering) -> v a -> a+maximumBy = G.maximumBy+{-# INLINE maximumBy #-}++-- | /O(n)/ Yield the minimum element of the vector. The vector may not be+-- empty.+minimum :: (G.Vector v a, Ord a) => v a -> a+minimum = G.minimum+{-# INLINE minimum #-}++-- | /O(n)/ Yield the minimum element of the vector according to the given+-- comparison function. The vector may not be empty.+minimumBy :: G.Vector v a => (a -> a -> Ordering) -> v a -> a+minimumBy = G.minimumBy+{-# INLINE minimumBy #-}++-- | /O(n)/ Yield the index of the maximum element of the vector. The vector+-- may not be empty.+maxIndex :: (G.Vector v a, Ord a) => v a -> Int+maxIndex = G.maxIndex+{-# INLINE maxIndex #-}++-- | /O(n)/ Yield the index of the maximum element of the vector according to+-- the given comparison function. The vector may not be empty.+maxIndexBy :: G.Vector v a => (a -> a -> Ordering) -> v a -> Int+maxIndexBy = G.maxIndexBy+{-# INLINE maxIndexBy #-}++-- | /O(n)/ Yield the index of the minimum element of the vector. The vector+-- may not be empty.+minIndex :: (G.Vector v a, Ord a) => v a -> Int+minIndex = G.minIndex+{-# INLINE minIndex #-}++-- | /O(n)/ Yield the index of the minimum element of the vector according to+-- the given comparison function. The vector may not be empty.+minIndexBy :: G.Vector v a => (a -> a -> Ordering) -> v a -> Int+minIndexBy = G.minIndexBy+{-# INLINE minIndexBy #-}++-- Monadic folds+-- -------------++-- | /O(n)/ Monadic fold+foldM :: (G.Vector v b, Monad m) => (a -> b -> m a) -> a -> v b -> m a+foldM = G.foldM+{-# INLINE foldM #-}++-- | /O(n)/ Monadic fold over non-empty vectors+fold1M :: (G.Vector v a, Monad m) => (a -> a -> m a) -> v a -> m a+fold1M = G.fold1M+{-# INLINE fold1M #-}++-- | /O(n)/ Monadic fold with strict accumulator+foldM' :: (G.Vector v b, Monad m) => (a -> b -> m a) -> a -> v b -> m a+foldM' = G.foldM'+{-# INLINE foldM' #-}++-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator+fold1M' :: (G.Vector v a, Monad m) => (a -> a -> m a) -> v a -> m a+fold1M' = G.fold1M'+{-# INLINE fold1M' #-}++-- | /O(n)/ Monadic fold that discards the result+foldM_ :: (G.Vector v b, Monad m) => (a -> b -> m a) -> a -> v b -> m ()+foldM_ = G.foldM_+{-# INLINE foldM_ #-}++-- | /O(n)/ Monadic fold over non-empty vectors that discards the result+fold1M_ :: (G.Vector v a, Monad m) => (a -> a -> m a) -> v a -> m ()+fold1M_ = G.fold1M_+{-# INLINE fold1M_ #-}++-- | /O(n)/ Monadic fold with strict accumulator that discards the result+foldM'_ :: (G.Vector v b, Monad m) => (a -> b -> m a) -> a -> v b -> m ()+foldM'_ = G.foldM'_+{-# INLINE foldM'_ #-}++-- | /O(n)/ Monadic fold over non-empty vectors with strict accumulator+-- that discards the result+fold1M'_ :: (G.Vector v a, Monad m) => (a -> a -> m a) -> Vector a -> m ()+fold1M'_ = G.fold1M'_+{-# INLINE fold1M'_ #-}++-- Monadic sequencing+-- ------------------++-- | Evaluate each action and collect the results+sequence :: (Mixed u v (m a), Monad m) => v (m a) -> m (Vector a)+sequence = mapM id+{-# INLINE sequence #-}++-- | Evaluate each action and discard the results+sequence_ :: (G.Vector v (m a), Monad m) => v (m a) -> m ()+sequence_ = mapM_ id+{-# INLINE sequence_ #-}++-- Prefix sums (scans)+-- -------------------++-- | /O(n)/ Prescan+--+-- @+-- prescanl f z = 'init' . 'scanl' f z+-- @+--+-- Example: @prescanl (+) 0 \<1,2,3,4\> = \<0,1,3,6\>@+--+prescanl :: G.Vector v b => (a -> b -> a) -> a -> v b -> Vector a+prescanl f z = boxed . G.unstream . Stream.inplace (MStream.prescanl f z) . G.stream+{-# INLINE prescanl #-}++-- | /O(n)/ Prescan with strict accumulator+prescanl' :: G.Vector v b => (a -> b -> a) -> a -> v b -> Vector a+prescanl' f z = boxed . G.unstream . Stream.inplace (MStream.prescanl' f z) . G.stream+{-# INLINE prescanl' #-}++-- | /O(n)/ Scan+--+-- @+-- postscanl f z = 'tail' . 'scanl' f z+-- @+--+-- Example: @postscanl (+) 0 \<1,2,3,4\> = \<1,3,6,10\>@+--+postscanl :: G.Vector v b => (a -> b -> a) -> a -> v b -> Vector a+postscanl f z = boxed . G.unstream . Stream.inplace (MStream.postscanl f z) . G.stream+{-# INLINE postscanl #-}++-- | /O(n)/ Scan with strict accumulator+postscanl' :: G.Vector v b => (a -> b -> a) -> a -> v b -> Vector a+postscanl' f z = boxed . G.unstream . Stream.inplace (MStream.postscanl' f z) . G.stream+{-# INLINE postscanl' #-}+++-- | /O(n)/ Haskell-style scan+--+-- > scanl f z <x1,...,xn> = <y1,...,y(n+1)>+-- >   where y1 = z+-- >         yi = f y(i-1) x(i-1)+--+-- Example: @scanl (+) 0 \<1,2,3,4\> = \<0,1,3,6,10\>@+--++scanl :: G.Vector v b => (a -> b -> a) -> a -> v b -> Vector a+scanl f z = boxed . G.unstream . Stream.scanl f z . G.stream+{-# INLINE scanl #-}++-- | /O(n)/ Haskell-style scan with strict accumulator+scanl' :: G.Vector v b => (a -> b -> a) -> a -> v b -> Vector a+scanl' f z = boxed . G.unstream . Stream.scanl' f z . G.stream+{-# INLINE scanl' #-}++-- | /O(n)/ Scan over a non-empty vector+--+-- > scanl f <x1,...,xn> = <y1,...,yn>+-- >   where y1 = x1+-- >         yi = f y(i-1) xi+--+scanl1 :: Mixed u v a => (a -> a -> a) -> v a -> Vector a+scanl1 f = mix . G.scanl1 f+{-# INLINE scanl1 #-}++-- | /O(n)/ Scan over a non-empty vector with a strict accumulator+scanl1' :: Mixed u v a => (a -> a -> a) -> v a -> Vector a+scanl1' f = mix . G.scanl1' f+{-# INLINE scanl1' #-}++-- | /O(n)/ Right-to-left prescan+--+-- @+-- prescanr f z = 'reverse' . 'prescanl' (flip f) z . 'reverse'+-- @+--+prescanr :: G.Vector v a => (a -> b -> b) -> b -> v a -> Vector b+prescanr f z = boxed . G.unstreamR . Stream.inplace (MStream.prescanl (flip f) z) . G.streamR+{-# INLINE prescanr #-}++-- | /O(n)/ Right-to-left prescan with strict accumulator+prescanr' :: G.Vector v a => (a -> b -> b) -> b -> v a -> Vector b+{-# INLINE prescanr' #-}+prescanr' f z = boxed . G.unstreamR . Stream.inplace (MStream.prescanl' (flip f) z) . G.streamR++-- | /O(n)/ Right-to-left scan+postscanr :: G.Vector v a => (a -> b -> b) -> b -> v a -> Vector b+postscanr f z = boxed . G.unstreamR . Stream.inplace (MStream.postscanl (flip f) z) . G.streamR+{-# INLINE postscanr #-}++-- | /O(n)/ Right-to-left scan with strict accumulator+postscanr' :: G.Vector v a => (a -> b -> b) -> b -> v a -> Vector b+postscanr' f z = boxed . G.unstreamR . Stream.inplace (MStream.postscanl' (flip f) z) . G.streamR+{-# INLINE postscanr' #-}++-- | /O(n)/ Right-to-left Haskell-style scan+scanr :: G.Vector v a => (a -> b -> b) -> b -> v a -> Vector b+scanr f z = boxed . G.unstreamR . Stream.scanl (flip f) z . G.streamR+{-# INLINE scanr #-}+++-- | /O(n)/ Right-to-left Haskell-style scan with strict accumulator+scanr' :: G.Vector v a => (a -> b -> b) -> b -> v a -> Vector b+scanr' f z = boxed . G.unstreamR . Stream.scanl' (flip f) z . G.streamR++{-# INLINE scanr' #-}++-- | /O(n)/ Right-to-left scan over a non-empty vector+scanr1 :: Mixed u v a => (a -> a -> a) -> v a -> Vector a+{-# INLINE scanr1 #-}+scanr1 f = mix . G.scanr1 f++-- | /O(n)/ Right-to-left scan over a non-empty vector with a strict+-- accumulator+scanr1' :: (a -> a -> a) -> Vector a -> Vector a+scanr1' f = mix . G.scanr1' f+{-# INLINE scanr1' #-}++-- Conversions - Lists+-- ------------------------++-- | /O(n)/ Convert a vector to a list+toList :: G.Vector v a => v a -> [a]+toList = G.toList+{-# INLINE toList #-}++-- | /O(n)/ Convert a list to a vector+fromList :: [a] -> Vector a+fromList = boxed . G.fromList+{-# INLINE fromList #-}++-- | /O(n)/ Convert the first @n@ elements of a list to a vector+--+-- @+-- fromListN n xs = 'fromList' ('take' n xs)+-- @+fromListN :: Int -> [a] -> Vector a+fromListN n = boxed . G.fromListN n+{-# INLINE fromListN #-}++-- Conversions - Mutable vectors+-- -----------------------------++-- | /O(1)/ Unsafe convert a mutable vector to an immutable one without+-- copying. The mutable vector may not be used after this operation.+unsafeFreeze :: (PrimMonad m, Mixed u v a) => u (PrimState m) a -> m (Vector a)+unsafeFreeze = liftM mix . G.unsafeFreeze+{-# INLINE unsafeFreeze #-}++-- | /O(1)/ Unsafely convert an immutable vector to a mutable one without+-- copying. The immutable vector may not be used after this operation.+unsafeThaw :: (PrimMonad m, Mixed u v a) => v a -> m (MVector (PrimState m) a)+unsafeThaw = liftM mmix . G.unsafeThaw+{-# INLINE unsafeThaw #-}++-- | /O(n)/ Yield a mutable copy of the immutable vector.+thaw :: (PrimMonad m, Mixed u v a) => v a -> m (MVector (PrimState m) a)+thaw = liftM mmix . G.thaw+{-# INLINE thaw #-}++-- | /O(n)/ Yield an immutable copy of the mutable vector.+freeze :: (PrimMonad m, Mixed u v a) => u (PrimState m) a -> m (Vector a)+freeze = liftM mix . G.freeze+{-# INLINE freeze #-}++-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must+-- have the same length. This is not checked.+unsafeCopy :: (PrimMonad m, Mixed u v a, Mixed u' v' a) => u (PrimState m) a -> v' a -> m ()+unsafeCopy dst src = G.unsafeCopy (mmix dst) (mix src)+{-# INLINE unsafeCopy #-}++-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must+-- have the same length.+copy :: (PrimMonad m, Mixed u v a, Mixed u' v' a) => u (PrimState m) a -> v' a -> m ()+copy dst src = G.copy (mmix dst) (mix src)+{-# INLINE copy #-}++-- Utilities+-- ---------++unstreamM :: (Monad m, G.Vector v a) => MStream m a -> m (v a)+unstreamM s = do+  xs <- MStream.toList s+  return $ G.unstream $ Stream.unsafeFromList (MStream.size s) xs+{-# INLINE [1] unstreamM #-}++-- We have to make sure that this is strict in the stream but we can't seq on+-- it while fusion is happening. Hence this ugliness.+modifyWithStream :: G.Vector v a+                 => (forall s. G.Mutable v s a -> Stream b -> ST s ())+                 -> v a -> Stream b -> v a+{-# INLINE modifyWithStream #-}+modifyWithStream p v s = G.new (New.modifyWithStream p (G.clone v) s)

@@ -0,0 +1,283 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE GADTs #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE FunctionalDependencies #-}++-- {-# OPTIONS_GHC -fno-method-sharing #-} -- See: http://trac.haskell.org/vector/ticket/12++#ifndef MIN_VERSION_base+#define MIN_VERSION_base(x,y,z) 1+#endif++module Data.Vector.Mixed.Internal+  ( MVector(..), mboxed, munboxed+  , Vector(..), boxed, unboxed+  , Mixed(..)+  ) where++import Control.Applicative+import Control.Monad+import Data.Monoid+import Data.Foldable+import Data.Traversable+import qualified Data.Vector.Generic.Mutable as GM+import qualified Data.Vector.Generic as G+import qualified Data.Vector as B+import qualified Data.Vector.Mutable as BM+import qualified Data.Vector.Storable as S+import qualified Data.Vector.Primitive as P+import qualified Data.Vector.Unboxed as U+import qualified Data.Vector.Hybrid as H+import Data.Vector.Fusion.Stream as Stream+import Data.Data+import Prelude hiding ( length, null, replicate, reverse, map, read, take, drop, init, tail )+import Text.Read++-- | Vector doesn't provide a way to recover the type of the immutable vector from the mutable vector type+--+-- This would otherwise prevent us from finishing the implementation of 'basicUnsafeFreeze' in 'Vector'+--+-- This class captures the invariants necessary to 'hide' the choice of vector type from the user in such+-- a way that we can go from mutable vector to immutabl vector and back again.+class+  ( Typeable2 mv+  , Typeable1 v+  , mv ~ G.Mutable v+  , GM.MVector mv a+  , G.Vector v a+  ) => Mixed mv v a | mv -> v, v -> mv where++  mmix :: mv s a -> MVector s a+  mmix = MV++  mix :: v a -> Vector a+  mix = V++instance                 Mixed B.MVector B.Vector a+instance S.Storable a => Mixed S.MVector S.Vector a+instance P.Prim a     => Mixed P.MVector P.Vector a+instance U.Unbox a    => Mixed U.MVector U.Vector a+instance (Mixed u v a, Mixed u' v' b) => Mixed (H.MVector u u') (H.Vector v v') (a, b)+instance Mixed MVector Vector a where+  mmix = id -- don't nest!+  mix = id++-- | A @MVector s a@ is mutable vector that could have any vector type underneath+data MVector :: * -> * -> * where+  MV :: Mixed mv v a => !(mv s a) -> MVector s a+ deriving Typeable++{-# RULES+"mstream/MV" forall v.+  GM.mstream (MV v) = GM.mstream v++"mstreamR/MV" forall v.+  GM.mstreamR (MV v) = GM.mstreamR v+  #-}++munboxed :: U.Unbox a => U.MVector s a -> MVector s a+munboxed = MV++mboxed :: BM.MVector s a -> MVector s a+mboxed = MV++unboxed :: U.Unbox a => U.Vector a -> Vector a+unboxed = V++boxed :: B.Vector a -> Vector a+boxed = V++newtype Id a = Id { runId :: a }++cast2 :: (Typeable2 p, Typeable2 q) => p a b -> Maybe (q a b)+cast2 x = runId <$> gcast2 (Id x)+{-# INLINE cast2 #-}++instance GM.MVector MVector a where+  basicLength (MV ks) = GM.basicLength ks+  {-# INLINE basicLength #-}+  basicUnsafeSlice s e (MV ks) = MV (GM.basicUnsafeSlice s e ks)+  {-# INLINE basicUnsafeSlice #-}+  basicOverlaps (MV as) (MV bs) = case cast2 as of+    Nothing -> True -- False could allow a composite vector that _does_ overlap internally to slip through!+    Just cs -> GM.basicOverlaps cs bs+  {-# INLINE basicOverlaps #-}+  basicUnsafeNew n = liftM mboxed (GM.basicUnsafeNew n)+  {-# INLINE basicUnsafeNew #-}+  basicUnsafeReplicate n k = liftM mboxed (GM.basicUnsafeReplicate n k)+  {-# INLINE basicUnsafeReplicate #-}+  basicUnsafeRead (MV ks) n = GM.basicUnsafeRead ks n+  {-# INLINE basicUnsafeRead #-}+  basicUnsafeWrite (MV ks) n k = GM.basicUnsafeWrite ks n k+  {-# INLINE basicUnsafeWrite #-}+  basicClear (MV ks) = GM.basicClear ks+  {-# INLINE basicClear #-}+  basicSet (MV ks) k = GM.basicSet ks k+  {-# INLINE basicSet #-}+  basicUnsafeCopy (MV dst) (MV src) = case cast2 dst of+      Nothing   -> go 0+      Just dst' -> GM.basicUnsafeCopy dst' src -- the types match, allow fast copy+    where+      n = GM.basicLength src+      go i+        | i < n = do+          x <- GM.basicUnsafeRead src i+          GM.basicUnsafeWrite dst i x+          go (i+1)+        | otherwise = return ()+  {-# INLINE basicUnsafeCopy #-}++  basicUnsafeMove (MV dst) (MV src) = case cast2 dst of+    Just dst' -> GM.basicUnsafeMove dst' src+    Nothing   -> do+      srcCopy <- GM.munstream (GM.mstream src)+      GM.basicUnsafeCopy dst srcCopy+  {-# INLINE basicUnsafeMove #-}++  basicUnsafeGrow (MV ks) n = liftM MV (GM.basicUnsafeGrow ks n)+  {-# INLINE basicUnsafeGrow #-}++-- mixed vectors+data Vector :: * -> * where+  V :: Mixed mv v a => !(v a) -> Vector a+ deriving Typeable++{-# RULES+"stream/V" forall v.+  G.stream (V v) = G.stream v+"streamR/V" forall v.+  G.streamR (V v) = G.streamR v+  #-}++type instance G.Mutable Vector = MVector++instance G.Vector Vector a where+  basicUnsafeFreeze (MV ks) = liftM V (G.basicUnsafeFreeze ks)+  {-# INLINE basicUnsafeFreeze #-}+  basicUnsafeThaw (V ks) = liftM MV (G.basicUnsafeThaw ks)+  {-# INLINE basicUnsafeThaw #-}+  basicLength (V ks) = G.basicLength ks+  {-# INLINE basicLength #-}+  basicUnsafeSlice i j (V ks) = V (G.basicUnsafeSlice i j ks)+  {-# INLINE basicUnsafeSlice #-}+  basicUnsafeIndexM (V ks) n = G.basicUnsafeIndexM ks n+  {-# INLINE basicUnsafeIndexM #-}+  basicUnsafeCopy (MV dst) (V src) = case cast2 dst of+      Just dst' -> G.basicUnsafeCopy dst' src+      Nothing -> go 0+    where+      !n = G.basicLength src+      go i+        | i < n = do+          x <- G.basicUnsafeIndexM src i+          GM.basicUnsafeWrite dst i x+          go (i+1)+        | otherwise = return ()+  {-# INLINE basicUnsafeCopy #-}+  elemseq (V ks) k b = G.elemseq ks k b+  {-# INLINE elemseq #-}++instance Monoid (Vector a) where+  mappend = (G.++)+  {-# INLINE mappend #-}+  mempty = G.empty+  {-# INLINE mempty #-}+  mconcat = G.concat+  {-# INLINE mconcat #-}++instance Show a => Show (Vector a) where+  showsPrec = G.showsPrec++instance Read a => Read (Vector a) where+  readPrec = G.readPrec+  readListPrec = readListPrecDefault++instance Data a => Data (Vector a) where+  gfoldl       = G.gfoldl+  toConstr _   = error "toConstr" -- TODO: virtual constructor+  gunfold _ _  = error "gunfold"  -- TODO: virtual constructor+  dataTypeOf _ = G.mkType "Data.Vector.Mixed.Vector"+  dataCast1    = G.dataCast++instance Eq a => Eq (Vector a) where+  xs == ys = Stream.eq (G.stream xs) (G.stream ys)+  {-# INLINE (==) #-}++  xs /= ys = not (Stream.eq (G.stream xs) (G.stream ys))+  {-# INLINE (/=) #-}+++-- See http://trac.haskell.org/vector/ticket/12+instance Ord a => Ord (Vector a) where+  compare xs ys = Stream.cmp (G.stream xs) (G.stream ys)+  {-# INLINE compare #-}++  xs < ys = Stream.cmp (G.stream xs) (G.stream ys) == LT+  {-# INLINE (<) #-}++  xs <= ys = Stream.cmp (G.stream xs) (G.stream ys) /= GT+  {-# INLINE (<=) #-}++  xs > ys = Stream.cmp (G.stream xs) (G.stream ys) == GT+  {-# INLINE (>) #-}++  xs >= ys = Stream.cmp (G.stream xs) (G.stream ys) /= LT+  {-# INLINE (>=) #-}++instance Functor Vector where+  fmap = G.map+  {-# INLINE fmap #-}++instance Monad Vector where+  return = G.singleton+  {-# INLINE return #-}++  (>>=) = flip G.concatMap+  {-# INLINE (>>=) #-}++instance MonadPlus Vector where+  {-# INLINE mzero #-}+  mzero = G.empty++  {-# INLINE mplus #-}+  mplus = (G.++)++instance Applicative Vector where+  pure = G.singleton+  {-# INLINE pure #-}++  (<*>) = ap+  {-# INLINE (<*>) #-}++instance Alternative Vector where+  empty = G.empty+  {-# INLINE empty #-}++  (<|>) = (G.++)+  {-# INLINE (<|>) #-}++instance Foldable Vector where+  foldr = G.foldr+  {-# INLINE foldr #-}++  foldl = G.foldl+  {-# INLINE foldl #-}++  foldr1 = G.foldr1+  {-# INLINE foldr1 #-}++  foldl1 = G.foldl1+  {-# INLINE foldl1 #-}++instance Traversable Vector where+  traverse f v = G.fromListN (G.length v) <$> traverse f (G.toList v)+  {-# INLINE traverse #-}

@@ -0,0 +1,276 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE KindSignatures #-}+{-# LANGUAGE GADTs #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE ScopedTypeVariables #-}++#ifndef MIN_VERSION_base+#define MIN_VERSION_base(x,y,z) 1+#endif++module Data.Vector.Mixed.Mutable+  ( MVector+  , IOVector+  , STVector++  -- * Accessors++  -- ** Length information+  , length, null++  -- ** Extracting subvectors+  , slice, init, tail, take, drop, splitAt+  , unsafeSlice, unsafeInit, unsafeTail, unsafeTake, unsafeDrop++  -- ** Overlapping+  , overlaps++  -- * Construction+  , replicateM, move, unsafeMove++  -- ** Initialisation+  , new, unsafeNew, replicate, clone++  -- ** Growing+  , grow, unsafeGrow++  -- ** Restricting memory usage+  , clear++  -- * Accessing individual elements+  , read, write, swap+  , unsafeRead, unsafeWrite, unsafeSwap++  -- * Modifying vectors++  -- ** Filling and copying+  , set, copy, unsafeCopy++  ) where++import Control.Monad (liftM)+import Control.Monad.Primitive+import qualified Data.Vector.Generic.Mutable as G+import Data.Vector.Mixed.Internal+import Prelude hiding (length, null, replicate, reverse, map, read, take, drop, init, tail, splitAt)++type IOVector = MVector RealWorld++type STVector = MVector++-- Length information+-- ------------------++-- | Length of the mutable vector.+length :: G.MVector u a => u s a -> Int+length = G.length+{-# INLINE length #-}++-- | Check whether the vector is empty+null :: G.MVector u a => u s a -> Bool+null = G.null+{-# INLINE null #-}++-- Extracting subvectors+-- ---------------------++-- | Yield a part of the mutable vector without copying it.+slice :: Mixed u v a => Int -> Int -> u s a -> MVector s a+slice i j m = mmix (G.slice i j m)+{-# INLINE slice #-}++take :: Mixed u v a => Int -> u s a -> MVector s a+take i m = mmix (G.take i m)+{-# INLINE take #-}++drop :: Mixed u v a => Int -> u s a -> MVector s a+drop i m = mmix (G.drop i m)+{-# INLINE drop #-}++splitAt :: Mixed u v a => Int -> u s a -> (MVector s a, MVector s a)+splitAt i m = case G.splitAt i m of+  (l,r) -> (mmix l, mmix r)+{-# INLINE splitAt #-}++init :: Mixed u v a => u s a -> MVector s a+init m = mmix (G.init m)+{-# INLINE init #-}++tail :: Mixed u v a => u s a -> MVector s a+tail m = mmix (G.tail m)+{-# INLINE tail #-}++-- | Yield a part of the mutable vector without copying it. No bounds checks+-- are performed.+unsafeSlice :: Mixed u v a => Int  -- ^ starting index+            -> Int  -- ^ length of the slice+            -> u s a+            -> MVector s a+unsafeSlice i j m  = mmix (G.unsafeSlice i j m)+{-# INLINE unsafeSlice #-}++unsafeTake :: Mixed u v a => Int -> u s a -> MVector s a+unsafeTake i m = mmix (G.unsafeTake i m)+{-# INLINE unsafeTake #-}++unsafeDrop :: Mixed u v a => Int -> u s a -> MVector s a+unsafeDrop i m = mmix (G.unsafeDrop i m)+{-# INLINE unsafeDrop #-}++unsafeInit :: Mixed u v a => u s a -> MVector s a+unsafeInit m = mmix (G.unsafeInit m)+{-# INLINE unsafeInit #-}++unsafeTail :: Mixed u v a => u s a -> MVector s a+unsafeTail m = mmix (G.unsafeTail m)+{-# INLINE unsafeTail #-}++-- Overlapping+-- -----------++-- Check whether two vectors overlap.+overlaps :: (Mixed u v a, Mixed u' v' a) => u s a -> u' s a -> Bool+overlaps m n = G.overlaps (mmix m) (mmix n)+{-# INLINE overlaps #-}++-- Initialisation+-- --------------++-- | Create a mutable vector of the given length.+new :: PrimMonad m => Int -> m (MVector (PrimState m) a)+new = G.new+{-# INLINE new #-}++-- | Create a mutable vector of the given length. The length is not checked.+unsafeNew :: PrimMonad m => Int -> m (MVector (PrimState m) a)+unsafeNew n = liftM mboxed (G.unsafeNew n)+{-# INLINE unsafeNew #-}++-- | Create a mutable vector of the given length (0 if the length is negative)+-- and fill it with an initial value.+replicate :: PrimMonad m => Int -> a -> m (MVector (PrimState m) a)+replicate n a = liftM mboxed (G.replicate n a)+{-# INLINE replicate #-}++-- | Create a mutable vector of the given length (0 if the length is negative)+-- and fill it with values produced by repeatedly executing the monadic action.+replicateM :: PrimMonad m => Int -> m a -> m (MVector (PrimState m) a)+replicateM n m = liftM mboxed (G.replicateM n m)+{-# INLINE replicateM #-}++-- | Create a copy of a mutable vector.+clone :: (PrimMonad m, Mixed u v a) => u (PrimState m) a -> m (MVector (PrimState m) a)+clone m = liftM mmix (G.clone m)+{-# INLINE clone #-}++-- Growing+-- -------++-- | Grow a vector by the given number of elements. The number must be+-- positive.+grow :: (PrimMonad m, Mixed u v a) => u (PrimState m) a -> Int -> m (MVector (PrimState m) a)+grow m n = liftM mmix (G.grow m n)+{-# INLINE grow #-}++-- | Grow a vector by the given number of elements. The number must be+-- positive but this is not checked.+unsafeGrow :: (PrimMonad m, Mixed u v a) => u (PrimState m) a -> Int -> m (MVector (PrimState m) a)+unsafeGrow m n = liftM mmix (G.unsafeGrow m n)+{-# INLINE unsafeGrow #-}++-- Restricting memory usage+-- ------------------------++-- | Reset all elements of the vector to some undefined value, clearing all+-- references to external objects. This is usually a noop for unboxed vectors.+clear :: (PrimMonad m, G.MVector u a) => u (PrimState m) a -> m ()+clear = G.clear+{-# INLINE clear #-}++-- Accessing individual elements+-- -----------------------------++-- | Yield the element at the given position.+read :: (PrimMonad m, G.MVector u a) => u (PrimState m) a -> Int -> m a+read = G.read+{-# INLINE read #-}++-- | Replace the element at the given position.+write :: (PrimMonad m, G.MVector u a) => u (PrimState m) a -> Int -> a -> m ()+write = G.write+{-# INLINE write #-}++-- | Swap the elements at the given positions.+swap :: (PrimMonad m, G.MVector u a) => u (PrimState m) a -> Int -> Int -> m ()+swap = G.swap+{-# INLINE swap #-}+++-- | Yield the element at the given position. No bounds checks are performed.+unsafeRead :: (PrimMonad m, G.MVector u a) => u (PrimState m) a -> Int -> m a+unsafeRead = G.unsafeRead+{-# INLINE unsafeRead #-}++-- | Replace the element at the given position. No bounds checks are performed.+unsafeWrite :: (PrimMonad m, G.MVector u a) => u (PrimState m) a -> Int -> a -> m ()+unsafeWrite = G.unsafeWrite+{-# INLINE unsafeWrite #-}++-- | Swap the elements at the given positions. No bounds checks are performed.+unsafeSwap :: (PrimMonad m, G.MVector u a) => u (PrimState m) a -> Int -> Int -> m ()+unsafeSwap = G.unsafeSwap+{-# INLINE unsafeSwap #-}++-- Filling and copying+-- -------------------++-- | Set all elements of the vector to the given value.+set :: (PrimMonad m, G.MVector u a) => u (PrimState m) a -> a -> m ()+set = G.set+{-# INLINE set #-}++-- | Copy a vector. The two vectors must have the same length and may not+-- overlap.+copy :: (PrimMonad m, Mixed u v a, Mixed u' v' a) => u (PrimState m) a -> u' (PrimState m) a -> m ()+copy dst src = G.copy (mmix dst) (mmix src)+{-# INLINE copy #-}++-- | Copy a vector. The two vectors must have the same length and may not+-- overlap. This is not checked.+unsafeCopy+  :: (PrimMonad m, Mixed u v a, Mixed u' v' a)+  => u (PrimState m) a   -- ^ target+  -> u' (PrimState m) a   -- ^ source+  -> m ()+unsafeCopy dst src = G.unsafeCopy (mmix dst) (mmix src)+{-# INLINE unsafeCopy #-}++-- | Move the contents of a vector. The two vectors must have the same+-- length.+--+-- If the vectors do not overlap, then this is equivalent to 'copy'.+-- Otherwise, the copying is performed as if the source vector were+-- copied to a temporary vector and then the temporary vector was copied+-- to the target vector.+move :: (PrimMonad m, Mixed u v a, Mixed u' v' a) => u (PrimState m) a -> u' (PrimState m) a -> m ()+move dst src = G.move (mmix dst) (mmix src)+{-# INLINE move #-}++-- | Move the contents of a vector. The two vectors must have the same+-- length, but this is not checked.+--+-- If the vectors do not overlap, then this is equivalent to 'unsafeCopy'.+-- Otherwise, the copying is performed as if the source vector were+-- copied to a temporary vector and then the temporary vector was copied+-- to the target vector.+unsafeMove :: (PrimMonad m, Mixed u v a, Mixed u' v' a)  +  => u (PrimState m) a   -- ^ target+  -> u' (PrimState m) a   -- ^ source+  -> m ()+unsafeMove dst src = G.unsafeMove (mmix dst) (mmix src)+{-# INLINE unsafeMove #-}