-- | Binary trees, used for O(1) append.

module Agda.Utils.BinTree1 (BinTree1, prependToList, toList, toList1) where

import Agda.Utils.List1 (List1)
import Agda.Utils.List1 qualified as List1
import Agda.Utils.Singleton

import Agda.Utils.Impossible

data BinTree1 a
  = Lf1 a
  | !(BinTree1 a) :++: !(BinTree1 a)
  deriving (BinTree1 a -> BinTree1 a -> Bool
(BinTree1 a -> BinTree1 a -> Bool)
-> (BinTree1 a -> BinTree1 a -> Bool) -> Eq (BinTree1 a)
forall a. Eq a => BinTree1 a -> BinTree1 a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => BinTree1 a -> BinTree1 a -> Bool
== :: BinTree1 a -> BinTree1 a -> Bool
$c/= :: forall a. Eq a => BinTree1 a -> BinTree1 a -> Bool
/= :: BinTree1 a -> BinTree1 a -> Bool
Eq, Eq (BinTree1 a)
Eq (BinTree1 a) =>
(BinTree1 a -> BinTree1 a -> Ordering)
-> (BinTree1 a -> BinTree1 a -> Bool)
-> (BinTree1 a -> BinTree1 a -> Bool)
-> (BinTree1 a -> BinTree1 a -> Bool)
-> (BinTree1 a -> BinTree1 a -> Bool)
-> (BinTree1 a -> BinTree1 a -> BinTree1 a)
-> (BinTree1 a -> BinTree1 a -> BinTree1 a)
-> Ord (BinTree1 a)
BinTree1 a -> BinTree1 a -> Bool
BinTree1 a -> BinTree1 a -> Ordering
BinTree1 a -> BinTree1 a -> BinTree1 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 (BinTree1 a)
forall a. Ord a => BinTree1 a -> BinTree1 a -> Bool
forall a. Ord a => BinTree1 a -> BinTree1 a -> Ordering
forall a. Ord a => BinTree1 a -> BinTree1 a -> BinTree1 a
$ccompare :: forall a. Ord a => BinTree1 a -> BinTree1 a -> Ordering
compare :: BinTree1 a -> BinTree1 a -> Ordering
$c< :: forall a. Ord a => BinTree1 a -> BinTree1 a -> Bool
< :: BinTree1 a -> BinTree1 a -> Bool
$c<= :: forall a. Ord a => BinTree1 a -> BinTree1 a -> Bool
<= :: BinTree1 a -> BinTree1 a -> Bool
$c> :: forall a. Ord a => BinTree1 a -> BinTree1 a -> Bool
> :: BinTree1 a -> BinTree1 a -> Bool
$c>= :: forall a. Ord a => BinTree1 a -> BinTree1 a -> Bool
>= :: BinTree1 a -> BinTree1 a -> Bool
$cmax :: forall a. Ord a => BinTree1 a -> BinTree1 a -> BinTree1 a
max :: BinTree1 a -> BinTree1 a -> BinTree1 a
$cmin :: forall a. Ord a => BinTree1 a -> BinTree1 a -> BinTree1 a
min :: BinTree1 a -> BinTree1 a -> BinTree1 a
Ord, Int -> BinTree1 a -> ShowS
[BinTree1 a] -> ShowS
BinTree1 a -> String
(Int -> BinTree1 a -> ShowS)
-> (BinTree1 a -> String)
-> ([BinTree1 a] -> ShowS)
-> Show (BinTree1 a)
forall a. Show a => Int -> BinTree1 a -> ShowS
forall a. Show a => [BinTree1 a] -> ShowS
forall a. Show a => BinTree1 a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> BinTree1 a -> ShowS
showsPrec :: Int -> BinTree1 a -> ShowS
$cshow :: forall a. Show a => BinTree1 a -> String
show :: BinTree1 a -> String
$cshowList :: forall a. Show a => [BinTree1 a] -> ShowS
showList :: [BinTree1 a] -> ShowS
Show, (forall a b. (a -> b) -> BinTree1 a -> BinTree1 b)
-> (forall a b. a -> BinTree1 b -> BinTree1 a) -> Functor BinTree1
forall a b. a -> BinTree1 b -> BinTree1 a
forall a b. (a -> b) -> BinTree1 a -> BinTree1 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) -> BinTree1 a -> BinTree1 b
fmap :: forall a b. (a -> b) -> BinTree1 a -> BinTree1 b
$c<$ :: forall a b. a -> BinTree1 b -> BinTree1 a
<$ :: forall a b. a -> BinTree1 b -> BinTree1 a
Functor, (forall m. Monoid m => BinTree1 m -> m)
-> (forall m a. Monoid m => (a -> m) -> BinTree1 a -> m)
-> (forall m a. Monoid m => (a -> m) -> BinTree1 a -> m)
-> (forall a b. (a -> b -> b) -> b -> BinTree1 a -> b)
-> (forall a b. (a -> b -> b) -> b -> BinTree1 a -> b)
-> (forall b a. (b -> a -> b) -> b -> BinTree1 a -> b)
-> (forall b a. (b -> a -> b) -> b -> BinTree1 a -> b)
-> (forall a. (a -> a -> a) -> BinTree1 a -> a)
-> (forall a. (a -> a -> a) -> BinTree1 a -> a)
-> (forall a. BinTree1 a -> [a])
-> (forall a. BinTree1 a -> Bool)
-> (forall a. BinTree1 a -> Int)
-> (forall a. Eq a => a -> BinTree1 a -> Bool)
-> (forall a. Ord a => BinTree1 a -> a)
-> (forall a. Ord a => BinTree1 a -> a)
-> (forall a. Num a => BinTree1 a -> a)
-> (forall a. Num a => BinTree1 a -> a)
-> Foldable BinTree1
forall a. Eq a => a -> BinTree1 a -> Bool
forall a. Num a => BinTree1 a -> a
forall a. Ord a => BinTree1 a -> a
forall m. Monoid m => BinTree1 m -> m
forall a. BinTree1 a -> Bool
forall a. BinTree1 a -> Int
forall a. BinTree1 a -> [a]
forall a. (a -> a -> a) -> BinTree1 a -> a
forall m a. Monoid m => (a -> m) -> BinTree1 a -> m
forall b a. (b -> a -> b) -> b -> BinTree1 a -> b
forall a b. (a -> b -> b) -> b -> BinTree1 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
$cfold :: forall m. Monoid m => BinTree1 m -> m
fold :: forall m. Monoid m => BinTree1 m -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> BinTree1 a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> BinTree1 a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> BinTree1 a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> BinTree1 a -> m
$cfoldr :: forall a b. (a -> b -> b) -> b -> BinTree1 a -> b
foldr :: forall a b. (a -> b -> b) -> b -> BinTree1 a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> BinTree1 a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> BinTree1 a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> BinTree1 a -> b
foldl :: forall b a. (b -> a -> b) -> b -> BinTree1 a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> BinTree1 a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> BinTree1 a -> b
$cfoldr1 :: forall a. (a -> a -> a) -> BinTree1 a -> a
foldr1 :: forall a. (a -> a -> a) -> BinTree1 a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> BinTree1 a -> a
foldl1 :: forall a. (a -> a -> a) -> BinTree1 a -> a
$ctoList :: forall a. BinTree1 a -> [a]
toList :: forall a. BinTree1 a -> [a]
$cnull :: forall a. BinTree1 a -> Bool
null :: forall a. BinTree1 a -> Bool
$clength :: forall a. BinTree1 a -> Int
length :: forall a. BinTree1 a -> Int
$celem :: forall a. Eq a => a -> BinTree1 a -> Bool
elem :: forall a. Eq a => a -> BinTree1 a -> Bool
$cmaximum :: forall a. Ord a => BinTree1 a -> a
maximum :: forall a. Ord a => BinTree1 a -> a
$cminimum :: forall a. Ord a => BinTree1 a -> a
minimum :: forall a. Ord a => BinTree1 a -> a
$csum :: forall a. Num a => BinTree1 a -> a
sum :: forall a. Num a => BinTree1 a -> a
$cproduct :: forall a. Num a => BinTree1 a -> a
product :: forall a. Num a => BinTree1 a -> a
Foldable, Functor BinTree1
Foldable BinTree1
(Functor BinTree1, Foldable BinTree1) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> BinTree1 a -> f (BinTree1 b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    BinTree1 (f a) -> f (BinTree1 a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> BinTree1 a -> m (BinTree1 b))
-> (forall (m :: * -> *) a.
    Monad m =>
    BinTree1 (m a) -> m (BinTree1 a))
-> Traversable BinTree1
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => BinTree1 (m a) -> m (BinTree1 a)
forall (f :: * -> *) a.
Applicative f =>
BinTree1 (f a) -> f (BinTree1 a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> BinTree1 a -> m (BinTree1 b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> BinTree1 a -> f (BinTree1 b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> BinTree1 a -> f (BinTree1 b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> BinTree1 a -> f (BinTree1 b)
$csequenceA :: forall (f :: * -> *) a.
Applicative f =>
BinTree1 (f a) -> f (BinTree1 a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
BinTree1 (f a) -> f (BinTree1 a)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> BinTree1 a -> m (BinTree1 b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> BinTree1 a -> m (BinTree1 b)
$csequence :: forall (m :: * -> *) a. Monad m => BinTree1 (m a) -> m (BinTree1 a)
sequence :: forall (m :: * -> *) a. Monad m => BinTree1 (m a) -> m (BinTree1 a)
Traversable)

instance Semigroup (BinTree1 a) where
  <> :: BinTree1 a -> BinTree1 a -> BinTree1 a
(<>) = BinTree1 a -> BinTree1 a -> BinTree1 a
forall a. BinTree1 a -> BinTree1 a -> BinTree1 a
(:++:)

instance Singleton a (BinTree1 a) where
  singleton :: a -> BinTree1 a
singleton = a -> BinTree1 a
forall a. a -> BinTree1 a
Lf1

prependToList :: BinTree1 a -> [a] -> [a]
prependToList :: forall a. BinTree1 a -> [a] -> [a]
prependToList = \case
  Lf1 a
a      -> (a
aa -> [a] -> [a]
forall a. a -> [a] -> [a]
:)
  BinTree1 a
t1 :++: BinTree1 a
t2 -> BinTree1 a -> [a] -> [a]
forall a. BinTree1 a -> [a] -> [a]
prependToList BinTree1 a
t1 ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BinTree1 a -> [a] -> [a]
forall a. BinTree1 a -> [a] -> [a]
prependToList BinTree1 a
t2

toList :: BinTree1 a -> [a]
toList :: forall a. BinTree1 a -> [a]
toList = (BinTree1 a -> [a] -> [a]
forall a. BinTree1 a -> [a] -> [a]
`prependToList` [])

toList1 :: BinTree1 a -> List1 a
toList1 :: forall a. BinTree1 a -> List1 a
toList1 = List1 a -> [a] -> List1 a
forall a. List1 a -> [a] -> List1 a
List1.fromListSafe List1 a
forall a. HasCallStack => a
__IMPOSSIBLE__ ([a] -> List1 a) -> (BinTree1 a -> [a]) -> BinTree1 a -> List1 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BinTree1 a -> [a]
forall a. BinTree1 a -> [a]
toList