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

 -- ** Reading from extreme left or right
 assertReadL,tryReadL,
 assertReadR,tryReadR,

 -- ** Reading from /sorted/ AVL trees
 assertRead,tryRead,tryReadMaybe,defaultRead,

 -- ** Simple searches of /sorted/ AVL trees
 contains,
) where

import Prelude -- so haddock finds the symbols there

import Data.COrdering
import Data.Tree.AVL.Internals.Types(AVL(..))

-- | Read the leftmost element from a /non-empty/ tree. Raises an error if the tree is empty.
-- If the tree is sorted this will return the least element.
--
-- Complexity: O(log n)
assertReadL :: AVL e -> e
assertReadL :: forall e. AVL e -> e
assertReadL  AVL e
E        = [Char] -> e
forall a. HasCallStack => [Char] -> a
error [Char]
"assertReadL: Empty tree."
assertReadL (N AVL e
l e
e AVL e
_) = AVL e -> e -> e
forall e. AVL e -> e -> e
readLE  AVL e
l e
e
assertReadL (Z AVL e
l e
e AVL e
_) = AVL e -> e -> e
forall e. AVL e -> e -> e
readLE  AVL e
l e
e
assertReadL (P AVL e
l e
_ AVL e
_) = AVL e -> e
forall e. AVL e -> e
readLNE AVL e
l     -- BF=+1, so left sub-tree cannot be empty.

-- | Similar to 'assertReadL' but returns 'Nothing' if the tree is empty.
--
-- Complexity: O(log n)
tryReadL :: AVL e -> Maybe e
tryReadL :: forall e. AVL e -> Maybe e
tryReadL  AVL e
E        = Maybe e
forall a. Maybe a
Nothing
tryReadL (N AVL e
l e
e AVL e
_) = e -> Maybe e
forall a. a -> Maybe a
Just (e -> Maybe e) -> e -> Maybe e
forall a b. (a -> b) -> a -> b
$! AVL e -> e -> e
forall e. AVL e -> e -> e
readLE  AVL e
l e
e
tryReadL (Z AVL e
l e
e AVL e
_) = e -> Maybe e
forall a. a -> Maybe a
Just (e -> Maybe e) -> e -> Maybe e
forall a b. (a -> b) -> a -> b
$! AVL e -> e -> e
forall e. AVL e -> e -> e
readLE  AVL e
l e
e
tryReadL (P AVL e
l e
_ AVL e
_) = e -> Maybe e
forall a. a -> Maybe a
Just (e -> Maybe e) -> e -> Maybe e
forall a b. (a -> b) -> a -> b
$! AVL e -> e
forall e. AVL e -> e
readLNE AVL e
l     -- BF=+1, so left sub-tree cannot be empty.

-- Local utilities for the above
readLNE :: AVL e -> e
readLNE :: forall e. AVL e -> e
readLNE  AVL e
E        = [Char] -> e
forall a. HasCallStack => [Char] -> a
error [Char]
"readLNE: Bug."
readLNE (N AVL e
l e
e AVL e
_) = AVL e -> e -> e
forall e. AVL e -> e -> e
readLE  AVL e
l e
e
readLNE (Z AVL e
l e
e AVL e
_) = AVL e -> e -> e
forall e. AVL e -> e -> e
readLE  AVL e
l e
e
readLNE (P AVL e
l e
_ AVL e
_) = AVL e -> e
forall e. AVL e -> e
readLNE AVL e
l     -- BF=+1, so left sub-tree cannot be empty.
readLE :: AVL e -> e -> e
readLE :: forall e. AVL e -> e -> e
readLE  AVL e
E        e
e = e
e
readLE (N AVL e
l e
e AVL e
_) e
_ = AVL e -> e -> e
forall e. AVL e -> e -> e
readLE  AVL e
l e
e
readLE (Z AVL e
l e
e AVL e
_) e
_ = AVL e -> e -> e
forall e. AVL e -> e -> e
readLE  AVL e
l e
e
readLE (P AVL e
l e
_ AVL e
_) e
_ = AVL e -> e
forall e. AVL e -> e
readLNE AVL e
l  -- BF=+1, so left sub-tree cannot be empty.


-- | Read the rightmost element from a /non-empty/ tree. Raises an error if the tree is empty.
-- If the tree is sorted this will return the greatest element.
--
-- Complexity: O(log n)
assertReadR :: AVL e -> e
assertReadR :: forall e. AVL e -> e
assertReadR  AVL e
E        = [Char] -> e
forall a. HasCallStack => [Char] -> a
error [Char]
"assertReadR: Empty tree."
assertReadR (P AVL e
_ e
e AVL e
r) = AVL e -> e -> e
forall e. AVL e -> e -> e
readRE  AVL e
r e
e
assertReadR (Z AVL e
_ e
e AVL e
r) = AVL e -> e -> e
forall e. AVL e -> e -> e
readRE  AVL e
r e
e
assertReadR (N AVL e
_ e
_ AVL e
r) = AVL e -> e
forall e. AVL e -> e
readRNE AVL e
r     -- BF=-1, so right sub-tree cannot be empty.

