{-
(c) The University of Glasgow 2006
(c) The AQUA Project, Glasgow University, 1993-1998


-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE UnboxedTuples #-}

-- | Provide trees (of instructions), so that lists of instructions can be
-- appended in linear time.
module GHC.Data.OrdList (
        OrdList, pattern NilOL, pattern ConsOL, pattern SnocOL,
        nilOL, isNilOL, unitOL, appOL, consOL, snocOL, concatOL, lastOL,
        headOL,
        mapOL, mapOL', fromOL, toOL, foldrOL, foldlOL, reverseOL, fromOLReverse,
        strictlyEqOL, strictlyOrdOL
) where

import GHC.Prelude
import Data.Foldable

import GHC.Utils.Misc (strictMap)
import GHC.Utils.Outputable
import GHC.Utils.Panic

import Data.List.NonEmpty (NonEmpty(..))
import qualified Data.List.NonEmpty as NE
import qualified Data.Semigroup as Semigroup

infixl 5  `appOL`
infixl 5  `snocOL`
infixr 5  `consOL`

data OrdList a
  = None
  | One a
  | Many (NonEmpty a)
  | Cons a (OrdList a)
  | Snoc (OrdList a) a
  | Two (OrdList a) -- Invariant: non-empty
        (OrdList a) -- Invariant: non-empty
  deriving ((forall a b. (a -> b) -> OrdList a -> OrdList b)
-> (forall a b. a -> OrdList b -> OrdList a) -> Functor OrdList
forall a b. a -> OrdList b -> OrdList a
forall a b. (a -> b) -> OrdList a -> OrdList b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall a b. (a -> b) -> OrdList a -> OrdList b
fmap :: forall a b. (a -> b) -> OrdList a -> OrdList b
$c<$ :: forall a b. a -> OrdList b -> OrdList a
<$ :: forall a b. a -> OrdList b -> OrdList a
Functor)

instance Outputable a => Outputable (OrdList a) where
  ppr :: OrdList a -> SDoc
ppr OrdList a
ol = [a] -> SDoc
forall a. Outputable a => a -> SDoc
ppr (OrdList a -> [a]
forall a. OrdList a -> [a]
fromOL OrdList a
ol)  -- Convert to list and print that

instance Semigroup (OrdList a) where
  <> :: OrdList a -> OrdList a -> OrdList a
(<>) = OrdList a -> OrdList a -> OrdList a
forall a. OrdList a -> OrdList a -> OrdList a
appOL

instance Monoid (OrdList a) where
  mempty :: OrdList a
mempty = OrdList a
forall a. OrdList a
nilOL
  mappend :: OrdList a -> OrdList a -> OrdList a
mappend = OrdList a -> OrdList a -> OrdList a
forall a. Semigroup a => a -> a -> a
(Semigroup.<>)
  mconcat :: [OrdList a] -> OrdList a
mconcat = [OrdList a] -> OrdList a
forall a. [OrdList a] -> OrdList a
concatOL

instance Foldable OrdList where
  foldr :: forall a b. (a -> b -> b) -> b -> OrdList a -> b
foldr   = (a -> b -> b) -> b -> OrdList a -> b
forall a b. (a -> b -> b) -> b -> OrdList a -> b
foldrOL
  foldl' :: forall b a. (b -> a -> b) -> b -> OrdList a -> b
foldl'  = (b -> a -> b) -> b -> OrdList a -> b
forall b a. (b -> a -> b) -> b -> OrdList a -> b
foldlOL
  toList :: forall a. OrdList a -> [a]
toList  = OrdList a -> [a]
forall a. OrdList a -> [a]
fromOL
  null :: forall a. OrdList a -> Bool
null    = OrdList a -> Bool
forall a. OrdList a -> Bool
isNilOL
  length :: forall a. OrdList a -> Int
length  = OrdList a -> Int
forall a. OrdList a -> Int
lengthOL

instance Traversable OrdList where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> OrdList a -> f (OrdList b)
traverse a -> f b
f OrdList a
xs = [b] -> OrdList b
forall a. [a] -> OrdList a
toOL ([b] -> OrdList b) -> f [b] -> f (OrdList b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> [a] -> f [b]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> [a] -> f [b]
traverse a -> f b
f (OrdList a -> [a]
forall a. OrdList a -> [a]
fromOL OrdList a
xs)

nilOL    :: OrdList a
isNilOL  :: OrdList a -> Bool

unitOL   :: a           -> OrdList a
snocOL   :: OrdList a   -> a         -> OrdList a
consOL   :: a           -> OrdList a -> OrdList a
appOL    :: OrdList a   -> OrdList a -> OrdList a
concatOL :: [OrdList a] -> OrdList a
headOL   :: OrdList a   -> a
lastOL   :: OrdList a   -> a
lengthOL :: OrdList a   -> Int

nilOL :: forall a. OrdList a
nilOL        = OrdList a
forall a. OrdList a
None
unitOL :: forall a. a -> OrdList a
unitOL a
as    = a -> OrdList a
forall a. a -> OrdList a
One a
as
snocOL :: forall a. OrdList a -> a -> OrdList a
snocOL OrdList a
as   a
b    = OrdList a -> a -> OrdList a
forall a. OrdList a -> a -> OrdList a
Snoc OrdList a
as a
b
consOL :: forall a. a -> OrdList a -> OrdList a
consOL a
a    OrdList a
bs   = a -> OrdList a -> OrdList a
forall a. a -> OrdList a -> OrdList a
Cons a
a OrdList a
bs
concatOL :: forall a. [OrdList a] -> OrdList a
concatOL [OrdList a]
aas = (OrdList a -> OrdList a -> OrdList a)
-> OrdList a -> [OrdList a] -> OrdList a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr OrdList a -> OrdList a -> OrdList a
forall a. OrdList a -> OrdList a -> OrdList a
appOL OrdList a
forall a. OrdList a
None [OrdList a]
aas

pattern NilOL :: OrdList a
pattern $mNilOL :: forall {r} {a}. OrdList a -> ((# #) -> r) -> ((# #) -> r) -> r
$bNilOL :: forall a. OrdList a
NilOL <- (isNilOL -> True) where
  NilOL = OrdList a
forall a. OrdList a
None

-- | An unboxed 'Maybe' type with two unboxed fields in the 'Just' case.
-- Useful for defining 'viewCons' and 'viewSnoc' without overhead.
type VMaybe a b = (# (# a, b #) | (# #) #)
pattern VJust :: a -> b -> VMaybe a b
pattern $mVJust :: forall {r} {a} {b}.
VMaybe a b -> (a -> b -> r) -> ((# #) -> r) -> r
$bVJust :: forall a b. a -> b -> VMaybe a b
VJust a b = (# (# a, b #) | #)
pattern VNothing :: VMaybe a b
pattern $mVNothing :: forall {r} {a} {b}. VMaybe a b -> ((# #) -> r) -> ((# #) -> r) -> r
$bVNothing :: (# #) -> forall a b. VMaybe a b
VNothing = (# | (# #) #)
{-# COMPLETE VJust, VNothing #-}

pattern ConsOL :: a -> OrdList a -> OrdList a
pattern $mConsOL :: forall {r} {a}.
OrdList a -> (a -> OrdList a -> r) -> ((# #) -> r) -> r
$bConsOL :: forall a. a -> OrdList a -> OrdList a
ConsOL x xs <- (viewCons -> VJust x xs) where
  ConsOL a
x OrdList a
xs = a -> OrdList a -> OrdList a
forall a. a -> OrdList a -> OrdList a
consOL a
x OrdList a
xs
{-# COMPLETE NilOL, ConsOL #-}

viewCons :: OrdList a -> VMaybe a (OrdList a)
viewCons :: forall a. OrdList a -> VMaybe a (OrdList a)
viewCons OrdList a
None        = (# #) -> forall a b. VMaybe a b
forall b. VMaybe (OrdList a) b
VNothing
viewCons (One a
a)     = a -> OrdList a -> VMaybe a (OrdList a)
forall a b. a -> b -> VMaybe a b
VJust a
a OrdList a
forall a. OrdList a
NilOL
viewCons (Many (a
a :| [])) = a -> OrdList a -> VMaybe a (OrdList a)
forall a b. a -> b -> VMaybe a b
VJust a
a OrdList a
forall a. OrdList a
NilOL
viewCons (Many (a
a :| a
b : [a]
bs)) = a -> OrdList a -> VMaybe a (OrdList a)
forall a b. a -> b -> VMaybe a b
VJust a
a (NonEmpty a -> OrdList a
forall a. NonEmpty a -> OrdList a
Many (a
b a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
bs))
viewCons (Cons a
a OrdList a
as) = a -> OrdList a -> VMaybe a (OrdList a)
forall a b. a -> b -> VMaybe a b
VJust a
a OrdList a
as
viewCons (Snoc OrdList a
as a
a) = case OrdList a -> VMaybe a (OrdList a)
forall a. OrdList a -> VMaybe a (OrdList a)
viewCons OrdList a
as of
  VJust a
a' OrdList a
as' -> a -> OrdList a -> VMaybe a (OrdList a)
forall a b. a -> b -> VMaybe a b
VJust a
a' (OrdList a -> a -> OrdList a
forall a. OrdList a -> a -> OrdList a
Snoc OrdList a
as' a
a)
  VMaybe a (OrdList a)
VNothing     -> a -> OrdList a -> VMaybe a (OrdList a)
forall a b. a -> b -> VMaybe a b
VJust a
a OrdList a
forall a. OrdList a
NilOL
viewCons (Two OrdList a
as1 OrdList a
as2) = case OrdList a -> VMaybe a (OrdList a)
forall a. OrdList a -> VMaybe a (OrdList a)
viewCons OrdList a
as1 of
  VJust a
a' OrdList a
as1' -> a -> OrdList a -> VMaybe a (OrdList a)
forall a b. a -> b -> VMaybe a b
VJust a
a' (OrdList a -> OrdList a -> OrdList a
forall a. OrdList a -> OrdList a -> OrdList a
Two OrdList a
as1' OrdList a
as2)
  VMaybe a (OrdList a)
VNothing      -> OrdList a -> VMaybe a (OrdList a)
forall a. OrdList a -> VMaybe a (OrdList a)
viewCons OrdList a
as2

pattern SnocOL :: OrdList a -> a -> OrdList a
pattern $mSnocOL :: forall {r} {a}.
OrdList a -> (OrdList a -> a -> r) -> ((# #) -> r) -> r
$bSnocOL :: forall a. OrdList a -> a -> OrdList a
SnocOL xs x <- (viewSnoc -> VJust xs x) where
  SnocOL OrdList a
xs a
x = OrdList a -> a -> OrdList a
forall a. OrdList a -> a -> OrdList a
snocOL OrdList a
xs a
x
{-# COMPLETE NilOL, SnocOL #-}

viewSnoc :: OrdList a -> VMaybe (OrdList a) a
viewSnoc :: forall a. OrdList a -> VMaybe (OrdList a) a
viewSnoc OrdList a
None        = (# #) -> forall a b. VMaybe a b
forall b. VMaybe a b
VNothing
viewSnoc (One a
a)     = OrdList a -> a -> VMaybe (OrdList a) a
forall a b. a -> b -> VMaybe a b
VJust OrdList a
forall a. OrdList a
NilOL a
a
viewSnoc (Many NonEmpty a
as)   = (OrdList a -> a -> VMaybe (OrdList a) a
forall a b. a -> b -> VMaybe a b
`VJust` NonEmpty a -> a
forall a. NonEmpty a -> a
NE.last NonEmpty a
as) (OrdList a -> VMaybe (OrdList a) a)
-> OrdList a -> VMaybe (OrdList a) a
forall a b. (a -> b) -> a -> b
$ case NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
NE.init NonEmpty a
as of
  [] -> OrdList a
forall a. OrdList a
NilOL
  a
b : [a]
bs -> NonEmpty a -> OrdList a
forall a. NonEmpty a -> OrdList a
Many (a
b a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
bs)
viewSnoc (Snoc OrdList a
as a
a) = OrdList a -> a -> VMaybe (OrdList a) a
forall a b. a -> b -> VMaybe a b
VJust OrdList a
as a
a
viewSnoc (Cons a
a OrdList a
as) = case OrdList a -> VMaybe (OrdList a) a
forall a. OrdList a -> VMaybe (OrdList a) a
viewSnoc OrdList a
as of
  VJust OrdList a
as' a
a' -> OrdList a -> a -> VMaybe (OrdList a) a
forall a b. a -> b -> VMaybe a b
VJust (a -> OrdList a -> OrdList a
forall a. a -> OrdList a -> OrdList a
Cons a
a OrdList a
as') a
a'
  VMaybe (OrdList a) a
VNothing     -> OrdList a -> a -> VMaybe (OrdList a) a
forall a b. a -> b -> VMaybe a b
VJust OrdList a
forall a. OrdList a
NilOL a
a
viewSnoc (Two OrdList a
as1 OrdList a
as2) = case OrdList a -> VMaybe (OrdList a) a
forall a. OrdList a -> VMaybe (OrdList a) a
viewSnoc OrdList a
as2 of
  VJust OrdList a
as2' a
a' -> OrdList a -> a -> VMaybe (OrdList a) a
forall a b. a -> b -> VMaybe a b
VJust (OrdList a -> OrdList a -> OrdList a
forall a. OrdList a -> OrdList a -> OrdList a
Two OrdList a
as1 OrdList a
as2') a
a'
  VMaybe (OrdList a) a
VNothing      -> OrdList a -> VMaybe (OrdList a) a
forall a. OrdList a -> VMaybe (OrdList a) a
viewSnoc OrdList a
as1

headOL :: forall a. OrdList a -> a
headOL OrdList a
None        = String -> a
forall a. HasCallStack => String -> a
panic String
"headOL"
headOL (One a
a)     = a
a
headOL (Many NonEmpty a
as)   = NonEmpty a -> a
forall a. NonEmpty a -> a
NE.head NonEmpty a
as
headOL (Cons a
a OrdList a
_)  = a
a
headOL (Snoc OrdList a
as a
_) = OrdList a -> a
forall a. OrdList a -> a
headOL OrdList a
as
headOL (Two OrdList a
as OrdList a
_)  = OrdList a -> a
forall a. OrdList a -> a
headOL OrdList a
as

lastOL :: forall a. OrdList a -> a
lastOL OrdList a
None        = String -> a
forall a. HasCallStack => String -> a
panic String
"lastOL"
lastOL (One a
a)     = a
a
lastOL (Many NonEmpty a
as)   = NonEmpty a -> a
forall a. NonEmpty a -> a
NE.last NonEmpty a
as
lastOL (Cons a
_ OrdList a
as) = OrdList a -> a
forall a. OrdList a -> a
lastOL OrdList a
as
lastOL (Snoc OrdList a
_ a
a)  = a
a
lastOL (Two OrdList a
_ OrdList a
as)  = OrdList a -> a
forall a. OrdList a -> a
lastOL OrdList a
as

lengthOL :: forall a. OrdList a -> Int
lengthOL OrdList a
None        = Int
0
lengthOL (One a
_)     = Int
1
lengthOL (Many NonEmpty a
as)   = NonEmpty a -> Int
forall a. NonEmpty a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length NonEmpty a
as
lengthOL (Cons a
_ OrdList a
as) = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ OrdList a -> Int
forall a. OrdList a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length OrdList a
as
lengthOL (Snoc OrdList a
as a
_) = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ OrdList a -> Int
forall a. OrdList a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length OrdList a
as
lengthOL (Two OrdList a
as OrdList a
bs) = OrdList a -> Int
forall a. OrdList a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length OrdList a
as Int -> Int -> Int
forall a. Num a => a -> a -> a
+ OrdList a -> Int
forall a. OrdList a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length OrdList a
bs

isNilOL :: forall a. OrdList a -> Bool
isNilOL OrdList a
None = Bool
True
isNilOL OrdList a
_    = Bool
False

OrdList a
None  appOL :: forall a. OrdList a -> OrdList a -> OrdList a
`appOL` OrdList a
b     = OrdList a
b
OrdList a
a     `appOL` OrdList a
None  = OrdList a
a
One a
a `appOL` OrdList a
b     = a -> OrdList a -> OrdList a
forall a. a -> OrdList a -> OrdList a
Cons a
a OrdList a
b
OrdList a
a     `appOL` One a
b = OrdList a -> a -> OrdList a
forall a. OrdList a -> a -> OrdList a
Snoc OrdList a
a a
b
OrdList a
a     `appOL` OrdList a
b     = OrdList a -> OrdList a -> OrdList a
forall a. OrdList a -> OrdList a -> OrdList a
Two OrdList a
a OrdList a
b

fromOL :: OrdList a -> [a]
fromOL :: forall a. OrdList a -> [a]
fromOL OrdList a
a = OrdList a -> [a] -> [a]
forall {a}. OrdList a -> [a] -> [a]
go OrdList a
a []
  where go :: OrdList a -> [a] -> [a]
go OrdList a
None       [a]
acc = [a]
acc
        go (One a
a)    [a]
acc = a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
acc
        go (Cons a
a OrdList a
b) [a]
acc = a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: OrdList a -> [a] -> [a]
go OrdList a
b [a]
acc
        go (Snoc OrdList a
a a
b) [a]
acc = OrdList a -> [a] -> [a]
go OrdList a
a (a
ba -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
acc)
        go (Two OrdList a
a OrdList a
b)  [a]
acc = OrdList a -> [a] -> [a]
go OrdList a
a (OrdList a -> [a] -> [a]
go OrdList a
b [a]
acc)
        go (Many NonEmpty a
xs)  [a]
acc = NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
NE.toList NonEmpty a
xs [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
acc

fromOLReverse :: OrdList a -> [a]
fromOLReverse :: forall a. OrdList a -> [a]
fromOLReverse OrdList a
a = OrdList a -> [a] -> [a]
forall {a}. OrdList a -> [a] -> [a]
go OrdList a
a []
        -- acc is already in reverse order
  where go :: OrdList a -> [a] -> [a]
        go :: forall {a}. OrdList a -> [a] -> [a]
go OrdList a
None       [a]
acc = [a]
acc
        go (One a
a)    [a]
acc = a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
acc
        go (Cons a
a OrdList a
b) [a]
acc = OrdList a -> [a] -> [a]
forall {a}. OrdList a -> [a] -> [a]
go OrdList a
b (a
a a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
acc)
        go (Snoc OrdList a
a a
b) [a]
acc = a
b a -> [a] -> [a]
forall a. a -> [a] -> [a]
: OrdList a -> [a] -> [a]
forall {a}. OrdList a -> [a] -> [a]
go OrdList a
a [a]
acc
        go (Two OrdList a
a OrdList a
b)  [a]
acc = OrdList a -> [a] -> [a]
forall {a}. OrdList a -> [a] -> [a]
go OrdList a
b (OrdList a -> [a] -> [a]
forall {a}. OrdList a -> [a] -> [a]
go OrdList a
a [a]
acc)
        go (Many NonEmpty a
xs)  [a]
acc = [a] -> [a]
forall a. [a] -> [a]
reverse (NonEmpty a -> [a]
forall a. NonEmpty a -> [a]
NE.toList NonEmpty a
xs) [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
acc

mapOL :: (a -> b) -> OrdList a -> OrdList b
mapOL :: forall a b. (a -> b) -> OrdList a -> OrdList b
mapOL = (a -> b) -> OrdList a -> OrdList b
forall a b. (a -> b) -> OrdList a -> OrdList b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap

mapOL' :: (a->b) -> OrdList a -> OrdList b
mapOL' :: forall a b. (a -> b) -> OrdList a -> OrdList b
mapOL' a -> b
_ OrdList a
None        = OrdList b
forall a. OrdList a
None
mapOL' a -> b
f (One a
x)     = b -> OrdList b
forall a. a -> OrdList a
One (b -> OrdList b) -> b -> OrdList b
forall a b. (a -> b) -> a -> b
$! a -> b
f a
x
mapOL' a -> b
f (Cons a
x OrdList a
xs) = let !x1 :: b
x1 = a -> b
f a
x
                           !xs1 :: OrdList b
xs1 = (a -> b) -> OrdList a -> OrdList b
forall a b. (a -> b) -> OrdList a -> OrdList b
mapOL' a -> b
f OrdList a
xs
                       in b -> OrdList b -> OrdList b
forall a. a -> OrdList a -> OrdList a
Cons b
x1 OrdList b
xs1
mapOL' a -> b
f (Snoc OrdList a
xs a
x) = let !x1 :: b
x1 = a -> b
f a
x
                           !xs1 :: OrdList b
xs1 = (a -> b) -> OrdList a -> OrdList b
forall a b. (a -> b) -> OrdList a -> OrdList b
mapOL' a -> b
f OrdList a
xs
                       in OrdList b -> b -> OrdList b
forall a. OrdList a -> a -> OrdList a
Snoc OrdList b
xs1 b
x1
mapOL' a -> b
f (Two OrdList a
b1 OrdList a
b2) = let !b1' :: OrdList b
b1' = (a -> b) -> OrdList a -> OrdList b
forall a b. (a -> b) -> OrdList a -> OrdList b
mapOL' a -> b
f OrdList a
b1
                           !b2' :: OrdList b
b2' = (a -> b) -> OrdList a -> OrdList b
forall a b. (a -> b) -> OrdList a -> OrdList b
mapOL' a -> b
f OrdList a
b2
                       in OrdList b -> OrdList b -> OrdList b
forall a. OrdList a -> OrdList a -> OrdList a
Two OrdList b
b1' OrdList b
b2'
mapOL' a -> b
f (Many (a
x :| [a]
xs)) = let !x1 :: b
x1 = a -> b
f a
x
                                !xs1 :: [b]
xs1 = (a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
strictMap a -> b
f [a]
xs
                            in NonEmpty b -> OrdList b
forall a. NonEmpty a -> OrdList a
Many (b
x1 b -> [b] -> NonEmpty b
forall a. a -> [a] -> NonEmpty a
:| [b]
xs1)

foldrOL :: (a->b->b) -> b -> OrdList a -> b
foldrOL :: forall a b. (a -> b -> b) -> b -> OrdList a -> b
foldrOL a -> b -> b
_ b
z OrdList a
None        = b
z
foldrOL a -> b -> b
k b
z (One a
x)     = a -> b -> b
k a
x b
z
foldrOL a -> b -> b
k b
z (Cons a
x OrdList a
xs) = a -> b -> b
k a
x ((a -> b -> b) -> b -> OrdList a -> b
forall a b. (a -> b -> b) -> b -> OrdList a -> b
foldrOL a -> b -> b
k b
z OrdList a
xs)
foldrOL a -> b -> b
k b
z (Snoc OrdList a
xs a
x) = (a -> b -> b) -> b -> OrdList a -> b
forall a b. (a -> b -> b) -> b -> OrdList a -> b
foldrOL a -> b -> b
k (a -> b -> b
k a
x b
z) OrdList a
xs
foldrOL a -> b -> b
k b
z (Two OrdList a
b1 OrdList a
b2) = (a -> b -> b) -> b -> OrdList a -> b
forall a b. (a -> b -> b) -> b -> OrdList a -> b
foldrOL a -> b -> b
k ((a -> b -> b) -> b -> OrdList a -> b
forall a b. (a -> b -> b) -> b -> OrdList a -> b
foldrOL a -> b -> b
k b
z OrdList a
b2) OrdList a
b1
foldrOL a -> b -> b
k b
z (Many NonEmpty a
xs)   = (a -> b -> b) -> b -> NonEmpty a -> b
forall a b. (a -> b -> b) -> b -> NonEmpty a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
k b
z NonEmpty a
xs

-- | Strict left fold.
foldlOL :: (b->a->b) -> b -> OrdList a -> b
foldlOL :: forall b a. (b -> a -> b) -> b -> OrdList a -> b
foldlOL b -> a -> b
_ b
z OrdList a
None        = b
z
foldlOL b -> a -> b
k b
z (One a
x)     = b -> a -> b
k b
z a
x
foldlOL b -> a -> b
k b
z (Cons a
x OrdList a
xs) = let !z' :: b
z' = (b -> a -> b
k b
z a
x) in (b -> a -> b) -> b -> OrdList a -> b
forall b a. (b -> a -> b) -> b -> OrdList a -> b
foldlOL b -> a -> b
k b
z' OrdList a
xs
foldlOL b -> a -> b
k b
z (Snoc OrdList a
xs a
x) = let !z' :: b
z' = ((b -> a -> b) -> b -> OrdList a -> b
forall b a. (b -> a -> b) -> b -> OrdList a -> b
foldlOL b -> a -> b
k b
z OrdList a
xs) in b -> a -> b
k b
z' a
x
foldlOL b -> a -> b
k b
z (Two OrdList a
b1 OrdList a
b2) = let !z' :: b
z' = ((b -> a -> b) -> b -> OrdList a -> b
forall b a. (b -> a -> b) -> b -> OrdList a -> b
foldlOL b -> a -> b
k b
z OrdList a
b1) in (b -> a -> b) -> b -> OrdList a -> b
forall b a. (b -> a -> b) -> b -> OrdList a -> b
foldlOL b -> a -> b
k b
z' OrdList a
b2
foldlOL b -> a -> b
k b
z (Many NonEmpty a
xs)   = (b -> a -> b) -> b -> NonEmpty a -> b
forall b a. (b -> a -> b) -> b -> NonEmpty a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
k b
z NonEmpty a
xs

toOL :: [a] -> OrdList a
toOL :: forall a. [a] -> OrdList a
toOL [] = OrdList a
forall a. OrdList a
None
toOL [a
x] = a -> OrdList a
forall a. a -> OrdList a
One a
x
toOL (a
x : [a]
xs) = NonEmpty a -> OrdList a
forall a. NonEmpty a -> OrdList a
Many (a
x a -> [a] -> NonEmpty a
forall a. a -> [a] -> NonEmpty a
:| [a]
xs)

reverseOL :: OrdList a -> OrdList a
reverseOL :: forall a. OrdList a -> OrdList a
reverseOL OrdList a
None = OrdList a
forall a. OrdList a
None
reverseOL (One a
x) = a -> OrdList a
forall a. a -> OrdList a
One a
x
reverseOL (Cons a
a OrdList a
b) = OrdList a -> a -> OrdList a
forall a. OrdList a -> a -> OrdList a
Snoc (OrdList a -> OrdList a
forall a. OrdList a -> OrdList a
reverseOL OrdList a
b) a
a
reverseOL (Snoc OrdList a
a a
b) = a -> OrdList a -> OrdList a
forall a. a -> OrdList a -> OrdList a
Cons a
b (OrdList a -> OrdList a
forall a. OrdList a -> OrdList a
reverseOL OrdList a
a)
reverseOL (Two OrdList a
a OrdList a
b)  = OrdList a -> OrdList a -> OrdList a
forall a. OrdList a -> OrdList a -> OrdList a
Two (OrdList a -> OrdList a
forall a. OrdList a -> OrdList a
reverseOL OrdList a
b) (OrdList a -> OrdList a
forall a. OrdList a -> OrdList a
reverseOL OrdList a
a)
reverseOL (Many NonEmpty a
xs)  = NonEmpty a -> OrdList a
forall a. NonEmpty a -> OrdList a
Many (NonEmpty a -> NonEmpty a
forall a. NonEmpty a -> NonEmpty a
NE.reverse NonEmpty a
xs)

-- | Compare not only the values but also the structure of two lists
strictlyEqOL :: Eq a => OrdList a   -> OrdList a -> Bool
strictlyEqOL :: forall a. Eq a => OrdList a -> OrdList a -> Bool
strictlyEqOL OrdList a
None         OrdList a
None       = Bool
True
strictlyEqOL (One a
x)     (One a
y)     = a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y
strictlyEqOL (Cons a
a OrdList a
as) (Cons a
b OrdList a
bs) = a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b Bool -> Bool -> Bool
&& OrdList a
as OrdList a -> OrdList a -> Bool
forall a. Eq a => OrdList a -> OrdList a -> Bool
`strictlyEqOL` OrdList a
bs
strictlyEqOL (Snoc OrdList a
as a
a) (Snoc OrdList a
bs a
b) = a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
b Bool -> Bool -> Bool
&& OrdList a
as OrdList a -> OrdList a -> Bool
forall a. Eq a => OrdList a -> OrdList a -> Bool
`strictlyEqOL` OrdList a
bs
strictlyEqOL (Two OrdList a
a1 OrdList a
a2) (Two OrdList a
b1 OrdList a
b2) = OrdList a
a1 OrdList a -> OrdList a -> Bool
forall a. Eq a => OrdList a -> OrdList a -> Bool
`strictlyEqOL` OrdList a
b1 Bool -> Bool -> Bool
&& OrdList a
a2 OrdList a -> OrdList a -> Bool
forall a. Eq a => OrdList a -> OrdList a -> Bool
`strictlyEqOL` OrdList a
b2
strictlyEqOL (Many NonEmpty a
as)   (Many NonEmpty a
bs)   = NonEmpty a
as NonEmpty a -> NonEmpty a -> Bool
forall a. Eq a => a -> a -> Bool
== NonEmpty a
bs
strictlyEqOL OrdList a
_            OrdList a
_          = Bool
False

-- | Compare not only the values but also the structure of two lists
strictlyOrdOL :: Ord a => OrdList a   -> OrdList a -> Ordering
strictlyOrdOL :: forall a. Ord a => OrdList a -> OrdList a -> Ordering
strictlyOrdOL OrdList a
None         OrdList a
None       = Ordering
EQ
strictlyOrdOL OrdList a
None         OrdList a
_          = Ordering
LT
strictlyOrdOL (One a
x)     (One a
y)     = a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y
strictlyOrdOL (One a
_)      OrdList a
_          = Ordering
LT
strictlyOrdOL (Cons a
a OrdList a
as) (Cons a
b OrdList a
bs) =
  a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
b Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend` OrdList a -> OrdList a -> Ordering
forall a. Ord a => OrdList a -> OrdList a -> Ordering
strictlyOrdOL OrdList a
as OrdList a
bs
strictlyOrdOL (Cons a
_ OrdList a
_)   OrdList a
_          = Ordering
LT
strictlyOrdOL (Snoc OrdList a
as a
a) (Snoc OrdList a
bs a
b) =
  a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
a a
b Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend` OrdList a -> OrdList a -> Ordering
forall a. Ord a => OrdList a -> OrdList a -> Ordering
strictlyOrdOL OrdList a
as OrdList a
bs
strictlyOrdOL (Snoc OrdList a
_ a
_)   OrdList a
_          = Ordering
LT
strictlyOrdOL (Two OrdList a
a1 OrdList a
a2) (Two OrdList a
b1 OrdList a
b2) =
  (OrdList a -> OrdList a -> Ordering
forall a. Ord a => OrdList a -> OrdList a -> Ordering
strictlyOrdOL OrdList a
a1 OrdList a
b1) Ordering -> Ordering -> Ordering
forall a. Monoid a => a -> a -> a
`mappend` (OrdList a -> OrdList a -> Ordering
forall a. Ord a => OrdList a -> OrdList a -> Ordering
strictlyOrdOL OrdList a
a2 OrdList a
b2)
strictlyOrdOL (Two OrdList a
_ OrdList a
_)    OrdList a
_          = Ordering
LT
strictlyOrdOL (Many NonEmpty a
as)   (Many NonEmpty a
bs)   = NonEmpty a -> NonEmpty a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare NonEmpty a
as NonEmpty a
bs
strictlyOrdOL (Many NonEmpty a
_ )   OrdList a
_           = Ordering
GT