-- |
-- Copyright   :  (c) Adrian Hey 2004,2005
-- License     :  BSD3
--
{-# OPTIONS_HADDOCK hide #-}
module Data.Tree.AVL.Write
(-- * Writing to AVL trees
 -- | These functions alter the content of a tree (values of tree elements) but not the structure
 -- of a tree.

 -- ** Writing to extreme left or right
 -- | I'm not sure these are likely to be much use in practice, but they're
 -- simple enough to implement so are included for the sake of completeness.
 writeL,tryWriteL,writeR,tryWriteR,

 -- ** Writing to /sorted/ trees
 write,writeFast,tryWrite,writeMaybe,tryWriteMaybe
) where

import Prelude -- so haddock finds the symbols there

import Data.COrdering
import Data.Tree.AVL.Internals.Types(AVL(..))
import Data.Tree.AVL.BinPath(BinPath(..),openPathWith,writePath)

---------------------------------------------------------------------------
--                       writeL, tryWriteL                               --
---------------------------------------------------------------------------
-- | Replace the left most element of a tree with the supplied new element.
-- This function raises an error if applied to an empty tree.
--
-- Complexity: O(log n)
writeL :: e -> AVL e -> AVL e
writeL :: forall e. e -> AVL e -> AVL e
writeL e
_   AVL e
E        = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"writeL: Empty Tree"
writeL e
e' (N AVL e
l e
e AVL e
r) = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLN e
e' AVL e
l e
e AVL e
r
writeL e
e' (Z AVL e
l e
e AVL e
r) = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLZ e
e' AVL e
l e
e AVL e
r
writeL e
e' (P AVL e
l e
e AVL e
r) = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLP e
e' AVL e
l e
e AVL e
r

-- | Similar to 'writeL', but returns 'Nothing' if applied to an empty tree.
--
-- Complexity: O(log n)
tryWriteL :: e -> AVL e -> Maybe (AVL e)
tryWriteL :: forall e. e -> AVL e -> Maybe (AVL e)
tryWriteL e
_   AVL e
E        = Maybe (AVL e)
forall a. Maybe a
Nothing
tryWriteL e
e' (N AVL e
l e
e AVL e
r) = AVL e -> Maybe (AVL e)
forall a. a -> Maybe a
Just (AVL e -> Maybe (AVL e)) -> AVL e -> Maybe (AVL e)
forall a b. (a -> b) -> a -> b
$! e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLN e
e' AVL e
l e
e AVL e
r
tryWriteL e
e' (Z AVL e
l e
e AVL e
r) = AVL e -> Maybe (AVL e)
forall a. a -> Maybe a
Just (AVL e -> Maybe (AVL e)) -> AVL e -> Maybe (AVL e)
forall a b. (a -> b) -> a -> b
$! e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLZ e
e' AVL e
l e
e AVL e
r
tryWriteL e
e' (P AVL e
l e
e AVL e
r) = AVL e -> Maybe (AVL e)
forall a. a -> Maybe a
Just (AVL e -> Maybe (AVL e)) -> AVL e -> Maybe (AVL e)
forall a b. (a -> b) -> a -> b
$! e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLP e
e' AVL e
l e
e AVL e
r

-- This version of writeL is for trees which are known to be non-empty.
writeL' :: e -> AVL e -> AVL e
writeL' :: forall e. e -> AVL e -> AVL e
writeL' e
_   AVL e
E        = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"writeL': Bug0"
writeL' e
e' (N AVL e
l e
e AVL e
r) = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLN e
e' AVL e
l e
e AVL e
r -- l may be empty
writeL' e
e' (Z AVL e
l e
e AVL e
r) = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLZ e
e' AVL e
l e
e AVL e
r -- l may be empty
writeL' e
e' (P AVL e
l e
e AVL e
r) = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLP e
e' AVL e
l e
e AVL e
r -- l can't be empty

-- Write to left sub-tree of N l e r, or here if l is empty
writeLN :: e -> AVL e -> e -> AVL e -> AVL e
writeLN :: forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLN e
e'  AVL e
E           e
_ AVL e
r = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
forall e. AVL e
E e
e' AVL e
r
writeLN e
e' (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLN e
e' AVL e
ll e
le AVL e
lr in AVL e
l' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l' e
e AVL e
r
writeLN e
e' (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLZ e
e' AVL e
ll e
le AVL e
lr in AVL e
l' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l' e
e AVL e
r
writeLN e
e' (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLP e
e' AVL e
ll e
le AVL e
lr in AVL e
l' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l' e
e AVL e
r

