-- |
-- 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(..), lookup
  )
  where

import Prelude hiding (lookup)

--------------------------------------------------------------------------------
-- 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


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