{-# LANGUAGE GeneralizedNewtypeDeriving #-}
-- |
-- Module: NetSpider.Queue
-- Description: 
-- Maintainer: Toshio Ito <debug.ito@gmail.com>
--
-- __this module is internal. End-users should not use it.__
module NetSpider.Queue
       ( Queue,
         newQueue,
         pushQueue,
         popQueue
       ) where

import Data.Foldable (Foldable)
import Data.Monoid (Monoid)
import Data.Semigroup (Semigroup)
import Data.Sequence (Seq, (|>), viewl, ViewL(..), fromList)
import Data.Traversable (Traversable)

-- | Pure FIFO queue.
newtype Queue a = Queue (Seq a)
                deriving (Int -> Queue a -> ShowS
[Queue a] -> ShowS
Queue a -> String
(Int -> Queue a -> ShowS)
-> (Queue a -> String) -> ([Queue a] -> ShowS) -> Show (Queue a)
forall a. Show a => Int -> Queue a -> ShowS
forall a. Show a => [Queue a] -> ShowS
forall a. Show a => Queue a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Queue a] -> ShowS
$cshowList :: forall a. Show a => [Queue a] -> ShowS
show :: Queue a -> String
$cshow :: forall a. Show a => Queue a -> String
showsPrec :: Int -> Queue a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Queue a -> ShowS
Show,Queue a -> Queue a -> Bool
(Queue a -> Queue a -> Bool)
-> (Queue a -> Queue a -> Bool) -> Eq (Queue a)
forall a. Eq a => Queue a -> Queue a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Queue a -> Queue a -> Bool
$c/= :: forall a. Eq a => Queue a -> Queue a -> Bool
== :: Queue a -> Queue a -> Bool
$c== :: forall a. Eq a => Queue a -> Queue a -> Bool
Eq,Eq (Queue a)
Eq (Queue a)
-> (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)
-> (Queue a -> Queue a -> Queue a)
-> (Queue a -> Queue a -> Queue a)
-> Ord (Queue a)
Queue a -> Queue a -> Bool
Queue a -> Queue a -> Ordering
Queue a -> Queue a -> Queue a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (Queue a)
forall a. Ord a => Queue a -> Queue a -> Bool
forall a. Ord a => Queue a -> Queue a -> Ordering
forall a. Ord a => Queue a -> Queue a -> Queue a
min :: Queue a -> Queue a -> Queue a
$cmin :: forall a. Ord a => Queue a -> Queue a -> Queue a
max :: Queue a -> Queue a -> Queue a
$cmax :: forall a. Ord a => Queue a -> Queue a -> Queue a
>= :: Queue a -> Queue a -> Bool
$c>= :: forall a. Ord a => Queue a -> Queue a -> Bool
> :: Queue a -> Queue a -> Bool
$c> :: forall a. Ord a => Queue a -> Queue a -> Bool
<= :: Queue a -> Queue a -> Bool
$c<= :: forall a. Ord a => Queue a -> Queue a -> Bool
< :: Queue a -> Queue a -> Bool
$c< :: forall a. Ord a => Queue a -> Queue a -> Bool
compare :: Queue a -> Queue a -> Ordering
$ccompare :: forall a. Ord a => Queue a -> Queue a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (Queue a)
Ord,b -> Queue a -> Queue a
NonEmpty (Queue a) -> Queue a
Queue a -> Queue a -> Queue a
(Queue a -> Queue a -> Queue a)
-> (NonEmpty (Queue a) -> Queue a)
-> (forall b. Integral b => b -> Queue a -> Queue a)
-> Semigroup (Queue a)
forall b. Integral b => b -> Queue a -> Queue a
forall a. NonEmpty (Queue a) -> Queue a
forall a. Queue a -> Queue a -> Queue a
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
forall a b. Integral b => b -> Queue a -> Queue a
stimes :: b -> Queue a -> Queue a
$cstimes :: forall a b. Integral b => b -> Queue a -> Queue a
sconcat :: NonEmpty (Queue a) -> Queue a
$csconcat :: forall a. NonEmpty (Queue a) -> Queue a
<> :: Queue a -> Queue a -> Queue a
$c<> :: forall a. Queue a -> Queue a -> Queue a
Semigroup,Semigroup (Queue a)
Queue a
Semigroup (Queue a)
-> Queue a
-> (Queue a -> Queue a -> Queue a)
-> ([Queue a] -> Queue a)
-> Monoid (Queue a)
[Queue a] -> Queue a
Queue a -> Queue a -> Queue a
forall a. Semigroup (Queue a)
forall a. Queue a
forall a.
Semigroup a -> a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
forall a. [Queue a] -> Queue a
forall a. Queue a -> Queue a -> Queue a
mconcat :: [Queue a] -> Queue a
$cmconcat :: forall a. [Queue a] -> Queue a
mappend :: Queue a -> Queue a -> Queue a
$cmappend :: forall a. Queue a -> Queue a -> Queue a
mempty :: Queue a
$cmempty :: forall a. Queue a
$cp1Monoid :: forall a. Semigroup (Queue a)
Monoid,a -> Queue a -> Bool
Queue m -> m
Queue a -> [a]
Queue a -> Bool
Queue a -> Int
Queue a -> a
Queue a -> a
Queue a -> a
Queue a -> a
(a -> m) -> Queue a -> m
(a -> m) -> Queue a -> m
(a -> b -> b) -> b -> Queue a -> b
(a -> b -> b) -> b -> Queue a -> b
(b -> a -> b) -> b -> Queue a -> b
(b -> a -> b) -> b -> Queue a -> b
(a -> a -> a) -> Queue a -> a
(a -> a -> a) -> Queue a -> a
(forall m. Monoid m => Queue m -> m)
-> (forall m a. Monoid m => (a -> m) -> Queue a -> m)
-> (forall m a. Monoid m => (a -> m) -> Queue a -> m)
-> (forall a b. (a -> b -> b) -> b -> Queue a -> b)
-> (forall a b. (a -> b -> b) -> b -> Queue a -> b)
-> (forall b a. (b -> a -> b) -> b -> Queue a -> b)
-> (forall b a. (b -> a -> b) -> b -> Queue a -> b)
-> (forall a. (a -> a -> a) -> Queue a -> a)
-> (forall a. (a -> a -> a) -> Queue a -> a)
-> (forall a. Queue a -> [a])
-> (forall a. Queue a -> Bool)
-> (forall a. Queue a -> Int)
-> (forall a. Eq a => a -> Queue a -> Bool)
-> (forall a. Ord a => Queue a -> a)
-> (forall a. Ord a => Queue a -> a)
-> (forall a. Num a => Queue a -> a)
-> (forall a. Num a => Queue a -> a)
-> Foldable Queue
forall a. Eq a => a -> Queue a -> Bool
forall a. Num a => Queue a -> a
forall a. Ord a => Queue a -> a
forall m. Monoid m => Queue m -> m
forall a. Queue a -> Bool
forall a. Queue a -> Int
forall a. Queue a -> [a]
forall a. (a -> a -> a) -> Queue a -> a
forall m a. Monoid m => (a -> m) -> Queue a -> m
forall b a. (b -> a -> b) -> b -> Queue a -> b
forall a b. (a -> b -> b) -> b -> Queue a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: Queue a -> a
$cproduct :: forall a. Num a => Queue a -> a
sum :: Queue a -> a
$csum :: forall a. Num a => Queue a -> a
minimum :: Queue a -> a
$cminimum :: forall a. Ord a => Queue a -> a
maximum :: Queue a -> a
$cmaximum :: forall a. Ord a => Queue a -> a
elem :: a -> Queue a -> Bool
$celem :: forall a. Eq a => a -> Queue a -> Bool
length :: Queue a -> Int
$clength :: forall a. Queue a -> Int
null :: Queue a -> Bool
$cnull :: forall a. Queue a -> Bool
toList :: Queue a -> [a]
$ctoList :: forall a. Queue a -> [a]
foldl1 :: (a -> a -> a) -> Queue a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Queue a -> a
foldr1 :: (a -> a -> a) -> Queue a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Queue a -> a
foldl' :: (b -> a -> b) -> b -> Queue a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Queue a -> b
foldl :: (b -> a -> b) -> b -> Queue a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Queue a -> b
foldr' :: (a -> b -> b) -> b -> Queue a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Queue a -> b
foldr :: (a -> b -> b) -> b -> Queue a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Queue a -> b
foldMap' :: (a -> m) -> Queue a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Queue a -> m
foldMap :: (a -> m) -> Queue a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Queue a -> m
fold :: Queue m -> m
$cfold :: forall m. Monoid m => Queue m -> m
Foldable,a -> Queue b -> Queue a
(a -> b) -> Queue a -> Queue b
(forall a b. (a -> b) -> Queue a -> Queue b)
-> (forall a b. a -> Queue b -> Queue a) -> Functor Queue
forall a b. a -> Queue b -> Queue a
forall a b. (a -> b) -> Queue a -> Queue b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Queue b -> Queue a
$c<$ :: forall a b. a -> Queue b -> Queue a
fmap :: (a -> b) -> Queue a -> Queue b
$cfmap :: forall a b. (a -> b) -> Queue a -> Queue b
Functor,Functor Queue
a -> Queue a
Functor Queue
-> (forall a. a -> Queue a)
-> (forall a b. Queue (a -> b) -> Queue a -> Queue b)
-> (forall a b c. (a -> b -> c) -> Queue a -> Queue b -> Queue c)
-> (forall a b. Queue a -> Queue b -> Queue b)
-> (forall a b. Queue a -> Queue b -> Queue a)
-> Applicative Queue
Queue a -> Queue b -> Queue b
Queue a -> Queue b -> Queue a
Queue (a -> b) -> Queue a -> Queue b
(a -> b -> c) -> Queue a -> Queue b -> Queue c
forall a. a -> Queue a
forall a b. Queue a -> Queue b -> Queue a
forall a b. Queue a -> Queue b -> Queue b
forall a b. Queue (a -> b) -> Queue a -> Queue b
forall a b c. (a -> b -> c) -> Queue a -> Queue b -> Queue c
forall (f :: * -> *).
Functor f
-> (forall a. a -> f a)
-> (forall a b. f (a -> b) -> f a -> f b)
-> (forall a b c. (a -> b -> c) -> f a -> f b -> f c)
-> (forall a b. f a -> f b -> f b)
-> (forall a b. f a -> f b -> f a)
-> Applicative f
<* :: Queue a -> Queue b -> Queue a
$c<* :: forall a b. Queue a -> Queue b -> Queue a
*> :: Queue a -> Queue b -> Queue b
$c*> :: forall a b. Queue a -> Queue b -> Queue b
liftA2 :: (a -> b -> c) -> Queue a -> Queue b -> Queue c
$cliftA2 :: forall a b c. (a -> b -> c) -> Queue a -> Queue b -> Queue c
<*> :: Queue (a -> b) -> Queue a -> Queue b
$c<*> :: forall a b. Queue (a -> b) -> Queue a -> Queue b
pure :: a -> Queue a
$cpure :: forall a. a -> Queue a
$cp1Applicative :: Functor Queue
Applicative,Applicative Queue
a -> Queue a
Applicative Queue
-> (forall a b. Queue a -> (a -> Queue b) -> Queue b)
-> (forall a b. Queue a -> Queue b -> Queue b)
-> (forall a. a -> Queue a)
-> Monad Queue
Queue a -> (a -> Queue b) -> Queue b
Queue a -> Queue b -> Queue b
forall a. a -> Queue a
forall a b. Queue a -> Queue b -> Queue b
forall a b. Queue a -> (a -> Queue b) -> Queue b
forall (m :: * -> *).
Applicative m
-> (forall a b. m a -> (a -> m b) -> m b)
-> (forall a b. m a -> m b -> m b)
-> (forall a. a -> m a)
-> Monad m
return :: a -> Queue a
$creturn :: forall a. a -> Queue a
>> :: Queue a -> Queue b -> Queue b
$c>> :: forall a b. Queue a -> Queue b -> Queue b
>>= :: Queue a -> (a -> Queue b) -> Queue b
$c>>= :: forall a b. Queue a -> (a -> Queue b) -> Queue b
$cp1Monad :: Applicative Queue
Monad)

newQueue :: [a] -> Queue a
newQueue :: [a] -> Queue a
newQueue = Seq a -> Queue a
forall a. Seq a -> Queue a
Queue (Seq a -> Queue a) -> ([a] -> Seq a) -> [a] -> Queue a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Seq a
forall a. [a] -> Seq a
fromList

pushQueue :: a -> Queue a -> Queue a
pushQueue :: a -> Queue a -> Queue a
pushQueue a
item (Queue Seq a
s) = Seq a -> Queue a
forall a. Seq a -> Queue a
Queue (Seq a
s Seq a -> a -> Seq a
forall a. Seq a -> a -> Seq a
|> a
item)

popQueue :: Queue a -> (Maybe a, Queue a)
popQueue :: Queue a -> (Maybe a, Queue a)
popQueue q :: Queue a
q@(Queue Seq a
s) =
  case Seq a -> ViewL a
forall a. Seq a -> ViewL a
viewl Seq a
s of
   ViewL a
EmptyL -> (Maybe a
forall a. Maybe a
Nothing, Queue a
q)
   (a
item :< Seq a
rest) -> (a -> Maybe a
forall a. a -> Maybe a
Just a
item, Seq a -> Queue a
forall a. Seq a -> Queue a
Queue Seq a
rest)