-- Write to left sub-tree of Z l e r, or here if l is empty
writeLZ :: e -> AVL e -> e -> AVL e -> AVL e
writeLZ :: forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLZ e
e'  AVL e
E           e
_ AVL e
r = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
forall e. AVL e
E e
e' AVL e
r -- r must be E too!
writeLZ e
e' (N AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLN e
e' AVL e
ll e
le AVL e
lr in AVL e
l' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l' e
e AVL e
r
writeLZ e
e' (Z AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLZ e
e' AVL e
ll e
le AVL e
lr in AVL e
l' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l' e
e AVL e
r
writeLZ e
e' (P AVL e
ll e
le AVL e
lr) e
e AVL e
r = let l' :: AVL e
l' = e -> AVL e -> e -> AVL e -> AVL e
forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLP e
e' AVL e
ll e
le AVL e
lr in AVL e
l' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l' e
e AVL e
r

-- Write to left sub-tree of P l e r (l can't be empty)
{-# INLINE writeLP #-}
writeLP ::  e -> AVL e -> e -> AVL e -> AVL e
writeLP :: forall e. e -> AVL e -> e -> AVL e -> AVL e
writeLP e
e'  AVL e
l           e
e AVL e
r = let l' :: AVL e
l' = e -> AVL e -> AVL e
forall e. e -> AVL e -> AVL e
writeL' e
e' AVL e
l in AVL e
l' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
l' e
e AVL e
r
---------------------------------------------------------------------------
--                       writeL, tryWriteL end here                      --
---------------------------------------------------------------------------


---------------------------------------------------------------------------
--                       writeR, tryWriteR                               --
---------------------------------------------------------------------------
-- | Replace the right most element of a tree with the supplied new element.
-- This function raises an error if applied to an empty tree.
--
-- Complexity: O(log n)
writeR :: AVL e -> e -> AVL e
writeR :: forall e. AVL e -> e -> AVL e
writeR  AVL e
E        e
_  = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"writeR: Empty Tree"
writeR (N AVL e
l e
e AVL e
r) e
e' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRN AVL e
l e
e AVL e
r e
e'
writeR (Z AVL e
l e
e AVL e
r) e
e' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRZ AVL e
l e
e AVL e
r e
e'
writeR (P AVL e
l e
e AVL e
r) e
e' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRP AVL e
l e
e AVL e
r e
e'

-- | Similar to 'writeR', but returns 'Nothing' if applied to an empty tree.
--
-- Complexity: O(log n)
tryWriteR :: AVL e -> e -> Maybe (AVL e)
tryWriteR :: forall e. AVL e -> e -> Maybe (AVL e)
tryWriteR  AVL e
E        e
_  = Maybe (AVL e)
forall a. Maybe a
Nothing
tryWriteR (N AVL e
l e
e AVL e
r) e
e' = AVL e -> Maybe (AVL e)
forall a. a -> Maybe a
Just (AVL e -> Maybe (AVL e)) -> AVL e -> Maybe (AVL e)
forall a b. (a -> b) -> a -> b
$! AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRN AVL e
l e
e AVL e
r e
e'
tryWriteR (Z AVL e
l e
e AVL e
r) e
e' = AVL e -> Maybe (AVL e)
forall a. a -> Maybe a
Just (AVL e -> Maybe (AVL e)) -> AVL e -> Maybe (AVL e)
forall a b. (a -> b) -> a -> b
$! AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRZ AVL e
l e
e AVL e
r e
e'
tryWriteR (P AVL e
l e
e AVL e
r) e
e' = AVL e -> Maybe (AVL e)
forall a. a -> Maybe a
Just (AVL e -> Maybe (AVL e)) -> AVL e -> Maybe (AVL e)
forall a b. (a -> b) -> a -> b
$! AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRP AVL e
l e
e AVL e
r e
e'

-- This version of writeR is for trees which are known to be non-empty.
writeR' :: AVL e -> e -> AVL e
writeR' :: forall e. AVL e -> e -> AVL e
writeR'  AVL e
E        e
_  = [Char] -> AVL e
forall a. HasCallStack => [Char] -> a
error [Char]
"writeR': Bug0"
writeR' (N AVL e
l e
e AVL e
r) e
e' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRN AVL e
l e
e AVL e
r e
e' -- r can't be empty
writeR' (Z AVL e
l e
e AVL e
r) e
e' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRZ AVL e
l e
e AVL e
r e
e' -- r may be empty
writeR' (P AVL e
l e
e AVL e
r) e
e' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRP AVL e
l e
e AVL e
r e
e' -- r may be empty

