{-# LANGUAGE
  DeriveFoldable, DeriveFunctor
#-}

-- |
-- Module      : OAlg.Data.Tree
-- Description : binary trees for lookup
-- Copyright   : (c) Erich Gut
-- License     : BSD3
-- Maintainer  : zerich.gut@gmail.com
--
-- binary trees for lookup.
module OAlg.Data.Tree
  ( Tree(..), trLookup, trFilter
  )
  where

import Prelude

--------------------------------------------------------------------------------
-- Tree -

-- | binary tree with node element in @__i__@ and leaf element in @__x__@.
data Tree i x = Node i (Tree i x) (Tree i x) | Leaf x
  deriving (Int -> Tree i x -> ShowS
[Tree i x] -> ShowS
Tree i x -> String
(Int -> Tree i x -> ShowS)
-> (Tree i x -> String) -> ([Tree i x] -> ShowS) -> Show (Tree i x)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall i x. (Show i, Show x) => Int -> Tree i x -> ShowS
forall i x. (Show i, Show x) => [Tree i x] -> ShowS
forall i x. (Show i, Show x) => Tree i x -> String
$cshowsPrec :: forall i x. (Show i, Show x) => Int -> Tree i x -> ShowS
showsPrec :: Int -> Tree i x -> ShowS
$cshow :: forall i x. (Show i, Show x) => Tree i x -> String
show :: Tree i x -> String
$cshowList :: forall i x. (Show i, Show x) => [Tree i x] -> ShowS
showList :: [Tree i x] -> ShowS
Show,Tree i x -> Tree i x -> Bool
(Tree i x -> Tree i x -> Bool)
-> (Tree i x -> Tree i x -> Bool) -> Eq (Tree i x)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall i x. (Eq i, Eq x) => Tree i x -> Tree i x -> Bool
$c== :: forall i x. (Eq i, Eq x) => Tree i x -> Tree i x -> Bool
== :: Tree i x -> Tree i x -> Bool
$c/= :: forall i x. (Eq i, Eq x) => Tree i x -> Tree i x -> Bool
/= :: Tree i x -> Tree i x -> Bool
Eq,Eq (Tree i x)
Eq (Tree i x) =>
(Tree i x -> Tree i x -> Ordering)
-> (Tree i x -> Tree i x -> Bool)
-> (Tree i x -> Tree i x -> Bool)
-> (Tree i x -> Tree i x -> Bool)
-> (Tree i x -> Tree i x -> Bool)
-> (Tree i x -> Tree i x -> Tree i x)
-> (Tree i x -> Tree i x -> Tree i x)
-> Ord (Tree i x)
Tree i x -> Tree i x -> Bool
Tree i x -> Tree i x -> Ordering
Tree i x -> Tree i x -> Tree i x
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall i x. (Ord i, Ord x) => Eq (Tree i x)
forall i x. (Ord i, Ord x) => Tree i x -> Tree i x -> Bool
forall i x. (Ord i, Ord x) => Tree i x -> Tree i x -> Ordering
forall i x. (Ord i, Ord x) => Tree i x -> Tree i x -> Tree i x
$ccompare :: forall i x. (Ord i, Ord x) => Tree i x -> Tree i x -> Ordering
compare :: Tree i x -> Tree i x -> Ordering
$c< :: forall i x. (Ord i, Ord x) => Tree i x -> Tree i x -> Bool
< :: Tree i x -> Tree i x -> Bool
$c<= :: forall i x. (Ord i, Ord x) => Tree i x -> Tree i x -> Bool
<= :: Tree i x -> Tree i x -> Bool
$c> :: forall i x. (Ord i, Ord x) => Tree i x -> Tree i x -> Bool
> :: Tree i x -> Tree i x -> Bool
$c>= :: forall i x. (Ord i, Ord x) => Tree i x -> Tree i x -> Bool
>= :: Tree i x -> Tree i x -> Bool
$cmax :: forall i x. (Ord i, Ord x) => Tree i x -> Tree i x -> Tree i x
max :: Tree i x -> Tree i x -> Tree i x
$cmin :: forall i x. (Ord i, Ord x) => Tree i x -> Tree i x -> Tree i x
min :: Tree i x -> Tree i x -> Tree i x
Ord,(forall m. Monoid m => Tree i m -> m)
-> (forall m a. Monoid m => (a -> m) -> Tree i a -> m)
-> (forall m a. Monoid m => (a -> m) -> Tree i a -> m)
-> (forall a b. (a -> b -> b) -> b -> Tree i a -> b)
-> (forall a b. (a -> b -> b) -> b -> Tree i a -> b)
-> (forall b a. (b -> a -> b) -> b -> Tree i a -> b)
-> (forall b a. (b -> a -> b) -> b -> Tree i a -> b)
-> (forall a. (a -> a -> a) -> Tree i a -> a)
-> (forall a. (a -> a -> a) -> Tree i a -> a)
-> (forall a. Tree i a -> [a])
-> (forall a. Tree i a -> Bool)
-> (forall a. Tree i a -> Int)
-> (forall a. Eq a => a -> Tree i a -> Bool)
-> (forall a. Ord a => Tree i a -> a)
-> (forall a. Ord a => Tree i a -> a)
-> (forall a. Num a => Tree i a -> a)
-> (forall a. Num a => Tree i a -> a)
-> Foldable (Tree i)
forall a. Eq a => a -> Tree i a -> Bool
forall a. Num a => Tree i a -> a
forall a. Ord a => Tree i a -> a
forall m. Monoid m => Tree i m -> m
forall a. Tree i a -> Bool
forall a. Tree i a -> Int
forall a. Tree i a -> [a]
forall a. (a -> a -> a) -> Tree i a -> a
forall i a. Eq a => a -> Tree i a -> Bool
forall i a. Num a => Tree i a -> a
forall i a. Ord a => Tree i a -> a
forall m a. Monoid m => (a -> m) -> Tree i a -> m
forall i m. Monoid m => Tree i m -> m
forall m a. Monoid m => (a -> m) -> Tree i a -> m
forall i a. Tree i a -> Bool
forall i a. Tree i a -> Int
forall i a. Tree i a -> [a]
forall b a. (b -> a -> b) -> b -> Tree i a -> b
forall a b. (a -> b -> b) -> b -> Tree i a -> b
forall i a. (a -> a -> a) -> Tree i a -> a
forall i m a. Monoid m => (a -> m) -> Tree i a -> m
forall i b a. (b -> a -> b) -> b -> Tree i a -> b
forall i a b. (a -> b -> b) -> b -> Tree i a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall i m. Monoid m => Tree i m -> m
fold :: forall m. Monoid m => Tree i m -> m
$cfoldMap :: forall i m a. Monoid m => (a -> m) -> Tree i a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Tree i a -> m
$cfoldMap' :: forall i m a. Monoid m => (a -> m) -> Tree i a -> m
foldMap' :: forall m a. Monoid m => (a -> m) -> Tree i a -> m
$cfoldr :: forall i a b. (a -> b -> b) -> b -> Tree i a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Tree i a -> b
$cfoldr' :: forall i a b. (a -> b -> b) -> b -> Tree i a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Tree i a -> b
$cfoldl :: forall i b a. (b -> a -> b) -> b -> Tree i a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Tree i a -> b
$cfoldl' :: forall i b a. (b -> a -> b) -> b -> Tree i a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> Tree i a -> b
$cfoldr1 :: forall i a. (a -> a -> a) -> Tree i a -> a
foldr1 :: forall a. (a -> a -> a) -> Tree i a -> a
$cfoldl1 :: forall i a. (a -> a -> a) -> Tree i a -> a
foldl1 :: forall a. (a -> a -> a) -> Tree i a -> a
$ctoList :: forall i a. Tree i a -> [a]
toList :: forall a. Tree i a -> [a]
$cnull :: forall i a. Tree i a -> Bool
null :: forall a. Tree i a -> Bool
$clength :: forall i a. Tree i a -> Int
length :: forall a. Tree i a -> Int
$celem :: forall i a. Eq a => a -> Tree i a -> Bool
elem :: forall a. Eq a => a -> Tree i a -> Bool
$cmaximum :: forall i a. Ord a => Tree i a -> a
maximum :: forall a. Ord a => Tree i a -> a
$cminimum :: forall i a. Ord a => Tree i a -> a
minimum :: forall a. Ord a => Tree i a -> a
$csum :: forall i a. Num a => Tree i a -> a
sum :: forall a. Num a => Tree i a -> a
$cproduct :: forall i a. Num a => Tree i a -> a
product :: forall a. Num a => Tree i a -> a
Foldable,(forall a b. (a -> b) -> Tree i a -> Tree i b)
-> (forall a b. a -> Tree i b -> Tree i a) -> Functor (Tree i)
forall a b. a -> Tree i b -> Tree i a
forall a b. (a -> b) -> Tree i a -> Tree i b
forall i a b. a -> Tree i b -> Tree i a
forall i a b. (a -> b) -> Tree i a -> Tree i b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall i a b. (a -> b) -> Tree i a -> Tree i b
fmap :: forall a b. (a -> b) -> Tree i a -> Tree i b
$c<$ :: forall i a b. a -> Tree i b -> Tree i a
<$ :: forall a b. a -> Tree i b -> Tree i a
Functor)

--------------------------------------------------------------------------------
-- trLookup -

-- | lookup a value in a binary tree.
trLookup :: Ord i => Tree i x -> i -> x
trLookup :: forall i x. Ord i => Tree i x -> i -> x
trLookup (Leaf x
x) i
_     = x
x
trLookup (Node i
i Tree i x
l Tree i x
r) i
j = if i
j i -> i -> Bool
forall a. Ord a => a -> a -> Bool
< i
i then Tree i x -> i -> x
forall i x. Ord i => Tree i x -> i -> x
trLookup Tree i x
l i
j else Tree i x -> i -> x
forall i x. Ord i => Tree i x -> i -> x
trLookup Tree i x
r i
j

--------------------------------------------------------------------------------
-- trFilter -

-- | the sub tree containing all leafs satisfying the given predicate.
trFilter :: (x -> Bool) -> Tree i x -> Maybe (Tree i x)
trFilter :: forall x i. (x -> Bool) -> Tree i x -> Maybe (Tree i x)
trFilter x -> Bool
p Tree i x
t = Tree i x -> Maybe (Tree i x)
forall {i}. Tree i x -> Maybe (Tree i x)
fltr Tree i x
t where
  fltr :: Tree i x -> Maybe (Tree i x)
fltr (Leaf x
x)     = if x -> Bool
p x
x then Tree i x -> Maybe (Tree i x)
forall a. a -> Maybe a
Just (x -> Tree i x
forall i x. x -> Tree i x
Leaf x
x) else Maybe (Tree i x)
forall a. Maybe a
Nothing
  fltr (Node i
i Tree i x
l Tree i x
r) = case (Tree i x -> Maybe (Tree i x)
fltr Tree i x
l,Tree i x -> Maybe (Tree i x)
fltr Tree i x
r) of
    (Maybe (Tree i x)
Nothing,Just Tree i x
r') -> Tree i x -> Maybe (Tree i x)
forall a. a -> Maybe a
Just Tree i x
r'
    (Just Tree i x
l',Maybe (Tree i x)
Nothing) -> Tree i x -> Maybe (Tree i x)
forall a. a -> Maybe a
Just Tree i x
l'
    (Just Tree i x
l',Just Tree i x
r') -> Tree i x -> Maybe (Tree i x)
forall a. a -> Maybe a
Just (Tree i x -> Maybe (Tree i x)) -> Tree i x -> Maybe (Tree i x)
forall a b. (a -> b) -> a -> b
$ i -> Tree i x -> Tree i x -> Tree i x
forall i x. i -> Tree i x -> Tree i x -> Tree i x
Node i
i Tree i x
l' Tree i x
r'
    (Maybe (Tree i x), Maybe (Tree i x))
_                 -> Maybe (Tree i x)
forall a. Maybe a
Nothing