Data.CompactSequence.Queue.Internal

Documentation

data FD n a

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

Constructors

RD0

RD1 !(Array n a)

RD2 !(Array n a) !(Array n a)

data Queue n a

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)

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)

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)

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)

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)

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)

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

Constructors

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

Constructors

EmptyA

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

data ViewA2 n a

Constructors

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

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

data ShiftedA n a

Constructors

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