-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Efficient multidimensional arrays
--   
--   <a>generalized Algebraic Dynamic Programming</a>
--   
--   This library provides efficient multidimensional arrays. Import
--   <tt>Data.PrimitiveArray</tt> for indices, lenses, and arrays.
--   
--   For <a>generalized ADP</a> users, the library also provides the
--   machinary to fill tables in the correct order required by usual
--   CYK-style parsers, or regular grammars (used e.g. in alignment
--   algorithms). This means that unless your grammar requires a strange
--   order in which parsing is to be performed, it will mostly "just work".
--   
--   In general operations do not perform bounds-checking or other
--   sanity-checking and are aimed towards efficiency as much as possible.
--   Users (like <tt>ADPfusion</tt>) should perform their own
--   bounds-checking, outside of code that performs "loop-like" operations.
@package PrimitiveArray
@version 0.10.1.0

module Data.PrimitiveArray.Index.Class

-- | Strict pairs -- as in <tt>repa</tt>.
data a :. b
(:.) :: !a -> !b -> (:.) a b
infixl 3 :.
infixl 3 :.

-- | A different version of strict pairs. Makes for simpler type inference
--   in multi-tape grammars. We use <tt>:&gt;</tt> when we have special
--   needs, like non-recursive instances on inductives tuples, as used for
--   set indices.
--   
--   This one is <tt>infixr</tt> so that in <tt>a :&gt; b</tt> we can have
--   the main type in <tt>a</tt> and the specializing types in <tt>b</tt>
--   and then dispatch on <tt>a :&gt; ts</tt> with <tt>ts</tt> maybe a
--   chain of <tt>:&gt;</tt>.
data a :> b
(:>) :: !a -> !b -> (:>) a b
infixr 3 :>
infixr 3 :>

-- | Base data constructor for multi-dimensional indices.
data Z
Z :: Z

-- | Index structures for complex, heterogeneous indexing. Mostly designed
--   for indexing in DP grammars, where the indices work for linear and
--   context-free grammars on one or more tapes, for strings, sets, later
--   on tree structures.
class Index i where {
    
    -- | Data structure encoding the upper limit for each array.
    data family LimitType i :: *;
}

-- | Given a maximal size, and a current index, calculate the linear index.
linearIndex :: Index i => LimitType i -> i -> Int

-- | Given a maximal size and a valid <tt>Int</tt>, return the index.
fromLinearIndex :: Index i => LimitType i -> Int -> i

-- | Given the <a>LimitType</a>, return the number of cells required for
--   storage.
size :: Index i => LimitType i -> Int

-- | Check if an index is within the bounds.
inBounds :: Index i => LimitType i -> i -> Bool

-- | A lower bound of <tt>zero</tt>
zeroBound :: Index i => i

-- | A lower bound of <tt>zero</tt> but for a <tt>LimitType i</tt>.
zeroBound' :: Index i => LimitType i

-- | The list of cell sizes for each dimension. its product yields the
--   total size.
totalSize :: Index i => LimitType i -> [Integer]

-- | Pretty-print all upper bounds
showBound :: Index i => LimitType i -> [String]

-- | Pretty-print all indices
showIndex :: Index i => i -> [String]

-- | Given the maximal number of cells (<tt>Word</tt>, because this is the
--   pointer limit for the machine), and the list of sizes, will check if
--   this is still legal. Consider dividing the <tt>Word</tt> by the actual
--   memory requirements for each cell, to get better exception handling
--   for too large arrays.
--   
--   One list should be given for each array.
sizeIsValid :: Monad m => Word -> [[Integer]] -> ExceptT SizeError m CellSize

-- | In case <tt>totalSize</tt> or variants thereof produce a size that is
--   too big to handle.
newtype SizeError
SizeError :: String -> SizeError

-- | The total number of cells that are allocated.
newtype CellSize
CellSize :: Word -> CellSize

-- | Generate a stream of indices in correct order for dynamic programming.
--   Since the stream generators require <tt>concatMap</tt> /
--   <tt>flatten</tt> we have to write more specialized code for
--   <tt>(z:.IX)</tt> stuff.
class (Index i) => IndexStream i

-- | Generate an index stream using <a>LimitType</a>s. This prevents having
--   to figure out how the actual limits for complicated index types (like
--   <tt>Set</tt>) would look like, since for <tt>Set</tt>, for example,
--   the <tt>LimitType Set == Int</tt> provides just the number of bits.
--   
--   This generates an index stream suitable for <tt>forward</tt> structure
--   filling. The first index is the smallest (or the first indices
--   considered are all equally small in partially ordered sets). Larger
--   indices follow up until the largest one.
streamUp :: (IndexStream i, Monad m) => LimitType i -> LimitType i -> Stream m i

-- | If <a>streamUp</a> generates indices from smallest to largest, then
--   <a>streamDown</a> generates indices from largest to smallest. Outside
--   grammars make implicit use of this. Asking for an axiom in
--   backtracking requests the first element from this stream.
streamDown :: (IndexStream i, Monad m) => LimitType i -> LimitType i -> Stream m i

-- | <tt>manhattan</tt> turns an index <tt>sh</tt> into a starting point
--   within <tt>sparseIndices</tt> of the <tt>Sparse</tt> data structure.
--   This should reduce the time required to search <tt>sparseIndices</tt>,
--   because <tt>manhattanStart[manhattan sh]</tt> yields a left bound,
--   while <tt>manhattanStart[manhattan sh +1]</tt> will yield an excluded
--   right bound.
--   
--   Uses the <tt>Manhattan</tt> distance.
--   
--   TODO This should probably be moved into the <tt>Index</tt> module.
class SparseBucket sh

-- | The manhattan distance for an index.
manhattan :: SparseBucket sh => LimitType sh -> sh -> Int

