Safe Haskell	None
Language	Haskell2010

Data.CompactSequence.Queue.Internal

Synopsis

data FD n a
- = FD1 !(Array n a)
- | FD2 !(Array n a) !(Array n a)
- | FD3 !(Array n a) !(Array n a) !(Array n a)
data RD n a
- = RD0
- | RD1 !(Array n a)
- | RD2 !(Array n a) !(Array n a)
data Queue n a
- = Empty
- | Node10 !(Array n a) !(Queue (Twice n) a)
- | Node11 !(Array n a) !(Queue (Twice n) a) !(Array n a)
- | Node12 !(Array n a) !(Queue (Twice n) a) !(Array n a) !(Array n a)
- | Node20 !(Array n a) !(Array n a) (Queue (Twice n) a)
- | Node21 !(Array n a) !(Array n a) (Queue (Twice n) a) !(Array n a)
- | Node22 !(Array n a) !(Array n a) !(Queue (Twice n) a) !(Array n a) !(Array n a)
- | Node30 !(Array n a) !(Array n a) !(Array n a) (Queue (Twice n) a)
- | Node31 !(Array n a) !(Array n a) !(Array n a) (Queue (Twice n) a) !(Array n a)
- | Node32 !(Array n a) !(Array n a) !(Array n a) !(Queue (Twice n) a) !(Array n a) !(Array n a)
data Queue_ n a
- = Empty_
- | Node_ !(FD n a) (Queue (Twice n) a) !(RD n a)
matchNode :: Queue n a -> Queue_ n a
pattern Node :: FD n a -> Queue (Twice n) a -> RD n a -> Queue n a
data ViewA n a
- = EmptyA
- | ConsA !(Array n a) (Queue n a)
data ViewA2 n a
- = EmptyA2
- | ConsA2 !(Array n a) !(Array n a) (Queue n a)
singletonA :: Array n a -> Queue n a
viewA :: Size n -> Queue n a -> ViewA n a
empty :: Queue n a
snocA :: Size n -> Queue n a -> Array n a -> Queue n a
shiftA :: Size n -> Queue (Twice n) a -> Array n a -> Array n a -> ShiftedA n a
shrift :: Size n -> Array (Twice n) a -> Queue (Twice n) a -> ShiftedA n a
data ShiftedA n a = ShiftedA !(Array n a) !(Array n a) (Queue (Twice n) a)

Documentation

data FD n a Source #

Constructors

FD1 !(Array n a)
FD2 !(Array n a) !(Array n a)
FD3 !(Array n a) !(Array n a) !(Array n a)

data RD n a Source #

Constructors

RD0
RD1 !(Array n a)
RD2 !(Array n a) !(Array n a)

data Queue n a Source #

Constructors

Empty
Node10 !(Array n a) !(Queue (Twice n) a)
Node11 !(Array n a) !(Queue (Twice n) a) !(Array n a)
Node12 !(Array n a) !(Queue (Twice n) a) !(Array n a) !(Array n a)
Node20 !(Array n a) !(Array n a) (Queue (Twice n) a)
Node21 !(Array n a) !(Array n a) (Queue (Twice n) a) !(Array n a)
Node22 !(Array n a) !(Array n a) !(Queue (Twice n) a) !(Array n a) !(Array n a)
Node30 !(Array n a) !(Array n a) !(Array n a) (Queue (Twice n) a)
Node31 !(Array n a) !(Array n a) !(Array n a) (Queue (Twice n) a) !(Array n a)
Node32 !(Array n a) !(Array n a) !(Array n a) !(Queue (Twice n) a) !(Array n a) !(Array n a)

Instances