-- | Similar to 'assertReadR' but returns 'Nothing' if the tree is empty.
--
-- Complexity: O(log n)
tryReadR :: AVL e -> Maybe e
tryReadR :: forall e. AVL e -> Maybe e
tryReadR  AVL e
E        = Maybe e
forall a. Maybe a
Nothing
tryReadR (P AVL e
_ e
e AVL e
r) = e -> Maybe e
forall a. a -> Maybe a
Just (e -> Maybe e) -> e -> Maybe e
forall a b. (a -> b) -> a -> b
$! AVL e -> e -> e
forall e. AVL e -> e -> e
readRE  AVL e
r e
e
tryReadR (Z AVL e
_ e
e AVL e
r) = e -> Maybe e
forall a. a -> Maybe a
Just (e -> Maybe e) -> e -> Maybe e
forall a b. (a -> b) -> a -> b
$! AVL e -> e -> e
forall e. AVL e -> e -> e
readRE  AVL e
r e
e
tryReadR (N AVL e
_ e
_ AVL e
r) = e -> Maybe e
forall a. a -> Maybe a
Just (e -> Maybe e) -> e -> Maybe e
forall a b. (a -> b) -> a -> b
$! AVL e -> e
forall e. AVL e -> e
readRNE AVL e
r   -- BF=-1, so right sub-tree cannot be empty.

-- Local utilities for the above
readRNE :: AVL e -> e
readRNE :: forall e. AVL e -> e
readRNE  AVL e
E        = [Char] -> e
forall a. HasCallStack => [Char] -> a
error [Char]
"readRNE: Bug."
readRNE (P AVL e
_ e
e AVL e
r) = AVL e -> e -> e
forall e. AVL e -> e -> e
readRE  AVL e
r e
e
readRNE (Z AVL e
_ e
e AVL e
r) = AVL e -> e -> e
forall e. AVL e -> e -> e
readRE  AVL e
r e
e
readRNE (N AVL e
_ e
_ AVL e
r) = AVL e -> e
forall e. AVL e -> e
readRNE AVL e
r     -- BF=-1, so right sub-tree cannot be empty.
readRE :: AVL e -> e -> e
readRE :: forall e. AVL e -> e -> e
readRE  AVL e
E        e
e = e
e
readRE (P AVL e
_ e
e AVL e
r) e
_ = AVL e -> e -> e
forall e. AVL e -> e -> e
readRE  AVL e
r e
e
readRE (Z AVL e
_ e
e AVL e
r) e
_ = AVL e -> e -> e
forall e. AVL e -> e -> e
readRE  AVL e
r e
e
readRE (N AVL e
_ e
_ AVL e
r) e
_ = AVL e -> e
forall e. AVL e -> e
readRNE AVL e
r  -- BF=-1, so right sub-tree cannot be empty.


-- | General purpose function to perform a search of a sorted tree, using the supplied selector.
-- This function raises a error if the search fails.
--
-- Complexity: O(log n)
assertRead :: AVL e -> (e -> COrdering a) -> a
assertRead :: forall e a. AVL e -> (e -> COrdering a) -> a
assertRead AVL e
t e -> COrdering a
c = AVL e -> a
genRead' AVL e
t where
 genRead' :: AVL e -> a
genRead'  AVL e
E        = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"assertRead failed."
 genRead' (N AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> a
genRead'' AVL e
l e
e AVL e
r
 genRead' (Z AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> a
genRead'' AVL e
l e
e AVL e
r
 genRead' (P AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> a
genRead'' AVL e
l e
e AVL e
r
 genRead'' :: AVL e -> e -> AVL e -> a
genRead''   AVL e
l e
e AVL e
r  = case e -> COrdering a
c e
e of
                      COrdering a
Lt   -> AVL e -> a
genRead' AVL e
l
                      Eq a
a -> a
a
                      COrdering a
Gt   -> AVL e -> a
genRead' AVL e
r

-- | General purpose function to perform a search of a sorted tree, using the supplied selector.
-- This function is similar to 'assertRead', but returns 'Nothing' if the search failed.
--
-- Complexity: O(log n)
tryRead :: AVL e -> (e -> COrdering a) ->  Maybe a
tryRead :: forall e a. AVL e -> (e -> COrdering a) -> Maybe a
tryRead AVL e
t e -> COrdering a
c = AVL e -> Maybe a
tryRead' AVL e
t where
 tryRead' :: AVL e -> Maybe a