-- | The maximal possible manhattan distance.
manhattanMax :: SparseBucket sh => LimitType sh -> Int
instance GHC.Show.Show Data.PrimitiveArray.Index.Class.SizeError
instance GHC.Classes.Ord Data.PrimitiveArray.Index.Class.SizeError
instance GHC.Classes.Eq Data.PrimitiveArray.Index.Class.SizeError
instance GHC.Enum.Enum Data.PrimitiveArray.Index.Class.CellSize
instance GHC.Real.Real Data.PrimitiveArray.Index.Class.CellSize
instance GHC.Real.Integral Data.PrimitiveArray.Index.Class.CellSize
instance GHC.Enum.Bounded Data.PrimitiveArray.Index.Class.CellSize
instance GHC.Num.Num Data.PrimitiveArray.Index.Class.CellSize
instance GHC.Show.Show Data.PrimitiveArray.Index.Class.CellSize
instance GHC.Classes.Ord Data.PrimitiveArray.Index.Class.CellSize
instance GHC.Classes.Eq Data.PrimitiveArray.Index.Class.CellSize
instance GHC.Classes.Eq (Data.PrimitiveArray.Index.Class.LimitType Data.PrimitiveArray.Index.Class.Z)
instance GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType Data.PrimitiveArray.Index.Class.Z)
instance GHC.Read.Read (Data.PrimitiveArray.Index.Class.LimitType Data.PrimitiveArray.Index.Class.Z)
instance GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType Data.PrimitiveArray.Index.Class.Z)
instance Data.Data.Data (Data.PrimitiveArray.Index.Class.LimitType Data.PrimitiveArray.Index.Class.Z)
instance GHC.Enum.Bounded (Data.PrimitiveArray.Index.Class.LimitType Data.PrimitiveArray.Index.Class.Z)
instance (GHC.Classes.Eq (Data.PrimitiveArray.Index.Class.LimitType zs), GHC.Classes.Eq (Data.PrimitiveArray.Index.Class.LimitType z)) => GHC.Classes.Eq (Data.PrimitiveArray.Index.Class.LimitType (zs Data.PrimitiveArray.Index.Class.:. z))
instance (GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType zs), GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType z)) => GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType (zs Data.PrimitiveArray.Index.Class.:. z))
instance (GHC.Read.Read (Data.PrimitiveArray.Index.Class.LimitType zs), GHC.Read.Read (Data.PrimitiveArray.Index.Class.LimitType z)) => GHC.Read.Read (Data.PrimitiveArray.Index.Class.LimitType (zs Data.PrimitiveArray.Index.Class.:. z))
instance (GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType zs), GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType z)) => GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType (zs Data.PrimitiveArray.Index.Class.:. z))
instance (Data.Data.Data zs, Data.Data.Data (Data.PrimitiveArray.Index.Class.LimitType zs), Data.Typeable.Internal.Typeable zs, Data.Data.Data z, Data.Data.Data (Data.PrimitiveArray.Index.Class.LimitType z), Data.Typeable.Internal.Typeable z) => Data.Data.Data (Data.PrimitiveArray.Index.Class.LimitType (zs Data.PrimitiveArray.Index.Class.:. z))
instance (GHC.Enum.Bounded (Data.PrimitiveArray.Index.Class.LimitType zs), GHC.Enum.Bounded (Data.PrimitiveArray.Index.Class.LimitType z)) => GHC.Enum.Bounded (Data.PrimitiveArray.Index.Class.LimitType (zs Data.PrimitiveArray.Index.Class.:. z))
instance Data.PrimitiveArray.Index.Class.SparseBucket Data.PrimitiveArray.Index.Class.Z
instance (Data.PrimitiveArray.Index.Class.SparseBucket i, Data.PrimitiveArray.Index.Class.SparseBucket is) => Data.PrimitiveArray.Index.Class.SparseBucket (is Data.PrimitiveArray.Index.Class.:. i)
instance Data.PrimitiveArray.Index.Class.IndexStream Data.PrimitiveArray.Index.Class.Z
instance Data.PrimitiveArray.Index.Class.Index Data.PrimitiveArray.Index.Class.Z
instance (Data.PrimitiveArray.Index.Class.Index zs, Data.PrimitiveArray.Index.Class.Index z) => Data.PrimitiveArray.Index.Class.Index (zs Data.PrimitiveArray.Index.Class.:. z)
instance Data.Vector.Unboxed.Base.Unbox Data.PrimitiveArray.Index.Class.Z
instance Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector Data.PrimitiveArray.Index.Class.Z
instance Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector Data.PrimitiveArray.Index.Class.Z
instance Data.Binary.Class.Binary Data.PrimitiveArray.Index.Class.Z
instance Data.Serialize.Serialize Data.PrimitiveArray.Index.Class.Z
instance Data.Aeson.Types.ToJSON.ToJSON Data.PrimitiveArray.Index.Class.Z
instance Data.Aeson.Types.FromJSON.FromJSON Data.PrimitiveArray.Index.Class.Z
instance Data.Hashable.Class.Hashable Data.PrimitiveArray.Index.Class.Z
instance Test.QuickCheck.Arbitrary.Arbitrary Data.PrimitiveArray.Index.Class.Z
instance Control.DeepSeq.NFData Data.PrimitiveArray.Index.Class.Z
instance Control.Lens.Tuple.Field1 (Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a) (Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a') a a'
instance Control.Lens.Tuple.Field1 ((Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a) Data.PrimitiveArray.Index.Class.:. b) ((Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a') Data.PrimitiveArray.Index.Class.:. b) a a'
instance Control.Lens.Tuple.Field1 (((Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a) Data.PrimitiveArray.Index.Class.:. b) Data.PrimitiveArray.Index.Class.:. c) (((Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a') Data.PrimitiveArray.Index.Class.:. b) Data.PrimitiveArray.Index.Class.:. c) a a'
instance Control.Lens.Tuple.Field2 ((Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a) Data.PrimitiveArray.Index.Class.:. b) ((Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a) Data.PrimitiveArray.Index.Class.:. b') b b'
instance Control.Lens.Tuple.Field2 (((Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a) Data.PrimitiveArray.Index.Class.:. b) Data.PrimitiveArray.Index.Class.:. c) (((Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a) Data.PrimitiveArray.Index.Class.:. b') Data.PrimitiveArray.Index.Class.:. c) b b'
instance Control.Lens.Tuple.Field3 (((Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a) Data.PrimitiveArray.Index.Class.:. b) Data.PrimitiveArray.Index.Class.:. c) (((Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. a) Data.PrimitiveArray.Index.Class.:. b) Data.PrimitiveArray.Index.Class.:. c') c c'
instance GHC.Enum.Bounded Data.PrimitiveArray.Index.Class.Z
instance Data.Data.Data Data.PrimitiveArray.Index.Class.Z
instance GHC.Generics.Generic Data.PrimitiveArray.Index.Class.Z
instance GHC.Show.Show Data.PrimitiveArray.Index.Class.Z
instance GHC.Read.Read Data.PrimitiveArray.Index.Class.Z
instance GHC.Classes.Ord Data.PrimitiveArray.Index.Class.Z
instance GHC.Classes.Eq Data.PrimitiveArray.Index.Class.Z
instance (GHC.Read.Read a, GHC.Read.Read b) => GHC.Read.Read (a Data.PrimitiveArray.Index.Class.:> b)
instance (Data.Vector.Unboxed.Base.Unbox a, Data.Vector.Unboxed.Base.Unbox b) => Data.Vector.Unboxed.Base.Unbox (a Data.PrimitiveArray.Index.Class.:> b)
instance (Data.Vector.Unboxed.Base.Unbox a, Data.Vector.Unboxed.Base.Unbox b) => Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (a Data.PrimitiveArray.Index.Class.:> b)
instance (Data.Vector.Unboxed.Base.Unbox a, Data.Vector.Unboxed.Base.Unbox b) => Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (a Data.PrimitiveArray.Index.Class.:> b)
instance (Data.Binary.Class.Binary a, Data.Binary.Class.Binary b) => Data.Binary.Class.Binary (a Data.PrimitiveArray.Index.Class.:> b)
instance (Data.Serialize.Serialize a, Data.Serialize.Serialize b) => Data.Serialize.Serialize (a Data.PrimitiveArray.Index.Class.:> b)
instance (Data.Aeson.Types.ToJSON.ToJSON a, Data.Aeson.Types.ToJSON.ToJSON b) => Data.Aeson.Types.ToJSON.ToJSON (a Data.PrimitiveArray.Index.Class.:> b)
instance (Data.Aeson.Types.FromJSON.FromJSON a, Data.Aeson.Types.FromJSON.FromJSON b) => Data.Aeson.Types.FromJSON.FromJSON (a Data.PrimitiveArray.Index.Class.:> b)
instance (Data.Hashable.Class.Hashable a, Data.Hashable.Class.Hashable b) => Data.Hashable.Class.Hashable (a Data.PrimitiveArray.Index.Class.:> b)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData b) => Control.DeepSeq.NFData (a Data.PrimitiveArray.Index.Class.:> b)
instance (Data.Data.Data a, Data.Data.Data b) => Data.Data.Data (a Data.PrimitiveArray.Index.Class.:> b)
instance GHC.Generics.Generic (a Data.PrimitiveArray.Index.Class.:> b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (a Data.PrimitiveArray.Index.Class.:> b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (a Data.PrimitiveArray.Index.Class.:> b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (a Data.PrimitiveArray.Index.Class.:> b)
instance (GHC.Read.Read a, GHC.Read.Read b) => GHC.Read.Read (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Vector.Unboxed.Base.Unbox a, Data.Vector.Unboxed.Base.Unbox b) => Data.Vector.Unboxed.Base.Unbox (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Vector.Unboxed.Base.Unbox a, Data.Vector.Unboxed.Base.Unbox b) => Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Vector.Unboxed.Base.Unbox a, Data.Vector.Unboxed.Base.Unbox b) => Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Binary.Class.Binary a, Data.Binary.Class.Binary b) => Data.Binary.Class.Binary (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Serialize.Serialize a, Data.Serialize.Serialize b) => Data.Serialize.Serialize (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Aeson.Types.ToJSON.ToJSON a, Data.Aeson.Types.ToJSON.ToJSON b) => Data.Aeson.Types.ToJSON.ToJSON (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Aeson.Types.FromJSON.FromJSON a, Data.Aeson.Types.FromJSON.FromJSON b) => Data.Aeson.Types.FromJSON.FromJSON (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Hashable.Class.Hashable a, Data.Hashable.Class.Hashable b) => Data.Hashable.Class.Hashable (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Aeson.Types.ToJSON.ToJSON a, Data.Aeson.Types.ToJSON.ToJSONKey a, Data.Aeson.Types.ToJSON.ToJSON b, Data.Aeson.Types.ToJSON.ToJSONKey b) => Data.Aeson.Types.ToJSON.ToJSONKey (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Aeson.Types.FromJSON.FromJSON a, Data.Aeson.Types.FromJSON.FromJSONKey a, Data.Aeson.Types.FromJSON.FromJSON b, Data.Aeson.Types.FromJSON.FromJSONKey b) => Data.Aeson.Types.FromJSON.FromJSONKey (a Data.PrimitiveArray.Index.Class.:. b)
instance (Control.DeepSeq.NFData a, Control.DeepSeq.NFData b) => Control.DeepSeq.NFData (a Data.PrimitiveArray.Index.Class.:. b)
instance (Test.QuickCheck.Arbitrary.Arbitrary a, Test.QuickCheck.Arbitrary.Arbitrary b) => Test.QuickCheck.Arbitrary.Arbitrary (a Data.PrimitiveArray.Index.Class.:. b)
instance (Data.Data.Data a, Data.Data.Data b) => Data.Data.Data (a Data.PrimitiveArray.Index.Class.:. b)
instance GHC.Generics.Generic (a Data.PrimitiveArray.Index.Class.:. b)
instance (GHC.Show.Show a, GHC.Show.Show b) => GHC.Show.Show (a Data.PrimitiveArray.Index.Class.:. b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord b) => GHC.Classes.Ord (a Data.PrimitiveArray.Index.Class.:. b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq b) => GHC.Classes.Eq (a Data.PrimitiveArray.Index.Class.:. b)


-- | Vastly extended primitive arrays. Some basic ideas are now modeled
--   after the vector package, especially the monadic mutable / pure
--   immutable array system.
--   
--   Note that in general only bulk operations should error out, error
--   handling for index<i>read</i>write is too costly. General usage should
--   be to create data structures and run the DP code within an error
--   monad, but keep error handling to high-level operations.
module Data.PrimitiveArray.Class

-- | Mutable version of an array.
data family MutArr (m :: * -> *) (arr :: *) :: *

-- | Associate a fill structure with each type of array (dense, sparse,
--   ...).
--   
--   Example: <tt>type instance FillStruc (Sparse w v sh e) = (w sh)</tt>
--   associates the type <tt>(w sh)</tt>, which is of the same type as the
--   underlying <tt>w</tt> structure holding index information for a sparse
--   array.
type family FillStruc arr :: *

-- | The core set of operations for pure and monadic arrays.
class (Index sh) => PrimArrayOps arr sh elm

-- | Returns the bounds of an immutable array, again inclusive bounds: <tt>
--   [lb..ub] </tt>.
upperBound :: PrimArrayOps arr sh elm => arr sh elm -> LimitType sh

-- | Extract a single element from the array. Generally unsafe as not
--   bounds-checking is performed.
unsafeIndex :: PrimArrayOps arr sh elm => arr sh elm -> sh -> elm

-- | Index into immutable array, but safe in case <tt>sh</tt> is not part
--   of the array.
safeIndex :: PrimArrayOps arr sh elm => arr sh elm -> sh -> Maybe elm

-- | Savely transform the shape space of a table.
transformShape :: (PrimArrayOps arr sh elm, Index sh') => (LimitType sh -> LimitType sh') -> arr sh elm -> arr sh' elm

-- | Return the bounds of the array. All bounds are inclusive, as in
--   <tt>[lb..ub]</tt>. Technically not monadic, but rather working on a
--   monadic array.
upperBoundM :: PrimArrayOps arr sh elm => MutArr m (arr sh elm) -> LimitType sh

-- | Given lower and upper bounds and a list of <i>all</i> elements,
--   produce a mutable array.
fromListM :: (PrimArrayOps arr sh elm, PrimMonad m) => LimitType sh -> [elm] -> m (MutArr m (arr sh elm))

-- | Creates a new array with the given bounds with each element within the
--   array being in an undefined state.
newM :: (PrimArrayOps arr sh elm, PrimMonad m) => LimitType sh -> m (MutArr m (arr sh elm))

-- | Variant of <a>newM</a> that requires a fill structure. Mostly for
--   special / sparse structures (hence the <tt>S</tt>, also to be
--   interpreted as "safe", since these functions won't fail with sparse
--   structures).
newSM :: (PrimArrayOps arr sh elm, Monad m, PrimMonad m) => LimitType sh -> FillStruc (arr sh elm) -> m (MutArr m (arr sh elm))

-- | Creates a new array with all elements being equal to <tt>elm</tt>.
newWithM :: (PrimArrayOps arr sh elm, PrimMonad m) => LimitType sh -> elm -> m (MutArr m (arr sh elm))

-- | Variant of <a>newWithM</a>
newWithSM :: (PrimArrayOps arr sh elm, Monad m, PrimMonad m) => LimitType sh -> FillStruc (arr sh elm) -> elm -> m (MutArr m (arr sh elm))

-- | Reads a single element in the array.
readM :: (PrimArrayOps arr sh elm, PrimMonad m) => MutArr m (arr sh elm) -> sh -> m elm

-- | Read from the mutable array, but return <tt>Nothing</tt> in case
--   <tt>sh</tt> does not exist. This will allow streaming DP combinators
--   to "jump" over missing elements.
--   
--   Should be used with <tt>Stream.Monadic.mapMaybe</tt> to get efficient
--   code.
safeReadM :: (PrimArrayOps arr sh elm, Monad m, PrimMonad m) => MutArr m (arr sh elm) -> sh -> m (Maybe elm)

-- | Writes a single element in the array.
writeM :: (PrimArrayOps arr sh elm, PrimMonad m) => MutArr m (arr sh elm) -> sh -> elm -> m ()

-- | Write into the mutable array, but if the index <tt>sh</tt> does not
--   exist, silently continue.
safeWriteM :: (PrimArrayOps arr sh elm, Monad m, PrimMonad m) => MutArr m (arr sh elm) -> sh -> elm -> m ()

-- | Freezes a mutable array an returns its immutable version. This
--   operation is <i>O(1)</i> and both arrays share the same memory. Do not
--   use the mutable array afterwards.
unsafeFreezeM :: (PrimArrayOps arr sh elm, PrimMonad m) => MutArr m (arr sh elm) -> m (arr sh elm)

-- | Thaw an immutable array into a mutable one. Both versions share
--   memory.
unsafeThawM :: (PrimArrayOps arr sh elm, PrimMonad m) => arr sh elm -> m (MutArr m (arr sh elm))
class PrimArrayMap arr sh e e'
mapArray :: PrimArrayMap arr sh e e' => (e -> e') -> arr sh e -> arr sh e'

-- | Sum type of errors that can happen when using primitive arrays.
data PAErrors
PAEUpperBound :: PAErrors

-- | Infix index operator. Performs minimal bounds-checking using assert in
--   non-optimized code.
--   
--   <tt>(!)</tt> is rewritten from phase <tt>[1]</tt> onwards into an
--   optimized form. Before, it uses a very slow form, that does bounds
--   checking.
(!) :: PrimArrayOps arr sh elm => arr sh elm -> sh -> elm

-- | Return value at an index that might not exist.
(!?) :: PrimArrayOps arr sh elm => arr sh elm -> sh -> Maybe elm

-- | Returns true if the index is valid for the array.
inBoundsM :: (Monad m, PrimArrayOps arr sh elm) => MutArr m (arr sh elm) -> sh -> Bool

-- | Construct a mutable primitive array from a lower and an upper bound, a
--   default element, and a list of associations.
fromAssocsM :: (PrimMonad m, PrimArrayOps arr sh elm) => LimitType sh -> elm -> [(sh, elm)] -> m (MutArr m (arr sh elm))

-- | Initialize an immutable array but stay within the primitive monad
--   <tt>m</tt>.
newWithPA :: (PrimMonad m, PrimArrayOps arr sh elm) => LimitType sh -> elm -> m (arr sh elm)

-- | Initialize an immutable array with a fill structure.
newWithSPA :: (PrimMonad m, PrimArrayOps arr sh elm) => LimitType sh -> FillStruc (arr sh elm) -> elm -> m (arr sh elm)

-- | Safely prepare a primitive array.
--   
--   TODO Check if having a <a>MonadError</a> instance degrades
--   performance. (We should see this once the test with NeedlemanWunsch is
--   under way).
safeNewWithPA :: forall m arr sh elm. (PrimMonad m, MonadError PAErrors m, PrimArrayOps arr sh elm) => LimitType sh -> elm -> m (arr sh elm)

-- | Return all associations from an array.
assocs :: forall arr sh elm. (IndexStream sh, PrimArrayOps arr sh elm) => arr sh elm -> [(sh, elm)]

-- | Return all associations from an array.
assocsS :: forall m arr sh elm. (Monad m, IndexStream sh, PrimArrayOps arr sh elm) => arr sh elm -> Stream m (sh, elm)

-- | Creates an immutable array from lower and upper bounds and a complete
--   list of elements.
fromList :: PrimArrayOps arr sh elm => LimitType sh -> [elm] -> arr sh elm

-- | Creates an immutable array from lower and upper bounds, a default
--   element, and a list of associations.
fromAssocs :: PrimArrayOps arr sh elm => LimitType sh -> elm -> [(sh, elm)] -> arr sh elm

-- | Returns all elements of an immutable array as a list.
toList :: forall arr sh elm. (IndexStream sh, PrimArrayOps arr sh elm) => arr sh elm -> [elm]
instance GHC.Generics.Generic Data.PrimitiveArray.Class.PAErrors
instance GHC.Classes.Eq Data.PrimitiveArray.Class.PAErrors
instance GHC.Show.Show Data.PrimitiveArray.Class.PAErrors


-- | A table representation that internally uses a hashtable from the
--   <tt>hashtables</tt> library. The implementation is currently a testbed
--   on which idea makes the most sense.
--   
--   In particular, once a hashtable has been created with, say,
--   <tt>newWithPA</tt>, it will be completely void of any entries. To
--   prime the system, call <tt>setValidKeys</tt> which will setup all keys
--   that are vaild, as well as setup an additional data structure to help
--   with <tt>streamUp</tt> and <tt>streamDown</tt>.
--   
--   This table does not store default values, since it is assumed that
--   lookups are only done on valid keys, and <tt>ADPfusion</tt> as the
--   default consumer should have rules "jump over" missing keys.
--   
--   Currently the idea is that any write to an undeclared key will just
--   fail SILENTLY!
--   
--   TODO this also forces rethinking <tt>inBounds</tt>, as this will now
--   depend on the internal structure given via <tt>setValidKeys</tt>.
module Data.PrimitiveArray.HashTable
data Hashed ht sh e
Hashed :: !LimitType sh -> !IOHashTable ht sh e -> !() -> Hashed ht sh e

-- | Explicitly store the upper bound.
[_hashedUpperBound] :: Hashed ht sh e -> !LimitType sh

-- | The hashtable to be updated / used.
[_hashedTable] :: Hashed ht sh e -> !IOHashTable ht sh e

-- | Helper structure for the <tt>streamUp</tt> / <tt>streamDown</tt>
--   functionality.
--   
--   TODO this should be a recursively constructed hashtable, based on the
--   shape of <tt>sh</tt>.
[_hashedUpDown] :: Hashed ht sh e -> !()

-- | Sets valid keys, working within a primitive Monad. The valid keys
--   should be a hashtable with all correct keys, but values set to
--   something resembling a default value. A good choice will be akin to
--   <tt>mzero</tt>.
--   
--   Internally, this function uses <tt>unsafeCoerce</tt> to change the
--   <tt>PrimState</tt> token held by the hash table to <tt>RealWord</tt>,
--   from whatever it is.
--   
--   TODO setup the <tt>hashedUpDown</tt> part, once it is clear what to
--   do.
setValidKeys :: (PrimMonad m, HashTable h) => LimitType sh -> h (PrimState m) k v -> m (Hashed ht sh e)


-- | Dense primitive arrays where the lower index is zero (or the
--   equivalent of zero for newtypes and enumerations).
--   
--   Actual <tt>write</tt>s to data structures use a more safe
--   <tt>write</tt> instead of the unsafe <tt>unsafeWrite</tt>. Writes also
--   tend to occur much less in DP algorithms (say, N^2 writes for an N^3
--   time algorithm -- mostly reads are being executed).
--   
--   TODO consider if we want to force the lower index to be zero, or allow
--   non-zero lower indices. Will have to be considered together with the
--   <tt>Index.Class</tt> module!
--   
--   TODO while <tt>Unboxed</tt> is, in princile, <tt>Hashable</tt>, we'd
--   need the corresponding <tt>VU.Vector</tt> instances ...
--   
--   TODO rename to Dense.Vector, since there are other possibilities to
--   store, without basing on vector.
module Data.PrimitiveArray.Dense
data Dense v sh e
Dense :: !LimitType sh -> !v e -> Dense v sh e
[_denseLimit] :: Dense v sh e -> !LimitType sh
[_denseV] :: Dense v sh e -> !v e
denseV :: forall k_awt9 (v_awt1 :: k_awt9 -> Type) sh_awt2 (e_awt3 :: k_awt9) k_awu9 (v_awu7 :: k_awu9 -> Type) (e_awu8 :: k_awu9). Lens (Dense (v_awt1 :: k_awt9 -> Type) sh_awt2 (e_awt3 :: k_awt9)) (Dense (v_awu7 :: k_awu9 -> Type) sh_awt2 (e_awu8 :: k_awu9)) (v_awt1 e_awt3) (v_awu7 e_awu8)
denseLimit :: forall k_awt9 (v_awt1 :: k_awt9 -> Type) sh_awt2 (e_awt3 :: k_awt9) sh_awu6. Lens (Dense (v_awt1 :: k_awt9 -> Type) sh_awt2 (e_awt3 :: k_awt9)) (Dense (v_awt1 :: k_awt9 -> Type) sh_awu6 (e_awt3 :: k_awt9)) (LimitType sh_awt2) (LimitType sh_awu6)
type Unboxed sh e = Dense Vector sh e
type Storable sh e = Dense Vector sh e
type Boxed sh e = Dense Vector sh e
instance GHC.Generics.Generic (Data.PrimitiveArray.Class.MutArr m (Data.PrimitiveArray.Dense.Dense v sh e))
instance forall k sh (v :: k -> *) (e :: k). (GHC.Classes.Eq (Data.PrimitiveArray.Index.Class.LimitType sh), GHC.Classes.Eq (v e)) => GHC.Classes.Eq (Data.PrimitiveArray.Dense.Dense v sh e)
instance forall k sh (v :: k -> *) (e :: k). (GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType sh), GHC.Generics.Generic (v e)) => GHC.Generics.Generic (Data.PrimitiveArray.Dense.Dense v sh e)
instance forall k sh (v :: k -> *) (e :: k). (GHC.Read.Read (Data.PrimitiveArray.Index.Class.LimitType sh), GHC.Read.Read (v e)) => GHC.Read.Read (Data.PrimitiveArray.Dense.Dense v sh e)
instance forall k sh (v :: k -> *) (e :: k). (GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType sh), GHC.Show.Show (v e)) => GHC.Show.Show (Data.PrimitiveArray.Dense.Dense v sh e)
instance GHC.Base.Functor v => GHC.Base.Functor (Data.PrimitiveArray.Dense.Dense v sh)
instance (Data.Data.Data (v e), Data.Data.Data (Data.PrimitiveArray.Index.Class.LimitType sh), Data.Data.Data e, Data.Data.Data sh, Data.Typeable.Internal.Typeable sh, Data.Typeable.Internal.Typeable e, Data.Typeable.Internal.Typeable v) => Data.Data.Data (Data.PrimitiveArray.Dense.Dense v sh e)
instance forall k sh (v :: k -> *) (e :: k). (Data.Binary.Class.Binary (Data.PrimitiveArray.Index.Class.LimitType sh), Data.Binary.Class.Binary (v e), GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType sh), GHC.Generics.Generic (v e)) => Data.Binary.Class.Binary (Data.PrimitiveArray.Dense.Dense v sh e)
instance forall k sh (v :: k -> *) (e :: k). (Data.Serialize.Serialize (Data.PrimitiveArray.Index.Class.LimitType sh), Data.Serialize.Serialize (v e), GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType sh), GHC.Generics.Generic (v e)) => Data.Serialize.Serialize (Data.PrimitiveArray.Dense.Dense v sh e)
instance forall k sh (v :: k -> *) (e :: k). (Data.Aeson.Types.ToJSON.ToJSON (Data.PrimitiveArray.Index.Class.LimitType sh), Data.Aeson.Types.ToJSON.ToJSON (v e), GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType sh), GHC.Generics.Generic (v e)) => Data.Aeson.Types.ToJSON.ToJSON (Data.PrimitiveArray.Dense.Dense v sh e)
instance forall k sh (v :: k -> *) (e :: k). (Data.Aeson.Types.FromJSON.FromJSON (Data.PrimitiveArray.Index.Class.LimitType sh), Data.Aeson.Types.FromJSON.FromJSON (v e), GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType sh), GHC.Generics.Generic (v e)) => Data.Aeson.Types.FromJSON.FromJSON (Data.PrimitiveArray.Dense.Dense v sh e)
instance forall k sh (v :: k -> *) (e :: k). (Data.Hashable.Class.Hashable (Data.PrimitiveArray.Index.Class.LimitType sh), Data.Hashable.Class.Hashable (v e), GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType sh), GHC.Generics.Generic (v e)) => Data.Hashable.Class.Hashable (Data.PrimitiveArray.Dense.Dense v sh e)
instance forall k sh (v :: k -> *) (e :: k). (Control.DeepSeq.NFData (Data.PrimitiveArray.Index.Class.LimitType sh), Control.DeepSeq.NFData (v e)) => Control.DeepSeq.NFData (Data.PrimitiveArray.Dense.Dense v sh e)
instance (GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType sh), GHC.Show.Show (Data.Vector.Generic.Base.Mutable v (Control.Monad.Primitive.PrimState m) e), Data.Vector.Generic.Base.Mutable v (Control.Monad.Primitive.PrimState m) e GHC.Types.~ mv) => GHC.Show.Show (Data.PrimitiveArray.Class.MutArr m (Data.PrimitiveArray.Dense.Dense v sh e))
instance (Control.DeepSeq.NFData (Data.PrimitiveArray.Index.Class.LimitType sh), Control.DeepSeq.NFData (Data.Vector.Generic.Base.Mutable v (Control.Monad.Primitive.PrimState m) e), Data.Vector.Generic.Base.Mutable v (Control.Monad.Primitive.PrimState m) e GHC.Types.~ mv) => Control.DeepSeq.NFData (Data.PrimitiveArray.Class.MutArr m (Data.PrimitiveArray.Dense.Dense v sh e))
instance (Data.PrimitiveArray.Index.Class.Index sh, Data.Vector.Generic.Base.Vector v e) => Data.PrimitiveArray.Class.PrimArrayOps (Data.PrimitiveArray.Dense.Dense v) sh e
instance (Data.PrimitiveArray.Index.Class.Index sh, Data.Vector.Generic.Base.Vector v e, Data.Vector.Generic.Base.Vector v e') => Data.PrimitiveArray.Class.PrimArrayMap (Data.PrimitiveArray.Dense.Dense v) sh e e'

module Data.PrimitiveArray.Index.IOC

-- | Phantom type for <tt>Inside</tt> indices.
data I

-- | Phantom type for <tt>Outside</tt> indices.
data O

-- | Phantom type for <tt>Complement</tt> indices.
data C


-- | A collection of a number of data types and type classes shared by all
--   bitset variants.
module Data.PrimitiveArray.Index.BitSetClasses

-- | Certain sets have an interface, a particular element with special
--   meaning. In this module, certain `<tt>meanings'</tt> are already
--   provided. These include a <tt>First</tt> element and a <tt>Last</tt>
--   element. We phantom-type these to reduce programming overhead.
newtype Boundary boundaryType ioc
Boundary :: Int -> Boundary boundaryType ioc
[getBoundary] :: Boundary boundaryType ioc -> Int

-- | Whenever we can not set the boundary we should have for a set, we use
--   this pattern. All legal boundaries are <tt>&gt;=0</tt>. We also need
--   to set the undefined boundary to <tt>0</tt>, since the
--   <tt>linearIndex</tt> will use this value to add, which for empty sets
--   would reduce to <tt>0 - UndefBoundary === 0</tt>.
pattern UndefBoundary :: Boundary boundaryType ioc
streamUpBndMk :: Monad m => b -> p -> a -> m (a, b)
streamUpBndStep :: forall k1 k2 m p a (boundaryType :: k1) (ioc :: k2). Monad m => p -> Int -> (a, Int) -> m (Step (a, Int) (a :. Boundary boundaryType ioc))
streamDownBndMk :: Monad m => p -> b -> a -> m (a, b)
streamDownBndStep :: forall k1 k2 m p a (boundaryType :: k1) (ioc :: k2). Monad m => Int -> p -> (a, Int) -> m (Step (a, Int) (a :. Boundary boundaryType ioc))

-- | Declare the interface to be the start of a path.
data First

-- | Declare the interface to be the end of a path.
data Last

-- | Declare the interface to match anything.
--   
--   TODO needed? want to use later in ADPfusion
data Any

-- | Successor and Predecessor for sets. Designed as a class to accomodate
--   sets with interfaces and without interfaces with one function.
--   
--   The functions are not written recursively, as we currently only have
--   three cases, and we do not want to "reset" while generating successors
--   and predecessors.
--   
--   Note that sets have a partial order. Within the group of element with
--   the same <tt>popCount</tt>, we use <tt>popPermutation</tt> which has
--   the same stepping order for both, <tt>setSucc</tt> and
--   <tt>setPred</tt>.
class SetPredSucc s

-- | Set successor. The first argument is the lower set limit, the second
--   the upper set limit, the third the current set.
setSucc :: SetPredSucc s => Int -> Int -> s -> Maybe s

-- | Set predecessor. The first argument is the lower set limit, the second
--   the upper set limit, the third the current set.
setPred :: SetPredSucc s => Int -> Int -> s -> Maybe s

-- | Masks are used quite often for different types of bitsets. We liberate
--   them as a type family.
type family Mask s :: *

-- | <tt>Fixed</tt> allows us to fix some or all bits of a bitset, thereby
--   providing <tt>succ/pred</tt> operations which are only partially free.
--   
--   <tt>f = getFixedMask .&amp;. getFixed</tt> are the fixed bits. <tt>n =
--   getFixed .&amp;. complement getFixedMask</tt> are the free bits.
--   <tt>to = complement getFixed</tt> is the to move mask <tt>n' =
--   popShiftR to n</tt> yields the population after the move <tt>p =
--   popPermutation undefined n'</tt> yields the new population permutation
--   <tt>p' = popShiftL to p</tt> yields the population moved back
--   <tt>final = p' .|. f</tt>
data FixedMask t
FixedMask :: Mask t -> !t -> FixedMask t
[getMask] :: FixedMask t -> Mask t
[getFixed] :: FixedMask t -> !t

-- | Assuming a bitset on bits <tt>[0 .. highbit]</tt>, we can apply a mask
--   that stretches out those bits over <tt>[0 .. higherBit]</tt> with
--   <tt>highbit &lt;= higherBit</tt>. Any active interfaces are correctly
--   set as well.
class ApplyMask s
applyMask :: ApplyMask s => Mask s -> s -> s

-- | for <a>Arbitrary</a>
arbitraryBitSetMax :: Int
instance forall k1 k2 (i :: k1) (t :: k2). Data.Vector.Unboxed.Base.Unbox (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)
instance forall k1 k2 (i :: k1) (t :: k2). Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)
instance forall k1 k2 (i :: k1) (t :: k2). Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)
instance forall k1 k2 (i :: k1) (t :: k2). Data.Binary.Class.Binary (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)
instance forall k1 k2 (i :: k1) (t :: k2). Data.Serialize.Serialize (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)
instance forall k1 k2 (i :: k1) (t :: k2). Data.Aeson.Types.ToJSON.ToJSON (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)
instance forall k1 k2 (i :: k1) (t :: k2). Data.Aeson.Types.FromJSON.FromJSON (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)
instance forall k1 k2 (i :: k1) (t :: k2). Data.Hashable.Class.Hashable (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)
instance forall k1 k2 (i :: k1) (t :: k2). Control.DeepSeq.NFData (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)
instance forall k1 k2 (i :: k1) (t :: k2). Data.PrimitiveArray.Index.Class.Index (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)
instance forall k1 z (k2 :: k1). Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.BitSetClasses.Boundary k2 Data.PrimitiveArray.Index.IOC.I)
instance forall k1 (k2 :: k1). Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.BitSetClasses.Boundary k2 Data.PrimitiveArray.Index.IOC.I) => Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.BitSetClasses.Boundary k2 Data.PrimitiveArray.Index.IOC.I)
instance forall k1 (boundaryType :: k1) k2 (ioc :: k2). GHC.Num.Num (Data.PrimitiveArray.Index.BitSetClasses.Boundary boundaryType ioc)
instance forall k1 (boundaryType :: k1) k2 (ioc :: k2). GHC.Generics.Generic (Data.PrimitiveArray.Index.BitSetClasses.Boundary boundaryType ioc)
instance forall k1 (boundaryType :: k1) k2 (ioc :: k2). GHC.Classes.Ord (Data.PrimitiveArray.Index.BitSetClasses.Boundary boundaryType ioc)
instance forall k1 (boundaryType :: k1) k2 (ioc :: k2). GHC.Classes.Eq (Data.PrimitiveArray.Index.BitSetClasses.Boundary boundaryType ioc)
instance forall k1 k2 (i :: k1) (t :: k2). GHC.Show.Show (Data.PrimitiveArray.Index.BitSetClasses.Boundary i t)


-- | The most basic bitset structure. Alone, not particularly useful,
--   because two sets <tt>{u,v},{v',w}</tt> have no way of annotating the
--   connection between the sets. Together with boundaries this yields sets
--   for useful DP algorithms.
module Data.PrimitiveArray.Index.BitSet0

-- | Newtype for a bitset.
--   
--   <tt>Int</tt> integrates better with the rest of the framework. But we
--   should consider moving to <tt>Word</tt>-based indexing, if possible.
newtype BitSet t
BitSet :: Int -> BitSet t
[_bitSet] :: BitSet t -> Int
bitSet :: forall k_aE1p (t_aE1o :: k_aE1p) k_aEof (t_aEoe :: k_aEof). Iso (BitSet (t_aE1o :: k_aE1p)) (BitSet (t_aEoe :: k_aEof)) Int Int
streamUpMk :: Monad m => Int -> Int -> t -> m (t, Maybe (BitSet ioc))
streamUpStep :: Monad m => Int -> Int -> (t, Maybe (BitSet ioc)) -> m (Step (t, Maybe (BitSet ioc)) (t :. BitSet ioc))
streamDownMk :: Monad m => Int -> Int -> t -> m (t, Maybe (BitSet ioc))
streamDownStep :: Monad m => Int -> Int -> (t, Maybe (BitSet ioc)) -> m (Step (t, Maybe (BitSet ioc)) (t :. BitSet ioc))
instance forall k (t :: k). Data.Vector.Unboxed.Base.Unbox (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). GHC.Show.Show (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Control.DeepSeq.NFData (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.PrimitiveArray.Index.Class.Index (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.PrimitiveArray.Index.BitSetClasses.SetPredSucc (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.BitSet0.BitSet Data.PrimitiveArray.Index.IOC.I)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.BitSet0.BitSet Data.PrimitiveArray.Index.IOC.O)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.BitSet0.BitSet Data.PrimitiveArray.Index.IOC.C)
instance forall k (t :: k). Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.BitSet0.BitSet t) => Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Test.QuickCheck.Arbitrary.Arbitrary (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Aeson.Types.FromJSON.FromJSON (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Aeson.Types.FromJSON.FromJSONKey (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Aeson.Types.ToJSON.ToJSON (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Aeson.Types.ToJSON.ToJSONKey (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Binary.Class.Binary (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Serialize.Serialize (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Hashable.Class.Hashable (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Bits.Bits (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). GHC.Num.Num (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Bits.Extras.Ranked (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). Data.Bits.FiniteBits (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). GHC.Classes.Ord (Data.PrimitiveArray.Index.BitSet0.BitSet t)
instance forall k (t :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.BitSet0.BitSet t)


-- | A bitset with one interface. This includes the often-encountered case
--   where <tt>{u,v},{v}</tt>, or sets with a single edge between the old
--   set and a new singleton set are required. Uses are Hamiltonian path
--   problems, and TSP, among others.
module Data.PrimitiveArray.Index.BitSet1

-- | The bitset with one interface or boundary.
data BitSet1 i ioc
BitSet1 :: !BitSet ioc -> !Boundary i ioc -> BitSet1 i ioc
[_bitset] :: BitSet1 i ioc -> !BitSet ioc
[_boundary] :: BitSet1 i ioc -> !Boundary i ioc
boundary :: forall k_aIjT (i_aIjM :: k_aIjT) k_aIjU (ioc_aIjN :: k_aIjU) k_aIqh (i_aIqg :: k_aIqh). Lens (BitSet1 (i_aIjM :: k_aIjT) (ioc_aIjN :: k_aIjU)) (BitSet1 (i_aIqg :: k_aIqh) (ioc_aIjN :: k_aIjU)) (Boundary i_aIjM ioc_aIjN) (Boundary i_aIqg ioc_aIjN)
bitset :: forall k_aIjT (i_aIjM :: k_aIjT) k_aIjU (ioc_aIjN :: k_aIjU). Lens' (BitSet1 (i_aIjM :: k_aIjT) (ioc_aIjN :: k_aIjU)) (BitSet ioc_aIjN)
streamUpMk :: Monad m => Int -> Int -> z -> m (z, Maybe (BitSet1 c ioc))
streamUpStep :: Monad m => Int -> Int -> (t, Maybe (BitSet1 c ioc)) -> m (Step (t, Maybe (BitSet1 c ioc)) (t :. BitSet1 c ioc))
streamDownMk :: Monad m => Int -> Int -> z -> m (z, Maybe (BitSet1 c ioc))
streamDownStep :: Monad m => Int -> Int -> (t, Maybe (BitSet1 c ioc)) -> m (Step (t, Maybe (BitSet1 c ioc)) (t :. BitSet1 c ioc))
instance forall k1 k2 (bnd :: k1) (ioc :: k2). GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.BitSet1.BitSet1 bnd ioc))
instance forall k1 k2 (i :: k1) (ioc :: k2). Data.Vector.Unboxed.Base.Unbox (Data.PrimitiveArray.Index.BitSet1.BitSet1 i ioc)
instance forall k1 k2 (i :: k1) (ioc :: k2). Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.PrimitiveArray.Index.BitSet1.BitSet1 i ioc)
instance forall k1 k2 (i :: k1) (ioc :: k2). Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.PrimitiveArray.Index.BitSet1.BitSet1 i ioc)
instance forall k1 k2 (bnd :: k1) (ioc :: k2). Data.PrimitiveArray.Index.Class.Index (Data.PrimitiveArray.Index.BitSet1.BitSet1 bnd ioc)
instance forall k z (i :: k). Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.BitSet1.BitSet1 i Data.PrimitiveArray.Index.IOC.I)
instance forall k z (i :: k). Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.BitSet1.BitSet1 i Data.PrimitiveArray.Index.IOC.O)
instance forall k1 k2 (i :: k1) (t :: k2). Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.BitSet1.BitSet1 i t) => Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.BitSet1.BitSet1 i t)
instance forall k1 k2 (t :: k1) (ioc :: k2). Data.PrimitiveArray.Index.BitSetClasses.SetPredSucc (Data.PrimitiveArray.Index.BitSet1.BitSet1 t ioc)
instance forall k1 k2 (t :: k1) (ioc :: k2). Data.PrimitiveArray.Index.BitSetClasses.SetPredSucc (Data.PrimitiveArray.Index.BitSetClasses.FixedMask (Data.PrimitiveArray.Index.BitSet1.BitSet1 t ioc))
instance forall k1 k2 (t :: k1) (ioc :: k2). Test.QuickCheck.Arbitrary.Arbitrary (Data.PrimitiveArray.Index.BitSet1.BitSet1 t ioc)
instance forall k1 (i :: k1) k2 (ioc :: k2). GHC.Show.Show (Data.PrimitiveArray.Index.BitSet1.BitSet1 i ioc)
instance forall k1 (i :: k1) k2 (ioc :: k2). GHC.Generics.Generic (Data.PrimitiveArray.Index.BitSet1.BitSet1 i ioc)
instance forall k1 (i :: k1) k2 (ioc :: k2). GHC.Classes.Ord (Data.PrimitiveArray.Index.BitSet1.BitSet1 i ioc)
instance forall k1 (i :: k1) k2 (ioc :: k2). GHC.Classes.Eq (Data.PrimitiveArray.Index.BitSet1.BitSet1 i ioc)

module Data.PrimitiveArray.Index.Int
instance GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType GHC.Types.Int)
instance Data.PrimitiveArray.Index.Class.Index GHC.Types.Int
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. GHC.Types.Int)
instance Data.PrimitiveArray.Index.Class.IndexStream GHC.Types.Int


-- | A linear 0-based int-index with a phantom type.
module Data.PrimitiveArray.Index.PhantomInt

-- | A <a>PInt</a> behaves exactly like an <tt>Int</tt>, but has an
--   attached phantom type <tt>p</tt>. In particular, the <tt>Index</tt>
--   and <tt>IndexStream</tt> instances are the same as for raw
--   <tt>Int</tt>s.
newtype PInt (ioc :: k) (p :: k)
PInt :: Int -> PInt (ioc :: k) (p :: k)
[getPInt] :: PInt (ioc :: k) (p :: k) -> Int
pIntI :: Int -> PInt I p
pIntO :: Int -> PInt O p
pIntC :: Int -> PInt C p
streamUpMk :: Monad m => b -> p -> a -> m (a, b)
streamUpStep :: forall k m p1 a (ioc :: k) (p2 :: k). Monad m => p1 -> Int -> (a, Int) -> m (Step (a, Int) (a :. PInt ioc p2))
streamDownMk :: Monad m => p -> b -> a -> m (a, b)
streamDownStep :: forall k m p1 a (ioc :: k) (p2 :: k). Monad m => Int -> p1 -> (a, Int) -> m (Step (a, Int) (a :. PInt ioc p2))
instance forall k (t :: k) (p :: k). GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.PhantomInt.PInt t p))
instance forall k (t :: k) (p :: k). GHC.Read.Read (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.PhantomInt.PInt t p))
instance forall k (t :: k) (p :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.PhantomInt.PInt t p))
instance forall k (t :: k) (p :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.PhantomInt.PInt t p))
instance forall k (t :: k) (p :: k). Data.Vector.Unboxed.Base.Unbox (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Data.Binary.Class.Binary (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Data.Serialize.Serialize (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Data.Aeson.Types.FromJSON.FromJSON (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Data.Aeson.Types.FromJSON.FromJSONKey (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Data.Aeson.Types.ToJSON.ToJSON (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Data.Aeson.Types.ToJSON.ToJSONKey (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Data.Hashable.Class.Hashable (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Control.DeepSeq.NFData (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance forall k (t :: k) (p :: k). Data.PrimitiveArray.Index.Class.Index (Data.PrimitiveArray.Index.PhantomInt.PInt t p)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.PhantomInt.PInt Data.PrimitiveArray.Index.IOC.I p)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.PhantomInt.PInt Data.PrimitiveArray.Index.IOC.O p)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.PhantomInt.PInt Data.PrimitiveArray.Index.IOC.C p)
instance forall k (ioc :: k) (p :: k). Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.PhantomInt.PInt ioc p) => Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). GHC.Real.Integral (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). GHC.Enum.Enum (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). GHC.Num.Num (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). GHC.Real.Real (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). GHC.Ix.Ix (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). (Data.Typeable.Internal.Typeable ioc, Data.Typeable.Internal.Typeable p, Data.Typeable.Internal.Typeable k) => Data.Data.Data (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). GHC.Classes.Ord (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). GHC.Show.Show (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)
instance forall k (ioc :: k) (p :: k). GHC.Read.Read (Data.PrimitiveArray.Index.PhantomInt.PInt ioc p)


-- | <tt>Point</tt> index structures are used for left- and right-linear
--   grammars. Such grammars have at most one syntactic symbol on each
--   r.h.s. of a rule. The syntactic symbol needs to be in an outermost
--   position.
module Data.PrimitiveArray.Index.Point

-- | A point in a left-linear grammar. The syntactic symbol is in left-most
--   position.
newtype PointL t
PointL :: Int -> PointL t
[fromPointL] :: PointL t -> Int
pointLI :: Int -> PointL I
pointLO :: Int -> PointL O
pointLC :: Int -> PointL C
data SP z
SP :: !z -> !Int# -> SP z
streamUpMk :: Monad m => Int -> z -> m (SP z)
streamUpStep :: Monad m => (Int -> b) -> Int -> SP z -> m (Step (SP z) (z :. b))
streamDownMk :: Monad m => Int -> z -> m (SP z)
streamDownStep :: Monad m => (Int -> b) -> Int -> SP z -> m (Step (SP z) (z :. b))

-- | A point in a right-linear grammars.
newtype PointR t
PointR :: Int -> PointR t
[fromPointR] :: PointR t -> Int
arbMaxPointR :: Int
instance forall k (t :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Point.PointR t))
instance forall k (t :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Point.PointR t))
instance forall k (t :: k). GHC.Read.Read (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Point.PointR t))
instance forall k (t :: k). GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Point.PointR t))
instance forall k (t :: k). Data.Vector.Unboxed.Base.Unbox (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Data.Binary.Class.Binary (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Data.Serialize.Serialize (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Data.Aeson.Types.FromJSON.FromJSON (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Data.Aeson.Types.FromJSON.FromJSONKey (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Data.Aeson.Types.ToJSON.ToJSON (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Data.Aeson.Types.ToJSON.ToJSONKey (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Data.Hashable.Class.Hashable (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Control.DeepSeq.NFData (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Data.PrimitiveArray.Index.Class.Index (Data.PrimitiveArray.Index.Point.PointR t)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Point.PointR Data.PrimitiveArray.Index.IOC.I)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Point.PointR Data.PrimitiveArray.Index.IOC.O)
instance forall k (t :: k). Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Point.PointR t) => Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). Test.QuickCheck.Arbitrary.Arbitrary (Data.PrimitiveArray.Index.Point.PointR t)
instance Data.PrimitiveArray.Index.Class.SparseBucket (Data.PrimitiveArray.Index.Point.PointL Data.PrimitiveArray.Index.IOC.I)
instance Data.PrimitiveArray.Index.Class.SparseBucket (Data.PrimitiveArray.Index.Point.PointL Data.PrimitiveArray.Index.IOC.O)
instance forall k (t :: k). GHC.Num.Num (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). GHC.Show.Show (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). GHC.Read.Read (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). GHC.Classes.Ord (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.Point.PointR t)
instance forall k (t :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Point.PointL t))
instance forall k (t :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Point.PointL t))
instance forall k (t :: k). GHC.Read.Read (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Point.PointL t))
instance forall k (t :: k). GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Point.PointL t))
instance forall k (t :: k). Data.Vector.Unboxed.Base.Unbox (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Data.Binary.Class.Binary (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Data.Serialize.Serialize (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Data.Aeson.Types.FromJSON.FromJSON (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Data.Aeson.Types.FromJSON.FromJSONKey (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Data.Aeson.Types.ToJSON.ToJSON (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Data.Aeson.Types.ToJSON.ToJSONKey (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Data.Hashable.Class.Hashable (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Control.DeepSeq.NFData (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Data.PrimitiveArray.Index.Class.Index (Data.PrimitiveArray.Index.Point.PointL t)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Point.PointL Data.PrimitiveArray.Index.IOC.I)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Point.PointL Data.PrimitiveArray.Index.IOC.O)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Point.PointL Data.PrimitiveArray.Index.IOC.C)
instance forall k (t :: k). Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Point.PointL t) => Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). Test.QuickCheck.Arbitrary.Arbitrary (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (m :: * -> *) (t :: k). GHC.Base.Monad m => Test.SmallCheck.Series.Serial m (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). GHC.Num.Num (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). GHC.Show.Show (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). GHC.Read.Read (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). GHC.Classes.Ord (Data.PrimitiveArray.Index.Point.PointL t)
instance forall k (t :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.Point.PointL t)


-- | Index structure for context-free grammars on strings. A
--   <tt>Subword</tt> captures a pair <tt>(i,j)</tt> with <tt>i&lt;=j</tt>.
module Data.PrimitiveArray.Index.Subword

-- | A subword wraps a pair of <tt>Int</tt> indices <tt>i,j</tt> with
--   <tt>i&lt;=j</tt>.
--   
--   Subwords always yield the upper-triangular part of a rect-angular
--   array. This gives the quite curious effect that <tt>(0,N)</tt> points
--   to the `<tt>largest'</tt> index, while <tt>(0,0) ... (1,1) ... (k,k)
--   ... (N,N)</tt> point to the smallest. We do, however, use (0,0) as the
--   smallest as (0,k) gives successively smaller upper triangular parts.
newtype Subword t
Subword :: (Int :. Int) -> Subword t
[fromSubword] :: Subword t -> Int :. Int
fromSubwordFst :: Subword t -> Int
fromSubwordSnd :: Subword t -> Int

-- | Create a <tt>Subword t</tt> where <tt>t</tt> is inferred.
subword :: Int -> Int -> Subword t
subwordI :: Int -> Int -> Subword I
subwordO :: Int -> Int -> Subword O
subwordC :: Int -> Int -> Subword C

-- | generic <tt>mk</tt> for <tt>streamUp</tt> / <tt>streamDown</tt>
streamUpMk :: Monad m => c -> a -> m (a, c, c)
streamUpStep :: forall k m a (t :: k). Monad m => Int -> Int -> (a, Int, Int) -> m (Step (a, Int, Int) (a :. Subword t))
streamDownMk :: Monad m => b -> c -> a -> m (a, b, c)
streamDownStep :: forall k m a (t :: k). Monad m => Int -> (a, Int, Int) -> m (Step (a, Int, Int) (a :. Subword t))
instance forall k (t :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Subword.Subword t))
instance forall k (t :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Subword.Subword t))
instance forall k (t :: k). GHC.Read.Read (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Subword.Subword t))
instance forall k (t :: k). GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Subword.Subword t))
instance forall k (t :: k). Data.Vector.Unboxed.Base.Unbox (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Data.Binary.Class.Binary (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Data.Serialize.Serialize (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Data.Aeson.Types.FromJSON.FromJSON (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Data.Aeson.Types.FromJSON.FromJSONKey (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Data.Aeson.Types.ToJSON.ToJSON (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Data.Aeson.Types.ToJSON.ToJSONKey (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Data.Hashable.Class.Hashable (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Control.DeepSeq.NFData (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Data.PrimitiveArray.Index.Class.Index (Data.PrimitiveArray.Index.Subword.Subword t)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Subword.Subword Data.PrimitiveArray.Index.IOC.I)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Subword.Subword Data.PrimitiveArray.Index.IOC.O)
instance Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Subword.Subword Data.PrimitiveArray.Index.IOC.C)
instance forall k (t :: k). Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Subword.Subword t) => Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). Test.QuickCheck.Arbitrary.Arbitrary (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (m :: * -> *) (t :: k). GHC.Base.Monad m => Test.SmallCheck.Series.Serial m (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). GHC.Read.Read (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). GHC.Show.Show (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). GHC.Classes.Ord (Data.PrimitiveArray.Index.Subword.Subword t)
instance forall k (t :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.Subword.Subword t)


-- | Unit indices admit a single element to be memoized. We can't use
--   <tt>()</tt> because we want to attach phantom types.
module Data.PrimitiveArray.Index.Unit
data Unit t
Unit :: Unit t
instance forall k (t :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Unit.Unit t))
instance forall k (t :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Unit.Unit t))
instance forall k (t :: k). GHC.Read.Read (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Unit.Unit t))
instance forall k (t :: k). GHC.Show.Show (Data.PrimitiveArray.Index.Class.LimitType (Data.PrimitiveArray.Index.Unit.Unit t))
instance forall k (t :: k). Data.Vector.Unboxed.Base.Unbox (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.Binary.Class.Binary (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.Serialize.Serialize (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.Aeson.Types.FromJSON.FromJSON (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.Aeson.Types.FromJSON.FromJSONKey (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.Aeson.Types.ToJSON.ToJSON (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.Aeson.Types.ToJSON.ToJSONKey (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.Hashable.Class.Hashable (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Control.DeepSeq.NFData (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.PrimitiveArray.Index.Class.Index (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k z (t :: k). Data.PrimitiveArray.Index.Class.IndexStream z => Data.PrimitiveArray.Index.Class.IndexStream (z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Class.Z Data.PrimitiveArray.Index.Class.:. Data.PrimitiveArray.Index.Unit.Unit t) => Data.PrimitiveArray.Index.Class.IndexStream (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). Test.QuickCheck.Arbitrary.Arbitrary (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). GHC.Read.Read (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). GHC.Generics.Generic (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). GHC.Show.Show (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). GHC.Classes.Ord (Data.PrimitiveArray.Index.Unit.Unit t)
instance forall k (t :: k). GHC.Classes.Eq (Data.PrimitiveArray.Index.Unit.Unit t)

module Data.PrimitiveArray.Index
data family Vector a
data family MVector s a

-- | Data structure encoding the upper limit for each array.
data family LimitType i :: *

-- | Newtype for a bitset.
--   
--   <tt>Int</tt> integrates better with the rest of the framework. But we
--   should consider moving to <tt>Word</tt>-based indexing, if possible.
newtype BitSet t
BitSet :: Int -> BitSet t
[_bitSet] :: BitSet t -> Int
bitSet :: forall k_aE1p (t_aE1o :: k_aE1p) k_aEof (t_aEoe :: k_aEof). Iso (BitSet (t_aE1o :: k_aE1p)) (BitSet (t_aEoe :: k_aEof)) Int Int
data family Vector a
data family MVector s a

-- | Data structure encoding the upper limit for each array.
data family LimitType i :: *

-- | The bitset with one interface or boundary.
data BitSet1 i ioc
BitSet1 :: !BitSet ioc -> !Boundary i ioc -> BitSet1 i ioc
[_bitset] :: BitSet1 i ioc -> !BitSet ioc
[_boundary] :: BitSet1 i ioc -> !Boundary i ioc
bitset :: forall k_aIjT (i_aIjM :: k_aIjT) k_aIjU (ioc_aIjN :: k_aIjU). Lens' (BitSet1 (i_aIjM :: k_aIjT) (ioc_aIjN :: k_aIjU)) (BitSet ioc_aIjN)
boundary :: forall k_aIjT (i_aIjM :: k_aIjT) k_aIjU (ioc_aIjN :: k_aIjU) k_aIqh (i_aIqg :: k_aIqh). Lens (BitSet1 (i_aIjM :: k_aIjT) (ioc_aIjN :: k_aIjU)) (BitSet1 (i_aIqg :: k_aIqh) (ioc_aIjN :: k_aIjU)) (Boundary i_aIjM ioc_aIjN) (Boundary i_aIqg ioc_aIjN)
data family Vector a
data family MVector s a

-- | Data structure encoding the upper limit for each array.
data family LimitType i :: *

-- | A <a>PInt</a> behaves exactly like an <tt>Int</tt>, but has an
--   attached phantom type <tt>p</tt>. In particular, the <tt>Index</tt>
--   and <tt>IndexStream</tt> instances are the same as for raw
--   <tt>Int</tt>s.
newtype PInt (ioc :: k) (p :: k)
PInt :: Int -> PInt (ioc :: k) (p :: k)
[getPInt] :: PInt (ioc :: k) (p :: k) -> Int
pIntI :: Int -> PInt I p
pIntO :: Int -> PInt O p
pIntC :: Int -> PInt C p
data family Vector a
data family MVector s a

-- | Data structure encoding the upper limit for each array.
data family LimitType i :: *

-- | A point in a left-linear grammar. The syntactic symbol is in left-most
--   position.
newtype PointL t
PointL :: Int -> PointL t
[fromPointL] :: PointL t -> Int
pointLI :: Int -> PointL I
pointLO :: Int -> PointL O
pointLC :: Int -> PointL C

-- | A point in a right-linear grammars.
newtype PointR t
PointR :: Int -> PointR t
[fromPointR] :: PointR t -> Int
data SP z
SP :: !z -> !Int# -> SP z
arbMaxPointR :: Int
data family Vector a
data family MVector s a

-- | Data structure encoding the upper limit for each array.
data family LimitType i :: *

-- | A subword wraps a pair of <tt>Int</tt> indices <tt>i,j</tt> with
--   <tt>i&lt;=j</tt>.
--   
--   Subwords always yield the upper-triangular part of a rect-angular
--   array. This gives the quite curious effect that <tt>(0,N)</tt> points
--   to the `<tt>largest'</tt> index, while <tt>(0,0) ... (1,1) ... (k,k)
--   ... (N,N)</tt> point to the smallest. We do, however, use (0,0) as the
--   smallest as (0,k) gives successively smaller upper triangular parts.
newtype Subword t
Subword :: (Int :. Int) -> Subword t
[fromSubword] :: Subword t -> Int :. Int
fromSubwordFst :: Subword t -> Int
fromSubwordSnd :: Subword t -> Int

-- | Create a <tt>Subword t</tt> where <tt>t</tt> is inferred.
subword :: Int -> Int -> Subword t
subwordI :: Int -> Int -> Subword I
subwordO :: Int -> Int -> Subword O
subwordC :: Int -> Int -> Subword C

module Data.PrimitiveArray


-- | This module exports everything that <tt>Data.PrimitiveArray</tt>
--   exports, but it will do some bounds-checking on certain operations.
--   
--   Checked are: <tt>(!)</tt>
module Data.PrimitiveArray.Checked
data family Vector a
data family MVector s a

-- | Strict pairs -- as in <tt>repa</tt>.
data a :. b
(:.) :: !a -> !b -> (:.) a b
infixl 3 :.
infixl 3 :.

-- | A different version of strict pairs. Makes for simpler type inference
--   in multi-tape grammars. We use <tt>:&gt;</tt> when we have special
--   needs, like non-recursive instances on inductives tuples, as used for
--   set indices.
--   
--   This one is <tt>infixr</tt> so that in <tt>a :&gt; b</tt> we can have
--   the main type in <tt>a</tt> and the specializing types in <tt>b</tt>
--   and then dispatch on <tt>a :&gt; ts</tt> with <tt>ts</tt> maybe a
--   chain of <tt>:&gt;</tt>.
data a :> b
(:>) :: !a -> !b -> (:>) a b
infixr 3 :>
infixr 3 :>

-- | Base data constructor for multi-dimensional indices.
data Z
Z :: Z

-- | <tt>manhattan</tt> turns an index <tt>sh</tt> into a starting point
--   within <tt>sparseIndices</tt> of the <tt>Sparse</tt> data structure.
--   This should reduce the time required to search <tt>sparseIndices</tt>,
--   because <tt>manhattanStart[manhattan sh]</tt> yields a left bound,
--   while <tt>manhattanStart[manhattan sh +1]</tt> will yield an excluded
--   right bound.
--   
--   Uses the <tt>Manhattan</tt> distance.
--   
--   TODO This should probably be moved into the <tt>Index</tt> module.
class SparseBucket sh

-- | The manhattan distance for an index.
manhattan :: SparseBucket sh => LimitType sh -> sh -> Int

-- | The maximal possible manhattan distance.
manhattanMax :: SparseBucket sh => LimitType sh -> Int

-- | Generate a stream of indices in correct order for dynamic programming.
--   Since the stream generators require <tt>concatMap</tt> /
--   <tt>flatten</tt> we have to write more specialized code for
--   <tt>(z:.IX)</tt> stuff.
class (Index i) => IndexStream i

-- | Generate an index stream using <a>LimitType</a>s. This prevents having
--   to figure out how the actual limits for complicated index types (like
--   <tt>Set</tt>) would look like, since for <tt>Set</tt>, for example,
--   the <tt>LimitType Set == Int</tt> provides just the number of bits.
--   
--   This generates an index stream suitable for <tt>forward</tt> structure
--   filling. The first index is the smallest (or the first indices
--   considered are all equally small in partially ordered sets). Larger
--   indices follow up until the largest one.
streamUp :: (IndexStream i, Monad m) => LimitType i -> LimitType i -> Stream m i

-- | If <a>streamUp</a> generates indices from smallest to largest, then
--   <a>streamDown</a> generates indices from largest to smallest. Outside
--   grammars make implicit use of this. Asking for an axiom in
--   backtracking requests the first element from this stream.
streamDown :: (IndexStream i, Monad m) => LimitType i -> LimitType i -> Stream m i

-- | The total number of cells that are allocated.
newtype CellSize
CellSize :: Word -> CellSize

-- | In case <tt>totalSize</tt> or variants thereof produce a size that is
--   too big to handle.
newtype SizeError
SizeError :: String -> SizeError

-- | Index structures for complex, heterogeneous indexing. Mostly designed
--   for indexing in DP grammars, where the indices work for linear and
--   context-free grammars on one or more tapes, for strings, sets, later
--   on tree structures.
class Index i where {
    
    -- | Data structure encoding the upper limit for each array.
    data family LimitType i :: *;
}

-- | Given a maximal size, and a current index, calculate the linear index.
linearIndex :: Index i => LimitType i -> i -> Int

-- | Given a maximal size and a valid <tt>Int</tt>, return the index.
fromLinearIndex :: Index i => LimitType i -> Int -> i

-- | Given the <a>LimitType</a>, return the number of cells required for
--   storage.
size :: Index i => LimitType i -> Int

-- | Check if an index is within the bounds.
inBounds :: Index i => LimitType i -> i -> Bool

-- | A lower bound of <tt>zero</tt>
zeroBound :: Index i => i

-- | A lower bound of <tt>zero</tt> but for a <tt>LimitType i</tt>.
zeroBound' :: Index i => LimitType i

-- | The list of cell sizes for each dimension. its product yields the
--   total size.
totalSize :: Index i => LimitType i -> [Integer]

-- | Pretty-print all upper bounds
showBound :: Index i => LimitType i -> [String]

-- | Pretty-print all indices
showIndex :: Index i => i -> [String]

-- | Given the maximal number of cells (<tt>Word</tt>, because this is the
--   pointer limit for the machine), and the list of sizes, will check if
--   this is still legal. Consider dividing the <tt>Word</tt> by the actual
--   memory requirements for each cell, to get better exception handling
--   for too large arrays.
--   
--   One list should be given for each array.
sizeIsValid :: Monad m => Word -> [[Integer]] -> ExceptT SizeError m CellSize

-- | Sum type of errors that can happen when using primitive arrays.
data PAErrors
PAEUpperBound :: PAErrors
class PrimArrayMap arr sh e e'
mapArray :: PrimArrayMap arr sh e e' => (e -> e') -> arr sh e -> arr sh e'

-- | The core set of operations for pure and monadic arrays.
class (Index sh) => PrimArrayOps arr sh elm

-- | Returns the bounds of an immutable array, again inclusive bounds: <tt>
--   [lb..ub] </tt>.
upperBound :: PrimArrayOps arr sh elm => arr sh elm -> LimitType sh

-- | Extract a single element from the array. Generally unsafe as not
--   bounds-checking is performed.
unsafeIndex :: PrimArrayOps arr sh elm => arr sh elm -> sh -> elm

-- | Index into immutable array, but safe in case <tt>sh</tt> is not part
--   of the array.
safeIndex :: PrimArrayOps arr sh elm => arr sh elm -> sh -> Maybe elm

-- | Savely transform the shape space of a table.
transformShape :: (PrimArrayOps arr sh elm, Index sh') => (LimitType sh -> LimitType sh') -> arr sh elm -> arr sh' elm

-- | Return the bounds of the array. All bounds are inclusive, as in
--   <tt>[lb..ub]</tt>. Technically not monadic, but rather working on a
--   monadic array.
upperBoundM :: PrimArrayOps arr sh elm => MutArr m (arr sh elm) -> LimitType sh

-- | Given lower and upper bounds and a list of <i>all</i> elements,
--   produce a mutable array.
fromListM :: (PrimArrayOps arr sh elm, PrimMonad m) => LimitType sh -> [elm] -> m (MutArr m (arr sh elm))

-- | Creates a new array with the given bounds with each element within the
--   array being in an undefined state.
newM :: (PrimArrayOps arr sh elm, PrimMonad m) => LimitType sh -> m (MutArr m (arr sh elm))

-- | Variant of <a>newM</a> that requires a fill structure. Mostly for
--   special / sparse structures (hence the <tt>S</tt>, also to be
--   interpreted as "safe", since these functions won't fail with sparse
--   structures).
newSM :: (PrimArrayOps arr sh elm, Monad m, PrimMonad m) => LimitType sh -> FillStruc (arr sh elm) -> m (MutArr m (arr sh elm))

-- | Creates a new array with all elements being equal to <tt>elm</tt>.
newWithM :: (PrimArrayOps arr sh elm, PrimMonad m) => LimitType sh -> elm -> m (MutArr m (arr sh elm))

-- | Variant of <a>newWithM</a>
newWithSM :: (PrimArrayOps arr sh elm, Monad m, PrimMonad m) => LimitType sh -> FillStruc (arr sh elm) -> elm -> m (MutArr m (arr sh elm))

-- | Reads a single element in the array.
readM :: (PrimArrayOps arr sh elm, PrimMonad m) => MutArr m (arr sh elm) -> sh -> m elm

-- | Read from the mutable array, but return <tt>Nothing</tt> in case
--   <tt>sh</tt> does not exist. This will allow streaming DP combinators
--   to "jump" over missing elements.
--   
--   Should be used with <tt>Stream.Monadic.mapMaybe</tt> to get efficient
--   code.
safeReadM :: (PrimArrayOps arr sh elm, Monad m, PrimMonad m) => MutArr m (arr sh elm) -> sh -> m (Maybe elm)

-- | Writes a single element in the array.
writeM :: (PrimArrayOps arr sh elm, PrimMonad m) => MutArr m (arr sh elm) -> sh -> elm -> m ()

-- | Write into the mutable array, but if the index <tt>sh</tt> does not
--   exist, silently continue.
safeWriteM :: (PrimArrayOps arr sh elm, Monad m, PrimMonad m) => MutArr m (arr sh elm) -> sh -> elm -> m ()

-- | Freezes a mutable array an returns its immutable version. This
--   operation is <i>O(1)</i> and both arrays share the same memory. Do not
--   use the mutable array afterwards.
unsafeFreezeM :: (PrimArrayOps arr sh elm, PrimMonad m) => MutArr m (arr sh elm) -> m (arr sh elm)

-- | Thaw an immutable array into a mutable one. Both versions share
--   memory.
unsafeThawM :: (PrimArrayOps arr sh elm, PrimMonad m) => arr sh elm -> m (MutArr m (arr sh elm))

-- | Associate a fill structure with each type of array (dense, sparse,
--   ...).
--   
--   Example: <tt>type instance FillStruc (Sparse w v sh e) = (w sh)</tt>
--   associates the type <tt>(w sh)</tt>, which is of the same type as the
--   underlying <tt>w</tt> structure holding index information for a sparse
--   array.
type family FillStruc arr :: *

-- | Mutable version of an array.
data family MutArr (m :: * -> *) (arr :: *) :: *

-- | Return value at an index that might not exist.
(!?) :: PrimArrayOps arr sh elm => arr sh elm -> sh -> Maybe elm

-- | Returns true if the index is valid for the array.
inBoundsM :: (Monad m, PrimArrayOps arr sh elm) => MutArr m (arr sh elm) -> sh -> Bool

-- | Construct a mutable primitive array from a lower and an upper bound, a
--   default element, and a list of associations.
fromAssocsM :: (PrimMonad m, PrimArrayOps arr sh elm) => LimitType sh -> elm -> [(sh, elm)] -> m (MutArr m (arr sh elm))

-- | Initialize an immutable array but stay within the primitive monad
--   <tt>m</tt>.
newWithPA :: (PrimMonad m, PrimArrayOps arr sh elm) => LimitType sh -> elm -> m (arr sh elm)

-- | Initialize an immutable array with a fill structure.
newWithSPA :: (PrimMonad m, PrimArrayOps arr sh elm) => LimitType sh -> FillStruc (arr sh elm) -> elm -> m (arr sh elm)

-- | Safely prepare a primitive array.
--   
--   TODO Check if having a <a>MonadError</a> instance degrades
--   performance. (We should see this once the test with NeedlemanWunsch is
--   under way).
safeNewWithPA :: forall m arr sh elm. (PrimMonad m, MonadError PAErrors m, PrimArrayOps arr sh elm) => LimitType sh -> elm -> m (arr sh elm)

-- | Return all associations from an array.
assocs :: forall arr sh elm. (IndexStream sh, PrimArrayOps arr sh elm) => arr sh elm -> [(sh, elm)]

-- | Return all associations from an array.
assocsS :: forall m arr sh elm. (Monad m, IndexStream sh, PrimArrayOps arr sh elm) => arr sh elm -> Stream m (sh, elm)

-- | Creates an immutable array from lower and upper bounds and a complete
--   list of elements.
fromList :: PrimArrayOps arr sh elm => LimitType sh -> [elm] -> arr sh elm

-- | Creates an immutable array from lower and upper bounds, a default
--   element, and a list of associations.
fromAssocs :: PrimArrayOps arr sh elm => LimitType sh -> elm -> [(sh, elm)] -> arr sh elm

-- | Returns all elements of an immutable array as a list.
toList :: forall arr sh elm. (IndexStream sh, PrimArrayOps arr sh elm) => arr sh elm -> [elm]
data Dense v sh e
Dense :: !LimitType sh -> !v e -> Dense v sh e
[_denseLimit] :: Dense v sh e -> !LimitType sh
[_denseV] :: Dense v sh e -> !v e
type Boxed sh e = Dense Vector sh e
type Storable sh e = Dense Vector sh e
type Unboxed sh e = Dense Vector sh e
denseLimit :: forall k_awt9 (v_awt1 :: k_awt9 -> Type) sh_awt2 (e_awt3 :: k_awt9) sh_awu6. Lens (Dense (v_awt1 :: k_awt9 -> Type) sh_awt2 (e_awt3 :: k_awt9)) (Dense (v_awt1 :: k_awt9 -> Type) sh_awu6 (e_awt3 :: k_awt9)) (LimitType sh_awt2) (LimitType sh_awu6)
denseV :: forall k_awt9 (v_awt1 :: k_awt9 -> Type) sh_awt2 (e_awt3 :: k_awt9) k_awu9 (v_awu7 :: k_awu9 -> Type) (e_awu8 :: k_awu9). Lens (Dense (v_awt1 :: k_awt9 -> Type) sh_awt2 (e_awt3 :: k_awt9)) (Dense (v_awu7 :: k_awu9 -> Type) sh_awt2 (e_awu8 :: k_awu9)) (v_awt1 e_awt3) (v_awu7 e_awu8)

-- | Phantom type for <tt>Complement</tt> indices.
data C

-- | Phantom type for <tt>Outside</tt> indices.
data O

-- | Phantom type for <tt>Inside</tt> indices.
data I

-- | Certain sets have an interface, a particular element with special
--   meaning. In this module, certain `<tt>meanings'</tt> are already
--   provided. These include a <tt>First</tt> element and a <tt>Last</tt>
--   element. We phantom-type these to reduce programming overhead.
newtype Boundary boundaryType ioc
Boundary :: Int -> Boundary boundaryType ioc
[getBoundary] :: Boundary boundaryType ioc -> Int

-- | Whenever we can not set the boundary we should have for a set, we use
--   this pattern. All legal boundaries are <tt>&gt;=0</tt>. We also need
--   to set the undefined boundary to <tt>0</tt>, since the
--   <tt>linearIndex</tt> will use this value to add, which for empty sets
--   would reduce to <tt>0 - UndefBoundary === 0</tt>.
pattern UndefBoundary :: Boundary boundaryType ioc

-- | Assuming a bitset on bits <tt>[0 .. highbit]</tt>, we can apply a mask
--   that stretches out those bits over <tt>[0 .. higherBit]</tt> with
--   <tt>highbit &lt;= higherBit</tt>. Any active interfaces are correctly
--   set as well.
class ApplyMask s
applyMask :: ApplyMask s => Mask s -> s -> s

-- | <tt>Fixed</tt> allows us to fix some or all bits of a bitset, thereby
--   providing <tt>succ/pred</tt> operations which are only partially free.
--   
--   <tt>f = getFixedMask .&amp;. getFixed</tt> are the fixed bits. <tt>n =
--   getFixed .&amp;. complement getFixedMask</tt> are the free bits.
--   <tt>to = complement getFixed</tt> is the to move mask <tt>n' =
--   popShiftR to n</tt> yields the population after the move <tt>p =
--   popPermutation undefined n'</tt> yields the new population permutation
--   <tt>p' = popShiftL to p</tt> yields the population moved back
--   <tt>final = p' .|. f</tt>
data FixedMask t
FixedMask :: Mask t -> !t -> FixedMask t
[getMask] :: FixedMask t -> Mask t
[getFixed] :: FixedMask t -> !t

-- | Masks are used quite often for different types of bitsets. We liberate
--   them as a type family.
type family Mask s :: *

-- | Successor and Predecessor for sets. Designed as a class to accomodate
--   sets with interfaces and without interfaces with one function.
--   
--   The functions are not written recursively, as we currently only have
--   three cases, and we do not want to "reset" while generating successors
--   and predecessors.
--   
--   Note that sets have a partial order. Within the group of element with
--   the same <tt>popCount</tt>, we use <tt>popPermutation</tt> which has
--   the same stepping order for both, <tt>setSucc</tt> and
--   <tt>setPred</tt>.
class SetPredSucc s

-- | Set successor. The first argument is the lower set limit, the second
--   the upper set limit, the third the current set.
setSucc :: SetPredSucc s => Int -> Int -> s -> Maybe s

-- | Set predecessor. The first argument is the lower set limit, the second
--   the upper set limit, the third the current set.
setPred :: SetPredSucc s => Int -> Int -> s -> Maybe s

-- | Declare the interface to match anything.
--   
--   TODO needed? want to use later in ADPfusion
data Any

-- | Declare the interface to be the end of a path.
data Last

-- | Declare the interface to be the start of a path.
data First
streamUpBndMk :: Monad m => b -> p -> a -> m (a, b)
streamUpBndStep :: forall k1 k2 m p a (boundaryType :: k1) (ioc :: k2). Monad m => p -> Int -> (a, Int) -> m (Step (a, Int) (a :. Boundary boundaryType ioc))
streamDownBndMk :: Monad m => p -> b -> a -> m (a, b)
streamDownBndStep :: forall k1 k2 m p a (boundaryType :: k1) (ioc :: k2). Monad m => Int -> p -> (a, Int) -> m (Step (a, Int) (a :. Boundary boundaryType ioc))

-- | for <a>Arbitrary</a>
arbitraryBitSetMax :: Int

-- | Newtype for a bitset.
--   
--   <tt>Int</tt> integrates better with the rest of the framework. But we
--   should consider moving to <tt>Word</tt>-based indexing, if possible.
newtype BitSet t
BitSet :: Int -> BitSet t
[_bitSet] :: BitSet t -> Int
bitSet :: forall k_aE1p (t_aE1o :: k_aE1p) k_aEof (t_aEoe :: k_aEof). Iso (BitSet (t_aE1o :: k_aE1p)) (BitSet (t_aEoe :: k_aEof)) Int Int

-- | The bitset with one interface or boundary.
data BitSet1 i ioc
BitSet1 :: !BitSet ioc -> !Boundary i ioc -> BitSet1 i ioc
[_bitset] :: BitSet1 i ioc -> !BitSet ioc
[_boundary] :: BitSet1 i ioc -> !Boundary i ioc
bitset :: forall k_aIjT (i_aIjM :: k_aIjT) k_aIjU (ioc_aIjN :: k_aIjU). Lens' (BitSet1 (i_aIjM :: k_aIjT) (ioc_aIjN :: k_aIjU)) (BitSet ioc_aIjN)
boundary :: forall k_aIjT (i_aIjM :: k_aIjT) k_aIjU (ioc_aIjN :: k_aIjU) k_aIqh (i_aIqg :: k_aIqh). Lens (BitSet1 (i_aIjM :: k_aIjT) (ioc_aIjN :: k_aIjU)) (BitSet1 (i_aIqg :: k_aIqh) (ioc_aIjN :: k_aIjU)) (Boundary i_aIjM ioc_aIjN) (Boundary i_aIqg ioc_aIjN)

-- | A <a>PInt</a> behaves exactly like an <tt>Int</tt>, but has an
--   attached phantom type <tt>p</tt>. In particular, the <tt>Index</tt>
--   and <tt>IndexStream</tt> instances are the same as for raw
--   <tt>Int</tt>s.
newtype PInt (ioc :: k) (p :: k)
PInt :: Int -> PInt (ioc :: k) (p :: k)
[getPInt] :: PInt (ioc :: k) (p :: k) -> Int
pIntI :: Int -> PInt I p
pIntO :: Int -> PInt O p
pIntC :: Int -> PInt C p

-- | A point in a left-linear grammar. The syntactic symbol is in left-most
--   position.
newtype PointL t
PointL :: Int -> PointL t
[fromPointL] :: PointL t -> Int
pointLI :: Int -> PointL I
pointLO :: Int -> PointL O
pointLC :: Int -> PointL C

-- | A point in a right-linear grammars.
newtype PointR t
PointR :: Int -> PointR t
[fromPointR] :: PointR t -> Int
data SP z
SP :: !z -> !Int# -> SP z
arbMaxPointR :: Int

-- | A subword wraps a pair of <tt>Int</tt> indices <tt>i,j</tt> with
--   <tt>i&lt;=j</tt>.
--   
--   Subwords always yield the upper-triangular part of a rect-angular
--   array. This gives the quite curious effect that <tt>(0,N)</tt> points
--   to the `<tt>largest'</tt> index, while <tt>(0,0) ... (1,1) ... (k,k)
--   ... (N,N)</tt> point to the smallest. We do, however, use (0,0) as the
--   smallest as (0,k) gives successively smaller upper triangular parts.
newtype Subword t
Subword :: (Int :. Int) -> Subword t
[fromSubword] :: Subword t -> Int :. Int
fromSubwordFst :: Subword t -> Int
fromSubwordSnd :: Subword t -> Int

-- | Create a <tt>Subword t</tt> where <tt>t</tt> is inferred.
subword :: Int -> Int -> Subword t
subwordI :: Int -> Int -> Subword I
subwordO :: Int -> Int -> Subword O
subwordC :: Int -> Int -> Subword C
data Unit t
Unit :: Unit t

-- | Bounds-checked version of indexing.
--   
--   First, we check via <tt>inBounds</tt>, second we check if the linear
--   index is outside of the allocated area.
(!) :: forall (v :: Type -> Type) p sh. (Vector v p, Index sh, Show sh, Show (LimitType sh)) => Dense v sh p -> sh -> p


-- | This solution to holding a sparse set of elements for dynamic
--   programming. The underlying representation requires <tt>O (log n)</tt>
--   access time for each read or write, where <tt>n</tt> is the number of
--   elements to be stored. It uses an experimental "bucketing" system to
--   provide better lower and upper bounds than otherwise possible.
--   
--   TODO <tt>ADPfusion / FillTyLvl</tt> handles actually filling the
--   tables. In case all <tt>BigOrder</tt> tables are dense and of the same
--   dimensional extent, we are fine. However if at least one table is
--   dense, while others are sparse, we will have write to nothing, which
--   should not crash. In case of all-sparse tables for a BigOrder, we have
--   to calculate the union of all indices. This all is currently not
--   happening...
--   
--   TODO require <tt>readMaybe</tt> and <tt>indexMaybe</tt> to return
--   <tt>Nothing</tt> on missing elements. This requires an extension of
--   the <tt>Class</tt> structure for tables.
module Data.PrimitiveArray.Sparse.BinSearch

-- | This is a sparse matrix, where only a subset of indices have data
--   associated.
data Sparse w v sh e
Sparse :: !LimitType sh -> !v e -> !w sh -> !Vector Int -> Sparse w v sh e

-- | The upper bound for the DP matrix. Not the upper bound of indexes in
--   use, but the theoretical upper bound.
[sparseUpperBound] :: Sparse w v sh e -> !LimitType sh

-- | Vector with actually existing data.
[sparseData] :: Sparse w v sh e -> !v e

-- | The index of each <tt>sh</tt> is the same as of the corresponding
--   <tt>sparseData</tt> structure. Indices should be ordered as required
--   by the <tt>streamUp</tt> function, to facilitate filling
--   <tt>Sparse</tt> by going from left to right.
[sparseIndices] :: Sparse w v sh e -> !w sh

-- | Provides left/right boundaries into <tt>sparseIndices</tt> to speed up
--   index search. Should be one larger than the largest index to look up,
--   to always provides a good excluded bound.
[manhattanStart] :: Sparse w v sh e -> !Vector Int
type Unboxed w sh e = Sparse w Vector sh e
type Storable w sh e = Sparse w Vector sh e
type Boxed w sh e = Sparse w Vector sh e

-- | Find the index with manhattan helper
--   
--   TODO consider using binary search instead of a linear scan here! e.g.:
--   <tt>k = VAS.binarySearchByBounds (==)</tt>
--   
--   NOTE running times with 100x100 DP problem <a>NeedlemanWunsch</a> full
--   findIndex of sixs: 0,050,000 cells/sec using manhattan buckets,
--   findIndex: 5,000,000 cells/sec using binarySearch on slices:
--   11,000,000 cells/sec
--   
--   On a 1000x1000 DP NeedlemanWunsch problem, binary search on slices is
--   at 6,500,000 cells/sec.
manhattanIndex :: (SparseBucket sh, Vector v sh, Eq sh, Ord sh) => LimitType sh -> Vector Int -> v sh -> sh -> Maybe Int
binarySearch :: (Eq sh, Ord sh, Vector v sh) => sh -> v sh -> Maybe Int

-- | Given two index vectors of the same shape, will return the correctly
--   ordered vector of the union of indices.
--   
--   TODO This requires that <tt>Ord (Shape O)</tt> uses the <tt>Down</tt>
--   instance of Ord! We need to fix this in the <tt>Index</tt> modules.
--   
--   TODO Rewrite to allow fusion without intermediate vectors using
--   uncons. This will make it possible to chain applications.
--   <tt>stream</tt> should be fine for this.
mergeIndexVectors :: (Eq sh, Ord sh, Vector w sh) => w sh -> w sh -> w sh
instance (Data.PrimitiveArray.Index.Class.Index sh, Data.PrimitiveArray.Index.Class.SparseBucket sh, GHC.Classes.Eq sh, GHC.Classes.Ord sh, Data.Vector.Generic.Base.Vector w sh, Data.Vector.Generic.Base.Vector w (GHC.Types.Int, sh), Data.Vector.Generic.Base.Vector w (GHC.Types.Int, (GHC.Types.Int, sh)), Data.Vector.Generic.Base.Vector v e) => Data.PrimitiveArray.Class.PrimArrayOps (Data.PrimitiveArray.Sparse.BinSearch.Sparse w v) sh e


-- | This solution to holding a sparse set of elements for dynamic
--   programming. The underlying representation requires <tt>O (log n)</tt>
--   access time for each read or write, where <tt>n</tt> is the number of
--   elements to be stored. It uses an experimental "bucketing" system to
--   provide better lower and upper bounds than otherwise possible.
--   
--   TODO <tt>ADPfusion / FillTyLvl</tt> handles actually filling the
--   tables. In case all <tt>BigOrder</tt> tables are dense and of the same
--   dimensional extent, we are fine. However if at least one table is
--   dense, while others are sparse, we will have write to nothing, which
--   should not crash. In case of all-sparse tables for a BigOrder, we have
--   to calculate the union of all indices. This all is currently not
--   happening...
--   
--   This version requires working <tt>fromLinearIndex</tt> but is
--   potentially faster.
module Data.PrimitiveArray.Sparse.IntBinSearch

-- | This is a sparse matrix, where only a subset of indices have data
--   associated.
data Sparse w v sh e
Sparse :: !LimitType sh -> !v e -> !Vector Int -> !Vector Int -> Sparse w v sh e

-- | The upper bound for the DP matrix. Not the upper bound of indexes in
--   use, but the theoretical upper bound.
[sparseUpperBound] :: Sparse w v sh e -> !LimitType sh

-- | Vector with actually existing data.
[sparseData] :: Sparse w v sh e -> !v e

-- | Linearly encoded sparse indices
[sparseIndices] :: Sparse w v sh e -> !Vector Int

-- | Provides left/right boundaries into <tt>sparseIndices</tt> to speed up
--   index search. Should be one larger than the largest index to look up,
--   to always provides a good excluded bound.
[manhattanStart] :: Sparse w v sh e -> !Vector Int
type Unboxed w sh e = Sparse w Vector sh e
type Storable w sh e = Sparse w Vector sh e
type Boxed w sh e = Sparse w Vector sh e

-- | Find the index with manhattan helper
--   
--   TODO consider using binary search instead of a linear scan here! e.g.:
--   <tt>k = VAS.binarySearchByBounds (==)</tt>
--   
--   NOTE running times with 100x100 DP problem <a>NeedlemanWunsch</a> full
--   findIndex of sixs: 0,050,000 cells/sec using manhattan buckets,
--   findIndex: 5,000,000 cells/sec using binarySearch on slices:
--   11,000,000 cells/sec
--   
--   On a 1000x1000 DP NeedlemanWunsch problem, binary search on slices is
--   at 6,500,000 cells/sec.
manhattanIndex :: (SparseBucket sh, Index sh) => LimitType sh -> Vector Int -> Vector Int -> sh -> Maybe Int
binarySearch :: Int -> Vector Int -> Maybe Int

-- | Given two index vectors of the same shape, will return the correctly
--   ordered vector of the union of indices.
--   
--   TODO This requires that <tt>Ord (Shape O)</tt> uses the <tt>Down</tt>
--   instance of Ord! We need to fix this in the <tt>Index</tt> modules.
--   
--   TODO Rewrite to allow fusion without intermediate vectors using
--   uncons. This will make it possible to chain applications.
--   <tt>stream</tt> should be fine for this.
mergeIndexVectors :: (Eq sh, Ord sh, Vector w sh) => w sh -> w sh -> w sh
instance (Data.PrimitiveArray.Index.Class.Index sh, Data.PrimitiveArray.Index.Class.SparseBucket sh, GHC.Classes.Eq sh, GHC.Classes.Ord sh, Data.Vector.Generic.Base.Vector w sh, Data.Vector.Generic.Base.Vector w (GHC.Types.Int, sh), Data.Vector.Generic.Base.Vector w (GHC.Types.Int, (GHC.Types.Int, sh)), Data.Vector.Generic.Base.Vector w (GHC.Types.Int, GHC.Types.Int), Data.Vector.Generic.Base.Vector w GHC.Types.Int, Data.Vector.Generic.Base.Vector v e) => Data.PrimitiveArray.Class.PrimArrayOps (Data.PrimitiveArray.Sparse.IntBinSearch.Sparse w v) sh e
instance forall k sh (v :: * -> *) e e' (w :: k). (Data.PrimitiveArray.Index.Class.Index sh, Data.Vector.Generic.Base.Vector v e, Data.Vector.Generic.Base.Vector v e') => Data.PrimitiveArray.Class.PrimArrayMap (Data.PrimitiveArray.Sparse.IntBinSearch.Sparse w v) sh e e'

module Data.PrimitiveArray.Sparse