compact-sequences-0.2.0.0: Stacks, queues, and deques with compact representations.

Data.CompactSequence.Queue.Simple.Internal

Description

Space-efficient queues with amortized $$O(\log n)$$ operations. These directly use an underlying array-based implementation, without doing any special optimization for the first few and last few elements of the queue.

Synopsis

# Documentation

newtype Queue a Source #

A queue.

Constructors

 Queue (Queue Sz1 a)

Bundled Patterns

 pattern Empty :: Queue a A bidirectional pattern synonym for the empty queue. pattern (:<) :: a -> Queue a -> Queue a infixr 5 A unidirectional pattern synonym for viewing the front of a queue.
Instances
 Source # Instance details Methodsfmap :: (a -> b) -> Queue a -> Queue b #(<\$) :: a -> Queue b -> Queue a # Source # Instance details Methodsfold :: Monoid m => Queue m -> m #foldMap :: Monoid m => (a -> m) -> Queue a -> m #foldr :: (a -> b -> b) -> b -> Queue a -> b #foldr' :: (a -> b -> b) -> b -> Queue a -> b #foldl :: (b -> a -> b) -> b -> Queue a -> b #foldl' :: (b -> a -> b) -> b -> Queue a -> b #foldr1 :: (a -> a -> a) -> Queue a -> a #foldl1 :: (a -> a -> a) -> Queue a -> a #toList :: Queue a -> [a] #null :: Queue a -> Bool #length :: Queue a -> Int #elem :: Eq a => a -> Queue a -> Bool #maximum :: Ord a => Queue a -> a #minimum :: Ord a => Queue a -> a #sum :: Num a => Queue a -> a #product :: Num a => Queue a -> a # Source # Instance details Methodstraverse :: Applicative f => (a -> f b) -> Queue a -> f (Queue b) #sequenceA :: Applicative f => Queue (f a) -> f (Queue a) #mapM :: Monad m => (a -> m b) -> Queue a -> m (Queue b) #sequence :: Monad m => Queue (m a) -> m (Queue a) # IsList (Queue a) Source # Instance details Associated Typestype Item (Queue a) :: Type # MethodsfromList :: [Item (Queue a)] -> Queue a #fromListN :: Int -> [Item (Queue a)] -> Queue a #toList :: Queue a -> [Item (Queue a)] # Eq a => Eq (Queue a) Source # Instance details Methods(==) :: Queue a -> Queue a -> Bool #(/=) :: Queue a -> Queue a -> Bool # Ord a => Ord (Queue a) Source # Instance details Methodscompare :: Queue a -> Queue a -> Ordering #(<) :: Queue a -> Queue a -> Bool #(<=) :: Queue a -> Queue a -> Bool #(>) :: Queue a -> Queue a -> Bool #(>=) :: Queue a -> Queue a -> Bool #max :: Queue a -> Queue a -> Queue a #min :: Queue a -> Queue a -> Queue a # Show a => Show (Queue a) Source # Instance details MethodsshowsPrec :: Int -> Queue a -> ShowS #show :: Queue a -> String #showList :: [Queue a] -> ShowS # Source # Instance details Methods(<>) :: Queue a -> Queue a -> Queue a #sconcat :: NonEmpty (Queue a) -> Queue a #stimes :: Integral b => b -> Queue a -> Queue a # Monoid (Queue a) Source # Instance details Methodsmempty :: Queue a #mappend :: Queue a -> Queue a -> Queue a #mconcat :: [Queue a] -> Queue a # type Item (Queue a) Source # Instance details type Item (Queue a) = a

(|>) :: Queue a -> a -> Queue a infixl 4 Source #

An infix synonym for snoc.

The empty queue.

snoc :: Queue a -> a -> Queue a infixl 4 Source #

Enqueue an element at the rear of a queue.

uncons :: Queue a -> Maybe (a, Queue a) Source #

Dequeue an element from the front of a queue.

take :: Int -> Queue a -> Queue a Source #

Take up to the given number of elements from the front of a queue to form a new queue. $$O(\min (k, n))$$, where $$k$$ is the integer argument and $$n$$ is the size of the queue.

fromList :: [a] -> Queue a Source #

$$O(n \log n)$$. Convert a list to a Queue, with the head of the list at the front of the queue.

fromListN :: Int -> [a] -> Queue a Source #

$$O(n)$$. Convert a list of the given size to a Queue, with the head of the list at the front of the queue.

fromListNIncremental :: Int -> [a] -> Queue a Source #

$$O(n)$$. Convert a list of the given size to a Queue, with the head of the list at the front of the queue. Unlike fromListN, the conversion is performed incrementally. This is generally beneficial if the list is represented compactly (e.g., an enumeration) or when it's otherwise not important to consume the entire list immediately.