tryRead'  AVL e
E        = Maybe a
forall a. Maybe a
Nothing
 tryRead' (N AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Maybe a
tryRead'' AVL e
l e
e AVL e
r
 tryRead' (Z AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Maybe a
tryRead'' AVL e
l e
e AVL e
r
 tryRead' (P AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Maybe a
tryRead'' AVL e
l e
e AVL e
r
 tryRead'' :: AVL e -> e -> AVL e -> Maybe a
tryRead''   AVL e
l e
e AVL e
r  = case e -> COrdering a
c e
e of
                      COrdering a
Lt   -> AVL e -> Maybe a
tryRead' AVL e
l
                      Eq a
a -> a -> Maybe a
forall a. a -> Maybe a
Just a
a
                      COrdering a
Gt   -> AVL e -> Maybe a
tryRead' AVL e
r

-- | This version returns the result of the selector (without adding a 'Just' wrapper) if the search
-- succeeds, or 'Nothing' if it fails.
--
-- Complexity: O(log n)
tryReadMaybe :: AVL e -> (e -> COrdering (Maybe a)) ->  Maybe a
tryReadMaybe :: forall e a. AVL e -> (e -> COrdering (Maybe a)) -> Maybe a
tryReadMaybe AVL e
t e -> COrdering (Maybe a)
c = AVL e -> Maybe a
tryRead' AVL e
t where
 tryRead' :: AVL e -> Maybe a
tryRead'  AVL e
E        = Maybe a
forall a. Maybe a
Nothing
 tryRead' (N AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Maybe a
tryRead'' AVL e
l e
e AVL e
r
 tryRead' (Z AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Maybe a
tryRead'' AVL e
l e
e AVL e
r
 tryRead' (P AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Maybe a
tryRead'' AVL e
l e
e AVL e
r
 tryRead'' :: AVL e -> e -> AVL e -> Maybe a
tryRead''   AVL e
l e
e AVL e
r  = case e -> COrdering (Maybe a)
c e
e of
                         COrdering (Maybe a)
Lt     -> AVL e -> Maybe a
tryRead' AVL e
l
                         Eq Maybe a
mba -> Maybe a
mba
                         COrdering (Maybe a)
Gt     -> AVL e -> Maybe a
tryRead' AVL e
r

-- | General purpose function to perform a search of a sorted tree, using the supplied selector.
-- This function is similar to 'assertRead', but returns a the default value (first argument) if
-- the search fails.
--
-- Complexity: O(log n)
defaultRead :: a -> AVL e -> (e -> COrdering a) -> a
defaultRead :: forall a e. a -> AVL e -> (e -> COrdering a) -> a
defaultRead a
d AVL e
t e -> COrdering a
c = AVL e -> a
genRead' AVL e
t where
 genRead' :: AVL e -> a
genRead'  AVL e
E        = a
d
 genRead' (N AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> a
genRead'' AVL e
l e
e AVL e
r
 genRead' (Z AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> a
genRead'' AVL e
l e
e AVL e
r
 genRead' (P AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> a
genRead'' AVL e
l e
e AVL e
r
 genRead'' :: AVL e -> e -> AVL e -> a
genRead''   AVL e
l e
e AVL e
r  = case e -> COrdering a
c e
e of
                      COrdering a
Lt   -> AVL e -> a
genRead' AVL e
l
                      Eq a
a -> a
a
                      COrdering a
Gt   -> AVL e -> a
genRead' AVL e
r

-- | General purpose function to perform a search of a sorted tree, using the supplied selector.
-- Returns True if matching element is found.
--
-- Complexity: O(log n)
contains :: AVL e -> (e -> Ordering) -> Bool
contains :: forall e. AVL e -> (e -> Ordering) -> Bool
contains AVL e
t e -> Ordering
c = AVL e -> Bool
contains' AVL e
t where
 contains' :: AVL e -> Bool
contains'  AVL e
E        = Bool
False
 contains' (N AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Bool
contains'' AVL e
l e
e AVL e
r
 contains' (Z AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Bool
contains'' AVL e
l e
e AVL e
r
 contains' (P AVL e
l e
e AVL e
r) = AVL e -> e -> AVL e -> Bool
contains'' AVL e
l e
e AVL e
r
 contains'' :: AVL e -> e -> AVL e -> Bool
contains''   AVL e
l e
e AVL e
r  = case e -> Ordering
c e
e of
                       Ordering
LT -> AVL e -> Bool
contains' AVL e
l
                       Ordering
EQ -> Bool
True
                       Ordering
GT -> AVL e -> Bool
contains' AVL e
r