-- |
-- Copyright   :  (c) Adrian Hey 2004,2005
-- License     :  BSD3
--
{-# OPTIONS_HADDOCK hide #-}
module Data.Tree.AVL.Split
(-- * Splitting AVL trees

 -- ** Taking fixed size lumps of tree
 -- | Bear in mind that the tree size (s) is not stored in the AVL data structure, but if it is
 -- already known for other reasons then for (n > s\/2) using the appropriate complementary
 -- function with argument (s-n) will be faster.
 -- But it's probably not worth invoking 'Data.Tree.AVL.Internals.Types.size' for no reason other than to
 -- exploit this optimisation (because this is O(s) anyway).
 splitAtL,splitAtR,takeL,takeR,dropL,dropR,

 -- ** Rotations
 -- | Bear in mind that the tree size (s) is not stored in the AVL data structure, but if it is
 -- already known for other reasons then for (n > s\/2) using the appropriate complementary
 -- function with argument (s-n) will be faster.
 -- But it's probably not worth invoking 'Data.Tree.AVL.Internals.Types.size' for no reason other than to exploit this optimisation
 -- (because this is O(s) anyway).
 rotateL,rotateR,popRotateL,popRotateR,rotateByL,rotateByR,

 -- ** Taking lumps of tree according to a supplied predicate
 spanL,spanR,takeWhileL,dropWhileL,takeWhileR,dropWhileR,

 -- ** Taking lumps of /sorted/ trees
 -- | Prepare to get confused. All these functions adhere to the same Ordering convention as
 -- is used for searches. That is, if the supplied selector returns LT that means the search
 -- key is less than the current tree element. Or put another way, the current tree element
 -- is greater than the search key.
 --
 -- So (for example) the result of the 'takeLT' function is a tree containing all those elements
 -- which are less than the notional search key. That is, all those elements for which the
 -- supplied selector returns GT (not LT as you might expect). I know that seems backwards, but
 -- it's consistent if you think about it.
 forkL,forkR,fork,
 takeLE,dropGT,
 takeLT,dropGE,
 takeGT,dropLE,
 takeGE,dropLT,
) where

import Prelude -- so haddock finds the symbols there


import Data.COrdering(COrdering(..))
import Data.Tree.AVL.Internals.Types(AVL(..))
import Data.Tree.AVL.Push(pushL,pushR)
import Data.Tree.AVL.Internals.DelUtils(popRN,popRZ,popRP,popLN,popLZ,popLP)
import Data.Tree.AVL.Internals.HAVL(HAVL(HAVL),spliceHAVL,pushLHAVL,pushRHAVL)
import Data.Tree.AVL.Internals.HJoin(joinH')

import GHC.Base
#include "ghcdefs.h"

-- Local Datatype for results of split operations.
data SplitResult e = All  (HAVL e) (HAVL e)     -- Two tree/height pairs. Non Strict!!
                   | More {-# UNPACK #-} !UINT  -- No of tree elements still required (>=0!!)

-- | Split an AVL tree from the Left. The 'Int' argument n (n >= 0) specifies the split point.
-- This function raises an error if n is negative.
--
-- If the tree size is greater than n the result is (Right (l,r)) where l contains
-- the leftmost n elements and r contains the remaining rightmost elements (r will be non-empty).
--
-- If the tree size is less than or equal to n then the result is (Left s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
splitAtL :: Int -> AVL e -> Either Int (AVL e, AVL e)
splitAtL :: forall e. Int -> AVL e -> Either Int (AVL e, AVL e)
splitAtL Int
n AVL e
_ | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0  = [Char] -> Either Int (AVL e, AVL e)
forall a. HasCallStack => [Char] -> a
error [Char]
"splitAtL: Negative argument."
splitAtL Int
0        AVL e
E = Int -> Either Int (AVL e, AVL e)
forall a b. a -> Either a b
Left Int
0       -- Treat this case specially
splitAtL Int
0        AVL e
t = (AVL e, AVL e) -> Either Int (AVL e, AVL e)
forall a b. b -> Either a b
Right (AVL e
forall e. AVL e
E,AVL e
t)
splitAtL ASINT(n) AVL e
t = case Int# -> AVL e -> Int# -> SplitResult e
forall e. Int# -> AVL e -> Int# -> SplitResult e
splitL Int#
n AVL e
t L(0) of -- Tree Heights are relative!!
                      More Int#
n_                   -> Int -> Either Int (AVL e, AVL e)
forall a b. a -> Either a b
Left ASINT(SUBINT(n,n_))
                      All (HAVL AVL e
l Int#
_) (HAVL AVL e
r Int#
_) -> (AVL e, AVL e) -> Either Int (AVL e, AVL e)
forall a b. b -> Either a b
Right (AVL e
l,AVL e
r)

-- n > 0 !!
-- N.B Never returns a result of form (ALL lhavl rhavl) where rhavl is empty
splitL :: UINT -> AVL e -> UINT -> SplitResult e
splitL :: forall e. Int# -> AVL e -> Int# -> SplitResult e
splitL Int#
n  AVL e
E        Int#
_ = Int# -> SplitResult e
forall e. Int# -> SplitResult e
More Int#
n
splitL Int#
n (N AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
splitL_ Int#
n AVL e
l DECINT2(h) e r DECINT1(h)
splitL Int#
n (Z AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
splitL_ Int#
n AVL e
l DECINT1(h) e r DECINT1(h)
splitL Int#
n (P AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
splitL_ Int#
n AVL e
l DECINT1(h) e r DECINT2(h)

-- n > 0 !!
-- N.B Never returns a result of form (ALL lhavl rhavl) where rhavl is empty
splitL_ :: UINT -> AVL e -> UINT -> e -> AVL e -> UINT -> SplitResult e
splitL_ :: forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
splitL_ Int#
n AVL e
l Int#
hl e
e AVL e
r Int#
hr =
 case Int# -> AVL e -> Int# -> SplitResult e
forall e. Int# -> AVL e -> Int# -> SplitResult e
splitL Int#
n AVL e
l Int#
hl of
 More L(0)         -> let rhavl = pushLHAVL e (HAVL r hr); lhavl = HAVL l hl
                      in  lhavl `seq` rhavl `seq` All lhavl rhavl
 More L(1)         -> case r of
                      E       -> More L(0)
                      _       -> let lhavl = pushRHAVL (HAVL l hl) e
                                     rhavl = HAVL r hr
                                 in  lhavl `seq` rhavl `seq` All lhavl rhavl
 More Int#
n_           -> let sr :: SplitResult e
sr = Int# -> AVL e -> Int# -> SplitResult e
forall e. Int# -> AVL e -> Int# -> SplitResult e
splitL DECINT1(n_) r hr
                      in case SplitResult e
sr of
                         More Int#
_          -> SplitResult e
sr
                         All HAVL e
havl0 HAVL e
havl1 -> let havl0' :: HAVL e
havl0' = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                                            in  HAVL e
havl0' HAVL e -> SplitResult e -> SplitResult e
forall a b. a -> b -> b
`seq` HAVL e -> HAVL e -> SplitResult e
forall e. HAVL e -> HAVL e -> SplitResult e
All HAVL e
havl0' HAVL e
havl1
 All HAVL e
havl0 HAVL e
havl1   -> let havl1' :: HAVL e
havl1' = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                      in  HAVL e
havl1' HAVL e -> SplitResult e -> SplitResult e
forall a b. a -> b -> b
`seq` HAVL e -> HAVL e -> SplitResult e
forall e. HAVL e -> HAVL e -> SplitResult e
All HAVL e
havl0 HAVL e
havl1'

-- | Split an AVL tree from the Right. The 'Int' argument n (n >= 0) specifies the split point.
-- This function raises an error if n is negative.
--
-- If the tree size is greater than n the result is (Right (l,r)) where r contains
-- the rightmost n elements and l contains the remaining leftmost elements (l will be non-empty).
--
-- If the tree size is less than or equal to n then the result is (Left s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
splitAtR :: Int -> AVL e -> Either Int (AVL e, AVL e)
splitAtR :: forall e. Int -> AVL e -> Either Int (AVL e, AVL e)
splitAtR Int
n        AVL e
_ | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0  = [Char] -> Either Int (AVL e, AVL e)
forall a. HasCallStack => [Char] -> a
error [Char]
"splitAtR: Negative argument."
splitAtR Int
0        AVL e
E = Int -> Either Int (AVL e, AVL e)
forall a b. a -> Either a b
Left Int
0       -- Treat this case specially
splitAtR Int
0        AVL e
t = (AVL e, AVL e) -> Either Int (AVL e, AVL e)
forall a b. b -> Either a b
Right (AVL e
t,AVL e
forall e. AVL e
E)
splitAtR ASINT(n) AVL e
t = case Int# -> AVL e -> Int# -> SplitResult e
forall e. Int# -> AVL e -> Int# -> SplitResult e
splitR Int#
n AVL e
t L(0) of -- Tree Heights are relative!!
                      More Int#
n_                   -> Int -> Either Int (AVL e, AVL e)
forall a b. a -> Either a b
Left ASINT(SUBINT(n,n_))
                      All (HAVL AVL e
l Int#
_) (HAVL AVL e
r Int#
_) -> (AVL e, AVL e) -> Either Int (AVL e, AVL e)
forall a b. b -> Either a b
Right (AVL e
l,AVL e
r)

-- n > 0 !!
-- N.B Never returns a result of form (ALL lhavl rhavl) where lhavl is empty
splitR :: UINT -> AVL e -> UINT -> SplitResult e
splitR :: forall e. Int# -> AVL e -> Int# -> SplitResult e
splitR Int#
n  AVL e
E        Int#
_ = Int# -> SplitResult e
forall e. Int# -> SplitResult e
More Int#
n
splitR Int#
n (N AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
splitR_ Int#
n AVL e
l DECINT2(h) e r DECINT1(h)
splitR Int#
n (Z AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
splitR_ Int#
n AVL e
l DECINT1(h) e r DECINT1(h)
splitR Int#
n (P AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
splitR_ Int#
n AVL e
l DECINT1(h) e r DECINT2(h)

-- n > 0 !!
-- N.B Never returns a result of form (ALL lhavl rhavl) where lhavl is empty
splitR_ :: UINT -> AVL e -> UINT -> e -> AVL e -> UINT -> SplitResult e
splitR_ :: forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> SplitResult e
splitR_ Int#
n AVL e
l Int#
hl e
e AVL e
r Int#
hr =
 case Int# -> AVL e -> Int# -> SplitResult e
forall e. Int# -> AVL e -> Int# -> SplitResult e
splitR Int#
n AVL e
r Int#
hr of
 More L(0)         -> let lhavl = pushRHAVL (HAVL l hl) e; rhavl = HAVL r hr
                      in  lhavl `seq` rhavl `seq` All lhavl rhavl
 More L(1)         -> case l of
                      E       -> More L(0)
                      _       -> let rhavl = pushLHAVL e (HAVL r hr)
                                     lhavl = HAVL l hl
                                 in  lhavl `seq` rhavl `seq` All lhavl rhavl
 More Int#
n_           -> let sr :: SplitResult e
sr = Int# -> AVL e -> Int# -> SplitResult e
forall e. Int# -> AVL e -> Int# -> SplitResult e
splitR DECINT1(n_) l hl
                      in case SplitResult e
sr of
                         More Int#
_          -> SplitResult e
sr
                         All HAVL e
havl0 HAVL e
havl1 -> let havl1' :: HAVL e
havl1' = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                                            in  HAVL e
havl1' HAVL e -> SplitResult e -> SplitResult e
forall a b. a -> b -> b
`seq` HAVL e -> HAVL e -> SplitResult e
forall e. HAVL e -> HAVL e -> SplitResult e
All HAVL e
havl0 HAVL e
havl1'
 All HAVL e
havl0 HAVL e
havl1   -> let havlO' :: HAVL e
havlO' = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                      in  HAVL e
havlO' HAVL e -> SplitResult e -> SplitResult e
forall a b. a -> b -> b
`seq` HAVL e -> HAVL e -> SplitResult e
forall e. HAVL e -> HAVL e -> SplitResult e
All HAVL e
havlO' HAVL e
havl1

-- Local Datatype for results of take/drop operations.
data TakeResult e = AllTR (HAVL e)               -- The resulting Tree
                  | MoreTR {-# UNPACK #-} !UINT  -- No of tree elements still required (>=0!!)

-- | This is a simplified version of 'splitAtL' which does not return the remaining tree.
-- The 'Int' argument n (n >= 0) specifies the number of elements to take (from the left).
-- This function raises an error if n is negative.
--
-- If the tree size is greater than n the result is (Right l) where l contains
-- the leftmost n elements.
--
-- If the tree size is less than or equal to n then the result is (Left s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
takeL :: Int -> AVL e -> Either Int (AVL e)
takeL :: forall e. Int -> AVL e -> Either Int (AVL e)
takeL Int
n AVL e
_ | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0  = [Char] -> Either Int (AVL e)
forall a. HasCallStack => [Char] -> a
error [Char]
"takeL: Negative argument."
takeL Int
0        AVL e
E = Int -> Either Int (AVL e)
forall a b. a -> Either a b
Left Int
0       -- Treat this case specially
takeL Int
0        AVL e
_ = AVL e -> Either Int (AVL e)
forall a b. b -> Either a b
Right AVL e
forall e. AVL e
E
takeL ASINT(n) AVL e
t = case Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
takeL_ Int#
n AVL e
t L(0) of -- Tree Heights are relative!!
                   MoreTR Int#
n_         -> Int -> Either Int (AVL e)
forall a b. a -> Either a b
Left ASINT(SUBINT(n,n_))
                   AllTR (HAVL AVL e
t' Int#
_) -> AVL e -> Either Int (AVL e)
forall a b. b -> Either a b
Right AVL e
t'

-- n > 0 !!
takeL_ :: UINT -> AVL e -> UINT -> TakeResult e
takeL_ :: forall e. Int# -> AVL e -> Int# -> TakeResult e
takeL_ Int#
n  AVL e
E        Int#
_ = Int# -> TakeResult e
forall e. Int# -> TakeResult e
MoreTR Int#
n
takeL_ Int#
n (N AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
takeL__ Int#
n AVL e
l DECINT2(h) e r DECINT1(h)
takeL_ Int#
n (Z AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
takeL__ Int#
n AVL e
l DECINT1(h) e r DECINT1(h)
takeL_ Int#
n (P AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
takeL__ Int#
n AVL e
l DECINT1(h) e r DECINT2(h)

-- n > 0 !!
takeL__ :: UINT -> AVL e -> UINT -> e -> AVL e -> UINT -> TakeResult e
takeL__ :: forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
takeL__ Int#
n AVL e
l Int#
hl e
e AVL e
r Int#
hr =
 let takel :: TakeResult e
takel = Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
takeL_ Int#
n AVL e
l Int#
hl
 in case TakeResult e
takel of
    MoreTR L(0) -> let lhavl = HAVL l hl
                   in  lhavl `seq` AllTR lhavl
    MoreTR L(1) -> case r of
                   E       -> MoreTR L(0)
                   _       -> let lhavl = pushRHAVL (HAVL l hl) e
                              in  lhavl `seq` AllTR lhavl
    MoreTR Int#
n_   -> let taker :: TakeResult e
taker = Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
takeL_ DECINT1(n_) r hr
                   in case TakeResult e
taker of
                      AllTR HAVL e
havl0 -> let havl0' :: HAVL e
havl0' = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                                     in  HAVL e
havl0' HAVL e -> TakeResult e -> TakeResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeResult e
forall e. HAVL e -> TakeResult e
AllTR HAVL e
havl0'
                      TakeResult e
_           -> TakeResult e
taker
    TakeResult e
_           -> TakeResult e
takel

-- | This is a simplified version of 'splitAtR' which does not return the remaining tree.
-- The 'Int' argument n (n >= 0) specifies the number of elements to take (from the right).
-- This function raises an error if n is negative.
--
-- If the tree size is greater than n the result is (Right r) where r contains
-- the rightmost n elements.
--
-- If the tree size is less than or equal to n then the result is (Left s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
takeR :: Int -> AVL e -> Either Int (AVL e)
takeR :: forall e. Int -> AVL e -> Either Int (AVL e)
takeR Int
n AVL e
_ | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0  = [Char] -> Either Int (AVL e)
forall a. HasCallStack => [Char] -> a
error [Char]
"takeR: Negative argument."
takeR Int
0        AVL e
E = Int -> Either Int (AVL e)
forall a b. a -> Either a b
Left Int
0       -- Treat this case specially
takeR Int
0        AVL e
_ = AVL e -> Either Int (AVL e)
forall a b. b -> Either a b
Right AVL e
forall e. AVL e
E
takeR ASINT(n) AVL e
t = case Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
takeR_ Int#
n AVL e
t L(0) of -- Tree Heights are relative!!
                   MoreTR Int#
n_         -> Int -> Either Int (AVL e)
forall a b. a -> Either a b
Left ASINT(SUBINT(n,n_))
                   AllTR (HAVL AVL e
t' Int#
_) -> AVL e -> Either Int (AVL e)
forall a b. b -> Either a b
Right AVL e
t'

-- n > 0 !!
takeR_ :: UINT -> AVL e -> UINT -> TakeResult e
takeR_ :: forall e. Int# -> AVL e -> Int# -> TakeResult e
takeR_ Int#
n  AVL e
E        Int#
_ = Int# -> TakeResult e
forall e. Int# -> TakeResult e
MoreTR Int#
n
takeR_ Int#
n (N AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
takeR__ Int#
n AVL e
l DECINT2(h) e r DECINT1(h)
takeR_ Int#
n (Z AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
takeR__ Int#
n AVL e
l DECINT1(h) e r DECINT1(h)
takeR_ Int#
n (P AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
takeR__ Int#
n AVL e
l DECINT1(h) e r DECINT2(h)

-- n > 0 !!
takeR__ :: UINT -> AVL e -> UINT -> e -> AVL e -> UINT -> TakeResult e
takeR__ :: forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
takeR__ Int#
n AVL e
l Int#
hl e
e AVL e
r Int#
hr =
 let taker :: TakeResult e
taker = Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
takeR_ Int#
n AVL e
r Int#
hr
 in case TakeResult e
taker of
    MoreTR L(0) -> let rhavl = HAVL r hr
                   in  rhavl `seq` AllTR rhavl
    MoreTR L(1) -> case l of
                   E       -> MoreTR L(0)
                   _       -> let rhavl = pushLHAVL e (HAVL r hr)
                              in  rhavl `seq` AllTR rhavl
    MoreTR Int#
n_   -> let takel :: TakeResult e
takel = Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
takeR_ DECINT1(n_) l hl
                   in case TakeResult e
takel of
                      AllTR HAVL e
havl0 -> let havl0' :: HAVL e
havl0' = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl0 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                                     in  HAVL e
havl0' HAVL e -> TakeResult e -> TakeResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeResult e
forall e. HAVL e -> TakeResult e
AllTR HAVL e
havl0'
                      TakeResult e
_           -> TakeResult e
takel
    TakeResult e
_           -> TakeResult e
taker

-- | This is a simplified version of 'splitAtL' which returns the remaining tree only (rightmost elements).
-- This function raises an error if n is negative.
--
-- If the tree size is greater than n the result is (Right r) where r contains
-- the remaining elements (r will be non-empty).
--
-- If the tree size is less than or equal to n then the result is (Left s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
dropL :: Int -> AVL e -> Either Int (AVL e)
dropL :: forall e. Int -> AVL e -> Either Int (AVL e)
dropL Int
n AVL e
_ | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0  = [Char] -> Either Int (AVL e)
forall a. HasCallStack => [Char] -> a
error [Char]
"dropL: Negative argument."
dropL Int
0        AVL e
E = Int -> Either Int (AVL e)
forall a b. a -> Either a b
Left Int
0       -- Treat this case specially
dropL Int
0        AVL e
t = AVL e -> Either Int (AVL e)
forall a b. b -> Either a b
Right AVL e
t
dropL ASINT(n) AVL e
t = case Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
dropL_ Int#
n AVL e
t L(0) of -- Tree Heights are relative!!
                   MoreTR Int#
n_        -> Int -> Either Int (AVL e)
forall a b. a -> Either a b
Left ASINT(SUBINT(n,n_))
                   AllTR (HAVL AVL e
r Int#
_) -> AVL e -> Either Int (AVL e)
forall a b. b -> Either a b
Right AVL e
r

-- n > 0 !!
-- N.B Never returns a result of form (AllTR rhavl) where rhavl is empty
dropL_ :: UINT -> AVL e -> UINT -> TakeResult e
dropL_ :: forall e. Int# -> AVL e -> Int# -> TakeResult e
dropL_ Int#
n  AVL e
E        Int#
_ = Int# -> TakeResult e
forall e. Int# -> TakeResult e
MoreTR Int#
n
dropL_ Int#
n (N AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
dropL__ Int#
n AVL e
l DECINT2(h) e r DECINT1(h)
dropL_ Int#
n (Z AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
dropL__ Int#
n AVL e
l DECINT1(h) e r DECINT1(h)
dropL_ Int#
n (P AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
dropL__ Int#
n AVL e
l DECINT1(h) e r DECINT2(h)

-- n > 0 !!
-- N.B Never returns a result of form (AllTR rhavl) where rhavl is empty
dropL__ :: UINT -> AVL e -> UINT -> e -> AVL e -> UINT -> TakeResult e
dropL__ :: forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
dropL__ Int#
n AVL e
l Int#
hl e
e AVL e
r Int#
hr =
 case Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
dropL_ Int#
n AVL e
l Int#
hl of
 MoreTR L(0) -> let rhavl = pushLHAVL e (HAVL r hr)
                in  rhavl `seq` AllTR rhavl
 MoreTR L(1) -> case r of
                E  -> MoreTR L(0)
                _  -> let rhavl = HAVL r hr in rhavl `seq` AllTR rhavl
 MoreTR Int#
n_   -> Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
dropL_ DECINT1(n_) r hr
 AllTR HAVL e
havl1 -> let havl1' :: HAVL e
havl1' = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                in  HAVL e
havl1' HAVL e -> TakeResult e -> TakeResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeResult e
forall e. HAVL e -> TakeResult e
AllTR HAVL e
havl1'

-- | This is a simplified version of 'splitAtR' which returns the remaining tree only (leftmost elements).
-- This function raises an error if n is negative.
--
-- If the tree size is greater than n the result is (Right l) where l contains
-- the remaining elements (l will be non-empty).
--
-- If the tree size is less than or equal to n then the result is (Left s), where s is tree size.
--
-- An empty tree will always yield a result of (Left 0).
--
-- Complexity: O(n)
dropR :: Int -> AVL e -> Either Int (AVL e)
dropR :: forall e. Int -> AVL e -> Either Int (AVL e)
dropR Int
n AVL e
_ | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0  = [Char] -> Either Int (AVL e)
forall a. HasCallStack => [Char] -> a
error [Char]
"dropL: Negative argument."
dropR Int
0        AVL e
E = Int -> Either Int (AVL e)
forall a b. a -> Either a b
Left Int
0       -- Treat this case specially
dropR Int
0        AVL e
t = AVL e -> Either Int (AVL e)
forall a b. b -> Either a b
Right AVL e
t
dropR ASINT(n) AVL e
t = case Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
dropR_ Int#
n AVL e
t L(0) of -- Tree Heights are relative!!
                   MoreTR Int#
n_        -> Int -> Either Int (AVL e)
forall a b. a -> Either a b
Left ASINT(SUBINT(n,n_))
                   AllTR (HAVL AVL e
l Int#
_) -> AVL e -> Either Int (AVL e)
forall a b. b -> Either a b
Right AVL e
l

-- n > 0 !!
-- N.B Never returns a result of form (AllTR lhavl) where lhavl is empty
dropR_ :: UINT -> AVL e -> UINT -> TakeResult e
dropR_ :: forall e. Int# -> AVL e -> Int# -> TakeResult e
dropR_ Int#
n  AVL e
E        Int#
_ = Int# -> TakeResult e
forall e. Int# -> TakeResult e
MoreTR Int#
n
dropR_ Int#
n (N AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
dropR__ Int#
n AVL e
l DECINT2(h) e r DECINT1(h)
dropR_ Int#
n (Z AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
dropR__ Int#
n AVL e
l DECINT1(h) e r DECINT1(h)
dropR_ Int#
n (P AVL e
l e
e AVL e
r) Int#
h = Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
dropR__ Int#
n AVL e
l DECINT1(h) e r DECINT2(h)

-- n > 0 !!
-- N.B Never returns a result of form (AllTR lhavl) where lhavl is empty
dropR__ :: UINT -> AVL e -> UINT -> e -> AVL e -> UINT -> TakeResult e
dropR__ :: forall e.
Int# -> AVL e -> Int# -> e -> AVL e -> Int# -> TakeResult e
dropR__ Int#
n AVL e
l Int#
hl e
e AVL e
r Int#
hr =
 case Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
dropR_ Int#
n AVL e
r Int#
hr of
 MoreTR L(0) -> let lhavl = pushRHAVL (HAVL l hl) e
                in  lhavl `seq` AllTR lhavl
 MoreTR L(1) -> case l of
                E  -> MoreTR L(0)
                _  -> let lhavl = HAVL l hl in lhavl `seq` AllTR lhavl
 MoreTR Int#
n_   -> Int# -> AVL e -> Int# -> TakeResult e
forall e. Int# -> AVL e -> Int# -> TakeResult e
dropR_ DECINT1(n_) l hl
 AllTR HAVL e
havl0 -> let havl0' :: HAVL e
havl0' = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                in  HAVL e
havl0' HAVL e -> TakeResult e -> TakeResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeResult e
forall e. HAVL e -> TakeResult e
AllTR HAVL e
havl0'


-- Local Datatype for results of span operations.
data SpanResult e = Some  (HAVL e) (HAVL e)     -- Two tree/height pairs. Non Strict!!
                  | TheLot                      -- The Lot satisfied

-- | Span an AVL tree from the left, using the supplied predicate. This function returns
-- a pair of trees (l,r), where l contains the leftmost consecutive elements which
-- satisfy the predicate. The leftmost element of r (if any) is the first to fail
-- the predicate. Either of the resulting trees may be empty. Element ordering is preserved.
--
-- Complexity: O(n), where n is the size of l.
spanL :: (e -> Bool) -> AVL e -> (AVL e, AVL e)
spanL :: forall e. (e -> Bool) -> AVL e -> (AVL e, AVL e)
spanL e -> Bool
p AVL e
t = case AVL e -> Int# -> SpanResult e
spanIt AVL e
t L(0) of -- Tree heights are relative
            SpanResult e
TheLot                     -> (AVL e
t, AVL e
forall e. AVL e
E)                  -- All satisfied
            Some (HAVL AVL e
l Int#
_) (HAVL AVL e
r Int#
_) -> (AVL e
l, AVL e
r)                  -- Some satisfied
 where
 spanIt :: AVL e -> Int# -> SpanResult e
spanIt   AVL e
E        Int#
_ = SpanResult e
forall e. SpanResult e
TheLot
 spanIt  (N AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> SpanResult e
spanIt_ AVL e
l DECINT2(h) e r DECINT1(h)
 spanIt  (Z AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> SpanResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT1(h)
 spanIt  (P AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> SpanResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT2(h)
 -- N.B: Never Returns (Some _ (HAVL E _)) (== TheLot)
 spanIt_ :: AVL e -> Int# -> e -> AVL e -> Int# -> SpanResult e
spanIt_ AVL e
l Int#
hl e
e AVL e
r Int#
hr =
  case AVL e -> Int# -> SpanResult e
spanIt AVL e
l Int#
hl of
  Some HAVL e
havl0 HAVL e
havl1 -> let havl1_ :: HAVL e
havl1_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                      in  HAVL e
havl1_ HAVL e -> SpanResult e -> SpanResult e
forall a b. a -> b -> b
`seq` HAVL e -> HAVL e -> SpanResult e
forall e. HAVL e -> HAVL e -> SpanResult e
Some HAVL e
havl0 HAVL e
havl1_
  SpanResult e
TheLot           -> if e -> Bool
p e
e
                      then let spanItr :: SpanResult e
spanItr = AVL e -> Int# -> SpanResult e
spanIt AVL e
r Int#
hr
                           in case SpanResult e
spanItr of
                              Some HAVL e
havl0 HAVL e
havl1 -> let havl0_ :: HAVL e
havl0_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                                                  in  HAVL e
havl0_ HAVL e -> SpanResult e -> SpanResult e
forall a b. a -> b -> b
`seq` HAVL e -> HAVL e -> SpanResult e
forall e. HAVL e -> HAVL e -> SpanResult e
Some HAVL e
havl0_ HAVL e
havl1
                              SpanResult e
_                -> SpanResult e
spanItr
                      else let rhavl :: HAVL e
rhavl = e -> HAVL e -> HAVL e
forall e. e -> HAVL e -> HAVL e
pushLHAVL e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                               lhavl :: HAVL e
lhavl = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl
                           in HAVL e
lhavl HAVL e -> SpanResult e -> SpanResult e
forall a b. a -> b -> b
`seq` HAVL e
rhavl HAVL e -> SpanResult e -> SpanResult e
forall a b. a -> b -> b
`seq` HAVL e -> HAVL e -> SpanResult e
forall e. HAVL e -> HAVL e -> SpanResult e
Some HAVL e
lhavl HAVL e
rhavl

-- | Span an AVL tree from the right, using the supplied predicate. This function returns
-- a pair of trees (l,r), where r contains the rightmost consecutive elements which
-- satisfy the predicate. The rightmost element of l (if any) is the first to fail
-- the predicate. Either of the resulting trees may be empty. Element ordering is preserved.
--
-- Complexity: O(n), where n is the size of r.
spanR :: (e -> Bool) -> AVL e -> (AVL e, AVL e)
spanR :: forall e. (e -> Bool) -> AVL e -> (AVL e, AVL e)
spanR e -> Bool
p AVL e
t = case AVL e -> Int# -> SpanResult e
spanIt AVL e
t L(0) of -- Tree heights are relative
            SpanResult e
TheLot                     -> (AVL e
forall e. AVL e
E, AVL e
t)                  -- All satisfied
            Some (HAVL AVL e
l Int#
_) (HAVL AVL e
r Int#
_) -> (AVL e
l, AVL e
r)                  -- Some satisfied
 where
 spanIt :: AVL e -> Int# -> SpanResult e
spanIt   AVL e
E        Int#
_ = SpanResult e
forall e. SpanResult e
TheLot
 spanIt  (N AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> SpanResult e
spanIt_ AVL e
l DECINT2(h) e r DECINT1(h)
 spanIt  (Z AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> SpanResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT1(h)
 spanIt  (P AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> SpanResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT2(h)
 -- N.B: Never Returns (Some (HAVL E _) _) (== TheLot)
 spanIt_ :: AVL e -> Int# -> e -> AVL e -> Int# -> SpanResult e
spanIt_ AVL e
l Int#
hl e
e AVL e
r Int#
hr =
  case AVL e -> Int# -> SpanResult e
spanIt AVL e
r Int#
hr of
  Some HAVL e
havl0 HAVL e
havl1 -> let havl0_ :: HAVL e
havl0_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                      in  HAVL e
havl0_ HAVL e -> SpanResult e -> SpanResult e
forall a b. a -> b -> b
`seq` HAVL e -> HAVL e -> SpanResult e
forall e. HAVL e -> HAVL e -> SpanResult e
Some HAVL e
havl0_ HAVL e
havl1
  SpanResult e
TheLot           -> if e -> Bool
p e
e
                      then let spanItl :: SpanResult e
spanItl = AVL e -> Int# -> SpanResult e
spanIt AVL e
l Int#
hl
                           in case SpanResult e
spanItl of
                              Some HAVL e
havl0 HAVL e
havl1 -> let havl1_ :: HAVL e
havl1_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL  HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                                                  in  HAVL e
havl1_ HAVL e -> SpanResult e -> SpanResult e
forall a b. a -> b -> b
`seq` HAVL e -> HAVL e -> SpanResult e
forall e. HAVL e -> HAVL e -> SpanResult e
Some HAVL e
havl0 HAVL e
havl1_
                              SpanResult e
_                -> SpanResult e
spanItl
                      else let lhavl :: HAVL e
lhavl = HAVL e -> e -> HAVL e
forall e. HAVL e -> e -> HAVL e
pushRHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e
                               rhavl :: HAVL e
rhavl = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr
                           in HAVL e
lhavl HAVL e -> SpanResult e -> SpanResult e
forall a b. a -> b -> b
`seq` HAVL e
rhavl HAVL e -> SpanResult e -> SpanResult e
forall a b. a -> b -> b
`seq` HAVL e -> HAVL e -> SpanResult e
forall e. HAVL e -> HAVL e -> SpanResult e
Some HAVL e
lhavl HAVL e
rhavl

-- Local Datatype for results of takeWhile/DropWhile operations.
data TakeWhileResult e = SomeTW (HAVL e)
                       | TheLotTW

-- | This is a simplified version of 'spanL' which does not return the remaining tree
-- The result is the leftmost consecutive sequence of elements which satisfy the
-- supplied predicate (which may be empty).
--
-- Complexity: O(n), where n is the size of the result.
takeWhileL :: (e -> Bool) -> AVL e -> AVL e
takeWhileL :: forall e. (e -> Bool) -> AVL e -> AVL e
takeWhileL e -> Bool
p AVL e
t = case AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
t L(0) of    -- Tree heights are relative
                 TakeWhileResult e
TheLotTW          -> AVL e
t   -- All satisfied
                 SomeTW (HAVL AVL e
l Int#
_) -> AVL e
l   -- Some satisfied
 where
 spanIt :: AVL e -> Int# -> TakeWhileResult e
spanIt   AVL e
E        Int#
_ = TakeWhileResult e
forall e. TakeWhileResult e
TheLotTW
 spanIt  (N AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT2(h) e r DECINT1(h)
 spanIt  (Z AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT1(h)
 spanIt  (P AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT2(h)
 spanIt_ :: AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l Int#
hl e
e AVL e
r Int#
hr =
  let twl :: TakeWhileResult e
twl = AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
l Int#
hl
  in case TakeWhileResult e
twl of
     TakeWhileResult e
TheLotTW -> if e -> Bool
p e
e
                 then let twr :: TakeWhileResult e
twr = AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
r Int#
hr
                      in case TakeWhileResult e
twr of
                      SomeTW HAVL e
havl0 -> let havl0_ :: HAVL e
havl0_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                                      in  HAVL e
havl0_ HAVL e -> TakeWhileResult e -> TakeWhileResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeWhileResult e
forall e. HAVL e -> TakeWhileResult e
SomeTW HAVL e
havl0_
                      TakeWhileResult e
_            -> TakeWhileResult e
twr
                 else let lhavl :: HAVL e
lhavl = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl in HAVL e
lhavl HAVL e -> TakeWhileResult e -> TakeWhileResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeWhileResult e
forall e. HAVL e -> TakeWhileResult e
SomeTW HAVL e
lhavl
     TakeWhileResult e
_        -> TakeWhileResult e
twl

-- | This is a simplified version of 'spanR' which does not return the remaining tree
-- The result is the rightmost consecutive sequence of elements which satisfy the
-- supplied predicate (which may be empty).
--
-- Complexity: O(n), where n is the size of the result.
takeWhileR :: (e -> Bool) -> AVL e -> AVL e
takeWhileR :: forall e. (e -> Bool) -> AVL e -> AVL e
takeWhileR e -> Bool
p AVL e
t = case AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
t L(0) of    -- Tree heights are relative
                 TakeWhileResult e
TheLotTW          -> AVL e
t   -- All satisfied
                 SomeTW (HAVL AVL e
r Int#
_) -> AVL e
r   -- Some satisfied
 where
 spanIt :: AVL e -> Int# -> TakeWhileResult e
spanIt   AVL e
E        Int#
_ = TakeWhileResult e
forall e. TakeWhileResult e
TheLotTW
 spanIt  (N AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT2(h) e r DECINT1(h)
 spanIt  (Z AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT1(h)
 spanIt  (P AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT2(h)
 spanIt_ :: AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l Int#
hl e
e AVL e
r Int#
hr =
  let twr :: TakeWhileResult e
twr = AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
r Int#
hr
  in case TakeWhileResult e
twr of
     TakeWhileResult e
TheLotTW -> if e -> Bool
p e
e
                 then let twl :: TakeWhileResult e
twl = AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
l Int#
hl
                      in case TakeWhileResult e
twl of
                      SomeTW HAVL e
havl1 -> let havl1_ :: HAVL e
havl1_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                                      in  HAVL e
havl1_ HAVL e -> TakeWhileResult e -> TakeWhileResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeWhileResult e
forall e. HAVL e -> TakeWhileResult e
SomeTW HAVL e
havl1_
                      TakeWhileResult e
_            -> TakeWhileResult e
twl
                 else let rhavl :: HAVL e
rhavl = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr in HAVL e
rhavl HAVL e -> TakeWhileResult e -> TakeWhileResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeWhileResult e
forall e. HAVL e -> TakeWhileResult e
SomeTW HAVL e
rhavl
     TakeWhileResult e
_        -> TakeWhileResult e
twr

-- | This is a simplified version of 'spanL' which does not return the tree containing
-- the elements which satisfy the supplied predicate.
-- The result is a tree whose leftmost element is the first to fail the predicate, starting from
-- the left (which may be empty).
--
-- Complexity: O(n), where n is the number of elements dropped.
dropWhileL :: (e -> Bool) -> AVL e -> AVL e
dropWhileL :: forall e. (e -> Bool) -> AVL e -> AVL e
dropWhileL e -> Bool
p AVL e
t = case AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
t L(0) of   -- Tree heights are relative
                 TakeWhileResult e
TheLotTW          -> AVL e
forall e. AVL e
E  -- All satisfied
                 SomeTW (HAVL AVL e
r Int#
_) -> AVL e
r  -- Some satisfied
 where
 spanIt :: AVL e -> Int# -> TakeWhileResult e
spanIt   AVL e
E        Int#
_ = TakeWhileResult e
forall e. TakeWhileResult e
TheLotTW
 spanIt  (N AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT2(h) e r DECINT1(h)
 spanIt  (Z AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT1(h)
 spanIt  (P AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT2(h)
 spanIt_ :: AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l Int#
hl e
e AVL e
r Int#
hr =
  case AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
l Int#
hl of
  SomeTW HAVL e
havl1 -> let havl1_ :: HAVL e
havl1_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                  in  HAVL e
havl1_ HAVL e -> TakeWhileResult e -> TakeWhileResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeWhileResult e
forall e. HAVL e -> TakeWhileResult e
SomeTW HAVL e
havl1_
  TakeWhileResult e
TheLotTW     -> if e -> Bool
p e
e
                  then AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
r Int#
hr
                  else let rhavl :: HAVL e
rhavl = e -> HAVL e -> HAVL e
forall e. e -> HAVL e -> HAVL e
pushLHAVL e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                       in HAVL e
rhavl HAVL e -> TakeWhileResult e -> TakeWhileResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeWhileResult e
forall e. HAVL e -> TakeWhileResult e
SomeTW HAVL e
rhavl

-- | This is a simplified version of 'spanR' which does not return the tree containing
-- the elements which satisfy the supplied predicate.
-- The result is a tree whose rightmost element is the first to fail the predicate, starting from
-- the right (which may be empty).
--
-- Complexity: O(n), where n is the number of elements dropped.
dropWhileR :: (e -> Bool) -> AVL e -> AVL e
dropWhileR :: forall e. (e -> Bool) -> AVL e -> AVL e
dropWhileR e -> Bool
p AVL e
t = case AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
t L(0) of   -- Tree heights are relative
                 TakeWhileResult e
TheLotTW          -> AVL e
forall e. AVL e
E  -- All satisfied
                 SomeTW (HAVL AVL e
l Int#
_) -> AVL e
l  -- Some satisfied
 where
 spanIt :: AVL e -> Int# -> TakeWhileResult e
spanIt   AVL e
E        Int#
_ = TakeWhileResult e
forall e. TakeWhileResult e
TheLotTW
 spanIt  (N AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT2(h) e r DECINT1(h)
 spanIt  (Z AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT1(h)
 spanIt  (P AVL e
l e
e AVL e
r) Int#
h = AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l DECINT1(h) e r DECINT2(h)
 spanIt_ :: AVL e -> Int# -> e -> AVL e -> Int# -> TakeWhileResult e
spanIt_ AVL e
l Int#
hl e
e AVL e
r Int#
hr =
  case AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
r Int#
hr of
  SomeTW HAVL e
havl0 -> let havl0_ :: HAVL e
havl0_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                  in  HAVL e
havl0_ HAVL e -> TakeWhileResult e -> TakeWhileResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeWhileResult e
forall e. HAVL e -> TakeWhileResult e
SomeTW HAVL e
havl0_
  TakeWhileResult e
TheLotTW     -> if e -> Bool
p e
e
                  then AVL e -> Int# -> TakeWhileResult e
spanIt AVL e
l Int#
hl
                  else let lhavl :: HAVL e
lhavl = HAVL e -> e -> HAVL e
forall e. HAVL e -> e -> HAVL e
pushRHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e
                       in HAVL e
lhavl HAVL e -> TakeWhileResult e -> TakeWhileResult e
forall a b. a -> b -> b
`seq` HAVL e -> TakeWhileResult e
forall e. HAVL e -> TakeWhileResult e
SomeTW HAVL e
lhavl

-- | Rotate an AVL tree one place left. This function pops the leftmost element and pushes into
-- the rightmost position. An empty tree yields an empty tree.
--
-- Complexity: O(log n)
rotateL :: AVL e -> AVL e
rotateL :: forall e. AVL e -> AVL e
rotateL  AVL e
E        = AVL e
forall e. AVL e
E
rotateL (N AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLN AVL e
l e
e AVL e
r of UBT2(e_,t) -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e
pushR AVL e
t e
e_
rotateL (Z AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLZ AVL e
l e
e AVL e
r of UBT2(e_,t) -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e
pushR AVL e
t e
e_
rotateL (P AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLP AVL e
l e
e AVL e
r of UBT2(e_,t) -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e
pushR AVL e
t e
e_

-- | Rotate an AVL tree one place right. This function pops the rightmost element and pushes into
-- the leftmost position. An empty tree yields an empty tree.
--
-- Complexity: O(log n)
rotateR :: AVL e -> AVL e
rotateR :: forall e. AVL e -> AVL e
rotateR  AVL e
E        = AVL e
forall e. AVL e
E
rotateR (N AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRN AVL e
l e
e AVL e
r of UBT2(t,e_) -> e -> AVL e -> AVL e
forall e. e -> AVL e -> AVL e
pushL e
e_ AVL e
t
rotateR (Z AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRZ AVL e
l e
e AVL e
r of UBT2(t,e_) -> e -> AVL e -> AVL e
forall e. e -> AVL e -> AVL e
pushL e
e_ AVL e
t
rotateR (P AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRP AVL e
l e
e AVL e
r of UBT2(t,e_) -> e -> AVL e -> AVL e
forall e. e -> AVL e -> AVL e
pushL e
e_ AVL e
t

-- | Similar to 'rotateL', but returns the rotated element. This function raises an error if
-- applied to an empty tree.
--
-- Complexity: O(log n)
popRotateL :: AVL e -> (e, AVL e)
popRotateL :: forall e. AVL e -> (e, AVL e)
popRotateL  AVL e
E        = [Char] -> (e, AVL e)
forall a. HasCallStack => [Char] -> a
error [Char]
"popRotateL: Empty tree."
popRotateL (N AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLN AVL e
l e
e AVL e
r of UBT2(e_,t) -> e -> AVL e -> (e, AVL e)
forall e. e -> AVL e -> (e, AVL e)
popRotateL' e
e_ AVL e
t
popRotateL (Z AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLZ AVL e
l e
e AVL e
r of UBT2(e_,t) -> e -> AVL e -> (e, AVL e)
forall e. e -> AVL e -> (e, AVL e)
popRotateL' e
e_ AVL e
t
popRotateL (P AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# e, AVL e #)
forall e. AVL e -> e -> AVL e -> (# e, AVL e #)
popLP AVL e
l e
e AVL e
r of UBT2(e_,t) -> e -> AVL e -> (e, AVL e)
forall e. e -> AVL e -> (e, AVL e)
popRotateL' e
e_ AVL e
t
popRotateL' :: e -> AVL e -> (e, AVL e)
popRotateL' :: forall e. e -> AVL e -> (e, AVL e)
popRotateL' e
e AVL e
t = let t' :: AVL e
t' = AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e
pushR AVL e
t e
e in AVL e
t' AVL e -> (e, AVL e) -> (e, AVL e)
forall a b. a -> b -> b
`seq` (e
e,AVL e
t')

-- | Similar to 'rotateR', but returns the rotated element. This function raises an error if
-- applied to an empty tree.
--
-- Complexity: O(log n)
popRotateR :: AVL e -> (AVL e, e)
popRotateR :: forall e. AVL e -> (AVL e, e)
popRotateR  AVL e
E        = [Char] -> (AVL e, e)
forall a. HasCallStack => [Char] -> a
error [Char]
"popRotateR: Empty tree."
popRotateR (N AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRN AVL e
l e
e AVL e
r of UBT2(t,e_) -> AVL e -> e -> (AVL e, e)
forall e. AVL e -> e -> (AVL e, e)
popRotateR' AVL e
t e
e_
popRotateR (Z AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRZ AVL e
l e
e AVL e
r of UBT2(t,e_) -> AVL e -> e -> (AVL e, e)
forall e. AVL e -> e -> (AVL e, e)
popRotateR' AVL e
t e
e_
popRotateR (P AVL e
l e
e AVL e
r) = case AVL e -> e -> AVL e -> (# AVL e, e #)
forall e. AVL e -> e -> AVL e -> (# AVL e, e #)
popRP AVL e
l e
e AVL e
r of UBT2(t,e_) -> AVL e -> e -> (AVL e, e)
forall e. AVL e -> e -> (AVL e, e)
popRotateR' AVL e
t e
e_
popRotateR' :: AVL e -> e -> (AVL e, e)
popRotateR' :: forall e. AVL e -> e -> (AVL e, e)
popRotateR' AVL e
t e
e = let t' :: AVL e
t' = e -> AVL e -> AVL e
forall e. e -> AVL e -> AVL e
pushL e
e AVL e
t in AVL e
t' AVL e -> (AVL e, e) -> (AVL e, e)
forall a b. a -> b -> b
`seq` (AVL e
t',e
e)


-- | Rotate an AVL tree left by n places. If s is the size of the tree then ordinarily n
-- should be in the range [0..s-1]. However, this function will deliver a correct result
-- for any n (n\<0 or n\>=s), the actual rotation being given by (n \`mod\` s) in such cases.
-- The result of rotating an empty tree is an empty tree.
--
-- Complexity: O(n)
rotateByL :: AVL e -> Int -> AVL e
rotateByL :: forall e. AVL e -> Int -> AVL e
rotateByL AVL e
t ASINT(n) = case Int# -> Int# -> Ordering
COMPAREUINT Int#
n L(0) of
                       Ordering
LT -> AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e
rotateByR__ AVL e
t NEGATE(n)
                       Ordering
EQ -> AVL e
t
                       Ordering
GT -> AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e
rotateByL__ AVL e
t Int#
n
-- n>=0!!
{-# INLINE rotateByL_ #-}
rotateByL_ :: AVL e -> UINT -> AVL e
rotateByL_ :: forall e. AVL e -> Int# -> AVL e
rotateByL_ AVL e
t L(0) AVL e
= t
rotateByL_ AVL e
t Int#
n    = AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e
rotateByL__ AVL e
t Int#
n
-- n>0!!
rotateByL__ :: AVL e -> UINT -> AVL e
rotateByL__ :: forall e. AVL e -> Int# -> AVL e
rotateByL__ AVL e
E Int#
_ = AVL e
forall e. AVL e
E
rotateByL__ AVL e
t Int#
n = case Int# -> AVL e -> Int# -> SplitResult e
forall e. Int# -> AVL e -> Int# -> SplitResult e
splitL Int#
n AVL e
t L(0) of -- Tree Heights are relative!!
                  More L(0)       -> t
                  More Int#
m          -> let s :: Int#
s  = SUBINT(n,m)      -- Actual size of tree, > 0!!
                                         n_ :: Int#
n_ = _MODULO_(n,s)    -- Actual shift required, 0..s-1
                                     in if Int# -> Bool
isTrue# (ADDINT(n_,n_) LEQ s)
                                        then AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e
rotateByL_  AVL e
t Int#
n_            -- n_ may be 0 !!
                                        else AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e
rotateByR__ AVL e
t SUBINT(s,n_)  -- (s-n_) can't be 0
                  All (HAVL AVL e
l Int#
hl) (HAVL AVL e
r Int#
hr) -> AVL e -> Int# -> AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e -> Int# -> AVL e
joinH' AVL e
r Int#
hr AVL e
l Int#
hl


-- | Rotate an AVL tree right by n places. If s is the size of the tree then ordinarily n
-- should be in the range [0..s-1]. However, this function will deliver a correct result
-- for any n (n\<0 or n\>=s), the actual rotation being given by (n \`mod\` s) in such cases.
-- The result of rotating an empty tree is an empty tree.
--
-- Complexity: O(n)
rotateByR :: AVL e -> Int -> AVL e
rotateByR :: forall e. AVL e -> Int -> AVL e
rotateByR AVL e
t ASINT(n) = case Int# -> Int# -> Ordering
COMPAREUINT Int#
n L(0) of
                       Ordering
LT -> AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e
rotateByL__ AVL e
t NEGATE(n)
                       Ordering
EQ -> AVL e
t
                       Ordering
GT -> AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e
rotateByR__ AVL e
t Int#
n
-- n>=0!!
{-# INLINE rotateByR_ #-}
rotateByR_ :: AVL e -> UINT -> AVL e
rotateByR_ :: forall e. AVL e -> Int# -> AVL e
rotateByR_ AVL e
t L(0) AVL e
= t
rotateByR_ AVL e
t Int#
n    = AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e
rotateByR__ AVL e
t Int#
n
-- n>0!!
rotateByR__ :: AVL e -> UINT -> AVL e
rotateByR__ :: forall e. AVL e -> Int# -> AVL e
rotateByR__ AVL e
E Int#
_ = AVL e
forall e. AVL e
E
rotateByR__ AVL e
t Int#
n = case Int# -> AVL e -> Int# -> SplitResult e
forall e. Int# -> AVL e -> Int# -> SplitResult e
splitR Int#
n AVL e
t L(0) of -- Tree Heights are relative!!
                  More L(0)       -> t
                  More Int#
m          -> let s :: Int#
s  = SUBINT(n,m)    -- Actual size of tree, > 0!!
                                         n_ :: Int#
n_ = _MODULO_(n,s)    -- Actual shift required, 0..s-1
                                     in if Int# -> Bool
isTrue# (ADDINT(n_,n_) LEQ s)
                                        then AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e
rotateByR_  AVL e
t Int#
n_         -- n_ may be 0 !!
                                        else AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e
rotateByL__ AVL e
t SUBINT(s,n_)  -- (s-n_) can_t be 0
                  All (HAVL AVL e
l Int#
hl) (HAVL AVL e
r Int#
hr) -> AVL e -> Int# -> AVL e -> Int# -> AVL e
forall e. AVL e -> Int# -> AVL e -> Int# -> AVL e
joinH' AVL e
r Int#
hr AVL e
l Int#
hl


-- | Divide a sorted AVL tree into left and right sorted trees (l,r), such that l contains all the
-- elements less than or equal to according to the supplied selector and r contains all the elements greater than
-- according to the supplied selector.
--
-- Complexity: O(log n)
forkL :: (e -> Ordering) -> AVL e -> (AVL e, AVL e)
forkL :: forall e. (e -> Ordering) -> AVL e -> (AVL e, AVL e)
forkL e -> Ordering
c AVL e
avl = let (HAVL AVL e
l Int#
_,HAVL AVL e
r Int#
_) = Int# -> AVL e -> (HAVL e, HAVL e)
forkL_ L(0) avl -- Tree heights are relative
                 in (AVL e
l,AVL e
r)
 where
 forkL_ :: Int# -> AVL e -> (HAVL e, HAVL e)
forkL_ Int#
h  AVL e
E        = (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
forall e. AVL e
E Int#
h, AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
forall e. AVL e
E Int#
h)
 forkL_ Int#
h (N AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, HAVL e)
forkL__ AVL e
l DECINT2(h) e r DECINT1(h)
 forkL_ Int#
h (Z AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, HAVL e)
forkL__ AVL e
l DECINT1(h) e r DECINT1(h)
 forkL_ Int#
h (P AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, HAVL e)
forkL__ AVL e
l DECINT1(h) e r DECINT2(h)
 forkL__ :: AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, HAVL e)
forkL__ AVL e
l Int#
hl e
e AVL e
r Int#
hr = case e -> Ordering
c e
e of
                          -- Current element > pivot, so goes in right half
                          Ordering
LT -> let (HAVL e
havl0,HAVL e
havl1) = Int# -> AVL e -> (HAVL e, HAVL e)
forkL_ Int#
hl AVL e
l
                                    havl1_ :: HAVL e
havl1_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                                in  HAVL e
havl1_ HAVL e -> (HAVL e, HAVL e) -> (HAVL e, HAVL e)
forall a b. a -> b -> b
`seq` (HAVL e
havl0, HAVL e
havl1_)
                          -- Current element = pivot, so goes in left half and stop here
                          Ordering
EQ -> let lhavl :: HAVL e
lhavl = HAVL e -> e -> HAVL e
forall e. HAVL e -> e -> HAVL e
pushRHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e
                                    rhavl :: HAVL e
rhavl = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr
                                in  HAVL e
lhavl HAVL e -> (HAVL e, HAVL e) -> (HAVL e, HAVL e)
forall a b. a -> b -> b
`seq` HAVL e
rhavl HAVL e -> (HAVL e, HAVL e) -> (HAVL e, HAVL e)
forall a b. a -> b -> b
`seq` (HAVL e
lhavl,HAVL e
rhavl)
                          -- Current element < pivot, so goes in left half
                          Ordering
GT -> let (HAVL e
havl0,HAVL e
havl1) = Int# -> AVL e -> (HAVL e, HAVL e)
forkL_ Int#
hr AVL e
r
                                    havl0_ :: HAVL e
havl0_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                                in  HAVL e
havl0_ HAVL e -> (HAVL e, HAVL e) -> (HAVL e, HAVL e)
forall a b. a -> b -> b
`seq` (HAVL e
havl0_, HAVL e
havl1)

-- | Divide a sorted AVL tree into left and right sorted trees (l,r), such that l contains all the
-- elements less than supplied selector and r contains all the elements greater than or equal to the
-- supplied selector.
--
-- Complexity: O(log n)
forkR :: (e -> Ordering) -> AVL e -> (AVL e, AVL e)
forkR :: forall e. (e -> Ordering) -> AVL e -> (AVL e, AVL e)
forkR e -> Ordering
c AVL e
avl = let (HAVL AVL e
l Int#
_,HAVL AVL e
r Int#
_) = Int# -> AVL e -> (HAVL e, HAVL e)
forkR_ L(0) avl  -- Tree heights are relative
                 in (AVL e
l,AVL e
r)
 where
 forkR_ :: Int# -> AVL e -> (HAVL e, HAVL e)
forkR_ Int#
h  AVL e
E        = (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
forall e. AVL e
E Int#
h, AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
forall e. AVL e
E Int#
h)
 forkR_ Int#
h (N AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, HAVL e)
forkR__ AVL e
l DECINT2(h) e r DECINT1(h)
 forkR_ Int#
h (Z AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, HAVL e)
forkR__ AVL e
l DECINT1(h) e r DECINT1(h)
 forkR_ Int#
h (P AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, HAVL e)
forkR__ AVL e
l DECINT1(h) e r DECINT2(h)
 forkR__ :: AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, HAVL e)
forkR__ AVL e
l Int#
hl e
e AVL e
r Int#
hr = case e -> Ordering
c e
e of
                          -- Current element > pivot, so goes in right half
                          Ordering
LT -> let (HAVL e
havl0,HAVL e
havl1) = Int# -> AVL e -> (HAVL e, HAVL e)
forkR_ Int#
hl AVL e
l
                                    havl1_ :: HAVL e
havl1_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                                in  HAVL e
havl1_ HAVL e -> (HAVL e, HAVL e) -> (HAVL e, HAVL e)
forall a b. a -> b -> b
`seq` (HAVL e
havl0, HAVL e
havl1_)
                          -- Current element = pivot, so goes in right half and stop here
                          Ordering
EQ -> let rhavl :: HAVL e
rhavl = e -> HAVL e -> HAVL e
forall e. e -> HAVL e -> HAVL e
pushLHAVL e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                                    lhavl :: HAVL e
lhavl = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl
                                in  HAVL e
lhavl HAVL e -> (HAVL e, HAVL e) -> (HAVL e, HAVL e)
forall a b. a -> b -> b
`seq` HAVL e
rhavl HAVL e -> (HAVL e, HAVL e) -> (HAVL e, HAVL e)
forall a b. a -> b -> b
`seq` (HAVL e
lhavl, HAVL e
rhavl)
                          -- Current element < pivot, so goes in left half
                          Ordering
GT -> let (HAVL e
havl0,HAVL e
havl1) = Int# -> AVL e -> (HAVL e, HAVL e)
forkR_ Int#
hr AVL e
r
                                    havl0_ :: HAVL e
havl0_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                                in  HAVL e
havl0_ HAVL e -> (HAVL e, HAVL e) -> (HAVL e, HAVL e)
forall a b. a -> b -> b
`seq` (HAVL e
havl0_, HAVL e
havl1)


-- | Similar to 'forkL' and 'forkR', but returns any equal element found (instead of
-- incorporating it into the left or right tree results respectively).
--
-- Complexity: O(log n)
fork :: (e -> COrdering a) -> AVL e -> (AVL e, Maybe a, AVL e)
fork :: forall e a. (e -> COrdering a) -> AVL e -> (AVL e, Maybe a, AVL e)
fork e -> COrdering a
c AVL e
avl = let (HAVL AVL e
l Int#
_, Maybe a
mba, HAVL AVL e
r Int#
_) = Int# -> AVL e -> (HAVL e, Maybe a, HAVL e)
fork_ L(0) avl -- Tree heights are relative
                in (AVL e
l,Maybe a
mba,AVL e
r)
 where
 fork_ :: Int# -> AVL e -> (HAVL e, Maybe a, HAVL e)
fork_ Int#
h  AVL e
E        = (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
forall e. AVL e
E Int#
h, Maybe a
forall a. Maybe a
Nothing, AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
forall e. AVL e
E Int#
h)
 fork_ Int#
h (N AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, Maybe a, HAVL e)
fork__ AVL e
l DECINT2(h) e r DECINT1(h)
 fork_ Int#
h (Z AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, Maybe a, HAVL e)
fork__ AVL e
l DECINT1(h) e r DECINT1(h)
 fork_ Int#
h (P AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, Maybe a, HAVL e)
fork__ AVL e
l DECINT1(h) e r DECINT2(h)
 fork__ :: AVL e -> Int# -> e -> AVL e -> Int# -> (HAVL e, Maybe a, HAVL e)
fork__ AVL e
l Int#
hl e
e AVL e
r Int#
hr = case e -> COrdering a
c e
e of
                          -- Current element > pivot
                          COrdering a
Lt   -> let (HAVL e
havl0,Maybe a
mba,HAVL e
havl1) = Int# -> AVL e -> (HAVL e, Maybe a, HAVL e)
fork_ Int#
hl AVL e
l
                                      havl1_ :: HAVL e
havl1_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                                  in  HAVL e
havl1_ HAVL e -> (HAVL e, Maybe a, HAVL e) -> (HAVL e, Maybe a, HAVL e)
forall a b. a -> b -> b
`seq` (HAVL e
havl0, Maybe a
mba, HAVL e
havl1_)
                          -- Current element = pivot
                          Eq a
a -> let lhavl :: HAVL e
lhavl = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl
                                      rhavl :: HAVL e
rhavl = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr
                                  in  HAVL e
lhavl HAVL e -> (HAVL e, Maybe a, HAVL e) -> (HAVL e, Maybe a, HAVL e)
forall a b. a -> b -> b
`seq` HAVL e
rhavl HAVL e -> (HAVL e, Maybe a, HAVL e) -> (HAVL e, Maybe a, HAVL e)
forall a b. a -> b -> b
`seq` (HAVL e
lhavl, a -> Maybe a
forall a. a -> Maybe a
Just a
a, HAVL e
rhavl)
                          -- Current element < pivot
                          COrdering a
Gt   -> let (HAVL e
havl0,Maybe a
mba,HAVL e
havl1) = Int# -> AVL e -> (HAVL e, Maybe a, HAVL e)
fork_ Int#
hr AVL e
r
                                      havl0_ :: HAVL e
havl0_ = HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0
                                  in  HAVL e
havl0_ HAVL e -> (HAVL e, Maybe a, HAVL e) -> (HAVL e, Maybe a, HAVL e)
forall a b. a -> b -> b
`seq` (HAVL e
havl0_, Maybe a
mba, HAVL e
havl1)

-- | This is a simplified version of 'forkL' which returns a sorted tree containing
-- only those elements which are less than or equal to according to the supplied selector.
-- This function also has the synonym 'dropGT'.
--
-- Complexity: O(log n)
takeLE :: (e -> Ordering) -> AVL e -> AVL e
takeLE :: forall e. (e -> Ordering) -> AVL e -> AVL e
takeLE e -> Ordering
c AVL e
avl = let HAVL AVL e
l Int#
_ = Int# -> AVL e -> HAVL e
forkL_ L(0) avl -- Tree heights are relative
                  in AVL e
l
 where
 forkL_ :: Int# -> AVL e -> HAVL e
forkL_ Int#
h  AVL e
E        = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
forall e. AVL e
E Int#
h
 forkL_ Int#
h (N AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT2(h) e r DECINT1(h)
 forkL_ Int#
h (Z AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT1(h) e r DECINT1(h)
 forkL_ Int#
h (P AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT1(h) e r DECINT2(h)
 forkL__ :: AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l Int#
hl e
e AVL e
r Int#
hr = case e -> Ordering
c e
e of
                          Ordering
LT -> Int# -> AVL e -> HAVL e
forkL_ Int#
hl AVL e
l
                          Ordering
EQ -> HAVL e -> e -> HAVL e
forall e. HAVL e -> e -> HAVL e
pushRHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e
                          Ordering
GT -> let havl0 :: HAVL e
havl0 = Int# -> AVL e -> HAVL e
forkL_ Int#
hr AVL e
r
                                in  HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0


-- | A synonym for 'takeLE'.
--
-- Complexity: O(log n)
dropGT :: (e -> Ordering) -> AVL e -> AVL e
dropGT :: forall e. (e -> Ordering) -> AVL e -> AVL e
dropGT = (e -> Ordering) -> AVL e -> AVL e
forall e. (e -> Ordering) -> AVL e -> AVL e
takeLE
{-# INLINE dropGT #-}

-- | This is a simplified version of 'forkL' which returns a sorted tree containing
-- only those elements which are greater according to the supplied selector.
-- This function also has the synonym 'dropLE'.
--
-- Complexity: O(log n)
takeGT :: (e -> Ordering) -> AVL e -> AVL e
takeGT :: forall e. (e -> Ordering) -> AVL e -> AVL e
takeGT e -> Ordering
c AVL e
avl = let HAVL AVL e
r Int#
_ = Int# -> AVL e -> HAVL e
forkL_ L(0) avl -- Tree heights are relative
                  in AVL e
r
 where
 forkL_ :: Int# -> AVL e -> HAVL e
forkL_ Int#
h  AVL e
E        = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
forall e. AVL e
E Int#
h
 forkL_ Int#
h (N AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT2(h) e r DECINT1(h)
 forkL_ Int#
h (Z AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT1(h) e r DECINT1(h)
 forkL_ Int#
h (P AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT1(h) e r DECINT2(h)
 forkL__ :: AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l Int#
hl e
e AVL e
r Int#
hr = case e -> Ordering
c e
e of
                          Ordering
LT -> let havl1 :: HAVL e
havl1  = Int# -> AVL e -> HAVL e
forkL_ Int#
hl AVL e
l
                                in  HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                          Ordering
EQ -> AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr
                          Ordering
GT -> Int# -> AVL e -> HAVL e
forkL_ Int#
hr AVL e
r

-- | A synonym for 'takeGT'.
--
-- Complexity: O(log n)
dropLE :: (e -> Ordering) -> AVL e -> AVL e
dropLE :: forall e. (e -> Ordering) -> AVL e -> AVL e
dropLE = (e -> Ordering) -> AVL e -> AVL e
forall e. (e -> Ordering) -> AVL e -> AVL e
takeGT
{-# INLINE dropLE #-}

-- | This is a simplified version of 'forkR' which returns a sorted tree containing
-- only those elements which are less than according to the supplied selector.
-- This function also has the synonym 'dropGE'.
--
-- Complexity: O(log n)
takeLT :: (e -> Ordering) -> AVL e -> AVL e
takeLT :: forall e. (e -> Ordering) -> AVL e -> AVL e
takeLT e -> Ordering
c AVL e
avl = let HAVL AVL e
l Int#
_ = Int# -> AVL e -> HAVL e
forkL_ L(0) avl -- Tree heights are relative
                  in AVL e
l
 where
 forkL_ :: Int# -> AVL e -> HAVL e
forkL_ Int#
h  AVL e
E        = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
forall e. AVL e
E Int#
h
 forkL_ Int#
h (N AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT2(h) e r DECINT1(h)
 forkL_ Int#
h (Z AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT1(h) e r DECINT1(h)
 forkL_ Int#
h (P AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT1(h) e r DECINT2(h)
 forkL__ :: AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l Int#
hl e
e AVL e
r Int#
hr = case e -> Ordering
c e
e of
                          Ordering
LT -> Int# -> AVL e -> HAVL e
forkL_ Int#
hl AVL e
l
                          Ordering
EQ -> AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl
                          Ordering
GT -> let havl0 :: HAVL e
havl0 = Int# -> AVL e -> HAVL e
forkL_ Int#
hr AVL e
r
                                in  HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
l Int#
hl) e
e HAVL e
havl0


-- | A synonym for 'takeLT'.
--
-- Complexity: O(log n)
dropGE :: (e -> Ordering) -> AVL e -> AVL e
dropGE :: forall e. (e -> Ordering) -> AVL e -> AVL e
dropGE = (e -> Ordering) -> AVL e -> AVL e
forall e. (e -> Ordering) -> AVL e -> AVL e
takeLT
{-# INLINE dropGE #-}

-- | This is a simplified version of 'forkR' which returns a sorted tree containing
-- only those elements which are greater or equal to according to the supplied selector.
-- This function also has the synonym 'dropLT'.
--
-- Complexity: O(log n)
takeGE :: (e -> Ordering) -> AVL e -> AVL e
takeGE :: forall e. (e -> Ordering) -> AVL e -> AVL e
takeGE e -> Ordering
c AVL e
avl = let HAVL AVL e
r Int#
_ = Int# -> AVL e -> HAVL e
forkL_ L(0) avl -- Tree heights are relative
               in AVL e
r
 where
 forkL_ :: Int# -> AVL e -> HAVL e
forkL_ Int#
h  AVL e
E        = AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
forall e. AVL e
E Int#
h
 forkL_ Int#
h (N AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT2(h) e r DECINT1(h)
 forkL_ Int#
h (Z AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT1(h) e r DECINT1(h)
 forkL_ Int#
h (P AVL e
l e
e AVL e
r) = AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l DECINT1(h) e r DECINT2(h)
 forkL__ :: AVL e -> Int# -> e -> AVL e -> Int# -> HAVL e
forkL__ AVL e
l Int#
hl e
e AVL e
r Int#
hr = case e -> Ordering
c e
e of
                          Ordering
LT -> let havl1 :: HAVL e
havl1  = Int# -> AVL e -> HAVL e
forkL_ Int#
hl AVL e
l
                                in  HAVL e -> e -> HAVL e -> HAVL e
forall e. HAVL e -> e -> HAVL e -> HAVL e
spliceHAVL HAVL e
havl1 e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                          Ordering
EQ -> e -> HAVL e -> HAVL e
forall e. e -> HAVL e -> HAVL e
pushLHAVL e
e (AVL e -> Int# -> HAVL e
forall e. AVL e -> Int# -> HAVL e
HAVL AVL e
r Int#
hr)
                          Ordering
GT -> Int# -> AVL e -> HAVL e
forkL_ Int#
hr AVL e
r

-- | A synonym for 'takeGE'.
--
-- Complexity: O(log n)
dropLT :: (e -> Ordering) -> AVL e -> AVL e
dropLT :: forall e. (e -> Ordering) -> AVL e -> AVL e
dropLT = (e -> Ordering) -> AVL e -> AVL e
forall e. (e -> Ordering) -> AVL e -> AVL e
takeGE
{-# INLINE dropLT #-}