--
-- Copyright (c) 2009 - 2010 Brendan Hickey - http://bhickey.net
-- New BSD License (see http://www.opensource.org/licenses/bsd-license.php)
--

module Data.Tree.AVL
(AVLTree, head, tail, singleton, empty, null, fromList, fromAscList, toList, toAscList, insert, delete, lookup, (!!), size) 
where

import Prelude hiding (head, tail, (!!), lookup, null)
import Data.Maybe


data AVLTree k v =
    Leaf
  | AVLTree !k !v !Int !Int !(AVLTree k v) !(AVLTree k v) deriving (Eq (AVLTree k v)
Eq (AVLTree k v) =>
(AVLTree k v -> AVLTree k v -> Ordering)
-> (AVLTree k v -> AVLTree k v -> Bool)
-> (AVLTree k v -> AVLTree k v -> Bool)
-> (AVLTree k v -> AVLTree k v -> Bool)
-> (AVLTree k v -> AVLTree k v -> Bool)
-> (AVLTree k v -> AVLTree k v -> AVLTree k v)
-> (AVLTree k v -> AVLTree k v -> AVLTree k v)
-> Ord (AVLTree k v)
AVLTree k v -> AVLTree k v -> Bool
AVLTree k v -> AVLTree k v -> Ordering
AVLTree k v -> AVLTree k v -> AVLTree k v
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 k v. (Ord k, Ord v) => Eq (AVLTree k v)
forall k v. (Ord k, Ord v) => AVLTree k v -> AVLTree k v -> Bool
forall k v.
(Ord k, Ord v) =>
AVLTree k v -> AVLTree k v -> Ordering
forall k v.
(Ord k, Ord v) =>
AVLTree k v -> AVLTree k v -> AVLTree k v
$ccompare :: forall k v.
(Ord k, Ord v) =>
AVLTree k v -> AVLTree k v -> Ordering
compare :: AVLTree k v -> AVLTree k v -> Ordering
$c< :: forall k v. (Ord k, Ord v) => AVLTree k v -> AVLTree k v -> Bool
< :: AVLTree k v -> AVLTree k v -> Bool
$c<= :: forall k v. (Ord k, Ord v) => AVLTree k v -> AVLTree k v -> Bool
<= :: AVLTree k v -> AVLTree k v -> Bool
$c> :: forall k v. (Ord k, Ord v) => AVLTree k v -> AVLTree k v -> Bool
> :: AVLTree k v -> AVLTree k v -> Bool
$c>= :: forall k v. (Ord k, Ord v) => AVLTree k v -> AVLTree k v -> Bool
>= :: AVLTree k v -> AVLTree k v -> Bool
$cmax :: forall k v.
(Ord k, Ord v) =>
AVLTree k v -> AVLTree k v -> AVLTree k v
max :: AVLTree k v -> AVLTree k v -> AVLTree k v
$cmin :: forall k v.
(Ord k, Ord v) =>
AVLTree k v -> AVLTree k v -> AVLTree k v
min :: AVLTree k v -> AVLTree k v -> AVLTree k v
Ord, AVLTree k v -> AVLTree k v -> Bool
(AVLTree k v -> AVLTree k v -> Bool)
-> (AVLTree k v -> AVLTree k v -> Bool) -> Eq (AVLTree k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. (Eq k, Eq v) => AVLTree k v -> AVLTree k v -> Bool
$c== :: forall k v. (Eq k, Eq v) => AVLTree k v -> AVLTree k v -> Bool
== :: AVLTree k v -> AVLTree k v -> Bool
$c/= :: forall k v. (Eq k, Eq v) => AVLTree k v -> AVLTree k v -> Bool
/= :: AVLTree k v -> AVLTree k v -> Bool
Eq, Int -> AVLTree k v -> ShowS
[AVLTree k v] -> ShowS
AVLTree k v -> String
(Int -> AVLTree k v -> ShowS)
-> (AVLTree k v -> String)
-> ([AVLTree k v] -> ShowS)
-> Show (AVLTree k v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k v. (Show k, Show v) => Int -> AVLTree k v -> ShowS
forall k v. (Show k, Show v) => [AVLTree k v] -> ShowS
forall k v. (Show k, Show v) => AVLTree k v -> String
$cshowsPrec :: forall k v. (Show k, Show v) => Int -> AVLTree k v -> ShowS
showsPrec :: Int -> AVLTree k v -> ShowS
$cshow :: forall k v. (Show k, Show v) => AVLTree k v -> String
show :: AVLTree k v -> String
$cshowList :: forall k v. (Show k, Show v) => [AVLTree k v] -> ShowS
showList :: [AVLTree k v] -> ShowS
Show)

-- | /O(1)/. 'singleton' constructs a singleton AVL tree
singleton :: (Ord k) => k -> v -> AVLTree k v
singleton :: forall k v. Ord k => k -> v -> AVLTree k v
singleton k
k v
v = k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k v
v Int
1 Int
1 AVLTree k v
forall k v. AVLTree k v
Leaf AVLTree k v
forall k v. AVLTree k v
Leaf

-- | /O(1)/. 'empty' produces an empty tree
empty :: (Ord k) => AVLTree k v
empty :: forall k v. Ord k => AVLTree k v
empty = AVLTree k v
forall k v. AVLTree k v
Leaf

-- | /O(1)/. 'null' returns True if a tree is empty, otherwise False.
null :: AVLTree k v -> Bool
null :: forall k v. AVLTree k v -> Bool
null AVLTree k v
Leaf = Bool
True
null AVLTree k v
_    = Bool
False

-- | /O(1)/. 'head' returns the head of a tree.
head :: (Ord k) => AVLTree k v -> v
head :: forall k v. Ord k => AVLTree k v -> v
head AVLTree k v
Leaf = String -> v
forall a. HasCallStack => String -> a
error String
"took the head of an empty tree"
head (AVLTree k
_ v
v Int
_ Int
_ AVLTree k v
_ AVLTree k v
_) = v
v

-- | /O(lg n)/. 'tail' discards the head of the tree and returns a tree.
tail :: (Ord k) => AVLTree k v -> AVLTree k v
tail :: forall k v. Ord k => AVLTree k v -> AVLTree k v
tail AVLTree k v
Leaf = String -> AVLTree k v
forall a. HasCallStack => String -> a
error String
"took the tail of an empty tree"
tail t :: AVLTree k v
t@(AVLTree k
k v
_ Int
_ Int
_ AVLTree k v
_ AVLTree k v
_) = k -> AVLTree k v -> AVLTree k v
forall k v. Ord k => k -> AVLTree k v -> AVLTree k v
delete k
k AVLTree k v
t

-- | /O(1)/. 'size' reports the number of children in a tree
size :: AVLTree k v -> Int
size :: forall k v. AVLTree k v -> Int
size AVLTree k v
Leaf = Int
0
size (AVLTree k
_ v
_ Int
s Int
_ AVLTree k v
_ AVLTree k v
_) = Int
s

-- | /O(1)/. 'height' reports the maximum distance to a leaf.
height :: AVLTree k v -> Int
height :: forall k v. AVLTree k v -> Int
height AVLTree k v
Leaf = Int
0
height (AVLTree k
_ v
_ Int
_ Int
h AVLTree k v
_ AVLTree k v
_) = Int
h

findHeight :: AVLTree k v -> AVLTree k v -> Int
findHeight :: forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
a AVLTree k v
b = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int -> Int
forall a. Ord a => a -> a -> a
max (AVLTree k v -> Int
forall k v. AVLTree k v -> Int
height AVLTree k v
a) (AVLTree k v -> Int
forall k v. AVLTree k v -> Int
height AVLTree k v
b)

findSize :: AVLTree k v -> AVLTree k v -> Int
findSize :: forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
a AVLTree k v
b = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ AVLTree k v -> Int
forall k v. AVLTree k v -> Int
size AVLTree k v
a Int -> Int -> Int
forall a. Num a => a -> a -> a
+ AVLTree k v -> Int
forall k v. AVLTree k v -> Int
size AVLTree k v
b

balance :: (Ord k) => AVLTree k v -> AVLTree k v
balance :: forall k v. Ord k => AVLTree k v -> AVLTree k v
balance AVLTree k v
Leaf = AVLTree k v
forall k v. AVLTree k v
Leaf
balance t :: AVLTree k v
t@(AVLTree k
k v
v Int
_ Int
_ AVLTree k v
l AVLTree k v
r)
  | Int -> Int
forall a. Num a => a -> a
abs (AVLTree k v -> Int
forall k v. AVLTree k v -> Int
height AVLTree k v
l Int -> Int -> Int
forall a. Num a => a -> a -> a
- AVLTree k v -> Int
forall k v. AVLTree k v -> Int
height AVLTree k v
r) Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
2 = AVLTree k v
t
  | AVLTree k v -> Int
forall k v. AVLTree k v -> Int
height AVLTree k v
l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< AVLTree k v -> Int
forall k v. AVLTree k v -> Int
height AVLTree k v
r =
    case AVLTree k v
r of
      AVLTree k v
Leaf -> String -> AVLTree k v
forall a. HasCallStack => String -> a
error String
"cannot promote a leaf" -- this should never happen
      (AVLTree k
k1 v
v1 Int
_ Int
_ AVLTree k v
l1 AVLTree k v
r1) -> 
        let child :: AVLTree k v
child = (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k v
v (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
l AVLTree k v
l1) (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
l AVLTree k v
l1) AVLTree k v
l AVLTree k v
l1) in
          (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k1 v
v1 (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
child AVLTree k v
r1) (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
child AVLTree k v
r1) AVLTree k v
child AVLTree k v
r1)  
  | Bool
otherwise = 
    case AVLTree k v
l of
      AVLTree k v
Leaf -> String -> AVLTree k v
forall a. HasCallStack => String -> a
error String
"cannot promote a leaf"
      (AVLTree k
k1 v
v1 Int
_ Int
_ AVLTree k v
l1 AVLTree k v
r1) -> 
        let child :: AVLTree k v
child = (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k v
v (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
r1 AVLTree k v
r) (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
r1 AVLTree k v
r) AVLTree k v
r1 AVLTree k v
r) in
          (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k1 v
v1 (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
l1 AVLTree k v
child) (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
l1 AVLTree k v
child) AVLTree k v
l1 AVLTree k v
child)

(!!) :: (Ord k) => AVLTree k v -> Int -> (k,v)
!! :: forall k v. Ord k => AVLTree k v -> Int -> (k, v)
(!!) AVLTree k v
Leaf Int
_ = String -> (k, v)
forall a. HasCallStack => String -> a
error String
"index out of bounds"
(!!) (AVLTree k
k v
v Int
d Int
_ AVLTree k v
l AVLTree k v
r) Int
n
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
d = String -> (k, v)
forall a. HasCallStack => String -> a
error String
"index out of bounds"
  | Bool
otherwise = 
    let l' :: Int
l' = AVLTree k v -> Int
forall k v. AVLTree k v -> Int
size AVLTree k v
l in
      if Int
n Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
l'
      then (k
k,v
v)
      else if Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
l'
           then AVLTree k v
l AVLTree k v -> Int -> (k, v)
forall k v. Ord k => AVLTree k v -> Int -> (k, v)
!! Int
n
           else AVLTree k v
r AVLTree k v -> Int -> (k, v)
forall k v. Ord k => AVLTree k v -> Int -> (k, v)
!! (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
l' Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)

-- | /O(lg n)/.
lookup :: (Ord k) => k -> AVLTree k v -> Maybe v
lookup :: forall k v. Ord k => k -> AVLTree k v -> Maybe v
lookup k
_ AVLTree k v
Leaf = Maybe v
forall a. Maybe a
Nothing
lookup k
k' (AVLTree k
k v
v Int
_ Int
_ AVLTree k v
l AVLTree k v
r)
  | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k' = v -> Maybe v
forall a. a -> Maybe a
Just v
v
  | k
k' k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k = k -> AVLTree k v -> Maybe v
forall k v. Ord k => k -> AVLTree k v -> Maybe v
lookup k
k' AVLTree k v
l
  | Bool
otherwise = k -> AVLTree k v -> Maybe v
forall k v. Ord k => k -> AVLTree k v -> Maybe v
lookup k
k' AVLTree k v
r

-- | /O(lg n)/.
insert :: (Ord k) => k -> v -> AVLTree k v -> AVLTree k v
insert :: forall k v. Ord k => k -> v -> AVLTree k v -> AVLTree k v
insert k
k v
v AVLTree k v
Leaf = k -> v -> AVLTree k v
forall k v. Ord k => k -> v -> AVLTree k v
singleton k
k v
v
insert k
k v
v (AVLTree k
k1 v
v1 Int
s Int
_ AVLTree k v
l AVLTree k v
r) =
  if k
k k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<= k
k1
  then let l' :: AVLTree k v
l' = k -> v -> AVLTree k v -> AVLTree k v
forall k v. Ord k => k -> v -> AVLTree k v -> AVLTree k v
insert k
k v
v AVLTree k v
l in
    AVLTree k v -> AVLTree k v
forall k v. Ord k => AVLTree k v -> AVLTree k v
balance (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k1 v
v1 (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
l' AVLTree k v
r) AVLTree k v
l' AVLTree k v
r)
  else let r' :: AVLTree k v
r' = k -> v -> AVLTree k v -> AVLTree k v
forall k v. Ord k => k -> v -> AVLTree k v -> AVLTree k v
insert k
k v
v AVLTree k v
r in
    AVLTree k v -> AVLTree k v
forall k v. Ord k => AVLTree k v -> AVLTree k v
balance (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k1 v
v1 (Int
s Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
l AVLTree k v
r') AVLTree k v
l AVLTree k v
r')

-- | /O(lg n)/.
delete :: (Ord k) => k -> AVLTree k v -> AVLTree k v
delete :: forall k v. Ord k => k -> AVLTree k v -> AVLTree k v
delete k
_ AVLTree k v
Leaf = AVLTree k v
forall k v. AVLTree k v
Leaf
delete k
k t :: AVLTree k v
t@(AVLTree k
k1 v
_ Int
_ Int
_ AVLTree k v
Leaf AVLTree k v
Leaf) = if k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k1 then AVLTree k v
forall k v. AVLTree k v
Leaf else AVLTree k v
t
delete k
k t :: AVLTree k v
t@(AVLTree k
k1 v
v1 Int
_ Int
_ AVLTree k v
l AVLTree k v
r)
  | k
k k -> k -> Bool
forall a. Eq a => a -> a -> Bool
== k
k1 =
    case AVLTree k v
t of
      AVLTree k v
Leaf -> AVLTree k v
forall k v. AVLTree k v
Leaf
      (AVLTree k
_ v
_ Int
_ Int
_ AVLTree k v
Leaf AVLTree k v
r1) -> 
        case AVLTree k v -> (Maybe (k, v), AVLTree k v)
forall k v. Ord k => AVLTree k v -> (Maybe (k, v), AVLTree k v)
getLeft AVLTree k v
r1 of
          (Maybe (k, v)
Nothing, AVLTree k v
_) -> AVLTree k v
forall k v. AVLTree k v
Leaf
          (Just (k
k', v
v'), AVLTree k v
r') -> 
            AVLTree k v -> AVLTree k v
forall k v. Ord k => AVLTree k v -> AVLTree k v
balance (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k' v
v' (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
forall k v. AVLTree k v
Leaf AVLTree k v
r') (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
forall k v. AVLTree k v
Leaf AVLTree k v
r') AVLTree k v
forall k v. AVLTree k v
Leaf AVLTree k v
r')
      (AVLTree k
_ v
_ Int
_ Int
_ AVLTree k v
l1 AVLTree k v
r1) -> 
        case AVLTree k v -> (Maybe (k, v), AVLTree k v)
forall k v. Ord k => AVLTree k v -> (Maybe (k, v), AVLTree k v)
getRight AVLTree k v
l1 of
          (Maybe (k, v)
Nothing, AVLTree k v
_) -> AVLTree k v
forall k v. AVLTree k v
Leaf
          (Just (k
k', v
v'), AVLTree k v
l') -> 
            AVLTree k v -> AVLTree k v
forall k v. Ord k => AVLTree k v -> AVLTree k v
balance (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k' v
v' (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
l' AVLTree k v
r1) (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
l' AVLTree k v
r1) AVLTree k v
l' AVLTree k v
r1)
    | k
k k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k1 =
      let l' :: AVLTree k v
l' = k -> AVLTree k v -> AVLTree k v
forall k v. Ord k => k -> AVLTree k v -> AVLTree k v
delete k
k AVLTree k v
l in
        AVLTree k v -> AVLTree k v
forall k v. Ord k => AVLTree k v -> AVLTree k v
balance (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k1 v
v1 (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
l' AVLTree k v
r) (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
l' AVLTree k v
r) AVLTree k v
l' AVLTree k v
r)
    | Bool
otherwise =
      let r' :: AVLTree k v
r' = k -> AVLTree k v -> AVLTree k v
forall k v. Ord k => k -> AVLTree k v -> AVLTree k v
delete k
k AVLTree k v
r in
        AVLTree k v -> AVLTree k v
forall k v. Ord k => AVLTree k v -> AVLTree k v
balance (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k1 v
v1 (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
l AVLTree k v
r') (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
l AVLTree k v
r') AVLTree k v
l AVLTree k v
r')

getRight :: (Ord k) => AVLTree k v -> (Maybe (k,v), AVLTree k v)
getRight :: forall k v. Ord k => AVLTree k v -> (Maybe (k, v), AVLTree k v)
getRight AVLTree k v
Leaf = (Maybe (k, v)
forall a. Maybe a
Nothing, AVLTree k v
forall k v. AVLTree k v
Leaf)
getRight (AVLTree k
k v
v Int
_ Int
_ AVLTree k v
Leaf AVLTree k v
Leaf) = ((k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
k,v
v), AVLTree k v
forall k v. AVLTree k v
Leaf)
getRight (AVLTree k
k v
v Int
_ Int
_ AVLTree k v
l AVLTree k v
Leaf) = ((k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
k,v
v), AVLTree k v
l)
getRight (AVLTree k
k v
v Int
_ Int
_ AVLTree k v
l AVLTree k v
r) = 
  case AVLTree k v -> (Maybe (k, v), AVLTree k v)
forall k v. Ord k => AVLTree k v -> (Maybe (k, v), AVLTree k v)
getRight AVLTree k v
r of
    (Maybe (k, v)
p, AVLTree k v
t2) -> (Maybe (k, v)
p, AVLTree k v -> AVLTree k v
forall k v. Ord k => AVLTree k v -> AVLTree k v
balance (k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k v
v (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
l AVLTree k v
t2) (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
l AVLTree k v
t2) AVLTree k v
l AVLTree k v
t2))

getLeft :: (Ord k) => AVLTree k v -> (Maybe (k,v), AVLTree k v)
getLeft :: forall k v. Ord k => AVLTree k v -> (Maybe (k, v), AVLTree k v)
getLeft AVLTree k v
Leaf = (Maybe (k, v)
forall a. Maybe a
Nothing, AVLTree k v
forall k v. AVLTree k v
Leaf)
getLeft (AVLTree k
k v
v Int
_ Int
_ AVLTree k v
Leaf AVLTree k v
Leaf) = ((k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
k,v
v), AVLTree k v
forall k v. AVLTree k v
Leaf)
getLeft (AVLTree k
k v
v Int
_ Int
_ AVLTree k v
Leaf AVLTree k v
r) = ((k, v) -> Maybe (k, v)
forall a. a -> Maybe a
Just (k
k,v
v), AVLTree k v
r)
getLeft (AVLTree k
k v
v Int
_ Int
_ AVLTree k v
_ AVLTree k v
r) = 
  case AVLTree k v -> (Maybe (k, v), AVLTree k v)
forall k v. Ord k => AVLTree k v -> (Maybe (k, v), AVLTree k v)
getLeft AVLTree k v
r of
    (Maybe (k, v)
p, AVLTree k v
t2) -> (Maybe (k, v)
p, k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
forall k v.
k -> v -> Int -> Int -> AVLTree k v -> AVLTree k v -> AVLTree k v
AVLTree k
k v
v (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findSize AVLTree k v
r AVLTree k v
t2) (AVLTree k v -> AVLTree k v -> Int
forall k v. AVLTree k v -> AVLTree k v -> Int
findHeight AVLTree k v
r AVLTree k v
t2) AVLTree k v
t2 AVLTree k v
r)

-- | /O(n lg n)/.
fromList :: (Ord k) => [(k,v)] -> AVLTree k v
fromList :: forall k v. Ord k => [(k, v)] -> AVLTree k v
fromList [] = AVLTree k v
forall k v. AVLTree k v
Leaf
fromList ((k
k,v
v):[]) = k -> v -> AVLTree k v
forall k v. Ord k => k -> v -> AVLTree k v
singleton k
k v
v
fromList ((k
k,v
v):[(k, v)]
tl) = k -> v -> AVLTree k v -> AVLTree k v
forall k v. Ord k => k -> v -> AVLTree k v -> AVLTree k v
insert k
k v
v ([(k, v)] -> AVLTree k v
forall k v. Ord k => [(k, v)] -> AVLTree k v
fromList [(k, v)]
tl)

-- | /O(n lg n)/.
fromAscList :: (Ord k) => [(k,v)] -> AVLTree k v
fromAscList :: forall k v. Ord k => [(k, v)] -> AVLTree k v
fromAscList = [(k, v)] -> AVLTree k v
forall k v. Ord k => [(k, v)] -> AVLTree k v
fromList

-- TODO implement an instance of foldable so that this can be concisely defined
-- | /O(n lg n)/.
toAscList :: (Ord k) => AVLTree k v -> [(k,v)]
toAscList :: forall k v. Ord k => AVLTree k v -> [(k, v)]
toAscList AVLTree k v
Leaf = []
toAscList (AVLTree k
k v
v Int
_ Int
_ AVLTree k v
l AVLTree k v
r) = AVLTree k v -> [(k, v)]
forall k v. Ord k => AVLTree k v -> [(k, v)]
toAscList AVLTree k v
l [(k, v)] -> [(k, v)] -> [(k, v)]
forall a. [a] -> [a] -> [a]
++ (k
k,v
v) (k, v) -> [(k, v)] -> [(k, v)]
forall a. a -> [a] -> [a]
: AVLTree k v -> [(k, v)]
forall k v. Ord k => AVLTree k v -> [(k, v)]
toAscList AVLTree k v
r

-- | /O(n lg n)/.
toList :: (Ord k) => AVLTree k v -> [(k,v)]
toList :: forall k v. Ord k => AVLTree k v -> [(k, v)]
toList = AVLTree k v -> [(k, v)]
forall k v. Ord k => AVLTree k v -> [(k, v)]
toAscList