-------------------------------------------------------------------------
--  
--         UseTree.hs
--  
--     Using the search tree ADT                    
--                                  
--         (c) Addison-Wesley, 1996-2011.                   
--  
-------------------------------------------------------------------------
            


module UseTree where

import Tree                 
--            
-- The size function  definable using the operations of the 
--      abstype.                            
--  

size :: Tree a -> Integer
size :: forall a. Tree a -> Integer
size Tree a
t 
  | Tree a -> Bool
forall a. Tree a -> Bool
isNil Tree a
t     = Integer
0
  | Bool
otherwise   = Integer
1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Tree a -> Integer
forall a. Tree a -> Integer
size (Tree a -> Tree a
forall a. Tree a -> Tree a
leftSub Tree a
t) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Tree a -> Integer
forall a. Tree a -> Integer
size (Tree a -> Tree a
forall a. Tree a -> Tree a
rightSub Tree a
t)

--  
-- Finding the nth element of a tree.               
--  

indexT :: Integer -> Tree a -> a

indexT :: forall a. Integer -> Tree a -> a
indexT Integer
n Tree a
t 
  | Tree a -> Bool
forall a. Tree a -> Bool
isNil Tree a
t     = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"indexT"
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
st1     = Integer -> Tree a -> a
forall a. Integer -> Tree a -> a
indexT Integer
n Tree a
t1
  | Integer
n Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
st1    = a
v
  | Bool
otherwise   = Integer -> Tree a -> a
forall a. Integer -> Tree a -> a
indexT (Integer
nInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
st1Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
-Integer
1) Tree a
t2
      where
      v :: a
v   = Tree a -> a
forall a. Tree a -> a
treeVal Tree a
t
      t1 :: Tree a
t1  = Tree a -> Tree a
forall a. Tree a -> Tree a
leftSub Tree a
t
      t2 :: Tree a
t2  = Tree a -> Tree a
forall a. Tree a -> Tree a
rightSub Tree a
t
      st1 :: Integer
st1 = Tree a -> Integer
forall a. Tree a -> Integer
size Tree a
t1