-- Write to right sub-tree of N l e r (r can't be empty)
{-# INLINE writeRN #-}
writeRN ::  AVL e -> e -> AVL e -> e -> AVL e
writeRN :: forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRN AVL e
l e
e  AVL e
r           e
e' = let r' :: AVL e
r' = AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e
writeR' AVL e
r e
e' in AVL e
r' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l e
e AVL e
r'

-- Write to right sub-tree of Z l e r, or here if r is empty
writeRZ :: AVL e -> e -> AVL e -> e -> AVL e
writeRZ :: forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRZ AVL e
l e
_  AVL e
E           e
e' = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l e
e' AVL e
forall e. AVL e
E -- l must be E too!
writeRZ AVL e
l e
e (N AVL e
rl e
re AVL e
rr) e
e' = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRN AVL e
rl e
re AVL e
rr e
e' in AVL e
r' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l e
e AVL e
r'
writeRZ AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) e
e' = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRZ AVL e
rl e
re AVL e
rr e
e' in AVL e
r' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l e
e AVL e
r'
writeRZ AVL e
l e
e (P AVL e
rl e
re AVL e
rr) e
e' = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRP AVL e
rl e
re AVL e
rr e
e' in AVL e
r' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l e
e AVL e
r'

-- Write to right sub-tree of P l e r, or here if r is empty
writeRP :: AVL e -> e -> AVL e -> e -> AVL e
writeRP :: forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRP AVL e
l e
_  AVL e
E           e
e' = AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
l e
e' AVL e
forall e. AVL e
E
writeRP AVL e
l e
e (N AVL e
rl e
re AVL e
rr) e
e' = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRN AVL e
rl e
re AVL e
rr e
e' in AVL e
r' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
l e
e AVL e
r'
writeRP AVL e
l e
e (Z AVL e
rl e
re AVL e
rr) e
e' = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRZ AVL e
rl e
re AVL e
rr e
e' in AVL e
r' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
l e
e AVL e
r'
writeRP AVL e
l e
e (P AVL e
rl e
re AVL e
rr) e
e' = let r' :: AVL e
r' = AVL e -> e -> AVL e -> e -> AVL e
forall e. AVL e -> e -> AVL e -> e -> AVL e
writeRP AVL e
rl e
re AVL e
rr e
e' in AVL e
r' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
l e
e AVL e
r'
---------------------------------------------------------------------------
--                       writeR, tryWriteR end here                      --
---------------------------------------------------------------------------


-- | A general purpose function to perform a search of a tree, using the supplied selector.
-- If the search succeeds the found element is replaced by the value (@e@) of the @('Data.COrdering.Eq' e)@
-- constructor returned by the selector. If the search fails this function returns the original tree.
--
-- Complexity: O(log n)
write :: (e -> COrdering e) -> AVL e -> AVL e
write :: forall e. (e -> COrdering e) -> AVL e -> AVL e
write e -> COrdering e
c AVL e
t = case (e -> COrdering e) -> AVL e -> BinPath e
forall e a. (e -> COrdering a) -> AVL e -> BinPath a
openPathWith e -> COrdering e
c AVL e
t of
            FullBP Int#
pth e
e -> Int# -> e -> AVL e -> AVL e
forall e. Int# -> e -> AVL e -> AVL e
writePath Int#
pth e
e AVL e
t
            BinPath e
_            -> AVL e
t

-- | Functionally identical to 'write', but returns an identical tree (one with all the nodes on
-- the path duplicated) if the search fails. This should probably only be used if you know the
-- search will succeed and will return an element which is different from that already present.
--
-- Complexity: O(log n)
writeFast :: (e -> COrdering e) -> AVL e -> AVL e
writeFast :: forall e. (e -> COrdering e) -> AVL e -> AVL e
writeFast e -> COrdering e
c = AVL e -> AVL e
w where
 w :: AVL e -> AVL e
w   AVL e
E        = AVL e
forall e. AVL e
E
 w  (N AVL e
l e
e AVL e
r) = case e -> COrdering e
c e
e of
                COrdering e
Lt   -> let l' :: AVL e
l' = AVL e -> AVL e
w AVL e
l in AVL e
l' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l' e
e AVL e
r
                Eq e
v -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l e
v AVL e
r
                COrdering e
Gt   -> let r' :: AVL e
r' = AVL e -> AVL e
w AVL e
r in AVL e
r' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
N AVL e
l  e
e AVL e
r'
 w  (Z AVL e
l e
e AVL e
r) = case e -> COrdering e
c e
e of
                COrdering e
Lt   -> let l' :: AVL e
l' = AVL e -> AVL e
w AVL e
l in AVL e
l' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l' e
e AVL e
r
                Eq e
v -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l e
v AVL e
r
                COrdering e
Gt   -> let r' :: AVL e
r' = AVL e -> AVL e
w AVL e
r in AVL e
r' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
Z AVL e
l  e
e AVL e
r'
 w  (P AVL e
l e
e AVL e
r) = case e -> COrdering e
c e
e of
                COrdering e
Lt   -> let l' :: AVL e
l' = AVL e -> AVL e
w AVL e
l in AVL e
l' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
l' e
e AVL e
r
                Eq e
v -> AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
l e
v AVL e
r
                COrdering e
Gt   -> let r' :: AVL e
r' = AVL e -> AVL e
w AVL e
r in AVL e
r' AVL e -> AVL e -> AVL e
forall a b. a -> b -> b
`seq` AVL e -> e -> AVL e -> AVL e
forall e. AVL e -> e -> AVL e -> AVL e
P AVL e
l  e
e AVL e
r'

-- | A general purpose function to perform a search of a tree, using the supplied selector.
-- The found element is replaced by the value (@e@) of the @('Data.COrdering.Eq' e)@ constructor returned by
-- the selector. This function returns 'Nothing' if the search failed.
--
-- Complexity: O(log n)
tryWrite :: (e -> COrdering e) -> AVL e -> Maybe (AVL e)
tryWrite :: forall e. (e -> COrdering e) -> AVL e -> Maybe (AVL e)
tryWrite e -> COrdering e
c AVL e
t = case (e -> COrdering e) -> AVL e -> BinPath e
forall e a. (e -> COrdering a) -> AVL e -> BinPath a
openPathWith e -> COrdering e
c AVL e
t of
               FullBP Int#
pth e
e -> AVL e -> Maybe (AVL e)
forall a. a -> Maybe a
Just (AVL e -> Maybe (AVL e)) -> AVL e -> Maybe (AVL e)
forall a b. (a -> b) -> a -> b
$! Int# -> e -> AVL e -> AVL e
forall e. Int# -> e -> AVL e -> AVL e
writePath Int#
pth e
e AVL e
t
               BinPath e
_            -> Maybe (AVL e)
forall a. Maybe a
Nothing

-- | Similar to 'write', but also returns the original tree if the search succeeds but
-- the selector returns @('Data.COrdering.Eq' 'Nothing')@. (This version is intended to help reduce heap burn
-- rate if it\'s likely that no modification of the value is needed.)
--
-- Complexity: O(log n)
writeMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e
writeMaybe :: forall e. (e -> COrdering (Maybe e)) -> AVL e -> AVL e
writeMaybe e -> COrdering (Maybe e)
c AVL e
t = case (e -> COrdering (Maybe e)) -> AVL e -> BinPath (Maybe e)
forall e a. (e -> COrdering a) -> AVL e -> BinPath a
openPathWith e -> COrdering (Maybe e)
c AVL e
t of
                 FullBP Int#
pth (Just e
e) -> Int# -> e -> AVL e -> AVL e
forall e. Int# -> e -> AVL e -> AVL e
writePath Int#
pth e
e AVL e
t
                 BinPath (Maybe e)
_                   -> AVL e
t

-- | Similar to 'tryWrite', but also returns the original tree if the search succeeds but
-- the selector returns @('Data.COrdering.Eq' 'Nothing')@. (This version is intended to help reduce heap burn
-- rate if it\'s likely that no modification of the value is needed.)
--
-- Complexity: O(log n)
tryWriteMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> Maybe (AVL e)
tryWriteMaybe :: forall e. (e -> COrdering (Maybe e)) -> AVL e -> Maybe (AVL e)
tryWriteMaybe e -> COrdering (Maybe e)
c AVL e
t = case (e -> COrdering (Maybe e)) -> AVL e -> BinPath (Maybe e)
forall e a. (e -> COrdering a) -> AVL e -> BinPath a
openPathWith e -> COrdering (Maybe e)
c AVL e
t of
                    FullBP Int#
pth (Just e
e) -> AVL e -> Maybe (AVL e)
forall a. a -> Maybe a
Just (AVL e -> Maybe (AVL e)) -> AVL e -> Maybe (AVL e)
forall a b. (a -> b) -> a -> b
$! Int# -> e -> AVL e -> AVL e
forall e. Int# -> e -> AVL e -> AVL e
writePath Int#
pth e
e AVL e
t
                    FullBP Int#
_   Maybe e
Nothing  -> AVL e -> Maybe (AVL e)
forall a. a -> Maybe a
Just AVL e
t
                    BinPath (Maybe e)
_                   -> Maybe (AVL e)
forall a. Maybe a
Nothing