132.73/107.24	MAYBE
135.27/107.99	proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
135.27/107.99	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
135.27/107.99	
135.27/107.99	
135.27/107.99	H-Termination with start terms of the given HASKELL could not be shown:
135.27/107.99	
135.27/107.99	(0) HASKELL
135.27/107.99	(1) LR [EQUIVALENT, 0 ms]
135.27/107.99	(2) HASKELL
135.27/107.99	(3) CR [EQUIVALENT, 0 ms]
135.27/107.99	(4) HASKELL
135.27/107.99	(5) BR [EQUIVALENT, 0 ms]
135.27/107.99	(6) HASKELL
135.27/107.99	(7) COR [EQUIVALENT, 9 ms]
135.27/107.99	(8) HASKELL
135.27/107.99	(9) LetRed [EQUIVALENT, 33 ms]
135.27/107.99	(10) HASKELL
135.27/107.99	(11) NumRed [SOUND, 0 ms]
135.27/107.99	(12) HASKELL
135.27/107.99	
135.27/107.99	
135.27/107.99	----------------------------------------
135.27/107.99	
135.27/107.99	(0)
135.27/107.99	Obligation:
135.27/107.99	mainModule Main 
135.27/107.99	module FiniteMap where {
135.27/107.99	import qualified Main;
135.27/107.99	import qualified Maybe;
135.27/107.99	import qualified Prelude;
135.27/107.99	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
135.27/107.99	
135.27/107.99	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
135.27/107.99	}
135.27/107.99	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
135.27/107.99	addToFM fm key elt = addToFM_C (\old new ->new) fm key elt;
135.27/107.99	
135.27/107.99	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
135.27/107.99	addToFM_C combiner EmptyFM key elt = unitFM key elt;
135.27/107.99	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
135.27/107.99	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
135.27/107.99	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
135.27/107.99	
135.27/107.99	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
135.27/107.99	deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l;
135.27/107.99	deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
135.27/107.99	
135.27/107.99	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
135.27/107.99	deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r;
135.27/107.99	deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
135.27/107.99	
135.27/107.99	emptyFM :: FiniteMap b a;
135.27/107.99	emptyFM = EmptyFM;
135.27/107.99	
135.27/107.99	findMax :: FiniteMap a b  ->  (a,b);
135.27/107.99	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
135.27/107.99	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
135.27/107.99	
135.27/107.99	findMin :: FiniteMap a b  ->  (a,b);
135.27/107.99	findMin (Branch key elt _ EmptyFM _) = (key,elt);
135.27/107.99	findMin (Branch key elt _ fm_l _) = findMin fm_l;
135.27/107.99	
135.27/107.99	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
135.27/107.99	glueBal EmptyFM fm2 = fm2;
135.27/107.99	glueBal fm1 EmptyFM = fm1;
135.27/107.99	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
135.27/107.99	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
135.27/107.99	mid_elt1 = (\(_,mid_elt1) ->mid_elt1) vv2;
135.27/107.99	mid_elt2 = (\(_,mid_elt2) ->mid_elt2) vv3;
135.27/107.99	mid_key1 = (\(mid_key1,_) ->mid_key1) vv2;
135.27/107.99	mid_key2 = (\(mid_key2,_) ->mid_key2) vv3;
135.27/107.99	vv2 = findMax fm1;
135.27/107.99	vv3 = findMin fm2;
135.27/107.99	 };
135.27/107.99	
135.27/107.99	glueVBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
135.27/107.99	glueVBal EmptyFM fm2 = fm2;
135.27/107.99	glueVBal fm1 EmptyFM = fm1;
135.27/107.99	glueVBal fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (glueVBal fm_l fm_rl) fm_rr
135.27/107.99	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r)
135.27/107.99	 | otherwise = glueBal fm_l fm_r where { 
135.27/107.99	size_l = sizeFM fm_l;
135.27/107.99	size_r = sizeFM fm_r;
135.27/107.99	 };
135.27/107.99	
135.27/107.99	minusFM :: Ord a => FiniteMap a b  ->  FiniteMap a c  ->  FiniteMap a b;
135.27/107.99	minusFM EmptyFM fm2 = emptyFM;
135.27/107.99	minusFM fm1 EmptyFM = fm1;
135.27/107.99	minusFM fm1 (Branch split_key elt _ left right) = glueVBal (minusFM lts left) (minusFM gts right) where { 
135.27/107.99	gts = splitGT fm1 split_key;
135.27/107.99	lts = splitLT fm1 split_key;
135.27/107.99	 };
135.27/107.99	
135.27/107.99	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/107.99	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
135.27/107.99	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
135.27/107.99	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
135.27/107.99	 | otherwise -> double_L fm_L fm_R; 
135.27/107.99	 } 
135.27/107.99	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
135.27/107.99	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
135.27/107.99	 | otherwise -> double_R fm_L fm_R; 
135.27/107.99	 } 
135.27/107.99	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
135.27/107.99	double_L fm_l (Branch key_r elt_r _ (Branch key_rl elt_rl _ fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
135.27/107.99	double_R (Branch key_l elt_l _ fm_ll (Branch key_lr elt_lr _ fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
135.27/107.99	single_L fm_l (Branch key_r elt_r _ fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
135.27/107.99	single_R (Branch key_l elt_l _ fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
135.27/107.99	size_l = sizeFM fm_L;
135.27/107.99	size_r = sizeFM fm_R;
135.27/107.99	 };
135.27/107.99	
135.27/107.99	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/107.99	mkBranch which key elt fm_l fm_r = let { 
135.27/107.99	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
135.27/107.99	} in result where { 
135.27/107.99	balance_ok = True;
135.27/107.99	left_ok = case fm_l of { 
135.27/107.99	EmptyFM-> True; 
135.27/107.99	Branch left_key _ _ _ _-> let { 
135.27/107.99	biggest_left_key = fst (findMax fm_l);
135.27/107.99	} in biggest_left_key < key; 
135.27/107.99	 } ;
135.27/107.99	left_size = sizeFM fm_l;
135.27/107.99	right_ok = case fm_r of { 
135.27/107.99	EmptyFM-> True; 
135.27/107.99	Branch right_key _ _ _ _-> let { 
135.27/107.99	smallest_right_key = fst (findMin fm_r);
135.27/107.99	} in key < smallest_right_key; 
135.27/107.99	 } ;
135.27/107.99	right_size = sizeFM fm_r;
135.27/107.99	unbox :: Int  ->  Int;
135.27/107.99	unbox x = x;
135.27/107.99	 };
135.27/107.99	
135.27/107.99	mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/107.99	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
135.27/107.99	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
135.27/107.99	mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr
135.27/107.99	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
135.27/107.99	 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
135.27/107.99	size_l = sizeFM fm_l;
135.27/107.99	size_r = sizeFM fm_r;
135.27/107.99	 };
135.27/107.99	
135.27/107.99	sIZE_RATIO :: Int;
135.27/107.99	sIZE_RATIO = 5;
135.27/107.99	
135.27/107.99	sizeFM :: FiniteMap b a  ->  Int;
135.27/107.99	sizeFM EmptyFM = 0;
135.27/107.99	sizeFM (Branch _ _ size _ _) = size;
135.27/107.99	
135.27/107.99	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
135.27/107.99	splitGT EmptyFM split_key = emptyFM;
135.27/107.99	splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
135.27/107.99	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
135.27/107.99	 | otherwise = fm_r;
135.27/107.99	
135.27/107.99	splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
135.27/107.99	splitLT EmptyFM split_key = emptyFM;
135.27/107.99	splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
135.27/107.99	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
135.27/107.99	 | otherwise = fm_l;
135.27/107.99	
135.27/107.99	unitFM :: b  ->  a  ->  FiniteMap b a;
135.27/107.99	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
135.27/107.99	
135.27/107.99	}
135.27/107.99	module Maybe where {
135.27/107.99	import qualified FiniteMap;
135.27/107.99	import qualified Main;
135.27/107.99	import qualified Prelude;
135.27/107.99	}
135.27/107.99	module Main where {
135.27/107.99	import qualified FiniteMap;
135.27/107.99	import qualified Maybe;
135.27/107.99	import qualified Prelude;
135.27/107.99	}
135.27/107.99	
135.27/107.99	----------------------------------------
135.27/107.99	
135.27/107.99	(1) LR (EQUIVALENT)
135.27/107.99	Lambda Reductions:
135.27/107.99	The following Lambda expression
135.27/107.99	"\oldnew->new"
135.27/107.99	is transformed to
135.27/107.99	"addToFM0 old new = new;
135.27/107.99	"
135.27/107.99	The following Lambda expression
135.27/107.99	"\(_,mid_elt2)->mid_elt2"
135.27/107.99	is transformed to
135.27/107.99	"mid_elt20 (_,mid_elt2) = mid_elt2;
135.27/107.99	"
135.27/107.99	The following Lambda expression
135.27/107.99	"\(mid_key2,_)->mid_key2"
135.27/107.99	is transformed to
135.27/107.99	"mid_key20 (mid_key2,_) = mid_key2;
135.27/107.99	"
135.27/107.99	The following Lambda expression
135.27/107.99	"\(mid_key1,_)->mid_key1"
135.27/107.99	is transformed to
135.27/107.99	"mid_key10 (mid_key1,_) = mid_key1;
135.27/107.99	"
135.27/107.99	The following Lambda expression
135.27/107.99	"\(_,mid_elt1)->mid_elt1"
135.27/107.99	is transformed to
135.27/107.99	"mid_elt10 (_,mid_elt1) = mid_elt1;
135.27/107.99	"
135.27/107.99	
135.27/107.99	----------------------------------------
135.27/107.99	
135.27/107.99	(2)
135.27/107.99	Obligation:
135.27/107.99	mainModule Main 
135.27/107.99	module FiniteMap where {
135.27/107.99	import qualified Main;
135.27/107.99	import qualified Maybe;
135.27/107.99	import qualified Prelude;
135.27/107.99	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
135.27/107.99	
135.27/107.99	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
135.27/107.99	}
135.27/107.99	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
135.27/107.99	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
135.27/107.99	
135.27/107.99	addToFM0 old new = new;
135.27/107.99	
135.27/107.99	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
135.27/107.99	addToFM_C combiner EmptyFM key elt = unitFM key elt;
135.27/107.99	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
135.27/108.00	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
135.27/108.00	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
135.27/108.00	
135.27/108.00	deleteMax :: Ord b => FiniteMap b a  ->  FiniteMap b a;
135.27/108.00	deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l;
135.27/108.00	deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
135.27/108.00	
135.27/108.00	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
135.27/108.00	deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r;
135.27/108.00	deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
135.27/108.00	
135.27/108.00	emptyFM :: FiniteMap a b;
135.27/108.00	emptyFM = EmptyFM;
135.27/108.00	
135.27/108.00	findMax :: FiniteMap a b  ->  (a,b);
135.27/108.00	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
135.27/108.00	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
135.27/108.00	
135.27/108.00	findMin :: FiniteMap b a  ->  (b,a);
135.27/108.00	findMin (Branch key elt _ EmptyFM _) = (key,elt);
135.27/108.00	findMin (Branch key elt _ fm_l _) = findMin fm_l;
135.27/108.00	
135.27/108.00	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
135.27/108.00	glueBal EmptyFM fm2 = fm2;
135.27/108.00	glueBal fm1 EmptyFM = fm1;
135.27/108.00	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
135.27/108.00	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
135.27/108.00	mid_elt1 = mid_elt10 vv2;
135.27/108.00	mid_elt10 (_,mid_elt1) = mid_elt1;
135.27/108.00	mid_elt2 = mid_elt20 vv3;
135.27/108.00	mid_elt20 (_,mid_elt2) = mid_elt2;
135.27/108.00	mid_key1 = mid_key10 vv2;
135.27/108.00	mid_key10 (mid_key1,_) = mid_key1;
135.27/108.00	mid_key2 = mid_key20 vv3;
135.27/108.00	mid_key20 (mid_key2,_) = mid_key2;
135.27/108.00	vv2 = findMax fm1;
135.27/108.00	vv3 = findMin fm2;
135.27/108.00	 };
135.27/108.00	
135.27/108.00	glueVBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/108.00	glueVBal EmptyFM fm2 = fm2;
135.27/108.00	glueVBal fm1 EmptyFM = fm1;
135.27/108.00	glueVBal fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (glueVBal fm_l fm_rl) fm_rr
135.27/108.00	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r)
135.27/108.00	 | otherwise = glueBal fm_l fm_r where { 
135.27/108.00	size_l = sizeFM fm_l;
135.27/108.00	size_r = sizeFM fm_r;
135.27/108.00	 };
135.27/108.00	
135.27/108.00	minusFM :: Ord b => FiniteMap b c  ->  FiniteMap b a  ->  FiniteMap b c;
135.27/108.00	minusFM EmptyFM fm2 = emptyFM;
135.27/108.00	minusFM fm1 EmptyFM = fm1;
135.27/108.00	minusFM fm1 (Branch split_key elt _ left right) = glueVBal (minusFM lts left) (minusFM gts right) where { 
135.27/108.00	gts = splitGT fm1 split_key;
135.27/108.00	lts = splitLT fm1 split_key;
135.27/108.00	 };
135.27/108.00	
135.27/108.00	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
135.27/108.00	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
135.27/108.00	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
135.27/108.00	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
135.27/108.00	 | otherwise -> double_L fm_L fm_R; 
135.27/108.00	 } 
135.27/108.00	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
135.27/108.00	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
135.27/108.00	 | otherwise -> double_R fm_L fm_R; 
135.27/108.00	 } 
135.27/108.00	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
135.27/108.00	double_L fm_l (Branch key_r elt_r _ (Branch key_rl elt_rl _ fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
135.27/108.00	double_R (Branch key_l elt_l _ fm_ll (Branch key_lr elt_lr _ fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
135.27/108.00	single_L fm_l (Branch key_r elt_r _ fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
135.27/108.00	single_R (Branch key_l elt_l _ fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
135.27/108.00	size_l = sizeFM fm_L;
135.27/108.00	size_r = sizeFM fm_R;
135.27/108.00	 };
135.27/108.00	
135.27/108.00	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/108.00	mkBranch which key elt fm_l fm_r = let { 
135.27/108.00	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
135.27/108.00	} in result where { 
135.27/108.00	balance_ok = True;
135.27/108.00	left_ok = case fm_l of { 
135.27/108.00	EmptyFM-> True; 
135.27/108.00	Branch left_key _ _ _ _-> let { 
135.27/108.00	biggest_left_key = fst (findMax fm_l);
135.27/108.00	} in biggest_left_key < key; 
135.27/108.00	 } ;
135.27/108.00	left_size = sizeFM fm_l;
135.27/108.00	right_ok = case fm_r of { 
135.27/108.00	EmptyFM-> True; 
135.27/108.00	Branch right_key _ _ _ _-> let { 
135.27/108.00	smallest_right_key = fst (findMin fm_r);
135.27/108.00	} in key < smallest_right_key; 
135.27/108.00	 } ;
135.27/108.00	right_size = sizeFM fm_r;
135.27/108.00	unbox :: Int  ->  Int;
135.27/108.00	unbox x = x;
135.27/108.00	 };
135.27/108.00	
135.27/108.00	mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/108.00	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
135.27/108.00	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
135.27/108.00	mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr
135.27/108.00	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
135.27/108.00	 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
135.27/108.00	size_l = sizeFM fm_l;
135.27/108.00	size_r = sizeFM fm_r;
135.27/108.00	 };
135.27/108.00	
135.27/108.00	sIZE_RATIO :: Int;
135.27/108.00	sIZE_RATIO = 5;
135.27/108.00	
135.27/108.00	sizeFM :: FiniteMap b a  ->  Int;
135.27/108.00	sizeFM EmptyFM = 0;
135.27/108.00	sizeFM (Branch _ _ size _ _) = size;
135.27/108.00	
135.27/108.00	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
135.27/108.00	splitGT EmptyFM split_key = emptyFM;
135.27/108.00	splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
135.27/108.00	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
135.27/108.00	 | otherwise = fm_r;
135.27/108.01	
135.27/108.01	splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
135.27/108.01	splitLT EmptyFM split_key = emptyFM;
135.27/108.01	splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
135.27/108.01	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
135.27/108.01	 | otherwise = fm_l;
135.27/108.01	
135.27/108.01	unitFM :: b  ->  a  ->  FiniteMap b a;
135.27/108.01	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
135.27/108.01	
135.27/108.01	}
135.27/108.01	module Maybe where {
135.27/108.01	import qualified FiniteMap;
135.27/108.01	import qualified Main;
135.27/108.01	import qualified Prelude;
135.27/108.01	}
135.27/108.01	module Main where {
135.27/108.01	import qualified FiniteMap;
135.27/108.01	import qualified Maybe;
135.27/108.01	import qualified Prelude;
135.27/108.01	}
135.27/108.01	
135.27/108.01	----------------------------------------
135.27/108.01	
135.27/108.01	(3) CR (EQUIVALENT)
135.27/108.01	Case Reductions:
135.27/108.01	The following Case expression
135.27/108.01	"case fm_r of {
135.27/108.01	EmptyFM  -> True;
135.27/108.01	Branch right_key _ _ _ _  -> let {
135.27/108.01	smallest_right_key  = fst (findMin fm_r);
135.27/108.01	} in key < smallest_right_key}
135.27/108.01	"
135.27/108.01	is transformed to
135.27/108.01	"right_ok0 fm_r key EmptyFM = True;
135.27/108.01	right_ok0 fm_r key (Branch right_key _ _ _ _) = let {
135.27/108.01	smallest_right_key  = fst (findMin fm_r);
135.27/108.01	} in key < smallest_right_key;
135.27/108.01	"
135.27/108.01	The following Case expression
135.27/108.01	"case fm_l of {
135.27/108.01	EmptyFM  -> True;
135.27/108.01	Branch left_key _ _ _ _  -> let {
135.27/108.01	biggest_left_key  = fst (findMax fm_l);
135.27/108.01	} in biggest_left_key < key}
135.27/108.01	"
135.27/108.01	is transformed to
135.27/108.01	"left_ok0 fm_l key EmptyFM = True;
135.27/108.01	left_ok0 fm_l key (Branch left_key _ _ _ _) = let {
135.27/108.01	biggest_left_key  = fst (findMax fm_l);
135.27/108.01	} in biggest_left_key < key;
135.27/108.01	"
135.27/108.01	The following Case expression
135.27/108.01	"case fm_R of {
135.27/108.01	Branch _ _ _ fm_rl fm_rr |sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R}
135.27/108.01	"
135.27/108.01	is transformed to
135.27/108.01	"mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
135.27/108.01	"
135.27/108.01	The following Case expression
135.27/108.01	"case fm_L of {
135.27/108.01	Branch _ _ _ fm_ll fm_lr |sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R}
135.27/108.01	"
135.27/108.01	is transformed to
135.27/108.01	"mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
135.27/108.01	"
135.27/108.01	
135.27/108.01	----------------------------------------
135.27/108.01	
135.27/108.01	(4)
135.27/108.01	Obligation:
135.27/108.01	mainModule Main 
135.27/108.01	module FiniteMap where {
135.27/108.01	import qualified Main;
135.27/108.01	import qualified Maybe;
135.27/108.01	import qualified Prelude;
135.27/108.01	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
135.27/108.01	
135.27/108.01	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
135.27/108.01	}
135.27/108.01	addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
135.27/108.01	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
135.27/108.01	
135.27/108.01	addToFM0 old new = new;
135.27/108.01	
135.27/108.01	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
135.27/108.01	addToFM_C combiner EmptyFM key elt = unitFM key elt;
135.27/108.01	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
135.27/108.01	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
135.27/108.01	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
135.27/108.01	
135.27/108.01	deleteMax :: Ord b => FiniteMap b a  ->  FiniteMap b a;
135.27/108.01	deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l;
135.27/108.01	deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
135.27/108.01	
135.27/108.01	deleteMin :: Ord a => FiniteMap a b  ->  FiniteMap a b;
135.27/108.01	deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r;
135.27/108.01	deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
135.27/108.01	
135.27/108.01	emptyFM :: FiniteMap a b;
135.27/108.01	emptyFM = EmptyFM;
135.27/108.01	
135.27/108.01	findMax :: FiniteMap b a  ->  (b,a);
135.27/108.01	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
135.27/108.01	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
135.27/108.01	
135.27/108.01	findMin :: FiniteMap a b  ->  (a,b);
135.27/108.01	findMin (Branch key elt _ EmptyFM _) = (key,elt);
135.27/108.01	findMin (Branch key elt _ fm_l _) = findMin fm_l;
135.27/108.01	
135.27/108.01	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
135.27/108.01	glueBal EmptyFM fm2 = fm2;
135.27/108.01	glueBal fm1 EmptyFM = fm1;
135.27/108.01	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
135.27/108.01	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
135.27/108.01	mid_elt1 = mid_elt10 vv2;
135.27/108.01	mid_elt10 (_,mid_elt1) = mid_elt1;
135.27/108.01	mid_elt2 = mid_elt20 vv3;
135.27/108.01	mid_elt20 (_,mid_elt2) = mid_elt2;
135.27/108.01	mid_key1 = mid_key10 vv2;
135.27/108.01	mid_key10 (mid_key1,_) = mid_key1;
135.27/108.01	mid_key2 = mid_key20 vv3;
135.27/108.01	mid_key20 (mid_key2,_) = mid_key2;
135.27/108.01	vv2 = findMax fm1;
135.27/108.01	vv3 = findMin fm2;
135.27/108.01	 };
135.27/108.01	
135.27/108.01	glueVBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/108.01	glueVBal EmptyFM fm2 = fm2;
135.27/108.01	glueVBal fm1 EmptyFM = fm1;
135.27/108.01	glueVBal fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (glueVBal fm_l fm_rl) fm_rr
135.27/108.01	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r)
135.27/108.01	 | otherwise = glueBal fm_l fm_r where { 
135.27/108.01	size_l = sizeFM fm_l;
135.27/108.01	size_r = sizeFM fm_r;
135.27/108.01	 };
135.27/108.01	
135.27/108.01	minusFM :: Ord c => FiniteMap c b  ->  FiniteMap c a  ->  FiniteMap c b;
135.27/108.01	minusFM EmptyFM fm2 = emptyFM;
135.27/108.01	minusFM fm1 EmptyFM = fm1;
135.27/108.01	minusFM fm1 (Branch split_key elt _ left right) = glueVBal (minusFM lts left) (minusFM gts right) where { 
135.27/108.01	gts = splitGT fm1 split_key;
135.27/108.01	lts = splitLT fm1 split_key;
135.27/108.01	 };
135.27/108.01	
135.27/108.01	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
135.27/108.01	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
135.27/108.01	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
135.27/108.01	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
135.27/108.01	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
135.27/108.01	double_L fm_l (Branch key_r elt_r _ (Branch key_rl elt_rl _ fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
135.27/108.01	double_R (Branch key_l elt_l _ fm_ll (Branch key_lr elt_lr _ fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
135.27/108.01	mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
135.27/108.01	 | otherwise = double_L fm_L fm_R;
135.27/108.01	mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
135.27/108.01	 | otherwise = double_R fm_L fm_R;
135.27/108.01	single_L fm_l (Branch key_r elt_r _ fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
135.27/108.01	single_R (Branch key_l elt_l _ fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
135.27/108.01	size_l = sizeFM fm_L;
135.27/108.01	size_r = sizeFM fm_R;
135.27/108.01	 };
135.27/108.01	
135.27/108.01	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
135.27/108.01	mkBranch which key elt fm_l fm_r = let { 
135.27/108.01	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
135.27/108.01	} in result where { 
135.27/108.01	balance_ok = True;
135.27/108.01	left_ok = left_ok0 fm_l key fm_l;
135.27/108.01	left_ok0 fm_l key EmptyFM = True;
135.27/108.01	left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 
135.27/108.01	biggest_left_key = fst (findMax fm_l);
135.27/108.01	} in biggest_left_key < key;
135.27/108.01	left_size = sizeFM fm_l;
135.27/108.01	right_ok = right_ok0 fm_r key fm_r;
135.27/108.01	right_ok0 fm_r key EmptyFM = True;
135.27/108.01	right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 
135.27/108.01	smallest_right_key = fst (findMin fm_r);
135.27/108.01	} in key < smallest_right_key;
135.27/108.01	right_size = sizeFM fm_r;
135.27/108.01	unbox :: Int  ->  Int;
135.27/108.01	unbox x = x;
135.27/108.01	 };
135.27/108.01	
135.27/108.01	mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/108.01	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
135.27/108.01	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
135.27/108.01	mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr
135.27/108.01	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
135.27/108.01	 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
135.27/108.01	size_l = sizeFM fm_l;
135.27/108.01	size_r = sizeFM fm_r;
135.27/108.01	 };
135.27/108.01	
135.27/108.01	sIZE_RATIO :: Int;
135.27/108.01	sIZE_RATIO = 5;
135.27/108.01	
135.27/108.01	sizeFM :: FiniteMap a b  ->  Int;
135.27/108.01	sizeFM EmptyFM = 0;
135.27/108.01	sizeFM (Branch _ _ size _ _) = size;
135.27/108.01	
135.27/108.01	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
135.27/108.01	splitGT EmptyFM split_key = emptyFM;
135.27/108.01	splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
135.27/108.01	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
135.27/108.01	 | otherwise = fm_r;
135.27/108.01	
135.27/108.01	splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
135.27/108.01	splitLT EmptyFM split_key = emptyFM;
135.27/108.01	splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
135.27/108.01	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
135.27/108.01	 | otherwise = fm_l;
135.27/108.01	
135.27/108.01	unitFM :: a  ->  b  ->  FiniteMap a b;
135.27/108.01	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
135.27/108.01	
135.27/108.01	}
135.27/108.01	module Maybe where {
135.27/108.01	import qualified FiniteMap;
135.27/108.01	import qualified Main;
135.27/108.01	import qualified Prelude;
135.27/108.01	}
135.27/108.01	module Main where {
135.27/108.01	import qualified FiniteMap;
135.27/108.01	import qualified Maybe;
135.27/108.01	import qualified Prelude;
135.27/108.01	}
135.27/108.01	
135.27/108.01	----------------------------------------
135.27/108.01	
135.27/108.01	(5) BR (EQUIVALENT)
135.27/108.01	Replaced joker patterns by fresh variables and removed binding patterns.
135.27/108.01	
135.27/108.01	Binding Reductions:
135.27/108.01	The bind variable of the following binding Pattern
135.27/108.01	"fm_l@(Branch wu wv ww wx wy)"
135.27/108.01	is replaced by the following term
135.27/108.01	"Branch wu wv ww wx wy"
135.27/108.01	The bind variable of the following binding Pattern
135.27/108.01	"fm_r@(Branch xu xv xw xx xy)"
135.27/108.01	is replaced by the following term
135.27/108.01	"Branch xu xv xw xx xy"
135.27/108.01	The bind variable of the following binding Pattern
135.27/108.01	"fm_l@(Branch vxx vxy vxz vyu vyv)"
135.27/108.01	is replaced by the following term
135.27/108.01	"Branch vxx vxy vxz vyu vyv"
135.27/108.01	The bind variable of the following binding Pattern
135.27/108.01	"fm_r@(Branch vyx vyy vyz vzu vzv)"
135.27/108.01	is replaced by the following term
135.27/108.01	"Branch vyx vyy vyz vzu vzv"
135.27/108.01	
135.27/108.01	----------------------------------------
135.27/108.01	
135.27/108.01	(6)
135.27/108.01	Obligation:
135.27/108.01	mainModule Main 
135.27/108.01	module FiniteMap where {
135.27/108.01	import qualified Main;
135.27/108.01	import qualified Maybe;
135.27/108.01	import qualified Prelude;
135.27/108.01	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
135.27/108.01	
135.27/108.01	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
135.27/108.01	}
135.27/108.01	addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
135.27/108.01	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
135.27/108.01	
135.27/108.01	addToFM0 old new = new;
135.27/108.01	
135.27/108.01	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
135.27/108.01	addToFM_C combiner EmptyFM key elt = unitFM key elt;
135.27/108.01	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
135.27/108.01	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
135.27/108.01	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
135.27/108.01	
135.27/108.01	deleteMax :: Ord b => FiniteMap b a  ->  FiniteMap b a;
135.27/108.01	deleteMax (Branch key elt xz fm_l EmptyFM) = fm_l;
135.27/108.01	deleteMax (Branch key elt yu fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
135.27/108.01	
135.27/108.01	deleteMin :: Ord a => FiniteMap a b  ->  FiniteMap a b;
135.27/108.01	deleteMin (Branch key elt wuu EmptyFM fm_r) = fm_r;
135.27/108.01	deleteMin (Branch key elt wuv fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
135.27/108.01	
135.27/108.01	emptyFM :: FiniteMap b a;
135.27/108.01	emptyFM = EmptyFM;
135.27/108.01	
135.27/108.01	findMax :: FiniteMap b a  ->  (b,a);
135.27/108.01	findMax (Branch key elt vuu vuv EmptyFM) = (key,elt);
135.27/108.01	findMax (Branch key elt vuw vux fm_r) = findMax fm_r;
135.27/108.01	
135.27/108.01	findMin :: FiniteMap a b  ->  (a,b);
135.27/108.01	findMin (Branch key elt wuw EmptyFM wux) = (key,elt);
135.27/108.01	findMin (Branch key elt wuy fm_l wuz) = findMin fm_l;
135.27/108.01	
135.27/108.01	glueBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/108.01	glueBal EmptyFM fm2 = fm2;
135.27/108.01	glueBal fm1 EmptyFM = fm1;
135.27/108.01	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
135.27/108.01	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
135.27/108.01	mid_elt1 = mid_elt10 vv2;
135.27/108.01	mid_elt10 (vwz,mid_elt1) = mid_elt1;
135.27/108.01	mid_elt2 = mid_elt20 vv3;
135.27/108.01	mid_elt20 (vwy,mid_elt2) = mid_elt2;
135.27/108.01	mid_key1 = mid_key10 vv2;
135.27/108.01	mid_key10 (mid_key1,vxu) = mid_key1;
135.27/108.01	mid_key2 = mid_key20 vv3;
135.27/108.01	mid_key20 (mid_key2,vxv) = mid_key2;
135.27/108.01	vv2 = findMax fm1;
135.27/108.01	vv3 = findMin fm2;
135.27/108.01	 };
135.27/108.01	
135.27/108.01	glueVBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/108.01	glueVBal EmptyFM fm2 = fm2;
135.27/108.01	glueVBal fm1 EmptyFM = fm1;
135.27/108.01	glueVBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv)  | sIZE_RATIO * size_l < size_r = mkBalBranch vyx vyy (glueVBal (Branch vxx vxy vxz vyu vyv) vzu) vzv
135.27/108.01	 | sIZE_RATIO * size_r < size_l = mkBalBranch vxx vxy vyu (glueVBal vyv (Branch vyx vyy vyz vzu vzv))
135.27/108.01	 | otherwise = glueBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv) where { 
135.27/108.01	size_l = sizeFM (Branch vxx vxy vxz vyu vyv);
135.27/108.01	size_r = sizeFM (Branch vyx vyy vyz vzu vzv);
135.27/108.01	 };
135.27/108.01	
135.27/108.01	minusFM :: Ord b => FiniteMap b c  ->  FiniteMap b a  ->  FiniteMap b c;
135.27/108.01	minusFM EmptyFM fm2 = emptyFM;
135.27/108.01	minusFM fm1 EmptyFM = fm1;
135.27/108.01	minusFM fm1 (Branch split_key elt yx left right) = glueVBal (minusFM lts left) (minusFM gts right) where { 
135.27/108.01	gts = splitGT fm1 split_key;
135.27/108.01	lts = splitLT fm1 split_key;
135.27/108.01	 };
135.27/108.01	
135.27/108.01	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/108.01	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
135.27/108.01	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
135.27/108.01	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
135.27/108.01	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
135.27/108.01	double_L fm_l (Branch key_r elt_r vvy (Branch key_rl elt_rl vvz fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
135.27/108.01	double_R (Branch key_l elt_l vuz fm_ll (Branch key_lr elt_lr vvu fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
135.27/108.01	mkBalBranch0 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
135.27/108.01	 | otherwise = double_L fm_L fm_R;
135.27/108.01	mkBalBranch1 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
135.27/108.01	 | otherwise = double_R fm_L fm_R;
135.27/108.01	single_L fm_l (Branch key_r elt_r vwx fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
135.27/108.01	single_R (Branch key_l elt_l vuy fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
135.27/108.01	size_l = sizeFM fm_L;
135.27/108.01	size_r = sizeFM fm_R;
135.27/108.01	 };
135.27/108.01	
135.27/108.01	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
135.27/108.01	mkBranch which key elt fm_l fm_r = let { 
135.27/108.01	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
135.27/108.01	} in result where { 
135.27/108.01	balance_ok = True;
135.27/108.01	left_ok = left_ok0 fm_l key fm_l;
135.27/108.01	left_ok0 fm_l key EmptyFM = True;
135.27/108.01	left_ok0 fm_l key (Branch left_key yy yz zu zv) = let { 
135.27/108.01	biggest_left_key = fst (findMax fm_l);
135.27/108.01	} in biggest_left_key < key;
135.27/108.01	left_size = sizeFM fm_l;
135.27/108.01	right_ok = right_ok0 fm_r key fm_r;
135.27/108.01	right_ok0 fm_r key EmptyFM = True;
135.27/108.01	right_ok0 fm_r key (Branch right_key zw zx zy zz) = let { 
135.27/108.01	smallest_right_key = fst (findMin fm_r);
135.27/108.01	} in key < smallest_right_key;
135.27/108.01	right_size = sizeFM fm_r;
135.27/108.01	unbox :: Int  ->  Int;
135.27/108.01	unbox x = x;
135.27/108.01	 };
135.27/108.01	
135.27/108.01	mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
135.27/108.01	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
135.27/108.01	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
135.27/108.01	mkVBalBranch key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy)  | sIZE_RATIO * size_l < size_r = mkBalBranch xu xv (mkVBalBranch key elt (Branch wu wv ww wx wy) xx) xy
135.27/108.01	 | sIZE_RATIO * size_r < size_l = mkBalBranch wu wv wx (mkVBalBranch key elt wy (Branch xu xv xw xx xy))
135.27/108.01	 | otherwise = mkBranch 13 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy) where { 
135.27/108.01	size_l = sizeFM (Branch wu wv ww wx wy);
135.27/108.01	size_r = sizeFM (Branch xu xv xw xx xy);
135.27/108.01	 };
135.27/108.01	
135.27/108.01	sIZE_RATIO :: Int;
135.27/108.01	sIZE_RATIO = 5;
135.27/108.01	
135.27/108.01	sizeFM :: FiniteMap a b  ->  Int;
135.27/108.01	sizeFM EmptyFM = 0;
135.27/108.01	sizeFM (Branch vzw vzx size vzy vzz) = size;
135.27/108.01	
135.27/108.01	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
135.27/108.01	splitGT EmptyFM split_key = emptyFM;
135.27/108.01	splitGT (Branch key elt yv fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
135.27/108.01	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
135.27/108.01	 | otherwise = fm_r;
135.27/108.01	
135.27/108.01	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
135.27/108.01	splitLT EmptyFM split_key = emptyFM;
135.27/108.01	splitLT (Branch key elt yw fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
135.27/108.01	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
135.27/108.01	 | otherwise = fm_l;
135.27/108.01	
135.27/108.01	unitFM :: b  ->  a  ->  FiniteMap b a;
135.27/108.01	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
135.27/108.01	
135.27/108.01	}
135.27/108.01	module Maybe where {
135.27/108.01	import qualified FiniteMap;
135.27/108.01	import qualified Main;
135.27/108.01	import qualified Prelude;
135.27/108.01	}
135.27/108.01	module Main where {
135.27/108.01	import qualified FiniteMap;
135.27/108.01	import qualified Maybe;
135.27/108.01	import qualified Prelude;
135.27/108.01	}
135.27/108.01	
135.27/108.01	----------------------------------------
135.27/108.01	
135.27/108.01	(7) COR (EQUIVALENT)
135.27/108.01	Cond Reductions:
135.27/108.01	The following Function with conditions
135.27/108.01	"undefined |Falseundefined;
135.27/108.01	"
135.27/108.01	is transformed to
135.27/108.01	"undefined  = undefined1;
135.27/108.01	"
135.27/108.01	"undefined0 True = undefined;
135.27/108.01	"
135.27/108.01	"undefined1  = undefined0 False;
135.27/108.01	"
135.27/108.01	The following Function with conditions
135.27/108.01	"addToFM_C combiner EmptyFM key elt = unitFM key elt;
135.27/108.01	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt|new_key < keymkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r|new_key > keymkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)|otherwiseBranch new_key (combiner elt new_elt) size fm_l fm_r;
135.27/108.01	"
135.27/108.01	is transformed to
135.27/108.01	"addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
135.27/108.01	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt;
135.27/108.01	"
135.27/108.01	"addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r;
135.27/108.01	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt (new_key > key);
135.27/108.01	"
135.27/108.01	"addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt);
135.27/108.01	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt otherwise;
135.27/108.01	"
135.27/108.01	"addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt True = Branch new_key (combiner elt new_elt) size fm_l fm_r;
135.27/108.01	"
135.27/108.01	"addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt (new_key < key);
135.27/108.01	"
135.27/108.01	"addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
135.27/108.01	addToFM_C4 wvw wvx wvy wvz = addToFM_C3 wvw wvx wvy wvz;
135.27/108.01	"
135.27/108.01	The following Function with conditions
135.27/108.01	"mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
135.27/108.01	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
135.27/108.01	mkVBalBranch key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy)|sIZE_RATIO * size_l < size_rmkBalBranch xu xv (mkVBalBranch key elt (Branch wu wv ww wx wy) xx) xy|sIZE_RATIO * size_r < size_lmkBalBranch wu wv wx (mkVBalBranch key elt wy (Branch xu xv xw xx xy))|otherwisemkBranch 13 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy) where {
135.27/108.01	size_l  = sizeFM (Branch wu wv ww wx wy);
135.27/108.01	;
135.27/108.01	size_r  = sizeFM (Branch xu xv xw xx xy);
135.27/108.01	} 
135.27/108.01	;
135.27/108.01	"
135.27/108.01	is transformed to
135.27/108.01	"mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
135.27/108.01	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
135.27/108.01	mkVBalBranch key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy) = mkVBalBranch3 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy);
135.27/108.01	"
135.27/108.01	"mkVBalBranch3 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy) = mkVBalBranch2 key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * size_l < size_r) where {
135.27/108.01	mkVBalBranch0 key elt wu wv ww wx wy xu xv xw xx xy True = mkBranch 13 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy);
135.27/108.01	;
135.27/108.01	mkVBalBranch1 key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch wu wv wx (mkVBalBranch key elt wy (Branch xu xv xw xx xy));
135.27/108.01	mkVBalBranch1 key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch0 key elt wu wv ww wx wy xu xv xw xx xy otherwise;
135.27/108.01	;
135.27/108.01	mkVBalBranch2 key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch xu xv (mkVBalBranch key elt (Branch wu wv ww wx wy) xx) xy;
136.23/108.24	mkVBalBranch2 key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch1 key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * size_r < size_l);
136.23/108.24	;
136.23/108.24	size_l  = sizeFM (Branch wu wv ww wx wy);
136.23/108.24	;
136.23/108.24	size_r  = sizeFM (Branch xu xv xw xx xy);
136.23/108.24	} 
136.23/108.24	;
136.23/108.24	"
136.23/108.24	"mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
136.23/108.24	mkVBalBranch4 wwx wwy wwz wxu = mkVBalBranch3 wwx wwy wwz wxu;
136.23/108.24	"
136.23/108.24	"mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
136.23/108.24	mkVBalBranch5 wxw wxx wxy wxz = mkVBalBranch4 wxw wxx wxy wxz;
136.23/108.24	"
136.23/108.24	The following Function with conditions
136.23/108.24	"splitGT EmptyFM split_key = emptyFM;
136.23/108.24	splitGT (Branch key elt yv fm_l fm_r) split_key|split_key > keysplitGT fm_r split_key|split_key < keymkVBalBranch key elt (splitGT fm_l split_key) fm_r|otherwisefm_r;
136.23/108.24	"
136.23/108.24	is transformed to
136.23/108.24	"splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
136.23/108.24	splitGT (Branch key elt yv fm_l fm_r) split_key = splitGT3 (Branch key elt yv fm_l fm_r) split_key;
136.23/108.24	"
136.23/108.24	"splitGT1 key elt yv fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
136.23/108.24	splitGT1 key elt yv fm_l fm_r split_key False = splitGT0 key elt yv fm_l fm_r split_key otherwise;
136.23/108.24	"
136.23/108.24	"splitGT0 key elt yv fm_l fm_r split_key True = fm_r;
136.23/108.24	"
136.23/108.24	"splitGT2 key elt yv fm_l fm_r split_key True = splitGT fm_r split_key;
136.23/108.24	splitGT2 key elt yv fm_l fm_r split_key False = splitGT1 key elt yv fm_l fm_r split_key (split_key < key);
136.23/108.24	"
136.23/108.24	"splitGT3 (Branch key elt yv fm_l fm_r) split_key = splitGT2 key elt yv fm_l fm_r split_key (split_key > key);
136.23/108.24	"
136.23/108.24	"splitGT4 EmptyFM split_key = emptyFM;
136.23/108.24	splitGT4 wyw wyx = splitGT3 wyw wyx;
136.23/108.24	"
136.23/108.24	The following Function with conditions
136.23/108.24	"splitLT EmptyFM split_key = emptyFM;
136.23/108.24	splitLT (Branch key elt yw fm_l fm_r) split_key|split_key < keysplitLT fm_l split_key|split_key > keymkVBalBranch key elt fm_l (splitLT fm_r split_key)|otherwisefm_l;
136.23/108.24	"
136.23/108.24	is transformed to
136.23/108.24	"splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
136.23/108.24	splitLT (Branch key elt yw fm_l fm_r) split_key = splitLT3 (Branch key elt yw fm_l fm_r) split_key;
136.23/108.24	"
136.23/108.24	"splitLT2 key elt yw fm_l fm_r split_key True = splitLT fm_l split_key;
136.23/108.24	splitLT2 key elt yw fm_l fm_r split_key False = splitLT1 key elt yw fm_l fm_r split_key (split_key > key);
136.23/108.24	"
136.23/108.24	"splitLT1 key elt yw fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
136.23/108.24	splitLT1 key elt yw fm_l fm_r split_key False = splitLT0 key elt yw fm_l fm_r split_key otherwise;
136.23/108.24	"
136.23/108.24	"splitLT0 key elt yw fm_l fm_r split_key True = fm_l;
136.23/108.24	"
136.23/108.24	"splitLT3 (Branch key elt yw fm_l fm_r) split_key = splitLT2 key elt yw fm_l fm_r split_key (split_key < key);
136.23/108.24	"
136.23/108.24	"splitLT4 EmptyFM split_key = emptyFM;
136.23/108.24	splitLT4 wzu wzv = splitLT3 wzu wzv;
136.23/108.24	"
136.23/108.24	The following Function with conditions
136.23/108.24	"mkBalBranch1 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
136.23/108.24	"
136.23/108.24	is transformed to
136.23/108.24	"mkBalBranch1 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr);
136.23/108.24	"
136.23/108.24	"mkBalBranch10 fm_L fm_R vvv vvw vvx fm_ll fm_lr True = double_R fm_L fm_R;
136.23/108.24	"
136.23/108.24	"mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr True = single_R fm_L fm_R;
136.23/108.24	mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vvv vvw vvx fm_ll fm_lr otherwise;
136.23/108.24	"
136.23/108.24	"mkBalBranch12 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
136.23/108.24	"
136.23/108.24	The following Function with conditions
136.23/108.24	"mkBalBranch0 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
136.23/108.24	"
136.23/108.24	is transformed to
136.23/108.24	"mkBalBranch0 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr);
136.23/108.24	"
136.23/108.24	"mkBalBranch00 fm_L fm_R vwu vwv vww fm_rl fm_rr True = double_L fm_L fm_R;
136.23/108.24	"
136.23/108.24	"mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr True = single_L fm_L fm_R;
136.23/108.24	mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vwu vwv vww fm_rl fm_rr otherwise;
136.23/108.24	"
136.23/108.24	"mkBalBranch02 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
136.23/108.24	"
136.23/108.24	The following Function with conditions
136.23/108.24	"mkBalBranch key elt fm_L fm_R|size_l + size_r < 2mkBranch 1 key elt fm_L fm_R|size_r > sIZE_RATIO * size_lmkBalBranch0 fm_L fm_R fm_R|size_l > sIZE_RATIO * size_rmkBalBranch1 fm_L fm_R fm_L|otherwisemkBranch 2 key elt fm_L fm_R where {
136.23/108.24	double_L fm_l (Branch key_r elt_r vvy (Branch key_rl elt_rl vvz fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
136.23/108.24	;
136.23/108.24	double_R (Branch key_l elt_l vuz fm_ll (Branch key_lr elt_lr vvu fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
136.23/108.24	;
136.23/108.24	mkBalBranch0 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
136.23/108.24	;
136.23/108.24	mkBalBranch1 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
136.23/108.24	;
136.23/108.24	single_L fm_l (Branch key_r elt_r vwx fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
136.23/108.24	;
136.23/108.24	single_R (Branch key_l elt_l vuy fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
136.23/108.24	;
136.23/108.24	size_l  = sizeFM fm_L;
136.23/108.24	;
136.23/108.24	size_r  = sizeFM fm_R;
136.23/108.24	} 
136.23/108.24	;
136.23/108.24	"
136.23/108.24	is transformed to
136.23/108.24	"mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
136.23/108.24	"
136.23/108.24	"mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
136.23/108.24	double_L fm_l (Branch key_r elt_r vvy (Branch key_rl elt_rl vvz fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
136.23/108.24	;
136.23/108.24	double_R (Branch key_l elt_l vuz fm_ll (Branch key_lr elt_lr vvu fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
136.23/108.24	;
136.23/108.24	mkBalBranch0 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr);
136.23/108.24	;
136.23/108.24	mkBalBranch00 fm_L fm_R vwu vwv vww fm_rl fm_rr True = double_L fm_L fm_R;
136.23/108.24	;
136.23/108.24	mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr True = single_L fm_L fm_R;
136.23/108.24	mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vwu vwv vww fm_rl fm_rr otherwise;
136.23/108.24	;
136.23/108.24	mkBalBranch02 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
136.23/108.24	;
136.23/108.24	mkBalBranch1 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr);
136.23/108.24	;
136.23/108.24	mkBalBranch10 fm_L fm_R vvv vvw vvx fm_ll fm_lr True = double_R fm_L fm_R;
136.23/108.24	;
136.23/108.24	mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr True = single_R fm_L fm_R;
136.23/108.24	mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vvv vvw vvx fm_ll fm_lr otherwise;
136.23/108.24	;
136.23/108.24	mkBalBranch12 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
136.23/108.24	;
136.23/108.24	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
136.23/108.24	;
136.23/108.24	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
136.23/108.24	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
136.23/108.24	;
136.23/108.24	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
136.23/108.24	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
136.23/108.24	;
136.23/108.24	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
136.23/108.24	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
136.23/108.24	;
136.23/108.24	single_L fm_l (Branch key_r elt_r vwx fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
136.23/108.24	;
136.23/108.24	single_R (Branch key_l elt_l vuy fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
136.23/108.24	;
136.23/108.24	size_l  = sizeFM fm_L;
136.23/108.24	;
136.23/108.24	size_r  = sizeFM fm_R;
136.23/108.24	} 
136.23/108.24	;
136.23/108.24	"
136.23/108.24	The following Function with conditions
136.23/108.24	"glueBal EmptyFM fm2 = fm2;
136.23/108.24	glueBal fm1 EmptyFM = fm1;
136.23/108.24	glueBal fm1 fm2|sizeFM fm2 > sizeFM fm1mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)|otherwisemkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where {
136.23/108.24	mid_elt1  = mid_elt10 vv2;
136.23/108.24	;
136.23/108.24	mid_elt10 (vwz,mid_elt1) = mid_elt1;
136.23/108.24	;
136.23/108.24	mid_elt2  = mid_elt20 vv3;
136.23/108.24	;
136.23/108.24	mid_elt20 (vwy,mid_elt2) = mid_elt2;
136.23/108.24	;
136.23/108.24	mid_key1  = mid_key10 vv2;
136.23/108.24	;
136.23/108.24	mid_key10 (mid_key1,vxu) = mid_key1;
136.23/108.24	;
136.23/108.24	mid_key2  = mid_key20 vv3;
136.23/108.24	;
136.23/108.24	mid_key20 (mid_key2,vxv) = mid_key2;
136.23/108.24	;
136.23/108.24	vv2  = findMax fm1;
136.23/108.24	;
136.23/108.24	vv3  = findMin fm2;
136.23/108.24	} 
136.23/108.24	;
136.23/108.24	"
136.23/108.24	is transformed to
136.23/108.24	"glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
136.23/108.24	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
136.23/108.24	glueBal fm1 fm2 = glueBal2 fm1 fm2;
136.23/108.24	"
136.23/108.24	"glueBal2 fm1 fm2 = glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where {
136.23/108.24	glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2;
136.23/108.24	;
136.23/108.24	glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2);
136.23/108.24	glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise;
136.23/108.24	;
136.23/108.24	mid_elt1  = mid_elt10 vv2;
136.23/108.24	;
136.23/108.24	mid_elt10 (vwz,mid_elt1) = mid_elt1;
136.23/108.24	;
136.23/108.24	mid_elt2  = mid_elt20 vv3;
136.23/108.24	;
136.23/108.24	mid_elt20 (vwy,mid_elt2) = mid_elt2;
136.23/108.24	;
136.23/108.24	mid_key1  = mid_key10 vv2;
136.23/108.24	;
136.23/108.24	mid_key10 (mid_key1,vxu) = mid_key1;
136.23/108.24	;
136.23/108.24	mid_key2  = mid_key20 vv3;
136.23/108.24	;
136.23/108.24	mid_key20 (mid_key2,vxv) = mid_key2;
136.23/108.24	;
136.23/108.24	vv2  = findMax fm1;
136.23/108.24	;
136.23/108.24	vv3  = findMin fm2;
136.23/108.24	} 
136.23/108.24	;
136.23/108.24	"
136.23/108.24	"glueBal3 fm1 EmptyFM = fm1;
136.23/108.24	glueBal3 wzz xuu = glueBal2 wzz xuu;
136.23/108.24	"
136.23/108.24	"glueBal4 EmptyFM fm2 = fm2;
136.23/108.24	glueBal4 xuw xux = glueBal3 xuw xux;
136.23/108.24	"
136.23/108.24	The following Function with conditions
136.23/108.24	"glueVBal EmptyFM fm2 = fm2;
136.23/108.24	glueVBal fm1 EmptyFM = fm1;
136.23/108.24	glueVBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv)|sIZE_RATIO * size_l < size_rmkBalBranch vyx vyy (glueVBal (Branch vxx vxy vxz vyu vyv) vzu) vzv|sIZE_RATIO * size_r < size_lmkBalBranch vxx vxy vyu (glueVBal vyv (Branch vyx vyy vyz vzu vzv))|otherwiseglueBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv) where {
136.23/108.24	size_l  = sizeFM (Branch vxx vxy vxz vyu vyv);
136.23/108.24	;
136.23/108.24	size_r  = sizeFM (Branch vyx vyy vyz vzu vzv);
136.23/108.24	} 
136.23/108.24	;
136.23/108.24	"
136.23/108.24	is transformed to
136.23/108.24	"glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2;
136.23/108.24	glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM;
136.23/108.24	glueVBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv) = glueVBal3 (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv);
136.23/108.24	"
136.23/108.24	"glueVBal3 (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv) = glueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * size_l < size_r) where {
136.23/108.24	glueVBal0 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = glueBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv);
136.23/108.24	;
136.23/108.24	glueVBal1 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vxx vxy vyu (glueVBal vyv (Branch vyx vyy vyz vzu vzv));
136.23/108.24	glueVBal1 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal0 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv otherwise;
136.23/108.24	;
136.23/108.24	glueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vyx vyy (glueVBal (Branch vxx vxy vxz vyu vyv) vzu) vzv;
136.23/108.24	glueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal1 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * size_r < size_l);
136.23/108.24	;
136.23/108.24	size_l  = sizeFM (Branch vxx vxy vxz vyu vyv);
136.23/108.24	;
136.23/108.24	size_r  = sizeFM (Branch vyx vyy vyz vzu vzv);
136.23/108.24	} 
136.23/108.24	;
136.23/108.24	"
136.23/108.24	"glueVBal4 fm1 EmptyFM = fm1;
136.23/108.24	glueVBal4 xvv xvw = glueVBal3 xvv xvw;
136.23/108.24	"
136.23/108.24	"glueVBal5 EmptyFM fm2 = fm2;
136.23/108.24	glueVBal5 xvy xvz = glueVBal4 xvy xvz;
136.23/108.24	"
136.23/108.24	
136.23/108.24	----------------------------------------
136.23/108.24	
136.23/108.24	(8)
136.23/108.24	Obligation:
136.23/108.24	mainModule Main 
136.23/108.24	module FiniteMap where {
136.23/108.24	import qualified Main;
136.23/108.24	import qualified Maybe;
136.23/108.24	import qualified Prelude;
136.23/108.24	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
136.23/108.24	
136.23/108.24	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
136.23/108.24	}
136.23/108.24	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
136.23/108.24	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
136.23/108.24	
136.23/108.24	addToFM0 old new = new;
136.23/108.24	
136.23/108.24	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
136.23/108.24	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
136.23/108.24	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt;
136.23/108.24	
136.23/108.24	addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt True = Branch new_key (combiner elt new_elt) size fm_l fm_r;
136.23/108.24	
136.23/108.24	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt);
136.23/108.24	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt otherwise;
136.23/108.24	
136.23/108.24	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r;
136.23/108.24	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt (new_key > key);
136.23/108.24	
136.23/108.24	addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt (new_key < key);
136.23/108.24	
136.23/108.24	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
136.23/108.24	addToFM_C4 wvw wvx wvy wvz = addToFM_C3 wvw wvx wvy wvz;
136.23/108.24	
136.23/108.24	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
136.23/108.24	deleteMax (Branch key elt xz fm_l EmptyFM) = fm_l;
136.23/108.24	deleteMax (Branch key elt yu fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
136.23/108.24	
136.23/108.24	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
136.23/108.24	deleteMin (Branch key elt wuu EmptyFM fm_r) = fm_r;
136.23/108.24	deleteMin (Branch key elt wuv fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
136.23/108.24	
136.23/108.24	emptyFM :: FiniteMap b a;
136.23/108.24	emptyFM = EmptyFM;
136.23/108.24	
136.23/108.24	findMax :: FiniteMap b a  ->  (b,a);
136.23/108.24	findMax (Branch key elt vuu vuv EmptyFM) = (key,elt);
136.23/108.24	findMax (Branch key elt vuw vux fm_r) = findMax fm_r;
136.23/108.24	
136.23/108.24	findMin :: FiniteMap a b  ->  (a,b);
136.23/108.24	findMin (Branch key elt wuw EmptyFM wux) = (key,elt);
136.23/108.24	findMin (Branch key elt wuy fm_l wuz) = findMin fm_l;
136.23/108.24	
136.23/108.24	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
136.23/108.24	glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
136.23/108.24	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
136.23/108.24	glueBal fm1 fm2 = glueBal2 fm1 fm2;
136.23/108.24	
136.23/108.24	glueBal2 fm1 fm2 = glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where { 
136.23/108.24	glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2;
136.23/108.24	glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2);
136.23/108.24	glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise;
136.23/108.24	mid_elt1 = mid_elt10 vv2;
136.23/108.24	mid_elt10 (vwz,mid_elt1) = mid_elt1;
136.23/108.24	mid_elt2 = mid_elt20 vv3;
136.23/108.24	mid_elt20 (vwy,mid_elt2) = mid_elt2;
136.23/108.24	mid_key1 = mid_key10 vv2;
136.23/108.24	mid_key10 (mid_key1,vxu) = mid_key1;
136.23/108.24	mid_key2 = mid_key20 vv3;
136.23/108.24	mid_key20 (mid_key2,vxv) = mid_key2;
136.23/108.24	vv2 = findMax fm1;
136.23/108.24	vv3 = findMin fm2;
136.23/108.24	 };
136.23/108.24	
136.23/108.24	glueBal3 fm1 EmptyFM = fm1;
136.23/108.24	glueBal3 wzz xuu = glueBal2 wzz xuu;
136.23/108.24	
136.23/108.24	glueBal4 EmptyFM fm2 = fm2;
136.23/108.24	glueBal4 xuw xux = glueBal3 xuw xux;
136.23/108.24	
136.23/108.24	glueVBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
136.23/108.24	glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2;
136.23/108.24	glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM;
136.23/108.24	glueVBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv) = glueVBal3 (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv);
136.23/108.24	
136.23/108.24	glueVBal3 (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv) = glueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * size_l < size_r) where { 
136.23/108.24	glueVBal0 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = glueBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv);
136.23/108.24	glueVBal1 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vxx vxy vyu (glueVBal vyv (Branch vyx vyy vyz vzu vzv));
136.23/108.24	glueVBal1 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal0 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv otherwise;
136.23/108.24	glueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vyx vyy (glueVBal (Branch vxx vxy vxz vyu vyv) vzu) vzv;
136.23/108.24	glueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal1 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * size_r < size_l);
136.23/108.24	size_l = sizeFM (Branch vxx vxy vxz vyu vyv);
136.23/108.24	size_r = sizeFM (Branch vyx vyy vyz vzu vzv);
136.23/108.24	 };
136.23/108.24	
136.23/108.24	glueVBal4 fm1 EmptyFM = fm1;
136.23/108.24	glueVBal4 xvv xvw = glueVBal3 xvv xvw;
136.23/108.24	
136.23/108.24	glueVBal5 EmptyFM fm2 = fm2;
136.23/108.24	glueVBal5 xvy xvz = glueVBal4 xvy xvz;
136.23/108.24	
136.23/108.24	minusFM :: Ord c => FiniteMap c b  ->  FiniteMap c a  ->  FiniteMap c b;
136.23/108.24	minusFM EmptyFM fm2 = emptyFM;
136.23/108.24	minusFM fm1 EmptyFM = fm1;
136.23/108.24	minusFM fm1 (Branch split_key elt yx left right) = glueVBal (minusFM lts left) (minusFM gts right) where { 
136.23/108.24	gts = splitGT fm1 split_key;
136.23/108.24	lts = splitLT fm1 split_key;
136.23/108.24	 };
136.23/108.24	
136.23/108.24	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
136.23/108.24	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
136.23/108.24	
136.23/108.24	mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 
136.23/108.24	double_L fm_l (Branch key_r elt_r vvy (Branch key_rl elt_rl vvz fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
136.23/108.24	double_R (Branch key_l elt_l vuz fm_ll (Branch key_lr elt_lr vvu fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
136.23/108.24	mkBalBranch0 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr);
136.23/108.24	mkBalBranch00 fm_L fm_R vwu vwv vww fm_rl fm_rr True = double_L fm_L fm_R;
136.23/108.24	mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr True = single_L fm_L fm_R;
136.23/108.24	mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vwu vwv vww fm_rl fm_rr otherwise;
136.23/108.24	mkBalBranch02 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
136.23/108.24	mkBalBranch1 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr);
136.23/108.24	mkBalBranch10 fm_L fm_R vvv vvw vvx fm_ll fm_lr True = double_R fm_L fm_R;
136.23/108.24	mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr True = single_R fm_L fm_R;
136.23/108.24	mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vvv vvw vvx fm_ll fm_lr otherwise;
136.23/108.24	mkBalBranch12 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
136.23/108.24	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
136.23/108.24	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
136.23/108.24	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
136.23/108.24	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
136.23/108.24	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
136.23/108.24	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
136.23/108.24	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
136.23/108.24	single_L fm_l (Branch key_r elt_r vwx fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
136.23/108.24	single_R (Branch key_l elt_l vuy fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
136.23/108.24	size_l = sizeFM fm_L;
136.23/108.24	size_r = sizeFM fm_R;
136.23/108.24	 };
136.23/108.24	
136.23/108.24	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
136.23/108.24	mkBranch which key elt fm_l fm_r = let { 
136.23/108.24	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
136.23/108.24	} in result where { 
136.23/108.24	balance_ok = True;
136.23/108.24	left_ok = left_ok0 fm_l key fm_l;
136.23/108.24	left_ok0 fm_l key EmptyFM = True;
136.23/108.24	left_ok0 fm_l key (Branch left_key yy yz zu zv) = let { 
136.23/108.24	biggest_left_key = fst (findMax fm_l);
136.23/108.24	} in biggest_left_key < key;
136.23/108.24	left_size = sizeFM fm_l;
136.23/108.24	right_ok = right_ok0 fm_r key fm_r;
136.23/108.24	right_ok0 fm_r key EmptyFM = True;
136.23/108.24	right_ok0 fm_r key (Branch right_key zw zx zy zz) = let { 
136.23/108.24	smallest_right_key = fst (findMin fm_r);
136.23/108.24	} in key < smallest_right_key;
136.23/108.24	right_size = sizeFM fm_r;
136.23/108.24	unbox :: Int  ->  Int;
136.23/108.24	unbox x = x;
136.23/108.24	 };
136.23/108.24	
136.23/108.24	mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
136.23/108.24	mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
136.23/108.24	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
136.23/108.24	mkVBalBranch key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy) = mkVBalBranch3 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy);
136.23/108.24	
136.23/108.24	mkVBalBranch3 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy) = mkVBalBranch2 key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * size_l < size_r) where { 
136.23/108.24	mkVBalBranch0 key elt wu wv ww wx wy xu xv xw xx xy True = mkBranch 13 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy);
136.23/108.24	mkVBalBranch1 key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch wu wv wx (mkVBalBranch key elt wy (Branch xu xv xw xx xy));
136.23/108.24	mkVBalBranch1 key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch0 key elt wu wv ww wx wy xu xv xw xx xy otherwise;
136.23/108.24	mkVBalBranch2 key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch xu xv (mkVBalBranch key elt (Branch wu wv ww wx wy) xx) xy;
136.23/108.24	mkVBalBranch2 key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch1 key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * size_r < size_l);
136.23/108.24	size_l = sizeFM (Branch wu wv ww wx wy);
136.23/108.24	size_r = sizeFM (Branch xu xv xw xx xy);
136.23/108.24	 };
136.23/108.24	
136.23/108.24	mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
136.23/108.24	mkVBalBranch4 wwx wwy wwz wxu = mkVBalBranch3 wwx wwy wwz wxu;
136.23/108.24	
136.23/108.24	mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
136.23/108.24	mkVBalBranch5 wxw wxx wxy wxz = mkVBalBranch4 wxw wxx wxy wxz;
136.23/108.24	
136.23/108.24	sIZE_RATIO :: Int;
136.23/108.24	sIZE_RATIO = 5;
136.23/108.24	
136.23/108.24	sizeFM :: FiniteMap b a  ->  Int;
136.23/108.24	sizeFM EmptyFM = 0;
136.23/108.24	sizeFM (Branch vzw vzx size vzy vzz) = size;
136.23/108.24	
136.23/108.24	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
136.23/108.24	splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
136.23/108.24	splitGT (Branch key elt yv fm_l fm_r) split_key = splitGT3 (Branch key elt yv fm_l fm_r) split_key;
136.23/108.24	
136.23/108.24	splitGT0 key elt yv fm_l fm_r split_key True = fm_r;
136.23/108.24	
136.23/108.24	splitGT1 key elt yv fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
136.23/108.24	splitGT1 key elt yv fm_l fm_r split_key False = splitGT0 key elt yv fm_l fm_r split_key otherwise;
136.23/108.24	
136.23/108.24	splitGT2 key elt yv fm_l fm_r split_key True = splitGT fm_r split_key;
136.23/108.24	splitGT2 key elt yv fm_l fm_r split_key False = splitGT1 key elt yv fm_l fm_r split_key (split_key < key);
136.23/108.24	
136.23/108.24	splitGT3 (Branch key elt yv fm_l fm_r) split_key = splitGT2 key elt yv fm_l fm_r split_key (split_key > key);
136.23/108.24	
136.23/108.24	splitGT4 EmptyFM split_key = emptyFM;
136.23/108.24	splitGT4 wyw wyx = splitGT3 wyw wyx;
136.23/108.24	
136.23/108.24	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
136.23/108.24	splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
136.23/108.24	splitLT (Branch key elt yw fm_l fm_r) split_key = splitLT3 (Branch key elt yw fm_l fm_r) split_key;
136.23/108.24	
136.23/108.24	splitLT0 key elt yw fm_l fm_r split_key True = fm_l;
136.23/108.24	
136.23/108.24	splitLT1 key elt yw fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
136.23/108.24	splitLT1 key elt yw fm_l fm_r split_key False = splitLT0 key elt yw fm_l fm_r split_key otherwise;
136.23/108.24	
136.23/108.24	splitLT2 key elt yw fm_l fm_r split_key True = splitLT fm_l split_key;
136.23/108.24	splitLT2 key elt yw fm_l fm_r split_key False = splitLT1 key elt yw fm_l fm_r split_key (split_key > key);
136.23/108.24	
136.23/108.24	splitLT3 (Branch key elt yw fm_l fm_r) split_key = splitLT2 key elt yw fm_l fm_r split_key (split_key < key);
136.23/108.24	
136.23/108.24	splitLT4 EmptyFM split_key = emptyFM;
136.23/108.24	splitLT4 wzu wzv = splitLT3 wzu wzv;
136.23/108.24	
136.23/108.24	unitFM :: a  ->  b  ->  FiniteMap a b;
136.23/108.24	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
136.23/108.24	
136.23/108.24	}
136.23/108.24	module Maybe where {
136.23/108.24	import qualified FiniteMap;
136.23/108.24	import qualified Main;
136.23/108.24	import qualified Prelude;
136.23/108.24	}
136.23/108.24	module Main where {
136.23/108.24	import qualified FiniteMap;
136.23/108.24	import qualified Maybe;
136.23/108.24	import qualified Prelude;
136.23/108.24	}
136.23/108.24	
136.23/108.24	----------------------------------------
136.23/108.24	
136.23/108.24	(9) LetRed (EQUIVALENT)
136.23/108.24	Let/Where Reductions:
136.23/108.24	The bindings of the following Let/Where expression
136.23/108.24	"mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
136.23/108.24	double_L fm_l (Branch key_r elt_r vvy (Branch key_rl elt_rl vvz fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
136.23/108.24	;
136.23/108.24	double_R (Branch key_l elt_l vuz fm_ll (Branch key_lr elt_lr vvu fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
136.23/108.24	;
136.23/108.24	mkBalBranch0 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr);
136.23/108.24	;
136.23/108.24	mkBalBranch00 fm_L fm_R vwu vwv vww fm_rl fm_rr True = double_L fm_L fm_R;
136.23/108.24	;
136.23/108.24	mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr True = single_L fm_L fm_R;
136.23/108.24	mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vwu vwv vww fm_rl fm_rr otherwise;
136.23/108.24	;
136.23/108.24	mkBalBranch02 fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vwu vwv vww fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
136.23/108.24	;
136.23/108.24	mkBalBranch1 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr);
136.23/108.24	;
136.23/108.24	mkBalBranch10 fm_L fm_R vvv vvw vvx fm_ll fm_lr True = double_R fm_L fm_R;
136.23/108.24	;
136.23/108.24	mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr True = single_R fm_L fm_R;
136.23/108.24	mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vvv vvw vvx fm_ll fm_lr otherwise;
136.23/108.24	;
136.23/108.24	mkBalBranch12 fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vvv vvw vvx fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
136.23/108.24	;
136.23/108.24	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
136.49/108.27	;
136.49/108.27	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
136.49/108.27	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
136.49/108.27	;
136.49/108.27	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
136.49/108.27	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
136.49/108.27	;
136.49/108.27	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
136.49/108.27	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
136.49/108.27	;
136.49/108.27	single_L fm_l (Branch key_r elt_r vwx fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
136.49/108.27	;
136.49/108.27	single_R (Branch key_l elt_l vuy fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
136.49/108.27	;
136.49/108.27	size_l  = sizeFM fm_L;
136.49/108.27	;
136.49/108.27	size_r  = sizeFM fm_R;
136.49/108.27	} 
136.49/108.27	"
136.49/108.27	are unpacked to the following functions on top level
136.49/108.27	"mkBalBranch6Double_R xwu xwv xww xwx (Branch key_l elt_l vuz fm_ll (Branch key_lr elt_lr vvu fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 xwu xwv fm_lrr fm_r);
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch01 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr True = mkBalBranch6Single_L xwu xwv xww xwx fm_L fm_R;
136.49/108.27	mkBalBranch6MkBalBranch01 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr False = mkBalBranch6MkBalBranch00 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr otherwise;
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch00 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr True = mkBalBranch6Double_L xwu xwv xww xwx fm_L fm_R;
136.49/108.27	"
136.49/108.27	"mkBalBranch6Single_L xwu xwv xww xwx fm_l (Branch key_r elt_r vwx fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 xwu xwv fm_l fm_rl) fm_rr;
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch5 xwu xwv xww xwx key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
136.49/108.27	mkBalBranch6MkBalBranch5 xwu xwv xww xwx key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 xwu xwv xww xwx key elt fm_L fm_R (mkBalBranch6Size_r xwu xwv xww xwx > sIZE_RATIO * mkBalBranch6Size_l xwu xwv xww xwx);
136.49/108.27	"
136.49/108.27	"mkBalBranch6Size_r xwu xwv xww xwx = sizeFM xww;
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch1 xwu xwv xww xwx fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch6MkBalBranch12 xwu xwv xww xwx fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr);
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch12 xwu xwv xww xwx fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch6MkBalBranch11 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch2 xwu xwv xww xwx key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
136.49/108.27	"
136.49/108.27	"mkBalBranch6Single_R xwu xwv xww xwx (Branch key_l elt_l vuy fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 xwu xwv fm_lr fm_r);
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch11 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr True = mkBalBranch6Single_R xwu xwv xww xwx fm_L fm_R;
136.49/108.27	mkBalBranch6MkBalBranch11 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr False = mkBalBranch6MkBalBranch10 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr otherwise;
136.49/108.27	"
136.49/108.27	"mkBalBranch6Size_l xwu xwv xww xwx = sizeFM xwx;
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch02 xwu xwv xww xwx fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch6MkBalBranch01 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch4 xwu xwv xww xwx key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 xwu xwv xww xwx fm_L fm_R fm_R;
136.49/108.27	mkBalBranch6MkBalBranch4 xwu xwv xww xwx key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 xwu xwv xww xwx key elt fm_L fm_R (mkBalBranch6Size_l xwu xwv xww xwx > sIZE_RATIO * mkBalBranch6Size_r xwu xwv xww xwx);
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch10 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr True = mkBalBranch6Double_R xwu xwv xww xwx fm_L fm_R;
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch0 xwu xwv xww xwx fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch6MkBalBranch02 xwu xwv xww xwx fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr);
136.49/108.27	"
136.49/108.27	"mkBalBranch6MkBalBranch3 xwu xwv xww xwx key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 xwu xwv xww xwx fm_L fm_R fm_L;
136.49/108.27	mkBalBranch6MkBalBranch3 xwu xwv xww xwx key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 xwu xwv xww xwx key elt fm_L fm_R otherwise;
136.49/108.27	"
136.49/108.27	"mkBalBranch6Double_L xwu xwv xww xwx fm_l (Branch key_r elt_r vvy (Branch key_rl elt_rl vvz fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 xwu xwv fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
136.49/108.27	"
136.49/108.27	The bindings of the following Let/Where expression
136.49/108.27	"glueVBal (minusFM lts left) (minusFM gts right) where {
136.49/108.27	gts  = splitGT fm1 split_key;
136.49/108.27	;
136.49/108.27	lts  = splitLT fm1 split_key;
136.49/108.27	} 
136.49/108.27	"
136.49/108.27	are unpacked to the following functions on top level
136.49/108.27	"minusFMLts xwy xwz = splitLT xwy xwz;
136.49/108.27	"
136.49/108.27	"minusFMGts xwy xwz = splitGT xwy xwz;
136.49/108.27	"
136.49/108.27	The bindings of the following Let/Where expression
136.49/108.27	"let {
136.49/108.27	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
136.49/108.27	} in result where {
136.49/108.27	balance_ok  = True;
136.49/108.27	;
136.49/108.27	left_ok  = left_ok0 fm_l key fm_l;
136.49/108.27	;
136.49/108.27	left_ok0 fm_l key EmptyFM = True;
136.49/108.27	left_ok0 fm_l key (Branch left_key yy yz zu zv) = let {
136.49/108.27	biggest_left_key  = fst (findMax fm_l);
136.49/108.27	} in biggest_left_key < key;
136.49/108.27	;
136.49/108.27	left_size  = sizeFM fm_l;
136.49/108.27	;
136.49/108.27	right_ok  = right_ok0 fm_r key fm_r;
136.49/108.27	;
136.49/108.27	right_ok0 fm_r key EmptyFM = True;
136.49/108.27	right_ok0 fm_r key (Branch right_key zw zx zy zz) = let {
136.49/108.27	smallest_right_key  = fst (findMin fm_r);
136.49/108.27	} in key < smallest_right_key;
136.49/108.27	;
136.49/108.27	right_size  = sizeFM fm_r;
136.49/108.27	;
136.49/108.27	unbox x = x;
136.49/108.27	} 
136.49/108.27	"
136.49/108.27	are unpacked to the following functions on top level
136.49/108.27	"mkBranchBalance_ok xxu xxv xxw = True;
136.49/108.27	"
136.49/108.27	"mkBranchLeft_size xxu xxv xxw = sizeFM xxu;
136.49/108.27	"
136.49/108.27	"mkBranchUnbox xxu xxv xxw x = x;
136.49/108.27	"
136.49/108.27	"mkBranchLeft_ok xxu xxv xxw = mkBranchLeft_ok0 xxu xxv xxw xxu xxv xxu;
136.49/108.27	"
136.49/108.27	"mkBranchRight_size xxu xxv xxw = sizeFM xxw;
136.49/108.27	"
136.49/108.27	"mkBranchRight_ok xxu xxv xxw = mkBranchRight_ok0 xxu xxv xxw xxw xxv xxw;
136.49/108.27	"
136.49/108.27	"mkBranchRight_ok0 xxu xxv xxw fm_r key EmptyFM = True;
136.49/108.27	mkBranchRight_ok0 xxu xxv xxw fm_r key (Branch right_key zw zx zy zz) = key < mkBranchRight_ok0Smallest_right_key fm_r;
136.49/108.27	"
136.49/108.27	"mkBranchLeft_ok0 xxu xxv xxw fm_l key EmptyFM = True;
136.49/108.27	mkBranchLeft_ok0 xxu xxv xxw fm_l key (Branch left_key yy yz zu zv) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
136.49/108.27	"
136.49/108.27	The bindings of the following Let/Where expression
136.49/108.27	"let {
136.49/108.27	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
136.49/108.27	} in result"
136.49/108.27	are unpacked to the following functions on top level
136.49/108.27	"mkBranchResult xxx xxy xxz xyu = Branch xxx xxy (mkBranchUnbox xxz xxx xyu (1 + mkBranchLeft_size xxz xxx xyu + mkBranchRight_size xxz xxx xyu)) xxz xyu;
136.49/108.27	"
136.49/108.27	The bindings of the following Let/Where expression
136.49/108.27	"glueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * size_l < size_r) where {
136.49/108.27	glueVBal0 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = glueBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv);
136.49/108.27	;
136.49/108.27	glueVBal1 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vxx vxy vyu (glueVBal vyv (Branch vyx vyy vyz vzu vzv));
136.49/108.27	glueVBal1 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal0 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv otherwise;
136.49/108.27	;
136.49/108.27	glueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vyx vyy (glueVBal (Branch vxx vxy vxz vyu vyv) vzu) vzv;
136.49/108.27	glueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal1 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * size_r < size_l);
136.49/108.27	;
136.49/108.27	size_l  = sizeFM (Branch vxx vxy vxz vyu vyv);
136.49/108.27	;
136.49/108.27	size_r  = sizeFM (Branch vyx vyy vyz vzu vzv);
136.49/108.27	} 
136.49/108.27	"
136.49/108.27	are unpacked to the following functions on top level
136.49/108.27	"glueVBal3Size_l xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy = sizeFM (Branch xyv xyw xyx xyy xyz);
136.49/108.27	"
136.49/108.27	"glueVBal3GlueVBal0 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = glueBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv);
136.49/108.27	"
136.49/108.27	"glueVBal3GlueVBal1 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vxx vxy vyu (glueVBal vyv (Branch vyx vyy vyz vzu vzv));
136.49/108.27	glueVBal3GlueVBal1 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal3GlueVBal0 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv otherwise;
136.49/108.27	"
136.49/108.27	"glueVBal3GlueVBal2 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vyx vyy (glueVBal (Branch vxx vxy vxz vyu vyv) vzu) vzv;
136.49/108.27	glueVBal3GlueVBal2 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal3GlueVBal1 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * glueVBal3Size_r xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy < glueVBal3Size_l xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy);
136.49/108.27	"
136.49/108.27	"glueVBal3Size_r xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy = sizeFM (Branch xzu xzv xzw xzx xzy);
136.49/108.27	"
136.49/108.27	The bindings of the following Let/Where expression
136.49/108.27	"glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where {
136.49/108.27	glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2;
136.49/108.27	;
136.49/108.27	glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2);
136.49/108.27	glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise;
136.49/108.27	;
136.49/108.27	mid_elt1  = mid_elt10 vv2;
136.49/108.27	;
136.49/108.27	mid_elt10 (vwz,mid_elt1) = mid_elt1;
136.49/108.27	;
136.49/108.27	mid_elt2  = mid_elt20 vv3;
136.49/108.27	;
136.49/108.27	mid_elt20 (vwy,mid_elt2) = mid_elt2;
136.49/108.27	;
136.49/108.27	mid_key1  = mid_key10 vv2;
136.49/108.27	;
136.49/108.27	mid_key10 (mid_key1,vxu) = mid_key1;
136.49/108.27	;
136.49/108.27	mid_key2  = mid_key20 vv3;
136.49/108.27	;
136.49/108.27	mid_key20 (mid_key2,vxv) = mid_key2;
136.49/108.27	;
136.49/108.27	vv2  = findMax fm1;
136.49/108.27	;
136.49/108.27	vv3  = findMin fm2;
136.49/108.27	} 
136.49/108.27	"
136.49/108.27	are unpacked to the following functions on top level
136.49/108.27	"glueBal2GlueBal0 xzz yuu fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 xzz yuu) (glueBal2Mid_elt1 xzz yuu) (deleteMax fm1) fm2;
136.49/108.27	"
136.49/108.27	"glueBal2Mid_elt10 xzz yuu (vwz,mid_elt1) = mid_elt1;
136.49/108.27	"
136.49/108.27	"glueBal2Mid_key20 xzz yuu (mid_key2,vxv) = mid_key2;
136.49/108.27	"
136.49/108.27	"glueBal2Mid_elt1 xzz yuu = glueBal2Mid_elt10 xzz yuu (glueBal2Vv2 xzz yuu);
136.49/108.27	"
136.49/108.27	"glueBal2Mid_key10 xzz yuu (mid_key1,vxu) = mid_key1;
136.49/108.27	"
136.49/108.27	"glueBal2Vv3 xzz yuu = findMin xzz;
136.49/108.27	"
136.49/108.27	"glueBal2GlueBal1 xzz yuu fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 xzz yuu) (glueBal2Mid_elt2 xzz yuu) fm1 (deleteMin fm2);
136.49/108.27	glueBal2GlueBal1 xzz yuu fm1 fm2 False = glueBal2GlueBal0 xzz yuu fm1 fm2 otherwise;
136.49/108.27	"
136.49/108.27	"glueBal2Mid_key2 xzz yuu = glueBal2Mid_key20 xzz yuu (glueBal2Vv3 xzz yuu);
136.49/108.27	"
136.49/108.27	"glueBal2Vv2 xzz yuu = findMax yuu;
136.49/108.27	"
136.49/108.27	"glueBal2Mid_key1 xzz yuu = glueBal2Mid_key10 xzz yuu (glueBal2Vv2 xzz yuu);
136.49/108.27	"
136.49/108.27	"glueBal2Mid_elt2 xzz yuu = glueBal2Mid_elt20 xzz yuu (glueBal2Vv3 xzz yuu);
136.49/108.27	"
136.49/108.27	"glueBal2Mid_elt20 xzz yuu (vwy,mid_elt2) = mid_elt2;
136.49/108.27	"
136.49/108.27	The bindings of the following Let/Where expression
136.49/108.27	"mkVBalBranch2 key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * size_l < size_r) where {
136.49/108.27	mkVBalBranch0 key elt wu wv ww wx wy xu xv xw xx xy True = mkBranch 13 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy);
136.49/108.27	;
136.49/108.27	mkVBalBranch1 key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch wu wv wx (mkVBalBranch key elt wy (Branch xu xv xw xx xy));
136.49/108.27	mkVBalBranch1 key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch0 key elt wu wv ww wx wy xu xv xw xx xy otherwise;
136.49/108.27	;
136.49/108.27	mkVBalBranch2 key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch xu xv (mkVBalBranch key elt (Branch wu wv ww wx wy) xx) xy;
136.49/108.27	mkVBalBranch2 key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch1 key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * size_r < size_l);
136.49/108.27	;
136.49/108.27	size_l  = sizeFM (Branch wu wv ww wx wy);
136.49/108.27	;
136.49/108.27	size_r  = sizeFM (Branch xu xv xw xx xy);
136.49/108.27	} 
136.49/108.27	"
136.49/108.27	are unpacked to the following functions on top level
136.49/108.27	"mkVBalBranch3MkVBalBranch0 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy True = mkBranch 13 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy);
136.49/108.27	"
136.49/108.27	"mkVBalBranch3Size_l yuv yuw yux yuy yuz yvu yvv yvw yvx yvy = sizeFM (Branch yuv yuw yux yuy yuz);
136.49/108.27	"
136.49/108.27	"mkVBalBranch3MkVBalBranch2 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch xu xv (mkVBalBranch key elt (Branch wu wv ww wx wy) xx) xy;
136.49/108.27	mkVBalBranch3MkVBalBranch2 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch3MkVBalBranch1 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * mkVBalBranch3Size_r yuv yuw yux yuy yuz yvu yvv yvw yvx yvy < mkVBalBranch3Size_l yuv yuw yux yuy yuz yvu yvv yvw yvx yvy);
136.49/108.27	"
136.49/108.27	"mkVBalBranch3MkVBalBranch1 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch wu wv wx (mkVBalBranch key elt wy (Branch xu xv xw xx xy));
136.49/108.27	mkVBalBranch3MkVBalBranch1 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch3MkVBalBranch0 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy otherwise;
136.49/108.27	"
136.49/108.27	"mkVBalBranch3Size_r yuv yuw yux yuy yuz yvu yvv yvw yvx yvy = sizeFM (Branch yvu yvv yvw yvx yvy);
136.49/108.27	"
136.49/108.27	The bindings of the following Let/Where expression
136.49/108.27	"let {
136.49/108.27	smallest_right_key  = fst (findMin fm_r);
136.49/108.27	} in key < smallest_right_key"
136.49/108.27	are unpacked to the following functions on top level
136.49/108.27	"mkBranchRight_ok0Smallest_right_key yvz = fst (findMin yvz);
136.49/108.27	"
136.49/108.27	The bindings of the following Let/Where expression
136.49/108.27	"let {
136.49/108.27	biggest_left_key  = fst (findMax fm_l);
136.49/108.27	} in biggest_left_key < key"
136.49/108.27	are unpacked to the following functions on top level
136.49/108.27	"mkBranchLeft_ok0Biggest_left_key ywu = fst (findMax ywu);
136.49/108.27	"
136.49/108.27	
136.49/108.27	----------------------------------------
136.49/108.27	
136.49/108.27	(10)
136.49/108.27	Obligation:
136.49/108.27	mainModule Main 
136.49/108.27	module FiniteMap where {
136.49/108.27	import qualified Main;
136.49/108.27	import qualified Maybe;
136.49/108.27	import qualified Prelude;
136.49/108.27	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
136.49/108.27	
136.49/108.27	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
136.49/108.27	}
136.49/108.27	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
136.49/108.27	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
136.49/108.27	
136.49/108.27	addToFM0 old new = new;
136.49/108.27	
136.49/108.27	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
136.49/108.27	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
136.49/108.27	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt;
136.49/108.27	
136.49/108.27	addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt True = Branch new_key (combiner elt new_elt) size fm_l fm_r;
136.49/108.27	
136.49/108.27	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt);
136.49/108.27	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt otherwise;
136.49/108.27	
136.49/108.27	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r;
136.49/108.27	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt (new_key > key);
136.49/108.27	
136.49/108.27	addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt (new_key < key);
136.49/108.27	
136.49/108.27	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
136.49/108.27	addToFM_C4 wvw wvx wvy wvz = addToFM_C3 wvw wvx wvy wvz;
136.49/108.27	
136.49/108.27	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
136.49/108.27	deleteMax (Branch key elt xz fm_l EmptyFM) = fm_l;
136.49/108.27	deleteMax (Branch key elt yu fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
136.49/108.27	
136.49/108.27	deleteMin :: Ord a => FiniteMap a b  ->  FiniteMap a b;
136.49/108.27	deleteMin (Branch key elt wuu EmptyFM fm_r) = fm_r;
136.49/108.27	deleteMin (Branch key elt wuv fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
136.49/108.27	
136.49/108.27	emptyFM :: FiniteMap b a;
136.49/108.27	emptyFM = EmptyFM;
136.49/108.27	
136.49/108.27	findMax :: FiniteMap a b  ->  (a,b);
136.49/108.27	findMax (Branch key elt vuu vuv EmptyFM) = (key,elt);
136.49/108.27	findMax (Branch key elt vuw vux fm_r) = findMax fm_r;
136.49/108.27	
136.49/108.27	findMin :: FiniteMap b a  ->  (b,a);
136.49/108.27	findMin (Branch key elt wuw EmptyFM wux) = (key,elt);
136.49/108.27	findMin (Branch key elt wuy fm_l wuz) = findMin fm_l;
136.49/108.27	
136.49/108.27	glueBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
136.49/108.27	glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
136.49/108.27	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
136.49/108.27	glueBal fm1 fm2 = glueBal2 fm1 fm2;
136.49/108.27	
136.49/108.27	glueBal2 fm1 fm2 = glueBal2GlueBal1 fm2 fm1 fm1 fm2 (sizeFM fm2 > sizeFM fm1);
136.49/108.27	
136.49/108.27	glueBal2GlueBal0 xzz yuu fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 xzz yuu) (glueBal2Mid_elt1 xzz yuu) (deleteMax fm1) fm2;
136.49/108.27	
136.49/108.27	glueBal2GlueBal1 xzz yuu fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 xzz yuu) (glueBal2Mid_elt2 xzz yuu) fm1 (deleteMin fm2);
136.49/108.27	glueBal2GlueBal1 xzz yuu fm1 fm2 False = glueBal2GlueBal0 xzz yuu fm1 fm2 otherwise;
136.49/108.27	
136.49/108.27	glueBal2Mid_elt1 xzz yuu = glueBal2Mid_elt10 xzz yuu (glueBal2Vv2 xzz yuu);
136.49/108.27	
136.49/108.27	glueBal2Mid_elt10 xzz yuu (vwz,mid_elt1) = mid_elt1;
136.49/108.27	
136.49/108.27	glueBal2Mid_elt2 xzz yuu = glueBal2Mid_elt20 xzz yuu (glueBal2Vv3 xzz yuu);
136.49/108.27	
136.49/108.27	glueBal2Mid_elt20 xzz yuu (vwy,mid_elt2) = mid_elt2;
136.49/108.27	
136.49/108.27	glueBal2Mid_key1 xzz yuu = glueBal2Mid_key10 xzz yuu (glueBal2Vv2 xzz yuu);
136.49/108.30	
136.49/108.30	glueBal2Mid_key10 xzz yuu (mid_key1,vxu) = mid_key1;
136.49/108.30	
136.49/108.30	glueBal2Mid_key2 xzz yuu = glueBal2Mid_key20 xzz yuu (glueBal2Vv3 xzz yuu);
136.49/108.30	
136.49/108.30	glueBal2Mid_key20 xzz yuu (mid_key2,vxv) = mid_key2;
136.49/108.30	
136.49/108.30	glueBal2Vv2 xzz yuu = findMax yuu;
136.49/108.30	
136.49/108.30	glueBal2Vv3 xzz yuu = findMin xzz;
136.49/108.30	
136.49/108.30	glueBal3 fm1 EmptyFM = fm1;
136.49/108.30	glueBal3 wzz xuu = glueBal2 wzz xuu;
136.49/108.30	
136.49/108.30	glueBal4 EmptyFM fm2 = fm2;
136.49/108.30	glueBal4 xuw xux = glueBal3 xuw xux;
136.49/108.30	
136.49/108.30	glueVBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
136.49/108.30	glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2;
136.49/108.30	glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM;
136.49/108.30	glueVBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv) = glueVBal3 (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv);
136.49/108.30	
136.49/108.30	glueVBal3 (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv) = glueVBal3GlueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * glueVBal3Size_l vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv < glueVBal3Size_r vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv);
136.49/108.30	
136.49/108.30	glueVBal3GlueVBal0 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = glueBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv);
136.49/108.30	
136.49/108.30	glueVBal3GlueVBal1 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vxx vxy vyu (glueVBal vyv (Branch vyx vyy vyz vzu vzv));
136.49/108.30	glueVBal3GlueVBal1 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal3GlueVBal0 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv otherwise;
136.49/108.30	
136.49/108.30	glueVBal3GlueVBal2 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vyx vyy (glueVBal (Branch vxx vxy vxz vyu vyv) vzu) vzv;
136.49/108.30	glueVBal3GlueVBal2 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal3GlueVBal1 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * glueVBal3Size_r xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy < glueVBal3Size_l xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy);
136.49/108.30	
136.49/108.30	glueVBal3Size_l xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy = sizeFM (Branch xyv xyw xyx xyy xyz);
136.49/108.30	
136.49/108.30	glueVBal3Size_r xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy = sizeFM (Branch xzu xzv xzw xzx xzy);
136.49/108.30	
136.49/108.30	glueVBal4 fm1 EmptyFM = fm1;
136.49/108.30	glueVBal4 xvv xvw = glueVBal3 xvv xvw;
136.49/108.30	
136.49/108.30	glueVBal5 EmptyFM fm2 = fm2;
136.49/108.30	glueVBal5 xvy xvz = glueVBal4 xvy xvz;
136.49/108.30	
136.49/108.30	minusFM :: Ord c => FiniteMap c b  ->  FiniteMap c a  ->  FiniteMap c b;
136.49/108.30	minusFM EmptyFM fm2 = emptyFM;
136.49/108.30	minusFM fm1 EmptyFM = fm1;
136.49/108.30	minusFM fm1 (Branch split_key elt yx left right) = glueVBal (minusFM (minusFMLts fm1 split_key) left) (minusFM (minusFMGts fm1 split_key) right);
136.49/108.30	
136.49/108.30	minusFMGts xwy xwz = splitGT xwy xwz;
136.49/108.30	
136.49/108.30	minusFMLts xwy xwz = splitLT xwy xwz;
136.49/108.30	
136.49/108.30	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
136.49/108.30	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
136.49/108.30	
136.49/108.30	mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_R fm_L key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_R fm_L + mkBalBranch6Size_r key elt fm_R fm_L < 2);
136.49/108.30	
136.49/108.30	mkBalBranch6Double_L xwu xwv xww xwx fm_l (Branch key_r elt_r vvy (Branch key_rl elt_rl vvz fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 xwu xwv fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
136.49/108.30	
136.49/108.30	mkBalBranch6Double_R xwu xwv xww xwx (Branch key_l elt_l vuz fm_ll (Branch key_lr elt_lr vvu fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 xwu xwv fm_lrr fm_r);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch0 xwu xwv xww xwx fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch6MkBalBranch02 xwu xwv xww xwx fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch00 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr True = mkBalBranch6Double_L xwu xwv xww xwx fm_L fm_R;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch01 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr True = mkBalBranch6Single_L xwu xwv xww xwx fm_L fm_R;
136.49/108.30	mkBalBranch6MkBalBranch01 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr False = mkBalBranch6MkBalBranch00 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr otherwise;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch02 xwu xwv xww xwx fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch6MkBalBranch01 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch1 xwu xwv xww xwx fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch6MkBalBranch12 xwu xwv xww xwx fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch10 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr True = mkBalBranch6Double_R xwu xwv xww xwx fm_L fm_R;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch11 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr True = mkBalBranch6Single_R xwu xwv xww xwx fm_L fm_R;
136.49/108.30	mkBalBranch6MkBalBranch11 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr False = mkBalBranch6MkBalBranch10 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr otherwise;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch12 xwu xwv xww xwx fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch6MkBalBranch11 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch2 xwu xwv xww xwx key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch3 xwu xwv xww xwx key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 xwu xwv xww xwx fm_L fm_R fm_L;
136.49/108.30	mkBalBranch6MkBalBranch3 xwu xwv xww xwx key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 xwu xwv xww xwx key elt fm_L fm_R otherwise;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch4 xwu xwv xww xwx key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 xwu xwv xww xwx fm_L fm_R fm_R;
136.49/108.30	mkBalBranch6MkBalBranch4 xwu xwv xww xwx key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 xwu xwv xww xwx key elt fm_L fm_R (mkBalBranch6Size_l xwu xwv xww xwx > sIZE_RATIO * mkBalBranch6Size_r xwu xwv xww xwx);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch5 xwu xwv xww xwx key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
136.49/108.30	mkBalBranch6MkBalBranch5 xwu xwv xww xwx key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 xwu xwv xww xwx key elt fm_L fm_R (mkBalBranch6Size_r xwu xwv xww xwx > sIZE_RATIO * mkBalBranch6Size_l xwu xwv xww xwx);
136.49/108.30	
136.49/108.30	mkBalBranch6Single_L xwu xwv xww xwx fm_l (Branch key_r elt_r vwx fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 xwu xwv fm_l fm_rl) fm_rr;
136.49/108.30	
136.49/108.30	mkBalBranch6Single_R xwu xwv xww xwx (Branch key_l elt_l vuy fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 xwu xwv fm_lr fm_r);
136.49/108.30	
136.49/108.30	mkBalBranch6Size_l xwu xwv xww xwx = sizeFM xwx;
136.49/108.30	
136.49/108.30	mkBalBranch6Size_r xwu xwv xww xwx = sizeFM xww;
136.49/108.30	
136.49/108.30	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
136.49/108.30	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r;
136.49/108.30	
136.49/108.30	mkBranchBalance_ok xxu xxv xxw = True;
136.49/108.30	
136.49/108.30	mkBranchLeft_ok xxu xxv xxw = mkBranchLeft_ok0 xxu xxv xxw xxu xxv xxu;
136.49/108.30	
136.49/108.30	mkBranchLeft_ok0 xxu xxv xxw fm_l key EmptyFM = True;
136.49/108.30	mkBranchLeft_ok0 xxu xxv xxw fm_l key (Branch left_key yy yz zu zv) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
136.49/108.30	
136.49/108.30	mkBranchLeft_ok0Biggest_left_key ywu = fst (findMax ywu);
136.49/108.30	
136.49/108.30	mkBranchLeft_size xxu xxv xxw = sizeFM xxu;
136.49/108.30	
136.49/108.30	mkBranchResult xxx xxy xxz xyu = Branch xxx xxy (mkBranchUnbox xxz xxx xyu (1 + mkBranchLeft_size xxz xxx xyu + mkBranchRight_size xxz xxx xyu)) xxz xyu;
136.49/108.30	
136.49/108.30	mkBranchRight_ok xxu xxv xxw = mkBranchRight_ok0 xxu xxv xxw xxw xxv xxw;
136.49/108.30	
136.49/108.30	mkBranchRight_ok0 xxu xxv xxw fm_r key EmptyFM = True;
136.49/108.30	mkBranchRight_ok0 xxu xxv xxw fm_r key (Branch right_key zw zx zy zz) = key < mkBranchRight_ok0Smallest_right_key fm_r;
136.49/108.30	
136.49/108.30	mkBranchRight_ok0Smallest_right_key yvz = fst (findMin yvz);
136.49/108.30	
136.49/108.30	mkBranchRight_size xxu xxv xxw = sizeFM xxw;
136.49/108.30	
136.49/108.30	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  a ( ->  (FiniteMap a b) (Int  ->  Int)));
136.49/108.30	mkBranchUnbox xxu xxv xxw x = x;
136.49/108.30	
136.49/108.30	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
136.49/108.30	mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
136.49/108.30	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
136.49/108.30	mkVBalBranch key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy) = mkVBalBranch3 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy);
136.49/108.30	
136.49/108.30	mkVBalBranch3 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy) = mkVBalBranch3MkVBalBranch2 wu wv ww wx wy xu xv xw xx xy key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * mkVBalBranch3Size_l wu wv ww wx wy xu xv xw xx xy < mkVBalBranch3Size_r wu wv ww wx wy xu xv xw xx xy);
136.49/108.30	
136.49/108.30	mkVBalBranch3MkVBalBranch0 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy True = mkBranch 13 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy);
136.49/108.30	
136.49/108.30	mkVBalBranch3MkVBalBranch1 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch wu wv wx (mkVBalBranch key elt wy (Branch xu xv xw xx xy));
136.49/108.30	mkVBalBranch3MkVBalBranch1 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch3MkVBalBranch0 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy otherwise;
136.49/108.30	
136.49/108.30	mkVBalBranch3MkVBalBranch2 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch xu xv (mkVBalBranch key elt (Branch wu wv ww wx wy) xx) xy;
136.49/108.30	mkVBalBranch3MkVBalBranch2 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch3MkVBalBranch1 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * mkVBalBranch3Size_r yuv yuw yux yuy yuz yvu yvv yvw yvx yvy < mkVBalBranch3Size_l yuv yuw yux yuy yuz yvu yvv yvw yvx yvy);
136.49/108.30	
136.49/108.30	mkVBalBranch3Size_l yuv yuw yux yuy yuz yvu yvv yvw yvx yvy = sizeFM (Branch yuv yuw yux yuy yuz);
136.49/108.30	
136.49/108.30	mkVBalBranch3Size_r yuv yuw yux yuy yuz yvu yvv yvw yvx yvy = sizeFM (Branch yvu yvv yvw yvx yvy);
136.49/108.30	
136.49/108.30	mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
136.49/108.30	mkVBalBranch4 wwx wwy wwz wxu = mkVBalBranch3 wwx wwy wwz wxu;
136.49/108.30	
136.49/108.30	mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
136.49/108.30	mkVBalBranch5 wxw wxx wxy wxz = mkVBalBranch4 wxw wxx wxy wxz;
136.49/108.30	
136.49/108.30	sIZE_RATIO :: Int;
136.49/108.30	sIZE_RATIO = 5;
136.49/108.30	
136.49/108.30	sizeFM :: FiniteMap b a  ->  Int;
136.49/108.30	sizeFM EmptyFM = 0;
136.49/108.30	sizeFM (Branch vzw vzx size vzy vzz) = size;
136.49/108.30	
136.49/108.30	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
136.49/108.30	splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
136.49/108.30	splitGT (Branch key elt yv fm_l fm_r) split_key = splitGT3 (Branch key elt yv fm_l fm_r) split_key;
136.49/108.30	
136.49/108.30	splitGT0 key elt yv fm_l fm_r split_key True = fm_r;
136.49/108.30	
136.49/108.30	splitGT1 key elt yv fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
136.49/108.30	splitGT1 key elt yv fm_l fm_r split_key False = splitGT0 key elt yv fm_l fm_r split_key otherwise;
136.49/108.30	
136.49/108.30	splitGT2 key elt yv fm_l fm_r split_key True = splitGT fm_r split_key;
136.49/108.30	splitGT2 key elt yv fm_l fm_r split_key False = splitGT1 key elt yv fm_l fm_r split_key (split_key < key);
136.49/108.30	
136.49/108.30	splitGT3 (Branch key elt yv fm_l fm_r) split_key = splitGT2 key elt yv fm_l fm_r split_key (split_key > key);
136.49/108.30	
136.49/108.30	splitGT4 EmptyFM split_key = emptyFM;
136.49/108.30	splitGT4 wyw wyx = splitGT3 wyw wyx;
136.49/108.30	
136.49/108.30	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
136.49/108.30	splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
136.49/108.30	splitLT (Branch key elt yw fm_l fm_r) split_key = splitLT3 (Branch key elt yw fm_l fm_r) split_key;
136.49/108.30	
136.49/108.30	splitLT0 key elt yw fm_l fm_r split_key True = fm_l;
136.49/108.30	
136.49/108.30	splitLT1 key elt yw fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
136.49/108.30	splitLT1 key elt yw fm_l fm_r split_key False = splitLT0 key elt yw fm_l fm_r split_key otherwise;
136.49/108.30	
136.49/108.30	splitLT2 key elt yw fm_l fm_r split_key True = splitLT fm_l split_key;
136.49/108.30	splitLT2 key elt yw fm_l fm_r split_key False = splitLT1 key elt yw fm_l fm_r split_key (split_key > key);
136.49/108.30	
136.49/108.30	splitLT3 (Branch key elt yw fm_l fm_r) split_key = splitLT2 key elt yw fm_l fm_r split_key (split_key < key);
136.49/108.30	
136.49/108.30	splitLT4 EmptyFM split_key = emptyFM;
136.49/108.30	splitLT4 wzu wzv = splitLT3 wzu wzv;
136.49/108.30	
136.49/108.30	unitFM :: b  ->  a  ->  FiniteMap b a;
136.49/108.30	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
136.49/108.30	
136.49/108.30	}
136.49/108.30	module Maybe where {
136.49/108.30	import qualified FiniteMap;
136.49/108.30	import qualified Main;
136.49/108.30	import qualified Prelude;
136.49/108.30	}
136.49/108.30	module Main where {
136.49/108.30	import qualified FiniteMap;
136.49/108.30	import qualified Maybe;
136.49/108.30	import qualified Prelude;
136.49/108.30	}
136.49/108.30	
136.49/108.30	----------------------------------------
136.49/108.30	
136.49/108.30	(11) NumRed (SOUND)
136.49/108.30	Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero.
136.49/108.30	----------------------------------------
136.49/108.30	
136.49/108.30	(12)
136.49/108.30	Obligation:
136.49/108.30	mainModule Main 
136.49/108.30	module FiniteMap where {
136.49/108.30	import qualified Main;
136.49/108.30	import qualified Maybe;
136.49/108.30	import qualified Prelude;
136.49/108.30	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
136.49/108.30	
136.49/108.30	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
136.49/108.30	}
136.49/108.30	addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
136.49/108.30	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
136.49/108.30	
136.49/108.30	addToFM0 old new = new;
136.49/108.30	
136.49/108.30	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
136.49/108.30	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
136.49/108.30	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt;
136.49/108.30	
136.49/108.30	addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt True = Branch new_key (combiner elt new_elt) size fm_l fm_r;
136.49/108.30	
136.49/108.30	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt);
136.49/108.30	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt otherwise;
136.49/108.30	
136.49/108.30	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r;
136.49/108.30	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt (new_key > key);
136.49/108.30	
136.49/108.30	addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt (new_key < key);
136.49/108.30	
136.49/108.30	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
136.49/108.30	addToFM_C4 wvw wvx wvy wvz = addToFM_C3 wvw wvx wvy wvz;
136.49/108.30	
136.49/108.30	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
136.49/108.30	deleteMax (Branch key elt xz fm_l EmptyFM) = fm_l;
136.49/108.30	deleteMax (Branch key elt yu fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
136.49/108.30	
136.49/108.30	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
136.49/108.30	deleteMin (Branch key elt wuu EmptyFM fm_r) = fm_r;
136.49/108.30	deleteMin (Branch key elt wuv fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
136.49/108.30	
136.49/108.30	emptyFM :: FiniteMap b a;
136.49/108.30	emptyFM = EmptyFM;
136.49/108.30	
136.49/108.30	findMax :: FiniteMap a b  ->  (a,b);
136.49/108.30	findMax (Branch key elt vuu vuv EmptyFM) = (key,elt);
136.49/108.30	findMax (Branch key elt vuw vux fm_r) = findMax fm_r;
136.49/108.30	
136.49/108.30	findMin :: FiniteMap a b  ->  (a,b);
136.49/108.30	findMin (Branch key elt wuw EmptyFM wux) = (key,elt);
136.49/108.30	findMin (Branch key elt wuy fm_l wuz) = findMin fm_l;
136.49/108.30	
136.49/108.30	glueBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
136.49/108.30	glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
136.49/108.30	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
136.49/108.30	glueBal fm1 fm2 = glueBal2 fm1 fm2;
136.49/108.30	
136.49/108.30	glueBal2 fm1 fm2 = glueBal2GlueBal1 fm2 fm1 fm1 fm2 (sizeFM fm2 > sizeFM fm1);
136.49/108.30	
136.49/108.30	glueBal2GlueBal0 xzz yuu fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 xzz yuu) (glueBal2Mid_elt1 xzz yuu) (deleteMax fm1) fm2;
136.49/108.30	
136.49/108.30	glueBal2GlueBal1 xzz yuu fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 xzz yuu) (glueBal2Mid_elt2 xzz yuu) fm1 (deleteMin fm2);
136.49/108.30	glueBal2GlueBal1 xzz yuu fm1 fm2 False = glueBal2GlueBal0 xzz yuu fm1 fm2 otherwise;
136.49/108.30	
136.49/108.30	glueBal2Mid_elt1 xzz yuu = glueBal2Mid_elt10 xzz yuu (glueBal2Vv2 xzz yuu);
136.49/108.30	
136.49/108.30	glueBal2Mid_elt10 xzz yuu (vwz,mid_elt1) = mid_elt1;
136.49/108.30	
136.49/108.30	glueBal2Mid_elt2 xzz yuu = glueBal2Mid_elt20 xzz yuu (glueBal2Vv3 xzz yuu);
136.49/108.30	
136.49/108.30	glueBal2Mid_elt20 xzz yuu (vwy,mid_elt2) = mid_elt2;
136.49/108.30	
136.49/108.30	glueBal2Mid_key1 xzz yuu = glueBal2Mid_key10 xzz yuu (glueBal2Vv2 xzz yuu);
136.49/108.30	
136.49/108.30	glueBal2Mid_key10 xzz yuu (mid_key1,vxu) = mid_key1;
136.49/108.30	
136.49/108.30	glueBal2Mid_key2 xzz yuu = glueBal2Mid_key20 xzz yuu (glueBal2Vv3 xzz yuu);
136.49/108.30	
136.49/108.30	glueBal2Mid_key20 xzz yuu (mid_key2,vxv) = mid_key2;
136.49/108.30	
136.49/108.30	glueBal2Vv2 xzz yuu = findMax yuu;
136.49/108.30	
136.49/108.30	glueBal2Vv3 xzz yuu = findMin xzz;
136.49/108.30	
136.49/108.30	glueBal3 fm1 EmptyFM = fm1;
136.49/108.30	glueBal3 wzz xuu = glueBal2 wzz xuu;
136.49/108.30	
136.49/108.30	glueBal4 EmptyFM fm2 = fm2;
136.49/108.30	glueBal4 xuw xux = glueBal3 xuw xux;
136.49/108.30	
136.49/108.30	glueVBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
136.49/108.30	glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2;
136.49/108.30	glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM;
136.49/108.30	glueVBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv) = glueVBal3 (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv);
136.49/108.30	
136.49/108.30	glueVBal3 (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv) = glueVBal3GlueVBal2 vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * glueVBal3Size_l vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv < glueVBal3Size_r vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv);
136.49/108.30	
136.49/108.30	glueVBal3GlueVBal0 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = glueBal (Branch vxx vxy vxz vyu vyv) (Branch vyx vyy vyz vzu vzv);
136.49/108.30	
136.49/108.30	glueVBal3GlueVBal1 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vxx vxy vyu (glueVBal vyv (Branch vyx vyy vyz vzu vzv));
136.49/108.30	glueVBal3GlueVBal1 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal3GlueVBal0 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv otherwise;
136.49/108.30	
136.49/108.30	glueVBal3GlueVBal2 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv True = mkBalBranch vyx vyy (glueVBal (Branch vxx vxy vxz vyu vyv) vzu) vzv;
136.49/108.30	glueVBal3GlueVBal2 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv False = glueVBal3GlueVBal1 xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy vxx vxy vxz vyu vyv vyx vyy vyz vzu vzv (sIZE_RATIO * glueVBal3Size_r xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy < glueVBal3Size_l xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy);
136.49/108.30	
136.49/108.30	glueVBal3Size_l xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy = sizeFM (Branch xyv xyw xyx xyy xyz);
136.49/108.30	
136.49/108.30	glueVBal3Size_r xyv xyw xyx xyy xyz xzu xzv xzw xzx xzy = sizeFM (Branch xzu xzv xzw xzx xzy);
136.49/108.30	
136.49/108.30	glueVBal4 fm1 EmptyFM = fm1;
136.49/108.30	glueVBal4 xvv xvw = glueVBal3 xvv xvw;
136.49/108.30	
136.49/108.30	glueVBal5 EmptyFM fm2 = fm2;
136.49/108.30	glueVBal5 xvy xvz = glueVBal4 xvy xvz;
136.49/108.30	
136.49/108.30	minusFM :: Ord b => FiniteMap b c  ->  FiniteMap b a  ->  FiniteMap b c;
136.49/108.30	minusFM EmptyFM fm2 = emptyFM;
136.49/108.30	minusFM fm1 EmptyFM = fm1;
136.49/108.30	minusFM fm1 (Branch split_key elt yx left right) = glueVBal (minusFM (minusFMLts fm1 split_key) left) (minusFM (minusFMGts fm1 split_key) right);
136.49/108.30	
136.49/108.30	minusFMGts xwy xwz = splitGT xwy xwz;
136.49/108.30	
136.49/108.30	minusFMLts xwy xwz = splitLT xwy xwz;
136.49/108.30	
136.49/108.30	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
136.49/108.30	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
136.49/108.30	
136.49/108.30	mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_R fm_L key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_R fm_L + mkBalBranch6Size_r key elt fm_R fm_L < Pos (Succ (Succ Zero)));
136.49/108.30	
136.49/108.30	mkBalBranch6Double_L xwu xwv xww xwx fm_l (Branch key_r elt_r vvy (Branch key_rl elt_rl vvz fm_rll fm_rlr) fm_rr) = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ Zero)))))) key_rl elt_rl (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))) xwu xwv fm_l fm_rll) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))) key_r elt_r fm_rlr fm_rr);
136.49/108.30	
136.49/108.30	mkBalBranch6Double_R xwu xwv xww xwx (Branch key_l elt_l vuz fm_ll (Branch key_lr elt_lr vvu fm_lrl fm_lrr)) fm_r = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))))) key_lr elt_lr (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))) key_l elt_l fm_ll fm_lrl) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))))))) xwu xwv fm_lrr fm_r);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch0 xwu xwv xww xwx fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch6MkBalBranch02 xwu xwv xww xwx fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch00 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr True = mkBalBranch6Double_L xwu xwv xww xwx fm_L fm_R;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch01 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr True = mkBalBranch6Single_L xwu xwv xww xwx fm_L fm_R;
136.49/108.30	mkBalBranch6MkBalBranch01 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr False = mkBalBranch6MkBalBranch00 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr otherwise;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch02 xwu xwv xww xwx fm_L fm_R (Branch vwu vwv vww fm_rl fm_rr) = mkBalBranch6MkBalBranch01 xwu xwv xww xwx fm_L fm_R vwu vwv vww fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch1 xwu xwv xww xwx fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch6MkBalBranch12 xwu xwv xww xwx fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch10 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr True = mkBalBranch6Double_R xwu xwv xww xwx fm_L fm_R;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch11 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr True = mkBalBranch6Single_R xwu xwv xww xwx fm_L fm_R;
136.49/108.30	mkBalBranch6MkBalBranch11 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr False = mkBalBranch6MkBalBranch10 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr otherwise;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch12 xwu xwv xww xwx fm_L fm_R (Branch vvv vvw vvx fm_ll fm_lr) = mkBalBranch6MkBalBranch11 xwu xwv xww xwx fm_L fm_R vvv vvw vvx fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch2 xwu xwv xww xwx key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch3 xwu xwv xww xwx key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 xwu xwv xww xwx fm_L fm_R fm_L;
136.49/108.30	mkBalBranch6MkBalBranch3 xwu xwv xww xwx key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 xwu xwv xww xwx key elt fm_L fm_R otherwise;
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch4 xwu xwv xww xwx key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 xwu xwv xww xwx fm_L fm_R fm_R;
136.49/108.30	mkBalBranch6MkBalBranch4 xwu xwv xww xwx key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 xwu xwv xww xwx key elt fm_L fm_R (mkBalBranch6Size_l xwu xwv xww xwx > sIZE_RATIO * mkBalBranch6Size_r xwu xwv xww xwx);
136.49/108.30	
136.49/108.30	mkBalBranch6MkBalBranch5 xwu xwv xww xwx key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R;
136.49/108.30	mkBalBranch6MkBalBranch5 xwu xwv xww xwx key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 xwu xwv xww xwx key elt fm_L fm_R (mkBalBranch6Size_r xwu xwv xww xwx > sIZE_RATIO * mkBalBranch6Size_l xwu xwv xww xwx);
136.49/108.30	
136.49/108.30	mkBalBranch6Single_L xwu xwv xww xwx fm_l (Branch key_r elt_r vwx fm_rl fm_rr) = mkBranch (Pos (Succ (Succ (Succ Zero)))) key_r elt_r (mkBranch (Pos (Succ (Succ (Succ (Succ Zero))))) xwu xwv fm_l fm_rl) fm_rr;
136.49/108.30	
136.49/108.30	mkBalBranch6Single_R xwu xwv xww xwx (Branch key_l elt_l vuy fm_ll fm_lr) fm_r = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))) key_l elt_l fm_ll (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))) xwu xwv fm_lr fm_r);
136.49/108.30	
136.49/108.30	mkBalBranch6Size_l xwu xwv xww xwx = sizeFM xwx;
136.49/108.30	
136.49/108.30	mkBalBranch6Size_r xwu xwv xww xwx = sizeFM xww;
136.49/108.30	
136.49/108.30	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
136.49/108.30	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r;
136.49/108.30	
136.49/108.30	mkBranchBalance_ok xxu xxv xxw = True;
136.49/108.30	
136.49/108.30	mkBranchLeft_ok xxu xxv xxw = mkBranchLeft_ok0 xxu xxv xxw xxu xxv xxu;
136.49/108.30	
136.49/108.30	mkBranchLeft_ok0 xxu xxv xxw fm_l key EmptyFM = True;
136.49/108.30	mkBranchLeft_ok0 xxu xxv xxw fm_l key (Branch left_key yy yz zu zv) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
136.49/108.30	
136.49/108.30	mkBranchLeft_ok0Biggest_left_key ywu = fst (findMax ywu);
136.49/108.30	
136.49/108.30	mkBranchLeft_size xxu xxv xxw = sizeFM xxu;
136.49/108.30	
136.49/108.30	mkBranchResult xxx xxy xxz xyu = Branch xxx xxy (mkBranchUnbox xxz xxx xyu (Pos (Succ Zero) + mkBranchLeft_size xxz xxx xyu + mkBranchRight_size xxz xxx xyu)) xxz xyu;
136.49/108.30	
136.49/108.30	mkBranchRight_ok xxu xxv xxw = mkBranchRight_ok0 xxu xxv xxw xxw xxv xxw;
136.49/108.30	
136.49/108.30	mkBranchRight_ok0 xxu xxv xxw fm_r key EmptyFM = True;
136.49/108.30	mkBranchRight_ok0 xxu xxv xxw fm_r key (Branch right_key zw zx zy zz) = key < mkBranchRight_ok0Smallest_right_key fm_r;
136.49/108.30	
136.49/108.30	mkBranchRight_ok0Smallest_right_key yvz = fst (findMin yvz);
136.49/108.30	
136.49/108.30	mkBranchRight_size xxu xxv xxw = sizeFM xxw;
136.49/108.30	
136.49/108.30	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  a ( ->  (FiniteMap a b) (Int  ->  Int)));
136.49/108.30	mkBranchUnbox xxu xxv xxw x = x;
136.49/108.30	
136.49/108.30	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
136.49/108.30	mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
136.49/108.30	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
136.49/108.30	mkVBalBranch key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy) = mkVBalBranch3 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy);
136.49/108.30	
136.49/108.30	mkVBalBranch3 key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy) = mkVBalBranch3MkVBalBranch2 wu wv ww wx wy xu xv xw xx xy key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * mkVBalBranch3Size_l wu wv ww wx wy xu xv xw xx xy < mkVBalBranch3Size_r wu wv ww wx wy xu xv xw xx xy);
136.49/108.30	
136.49/108.30	mkVBalBranch3MkVBalBranch0 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy True = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))))) key elt (Branch wu wv ww wx wy) (Branch xu xv xw xx xy);
136.49/108.30	
136.49/108.30	mkVBalBranch3MkVBalBranch1 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch wu wv wx (mkVBalBranch key elt wy (Branch xu xv xw xx xy));
136.49/108.30	mkVBalBranch3MkVBalBranch1 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch3MkVBalBranch0 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy otherwise;
136.49/108.30	
136.49/108.30	mkVBalBranch3MkVBalBranch2 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy True = mkBalBranch xu xv (mkVBalBranch key elt (Branch wu wv ww wx wy) xx) xy;
136.49/108.30	mkVBalBranch3MkVBalBranch2 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy False = mkVBalBranch3MkVBalBranch1 yuv yuw yux yuy yuz yvu yvv yvw yvx yvy key elt wu wv ww wx wy xu xv xw xx xy (sIZE_RATIO * mkVBalBranch3Size_r yuv yuw yux yuy yuz yvu yvv yvw yvx yvy < mkVBalBranch3Size_l yuv yuw yux yuy yuz yvu yvv yvw yvx yvy);
136.49/108.30	
136.49/108.30	mkVBalBranch3Size_l yuv yuw yux yuy yuz yvu yvv yvw yvx yvy = sizeFM (Branch yuv yuw yux yuy yuz);
136.49/108.30	
136.49/108.30	mkVBalBranch3Size_r yuv yuw yux yuy yuz yvu yvv yvw yvx yvy = sizeFM (Branch yvu yvv yvw yvx yvy);
136.49/108.30	
136.49/108.30	mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
136.49/108.30	mkVBalBranch4 wwx wwy wwz wxu = mkVBalBranch3 wwx wwy wwz wxu;
136.49/108.30	
136.49/108.30	mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
136.49/108.30	mkVBalBranch5 wxw wxx wxy wxz = mkVBalBranch4 wxw wxx wxy wxz;
136.49/108.30	
136.49/108.30	sIZE_RATIO :: Int;
136.49/108.30	sIZE_RATIO = Pos (Succ (Succ (Succ (Succ (Succ Zero)))));
136.49/108.30	
136.49/108.30	sizeFM :: FiniteMap b a  ->  Int;
136.49/108.30	sizeFM EmptyFM = Pos Zero;
136.49/108.30	sizeFM (Branch vzw vzx size vzy vzz) = size;
136.49/108.30	
136.49/108.30	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
136.49/108.30	splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
136.49/108.30	splitGT (Branch key elt yv fm_l fm_r) split_key = splitGT3 (Branch key elt yv fm_l fm_r) split_key;
136.49/108.30	
136.49/108.30	splitGT0 key elt yv fm_l fm_r split_key True = fm_r;
136.49/108.30	
136.49/108.30	splitGT1 key elt yv fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
136.49/108.30	splitGT1 key elt yv fm_l fm_r split_key False = splitGT0 key elt yv fm_l fm_r split_key otherwise;
136.49/108.30	
136.49/108.30	splitGT2 key elt yv fm_l fm_r split_key True = splitGT fm_r split_key;
136.49/108.30	splitGT2 key elt yv fm_l fm_r split_key False = splitGT1 key elt yv fm_l fm_r split_key (split_key < key);
136.49/108.30	
136.49/108.30	splitGT3 (Branch key elt yv fm_l fm_r) split_key = splitGT2 key elt yv fm_l fm_r split_key (split_key > key);
136.49/108.30	
136.49/108.30	splitGT4 EmptyFM split_key = emptyFM;
136.49/108.30	splitGT4 wyw wyx = splitGT3 wyw wyx;
136.49/108.30	
136.49/108.30	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
136.49/108.30	splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
136.49/108.30	splitLT (Branch key elt yw fm_l fm_r) split_key = splitLT3 (Branch key elt yw fm_l fm_r) split_key;
136.49/108.30	
136.49/108.30	splitLT0 key elt yw fm_l fm_r split_key True = fm_l;
136.49/108.30	
136.49/108.30	splitLT1 key elt yw fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
136.49/108.30	splitLT1 key elt yw fm_l fm_r split_key False = splitLT0 key elt yw fm_l fm_r split_key otherwise;
136.49/108.30	
136.49/108.30	splitLT2 key elt yw fm_l fm_r split_key True = splitLT fm_l split_key;
136.49/108.30	splitLT2 key elt yw fm_l fm_r split_key False = splitLT1 key elt yw fm_l fm_r split_key (split_key > key);
136.49/108.30	
136.49/108.30	splitLT3 (Branch key elt yw fm_l fm_r) split_key = splitLT2 key elt yw fm_l fm_r split_key (split_key < key);
136.49/108.30	
136.49/108.30	splitLT4 EmptyFM split_key = emptyFM;
136.49/108.30	splitLT4 wzu wzv = splitLT3 wzu wzv;
136.49/108.30	
136.49/108.30	unitFM :: a  ->  b  ->  FiniteMap a b;
136.49/108.30	unitFM key elt = Branch key elt (Pos (Succ Zero)) emptyFM emptyFM;
136.49/108.30	
136.49/108.30	}
136.49/108.30	module Maybe where {
136.49/108.30	import qualified FiniteMap;
136.49/108.30	import qualified Main;
136.49/108.30	import qualified Prelude;
136.49/108.30	}
136.49/108.30	module Main where {
136.49/108.30	import qualified FiniteMap;
136.49/108.30	import qualified Maybe;
136.49/108.30	import qualified Prelude;
136.49/108.30	}
136.62/108.34	EOF