Functor (Queue n) Source #
Instance details Defined in Data.CompactSequence.Queue.Internal Methods fmap :: (a -> b) -> Queue n a -> Queue n b # (<$) :: a -> Queue n b -> Queue n a #
Foldable (Queue n) Source #
Instance details Defined in Data.CompactSequence.Queue.Internal Methods fold :: Monoid m => Queue n m -> m # foldMap :: Monoid m => (a -> m) -> Queue n a -> m # foldr :: (a -> b -> b) -> b -> Queue n a -> b # foldr' :: (a -> b -> b) -> b -> Queue n a -> b # foldl :: (b -> a -> b) -> b -> Queue n a -> b # foldl' :: (b -> a -> b) -> b -> Queue n a -> b # foldr1 :: (a -> a -> a) -> Queue n a -> a # foldl1 :: (a -> a -> a) -> Queue n a -> a # toList :: Queue n a -> [a] # null :: Queue n a -> Bool # length :: Queue n a -> Int # elem :: Eq a => a -> Queue n a -> Bool # maximum :: Ord a => Queue n a -> a # minimum :: Ord a => Queue n a -> a # sum :: Num a => Queue n a -> a # product :: Num a => Queue n a -> a #
Traversable (Queue n) Source #
Instance details Defined in Data.CompactSequence.Queue.Internal Methods traverse :: Applicative f => (a -> f b) -> Queue n a -> f (Queue n b) # sequenceA :: Applicative f => Queue n (f a) -> f (Queue n a) # mapM :: Monad m => (a -> m b) -> Queue n a -> m (Queue n b) # sequence :: Monad m => Queue n (m a) -> m (Queue n a) #
Eq a => Eq (Queue n a) Source #
Instance details Defined in Data.CompactSequence.Queue.Internal Methods (==) :: Queue n a -> Queue n a -> Bool # (/=) :: Queue n a -> Queue n a -> Bool #
Ord a => Ord (Queue n a) Source #
Instance details Defined in Data.CompactSequence.Queue.Internal Methods compare :: Queue n a -> Queue n a -> Ordering # (<) :: Queue n a -> Queue n a -> Bool # (<=) :: Queue n a -> Queue n a -> Bool # (>) :: Queue n a -> Queue n a -> Bool # (>=) :: Queue n a -> Queue n a -> Bool # max :: Queue n a -> Queue n a -> Queue n a # min :: Queue n a -> Queue n a -> Queue n a #
Show a => Show (Queue n a) Source #
Instance details Defined in Data.CompactSequence.Queue.Internal Methods showsPrec :: Int -> Queue n a -> ShowS # show :: Queue n a -> String # showList :: [Queue n a] -> ShowS #

data Queue_ n a Source #

Constructors

Empty_
Node_ !(FD n a) (Queue (Twice n) a) !(RD n a)

matchNode :: Queue n a -> Queue_ n a Source #

pattern Node :: FD n a -> Queue (Twice n) a -> RD n a -> Queue n a Source #

data ViewA n a Source #

Constructors

EmptyA
ConsA !(Array n a) (Queue n a)

data ViewA2 n a Source #

Constructors

EmptyA2
ConsA2 !(Array n a) !(Array n a) (Queue n a)

singletonA :: Array n a -> Queue n a Source #

viewA :: Size n -> Queue n a -> ViewA n a Source #

empty :: Queue n a Source #

snocA :: Size n -> Queue n a -> Array n a -> Queue n a Source #

shiftA :: Size n -> Queue (Twice n) a -> Array n a -> Array n a -> ShiftedA n a Source #

Uncons from a node and snoc onto it. Ensure that if the operation is expensive then it leaves the node in a safe configuration. Why do we need this? Suppose we have

Two m Two

If we snoc onto this, the operation cascades, and we get

Two m Zero

Then when we view, we get

One m Zero

which is not safe.

Instead, we need to view first, getting

One m Two

immediately, then snoc on, cascading and getting

Three m Zero

which is safe.

If instead we have

One m One

we have to do the opposite: snoc then view. We might as well just write a dedicated shifting operation.

shrift :: Size n -> Array (Twice n) a -> Queue (Twice n) a -> ShiftedA n a Source #

data ShiftedA n a Source #

Constructors

ShiftedA !(Array n a) !(Array n a) (Queue (Twice n) a)