```-----------------------------------------------------------------------------
-- |
--
-- Maintainer  :  http://homepages.nildram.co.uk/~ahey/em.png
-- Stability   :  stable
-- Portability :  portable
-----------------------------------------------------------------------------
(-- * Reading from AVL trees

-- ** Reading from extreme left or right

-- ** Reading from /sorted/ AVL trees

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

import Prelude -- so haddock finds the symbols there

import Data.COrdering
import Data.Tree.AVL.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 (P l _ _) = readLNE 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 (P l _ _) = Just \$! readLNE l     -- BF=+1, so left sub-tree cannot be empty.

-- Local utilities for the above
readLNE :: AVL e -> e
readLNE (P l _ _) = readLNE l     -- BF=+1, so left sub-tree cannot be empty.
readLE :: AVL e -> e -> e
readLE (P l _ _) _ = readLNE 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 (N _ _ r) = readRNE 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 (N _ _ r) = Just \$! readRNE r   -- BF=-1, so right sub-tree cannot be empty.

-- Local utilities for the above
readRNE :: AVL e -> e
readRNE (N _ _ r) = readRNE r     -- BF=-1, so right sub-tree cannot be empty.
readRE :: AVL e -> e -> e
readRE (N _ _ r) _ = readRNE 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)
genAssertRead :: AVL e -> (e -> COrdering a) -> a
genRead''   l e r  = case c e of
Eq a -> a

-- | General purpose function to perform a search of a sorted tree, using the supplied selector.
-- This function is similar to 'genAssertRead', but returns 'Nothing' if the search failed.
--
-- Complexity: O(log n)
genTryRead :: AVL e -> (e -> COrdering a) ->  Maybe a
genTryRead''   l e r  = case c e of
Eq a -> Just a

-- | 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)
genTryReadMaybe :: AVL e -> (e -> COrdering (Maybe a)) ->  Maybe a
genTryRead''   l e r  = case c e of
Eq mba -> mba

-- | General purpose function to perform a search of a sorted tree, using the supplied selector.
-- This function is similar to 'genAssertRead', but returns a the default value (first argument) if
-- the search fails.
--
-- Complexity: O(log n)
genDefaultRead :: a -> AVL e -> (e -> COrdering a) -> a
genRead''   l e r  = case c e of
Eq a -> a

-- | 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)
genContains :: AVL e -> (e -> Ordering) -> Bool
genContains t c = genContains' t where
genContains'  E        = False
genContains' (N l e r) = genContains'' l e r
genContains' (Z l e r) = genContains'' l e r
genContains' (P l e r) = genContains'' l e r
genContains''   l e r  = case c e of
LT -> genContains' l
EQ -> True
GT -> genContains' r
```