compact-sequences-0.1.0.0: Stacks and queues with compact representations.

Data.CompactSequence.Queue.Internal

Synopsis

# 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)
Instances
 Functor (FD n) Source # Instance detailsDefined in Data.CompactSequence.Queue.Internal Methodsfmap :: (a -> b) -> FD n a -> FD n b #(<$) :: a -> FD n b -> FD n a # Foldable (FD n) Source # Instance detailsDefined in Data.CompactSequence.Queue.Internal Methodsfold :: Monoid m => FD n m -> m #foldMap :: Monoid m => (a -> m) -> FD n a -> m #foldr :: (a -> b -> b) -> b -> FD n a -> b #foldr' :: (a -> b -> b) -> b -> FD n a -> b #foldl :: (b -> a -> b) -> b -> FD n a -> b #foldl' :: (b -> a -> b) -> b -> FD n a -> b #foldr1 :: (a -> a -> a) -> FD n a -> a #foldl1 :: (a -> a -> a) -> FD n a -> a #toList :: FD n a -> [a] #null :: FD n a -> Bool #length :: FD n a -> Int #elem :: Eq a => a -> FD n a -> Bool #maximum :: Ord a => FD n a -> a #minimum :: Ord a => FD n a -> a #sum :: Num a => FD n a -> a #product :: Num a => FD n a -> a # Source # Instance detailsDefined in Data.CompactSequence.Queue.Internal Methodstraverse :: Applicative f => (a -> f b) -> FD n a -> f (FD n b) #sequenceA :: Applicative f => FD n (f a) -> f (FD n a) #mapM :: Monad m => (a -> m b) -> FD n a -> m (FD n b) #sequence :: Monad m => FD n (m a) -> m (FD n a) # data RD n a Source # Constructors  RD0 RD1 !(Array n a) RD2 !(Array n a) !(Array n a) Instances  Functor (RD n) Source # Instance detailsDefined in Data.CompactSequence.Queue.Internal Methodsfmap :: (a -> b) -> RD n a -> RD n b #(<$) :: a -> RD n b -> RD n a # Foldable (RD n) Source # Instance detailsDefined in Data.CompactSequence.Queue.Internal Methodsfold :: Monoid m => RD n m -> m #foldMap :: Monoid m => (a -> m) -> RD n a -> m #foldr :: (a -> b -> b) -> b -> RD n a -> b #foldr' :: (a -> b -> b) -> b -> RD n a -> b #foldl :: (b -> a -> b) -> b -> RD n a -> b #foldl' :: (b -> a -> b) -> b -> RD n a -> b #foldr1 :: (a -> a -> a) -> RD n a -> a #foldl1 :: (a -> a -> a) -> RD n a -> a #toList :: RD n a -> [a] #null :: RD n a -> Bool #length :: RD n a -> Int #elem :: Eq a => a -> RD n a -> Bool #maximum :: Ord a => RD n a -> a #minimum :: Ord a => RD n a -> a #sum :: Num a => RD n a -> a #product :: Num a => RD n a -> a # Source # Instance detailsDefined in Data.CompactSequence.Queue.Internal Methodstraverse :: Applicative f => (a -> f b) -> RD n a -> f (RD n b) #sequenceA :: Applicative f => RD n (f a) -> f (RD n a) #mapM :: Monad m => (a -> m b) -> RD n a -> m (RD n b) #sequence :: Monad m => RD n (m a) -> m (RD n a) #

data Queue n a Source #

Constructors

 Empty Node !(FD n a) (Queue (Twice n) a) !(RD n a)
Instances
 Functor (Queue n) Source # Instance detailsDefined in Data.CompactSequence.Queue.Internal Methodsfmap :: (a -> b) -> Queue n a -> Queue n b #(<\$) :: a -> Queue n b -> Queue n a # Source # Instance detailsDefined in Data.CompactSequence.Queue.Internal Methodsfold :: 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 # Source # Instance detailsDefined in Data.CompactSequence.Queue.Internal Methodstraverse :: 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 detailsDefined 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 detailsDefined in Data.CompactSequence.Queue.Internal Methodscompare :: 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 detailsDefined in Data.CompactSequence.Queue.Internal MethodsshowsPrec :: Int -> Queue n a -> ShowS #show :: Queue n a -> String #showList :: [Queue n a] -> ShowS #

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 #

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

shiftA :: Size n -> Queue 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.