87.17/59.55	MAYBE
89.76/60.25	proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
89.76/60.25	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
89.76/60.25	
89.76/60.25	
89.76/60.25	H-Termination with start terms of the given HASKELL could not be shown:
89.76/60.25	
89.76/60.25	(0) HASKELL
89.76/60.25	(1) LR [EQUIVALENT, 0 ms]
89.76/60.25	(2) HASKELL
89.76/60.25	(3) CR [EQUIVALENT, 0 ms]
89.76/60.25	(4) HASKELL
89.76/60.25	(5) IFR [EQUIVALENT, 0 ms]
89.76/60.25	(6) HASKELL
89.76/60.25	(7) BR [EQUIVALENT, 1 ms]
89.76/60.25	(8) HASKELL
89.76/60.25	(9) COR [EQUIVALENT, 0 ms]
89.76/60.25	(10) HASKELL
89.76/60.25	(11) LetRed [EQUIVALENT, 0 ms]
89.76/60.25	(12) HASKELL
89.76/60.25	(13) NumRed [SOUND, 7 ms]
89.76/60.25	(14) HASKELL
89.76/60.25	
89.76/60.25	
89.76/60.25	----------------------------------------
89.76/60.25	
89.76/60.25	(0)
89.76/60.25	Obligation:
89.76/60.25	mainModule Main 
89.76/60.25	module FiniteMap where {
89.76/60.25	import qualified Main;
89.76/60.25	import qualified Maybe;
89.76/60.25	import qualified Prelude;
89.76/60.25	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
89.76/60.25	
89.76/60.25	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
89.76/60.25	(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
89.76/60.25	}
89.76/60.25	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
89.76/60.25	addToFM fm key elt = addToFM_C (\old new ->new) fm key elt;
89.76/60.25	
89.76/60.25	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
89.76/60.25	addToFM_C combiner EmptyFM key elt = unitFM key elt;
89.76/60.25	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
89.76/60.25	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
89.76/60.25	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
89.76/60.25	
89.76/60.25	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
89.76/60.25	deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l;
89.76/60.25	deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
89.76/60.25	
89.76/60.25	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
89.76/60.25	deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r;
89.76/60.25	deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
89.76/60.25	
89.76/60.25	emptyFM :: FiniteMap b a;
89.76/60.25	emptyFM = EmptyFM;
89.76/60.25	
89.76/60.25	findMax :: FiniteMap b a  ->  (b,a);
89.76/60.25	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
89.76/60.25	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
89.76/60.25	
89.76/60.25	findMin :: FiniteMap a b  ->  (a,b);
89.76/60.25	findMin (Branch key elt _ EmptyFM _) = (key,elt);
89.76/60.25	findMin (Branch key elt _ fm_l _) = findMin fm_l;
89.76/60.25	
89.76/60.25	fmToList :: FiniteMap a b  ->  [(a,b)];
89.76/60.25	fmToList fm = foldFM (\key elt rest ->(key,elt) : rest) [] fm;
89.76/60.25	
89.76/60.25	foldFM :: (b  ->  a  ->  c  ->  c)  ->  c  ->  FiniteMap b a  ->  c;
89.76/60.25	foldFM k z EmptyFM = z;
89.76/60.25	foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;
89.76/60.25	
89.76/60.25	glueBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
89.76/60.25	glueBal EmptyFM fm2 = fm2;
89.76/60.25	glueBal fm1 EmptyFM = fm1;
89.76/60.25	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
89.76/60.25	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
89.76/60.25	mid_elt1 = (\(_,mid_elt1) ->mid_elt1) vv2;
89.76/60.25	mid_elt2 = (\(_,mid_elt2) ->mid_elt2) vv3;
89.76/60.25	mid_key1 = (\(mid_key1,_) ->mid_key1) vv2;
89.76/60.25	mid_key2 = (\(mid_key2,_) ->mid_key2) vv3;
89.76/60.25	vv2 = findMax fm1;
89.76/60.25	vv3 = findMin fm2;
89.76/60.25	 };
89.76/60.25	
89.76/60.25	glueVBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
89.76/60.25	glueVBal EmptyFM fm2 = fm2;
89.76/60.25	glueVBal fm1 EmptyFM = fm1;
89.76/60.25	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
89.76/60.25	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r)
89.76/60.25	 | otherwise = glueBal fm_l fm_r where { 
89.76/60.25	size_l = sizeFM fm_l;
89.76/60.25	size_r = sizeFM fm_r;
89.76/60.25	 };
89.76/60.25	
89.76/60.25	intersectFM_C :: Ord c => (b  ->  a  ->  d)  ->  FiniteMap c b  ->  FiniteMap c a  ->  FiniteMap c d;
89.76/60.25	intersectFM_C combiner fm1 EmptyFM = emptyFM;
89.76/60.25	intersectFM_C combiner EmptyFM fm2 = emptyFM;
89.76/60.25	intersectFM_C combiner fm1 (Branch split_key elt2 _ left right)  | Maybe.isJust maybe_elt1 = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right)
89.76/60.25	 | otherwise = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 
89.76/60.25	elt1 = (\(Just elt1) ->elt1) vv1;
89.76/60.25	gts = splitGT fm1 split_key;
89.76/60.25	lts = splitLT fm1 split_key;
89.76/60.25	maybe_elt1 = lookupFM fm1 split_key;
89.76/60.25	vv1 = maybe_elt1;
89.76/60.25	 };
89.76/60.25	
89.76/60.25	lookupFM :: Ord a => FiniteMap a b  ->  a  ->  Maybe b;
89.76/60.25	lookupFM EmptyFM key = Nothing;
89.76/60.25	lookupFM (Branch key elt _ fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
89.76/60.25	 | key_to_find > key = lookupFM fm_r key_to_find
89.76/60.25	 | otherwise = Just elt;
89.76/60.25	
89.76/60.25	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
89.76/60.25	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
89.76/60.25	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
89.76/60.25	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
89.76/60.25	 | otherwise -> double_L fm_L fm_R; 
89.76/60.25	 } 
89.76/60.25	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
89.76/60.25	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
89.76/60.25	 | otherwise -> double_R fm_L fm_R; 
89.76/60.25	 } 
89.76/60.25	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
89.76/60.25	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);
89.76/60.25	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);
89.76/60.25	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;
89.76/60.25	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);
89.76/60.25	size_l = sizeFM fm_L;
89.76/60.25	size_r = sizeFM fm_R;
89.76/60.25	 };
89.76/60.25	
89.76/60.25	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
89.76/60.25	mkBranch which key elt fm_l fm_r = let { 
89.76/60.25	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
89.76/60.25	} in result where { 
89.76/60.25	balance_ok = True;
89.76/60.25	left_ok = case fm_l of { 
89.76/60.25	EmptyFM-> True; 
89.76/60.25	Branch left_key _ _ _ _-> let { 
89.76/60.25	biggest_left_key = fst (findMax fm_l);
89.76/60.25	} in biggest_left_key < key; 
89.76/60.25	 } ;
89.76/60.25	left_size = sizeFM fm_l;
89.76/60.25	right_ok = case fm_r of { 
89.76/60.25	EmptyFM-> True; 
89.76/60.25	Branch right_key _ _ _ _-> let { 
89.76/60.25	smallest_right_key = fst (findMin fm_r);
89.76/60.25	} in key < smallest_right_key; 
89.76/60.25	 } ;
89.76/60.25	right_size = sizeFM fm_r;
89.76/60.25	unbox :: Int  ->  Int;
89.76/60.25	unbox x = x;
89.76/60.25	 };
89.76/60.25	
89.76/60.25	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
89.76/60.25	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
89.76/60.25	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
89.76/60.25	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
89.76/60.25	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
89.76/60.25	 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
89.76/60.25	size_l = sizeFM fm_l;
89.76/60.25	size_r = sizeFM fm_r;
89.76/60.25	 };
89.76/60.25	
89.76/60.25	sIZE_RATIO :: Int;
89.76/60.25	sIZE_RATIO = 5;
89.76/60.25	
89.76/60.25	sizeFM :: FiniteMap b a  ->  Int;
89.76/60.25	sizeFM EmptyFM = 0;
89.76/60.25	sizeFM (Branch _ _ size _ _) = size;
89.76/60.25	
89.76/60.25	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
89.76/60.25	splitGT EmptyFM split_key = emptyFM;
89.76/60.25	splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
89.76/60.25	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
89.76/60.25	 | otherwise = fm_r;
89.76/60.25	
89.76/60.25	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
89.76/60.25	splitLT EmptyFM split_key = emptyFM;
89.76/60.25	splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
89.76/60.25	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
89.76/60.25	 | otherwise = fm_l;
89.76/60.25	
89.76/60.25	unitFM :: b  ->  a  ->  FiniteMap b a;
89.76/60.25	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
89.76/60.25	
89.76/60.25	}
89.76/60.25	module Maybe where {
89.76/60.25	import qualified FiniteMap;
89.76/60.25	import qualified Main;
89.76/60.25	import qualified Prelude;
89.76/60.25	isJust :: Maybe a  ->  Bool;
89.76/60.25	isJust Nothing = False;
89.76/60.25	isJust _ = True;
89.76/60.25	
89.76/60.25	}
89.76/60.25	module Main where {
89.76/60.25	import qualified FiniteMap;
89.76/60.25	import qualified Maybe;
89.76/60.25	import qualified Prelude;
89.76/60.25	}
89.76/60.25	
89.76/60.25	----------------------------------------
89.76/60.25	
89.76/60.25	(1) LR (EQUIVALENT)
89.76/60.25	Lambda Reductions:
89.76/60.25	The following Lambda expression
89.76/60.25	"\oldnew->new"
89.76/60.25	is transformed to
89.76/60.25	"addToFM0 old new = new;
89.76/60.25	"
89.76/60.25	The following Lambda expression
89.76/60.25	"\(_,mid_elt2)->mid_elt2"
89.76/60.25	is transformed to
89.76/60.25	"mid_elt20 (_,mid_elt2) = mid_elt2;
89.76/60.27	"
89.76/60.27	The following Lambda expression
89.76/60.27	"\(mid_key2,_)->mid_key2"
89.76/60.27	is transformed to
89.76/60.27	"mid_key20 (mid_key2,_) = mid_key2;
89.76/60.27	"
89.76/60.27	The following Lambda expression
89.76/60.27	"\(mid_key1,_)->mid_key1"
89.76/60.27	is transformed to
89.76/60.27	"mid_key10 (mid_key1,_) = mid_key1;
89.76/60.27	"
89.76/60.27	The following Lambda expression
89.76/60.27	"\(_,mid_elt1)->mid_elt1"
89.76/60.27	is transformed to
89.76/60.27	"mid_elt10 (_,mid_elt1) = mid_elt1;
89.76/60.27	"
89.76/60.27	The following Lambda expression
89.76/60.27	"\keyeltrest->(key,elt) : rest"
89.76/60.27	is transformed to
89.76/60.27	"fmToList0 key elt rest = (key,elt) : rest;
89.76/60.27	"
89.76/60.27	The following Lambda expression
89.76/60.27	"\(Just elt1)->elt1"
89.76/60.27	is transformed to
89.76/60.27	"elt10 (Just elt1) = elt1;
89.76/60.27	"
89.76/60.27	
89.76/60.27	----------------------------------------
89.76/60.27	
89.76/60.27	(2)
89.76/60.27	Obligation:
89.76/60.27	mainModule Main 
89.76/60.27	module FiniteMap where {
89.76/60.27	import qualified Main;
89.76/60.27	import qualified Maybe;
89.76/60.27	import qualified Prelude;
89.76/60.27	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
89.76/60.27	
89.76/60.27	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
89.76/60.27	(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
89.76/60.27	}
89.76/60.27	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
89.76/60.27	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
89.76/60.27	
89.76/60.27	addToFM0 old new = new;
89.76/60.27	
89.76/60.27	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
89.76/60.27	addToFM_C combiner EmptyFM key elt = unitFM key elt;
89.76/60.27	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
89.76/60.27	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
89.76/60.27	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
89.76/60.27	
89.76/60.27	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
89.76/60.27	deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l;
89.76/60.27	deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
89.76/60.27	
89.76/60.27	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
89.76/60.27	deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r;
89.76/60.27	deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
89.76/60.27	
89.76/60.27	emptyFM :: FiniteMap a b;
89.76/60.27	emptyFM = EmptyFM;
89.76/60.27	
89.76/60.27	findMax :: FiniteMap b a  ->  (b,a);
89.76/60.27	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
89.76/60.27	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
89.76/60.27	
89.76/60.27	findMin :: FiniteMap a b  ->  (a,b);
89.76/60.27	findMin (Branch key elt _ EmptyFM _) = (key,elt);
89.76/60.27	findMin (Branch key elt _ fm_l _) = findMin fm_l;
89.76/60.27	
89.76/60.27	fmToList :: FiniteMap b a  ->  [(b,a)];
89.76/60.27	fmToList fm = foldFM fmToList0 [] fm;
89.76/60.27	
89.76/60.27	fmToList0 key elt rest = (key,elt) : rest;
89.76/60.27	
89.76/60.27	foldFM :: (b  ->  c  ->  a  ->  a)  ->  a  ->  FiniteMap b c  ->  a;
89.76/60.27	foldFM k z EmptyFM = z;
89.76/60.27	foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;
89.76/60.27	
89.76/60.27	glueBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
89.76/60.27	glueBal EmptyFM fm2 = fm2;
89.76/60.27	glueBal fm1 EmptyFM = fm1;
89.76/60.27	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
89.76/60.27	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
89.76/60.27	mid_elt1 = mid_elt10 vv2;
89.76/60.27	mid_elt10 (_,mid_elt1) = mid_elt1;
89.76/60.27	mid_elt2 = mid_elt20 vv3;
89.76/60.27	mid_elt20 (_,mid_elt2) = mid_elt2;
89.76/60.27	mid_key1 = mid_key10 vv2;
89.76/60.27	mid_key10 (mid_key1,_) = mid_key1;
89.76/60.27	mid_key2 = mid_key20 vv3;
89.76/60.27	mid_key20 (mid_key2,_) = mid_key2;
89.76/60.27	vv2 = findMax fm1;
89.76/60.27	vv3 = findMin fm2;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	glueVBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
89.76/60.27	glueVBal EmptyFM fm2 = fm2;
89.76/60.27	glueVBal fm1 EmptyFM = fm1;
89.76/60.27	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
89.76/60.27	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r)
89.76/60.27	 | otherwise = glueBal fm_l fm_r where { 
89.76/60.27	size_l = sizeFM fm_l;
89.76/60.27	size_r = sizeFM fm_r;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	intersectFM_C :: Ord a => (d  ->  b  ->  c)  ->  FiniteMap a d  ->  FiniteMap a b  ->  FiniteMap a c;
89.76/60.27	intersectFM_C combiner fm1 EmptyFM = emptyFM;
89.76/60.27	intersectFM_C combiner EmptyFM fm2 = emptyFM;
89.76/60.27	intersectFM_C combiner fm1 (Branch split_key elt2 _ left right)  | Maybe.isJust maybe_elt1 = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right)
89.76/60.27	 | otherwise = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 
89.76/60.27	elt1 = elt10 vv1;
89.76/60.27	elt10 (Just elt1) = elt1;
89.76/60.27	gts = splitGT fm1 split_key;
89.76/60.27	lts = splitLT fm1 split_key;
89.76/60.27	maybe_elt1 = lookupFM fm1 split_key;
89.76/60.27	vv1 = maybe_elt1;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
89.76/60.27	lookupFM EmptyFM key = Nothing;
89.76/60.27	lookupFM (Branch key elt _ fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
89.76/60.27	 | key_to_find > key = lookupFM fm_r key_to_find
89.76/60.27	 | otherwise = Just elt;
89.76/60.27	
89.76/60.27	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
89.76/60.27	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
89.76/60.27	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
89.76/60.27	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
89.76/60.27	 | otherwise -> double_L fm_L fm_R; 
89.76/60.27	 } 
89.76/60.27	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
89.76/60.27	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
89.76/60.27	 | otherwise -> double_R fm_L fm_R; 
89.76/60.27	 } 
89.76/60.27	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
89.76/60.27	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);
89.76/60.27	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);
89.76/60.27	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;
89.76/60.27	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);
89.76/60.27	size_l = sizeFM fm_L;
89.76/60.27	size_r = sizeFM fm_R;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
89.76/60.27	mkBranch which key elt fm_l fm_r = let { 
89.76/60.27	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
89.76/60.27	} in result where { 
89.76/60.27	balance_ok = True;
89.76/60.27	left_ok = case fm_l of { 
89.76/60.27	EmptyFM-> True; 
89.76/60.27	Branch left_key _ _ _ _-> let { 
89.76/60.27	biggest_left_key = fst (findMax fm_l);
89.76/60.27	} in biggest_left_key < key; 
89.76/60.27	 } ;
89.76/60.27	left_size = sizeFM fm_l;
89.76/60.27	right_ok = case fm_r of { 
89.76/60.27	EmptyFM-> True; 
89.76/60.27	Branch right_key _ _ _ _-> let { 
89.76/60.27	smallest_right_key = fst (findMin fm_r);
89.76/60.27	} in key < smallest_right_key; 
89.76/60.27	 } ;
89.76/60.27	right_size = sizeFM fm_r;
89.76/60.27	unbox :: Int  ->  Int;
89.76/60.27	unbox x = x;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
89.76/60.27	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
89.76/60.27	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
89.76/60.27	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
89.76/60.27	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
89.76/60.27	 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
89.76/60.27	size_l = sizeFM fm_l;
89.76/60.27	size_r = sizeFM fm_r;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	sIZE_RATIO :: Int;
89.76/60.27	sIZE_RATIO = 5;
89.76/60.27	
89.76/60.27	sizeFM :: FiniteMap b a  ->  Int;
89.76/60.27	sizeFM EmptyFM = 0;
89.76/60.27	sizeFM (Branch _ _ size _ _) = size;
89.76/60.27	
89.76/60.27	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
89.76/60.27	splitGT EmptyFM split_key = emptyFM;
89.76/60.27	splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
89.76/60.27	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
89.76/60.27	 | otherwise = fm_r;
89.76/60.27	
89.76/60.27	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
89.76/60.27	splitLT EmptyFM split_key = emptyFM;
89.76/60.27	splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
89.76/60.27	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
89.76/60.27	 | otherwise = fm_l;
89.76/60.27	
89.76/60.27	unitFM :: a  ->  b  ->  FiniteMap a b;
89.76/60.27	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
89.76/60.27	
89.76/60.27	}
89.76/60.27	module Maybe where {
89.76/60.27	import qualified FiniteMap;
89.76/60.27	import qualified Main;
89.76/60.27	import qualified Prelude;
89.76/60.27	isJust :: Maybe a  ->  Bool;
89.76/60.27	isJust Nothing = False;
89.76/60.27	isJust _ = True;
89.76/60.27	
89.76/60.27	}
89.76/60.27	module Main where {
89.76/60.27	import qualified FiniteMap;
89.76/60.27	import qualified Maybe;
89.76/60.27	import qualified Prelude;
89.76/60.27	}
89.76/60.27	
89.76/60.27	----------------------------------------
89.76/60.27	
89.76/60.27	(3) CR (EQUIVALENT)
89.76/60.27	Case Reductions:
89.76/60.27	The following Case expression
89.76/60.27	"case compare x y of {
89.76/60.27	EQ  -> o;
89.76/60.27	LT  -> LT;
89.76/60.27	GT  -> GT}
89.76/60.27	"
89.76/60.27	is transformed to
89.76/60.27	"primCompAux0 o EQ = o;
89.76/60.27	primCompAux0 o LT = LT;
89.76/60.27	primCompAux0 o GT = GT;
89.76/60.27	"
89.76/60.27	The following Case expression
89.76/60.27	"case fm_r of {
89.76/60.27	EmptyFM  -> True;
89.76/60.27	Branch right_key _ _ _ _  -> let {
89.76/60.27	smallest_right_key  = fst (findMin fm_r);
89.76/60.27	} in key < smallest_right_key}
89.76/60.27	"
89.76/60.27	is transformed to
89.76/60.27	"right_ok0 fm_r key EmptyFM = True;
89.76/60.27	right_ok0 fm_r key (Branch right_key _ _ _ _) = let {
89.76/60.27	smallest_right_key  = fst (findMin fm_r);
89.76/60.27	} in key < smallest_right_key;
89.76/60.27	"
89.76/60.27	The following Case expression
89.76/60.27	"case fm_l of {
89.76/60.27	EmptyFM  -> True;
89.76/60.27	Branch left_key _ _ _ _  -> let {
89.76/60.27	biggest_left_key  = fst (findMax fm_l);
89.76/60.27	} in biggest_left_key < key}
89.76/60.27	"
89.76/60.27	is transformed to
89.76/60.27	"left_ok0 fm_l key EmptyFM = True;
89.76/60.27	left_ok0 fm_l key (Branch left_key _ _ _ _) = let {
89.76/60.27	biggest_left_key  = fst (findMax fm_l);
89.76/60.27	} in biggest_left_key < key;
89.76/60.27	"
89.76/60.27	The following Case expression
89.76/60.27	"case fm_R of {
89.76/60.27	Branch _ _ _ fm_rl fm_rr |sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R}
89.76/60.27	"
89.76/60.27	is transformed to
89.76/60.27	"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;
89.76/60.27	"
89.76/60.27	The following Case expression
89.76/60.27	"case fm_L of {
89.76/60.27	Branch _ _ _ fm_ll fm_lr |sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R}
89.76/60.27	"
89.76/60.27	is transformed to
89.76/60.27	"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;
89.76/60.27	"
89.76/60.27	
89.76/60.27	----------------------------------------
89.76/60.27	
89.76/60.27	(4)
89.76/60.27	Obligation:
89.76/60.27	mainModule Main 
89.76/60.27	module FiniteMap where {
89.76/60.27	import qualified Main;
89.76/60.27	import qualified Maybe;
89.76/60.27	import qualified Prelude;
89.76/60.27	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
89.76/60.27	
89.76/60.27	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
89.76/60.27	(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
89.76/60.27	}
89.76/60.27	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
89.76/60.27	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
89.76/60.27	
89.76/60.27	addToFM0 old new = new;
89.76/60.27	
89.76/60.27	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
89.76/60.27	addToFM_C combiner EmptyFM key elt = unitFM key elt;
89.76/60.27	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
89.76/60.27	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
89.76/60.27	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
89.76/60.27	
89.76/60.27	deleteMax :: Ord b => FiniteMap b a  ->  FiniteMap b a;
89.76/60.27	deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l;
89.76/60.27	deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
89.76/60.27	
89.76/60.27	deleteMin :: Ord a => FiniteMap a b  ->  FiniteMap a b;
89.76/60.27	deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r;
89.76/60.27	deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
89.76/60.27	
89.76/60.27	emptyFM :: FiniteMap a b;
89.76/60.27	emptyFM = EmptyFM;
89.76/60.27	
89.76/60.27	findMax :: FiniteMap a b  ->  (a,b);
89.76/60.27	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
89.76/60.27	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
89.76/60.27	
89.76/60.27	findMin :: FiniteMap a b  ->  (a,b);
89.76/60.27	findMin (Branch key elt _ EmptyFM _) = (key,elt);
89.76/60.27	findMin (Branch key elt _ fm_l _) = findMin fm_l;
89.76/60.27	
89.76/60.27	fmToList :: FiniteMap b a  ->  [(b,a)];
89.76/60.27	fmToList fm = foldFM fmToList0 [] fm;
89.76/60.27	
89.76/60.27	fmToList0 key elt rest = (key,elt) : rest;
89.76/60.27	
89.76/60.27	foldFM :: (b  ->  c  ->  a  ->  a)  ->  a  ->  FiniteMap b c  ->  a;
89.76/60.27	foldFM k z EmptyFM = z;
89.76/60.27	foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;
89.76/60.27	
89.76/60.27	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
89.76/60.27	glueBal EmptyFM fm2 = fm2;
89.76/60.27	glueBal fm1 EmptyFM = fm1;
89.76/60.27	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
89.76/60.27	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
89.76/60.27	mid_elt1 = mid_elt10 vv2;
89.76/60.27	mid_elt10 (_,mid_elt1) = mid_elt1;
89.76/60.27	mid_elt2 = mid_elt20 vv3;
89.76/60.27	mid_elt20 (_,mid_elt2) = mid_elt2;
89.76/60.27	mid_key1 = mid_key10 vv2;
89.76/60.27	mid_key10 (mid_key1,_) = mid_key1;
89.76/60.27	mid_key2 = mid_key20 vv3;
89.76/60.27	mid_key20 (mid_key2,_) = mid_key2;
89.76/60.27	vv2 = findMax fm1;
89.76/60.27	vv3 = findMin fm2;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	glueVBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
89.76/60.27	glueVBal EmptyFM fm2 = fm2;
89.76/60.27	glueVBal fm1 EmptyFM = fm1;
89.76/60.27	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
89.76/60.27	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r)
89.76/60.27	 | otherwise = glueBal fm_l fm_r where { 
89.76/60.27	size_l = sizeFM fm_l;
89.76/60.27	size_r = sizeFM fm_r;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	intersectFM_C :: Ord a => (b  ->  c  ->  d)  ->  FiniteMap a b  ->  FiniteMap a c  ->  FiniteMap a d;
89.76/60.27	intersectFM_C combiner fm1 EmptyFM = emptyFM;
89.76/60.27	intersectFM_C combiner EmptyFM fm2 = emptyFM;
89.76/60.27	intersectFM_C combiner fm1 (Branch split_key elt2 _ left right)  | Maybe.isJust maybe_elt1 = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right)
89.76/60.27	 | otherwise = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 
89.76/60.27	elt1 = elt10 vv1;
89.76/60.27	elt10 (Just elt1) = elt1;
89.76/60.27	gts = splitGT fm1 split_key;
89.76/60.27	lts = splitLT fm1 split_key;
89.76/60.27	maybe_elt1 = lookupFM fm1 split_key;
89.76/60.27	vv1 = maybe_elt1;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
89.76/60.27	lookupFM EmptyFM key = Nothing;
89.76/60.27	lookupFM (Branch key elt _ fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
89.76/60.27	 | key_to_find > key = lookupFM fm_r key_to_find
89.76/60.27	 | otherwise = Just elt;
89.76/60.27	
89.76/60.27	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
89.76/60.27	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
89.76/60.27	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
89.76/60.27	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
89.76/60.27	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
89.76/60.27	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);
89.76/60.27	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);
89.76/60.27	mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
89.76/60.27	 | otherwise = double_L fm_L fm_R;
89.76/60.27	mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
89.76/60.27	 | otherwise = double_R fm_L fm_R;
89.76/60.27	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;
89.76/60.27	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);
89.76/60.27	size_l = sizeFM fm_L;
89.76/60.27	size_r = sizeFM fm_R;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
89.76/60.27	mkBranch which key elt fm_l fm_r = let { 
89.76/60.27	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
89.76/60.27	} in result where { 
89.76/60.27	balance_ok = True;
89.76/60.27	left_ok = left_ok0 fm_l key fm_l;
89.76/60.27	left_ok0 fm_l key EmptyFM = True;
89.76/60.27	left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 
89.76/60.27	biggest_left_key = fst (findMax fm_l);
89.76/60.27	} in biggest_left_key < key;
89.76/60.27	left_size = sizeFM fm_l;
89.76/60.27	right_ok = right_ok0 fm_r key fm_r;
89.76/60.27	right_ok0 fm_r key EmptyFM = True;
89.76/60.27	right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 
89.76/60.27	smallest_right_key = fst (findMin fm_r);
89.76/60.27	} in key < smallest_right_key;
89.76/60.27	right_size = sizeFM fm_r;
89.76/60.27	unbox :: Int  ->  Int;
89.76/60.27	unbox x = x;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
89.76/60.27	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
89.76/60.27	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
89.76/60.27	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
89.76/60.27	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
89.76/60.27	 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
89.76/60.27	size_l = sizeFM fm_l;
89.76/60.27	size_r = sizeFM fm_r;
89.76/60.27	 };
89.76/60.27	
89.76/60.27	sIZE_RATIO :: Int;
89.76/60.27	sIZE_RATIO = 5;
89.76/60.27	
89.76/60.27	sizeFM :: FiniteMap b a  ->  Int;
89.76/60.27	sizeFM EmptyFM = 0;
89.76/60.27	sizeFM (Branch _ _ size _ _) = size;
90.91/60.57	
90.91/60.57	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
90.91/60.57	splitGT EmptyFM split_key = emptyFM;
90.91/60.57	splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
90.91/60.57	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
90.91/60.57	 | otherwise = fm_r;
90.91/60.57	
90.91/60.57	splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
90.91/60.57	splitLT EmptyFM split_key = emptyFM;
90.91/60.57	splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
90.91/60.57	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
90.91/60.57	 | otherwise = fm_l;
90.91/60.57	
90.91/60.57	unitFM :: a  ->  b  ->  FiniteMap a b;
90.91/60.57	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
90.91/60.57	
90.91/60.57	}
90.91/60.57	module Maybe where {
90.91/60.57	import qualified FiniteMap;
90.91/60.57	import qualified Main;
90.91/60.57	import qualified Prelude;
90.91/60.57	isJust :: Maybe a  ->  Bool;
90.91/60.57	isJust Nothing = False;
90.91/60.57	isJust _ = True;
90.91/60.57	
90.91/60.57	}
90.91/60.57	module Main where {
90.91/60.57	import qualified FiniteMap;
90.91/60.57	import qualified Maybe;
90.91/60.57	import qualified Prelude;
90.91/60.57	}
90.91/60.57	
90.91/60.57	----------------------------------------
90.91/60.57	
90.91/60.57	(5) IFR (EQUIVALENT)
90.91/60.57	If Reductions:
90.91/60.57	The following If expression
90.91/60.57	"if primGEqNatS x y then Succ (primDivNatS (primMinusNatS x y) (Succ y)) else Zero"
90.91/60.57	is transformed to
90.91/60.57	"primDivNatS0 x y True = Succ (primDivNatS (primMinusNatS x y) (Succ y));
90.91/60.57	primDivNatS0 x y False = Zero;
90.91/60.57	"
90.91/60.57	The following If expression
90.91/60.57	"if primGEqNatS x y then primModNatS (primMinusNatS x y) (Succ y) else Succ x"
90.91/60.57	is transformed to
90.91/60.57	"primModNatS0 x y True = primModNatS (primMinusNatS x y) (Succ y);
90.91/60.57	primModNatS0 x y False = Succ x;
90.91/60.57	"
90.91/60.57	
90.91/60.57	----------------------------------------
90.91/60.57	
90.91/60.57	(6)
90.91/60.57	Obligation:
90.91/60.57	mainModule Main 
90.91/60.57	module FiniteMap where {
90.91/60.57	import qualified Main;
90.91/60.57	import qualified Maybe;
90.91/60.57	import qualified Prelude;
90.91/60.57	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
90.91/60.57	
90.91/60.57	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
90.91/60.57	(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
90.91/60.57	}
90.91/60.57	addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
90.91/60.57	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
90.91/60.57	
90.91/60.57	addToFM0 old new = new;
90.91/60.57	
90.91/60.57	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
90.91/60.57	addToFM_C combiner EmptyFM key elt = unitFM key elt;
90.91/60.57	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
90.91/60.57	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
90.91/60.57	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
90.91/60.57	
90.91/60.57	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
90.91/60.57	deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l;
90.91/60.57	deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
90.91/60.57	
90.91/60.57	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
90.91/60.57	deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r;
90.91/60.57	deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
90.91/60.57	
90.91/60.57	emptyFM :: FiniteMap b a;
90.91/60.57	emptyFM = EmptyFM;
90.91/60.57	
90.91/60.57	findMax :: FiniteMap a b  ->  (a,b);
90.91/60.57	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
90.91/60.57	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
90.91/60.57	
90.91/60.57	findMin :: FiniteMap a b  ->  (a,b);
90.91/60.57	findMin (Branch key elt _ EmptyFM _) = (key,elt);
90.91/60.57	findMin (Branch key elt _ fm_l _) = findMin fm_l;
90.91/60.57	
90.91/60.57	fmToList :: FiniteMap a b  ->  [(a,b)];
90.91/60.57	fmToList fm = foldFM fmToList0 [] fm;
90.91/60.57	
90.91/60.57	fmToList0 key elt rest = (key,elt) : rest;
90.91/60.57	
90.91/60.57	foldFM :: (a  ->  c  ->  b  ->  b)  ->  b  ->  FiniteMap a c  ->  b;
90.91/60.57	foldFM k z EmptyFM = z;
90.91/60.57	foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;
90.91/60.57	
90.91/60.57	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
90.91/60.57	glueBal EmptyFM fm2 = fm2;
90.91/60.57	glueBal fm1 EmptyFM = fm1;
90.91/60.57	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
90.91/60.57	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
90.91/60.57	mid_elt1 = mid_elt10 vv2;
90.91/60.57	mid_elt10 (_,mid_elt1) = mid_elt1;
90.91/60.57	mid_elt2 = mid_elt20 vv3;
90.91/60.57	mid_elt20 (_,mid_elt2) = mid_elt2;
90.91/60.57	mid_key1 = mid_key10 vv2;
90.91/60.57	mid_key10 (mid_key1,_) = mid_key1;
90.91/60.57	mid_key2 = mid_key20 vv3;
90.91/60.57	mid_key20 (mid_key2,_) = mid_key2;
90.91/60.57	vv2 = findMax fm1;
90.91/60.57	vv3 = findMin fm2;
90.91/60.57	 };
90.91/60.57	
90.91/60.57	glueVBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
90.91/60.57	glueVBal EmptyFM fm2 = fm2;
90.91/60.57	glueVBal fm1 EmptyFM = fm1;
90.91/60.57	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
90.91/60.57	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r)
90.91/60.57	 | otherwise = glueBal fm_l fm_r where { 
90.91/60.57	size_l = sizeFM fm_l;
90.91/60.57	size_r = sizeFM fm_r;
90.91/60.57	 };
90.91/60.57	
90.91/60.57	intersectFM_C :: Ord d => (c  ->  b  ->  a)  ->  FiniteMap d c  ->  FiniteMap d b  ->  FiniteMap d a;
90.91/60.57	intersectFM_C combiner fm1 EmptyFM = emptyFM;
90.91/60.57	intersectFM_C combiner EmptyFM fm2 = emptyFM;
90.91/60.57	intersectFM_C combiner fm1 (Branch split_key elt2 _ left right)  | Maybe.isJust maybe_elt1 = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right)
90.91/60.57	 | otherwise = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 
90.91/60.57	elt1 = elt10 vv1;
90.91/60.57	elt10 (Just elt1) = elt1;
90.91/60.57	gts = splitGT fm1 split_key;
90.91/60.57	lts = splitLT fm1 split_key;
90.91/60.57	maybe_elt1 = lookupFM fm1 split_key;
90.91/60.57	vv1 = maybe_elt1;
90.91/60.57	 };
90.91/60.57	
90.91/60.57	lookupFM :: Ord a => FiniteMap a b  ->  a  ->  Maybe b;
90.91/60.57	lookupFM EmptyFM key = Nothing;
90.91/60.57	lookupFM (Branch key elt _ fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
90.91/60.57	 | key_to_find > key = lookupFM fm_r key_to_find
90.91/60.57	 | otherwise = Just elt;
90.91/60.57	
90.91/60.57	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
90.91/60.57	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
90.91/60.57	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
90.91/60.57	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
90.91/60.57	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
90.91/60.57	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);
90.91/60.57	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);
90.91/60.57	mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
90.91/60.57	 | otherwise = double_L fm_L fm_R;
90.91/60.57	mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
90.91/60.57	 | otherwise = double_R fm_L fm_R;
90.91/60.57	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;
90.91/60.57	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);
90.91/60.57	size_l = sizeFM fm_L;
90.91/60.57	size_r = sizeFM fm_R;
90.91/60.57	 };
90.91/60.57	
90.91/60.57	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
90.91/60.57	mkBranch which key elt fm_l fm_r = let { 
90.91/60.57	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
90.91/60.57	} in result where { 
90.91/60.57	balance_ok = True;
90.91/60.57	left_ok = left_ok0 fm_l key fm_l;
90.91/60.57	left_ok0 fm_l key EmptyFM = True;
90.91/60.57	left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 
90.91/60.57	biggest_left_key = fst (findMax fm_l);
90.91/60.57	} in biggest_left_key < key;
90.91/60.57	left_size = sizeFM fm_l;
90.91/60.57	right_ok = right_ok0 fm_r key fm_r;
90.91/60.57	right_ok0 fm_r key EmptyFM = True;
90.91/60.57	right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 
90.91/60.57	smallest_right_key = fst (findMin fm_r);
90.91/60.57	} in key < smallest_right_key;
90.91/60.57	right_size = sizeFM fm_r;
90.91/60.57	unbox :: Int  ->  Int;
90.91/60.57	unbox x = x;
90.91/60.57	 };
90.91/60.57	
90.91/60.57	mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
90.91/60.57	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
90.91/60.57	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
90.91/60.57	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
90.91/60.57	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
90.91/60.57	 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
90.91/60.57	size_l = sizeFM fm_l;
90.91/60.57	size_r = sizeFM fm_r;
90.91/60.57	 };
90.91/60.57	
90.91/60.57	sIZE_RATIO :: Int;
90.91/60.57	sIZE_RATIO = 5;
90.91/60.57	
90.91/60.57	sizeFM :: FiniteMap b a  ->  Int;
90.91/60.57	sizeFM EmptyFM = 0;
90.91/60.57	sizeFM (Branch _ _ size _ _) = size;
90.91/60.57	
90.91/60.57	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
90.91/60.57	splitGT EmptyFM split_key = emptyFM;
90.91/60.57	splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
90.91/60.57	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
90.91/60.57	 | otherwise = fm_r;
90.91/60.57	
90.91/60.57	splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
90.91/60.57	splitLT EmptyFM split_key = emptyFM;
90.91/60.57	splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
90.91/60.57	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
90.91/60.57	 | otherwise = fm_l;
90.91/60.57	
90.91/60.57	unitFM :: a  ->  b  ->  FiniteMap a b;
90.91/60.57	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
90.91/60.57	
90.91/60.57	}
90.91/60.57	module Maybe where {
90.91/60.57	import qualified FiniteMap;
90.91/60.57	import qualified Main;
90.91/60.57	import qualified Prelude;
90.91/60.57	isJust :: Maybe a  ->  Bool;
90.91/60.57	isJust Nothing = False;
90.91/60.57	isJust _ = True;
90.91/60.57	
90.91/60.57	}
90.91/60.57	module Main where {
90.91/60.57	import qualified FiniteMap;
90.91/60.57	import qualified Maybe;
90.91/60.57	import qualified Prelude;
90.91/60.57	}
90.91/60.57	
90.91/60.57	----------------------------------------
90.91/60.57	
90.91/60.57	(7) BR (EQUIVALENT)
90.91/60.57	Replaced joker patterns by fresh variables and removed binding patterns.
90.91/60.57	
90.91/60.57	Binding Reductions:
90.91/60.57	The bind variable of the following binding Pattern
90.91/60.57	"fm_l@(Branch vuu vuv vuw vux vuy)"
90.91/60.57	is replaced by the following term
90.91/60.57	"Branch vuu vuv vuw vux vuy"
90.91/60.57	The bind variable of the following binding Pattern
90.91/60.57	"fm_r@(Branch vvu vvv vvw vvx vvy)"
90.91/60.57	is replaced by the following term
90.91/60.57	"Branch vvu vvv vvw vvx vvy"
90.91/60.57	The bind variable of the following binding Pattern
90.91/60.57	"fm_l@(Branch wvw wvx wvy wvz wwu)"
90.91/60.57	is replaced by the following term
90.91/60.57	"Branch wvw wvx wvy wvz wwu"
90.91/60.57	The bind variable of the following binding Pattern
90.91/60.57	"fm_r@(Branch www wwx wwy wwz wxu)"
90.91/60.57	is replaced by the following term
90.91/60.57	"Branch www wwx wwy wwz wxu"
90.91/60.57	
90.91/60.57	----------------------------------------
90.91/60.57	
90.91/60.57	(8)
90.91/60.57	Obligation:
90.91/60.57	mainModule Main 
90.91/60.57	module FiniteMap where {
90.91/60.57	import qualified Main;
90.91/60.57	import qualified Maybe;
90.91/60.57	import qualified Prelude;
90.91/60.57	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
90.91/60.57	
90.91/60.57	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
90.91/60.57	(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
90.91/60.57	}
90.91/60.57	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
90.91/60.57	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
90.91/60.57	
90.91/60.57	addToFM0 old new = new;
90.91/60.57	
90.91/60.57	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
90.91/60.57	addToFM_C combiner EmptyFM key elt = unitFM key elt;
90.91/60.57	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
90.91/60.57	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
90.91/60.57	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
90.91/60.57	
90.91/60.57	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
90.91/60.57	deleteMax (Branch key elt vvz fm_l EmptyFM) = fm_l;
90.91/60.57	deleteMax (Branch key elt vwu fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
90.91/60.57	
90.91/60.57	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
90.91/60.57	deleteMin (Branch key elt wyv EmptyFM fm_r) = fm_r;
90.91/60.57	deleteMin (Branch key elt wyw fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
90.91/60.57	
90.91/60.57	emptyFM :: FiniteMap b a;
90.91/60.57	emptyFM = EmptyFM;
90.91/60.57	
90.91/60.57	findMax :: FiniteMap b a  ->  (b,a);
90.91/60.57	findMax (Branch key elt vxz vyu EmptyFM) = (key,elt);
90.91/60.57	findMax (Branch key elt vyv vyw fm_r) = findMax fm_r;
90.91/60.57	
90.91/60.57	findMin :: FiniteMap a b  ->  (a,b);
90.91/60.57	findMin (Branch key elt wyy EmptyFM wyz) = (key,elt);
90.91/60.57	findMin (Branch key elt wzu fm_l wzv) = findMin fm_l;
90.91/60.57	
90.91/60.57	fmToList :: FiniteMap b a  ->  [(b,a)];
90.91/60.57	fmToList fm = foldFM fmToList0 [] fm;
90.91/60.57	
90.91/60.57	fmToList0 key elt rest = (key,elt) : rest;
90.91/60.57	
90.91/60.57	foldFM :: (c  ->  b  ->  a  ->  a)  ->  a  ->  FiniteMap c b  ->  a;
90.91/60.57	foldFM k z EmptyFM = z;
90.91/60.57	foldFM k z (Branch key elt wxv fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;
90.91/60.57	
90.91/60.57	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
90.91/60.57	glueBal EmptyFM fm2 = fm2;
90.91/60.57	glueBal fm1 EmptyFM = fm1;
90.91/60.57	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
90.91/60.57	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
90.91/60.57	mid_elt1 = mid_elt10 vv2;
90.91/60.57	mid_elt10 (wuy,mid_elt1) = mid_elt1;
90.91/60.57	mid_elt2 = mid_elt20 vv3;
90.91/60.57	mid_elt20 (wux,mid_elt2) = mid_elt2;
90.91/60.57	mid_key1 = mid_key10 vv2;
90.91/60.57	mid_key10 (mid_key1,wuz) = mid_key1;
90.91/60.57	mid_key2 = mid_key20 vv3;
90.91/60.57	mid_key20 (mid_key2,wvu) = mid_key2;
90.91/60.57	vv2 = findMax fm1;
90.91/60.57	vv3 = findMin fm2;
90.91/60.57	 };
90.91/60.57	
90.91/60.57	glueVBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
90.91/60.57	glueVBal EmptyFM fm2 = fm2;
90.91/60.57	glueVBal fm1 EmptyFM = fm1;
90.91/60.57	glueVBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu)  | sIZE_RATIO * size_l < size_r = mkBalBranch www wwx (glueVBal (Branch wvw wvx wvy wvz wwu) wwz) wxu
90.91/60.57	 | sIZE_RATIO * size_r < size_l = mkBalBranch wvw wvx wvz (glueVBal wwu (Branch www wwx wwy wwz wxu))
90.91/60.57	 | otherwise = glueBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu) where { 
90.91/60.57	size_l = sizeFM (Branch wvw wvx wvy wvz wwu);
90.91/60.57	size_r = sizeFM (Branch www wwx wwy wwz wxu);
90.91/60.57	 };
90.91/60.57	
90.91/60.57	intersectFM_C :: Ord a => (c  ->  d  ->  b)  ->  FiniteMap a c  ->  FiniteMap a d  ->  FiniteMap a b;
90.91/60.57	intersectFM_C combiner fm1 EmptyFM = emptyFM;
90.91/60.57	intersectFM_C combiner EmptyFM fm2 = emptyFM;
90.91/60.57	intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right)  | Maybe.isJust maybe_elt1 = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right)
90.91/60.57	 | otherwise = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 
90.91/60.57	elt1 = elt10 vv1;
90.91/60.57	elt10 (Just elt1) = elt1;
90.91/60.57	gts = splitGT fm1 split_key;
90.91/60.57	lts = splitLT fm1 split_key;
90.91/60.57	maybe_elt1 = lookupFM fm1 split_key;
90.91/60.57	vv1 = maybe_elt1;
90.91/60.57	 };
90.91/60.57	
90.91/60.57	lookupFM :: Ord a => FiniteMap a b  ->  a  ->  Maybe b;
90.91/60.57	lookupFM EmptyFM key = Nothing;
90.91/60.57	lookupFM (Branch key elt wyu fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
90.91/60.57	 | key_to_find > key = lookupFM fm_r key_to_find
90.91/60.57	 | otherwise = Just elt;
90.91/60.57	
90.91/60.57	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
90.91/60.57	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
90.91/60.57	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
90.91/60.57	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
90.91/60.57	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
90.91/60.57	double_L fm_l (Branch key_r elt_r vzx (Branch key_rl elt_rl vzy 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);
90.91/60.57	double_R (Branch key_l elt_l vyy fm_ll (Branch key_lr elt_lr vyz 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);
90.91/60.57	mkBalBranch0 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
90.91/60.57	 | otherwise = double_L fm_L fm_R;
90.91/60.57	mkBalBranch1 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
90.91/60.57	 | otherwise = double_R fm_L fm_R;
90.91/60.57	single_L fm_l (Branch key_r elt_r wuw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
90.91/60.57	single_R (Branch key_l elt_l vyx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
90.91/60.57	size_l = sizeFM fm_L;
90.91/60.57	size_r = sizeFM fm_R;
90.91/60.57	 };
90.91/60.57	
90.91/60.57	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
90.91/60.57	mkBranch which key elt fm_l fm_r = let { 
90.91/60.57	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
90.91/60.57	} in result where { 
90.91/60.57	balance_ok = True;
90.91/60.57	left_ok = left_ok0 fm_l key fm_l;
90.91/60.57	left_ok0 fm_l key EmptyFM = True;
90.91/60.57	left_ok0 fm_l key (Branch left_key vwx vwy vwz vxu) = let { 
90.91/60.57	biggest_left_key = fst (findMax fm_l);
90.91/60.57	} in biggest_left_key < key;
90.91/60.57	left_size = sizeFM fm_l;
90.91/60.57	right_ok = right_ok0 fm_r key fm_r;
90.91/60.57	right_ok0 fm_r key EmptyFM = True;
90.91/60.57	right_ok0 fm_r key (Branch right_key vxv vxw vxx vxy) = let { 
90.91/60.57	smallest_right_key = fst (findMin fm_r);
90.91/60.57	} in key < smallest_right_key;
90.91/60.57	right_size = sizeFM fm_r;
90.91/60.57	unbox :: Int  ->  Int;
90.91/60.57	unbox x = x;
90.91/60.57	 };
90.91/60.57	
90.91/60.57	mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
90.91/60.57	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
90.91/60.57	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
90.91/60.57	mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy)  | sIZE_RATIO * size_l < size_r = mkBalBranch vvu vvv (mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) vvx) vvy
90.91/60.57	 | sIZE_RATIO * size_r < size_l = mkBalBranch vuu vuv vux (mkVBalBranch key elt vuy (Branch vvu vvv vvw vvx vvy))
90.91/60.57	 | otherwise = mkBranch 13 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy) where { 
90.91/60.57	size_l = sizeFM (Branch vuu vuv vuw vux vuy);
90.91/60.57	size_r = sizeFM (Branch vvu vvv vvw vvx vvy);
90.91/60.57	 };
90.91/60.57	
90.91/60.57	sIZE_RATIO :: Int;
90.91/60.57	sIZE_RATIO = 5;
90.91/60.57	
90.91/60.57	sizeFM :: FiniteMap b a  ->  Int;
90.91/60.57	sizeFM EmptyFM = 0;
90.91/60.57	sizeFM (Branch wxw wxx size wxy wxz) = size;
90.91/60.57	
90.91/60.57	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
90.91/60.57	splitGT EmptyFM split_key = emptyFM;
90.91/60.57	splitGT (Branch key elt vwv fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
90.91/60.57	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
90.91/60.57	 | otherwise = fm_r;
90.91/60.57	
90.91/60.57	splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
90.91/60.57	splitLT EmptyFM split_key = emptyFM;
90.91/60.57	splitLT (Branch key elt vww fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
90.91/60.57	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
90.91/60.57	 | otherwise = fm_l;
90.91/60.57	
90.91/60.57	unitFM :: b  ->  a  ->  FiniteMap b a;
90.91/60.57	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
90.91/60.57	
90.91/60.57	}
90.91/60.57	module Maybe where {
90.91/60.57	import qualified FiniteMap;
90.91/60.57	import qualified Main;
90.91/60.57	import qualified Prelude;
90.91/60.57	isJust :: Maybe a  ->  Bool;
90.91/60.57	isJust Nothing = False;
90.91/60.57	isJust wzw = True;
90.91/60.57	
90.91/60.57	}
90.91/60.57	module Main where {
90.91/60.57	import qualified FiniteMap;
90.91/60.57	import qualified Maybe;
90.91/60.57	import qualified Prelude;
90.91/60.57	}
90.91/60.57	
90.91/60.57	----------------------------------------
90.91/60.57	
90.91/60.57	(9) COR (EQUIVALENT)
90.91/60.57	Cond Reductions:
90.91/60.57	The following Function with conditions
90.91/60.57	"compare x y|x == yEQ|x <= yLT|otherwiseGT;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"compare x y = compare3 x y;
90.91/60.57	"
90.91/60.57	"compare0 x y True = GT;
90.91/60.57	"
90.91/60.57	"compare1 x y True = LT;
90.91/60.57	compare1 x y False = compare0 x y otherwise;
90.91/60.57	"
90.91/60.57	"compare2 x y True = EQ;
90.91/60.57	compare2 x y False = compare1 x y (x <= y);
90.91/60.57	"
90.91/60.57	"compare3 x y = compare2 x y (x == y);
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"absReal x|x >= 0x|otherwise`negate` x;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"absReal x = absReal2 x;
90.91/60.57	"
90.91/60.57	"absReal1 x True = x;
90.91/60.57	absReal1 x False = absReal0 x otherwise;
90.91/60.57	"
90.91/60.57	"absReal0 x True = `negate` x;
90.91/60.57	"
90.91/60.57	"absReal2 x = absReal1 x (x >= 0);
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"gcd' x 0 = x;
90.91/60.57	gcd' x y = gcd' y (x `rem` y);
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"gcd' x wzx = gcd'2 x wzx;
90.91/60.57	gcd' x y = gcd'0 x y;
90.91/60.57	"
90.91/60.57	"gcd'0 x y = gcd' y (x `rem` y);
90.91/60.57	"
90.91/60.57	"gcd'1 True x wzx = x;
90.91/60.57	gcd'1 wzy wzz xuu = gcd'0 wzz xuu;
90.91/60.57	"
90.91/60.57	"gcd'2 x wzx = gcd'1 (wzx == 0) x wzx;
90.91/60.57	gcd'2 xuv xuw = gcd'0 xuv xuw;
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"gcd 0 0 = error [];
90.91/60.57	gcd x y = gcd' (abs x) (abs y) where {
90.91/60.57	gcd' x 0 = x;
90.91/60.57	gcd' x y = gcd' y (x `rem` y);
90.91/60.57	} 
90.91/60.57	;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"gcd xux xuy = gcd3 xux xuy;
90.91/60.57	gcd x y = gcd0 x y;
90.91/60.57	"
90.91/60.57	"gcd0 x y = gcd' (abs x) (abs y) where {
90.91/60.57	gcd' x wzx = gcd'2 x wzx;
90.91/60.57	gcd' x y = gcd'0 x y;
90.91/60.57	;
90.91/60.57	gcd'0 x y = gcd' y (x `rem` y);
90.91/60.57	;
90.91/60.57	gcd'1 True x wzx = x;
90.91/60.57	gcd'1 wzy wzz xuu = gcd'0 wzz xuu;
90.91/60.57	;
90.91/60.57	gcd'2 x wzx = gcd'1 (wzx == 0) x wzx;
90.91/60.57	gcd'2 xuv xuw = gcd'0 xuv xuw;
90.91/60.57	} 
90.91/60.57	;
90.91/60.57	"
90.91/60.57	"gcd1 True xux xuy = error [];
90.91/60.57	gcd1 xuz xvu xvv = gcd0 xvu xvv;
90.91/60.57	"
90.91/60.57	"gcd2 True xux xuy = gcd1 (xuy == 0) xux xuy;
90.91/60.57	gcd2 xvw xvx xvy = gcd0 xvx xvy;
90.91/60.57	"
90.91/60.57	"gcd3 xux xuy = gcd2 (xux == 0) xux xuy;
90.91/60.57	gcd3 xvz xwu = gcd0 xvz xwu;
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"undefined |Falseundefined;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"undefined  = undefined1;
90.91/60.57	"
90.91/60.57	"undefined0 True = undefined;
90.91/60.57	"
90.91/60.57	"undefined1  = undefined0 False;
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"reduce x y|y == 0error []|otherwisex `quot` d :% (y `quot` d) where {
90.91/60.57	d  = gcd x y;
90.91/60.57	} 
90.91/60.57	;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"reduce x y = reduce2 x y;
90.91/60.57	"
90.91/60.57	"reduce2 x y = reduce1 x y (y == 0) where {
90.91/60.57	d  = gcd x y;
90.91/60.57	;
90.91/60.57	reduce0 x y True = x `quot` d :% (y `quot` d);
90.91/60.57	;
90.91/60.57	reduce1 x y True = error [];
90.91/60.57	reduce1 x y False = reduce0 x y otherwise;
90.91/60.57	} 
90.91/60.57	;
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"addToFM_C combiner EmptyFM key elt = unitFM key elt;
90.91/60.57	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;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
90.91/60.57	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;
90.91/60.57	"
90.91/60.57	"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);
90.91/60.57	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;
90.91/60.57	"
90.91/60.57	"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;
90.91/60.57	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);
90.91/60.57	"
90.91/60.57	"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;
90.91/60.57	"
90.91/60.57	"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);
90.91/60.57	"
90.91/60.57	"addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
90.91/60.57	addToFM_C4 xwx xwy xwz xxu = addToFM_C3 xwx xwy xwz xxu;
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
90.91/60.57	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
90.91/60.57	mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy)|sIZE_RATIO * size_l < size_rmkBalBranch vvu vvv (mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) vvx) vvy|sIZE_RATIO * size_r < size_lmkBalBranch vuu vuv vux (mkVBalBranch key elt vuy (Branch vvu vvv vvw vvx vvy))|otherwisemkBranch 13 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy) where {
90.91/60.57	size_l  = sizeFM (Branch vuu vuv vuw vux vuy);
90.91/60.57	;
90.91/60.57	size_r  = sizeFM (Branch vvu vvv vvw vvx vvy);
90.91/60.57	} 
90.91/60.57	;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
90.91/60.57	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
90.91/60.57	mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy) = mkVBalBranch3 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy);
90.91/60.57	"
90.91/60.57	"mkVBalBranch3 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy) = mkVBalBranch2 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * size_l < size_r) where {
90.91/60.57	mkVBalBranch0 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBranch 13 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy);
90.91/60.57	;
90.91/60.57	mkVBalBranch1 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vuu vuv vux (mkVBalBranch key elt vuy (Branch vvu vvv vvw vvx vvy));
90.91/60.57	mkVBalBranch1 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch0 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy otherwise;
90.91/60.57	;
90.91/60.57	mkVBalBranch2 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vvu vvv (mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) vvx) vvy;
90.91/60.57	mkVBalBranch2 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch1 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * size_r < size_l);
90.91/60.57	;
90.91/60.57	size_l  = sizeFM (Branch vuu vuv vuw vux vuy);
90.91/60.57	;
90.91/60.57	size_r  = sizeFM (Branch vvu vvv vvw vvx vvy);
90.91/60.57	} 
90.91/60.57	;
90.91/60.57	"
90.91/60.57	"mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
90.91/60.57	mkVBalBranch4 xxy xxz xyu xyv = mkVBalBranch3 xxy xxz xyu xyv;
90.91/60.57	"
90.91/60.57	"mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
90.91/60.57	mkVBalBranch5 xyx xyy xyz xzu = mkVBalBranch4 xyx xyy xyz xzu;
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"splitGT EmptyFM split_key = emptyFM;
90.91/60.57	splitGT (Branch key elt vwv 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;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
90.91/60.57	splitGT (Branch key elt vwv fm_l fm_r) split_key = splitGT3 (Branch key elt vwv fm_l fm_r) split_key;
90.91/60.57	"
90.91/60.57	"splitGT0 key elt vwv fm_l fm_r split_key True = fm_r;
90.91/60.57	"
90.91/60.57	"splitGT2 key elt vwv fm_l fm_r split_key True = splitGT fm_r split_key;
90.91/60.57	splitGT2 key elt vwv fm_l fm_r split_key False = splitGT1 key elt vwv fm_l fm_r split_key (split_key < key);
90.91/60.57	"
90.91/60.57	"splitGT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
90.91/60.57	splitGT1 key elt vwv fm_l fm_r split_key False = splitGT0 key elt vwv fm_l fm_r split_key otherwise;
90.91/60.57	"
90.91/60.57	"splitGT3 (Branch key elt vwv fm_l fm_r) split_key = splitGT2 key elt vwv fm_l fm_r split_key (split_key > key);
90.91/60.57	"
90.91/60.57	"splitGT4 EmptyFM split_key = emptyFM;
90.91/60.57	splitGT4 xzx xzy = splitGT3 xzx xzy;
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"splitLT EmptyFM split_key = emptyFM;
90.91/60.57	splitLT (Branch key elt vww 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;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
90.91/60.57	splitLT (Branch key elt vww fm_l fm_r) split_key = splitLT3 (Branch key elt vww fm_l fm_r) split_key;
90.91/60.57	"
90.91/60.57	"splitLT1 key elt vww fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
90.91/60.57	splitLT1 key elt vww fm_l fm_r split_key False = splitLT0 key elt vww fm_l fm_r split_key otherwise;
90.91/60.57	"
90.91/60.57	"splitLT2 key elt vww fm_l fm_r split_key True = splitLT fm_l split_key;
90.91/60.57	splitLT2 key elt vww fm_l fm_r split_key False = splitLT1 key elt vww fm_l fm_r split_key (split_key > key);
90.91/60.57	"
90.91/60.57	"splitLT0 key elt vww fm_l fm_r split_key True = fm_l;
90.91/60.57	"
90.91/60.57	"splitLT3 (Branch key elt vww fm_l fm_r) split_key = splitLT2 key elt vww fm_l fm_r split_key (split_key < key);
90.91/60.57	"
90.91/60.57	"splitLT4 EmptyFM split_key = emptyFM;
90.91/60.57	splitLT4 yuv yuw = splitLT3 yuv yuw;
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"mkBalBranch1 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"mkBalBranch1 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr);
90.91/60.57	"
90.91/60.57	"mkBalBranch10 fm_L fm_R vzu vzv vzw fm_ll fm_lr True = double_R fm_L fm_R;
90.91/60.57	"
90.91/60.57	"mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr True = single_R fm_L fm_R;
90.91/60.57	mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vzu vzv vzw fm_ll fm_lr otherwise;
90.91/60.57	"
90.91/60.57	"mkBalBranch12 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"mkBalBranch0 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"mkBalBranch0 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr);
90.91/60.57	"
90.91/60.57	"mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr True = single_L fm_L fm_R;
90.91/60.57	mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzz wuu wuv fm_rl fm_rr otherwise;
90.91/60.57	"
90.91/60.57	"mkBalBranch00 fm_L fm_R vzz wuu wuv fm_rl fm_rr True = double_L fm_L fm_R;
90.91/60.57	"
90.91/60.57	"mkBalBranch02 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"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 {
90.91/60.57	double_L fm_l (Branch key_r elt_r vzx (Branch key_rl elt_rl vzy 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);
90.91/60.57	;
90.91/60.57	double_R (Branch key_l elt_l vyy fm_ll (Branch key_lr elt_lr vyz 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);
90.91/60.57	;
90.91/60.57	mkBalBranch0 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
90.91/60.57	;
90.91/60.57	mkBalBranch1 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
90.91/60.57	;
90.91/60.57	single_L fm_l (Branch key_r elt_r wuw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
90.91/60.57	;
90.91/60.57	single_R (Branch key_l elt_l vyx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
90.91/60.57	;
90.91/60.57	size_l  = sizeFM fm_L;
90.91/60.57	;
90.91/60.57	size_r  = sizeFM fm_R;
90.91/60.57	} 
90.91/60.57	;
90.91/60.57	"
90.91/60.57	is transformed to
90.91/60.57	"mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
90.91/60.57	"
90.91/60.57	"mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
90.91/60.57	double_L fm_l (Branch key_r elt_r vzx (Branch key_rl elt_rl vzy 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);
90.91/60.57	;
90.91/60.57	double_R (Branch key_l elt_l vyy fm_ll (Branch key_lr elt_lr vyz 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);
90.91/60.57	;
90.91/60.57	mkBalBranch0 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr);
90.91/60.57	;
90.91/60.57	mkBalBranch00 fm_L fm_R vzz wuu wuv fm_rl fm_rr True = double_L fm_L fm_R;
90.91/60.57	;
90.91/60.57	mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr True = single_L fm_L fm_R;
90.91/60.57	mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzz wuu wuv fm_rl fm_rr otherwise;
90.91/60.57	;
90.91/60.57	mkBalBranch02 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
90.91/60.57	;
90.91/60.57	mkBalBranch1 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr);
90.91/60.57	;
90.91/60.57	mkBalBranch10 fm_L fm_R vzu vzv vzw fm_ll fm_lr True = double_R fm_L fm_R;
90.91/60.57	;
90.91/60.57	mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr True = single_R fm_L fm_R;
90.91/60.57	mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vzu vzv vzw fm_ll fm_lr otherwise;
90.91/60.57	;
90.91/60.57	mkBalBranch12 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
90.91/60.57	;
90.91/60.57	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
90.91/60.57	;
90.91/60.57	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
90.91/60.57	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
90.91/60.57	;
90.91/60.57	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
90.91/60.57	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
90.91/60.57	;
90.91/60.57	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
90.91/60.57	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
90.91/60.57	;
90.91/60.57	single_L fm_l (Branch key_r elt_r wuw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
90.91/60.57	;
90.91/60.57	single_R (Branch key_l elt_l vyx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
90.91/60.57	;
90.91/60.57	size_l  = sizeFM fm_L;
90.91/60.57	;
90.91/60.57	size_r  = sizeFM fm_R;
90.91/60.57	} 
90.91/60.57	;
90.91/60.57	"
90.91/60.57	The following Function with conditions
90.91/60.57	"glueBal EmptyFM fm2 = fm2;
90.91/60.57	glueBal fm1 EmptyFM = fm1;
90.91/60.57	glueBal fm1 fm2|sizeFM fm2 > sizeFM fm1mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)|otherwisemkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where {
90.91/60.57	mid_elt1  = mid_elt10 vv2;
90.91/60.57	;
90.91/60.57	mid_elt10 (wuy,mid_elt1) = mid_elt1;
90.91/60.57	;
90.91/60.57	mid_elt2  = mid_elt20 vv3;
90.91/60.57	;
90.91/60.57	mid_elt20 (wux,mid_elt2) = mid_elt2;
90.91/60.57	;
90.91/60.57	mid_key1  = mid_key10 vv2;
90.91/60.57	;
90.91/60.57	mid_key10 (mid_key1,wuz) = mid_key1;
90.91/60.57	;
90.91/60.57	mid_key2  = mid_key20 vv3;
90.91/60.57	;
90.91/60.57	mid_key20 (mid_key2,wvu) = mid_key2;
90.91/60.57	;
90.91/60.58	vv2  = findMax fm1;
90.91/60.58	;
90.91/60.58	vv3  = findMin fm2;
90.91/60.58	} 
90.91/60.58	;
90.91/60.58	"
90.91/60.58	is transformed to
90.91/60.58	"glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
90.91/60.58	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
90.91/60.58	glueBal fm1 fm2 = glueBal2 fm1 fm2;
90.91/60.58	"
90.91/60.58	"glueBal2 fm1 fm2 = glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where {
90.91/60.58	glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2;
90.91/60.58	;
90.91/60.58	glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2);
90.91/60.58	glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise;
90.91/60.58	;
90.91/60.58	mid_elt1  = mid_elt10 vv2;
90.91/60.58	;
90.91/60.58	mid_elt10 (wuy,mid_elt1) = mid_elt1;
90.91/60.58	;
90.91/60.58	mid_elt2  = mid_elt20 vv3;
90.91/60.58	;
90.91/60.58	mid_elt20 (wux,mid_elt2) = mid_elt2;
90.91/60.58	;
90.91/60.58	mid_key1  = mid_key10 vv2;
90.91/60.58	;
90.91/60.58	mid_key10 (mid_key1,wuz) = mid_key1;
90.91/60.58	;
90.91/60.58	mid_key2  = mid_key20 vv3;
90.91/60.58	;
90.91/60.58	mid_key20 (mid_key2,wvu) = mid_key2;
90.91/60.58	;
90.91/60.58	vv2  = findMax fm1;
90.91/60.58	;
90.91/60.58	vv3  = findMin fm2;
90.91/60.58	} 
90.91/60.58	;
90.91/60.58	"
90.91/60.58	"glueBal3 fm1 EmptyFM = fm1;
90.91/60.58	glueBal3 yvu yvv = glueBal2 yvu yvv;
90.91/60.58	"
90.91/60.58	"glueBal4 EmptyFM fm2 = fm2;
90.91/60.58	glueBal4 yvx yvy = glueBal3 yvx yvy;
90.91/60.58	"
90.91/60.58	The following Function with conditions
90.91/60.58	"glueVBal EmptyFM fm2 = fm2;
90.91/60.58	glueVBal fm1 EmptyFM = fm1;
90.91/60.58	glueVBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu)|sIZE_RATIO * size_l < size_rmkBalBranch www wwx (glueVBal (Branch wvw wvx wvy wvz wwu) wwz) wxu|sIZE_RATIO * size_r < size_lmkBalBranch wvw wvx wvz (glueVBal wwu (Branch www wwx wwy wwz wxu))|otherwiseglueBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu) where {
90.91/60.58	size_l  = sizeFM (Branch wvw wvx wvy wvz wwu);
90.91/60.58	;
90.91/60.58	size_r  = sizeFM (Branch www wwx wwy wwz wxu);
90.91/60.58	} 
90.91/60.58	;
90.91/60.58	"
90.91/60.58	is transformed to
90.91/60.58	"glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2;
90.91/60.58	glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM;
90.91/60.58	glueVBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu) = glueVBal3 (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu);
90.91/60.58	"
90.91/60.58	"glueVBal3 (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu) = glueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * size_l < size_r) where {
90.91/60.58	glueVBal0 wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = glueBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu);
90.91/60.58	;
90.91/60.58	glueVBal1 wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch wvw wvx wvz (glueVBal wwu (Branch www wwx wwy wwz wxu));
90.91/60.58	glueVBal1 wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal0 wvw wvx wvy wvz wwu www wwx wwy wwz wxu otherwise;
90.91/60.58	;
90.91/60.58	glueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch www wwx (glueVBal (Branch wvw wvx wvy wvz wwu) wwz) wxu;
90.91/60.58	glueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal1 wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * size_r < size_l);
90.91/60.58	;
90.91/60.58	size_l  = sizeFM (Branch wvw wvx wvy wvz wwu);
90.91/60.58	;
90.91/60.58	size_r  = sizeFM (Branch www wwx wwy wwz wxu);
90.91/60.58	} 
90.91/60.58	;
90.91/60.58	"
90.91/60.58	"glueVBal4 fm1 EmptyFM = fm1;
90.91/60.58	glueVBal4 yww ywx = glueVBal3 yww ywx;
90.91/60.58	"
90.91/60.58	"glueVBal5 EmptyFM fm2 = fm2;
90.91/60.58	glueVBal5 ywz yxu = glueVBal4 ywz yxu;
90.91/60.58	"
90.91/60.58	The following Function with conditions
90.91/60.58	"lookupFM EmptyFM key = Nothing;
90.91/60.58	lookupFM (Branch key elt wyu fm_l fm_r) key_to_find|key_to_find < keylookupFM fm_l key_to_find|key_to_find > keylookupFM fm_r key_to_find|otherwiseJust elt;
90.91/60.58	"
90.91/60.58	is transformed to
90.91/60.58	"lookupFM EmptyFM key = lookupFM4 EmptyFM key;
90.91/60.58	lookupFM (Branch key elt wyu fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wyu fm_l fm_r) key_to_find;
90.91/60.58	"
90.91/60.58	"lookupFM2 key elt wyu fm_l fm_r key_to_find True = lookupFM fm_l key_to_find;
90.91/60.58	lookupFM2 key elt wyu fm_l fm_r key_to_find False = lookupFM1 key elt wyu fm_l fm_r key_to_find (key_to_find > key);
90.91/60.58	"
90.91/60.58	"lookupFM0 key elt wyu fm_l fm_r key_to_find True = Just elt;
90.91/60.58	"
90.91/60.58	"lookupFM1 key elt wyu fm_l fm_r key_to_find True = lookupFM fm_r key_to_find;
90.91/60.58	lookupFM1 key elt wyu fm_l fm_r key_to_find False = lookupFM0 key elt wyu fm_l fm_r key_to_find otherwise;
90.91/60.58	"
90.91/60.58	"lookupFM3 (Branch key elt wyu fm_l fm_r) key_to_find = lookupFM2 key elt wyu fm_l fm_r key_to_find (key_to_find < key);
90.91/60.58	"
90.91/60.58	"lookupFM4 EmptyFM key = Nothing;
90.91/60.58	lookupFM4 yxx yxy = lookupFM3 yxx yxy;
90.91/60.58	"
90.91/60.58	The following Function with conditions
90.91/60.58	"intersectFM_C combiner fm1 EmptyFM = emptyFM;
90.91/60.58	intersectFM_C combiner EmptyFM fm2 = emptyFM;
90.91/60.58	intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right)|Maybe.isJust maybe_elt1mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right)|otherwiseglueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where {
90.91/60.58	elt1  = elt10 vv1;
90.91/60.58	;
90.91/60.58	elt10 (Just elt1) = elt1;
90.91/60.58	;
90.91/60.58	gts  = splitGT fm1 split_key;
90.91/60.58	;
90.91/60.58	lts  = splitLT fm1 split_key;
90.91/60.58	;
90.91/60.58	maybe_elt1  = lookupFM fm1 split_key;
90.91/60.58	;
90.91/60.58	vv1  = maybe_elt1;
90.91/60.58	} 
90.91/60.58	;
90.91/60.58	"
90.91/60.58	is transformed to
90.91/60.58	"intersectFM_C combiner fm1 EmptyFM = intersectFM_C4 combiner fm1 EmptyFM;
90.91/60.58	intersectFM_C combiner EmptyFM fm2 = intersectFM_C3 combiner EmptyFM fm2;
90.91/60.58	intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right);
90.91/60.58	"
90.91/60.58	"intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C1 combiner fm1 split_key elt2 wyx left right (Maybe.isJust maybe_elt1) where {
90.91/60.58	elt1  = elt10 vv1;
90.91/60.58	;
90.91/60.58	elt10 (Just elt1) = elt1;
90.91/60.58	;
90.91/60.58	gts  = splitGT fm1 split_key;
90.91/60.58	;
90.91/60.58	intersectFM_C0 combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right);
90.91/60.58	;
90.91/60.58	intersectFM_C1 combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right);
90.91/60.58	intersectFM_C1 combiner fm1 split_key elt2 wyx left right False = intersectFM_C0 combiner fm1 split_key elt2 wyx left right otherwise;
90.91/60.58	;
90.91/60.58	lts  = splitLT fm1 split_key;
90.91/60.58	;
90.91/60.58	maybe_elt1  = lookupFM fm1 split_key;
90.91/60.58	;
90.91/60.58	vv1  = maybe_elt1;
90.91/60.58	} 
90.91/60.58	;
90.91/60.58	"
90.91/60.58	"intersectFM_C3 combiner EmptyFM fm2 = emptyFM;
90.91/60.58	intersectFM_C3 yyv yyw yyx = intersectFM_C2 yyv yyw yyx;
90.91/60.58	"
90.91/60.58	"intersectFM_C4 combiner fm1 EmptyFM = emptyFM;
90.91/60.58	intersectFM_C4 yyz yzu yzv = intersectFM_C3 yyz yzu yzv;
90.91/60.58	"
90.91/60.58	
90.91/60.58	----------------------------------------
90.91/60.58	
90.91/60.58	(10)
90.91/60.58	Obligation:
90.91/60.58	mainModule Main 
90.91/60.58	module FiniteMap where {
90.91/60.58	import qualified Main;
90.91/60.58	import qualified Maybe;
90.91/60.58	import qualified Prelude;
90.91/60.58	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
90.91/60.58	
90.91/60.58	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
90.91/60.58	(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
90.91/60.58	}
90.91/60.58	addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
90.91/60.58	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
90.91/60.58	
90.91/60.58	addToFM0 old new = new;
90.91/60.58	
90.91/60.58	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
90.91/60.58	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
90.91/60.58	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;
90.91/60.58	
90.91/60.58	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;
90.91/60.58	
90.91/60.58	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);
90.91/60.58	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;
90.91/60.58	
90.91/60.58	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;
90.91/60.58	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);
90.91/60.58	
90.91/60.58	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);
90.91/60.58	
90.91/60.58	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
90.91/60.58	addToFM_C4 xwx xwy xwz xxu = addToFM_C3 xwx xwy xwz xxu;
90.91/60.58	
90.91/60.58	deleteMax :: Ord b => FiniteMap b a  ->  FiniteMap b a;
90.91/60.58	deleteMax (Branch key elt vvz fm_l EmptyFM) = fm_l;
90.91/60.58	deleteMax (Branch key elt vwu fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
90.91/60.58	
90.91/60.58	deleteMin :: Ord a => FiniteMap a b  ->  FiniteMap a b;
90.91/60.58	deleteMin (Branch key elt wyv EmptyFM fm_r) = fm_r;
90.91/60.58	deleteMin (Branch key elt wyw fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
90.91/60.58	
90.91/60.58	emptyFM :: FiniteMap b a;
90.91/60.58	emptyFM = EmptyFM;
90.91/60.58	
90.91/60.58	findMax :: FiniteMap a b  ->  (a,b);
90.91/60.58	findMax (Branch key elt vxz vyu EmptyFM) = (key,elt);
90.91/60.58	findMax (Branch key elt vyv vyw fm_r) = findMax fm_r;
90.91/60.58	
90.91/60.58	findMin :: FiniteMap a b  ->  (a,b);
90.91/60.58	findMin (Branch key elt wyy EmptyFM wyz) = (key,elt);
90.91/60.58	findMin (Branch key elt wzu fm_l wzv) = findMin fm_l;
90.91/60.58	
90.91/60.58	fmToList :: FiniteMap b a  ->  [(b,a)];
90.91/60.58	fmToList fm = foldFM fmToList0 [] fm;
90.91/60.58	
90.91/60.58	fmToList0 key elt rest = (key,elt) : rest;
90.91/60.58	
90.91/60.58	foldFM :: (b  ->  c  ->  a  ->  a)  ->  a  ->  FiniteMap b c  ->  a;
90.91/60.58	foldFM k z EmptyFM = z;
90.91/60.58	foldFM k z (Branch key elt wxv fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;
90.91/60.58	
90.91/60.58	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
90.91/60.58	glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
90.91/60.58	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
90.91/60.58	glueBal fm1 fm2 = glueBal2 fm1 fm2;
90.91/60.58	
90.91/60.58	glueBal2 fm1 fm2 = glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where { 
90.91/60.58	glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2;
90.91/60.58	glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2);
90.91/60.58	glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise;
90.91/60.58	mid_elt1 = mid_elt10 vv2;
90.91/60.58	mid_elt10 (wuy,mid_elt1) = mid_elt1;
90.91/60.58	mid_elt2 = mid_elt20 vv3;
90.91/60.58	mid_elt20 (wux,mid_elt2) = mid_elt2;
90.91/60.58	mid_key1 = mid_key10 vv2;
90.91/60.58	mid_key10 (mid_key1,wuz) = mid_key1;
90.91/60.58	mid_key2 = mid_key20 vv3;
90.91/60.58	mid_key20 (mid_key2,wvu) = mid_key2;
90.91/60.58	vv2 = findMax fm1;
90.91/60.58	vv3 = findMin fm2;
90.91/60.58	 };
90.91/60.58	
90.91/60.58	glueBal3 fm1 EmptyFM = fm1;
90.91/60.58	glueBal3 yvu yvv = glueBal2 yvu yvv;
90.91/60.58	
90.91/60.58	glueBal4 EmptyFM fm2 = fm2;
90.91/60.58	glueBal4 yvx yvy = glueBal3 yvx yvy;
90.91/60.58	
90.91/60.58	glueVBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
90.91/60.58	glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2;
90.91/60.58	glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM;
90.91/60.58	glueVBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu) = glueVBal3 (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu);
90.91/60.58	
90.91/60.58	glueVBal3 (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu) = glueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * size_l < size_r) where { 
90.91/60.58	glueVBal0 wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = glueBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu);
90.91/60.58	glueVBal1 wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch wvw wvx wvz (glueVBal wwu (Branch www wwx wwy wwz wxu));
90.91/60.58	glueVBal1 wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal0 wvw wvx wvy wvz wwu www wwx wwy wwz wxu otherwise;
90.91/60.58	glueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch www wwx (glueVBal (Branch wvw wvx wvy wvz wwu) wwz) wxu;
90.91/60.58	glueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal1 wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * size_r < size_l);
90.91/60.58	size_l = sizeFM (Branch wvw wvx wvy wvz wwu);
90.91/60.58	size_r = sizeFM (Branch www wwx wwy wwz wxu);
90.91/60.58	 };
90.91/60.58	
90.91/60.58	glueVBal4 fm1 EmptyFM = fm1;
90.91/60.58	glueVBal4 yww ywx = glueVBal3 yww ywx;
90.91/60.58	
90.91/60.58	glueVBal5 EmptyFM fm2 = fm2;
90.91/60.58	glueVBal5 ywz yxu = glueVBal4 ywz yxu;
90.91/60.58	
90.91/60.58	intersectFM_C :: Ord c => (a  ->  b  ->  d)  ->  FiniteMap c a  ->  FiniteMap c b  ->  FiniteMap c d;
90.91/60.58	intersectFM_C combiner fm1 EmptyFM = intersectFM_C4 combiner fm1 EmptyFM;
90.91/60.58	intersectFM_C combiner EmptyFM fm2 = intersectFM_C3 combiner EmptyFM fm2;
90.91/60.58	intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right);
90.91/60.58	
90.91/60.58	intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C1 combiner fm1 split_key elt2 wyx left right (Maybe.isJust maybe_elt1) where { 
90.91/60.58	elt1 = elt10 vv1;
90.91/60.58	elt10 (Just elt1) = elt1;
90.91/60.58	gts = splitGT fm1 split_key;
90.91/60.58	intersectFM_C0 combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right);
90.91/60.58	intersectFM_C1 combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right);
90.91/60.58	intersectFM_C1 combiner fm1 split_key elt2 wyx left right False = intersectFM_C0 combiner fm1 split_key elt2 wyx left right otherwise;
90.91/60.58	lts = splitLT fm1 split_key;
90.91/60.58	maybe_elt1 = lookupFM fm1 split_key;
90.91/60.58	vv1 = maybe_elt1;
90.91/60.58	 };
90.91/60.58	
90.91/60.58	intersectFM_C3 combiner EmptyFM fm2 = emptyFM;
90.91/60.58	intersectFM_C3 yyv yyw yyx = intersectFM_C2 yyv yyw yyx;
90.91/60.58	
90.91/60.58	intersectFM_C4 combiner fm1 EmptyFM = emptyFM;
90.91/60.58	intersectFM_C4 yyz yzu yzv = intersectFM_C3 yyz yzu yzv;
90.91/60.58	
90.91/60.58	lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
90.91/60.58	lookupFM EmptyFM key = lookupFM4 EmptyFM key;
90.91/60.58	lookupFM (Branch key elt wyu fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wyu fm_l fm_r) key_to_find;
90.91/60.58	
90.91/60.58	lookupFM0 key elt wyu fm_l fm_r key_to_find True = Just elt;
90.91/60.58	
90.91/60.58	lookupFM1 key elt wyu fm_l fm_r key_to_find True = lookupFM fm_r key_to_find;
90.91/60.58	lookupFM1 key elt wyu fm_l fm_r key_to_find False = lookupFM0 key elt wyu fm_l fm_r key_to_find otherwise;
90.91/60.58	
90.91/60.58	lookupFM2 key elt wyu fm_l fm_r key_to_find True = lookupFM fm_l key_to_find;
90.91/60.58	lookupFM2 key elt wyu fm_l fm_r key_to_find False = lookupFM1 key elt wyu fm_l fm_r key_to_find (key_to_find > key);
90.91/60.58	
90.91/60.58	lookupFM3 (Branch key elt wyu fm_l fm_r) key_to_find = lookupFM2 key elt wyu fm_l fm_r key_to_find (key_to_find < key);
90.91/60.58	
90.91/60.58	lookupFM4 EmptyFM key = Nothing;
90.91/60.58	lookupFM4 yxx yxy = lookupFM3 yxx yxy;
90.91/60.58	
90.91/60.58	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
90.91/60.58	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
90.91/60.58	
90.91/60.58	mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 
90.91/60.58	double_L fm_l (Branch key_r elt_r vzx (Branch key_rl elt_rl vzy 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);
90.91/60.58	double_R (Branch key_l elt_l vyy fm_ll (Branch key_lr elt_lr vyz 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);
90.91/60.58	mkBalBranch0 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr);
90.91/60.58	mkBalBranch00 fm_L fm_R vzz wuu wuv fm_rl fm_rr True = double_L fm_L fm_R;
90.91/60.58	mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr True = single_L fm_L fm_R;
90.91/60.58	mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzz wuu wuv fm_rl fm_rr otherwise;
90.91/60.58	mkBalBranch02 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
90.91/60.58	mkBalBranch1 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr);
90.91/60.58	mkBalBranch10 fm_L fm_R vzu vzv vzw fm_ll fm_lr True = double_R fm_L fm_R;
90.91/60.58	mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr True = single_R fm_L fm_R;
90.91/60.58	mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vzu vzv vzw fm_ll fm_lr otherwise;
90.91/60.58	mkBalBranch12 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
90.91/60.58	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
90.91/60.58	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
90.91/60.58	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
90.91/60.58	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
90.91/60.58	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
90.91/60.58	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
90.91/60.58	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
90.91/60.58	single_L fm_l (Branch key_r elt_r wuw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
90.91/60.58	single_R (Branch key_l elt_l vyx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
90.91/60.58	size_l = sizeFM fm_L;
90.91/60.58	size_r = sizeFM fm_R;
90.91/60.58	 };
90.91/60.58	
90.91/60.58	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
90.91/60.58	mkBranch which key elt fm_l fm_r = let { 
90.91/60.58	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
90.91/60.58	} in result where { 
90.91/60.58	balance_ok = True;
90.91/60.58	left_ok = left_ok0 fm_l key fm_l;
90.91/60.58	left_ok0 fm_l key EmptyFM = True;
90.91/60.58	left_ok0 fm_l key (Branch left_key vwx vwy vwz vxu) = let { 
90.91/60.58	biggest_left_key = fst (findMax fm_l);
90.91/60.58	} in biggest_left_key < key;
90.91/60.58	left_size = sizeFM fm_l;
90.91/60.58	right_ok = right_ok0 fm_r key fm_r;
90.91/60.58	right_ok0 fm_r key EmptyFM = True;
90.91/60.58	right_ok0 fm_r key (Branch right_key vxv vxw vxx vxy) = let { 
90.91/60.58	smallest_right_key = fst (findMin fm_r);
90.91/60.58	} in key < smallest_right_key;
90.91/60.58	right_size = sizeFM fm_r;
90.91/60.58	unbox :: Int  ->  Int;
90.91/60.58	unbox x = x;
90.91/60.58	 };
90.91/60.58	
90.91/60.58	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
90.91/60.58	mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
90.91/60.58	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
90.91/60.58	mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy) = mkVBalBranch3 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy);
90.91/60.58	
90.91/60.58	mkVBalBranch3 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy) = mkVBalBranch2 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * size_l < size_r) where { 
90.91/60.58	mkVBalBranch0 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBranch 13 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy);
90.91/60.58	mkVBalBranch1 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vuu vuv vux (mkVBalBranch key elt vuy (Branch vvu vvv vvw vvx vvy));
90.91/60.58	mkVBalBranch1 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch0 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy otherwise;
90.91/60.58	mkVBalBranch2 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vvu vvv (mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) vvx) vvy;
90.91/60.58	mkVBalBranch2 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch1 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * size_r < size_l);
90.91/60.58	size_l = sizeFM (Branch vuu vuv vuw vux vuy);
90.91/60.58	size_r = sizeFM (Branch vvu vvv vvw vvx vvy);
90.91/60.58	 };
90.91/60.58	
90.91/60.58	mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
90.91/60.58	mkVBalBranch4 xxy xxz xyu xyv = mkVBalBranch3 xxy xxz xyu xyv;
90.91/60.58	
90.91/60.58	mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
90.91/60.58	mkVBalBranch5 xyx xyy xyz xzu = mkVBalBranch4 xyx xyy xyz xzu;
90.91/60.58	
90.91/60.58	sIZE_RATIO :: Int;
90.91/60.58	sIZE_RATIO = 5;
90.91/60.58	
90.91/60.58	sizeFM :: FiniteMap b a  ->  Int;
90.91/60.58	sizeFM EmptyFM = 0;
90.91/60.58	sizeFM (Branch wxw wxx size wxy wxz) = size;
90.91/60.58	
90.91/60.58	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
90.91/60.58	splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
90.91/60.58	splitGT (Branch key elt vwv fm_l fm_r) split_key = splitGT3 (Branch key elt vwv fm_l fm_r) split_key;
90.91/60.58	
90.91/60.58	splitGT0 key elt vwv fm_l fm_r split_key True = fm_r;
90.91/60.58	
90.91/60.58	splitGT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
90.91/60.58	splitGT1 key elt vwv fm_l fm_r split_key False = splitGT0 key elt vwv fm_l fm_r split_key otherwise;
90.91/60.58	
90.91/60.58	splitGT2 key elt vwv fm_l fm_r split_key True = splitGT fm_r split_key;
90.91/60.58	splitGT2 key elt vwv fm_l fm_r split_key False = splitGT1 key elt vwv fm_l fm_r split_key (split_key < key);
90.91/60.58	
90.91/60.58	splitGT3 (Branch key elt vwv fm_l fm_r) split_key = splitGT2 key elt vwv fm_l fm_r split_key (split_key > key);
90.91/60.58	
90.91/60.58	splitGT4 EmptyFM split_key = emptyFM;
90.91/60.58	splitGT4 xzx xzy = splitGT3 xzx xzy;
90.91/60.58	
90.91/60.58	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
90.91/60.58	splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
90.91/60.58	splitLT (Branch key elt vww fm_l fm_r) split_key = splitLT3 (Branch key elt vww fm_l fm_r) split_key;
90.91/60.58	
90.91/60.58	splitLT0 key elt vww fm_l fm_r split_key True = fm_l;
90.91/60.58	
90.91/60.58	splitLT1 key elt vww fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
90.91/60.58	splitLT1 key elt vww fm_l fm_r split_key False = splitLT0 key elt vww fm_l fm_r split_key otherwise;
90.91/60.58	
90.91/60.58	splitLT2 key elt vww fm_l fm_r split_key True = splitLT fm_l split_key;
90.91/60.58	splitLT2 key elt vww fm_l fm_r split_key False = splitLT1 key elt vww fm_l fm_r split_key (split_key > key);
90.91/60.58	
90.91/60.58	splitLT3 (Branch key elt vww fm_l fm_r) split_key = splitLT2 key elt vww fm_l fm_r split_key (split_key < key);
90.91/60.58	
90.91/60.58	splitLT4 EmptyFM split_key = emptyFM;
90.91/60.58	splitLT4 yuv yuw = splitLT3 yuv yuw;
90.91/60.58	
90.91/60.58	unitFM :: b  ->  a  ->  FiniteMap b a;
90.91/60.58	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
90.91/60.58	
90.91/60.58	}
90.91/60.58	module Maybe where {
90.91/60.58	import qualified FiniteMap;
90.91/60.58	import qualified Main;
90.91/60.58	import qualified Prelude;
90.91/60.58	isJust :: Maybe a  ->  Bool;
90.91/60.58	isJust Nothing = False;
90.91/60.58	isJust wzw = True;
90.91/60.58	
90.91/60.58	}
90.91/60.58	module Main where {
90.91/60.58	import qualified FiniteMap;
90.91/60.58	import qualified Maybe;
90.91/60.58	import qualified Prelude;
90.91/60.58	}
90.91/60.58	
90.91/60.58	----------------------------------------
90.91/60.58	
90.91/60.58	(11) LetRed (EQUIVALENT)
90.91/60.58	Let/Where Reductions:
90.91/60.58	The bindings of the following Let/Where expression
90.91/60.58	"gcd' (abs x) (abs y) where {
90.91/60.58	gcd' x wzx = gcd'2 x wzx;
90.91/60.58	gcd' x y = gcd'0 x y;
90.91/60.58	;
90.91/60.58	gcd'0 x y = gcd' y (x `rem` y);
90.91/60.58	;
90.91/60.58	gcd'1 True x wzx = x;
90.91/60.58	gcd'1 wzy wzz xuu = gcd'0 wzz xuu;
90.91/60.58	;
90.91/60.58	gcd'2 x wzx = gcd'1 (wzx == 0) x wzx;
90.91/60.58	gcd'2 xuv xuw = gcd'0 xuv xuw;
90.91/60.58	} 
90.91/60.58	"
90.91/60.58	are unpacked to the following functions on top level
90.91/60.58	"gcd0Gcd'1 True x wzx = x;
90.91/60.58	gcd0Gcd'1 wzy wzz xuu = gcd0Gcd'0 wzz xuu;
90.91/60.58	"
90.91/60.58	"gcd0Gcd' x wzx = gcd0Gcd'2 x wzx;
90.91/60.58	gcd0Gcd' x y = gcd0Gcd'0 x y;
90.91/60.58	"
90.91/60.58	"gcd0Gcd'2 x wzx = gcd0Gcd'1 (wzx == 0) x wzx;
90.91/60.58	gcd0Gcd'2 xuv xuw = gcd0Gcd'0 xuv xuw;
90.91/60.58	"
90.91/60.58	"gcd0Gcd'0 x y = gcd0Gcd' y (x `rem` y);
90.91/60.58	"
90.91/60.58	The bindings of the following Let/Where expression
90.91/60.58	"reduce1 x y (y == 0) where {
90.91/60.58	d  = gcd x y;
90.91/60.58	;
90.91/60.58	reduce0 x y True = x `quot` d :% (y `quot` d);
90.91/60.58	;
90.91/60.58	reduce1 x y True = error [];
90.91/60.58	reduce1 x y False = reduce0 x y otherwise;
90.91/60.58	} 
90.91/60.58	"
90.91/60.58	are unpacked to the following functions on top level
90.91/60.58	"reduce2Reduce0 yzw yzx x y True = x `quot` reduce2D yzw yzx :% (y `quot` reduce2D yzw yzx);
90.91/60.58	"
90.91/60.58	"reduce2D yzw yzx = gcd yzw yzx;
90.91/60.58	"
90.91/60.58	"reduce2Reduce1 yzw yzx x y True = error [];
90.91/60.58	reduce2Reduce1 yzw yzx x y False = reduce2Reduce0 yzw yzx x y otherwise;
90.91/60.58	"
90.91/60.58	The bindings of the following Let/Where expression
90.91/60.58	"glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where {
90.91/60.58	glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2;
90.91/60.58	;
90.91/60.58	glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2);
90.91/60.58	glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise;
90.91/60.58	;
90.91/60.58	mid_elt1  = mid_elt10 vv2;
90.91/60.58	;
90.91/60.58	mid_elt10 (wuy,mid_elt1) = mid_elt1;
90.91/60.58	;
90.91/60.58	mid_elt2  = mid_elt20 vv3;
90.91/60.58	;
90.91/60.58	mid_elt20 (wux,mid_elt2) = mid_elt2;
90.91/60.58	;
90.91/60.58	mid_key1  = mid_key10 vv2;
90.91/60.58	;
90.91/60.58	mid_key10 (mid_key1,wuz) = mid_key1;
90.91/60.58	;
90.91/60.58	mid_key2  = mid_key20 vv3;
90.91/60.58	;
90.91/60.58	mid_key20 (mid_key2,wvu) = mid_key2;
90.91/60.58	;
90.91/60.58	vv2  = findMax fm1;
90.91/60.58	;
90.91/60.58	vv3  = findMin fm2;
90.91/60.58	} 
90.91/60.58	"
90.91/60.58	are unpacked to the following functions on top level
90.91/60.58	"glueBal2GlueBal0 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 yzy yzz) (glueBal2Mid_elt1 yzy yzz) (deleteMax fm1) fm2;
90.91/60.58	"
90.91/60.58	"glueBal2Mid_key10 yzy yzz (mid_key1,wuz) = mid_key1;
90.91/60.58	"
90.91/60.58	"glueBal2Mid_key20 yzy yzz (mid_key2,wvu) = mid_key2;
90.91/60.58	"
90.91/60.58	"glueBal2Mid_elt1 yzy yzz = glueBal2Mid_elt10 yzy yzz (glueBal2Vv2 yzy yzz);
90.91/60.58	"
90.91/60.58	"glueBal2Mid_key1 yzy yzz = glueBal2Mid_key10 yzy yzz (glueBal2Vv2 yzy yzz);
90.91/60.58	"
90.91/60.58	"glueBal2GlueBal1 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 yzy yzz) (glueBal2Mid_elt2 yzy yzz) fm1 (deleteMin fm2);
90.91/60.58	glueBal2GlueBal1 yzy yzz fm1 fm2 False = glueBal2GlueBal0 yzy yzz fm1 fm2 otherwise;
90.91/60.58	"
90.91/60.58	"glueBal2Mid_key2 yzy yzz = glueBal2Mid_key20 yzy yzz (glueBal2Vv3 yzy yzz);
90.91/60.58	"
90.91/60.58	"glueBal2Mid_elt10 yzy yzz (wuy,mid_elt1) = mid_elt1;
90.91/60.58	"
90.91/60.58	"glueBal2Vv2 yzy yzz = findMax yzy;
90.91/60.58	"
90.91/60.58	"glueBal2Mid_elt20 yzy yzz (wux,mid_elt2) = mid_elt2;
90.91/60.58	"
90.91/60.58	"glueBal2Vv3 yzy yzz = findMin yzz;
90.91/60.58	"
90.91/60.58	"glueBal2Mid_elt2 yzy yzz = glueBal2Mid_elt20 yzy yzz (glueBal2Vv3 yzy yzz);
90.91/60.58	"
90.91/60.58	The bindings of the following Let/Where expression
90.91/60.58	"mkVBalBranch2 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * size_l < size_r) where {
90.91/60.58	mkVBalBranch0 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBranch 13 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy);
90.91/60.58	;
90.91/60.58	mkVBalBranch1 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vuu vuv vux (mkVBalBranch key elt vuy (Branch vvu vvv vvw vvx vvy));
90.91/60.58	mkVBalBranch1 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch0 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy otherwise;
90.91/60.58	;
90.91/60.58	mkVBalBranch2 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vvu vvv (mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) vvx) vvy;
90.91/60.58	mkVBalBranch2 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch1 key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * size_r < size_l);
90.91/60.58	;
90.91/60.58	size_l  = sizeFM (Branch vuu vuv vuw vux vuy);
90.91/60.58	;
90.91/60.58	size_r  = sizeFM (Branch vvu vvv vvw vvx vvy);
90.91/60.58	} 
90.91/60.58	"
90.91/60.58	are unpacked to the following functions on top level
90.91/60.58	"mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vuu vuv vux (mkVBalBranch key elt vuy (Branch vvu vvv vvw vvx vvy));
90.91/60.58	mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy otherwise;
90.91/60.58	"
90.91/60.58	"mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vvu vvv (mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) vvx) vvy;
90.91/60.58	mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx < mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx);
90.91/60.58	"
90.91/60.58	"mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuu zuv zuw zux zuy);
90.91/60.58	"
90.91/60.58	"mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBranch 13 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy);
90.91/60.58	"
90.91/60.58	"mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuz zvu zvv zvw zvx);
90.91/60.58	"
90.91/60.58	The bindings of the following Let/Where expression
90.91/60.58	"mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
90.91/60.58	double_L fm_l (Branch key_r elt_r vzx (Branch key_rl elt_rl vzy 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);
90.91/60.58	;
90.91/60.58	double_R (Branch key_l elt_l vyy fm_ll (Branch key_lr elt_lr vyz 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);
90.91/60.58	;
90.91/60.58	mkBalBranch0 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr);
90.91/60.58	;
90.91/60.58	mkBalBranch00 fm_L fm_R vzz wuu wuv fm_rl fm_rr True = double_L fm_L fm_R;
90.91/60.58	;
90.91/60.58	mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr True = single_L fm_L fm_R;
90.91/60.58	mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzz wuu wuv fm_rl fm_rr otherwise;
90.91/60.58	;
90.91/60.58	mkBalBranch02 fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzz wuu wuv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
90.91/60.58	;
90.91/60.58	mkBalBranch1 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr);
90.91/60.58	;
90.91/60.58	mkBalBranch10 fm_L fm_R vzu vzv vzw fm_ll fm_lr True = double_R fm_L fm_R;
90.91/60.58	;
90.91/60.58	mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr True = single_R fm_L fm_R;
90.91/60.58	mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vzu vzv vzw fm_ll fm_lr otherwise;
90.91/60.58	;
90.91/60.58	mkBalBranch12 fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vzu vzv vzw fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
90.91/60.58	;
90.91/60.58	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
90.91/60.58	;
90.91/60.58	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
90.91/60.58	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
90.91/60.58	;
90.91/60.58	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
90.91/60.58	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
90.91/60.58	;
90.91/60.58	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
90.91/60.58	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
90.91/60.58	;
90.91/60.58	single_L fm_l (Branch key_r elt_r wuw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
90.91/60.58	;
90.91/60.58	single_R (Branch key_l elt_l vyx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
90.91/60.58	;
90.91/60.58	size_l  = sizeFM fm_L;
90.91/60.58	;
90.91/60.58	size_r  = sizeFM fm_R;
90.91/60.58	} 
90.91/60.58	"
90.91/60.58	are unpacked to the following functions on top level
90.91/60.58	"mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
90.91/60.58	mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_r zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_l zvy zvz zwu zwv);
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R fm_R;
90.91/60.58	mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_l zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_r zvy zvz zwu zwv);
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr);
90.91/60.58	"
90.91/60.58	"mkBalBranch6Double_L zvy zvz zwu zwv fm_l (Branch key_r elt_r vzx (Branch key_rl elt_rl vzy fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 zvy zvz fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr);
90.91/60.58	"
90.91/60.58	"mkBalBranch6Size_r zvy zvz zwu zwv = sizeFM zwu;
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
90.91/60.58	"
90.91/60.58	"mkBalBranch6Single_L zvy zvz zwu zwv fm_l (Branch key_r elt_r wuw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 zvy zvz fm_l fm_rl) fm_rr;
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr True = mkBalBranch6Single_R zvy zvz zwu zwv fm_L fm_R;
90.91/60.58	mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr False = mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr otherwise;
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr True = mkBalBranch6Double_R zvy zvz zwu zwv fm_L fm_R;
90.91/60.58	"
90.91/60.58	"mkBalBranch6Double_R zvy zvz zwu zwv (Branch key_l elt_l vyy fm_ll (Branch key_lr elt_lr vyz fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 zvy zvz fm_lrr fm_r);
90.91/60.58	"
90.91/60.58	"mkBalBranch6Single_R zvy zvz zwu zwv (Branch key_l elt_l vyx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 zvy zvz fm_lr fm_r);
90.91/60.58	"
90.91/60.58	"mkBalBranch6Size_l zvy zvz zwu zwv = sizeFM zwv;
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr True = mkBalBranch6Single_L zvy zvz zwu zwv fm_L fm_R;
90.91/60.58	mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr False = mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr otherwise;
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr True = mkBalBranch6Double_L zvy zvz zwu zwv fm_L fm_R;
90.91/60.58	"
90.91/60.58	"mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R fm_L;
90.91/60.58	mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R otherwise;
90.91/60.58	"
90.91/60.58	The bindings of the following Let/Where expression
90.91/60.58	"intersectFM_C1 combiner fm1 split_key elt2 wyx left right (Maybe.isJust maybe_elt1) where {
90.91/60.58	elt1  = elt10 vv1;
90.91/60.58	;
90.91/60.58	elt10 (Just elt1) = elt1;
90.91/60.58	;
90.91/60.58	gts  = splitGT fm1 split_key;
90.91/60.58	;
90.91/60.58	intersectFM_C0 combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right);
90.91/60.58	;
90.91/60.58	intersectFM_C1 combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right);
90.91/60.58	intersectFM_C1 combiner fm1 split_key elt2 wyx left right False = intersectFM_C0 combiner fm1 split_key elt2 wyx left right otherwise;
90.91/60.58	;
90.91/60.58	lts  = splitLT fm1 split_key;
90.91/60.58	;
90.91/60.58	maybe_elt1  = lookupFM fm1 split_key;
90.91/60.58	;
90.91/60.58	vv1  = maybe_elt1;
90.91/60.58	} 
90.91/60.58	"
90.91/60.58	are unpacked to the following functions on top level
90.91/60.58	"intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner (intersectFM_C2Elt1 zww zwx) elt2) (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right);
90.91/60.58	intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right False = intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right otherwise;
90.91/60.58	"
90.91/60.58	"intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right);
90.91/60.58	"
90.91/60.58	"intersectFM_C2Lts zww zwx = splitLT zww zwx;
90.91/60.58	"
90.91/60.58	"intersectFM_C2Maybe_elt1 zww zwx = lookupFM zww zwx;
90.91/60.58	"
90.91/60.58	"intersectFM_C2Elt10 zww zwx (Just elt1) = elt1;
90.91/60.58	"
90.91/60.58	"intersectFM_C2Elt1 zww zwx = intersectFM_C2Elt10 zww zwx (intersectFM_C2Vv1 zww zwx);
90.91/60.58	"
90.91/60.58	"intersectFM_C2Vv1 zww zwx = intersectFM_C2Maybe_elt1 zww zwx;
90.91/60.58	"
90.91/60.58	"intersectFM_C2Gts zww zwx = splitGT zww zwx;
90.91/60.58	"
90.91/60.58	The bindings of the following Let/Where expression
90.91/60.58	"let {
90.91/60.58	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
90.91/60.58	} in result where {
90.91/60.58	balance_ok  = True;
90.91/60.58	;
90.91/60.58	left_ok  = left_ok0 fm_l key fm_l;
90.91/60.58	;
90.91/60.58	left_ok0 fm_l key EmptyFM = True;
90.91/60.58	left_ok0 fm_l key (Branch left_key vwx vwy vwz vxu) = let {
90.91/60.58	biggest_left_key  = fst (findMax fm_l);
90.91/60.58	} in biggest_left_key < key;
90.91/60.58	;
90.91/60.58	left_size  = sizeFM fm_l;
90.91/60.58	;
90.91/60.58	right_ok  = right_ok0 fm_r key fm_r;
90.91/60.58	;
90.91/60.58	right_ok0 fm_r key EmptyFM = True;
91.06/60.58	right_ok0 fm_r key (Branch right_key vxv vxw vxx vxy) = let {
91.06/60.58	smallest_right_key  = fst (findMin fm_r);
91.06/60.58	} in key < smallest_right_key;
91.06/60.58	;
91.06/60.58	right_size  = sizeFM fm_r;
91.06/60.58	;
91.06/60.58	unbox x = x;
91.06/60.58	} 
91.06/60.58	"
91.06/60.58	are unpacked to the following functions on top level
91.06/60.58	"mkBranchRight_size zwy zwz zxu = sizeFM zwy;
91.06/60.58	"
91.06/60.58	"mkBranchRight_ok zwy zwz zxu = mkBranchRight_ok0 zwy zwz zxu zwy zwz zwy;
91.06/60.58	"
91.06/60.58	"mkBranchUnbox zwy zwz zxu x = x;
91.06/60.58	"
91.06/60.58	"mkBranchLeft_ok0 zwy zwz zxu fm_l key EmptyFM = True;
91.06/60.58	mkBranchLeft_ok0 zwy zwz zxu fm_l key (Branch left_key vwx vwy vwz vxu) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
91.06/60.58	"
91.06/60.58	"mkBranchBalance_ok zwy zwz zxu = True;
91.06/60.58	"
91.06/60.58	"mkBranchLeft_ok zwy zwz zxu = mkBranchLeft_ok0 zwy zwz zxu zxu zwz zxu;
91.06/60.58	"
91.06/60.58	"mkBranchLeft_size zwy zwz zxu = sizeFM zxu;
91.06/60.58	"
91.06/60.58	"mkBranchRight_ok0 zwy zwz zxu fm_r key EmptyFM = True;
91.06/60.58	mkBranchRight_ok0 zwy zwz zxu fm_r key (Branch right_key vxv vxw vxx vxy) = key < mkBranchRight_ok0Smallest_right_key fm_r;
91.06/60.58	"
91.06/60.58	The bindings of the following Let/Where expression
91.06/60.58	"let {
91.06/60.58	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
91.06/60.58	} in result"
91.06/60.58	are unpacked to the following functions on top level
91.06/60.58	"mkBranchResult zxv zxw zxx zxy = Branch zxv zxw (mkBranchUnbox zxx zxv zxy (1 + mkBranchLeft_size zxx zxv zxy + mkBranchRight_size zxx zxv zxy)) zxy zxx;
91.06/60.58	"
91.06/60.58	The bindings of the following Let/Where expression
91.06/60.58	"glueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * size_l < size_r) where {
91.06/60.58	glueVBal0 wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = glueBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu);
91.06/60.58	;
91.06/60.58	glueVBal1 wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch wvw wvx wvz (glueVBal wwu (Branch www wwx wwy wwz wxu));
91.06/60.58	glueVBal1 wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal0 wvw wvx wvy wvz wwu www wwx wwy wwz wxu otherwise;
91.06/60.58	;
91.06/60.58	glueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch www wwx (glueVBal (Branch wvw wvx wvy wvz wwu) wwz) wxu;
91.06/60.58	glueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal1 wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * size_r < size_l);
91.06/60.58	;
91.06/60.58	size_l  = sizeFM (Branch wvw wvx wvy wvz wwu);
91.06/60.58	;
91.06/60.58	size_r  = sizeFM (Branch www wwx wwy wwz wxu);
91.06/60.58	} 
91.06/60.58	"
91.06/60.58	are unpacked to the following functions on top level
91.06/60.58	"glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch wvw wvx wvz (glueVBal wwu (Branch www wwx wwy wwz wxu));
91.06/60.58	glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu otherwise;
91.06/60.58	"
91.06/60.58	"glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zxz zyu zyv zyw zyx);
91.06/60.58	"
91.06/60.58	"glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = glueBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu);
91.06/60.58	"
91.06/60.58	"glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch www wwx (glueVBal (Branch wvw wvx wvy wvz wwu) wwz) wxu;
91.06/60.58	glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw < glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw);
91.06/60.58	"
91.06/60.58	"glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zyy zyz zzu zzv zzw);
91.06/60.58	"
91.06/60.58	The bindings of the following Let/Where expression
91.06/60.58	"let {
91.06/60.58	biggest_left_key  = fst (findMax fm_l);
91.06/60.58	} in biggest_left_key < key"
91.06/60.58	are unpacked to the following functions on top level
91.06/60.58	"mkBranchLeft_ok0Biggest_left_key zzx = fst (findMax zzx);
91.06/60.58	"
91.06/60.58	The bindings of the following Let/Where expression
91.06/60.58	"let {
91.06/60.58	smallest_right_key  = fst (findMin fm_r);
91.06/60.58	} in key < smallest_right_key"
91.06/60.58	are unpacked to the following functions on top level
91.06/60.58	"mkBranchRight_ok0Smallest_right_key zzy = fst (findMin zzy);
91.06/60.58	"
91.06/60.58	
91.06/60.58	----------------------------------------
91.06/60.58	
91.06/60.58	(12)
91.06/60.58	Obligation:
91.06/60.58	mainModule Main 
91.06/60.58	module FiniteMap where {
91.06/60.58	import qualified Main;
91.06/60.58	import qualified Maybe;
91.06/60.58	import qualified Prelude;
91.06/60.58	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
91.06/60.58	
91.06/60.58	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
91.06/60.58	(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
91.06/60.58	}
91.06/60.58	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
91.06/60.58	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
91.06/60.58	
91.06/60.58	addToFM0 old new = new;
91.06/60.58	
91.06/60.58	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
91.06/60.58	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
91.06/60.58	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;
91.06/60.58	
91.06/60.58	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;
91.06/60.58	
91.06/60.58	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);
91.06/60.58	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;
91.06/60.58	
91.06/60.58	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;
91.06/60.58	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);
91.06/60.58	
91.06/60.58	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);
91.06/60.58	
91.06/60.58	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
91.06/60.58	addToFM_C4 xwx xwy xwz xxu = addToFM_C3 xwx xwy xwz xxu;
91.06/60.58	
91.06/60.58	deleteMax :: Ord b => FiniteMap b a  ->  FiniteMap b a;
91.06/60.58	deleteMax (Branch key elt vvz fm_l EmptyFM) = fm_l;
91.06/60.58	deleteMax (Branch key elt vwu fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
91.06/60.58	
91.06/60.58	deleteMin :: Ord a => FiniteMap a b  ->  FiniteMap a b;
91.06/60.58	deleteMin (Branch key elt wyv EmptyFM fm_r) = fm_r;
91.06/60.58	deleteMin (Branch key elt wyw fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
91.06/60.58	
91.06/60.58	emptyFM :: FiniteMap b a;
91.06/60.58	emptyFM = EmptyFM;
91.06/60.58	
91.06/60.58	findMax :: FiniteMap a b  ->  (a,b);
91.06/60.58	findMax (Branch key elt vxz vyu EmptyFM) = (key,elt);
91.06/60.58	findMax (Branch key elt vyv vyw fm_r) = findMax fm_r;
91.06/60.58	
91.06/60.58	findMin :: FiniteMap b a  ->  (b,a);
91.06/60.58	findMin (Branch key elt wyy EmptyFM wyz) = (key,elt);
91.06/60.58	findMin (Branch key elt wzu fm_l wzv) = findMin fm_l;
91.06/60.58	
91.06/60.58	fmToList :: FiniteMap b a  ->  [(b,a)];
91.06/60.58	fmToList fm = foldFM fmToList0 [] fm;
91.06/60.58	
91.06/60.58	fmToList0 key elt rest = (key,elt) : rest;
91.06/60.58	
91.06/60.58	foldFM :: (c  ->  a  ->  b  ->  b)  ->  b  ->  FiniteMap c a  ->  b;
91.06/60.58	foldFM k z EmptyFM = z;
91.06/60.58	foldFM k z (Branch key elt wxv fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;
91.06/60.58	
91.06/60.58	glueBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
91.06/60.58	glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
91.06/60.58	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
91.06/60.58	glueBal fm1 fm2 = glueBal2 fm1 fm2;
91.06/60.58	
91.06/60.58	glueBal2 fm1 fm2 = glueBal2GlueBal1 fm1 fm2 fm1 fm2 (sizeFM fm2 > sizeFM fm1);
91.06/60.58	
91.06/60.58	glueBal2GlueBal0 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 yzy yzz) (glueBal2Mid_elt1 yzy yzz) (deleteMax fm1) fm2;
91.06/60.58	
91.06/60.58	glueBal2GlueBal1 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 yzy yzz) (glueBal2Mid_elt2 yzy yzz) fm1 (deleteMin fm2);
91.06/60.58	glueBal2GlueBal1 yzy yzz fm1 fm2 False = glueBal2GlueBal0 yzy yzz fm1 fm2 otherwise;
91.06/60.58	
91.06/60.58	glueBal2Mid_elt1 yzy yzz = glueBal2Mid_elt10 yzy yzz (glueBal2Vv2 yzy yzz);
91.06/60.58	
91.06/60.58	glueBal2Mid_elt10 yzy yzz (wuy,mid_elt1) = mid_elt1;
91.06/60.58	
91.06/60.58	glueBal2Mid_elt2 yzy yzz = glueBal2Mid_elt20 yzy yzz (glueBal2Vv3 yzy yzz);
91.06/60.58	
91.06/60.58	glueBal2Mid_elt20 yzy yzz (wux,mid_elt2) = mid_elt2;
91.06/60.58	
91.06/60.58	glueBal2Mid_key1 yzy yzz = glueBal2Mid_key10 yzy yzz (glueBal2Vv2 yzy yzz);
91.06/60.58	
91.06/60.58	glueBal2Mid_key10 yzy yzz (mid_key1,wuz) = mid_key1;
91.06/60.58	
91.06/60.58	glueBal2Mid_key2 yzy yzz = glueBal2Mid_key20 yzy yzz (glueBal2Vv3 yzy yzz);
91.06/60.58	
91.06/60.58	glueBal2Mid_key20 yzy yzz (mid_key2,wvu) = mid_key2;
91.06/60.58	
91.06/60.58	glueBal2Vv2 yzy yzz = findMax yzy;
91.06/60.58	
91.06/60.58	glueBal2Vv3 yzy yzz = findMin yzz;
91.06/60.58	
91.06/60.58	glueBal3 fm1 EmptyFM = fm1;
91.06/60.58	glueBal3 yvu yvv = glueBal2 yvu yvv;
91.06/60.58	
91.06/60.58	glueBal4 EmptyFM fm2 = fm2;
91.06/60.58	glueBal4 yvx yvy = glueBal3 yvx yvy;
91.06/60.58	
91.06/60.58	glueVBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
91.06/60.58	glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2;
91.06/60.58	glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM;
91.06/60.58	glueVBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu) = glueVBal3 (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu);
91.06/60.58	
91.06/60.58	glueVBal3 (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu) = glueVBal3GlueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * glueVBal3Size_l wvw wvx wvy wvz wwu www wwx wwy wwz wxu < glueVBal3Size_r wvw wvx wvy wvz wwu www wwx wwy wwz wxu);
91.06/60.58	
91.06/60.58	glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = glueBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu);
91.06/60.58	
91.06/60.58	glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch wvw wvx wvz (glueVBal wwu (Branch www wwx wwy wwz wxu));
91.06/60.58	glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu otherwise;
91.06/60.58	
91.06/60.58	glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch www wwx (glueVBal (Branch wvw wvx wvy wvz wwu) wwz) wxu;
91.06/60.58	glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw < glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw);
91.06/60.58	
91.06/60.58	glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zxz zyu zyv zyw zyx);
91.06/60.58	
91.06/60.58	glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zyy zyz zzu zzv zzw);
91.06/60.58	
91.06/60.58	glueVBal4 fm1 EmptyFM = fm1;
91.06/60.58	glueVBal4 yww ywx = glueVBal3 yww ywx;
91.06/60.58	
91.06/60.58	glueVBal5 EmptyFM fm2 = fm2;
91.06/60.58	glueVBal5 ywz yxu = glueVBal4 ywz yxu;
91.06/60.58	
91.06/60.58	intersectFM_C :: Ord a => (d  ->  b  ->  c)  ->  FiniteMap a d  ->  FiniteMap a b  ->  FiniteMap a c;
91.06/60.58	intersectFM_C combiner fm1 EmptyFM = intersectFM_C4 combiner fm1 EmptyFM;
91.06/60.58	intersectFM_C combiner EmptyFM fm2 = intersectFM_C3 combiner EmptyFM fm2;
91.06/60.58	intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right);
91.06/60.58	
91.06/60.58	intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2IntersectFM_C1 fm1 split_key combiner fm1 split_key elt2 wyx left right (Maybe.isJust (intersectFM_C2Maybe_elt1 fm1 split_key));
91.06/60.58	
91.06/60.58	intersectFM_C2Elt1 zww zwx = intersectFM_C2Elt10 zww zwx (intersectFM_C2Vv1 zww zwx);
91.06/60.58	
91.06/60.58	intersectFM_C2Elt10 zww zwx (Just elt1) = elt1;
91.06/60.58	
91.06/60.58	intersectFM_C2Gts zww zwx = splitGT zww zwx;
91.06/60.58	
91.06/60.58	intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right);
91.06/60.58	
91.06/60.58	intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner (intersectFM_C2Elt1 zww zwx) elt2) (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right);
91.06/60.58	intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right False = intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right otherwise;
91.06/60.58	
91.06/60.58	intersectFM_C2Lts zww zwx = splitLT zww zwx;
91.06/60.58	
91.06/60.58	intersectFM_C2Maybe_elt1 zww zwx = lookupFM zww zwx;
91.06/60.58	
91.06/60.58	intersectFM_C2Vv1 zww zwx = intersectFM_C2Maybe_elt1 zww zwx;
91.06/60.58	
91.06/60.58	intersectFM_C3 combiner EmptyFM fm2 = emptyFM;
91.06/60.58	intersectFM_C3 yyv yyw yyx = intersectFM_C2 yyv yyw yyx;
91.06/60.58	
91.06/60.58	intersectFM_C4 combiner fm1 EmptyFM = emptyFM;
91.06/60.58	intersectFM_C4 yyz yzu yzv = intersectFM_C3 yyz yzu yzv;
91.06/60.58	
91.06/60.58	lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
91.06/60.58	lookupFM EmptyFM key = lookupFM4 EmptyFM key;
91.06/60.58	lookupFM (Branch key elt wyu fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wyu fm_l fm_r) key_to_find;
91.06/60.58	
91.06/60.58	lookupFM0 key elt wyu fm_l fm_r key_to_find True = Just elt;
91.06/60.58	
91.06/60.58	lookupFM1 key elt wyu fm_l fm_r key_to_find True = lookupFM fm_r key_to_find;
91.06/60.58	lookupFM1 key elt wyu fm_l fm_r key_to_find False = lookupFM0 key elt wyu fm_l fm_r key_to_find otherwise;
91.06/60.58	
91.06/60.58	lookupFM2 key elt wyu fm_l fm_r key_to_find True = lookupFM fm_l key_to_find;
91.06/60.58	lookupFM2 key elt wyu fm_l fm_r key_to_find False = lookupFM1 key elt wyu fm_l fm_r key_to_find (key_to_find > key);
91.06/60.58	
91.06/60.58	lookupFM3 (Branch key elt wyu fm_l fm_r) key_to_find = lookupFM2 key elt wyu fm_l fm_r key_to_find (key_to_find < key);
91.06/60.58	
91.06/60.58	lookupFM4 EmptyFM key = Nothing;
91.06/60.58	lookupFM4 yxx yxy = lookupFM3 yxx yxy;
91.06/60.58	
91.06/60.58	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
91.06/60.58	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
91.06/60.58	
91.06/60.58	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);
91.06/60.58	
91.06/60.58	mkBalBranch6Double_L zvy zvz zwu zwv fm_l (Branch key_r elt_r vzx (Branch key_rl elt_rl vzy fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 zvy zvz fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
91.06/60.58	
91.06/60.58	mkBalBranch6Double_R zvy zvz zwu zwv (Branch key_l elt_l vyy fm_ll (Branch key_lr elt_lr vyz fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 zvy zvz fm_lrr fm_r);
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr);
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr True = mkBalBranch6Double_L zvy zvz zwu zwv fm_L fm_R;
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr True = mkBalBranch6Single_L zvy zvz zwu zwv fm_L fm_R;
91.06/60.58	mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr False = mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr otherwise;
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr);
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr True = mkBalBranch6Double_R zvy zvz zwu zwv fm_L fm_R;
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr True = mkBalBranch6Single_R zvy zvz zwu zwv fm_L fm_R;
91.06/60.58	mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr False = mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr otherwise;
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R fm_L;
91.06/60.58	mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R otherwise;
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R fm_R;
91.06/60.58	mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_l zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_r zvy zvz zwu zwv);
91.06/60.58	
91.06/60.58	mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
91.06/60.58	mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_r zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_l zvy zvz zwu zwv);
91.06/60.58	
91.06/60.58	mkBalBranch6Single_L zvy zvz zwu zwv fm_l (Branch key_r elt_r wuw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 zvy zvz fm_l fm_rl) fm_rr;
91.06/60.58	
91.06/60.58	mkBalBranch6Single_R zvy zvz zwu zwv (Branch key_l elt_l vyx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 zvy zvz fm_lr fm_r);
91.06/60.58	
91.06/60.58	mkBalBranch6Size_l zvy zvz zwu zwv = sizeFM zwv;
91.06/60.58	
91.06/60.58	mkBalBranch6Size_r zvy zvz zwu zwv = sizeFM zwu;
91.06/60.58	
91.06/60.58	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
91.06/60.58	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_r fm_l;
91.06/60.58	
91.06/60.58	mkBranchBalance_ok zwy zwz zxu = True;
91.06/60.58	
91.06/60.58	mkBranchLeft_ok zwy zwz zxu = mkBranchLeft_ok0 zwy zwz zxu zxu zwz zxu;
91.06/60.58	
91.06/60.58	mkBranchLeft_ok0 zwy zwz zxu fm_l key EmptyFM = True;
91.06/60.58	mkBranchLeft_ok0 zwy zwz zxu fm_l key (Branch left_key vwx vwy vwz vxu) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
91.06/60.58	
91.06/60.58	mkBranchLeft_ok0Biggest_left_key zzx = fst (findMax zzx);
91.06/60.58	
91.06/60.58	mkBranchLeft_size zwy zwz zxu = sizeFM zxu;
91.06/60.58	
91.06/60.58	mkBranchResult zxv zxw zxx zxy = Branch zxv zxw (mkBranchUnbox zxx zxv zxy (1 + mkBranchLeft_size zxx zxv zxy + mkBranchRight_size zxx zxv zxy)) zxy zxx;
91.06/60.58	
91.06/60.58	mkBranchRight_ok zwy zwz zxu = mkBranchRight_ok0 zwy zwz zxu zwy zwz zwy;
91.06/60.58	
91.06/60.58	mkBranchRight_ok0 zwy zwz zxu fm_r key EmptyFM = True;
91.06/60.58	mkBranchRight_ok0 zwy zwz zxu fm_r key (Branch right_key vxv vxw vxx vxy) = key < mkBranchRight_ok0Smallest_right_key fm_r;
91.06/60.58	
91.06/60.58	mkBranchRight_ok0Smallest_right_key zzy = fst (findMin zzy);
91.06/60.58	
91.06/60.58	mkBranchRight_size zwy zwz zxu = sizeFM zwy;
91.06/60.58	
91.06/60.58	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  a ( ->  (FiniteMap a b) (Int  ->  Int)));
91.06/60.58	mkBranchUnbox zwy zwz zxu x = x;
91.06/60.58	
91.06/60.58	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
91.06/60.58	mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
91.06/60.58	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
91.06/60.58	mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy) = mkVBalBranch3 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy);
91.06/60.58	
91.06/60.58	mkVBalBranch3 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy) = mkVBalBranch3MkVBalBranch2 vvu vvv vvw vvx vvy vuu vuv vuw vux vuy key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * mkVBalBranch3Size_l vvu vvv vvw vvx vvy vuu vuv vuw vux vuy < mkVBalBranch3Size_r vvu vvv vvw vvx vvy vuu vuv vuw vux vuy);
91.06/60.58	
91.06/60.58	mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBranch 13 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy);
91.06/60.58	
91.06/60.58	mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vuu vuv vux (mkVBalBranch key elt vuy (Branch vvu vvv vvw vvx vvy));
91.06/60.58	mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy otherwise;
91.06/60.58	
91.06/60.58	mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vvu vvv (mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) vvx) vvy;
91.06/60.58	mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx < mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx);
91.06/60.58	
91.06/60.58	mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuz zvu zvv zvw zvx);
91.06/60.58	
91.06/60.58	mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuu zuv zuw zux zuy);
91.06/60.58	
91.06/60.58	mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
91.06/60.58	mkVBalBranch4 xxy xxz xyu xyv = mkVBalBranch3 xxy xxz xyu xyv;
91.06/60.58	
91.06/60.58	mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
91.06/60.58	mkVBalBranch5 xyx xyy xyz xzu = mkVBalBranch4 xyx xyy xyz xzu;
91.06/60.58	
91.06/60.58	sIZE_RATIO :: Int;
91.06/60.58	sIZE_RATIO = 5;
91.06/60.58	
91.06/60.58	sizeFM :: FiniteMap a b  ->  Int;
91.06/60.58	sizeFM EmptyFM = 0;
91.06/60.58	sizeFM (Branch wxw wxx size wxy wxz) = size;
91.06/60.58	
91.06/60.58	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
91.06/60.58	splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
91.06/60.59	splitGT (Branch key elt vwv fm_l fm_r) split_key = splitGT3 (Branch key elt vwv fm_l fm_r) split_key;
91.06/60.59	
91.06/60.59	splitGT0 key elt vwv fm_l fm_r split_key True = fm_r;
91.06/60.59	
91.06/60.59	splitGT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
91.06/60.59	splitGT1 key elt vwv fm_l fm_r split_key False = splitGT0 key elt vwv fm_l fm_r split_key otherwise;
91.06/60.59	
91.06/60.59	splitGT2 key elt vwv fm_l fm_r split_key True = splitGT fm_r split_key;
91.06/60.59	splitGT2 key elt vwv fm_l fm_r split_key False = splitGT1 key elt vwv fm_l fm_r split_key (split_key < key);
91.06/60.59	
91.06/60.59	splitGT3 (Branch key elt vwv fm_l fm_r) split_key = splitGT2 key elt vwv fm_l fm_r split_key (split_key > key);
91.06/60.59	
91.06/60.59	splitGT4 EmptyFM split_key = emptyFM;
91.06/60.59	splitGT4 xzx xzy = splitGT3 xzx xzy;
91.06/60.59	
91.06/60.59	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
91.06/60.59	splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
91.06/60.59	splitLT (Branch key elt vww fm_l fm_r) split_key = splitLT3 (Branch key elt vww fm_l fm_r) split_key;
91.06/60.59	
91.06/60.59	splitLT0 key elt vww fm_l fm_r split_key True = fm_l;
91.06/60.59	
91.06/60.59	splitLT1 key elt vww fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
91.06/60.59	splitLT1 key elt vww fm_l fm_r split_key False = splitLT0 key elt vww fm_l fm_r split_key otherwise;
91.06/60.59	
91.06/60.59	splitLT2 key elt vww fm_l fm_r split_key True = splitLT fm_l split_key;
91.06/60.59	splitLT2 key elt vww fm_l fm_r split_key False = splitLT1 key elt vww fm_l fm_r split_key (split_key > key);
91.06/60.59	
91.06/60.59	splitLT3 (Branch key elt vww fm_l fm_r) split_key = splitLT2 key elt vww fm_l fm_r split_key (split_key < key);
91.06/60.59	
91.06/60.59	splitLT4 EmptyFM split_key = emptyFM;
91.06/60.59	splitLT4 yuv yuw = splitLT3 yuv yuw;
91.06/60.59	
91.06/60.59	unitFM :: b  ->  a  ->  FiniteMap b a;
91.06/60.59	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
91.06/60.59	
91.06/60.59	}
91.06/60.59	module Maybe where {
91.06/60.59	import qualified FiniteMap;
91.06/60.59	import qualified Main;
91.06/60.59	import qualified Prelude;
91.06/60.59	isJust :: Maybe a  ->  Bool;
91.06/60.59	isJust Nothing = False;
91.06/60.59	isJust wzw = True;
91.06/60.59	
91.06/60.59	}
91.06/60.59	module Main where {
91.06/60.59	import qualified FiniteMap;
91.06/60.59	import qualified Maybe;
91.06/60.59	import qualified Prelude;
91.06/60.59	}
91.06/60.59	
91.06/60.59	----------------------------------------
91.06/60.59	
91.06/60.59	(13) NumRed (SOUND)
91.06/60.59	Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero.
91.06/60.59	----------------------------------------
91.06/60.59	
91.06/60.59	(14)
91.06/60.59	Obligation:
91.06/60.59	mainModule Main 
91.06/60.59	module FiniteMap where {
91.06/60.59	import qualified Main;
91.06/60.59	import qualified Maybe;
91.06/60.59	import qualified Prelude;
91.06/60.59	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
91.06/60.59	
91.06/60.59	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
91.06/60.59	(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
91.06/60.59	}
91.06/60.59	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
91.06/60.59	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
91.06/60.59	
91.06/60.59	addToFM0 old new = new;
91.06/60.59	
91.06/60.59	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
91.06/60.59	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
91.06/60.59	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;
91.06/60.59	
91.06/60.59	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;
91.06/60.59	
91.06/60.59	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);
91.06/60.59	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;
91.06/60.59	
91.06/60.59	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;
91.06/60.59	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);
91.06/60.59	
91.06/60.59	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);
91.06/60.59	
91.06/60.59	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
91.06/60.59	addToFM_C4 xwx xwy xwz xxu = addToFM_C3 xwx xwy xwz xxu;
91.06/60.59	
91.06/60.59	deleteMax :: Ord b => FiniteMap b a  ->  FiniteMap b a;
91.06/60.59	deleteMax (Branch key elt vvz fm_l EmptyFM) = fm_l;
91.06/60.59	deleteMax (Branch key elt vwu fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
91.06/60.59	
91.06/60.59	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
91.06/60.59	deleteMin (Branch key elt wyv EmptyFM fm_r) = fm_r;
91.06/60.59	deleteMin (Branch key elt wyw fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
91.06/60.59	
91.06/60.59	emptyFM :: FiniteMap b a;
91.06/60.59	emptyFM = EmptyFM;
91.06/60.59	
91.06/60.59	findMax :: FiniteMap a b  ->  (a,b);
91.06/60.59	findMax (Branch key elt vxz vyu EmptyFM) = (key,elt);
91.06/60.59	findMax (Branch key elt vyv vyw fm_r) = findMax fm_r;
91.06/60.59	
91.06/60.59	findMin :: FiniteMap a b  ->  (a,b);
91.06/60.59	findMin (Branch key elt wyy EmptyFM wyz) = (key,elt);
91.06/60.59	findMin (Branch key elt wzu fm_l wzv) = findMin fm_l;
91.06/60.59	
91.06/60.59	fmToList :: FiniteMap b a  ->  [(b,a)];
91.06/60.59	fmToList fm = foldFM fmToList0 [] fm;
91.06/60.59	
91.06/60.59	fmToList0 key elt rest = (key,elt) : rest;
91.06/60.59	
91.06/60.59	foldFM :: (c  ->  a  ->  b  ->  b)  ->  b  ->  FiniteMap c a  ->  b;
91.06/60.59	foldFM k z EmptyFM = z;
91.06/60.59	foldFM k z (Branch key elt wxv fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;
91.06/60.59	
91.06/60.59	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
91.06/60.59	glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
91.06/60.59	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
91.06/60.59	glueBal fm1 fm2 = glueBal2 fm1 fm2;
91.06/60.59	
91.06/60.59	glueBal2 fm1 fm2 = glueBal2GlueBal1 fm1 fm2 fm1 fm2 (sizeFM fm2 > sizeFM fm1);
91.06/60.59	
91.06/60.59	glueBal2GlueBal0 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 yzy yzz) (glueBal2Mid_elt1 yzy yzz) (deleteMax fm1) fm2;
91.06/60.59	
91.06/60.59	glueBal2GlueBal1 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 yzy yzz) (glueBal2Mid_elt2 yzy yzz) fm1 (deleteMin fm2);
91.06/60.59	glueBal2GlueBal1 yzy yzz fm1 fm2 False = glueBal2GlueBal0 yzy yzz fm1 fm2 otherwise;
91.06/60.59	
91.06/60.59	glueBal2Mid_elt1 yzy yzz = glueBal2Mid_elt10 yzy yzz (glueBal2Vv2 yzy yzz);
91.06/60.59	
91.06/60.59	glueBal2Mid_elt10 yzy yzz (wuy,mid_elt1) = mid_elt1;
91.06/60.59	
91.06/60.59	glueBal2Mid_elt2 yzy yzz = glueBal2Mid_elt20 yzy yzz (glueBal2Vv3 yzy yzz);
91.06/60.59	
91.06/60.59	glueBal2Mid_elt20 yzy yzz (wux,mid_elt2) = mid_elt2;
91.06/60.59	
91.06/60.59	glueBal2Mid_key1 yzy yzz = glueBal2Mid_key10 yzy yzz (glueBal2Vv2 yzy yzz);
91.06/60.59	
91.06/60.59	glueBal2Mid_key10 yzy yzz (mid_key1,wuz) = mid_key1;
91.06/60.59	
91.06/60.59	glueBal2Mid_key2 yzy yzz = glueBal2Mid_key20 yzy yzz (glueBal2Vv3 yzy yzz);
91.06/60.59	
91.06/60.59	glueBal2Mid_key20 yzy yzz (mid_key2,wvu) = mid_key2;
91.06/60.59	
91.06/60.59	glueBal2Vv2 yzy yzz = findMax yzy;
91.06/60.59	
91.06/60.59	glueBal2Vv3 yzy yzz = findMin yzz;
91.06/60.59	
91.06/60.59	glueBal3 fm1 EmptyFM = fm1;
91.06/60.59	glueBal3 yvu yvv = glueBal2 yvu yvv;
91.06/60.59	
91.06/60.59	glueBal4 EmptyFM fm2 = fm2;
91.06/60.59	glueBal4 yvx yvy = glueBal3 yvx yvy;
91.06/60.59	
91.06/60.59	glueVBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
91.06/60.59	glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2;
91.06/60.59	glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM;
91.06/60.59	glueVBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu) = glueVBal3 (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu);
91.06/60.59	
91.06/60.59	glueVBal3 (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu) = glueVBal3GlueVBal2 wvw wvx wvy wvz wwu www wwx wwy wwz wxu wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * glueVBal3Size_l wvw wvx wvy wvz wwu www wwx wwy wwz wxu < glueVBal3Size_r wvw wvx wvy wvz wwu www wwx wwy wwz wxu);
91.06/60.59	
91.06/60.59	glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = glueBal (Branch wvw wvx wvy wvz wwu) (Branch www wwx wwy wwz wxu);
91.06/60.59	
91.06/60.59	glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch wvw wvx wvz (glueVBal wwu (Branch www wwx wwy wwz wxu));
91.06/60.59	glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu otherwise;
91.06/60.59	
91.06/60.59	glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu True = mkBalBranch www wwx (glueVBal (Branch wvw wvx wvy wvz wwu) wwz) wxu;
91.06/60.59	glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu False = glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw wvw wvx wvy wvz wwu www wwx wwy wwz wxu (sIZE_RATIO * glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw < glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw);
91.06/60.59	
91.06/60.59	glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zxz zyu zyv zyw zyx);
91.06/60.59	
91.06/60.59	glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zyy zyz zzu zzv zzw);
91.06/60.59	
91.06/60.59	glueVBal4 fm1 EmptyFM = fm1;
91.06/60.59	glueVBal4 yww ywx = glueVBal3 yww ywx;
91.06/60.59	
91.06/60.59	glueVBal5 EmptyFM fm2 = fm2;
91.06/60.59	glueVBal5 ywz yxu = glueVBal4 ywz yxu;
91.06/60.59	
91.06/60.59	intersectFM_C :: Ord a => (c  ->  b  ->  d)  ->  FiniteMap a c  ->  FiniteMap a b  ->  FiniteMap a d;
91.06/60.59	intersectFM_C combiner fm1 EmptyFM = intersectFM_C4 combiner fm1 EmptyFM;
91.06/60.59	intersectFM_C combiner EmptyFM fm2 = intersectFM_C3 combiner EmptyFM fm2;
91.06/60.59	intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right);
91.06/60.59	
91.06/60.59	intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2IntersectFM_C1 fm1 split_key combiner fm1 split_key elt2 wyx left right (Maybe.isJust (intersectFM_C2Maybe_elt1 fm1 split_key));
91.06/60.59	
91.06/60.59	intersectFM_C2Elt1 zww zwx = intersectFM_C2Elt10 zww zwx (intersectFM_C2Vv1 zww zwx);
91.06/60.59	
91.06/60.59	intersectFM_C2Elt10 zww zwx (Just elt1) = elt1;
91.06/60.59	
91.06/60.59	intersectFM_C2Gts zww zwx = splitGT zww zwx;
91.06/60.59	
91.06/60.59	intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right);
91.06/60.59	
91.06/60.59	intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner (intersectFM_C2Elt1 zww zwx) elt2) (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right);
91.06/60.59	intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right False = intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right otherwise;
91.06/60.59	
91.06/60.59	intersectFM_C2Lts zww zwx = splitLT zww zwx;
91.06/60.59	
91.06/60.59	intersectFM_C2Maybe_elt1 zww zwx = lookupFM zww zwx;
91.06/60.59	
91.06/60.59	intersectFM_C2Vv1 zww zwx = intersectFM_C2Maybe_elt1 zww zwx;
91.06/60.59	
91.06/60.59	intersectFM_C3 combiner EmptyFM fm2 = emptyFM;
91.06/60.59	intersectFM_C3 yyv yyw yyx = intersectFM_C2 yyv yyw yyx;
91.06/60.59	
91.06/60.59	intersectFM_C4 combiner fm1 EmptyFM = emptyFM;
91.06/60.59	intersectFM_C4 yyz yzu yzv = intersectFM_C3 yyz yzu yzv;
91.06/60.59	
91.06/60.59	lookupFM :: Ord a => FiniteMap a b  ->  a  ->  Maybe b;
91.06/60.59	lookupFM EmptyFM key = lookupFM4 EmptyFM key;
91.06/60.59	lookupFM (Branch key elt wyu fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wyu fm_l fm_r) key_to_find;
91.06/60.59	
91.06/60.59	lookupFM0 key elt wyu fm_l fm_r key_to_find True = Just elt;
91.06/60.59	
91.06/60.59	lookupFM1 key elt wyu fm_l fm_r key_to_find True = lookupFM fm_r key_to_find;
91.06/60.59	lookupFM1 key elt wyu fm_l fm_r key_to_find False = lookupFM0 key elt wyu fm_l fm_r key_to_find otherwise;
91.06/60.59	
91.06/60.59	lookupFM2 key elt wyu fm_l fm_r key_to_find True = lookupFM fm_l key_to_find;
91.06/60.59	lookupFM2 key elt wyu fm_l fm_r key_to_find False = lookupFM1 key elt wyu fm_l fm_r key_to_find (key_to_find > key);
91.06/60.59	
91.06/60.59	lookupFM3 (Branch key elt wyu fm_l fm_r) key_to_find = lookupFM2 key elt wyu fm_l fm_r key_to_find (key_to_find < key);
91.06/60.59	
91.06/60.59	lookupFM4 EmptyFM key = Nothing;
91.06/60.59	lookupFM4 yxx yxy = lookupFM3 yxx yxy;
91.06/60.59	
91.06/60.59	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
91.06/60.59	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
91.06/60.59	
91.06/60.59	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)));
91.06/60.59	
91.06/60.59	mkBalBranch6Double_L zvy zvz zwu zwv fm_l (Branch key_r elt_r vzx (Branch key_rl elt_rl vzy 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))))))) zvy zvz fm_l fm_rll) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))) key_r elt_r fm_rlr fm_rr);
91.06/60.59	
91.06/60.59	mkBalBranch6Double_R zvy zvz zwu zwv (Branch key_l elt_l vyy fm_ll (Branch key_lr elt_lr vyz 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))))))))))))) zvy zvz fm_lrr fm_r);
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr);
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr True = mkBalBranch6Double_L zvy zvz zwu zwv fm_L fm_R;
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr True = mkBalBranch6Single_L zvy zvz zwu zwv fm_L fm_R;
91.06/60.59	mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr False = mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr otherwise;
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch vzz wuu wuv fm_rl fm_rr) = mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R vzz wuu wuv fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr);
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr);
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr True = mkBalBranch6Double_R zvy zvz zwu zwv fm_L fm_R;
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr True = mkBalBranch6Single_R zvy zvz zwu zwv fm_L fm_R;
91.06/60.59	mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr False = mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr otherwise;
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch vzu vzv vzw fm_ll fm_lr) = mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R vzu vzv vzw fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll);
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R;
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R fm_L;
91.06/60.59	mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R otherwise;
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R fm_R;
91.06/60.59	mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_l zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_r zvy zvz zwu zwv);
91.06/60.59	
91.06/60.59	mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R;
91.06/60.59	mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_r zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_l zvy zvz zwu zwv);
91.06/60.59	
91.06/60.59	mkBalBranch6Single_L zvy zvz zwu zwv fm_l (Branch key_r elt_r wuw fm_rl fm_rr) = mkBranch (Pos (Succ (Succ (Succ Zero)))) key_r elt_r (mkBranch (Pos (Succ (Succ (Succ (Succ Zero))))) zvy zvz fm_l fm_rl) fm_rr;
91.06/60.59	
91.06/60.59	mkBalBranch6Single_R zvy zvz zwu zwv (Branch key_l elt_l vyx 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)))))))))) zvy zvz fm_lr fm_r);
91.06/60.59	
91.06/60.59	mkBalBranch6Size_l zvy zvz zwu zwv = sizeFM zwv;
91.06/60.59	
91.06/60.59	mkBalBranch6Size_r zvy zvz zwu zwv = sizeFM zwu;
91.06/60.59	
91.06/60.59	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
91.06/60.59	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_r fm_l;
91.06/60.59	
91.06/60.59	mkBranchBalance_ok zwy zwz zxu = True;
91.06/60.59	
91.06/60.59	mkBranchLeft_ok zwy zwz zxu = mkBranchLeft_ok0 zwy zwz zxu zxu zwz zxu;
91.06/60.59	
91.06/60.59	mkBranchLeft_ok0 zwy zwz zxu fm_l key EmptyFM = True;
91.06/60.59	mkBranchLeft_ok0 zwy zwz zxu fm_l key (Branch left_key vwx vwy vwz vxu) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
91.06/60.59	
91.06/60.59	mkBranchLeft_ok0Biggest_left_key zzx = fst (findMax zzx);
91.06/60.59	
91.06/60.59	mkBranchLeft_size zwy zwz zxu = sizeFM zxu;
91.06/60.59	
91.06/60.59	mkBranchResult zxv zxw zxx zxy = Branch zxv zxw (mkBranchUnbox zxx zxv zxy (Pos (Succ Zero) + mkBranchLeft_size zxx zxv zxy + mkBranchRight_size zxx zxv zxy)) zxy zxx;
91.06/60.59	
91.06/60.59	mkBranchRight_ok zwy zwz zxu = mkBranchRight_ok0 zwy zwz zxu zwy zwz zwy;
91.06/60.59	
91.06/60.59	mkBranchRight_ok0 zwy zwz zxu fm_r key EmptyFM = True;
91.06/60.59	mkBranchRight_ok0 zwy zwz zxu fm_r key (Branch right_key vxv vxw vxx vxy) = key < mkBranchRight_ok0Smallest_right_key fm_r;
91.06/60.59	
91.06/60.59	mkBranchRight_ok0Smallest_right_key zzy = fst (findMin zzy);
91.06/60.59	
91.06/60.59	mkBranchRight_size zwy zwz zxu = sizeFM zwy;
91.06/60.59	
91.06/60.59	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  a ( ->  (FiniteMap a b) (Int  ->  Int)));
91.06/60.59	mkBranchUnbox zwy zwz zxu x = x;
91.06/60.59	
91.06/60.59	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
91.06/60.59	mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
91.06/60.59	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
91.06/60.59	mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy) = mkVBalBranch3 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy);
91.06/60.59	
91.06/60.59	mkVBalBranch3 key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy) = mkVBalBranch3MkVBalBranch2 vvu vvv vvw vvx vvy vuu vuv vuw vux vuy key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * mkVBalBranch3Size_l vvu vvv vvw vvx vvy vuu vuv vuw vux vuy < mkVBalBranch3Size_r vvu vvv vvw vvx vvy vuu vuv vuw vux vuy);
91.06/60.59	
91.06/60.59	mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))))) key elt (Branch vuu vuv vuw vux vuy) (Branch vvu vvv vvw vvx vvy);
91.06/60.59	
91.06/60.59	mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vuu vuv vux (mkVBalBranch key elt vuy (Branch vvu vvv vvw vvx vvy));
91.06/60.59	mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy otherwise;
91.06/60.59	
91.06/60.59	mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy True = mkBalBranch vvu vvv (mkVBalBranch key elt (Branch vuu vuv vuw vux vuy) vvx) vvy;
91.06/60.59	mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy False = mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vuu vuv vuw vux vuy vvu vvv vvw vvx vvy (sIZE_RATIO * mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx < mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx);
91.06/60.59	
91.06/60.59	mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuz zvu zvv zvw zvx);
91.06/60.59	
91.06/60.59	mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuu zuv zuw zux zuy);
91.06/60.59	
91.06/60.59	mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
91.06/60.59	mkVBalBranch4 xxy xxz xyu xyv = mkVBalBranch3 xxy xxz xyu xyv;
91.06/60.59	
91.06/60.59	mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
91.06/60.59	mkVBalBranch5 xyx xyy xyz xzu = mkVBalBranch4 xyx xyy xyz xzu;
91.06/60.59	
91.06/60.59	sIZE_RATIO :: Int;
91.06/60.59	sIZE_RATIO = Pos (Succ (Succ (Succ (Succ (Succ Zero)))));
91.06/60.59	
91.06/60.59	sizeFM :: FiniteMap b a  ->  Int;
91.06/60.59	sizeFM EmptyFM = Pos Zero;
91.06/60.59	sizeFM (Branch wxw wxx size wxy wxz) = size;
91.06/60.59	
91.06/60.59	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
91.06/60.59	splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
91.06/60.59	splitGT (Branch key elt vwv fm_l fm_r) split_key = splitGT3 (Branch key elt vwv fm_l fm_r) split_key;
91.06/60.59	
91.06/60.59	splitGT0 key elt vwv fm_l fm_r split_key True = fm_r;
91.06/60.59	
91.06/60.59	splitGT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
91.06/60.59	splitGT1 key elt vwv fm_l fm_r split_key False = splitGT0 key elt vwv fm_l fm_r split_key otherwise;
91.06/60.59	
91.06/60.59	splitGT2 key elt vwv fm_l fm_r split_key True = splitGT fm_r split_key;
91.06/60.59	splitGT2 key elt vwv fm_l fm_r split_key False = splitGT1 key elt vwv fm_l fm_r split_key (split_key < key);
91.06/60.59	
91.06/60.59	splitGT3 (Branch key elt vwv fm_l fm_r) split_key = splitGT2 key elt vwv fm_l fm_r split_key (split_key > key);
91.06/60.59	
91.06/60.59	splitGT4 EmptyFM split_key = emptyFM;
91.06/60.59	splitGT4 xzx xzy = splitGT3 xzx xzy;
91.06/60.59	
91.06/60.59	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
91.06/60.59	splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
91.06/60.59	splitLT (Branch key elt vww fm_l fm_r) split_key = splitLT3 (Branch key elt vww fm_l fm_r) split_key;
91.06/60.59	
91.06/60.59	splitLT0 key elt vww fm_l fm_r split_key True = fm_l;
91.06/60.59	
91.06/60.59	splitLT1 key elt vww fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
91.06/60.59	splitLT1 key elt vww fm_l fm_r split_key False = splitLT0 key elt vww fm_l fm_r split_key otherwise;
91.06/60.59	
91.06/60.59	splitLT2 key elt vww fm_l fm_r split_key True = splitLT fm_l split_key;
91.06/60.59	splitLT2 key elt vww fm_l fm_r split_key False = splitLT1 key elt vww fm_l fm_r split_key (split_key > key);
91.06/60.59	
91.06/60.59	splitLT3 (Branch key elt vww fm_l fm_r) split_key = splitLT2 key elt vww fm_l fm_r split_key (split_key < key);
91.06/60.59	
91.06/60.59	splitLT4 EmptyFM split_key = emptyFM;
91.06/60.59	splitLT4 yuv yuw = splitLT3 yuv yuw;
91.06/60.59	
91.06/60.59	unitFM :: b  ->  a  ->  FiniteMap b a;
91.06/60.59	unitFM key elt = Branch key elt (Pos (Succ Zero)) emptyFM emptyFM;
91.06/60.59	
91.06/60.59	}
91.06/60.59	module Maybe where {
91.06/60.59	import qualified FiniteMap;
91.06/60.59	import qualified Main;
91.06/60.59	import qualified Prelude;
91.06/60.59	isJust :: Maybe a  ->  Bool;
91.06/60.59	isJust Nothing = False;
91.06/60.59	isJust wzw = True;
91.06/60.59	
91.06/60.59	}
91.06/60.59	module Main where {
91.06/60.59	import qualified FiniteMap;
91.06/60.59	import qualified Maybe;
91.06/60.59	import qualified Prelude;
91.06/60.59	}
91.06/60.62	EOF