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