188.92/161.89	MAYBE
191.26/162.57	proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
191.26/162.57	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
191.26/162.57	
191.26/162.57	
191.26/162.57	H-Termination with start terms of the given HASKELL could not be shown:
191.26/162.57	
191.26/162.57	(0) HASKELL
191.26/162.57	(1) LR [EQUIVALENT, 0 ms]
191.26/162.57	(2) HASKELL
191.26/162.57	(3) CR [EQUIVALENT, 0 ms]
191.26/162.57	(4) HASKELL
191.26/162.57	(5) BR [EQUIVALENT, 0 ms]
191.26/162.57	(6) HASKELL
191.26/162.57	(7) COR [EQUIVALENT, 11 ms]
191.26/162.57	(8) HASKELL
191.26/162.57	(9) LetRed [EQUIVALENT, 0 ms]
191.26/162.57	(10) HASKELL
191.26/162.57	(11) NumRed [SOUND, 12 ms]
191.26/162.57	(12) HASKELL
191.26/162.57	
191.26/162.57	
191.26/162.57	----------------------------------------
191.26/162.57	
191.26/162.57	(0)
191.26/162.57	Obligation:
191.26/162.57	mainModule Main 
191.26/162.57	module FiniteMap where {
191.26/162.57	import qualified Main;
191.26/162.57	import qualified Maybe;
191.26/162.57	import qualified Prelude;
191.26/162.57	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
191.26/162.57	
191.26/162.57	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
191.26/162.57	}
191.26/162.57	addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
191.26/162.57	addToFM fm key elt = addToFM_C (\old new ->new) fm key elt;
191.26/162.57	
191.26/162.57	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
191.26/162.57	addToFM_C combiner EmptyFM key elt = unitFM key elt;
191.26/162.57	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
191.26/162.57	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
191.26/162.57	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
191.26/162.57	
191.26/162.57	emptyFM :: FiniteMap a b;
191.26/162.57	emptyFM = EmptyFM;
191.26/162.57	
191.26/162.57	findMax :: FiniteMap a b  ->  (a,b);
191.26/162.57	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
191.26/162.57	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
191.26/162.57	
191.26/162.57	findMin :: FiniteMap a b  ->  (a,b);
191.26/162.57	findMin (Branch key elt _ EmptyFM _) = (key,elt);
191.26/162.57	findMin (Branch key elt _ fm_l _) = findMin fm_l;
191.26/162.57	
191.26/162.57	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
191.26/162.57	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
191.26/162.57	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
191.26/162.57	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
191.26/162.57	 | otherwise -> double_L fm_L fm_R; 
191.26/162.57	 } 
191.26/162.57	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
191.26/162.57	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
191.26/162.57	 | otherwise -> double_R fm_L fm_R; 
191.26/162.57	 } 
191.26/162.57	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
191.26/162.57	double_L fm_l (Branch key_r elt_r _ (Branch key_rl elt_rl _ fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
191.26/162.57	double_R (Branch key_l elt_l _ fm_ll (Branch key_lr elt_lr _ fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
191.26/162.57	single_L fm_l (Branch key_r elt_r _ fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
191.26/162.57	single_R (Branch key_l elt_l _ fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
191.26/162.57	size_l = sizeFM fm_L;
191.26/162.57	size_r = sizeFM fm_R;
191.26/162.57	 };
191.26/162.57	
191.26/162.57	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
191.26/162.57	mkBranch which key elt fm_l fm_r = let { 
191.26/162.57	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
191.26/162.57	} in result where { 
191.26/162.57	balance_ok = True;
191.26/162.57	left_ok = case fm_l of { 
191.26/162.57	EmptyFM-> True; 
191.26/162.57	Branch left_key _ _ _ _-> let { 
191.26/162.57	biggest_left_key = fst (findMax fm_l);
191.26/162.57	} in biggest_left_key < key; 
191.26/162.57	 } ;
191.26/162.57	left_size = sizeFM fm_l;
191.26/162.57	right_ok = case fm_r of { 
191.26/162.57	EmptyFM-> True; 
191.26/162.57	Branch right_key _ _ _ _-> let { 
191.26/162.57	smallest_right_key = fst (findMin fm_r);
191.26/162.57	} in key < smallest_right_key; 
191.26/162.57	 } ;
191.26/162.57	right_size = sizeFM fm_r;
191.26/162.57	unbox :: Int  ->  Int;
191.26/162.57	unbox x = x;
191.26/162.57	 };
191.26/162.57	
191.26/162.57	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
191.26/162.57	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
191.26/162.57	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
191.26/162.57	mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr
191.26/162.57	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
191.26/162.57	 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
191.26/162.57	size_l = sizeFM fm_l;
191.26/162.57	size_r = sizeFM fm_r;
191.26/162.57	 };
191.26/162.57	
191.26/162.57	plusFM :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
191.26/162.57	plusFM EmptyFM fm2 = fm2;
191.26/162.57	plusFM fm1 EmptyFM = fm1;
191.26/162.57	plusFM fm1 (Branch split_key elt1 _ left right) = mkVBalBranch split_key elt1 (plusFM lts left) (plusFM gts right) where { 
191.26/162.57	gts = splitGT fm1 split_key;
191.26/162.57	lts = splitLT fm1 split_key;
191.26/162.57	 };
191.26/162.57	
191.26/162.57	sIZE_RATIO :: Int;
191.26/162.57	sIZE_RATIO = 5;
191.26/162.57	
191.26/162.57	sizeFM :: FiniteMap a b  ->  Int;
191.26/162.57	sizeFM EmptyFM = 0;
191.26/162.57	sizeFM (Branch _ _ size _ _) = size;
191.26/162.57	
191.26/162.57	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
191.26/162.57	splitGT EmptyFM split_key = emptyFM;
191.26/162.57	splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
191.26/162.57	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
191.26/162.57	 | otherwise = fm_r;
191.26/162.57	
191.26/162.57	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
191.26/162.57	splitLT EmptyFM split_key = emptyFM;
191.26/162.57	splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
191.26/162.57	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
191.26/162.57	 | otherwise = fm_l;
191.26/162.57	
191.26/162.57	unitFM :: b  ->  a  ->  FiniteMap b a;
191.26/162.57	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
191.26/162.57	
191.26/162.57	}
191.26/162.57	module Maybe where {
191.26/162.57	import qualified FiniteMap;
191.26/162.57	import qualified Main;
191.26/162.57	import qualified Prelude;
191.26/162.57	}
191.26/162.57	module Main where {
191.26/162.57	import qualified FiniteMap;
191.26/162.57	import qualified Maybe;
191.26/162.57	import qualified Prelude;
191.26/162.57	}
191.26/162.57	
191.26/162.57	----------------------------------------
191.26/162.57	
191.26/162.57	(1) LR (EQUIVALENT)
191.26/162.57	Lambda Reductions:
191.26/162.57	The following Lambda expression
191.26/162.57	"\oldnew->new"
191.26/162.57	is transformed to
191.26/162.57	"addToFM0 old new = new;
191.26/162.57	"
191.26/162.57	
191.26/162.57	----------------------------------------
191.26/162.57	
191.26/162.57	(2)
191.26/162.57	Obligation:
191.26/162.57	mainModule Main 
191.26/162.57	module FiniteMap where {
191.26/162.57	import qualified Main;
191.26/162.57	import qualified Maybe;
191.26/162.57	import qualified Prelude;
191.26/162.57	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
191.26/162.57	
191.26/162.57	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
191.26/162.57	}
191.26/162.57	addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
191.26/162.57	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
191.26/162.57	
191.26/162.57	addToFM0 old new = new;
191.26/162.57	
191.26/162.57	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
191.26/162.57	addToFM_C combiner EmptyFM key elt = unitFM key elt;
191.26/162.57	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
191.26/162.57	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
191.26/162.57	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
191.26/162.57	
191.26/162.57	emptyFM :: FiniteMap a b;
191.26/162.57	emptyFM = EmptyFM;
191.26/162.57	
191.26/162.57	findMax :: FiniteMap a b  ->  (a,b);
191.26/162.57	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
191.26/162.57	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
191.26/162.57	
191.26/162.57	findMin :: FiniteMap b a  ->  (b,a);
191.26/162.57	findMin (Branch key elt _ EmptyFM _) = (key,elt);
191.26/162.57	findMin (Branch key elt _ fm_l _) = findMin fm_l;
191.26/162.57	
191.26/162.57	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
191.26/162.57	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
191.26/162.57	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
191.26/162.57	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
191.26/162.57	 | otherwise -> double_L fm_L fm_R; 
191.26/162.57	 } 
191.26/162.57	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
191.26/162.57	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
191.26/162.57	 | otherwise -> double_R fm_L fm_R; 
191.26/162.57	 } 
191.26/162.57	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
191.26/162.57	double_L fm_l (Branch key_r elt_r _ (Branch key_rl elt_rl _ fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
191.26/162.57	double_R (Branch key_l elt_l _ fm_ll (Branch key_lr elt_lr _ fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
191.26/162.57	single_L fm_l (Branch key_r elt_r _ fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
191.26/162.57	single_R (Branch key_l elt_l _ fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
191.26/162.57	size_l = sizeFM fm_L;
191.26/162.57	size_r = sizeFM fm_R;
191.26/162.57	 };
191.26/162.57	
191.26/162.57	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
191.26/162.57	mkBranch which key elt fm_l fm_r = let { 
191.39/162.57	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
191.39/162.57	} in result where { 
191.39/162.57	balance_ok = True;
191.39/162.57	left_ok = case fm_l of { 
191.39/162.57	EmptyFM-> True; 
191.39/162.57	Branch left_key _ _ _ _-> let { 
191.39/162.57	biggest_left_key = fst (findMax fm_l);
191.39/162.57	} in biggest_left_key < key; 
191.39/162.57	 } ;
191.39/162.57	left_size = sizeFM fm_l;
191.39/162.57	right_ok = case fm_r of { 
191.39/162.57	EmptyFM-> True; 
191.39/162.57	Branch right_key _ _ _ _-> let { 
191.39/162.57	smallest_right_key = fst (findMin fm_r);
191.39/162.57	} in key < smallest_right_key; 
191.39/162.57	 } ;
191.39/162.57	right_size = sizeFM fm_r;
191.39/162.57	unbox :: Int  ->  Int;
191.39/162.57	unbox x = x;
191.39/162.57	 };
191.39/162.57	
191.39/162.57	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
191.39/162.57	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
191.39/162.57	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
191.39/162.57	mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr
191.39/162.57	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
191.39/162.57	 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
191.39/162.57	size_l = sizeFM fm_l;
191.39/162.57	size_r = sizeFM fm_r;
191.39/162.57	 };
191.39/162.57	
191.39/162.57	plusFM :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
191.39/162.57	plusFM EmptyFM fm2 = fm2;
191.39/162.57	plusFM fm1 EmptyFM = fm1;
191.39/162.57	plusFM fm1 (Branch split_key elt1 _ left right) = mkVBalBranch split_key elt1 (plusFM lts left) (plusFM gts right) where { 
191.39/162.57	gts = splitGT fm1 split_key;
191.39/162.57	lts = splitLT fm1 split_key;
191.39/162.57	 };
191.39/162.57	
191.39/162.57	sIZE_RATIO :: Int;
191.39/162.57	sIZE_RATIO = 5;
191.39/162.57	
191.39/162.57	sizeFM :: FiniteMap a b  ->  Int;
191.39/162.57	sizeFM EmptyFM = 0;
191.39/162.57	sizeFM (Branch _ _ size _ _) = size;
191.39/162.57	
191.39/162.57	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
191.39/162.57	splitGT EmptyFM split_key = emptyFM;
191.39/162.57	splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
191.39/162.57	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
191.39/162.57	 | otherwise = fm_r;
191.39/162.57	
191.39/162.57	splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
191.39/162.57	splitLT EmptyFM split_key = emptyFM;
191.39/162.57	splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
191.39/162.57	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
191.39/162.57	 | otherwise = fm_l;
191.39/162.57	
191.39/162.57	unitFM :: b  ->  a  ->  FiniteMap b a;
191.39/162.57	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
191.39/162.57	
191.39/162.57	}
191.39/162.57	module Maybe where {
191.39/162.57	import qualified FiniteMap;
191.39/162.57	import qualified Main;
191.39/162.57	import qualified Prelude;
191.39/162.57	}
191.39/162.57	module Main where {
191.39/162.57	import qualified FiniteMap;
191.39/162.57	import qualified Maybe;
191.39/162.57	import qualified Prelude;
191.39/162.57	}
191.39/162.57	
191.39/162.57	----------------------------------------
191.39/162.57	
191.39/162.57	(3) CR (EQUIVALENT)
191.39/162.57	Case Reductions:
191.39/162.57	The following Case expression
191.39/162.57	"case fm_r of {
191.39/162.57	EmptyFM  -> True;
191.39/162.57	Branch right_key _ _ _ _  -> let {
191.39/162.57	smallest_right_key  = fst (findMin fm_r);
191.39/162.57	} in key < smallest_right_key}
191.39/162.57	"
191.39/162.57	is transformed to
191.39/162.57	"right_ok0 fm_r key EmptyFM = True;
191.39/162.57	right_ok0 fm_r key (Branch right_key _ _ _ _) = let {
191.39/162.57	smallest_right_key  = fst (findMin fm_r);
191.39/162.57	} in key < smallest_right_key;
191.39/162.57	"
191.39/162.57	The following Case expression
191.39/162.57	"case fm_l of {
191.39/162.57	EmptyFM  -> True;
191.39/162.57	Branch left_key _ _ _ _  -> let {
191.39/162.57	biggest_left_key  = fst (findMax fm_l);
191.39/162.57	} in biggest_left_key < key}
191.39/162.57	"
191.39/162.57	is transformed to
191.39/162.57	"left_ok0 fm_l key EmptyFM = True;
191.39/162.57	left_ok0 fm_l key (Branch left_key _ _ _ _) = let {
191.39/162.57	biggest_left_key  = fst (findMax fm_l);
191.39/162.57	} in biggest_left_key < key;
191.39/162.57	"
191.39/162.57	The following Case expression
191.39/162.57	"case fm_R of {
191.39/162.57	Branch _ _ _ fm_rl fm_rr |sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R}
191.39/162.57	"
191.39/162.57	is transformed to
191.39/162.57	"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.39/162.57	"
191.39/162.57	The following Case expression
191.39/162.57	"case fm_L of {
191.39/162.57	Branch _ _ _ fm_ll fm_lr |sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R}
191.39/162.57	"
191.39/162.57	is transformed to
191.39/162.57	"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.39/162.57	"
191.39/162.57	
191.39/162.57	----------------------------------------
191.39/162.57	
191.39/162.57	(4)
191.39/162.57	Obligation:
191.39/162.57	mainModule Main 
191.39/162.57	module FiniteMap where {
191.39/162.57	import qualified Main;
191.39/162.57	import qualified Maybe;
191.39/162.57	import qualified Prelude;
191.39/162.57	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
191.39/162.57	
191.39/162.57	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
191.39/162.57	}
191.39/162.57	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
191.39/162.57	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
191.39/162.57	
191.39/162.57	addToFM0 old new = new;
191.39/162.57	
191.39/162.57	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
191.39/162.57	addToFM_C combiner EmptyFM key elt = unitFM key elt;
191.39/162.57	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
191.39/162.57	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
191.39/162.57	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
191.39/162.57	
191.39/162.57	emptyFM :: FiniteMap b a;
191.39/162.57	emptyFM = EmptyFM;
191.39/162.57	
191.39/162.57	findMax :: FiniteMap a b  ->  (a,b);
191.39/162.57	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
191.39/162.57	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
191.39/162.57	
191.39/162.57	findMin :: FiniteMap b a  ->  (b,a);
191.39/162.57	findMin (Branch key elt _ EmptyFM _) = (key,elt);
191.39/162.57	findMin (Branch key elt _ fm_l _) = findMin fm_l;
191.39/162.57	
191.39/162.57	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
191.39/162.57	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
191.39/162.57	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
191.39/162.57	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
191.39/162.57	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
191.39/162.57	double_L fm_l (Branch key_r elt_r _ (Branch key_rl elt_rl _ fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
191.39/162.57	double_R (Branch key_l elt_l _ fm_ll (Branch key_lr elt_lr _ fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
191.39/162.57	mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
191.39/162.57	 | otherwise = double_L fm_L fm_R;
191.39/162.57	mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
191.39/162.57	 | otherwise = double_R fm_L fm_R;
191.39/162.57	single_L fm_l (Branch key_r elt_r _ fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
191.39/162.57	single_R (Branch key_l elt_l _ fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
191.39/162.57	size_l = sizeFM fm_L;
191.39/162.57	size_r = sizeFM fm_R;
191.39/162.57	 };
191.39/162.57	
191.39/162.57	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
191.39/162.57	mkBranch which key elt fm_l fm_r = let { 
191.39/162.57	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
191.39/162.57	} in result where { 
191.39/162.57	balance_ok = True;
191.39/162.57	left_ok = left_ok0 fm_l key fm_l;
191.39/162.57	left_ok0 fm_l key EmptyFM = True;
191.39/162.57	left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 
191.39/162.57	biggest_left_key = fst (findMax fm_l);
191.39/162.57	} in biggest_left_key < key;
191.39/162.57	left_size = sizeFM fm_l;
191.39/162.57	right_ok = right_ok0 fm_r key fm_r;
191.39/162.57	right_ok0 fm_r key EmptyFM = True;
191.39/162.57	right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 
191.39/162.57	smallest_right_key = fst (findMin fm_r);
191.39/162.57	} in key < smallest_right_key;
191.39/162.57	right_size = sizeFM fm_r;
191.39/162.57	unbox :: Int  ->  Int;
191.39/162.57	unbox x = x;
191.39/162.57	 };
191.39/162.57	
191.39/162.57	mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
191.39/162.57	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
191.39/162.57	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
191.39/162.57	mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr
191.39/162.57	 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
191.39/162.57	 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
191.39/162.57	size_l = sizeFM fm_l;
191.39/162.57	size_r = sizeFM fm_r;
191.39/162.57	 };
191.39/162.57	
191.39/162.57	plusFM :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
191.39/162.57	plusFM EmptyFM fm2 = fm2;
191.39/162.57	plusFM fm1 EmptyFM = fm1;
191.39/162.57	plusFM fm1 (Branch split_key elt1 _ left right) = mkVBalBranch split_key elt1 (plusFM lts left) (plusFM gts right) where { 
191.39/162.57	gts = splitGT fm1 split_key;
191.39/162.57	lts = splitLT fm1 split_key;
191.39/162.57	 };
191.39/162.57	
191.39/162.57	sIZE_RATIO :: Int;
191.39/162.57	sIZE_RATIO = 5;
191.39/162.57	
191.39/162.57	sizeFM :: FiniteMap a b  ->  Int;
191.39/162.57	sizeFM EmptyFM = 0;
191.39/162.57	sizeFM (Branch _ _ size _ _) = size;
191.39/162.57	
191.39/162.57	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
191.39/162.57	splitGT EmptyFM split_key = emptyFM;
191.39/162.57	splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
191.39/162.57	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
191.39/162.57	 | otherwise = fm_r;
191.39/162.57	
191.39/162.57	splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
191.39/162.57	splitLT EmptyFM split_key = emptyFM;
191.39/162.57	splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
191.39/162.57	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
191.39/162.57	 | otherwise = fm_l;
191.39/162.57	
191.39/162.57	unitFM :: a  ->  b  ->  FiniteMap a b;
191.39/162.57	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
191.39/162.57	
191.39/162.57	}
191.39/162.57	module Maybe where {
191.39/162.57	import qualified FiniteMap;
191.39/162.57	import qualified Main;
191.39/162.57	import qualified Prelude;
191.39/162.57	}
191.39/162.57	module Main where {
191.39/162.57	import qualified FiniteMap;
191.39/162.57	import qualified Maybe;
191.39/162.57	import qualified Prelude;
191.39/162.57	}
191.39/162.57	
191.39/162.57	----------------------------------------
191.39/162.57	
191.39/162.57	(5) BR (EQUIVALENT)
191.39/162.57	Replaced joker patterns by fresh variables and removed binding patterns.
191.39/162.57	
191.39/162.57	Binding Reductions:
191.39/162.57	The bind variable of the following binding Pattern
191.39/162.57	"fm_l@(Branch wv ww wx wy wz)"
191.39/162.57	is replaced by the following term
191.39/162.57	"Branch wv ww wx wy wz"
191.39/162.57	The bind variable of the following binding Pattern
191.39/162.57	"fm_r@(Branch xv xw xx xy xz)"
191.39/162.57	is replaced by the following term
191.39/162.57	"Branch xv xw xx xy xz"
191.39/162.57	
191.39/162.57	----------------------------------------
191.39/162.57	
191.39/162.57	(6)
191.39/162.57	Obligation:
191.39/162.57	mainModule Main 
191.39/162.57	module FiniteMap where {
191.39/162.57	import qualified Main;
191.39/162.57	import qualified Maybe;
191.39/162.57	import qualified Prelude;
191.39/162.57	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
191.39/162.57	
191.39/162.57	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
191.39/162.57	}
191.39/162.57	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
191.39/162.57	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
191.39/162.57	
191.39/162.57	addToFM0 old new = new;
191.39/162.57	
191.39/162.57	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
191.39/162.57	addToFM_C combiner EmptyFM key elt = unitFM key elt;
191.39/162.57	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
191.39/162.57	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
191.39/162.57	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
191.39/162.57	
191.39/162.57	emptyFM :: FiniteMap b a;
191.39/162.57	emptyFM = EmptyFM;
191.39/162.57	
191.39/162.57	findMax :: FiniteMap b a  ->  (b,a);
191.39/162.57	findMax (Branch key elt zy zz EmptyFM) = (key,elt);
191.39/162.57	findMax (Branch key elt vuu vuv fm_r) = findMax fm_r;
191.39/162.57	
191.39/162.57	findMin :: FiniteMap a b  ->  (a,b);
191.39/162.57	findMin (Branch key elt vxu EmptyFM vxv) = (key,elt);
191.39/162.57	findMin (Branch key elt vxw fm_l vxx) = findMin fm_l;
191.39/162.57	
191.39/162.57	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
191.39/162.57	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
191.39/162.57	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
191.39/162.57	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
191.39/162.57	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
191.39/162.57	double_L fm_l (Branch key_r elt_r vvw (Branch key_rl elt_rl vvx 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.39/162.57	double_R (Branch key_l elt_l vux fm_ll (Branch key_lr elt_lr vuy 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.39/162.57	mkBalBranch0 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
191.39/162.57	 | otherwise = double_L fm_L fm_R;
191.39/162.57	mkBalBranch1 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
191.39/162.57	 | otherwise = double_R fm_L fm_R;
191.39/162.57	single_L fm_l (Branch key_r elt_r vwv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
191.39/162.57	single_R (Branch key_l elt_l vuw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
191.39/162.57	size_l = sizeFM fm_L;
191.39/162.57	size_r = sizeFM fm_R;
191.39/162.57	 };
191.39/162.57	
191.39/162.57	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
191.39/162.57	mkBranch which key elt fm_l fm_r = let { 
191.39/162.57	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
191.39/162.57	} in result where { 
191.39/162.57	balance_ok = True;
191.39/162.57	left_ok = left_ok0 fm_l key fm_l;
191.39/162.57	left_ok0 fm_l key EmptyFM = True;
191.39/162.57	left_ok0 fm_l key (Branch left_key yw yx yy yz) = let { 
191.39/162.57	biggest_left_key = fst (findMax fm_l);
191.39/162.57	} in biggest_left_key < key;
191.39/162.57	left_size = sizeFM fm_l;
191.39/162.57	right_ok = right_ok0 fm_r key fm_r;
191.39/162.57	right_ok0 fm_r key EmptyFM = True;
191.39/162.57	right_ok0 fm_r key (Branch right_key zu zv zw zx) = let { 
191.39/162.57	smallest_right_key = fst (findMin fm_r);
191.39/162.57	} in key < smallest_right_key;
191.39/162.57	right_size = sizeFM fm_r;
191.39/162.57	unbox :: Int  ->  Int;
191.39/162.57	unbox x = x;
191.39/162.57	 };
191.39/162.57	
191.39/162.57	mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
191.39/162.57	mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
191.39/162.57	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
191.39/162.57	mkVBalBranch key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz)  | sIZE_RATIO * size_l < size_r = mkBalBranch xv xw (mkVBalBranch key elt (Branch wv ww wx wy wz) xy) xz
191.39/162.57	 | sIZE_RATIO * size_r < size_l = mkBalBranch wv ww wy (mkVBalBranch key elt wz (Branch xv xw xx xy xz))
191.39/162.57	 | otherwise = mkBranch 13 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz) where { 
191.39/162.57	size_l = sizeFM (Branch wv ww wx wy wz);
191.39/162.57	size_r = sizeFM (Branch xv xw xx xy xz);
191.39/162.57	 };
191.39/162.57	
191.39/162.57	plusFM :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
191.39/162.57	plusFM EmptyFM fm2 = fm2;
191.39/162.57	plusFM fm1 EmptyFM = fm1;
191.39/162.57	plusFM fm1 (Branch split_key elt1 vz left right) = mkVBalBranch split_key elt1 (plusFM lts left) (plusFM gts right) where { 
191.39/162.57	gts = splitGT fm1 split_key;
191.39/162.57	lts = splitLT fm1 split_key;
191.39/162.57	 };
191.39/162.57	
191.39/162.57	sIZE_RATIO :: Int;
191.39/162.57	sIZE_RATIO = 5;
191.39/162.57	
191.39/162.57	sizeFM :: FiniteMap b a  ->  Int;
191.39/162.57	sizeFM EmptyFM = 0;
191.39/162.57	sizeFM (Branch vww vwx size vwy vwz) = size;
191.39/162.57	
191.39/162.57	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
191.39/162.57	splitGT EmptyFM split_key = emptyFM;
191.39/162.57	splitGT (Branch key elt yu fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
191.39/162.57	 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
191.39/162.57	 | otherwise = fm_r;
191.39/162.57	
191.39/162.57	splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
191.39/162.57	splitLT EmptyFM split_key = emptyFM;
191.39/162.57	splitLT (Branch key elt yv fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
191.39/162.57	 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
191.39/162.57	 | otherwise = fm_l;
191.39/162.57	
191.39/162.57	unitFM :: a  ->  b  ->  FiniteMap a b;
191.39/162.57	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
191.39/162.57	
191.39/162.57	}
191.39/162.57	module Maybe where {
191.39/162.57	import qualified FiniteMap;
191.39/162.57	import qualified Main;
191.39/162.57	import qualified Prelude;
191.39/162.57	}
191.39/162.57	module Main where {
191.39/162.57	import qualified FiniteMap;
191.39/162.57	import qualified Maybe;
191.39/162.57	import qualified Prelude;
191.39/162.57	}
191.39/162.57	
191.39/162.57	----------------------------------------
191.39/162.57	
191.39/162.57	(7) COR (EQUIVALENT)
191.39/162.57	Cond Reductions:
191.39/162.57	The following Function with conditions
191.39/162.57	"undefined |Falseundefined;
191.39/162.57	"
191.39/162.57	is transformed to
191.39/162.57	"undefined  = undefined1;
191.39/162.57	"
191.39/162.57	"undefined0 True = undefined;
191.39/162.57	"
191.39/162.57	"undefined1  = undefined0 False;
191.39/162.57	"
191.39/162.57	The following Function with conditions
191.39/162.57	"addToFM_C combiner EmptyFM key elt = unitFM key elt;
191.39/162.57	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt|new_key < keymkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r|new_key > keymkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)|otherwiseBranch new_key (combiner elt new_elt) size fm_l fm_r;
191.39/162.57	"
191.39/162.57	is transformed to
191.39/162.57	"addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
191.39/162.57	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt;
191.39/162.57	"
191.39/162.57	"addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r;
191.39/162.57	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt (new_key > key);
191.39/162.57	"
191.39/162.57	"addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt True = Branch new_key (combiner elt new_elt) size fm_l fm_r;
191.39/162.57	"
191.39/162.57	"addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt);
191.39/162.57	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt otherwise;
191.39/162.57	"
191.39/162.57	"addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt (new_key < key);
191.39/162.57	"
191.39/162.57	"addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
192.13/162.81	addToFM_C4 vyu vyv vyw vyx = addToFM_C3 vyu vyv vyw vyx;
192.13/162.81	"
192.13/162.81	The following Function with conditions
192.13/162.81	"mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
192.13/162.81	mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
192.13/162.81	mkVBalBranch key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz)|sIZE_RATIO * size_l < size_rmkBalBranch xv xw (mkVBalBranch key elt (Branch wv ww wx wy wz) xy) xz|sIZE_RATIO * size_r < size_lmkBalBranch wv ww wy (mkVBalBranch key elt wz (Branch xv xw xx xy xz))|otherwisemkBranch 13 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz) where {
192.13/162.81	size_l  = sizeFM (Branch wv ww wx wy wz);
192.13/162.81	;
192.13/162.81	size_r  = sizeFM (Branch xv xw xx xy xz);
192.13/162.81	} 
192.13/162.81	;
192.13/162.81	"
192.13/162.81	is transformed to
192.13/162.81	"mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
192.13/162.81	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
192.13/162.81	mkVBalBranch key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz) = mkVBalBranch3 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz);
192.13/162.81	"
192.13/162.81	"mkVBalBranch3 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz) = mkVBalBranch2 key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * size_l < size_r) where {
192.13/162.81	mkVBalBranch0 key elt wv ww wx wy wz xv xw xx xy xz True = mkBranch 13 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz);
192.13/162.81	;
192.13/162.81	mkVBalBranch1 key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch wv ww wy (mkVBalBranch key elt wz (Branch xv xw xx xy xz));
192.13/162.81	mkVBalBranch1 key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch0 key elt wv ww wx wy wz xv xw xx xy xz otherwise;
192.13/162.81	;
192.13/162.81	mkVBalBranch2 key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch xv xw (mkVBalBranch key elt (Branch wv ww wx wy wz) xy) xz;
192.13/162.81	mkVBalBranch2 key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch1 key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * size_r < size_l);
192.13/162.81	;
192.13/162.81	size_l  = sizeFM (Branch wv ww wx wy wz);
192.13/162.81	;
192.13/162.81	size_r  = sizeFM (Branch xv xw xx xy xz);
192.13/162.81	} 
192.13/162.81	;
192.13/162.81	"
192.13/162.81	"mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
192.13/162.81	mkVBalBranch4 vzv vzw vzx vzy = mkVBalBranch3 vzv vzw vzx vzy;
192.13/162.81	"
192.13/162.81	"mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
192.13/162.81	mkVBalBranch5 wuu wuv wuw wux = mkVBalBranch4 wuu wuv wuw wux;
192.13/162.81	"
192.13/162.81	The following Function with conditions
192.13/162.81	"splitGT EmptyFM split_key = emptyFM;
192.13/162.81	splitGT (Branch key elt yu 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.13/162.81	"
192.13/162.81	is transformed to
192.13/162.81	"splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
192.13/162.81	splitGT (Branch key elt yu fm_l fm_r) split_key = splitGT3 (Branch key elt yu fm_l fm_r) split_key;
192.13/162.81	"
192.13/162.81	"splitGT0 key elt yu fm_l fm_r split_key True = fm_r;
192.13/162.81	"
192.13/162.81	"splitGT1 key elt yu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
192.13/162.81	splitGT1 key elt yu fm_l fm_r split_key False = splitGT0 key elt yu fm_l fm_r split_key otherwise;
192.13/162.81	"
192.13/162.81	"splitGT2 key elt yu fm_l fm_r split_key True = splitGT fm_r split_key;
192.13/162.81	splitGT2 key elt yu fm_l fm_r split_key False = splitGT1 key elt yu fm_l fm_r split_key (split_key < key);
192.13/162.81	"
192.13/162.81	"splitGT3 (Branch key elt yu fm_l fm_r) split_key = splitGT2 key elt yu fm_l fm_r split_key (split_key > key);
192.13/162.81	"
192.13/162.81	"splitGT4 EmptyFM split_key = emptyFM;
192.13/162.81	splitGT4 wvu wvv = splitGT3 wvu wvv;
192.13/162.81	"
192.13/162.81	The following Function with conditions
192.13/162.81	"splitLT EmptyFM split_key = emptyFM;
192.13/162.81	splitLT (Branch key elt yv 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.13/162.81	"
192.13/162.81	is transformed to
192.13/162.81	"splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
192.13/162.81	splitLT (Branch key elt yv fm_l fm_r) split_key = splitLT3 (Branch key elt yv fm_l fm_r) split_key;
192.13/162.81	"
192.13/162.81	"splitLT1 key elt yv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
192.13/162.81	splitLT1 key elt yv fm_l fm_r split_key False = splitLT0 key elt yv fm_l fm_r split_key otherwise;
192.13/162.81	"
192.13/162.81	"splitLT0 key elt yv fm_l fm_r split_key True = fm_l;
192.13/162.81	"
192.13/162.81	"splitLT2 key elt yv fm_l fm_r split_key True = splitLT fm_l split_key;
192.13/162.81	splitLT2 key elt yv fm_l fm_r split_key False = splitLT1 key elt yv fm_l fm_r split_key (split_key > key);
192.13/162.81	"
192.13/162.81	"splitLT3 (Branch key elt yv fm_l fm_r) split_key = splitLT2 key elt yv fm_l fm_r split_key (split_key < key);
192.13/162.81	"
192.13/162.81	"splitLT4 EmptyFM split_key = emptyFM;
192.13/162.81	splitLT4 wvy wvz = splitLT3 wvy wvz;
192.13/162.81	"
192.13/162.81	The following Function with conditions
192.13/162.81	"mkBalBranch1 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
192.13/162.81	"
192.13/162.81	is transformed to
192.13/162.81	"mkBalBranch1 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr);
192.13/162.81	"
192.13/162.81	"mkBalBranch10 fm_L fm_R vuz vvu vvv fm_ll fm_lr True = double_R fm_L fm_R;
192.13/162.81	"
192.13/162.81	"mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr True = single_R fm_L fm_R;
192.13/162.81	mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vuz vvu vvv fm_ll fm_lr otherwise;
192.13/162.81	"
192.13/162.81	"mkBalBranch12 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
192.13/162.81	"
192.13/162.81	The following Function with conditions
192.13/162.81	"mkBalBranch0 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
192.13/162.81	"
192.13/162.81	is transformed to
192.13/162.81	"mkBalBranch0 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr);
192.13/162.81	"
192.13/162.81	"mkBalBranch00 fm_L fm_R vvy vvz vwu fm_rl fm_rr True = double_L fm_L fm_R;
192.13/162.81	"
192.13/162.81	"mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr True = single_L fm_L fm_R;
192.13/162.81	mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vvy vvz vwu fm_rl fm_rr otherwise;
192.13/162.81	"
192.13/162.81	"mkBalBranch02 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
192.13/162.81	"
192.13/162.81	The following Function with conditions
192.13/162.81	"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.13/162.81	double_L fm_l (Branch key_r elt_r vvw (Branch key_rl elt_rl vvx 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.13/162.81	;
192.13/162.81	double_R (Branch key_l elt_l vux fm_ll (Branch key_lr elt_lr vuy 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.13/162.81	;
192.13/162.81	mkBalBranch0 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
192.13/162.81	;
192.13/162.81	mkBalBranch1 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
192.13/162.81	;
192.13/162.81	single_L fm_l (Branch key_r elt_r vwv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
192.13/162.81	;
192.13/162.81	single_R (Branch key_l elt_l vuw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
192.13/162.81	;
192.13/162.81	size_l  = sizeFM fm_L;
192.13/162.81	;
192.13/162.81	size_r  = sizeFM fm_R;
192.13/162.81	} 
192.13/162.81	;
192.13/162.81	"
192.13/162.81	is transformed to
192.13/162.81	"mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
192.13/162.81	"
192.13/162.81	"mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
192.13/162.81	double_L fm_l (Branch key_r elt_r vvw (Branch key_rl elt_rl vvx 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.13/162.81	;
192.13/162.81	double_R (Branch key_l elt_l vux fm_ll (Branch key_lr elt_lr vuy 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.13/162.81	;
192.13/162.81	mkBalBranch0 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr);
192.13/162.81	;
192.13/162.81	mkBalBranch00 fm_L fm_R vvy vvz vwu fm_rl fm_rr True = double_L fm_L fm_R;
192.13/162.81	;
192.13/162.81	mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr True = single_L fm_L fm_R;
192.13/162.81	mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vvy vvz vwu fm_rl fm_rr otherwise;
192.13/162.81	;
192.13/162.81	mkBalBranch02 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
192.13/162.81	;
192.13/162.81	mkBalBranch1 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr);
192.13/162.81	;
192.13/162.81	mkBalBranch10 fm_L fm_R vuz vvu vvv fm_ll fm_lr True = double_R fm_L fm_R;
192.13/162.81	;
192.13/162.81	mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr True = single_R fm_L fm_R;
192.13/162.81	mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vuz vvu vvv fm_ll fm_lr otherwise;
192.13/162.81	;
192.13/162.81	mkBalBranch12 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
192.13/162.81	;
192.13/162.81	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
192.13/162.81	;
192.13/162.81	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
192.13/162.81	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
192.13/162.81	;
192.13/162.81	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
192.13/162.81	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
192.13/162.81	;
192.13/162.81	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
192.13/162.81	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
192.13/162.81	;
192.13/162.81	single_L fm_l (Branch key_r elt_r vwv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
192.13/162.81	;
192.13/162.81	single_R (Branch key_l elt_l vuw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
192.13/162.81	;
192.13/162.81	size_l  = sizeFM fm_L;
192.13/162.81	;
192.13/162.81	size_r  = sizeFM fm_R;
192.13/162.81	} 
192.13/162.81	;
192.13/162.81	"
192.13/162.81	
192.13/162.81	----------------------------------------
192.13/162.81	
192.13/162.81	(8)
192.13/162.81	Obligation:
192.13/162.81	mainModule Main 
192.13/162.81	module FiniteMap where {
192.13/162.81	import qualified Main;
192.13/162.81	import qualified Maybe;
192.13/162.81	import qualified Prelude;
192.13/162.81	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
192.13/162.81	
192.13/162.81	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
192.13/162.81	}
192.13/162.81	addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
192.13/162.81	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
192.13/162.81	
192.13/162.81	addToFM0 old new = new;
192.13/162.81	
192.13/162.81	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
192.13/162.81	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
192.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	
192.13/162.81	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
192.13/162.81	addToFM_C4 vyu vyv vyw vyx = addToFM_C3 vyu vyv vyw vyx;
192.13/162.81	
192.13/162.81	emptyFM :: FiniteMap a b;
192.13/162.81	emptyFM = EmptyFM;
192.13/162.81	
192.13/162.81	findMax :: FiniteMap b a  ->  (b,a);
192.13/162.81	findMax (Branch key elt zy zz EmptyFM) = (key,elt);
192.13/162.81	findMax (Branch key elt vuu vuv fm_r) = findMax fm_r;
192.13/162.81	
192.13/162.81	findMin :: FiniteMap a b  ->  (a,b);
192.13/162.81	findMin (Branch key elt vxu EmptyFM vxv) = (key,elt);
192.13/162.81	findMin (Branch key elt vxw fm_l vxx) = findMin fm_l;
192.13/162.81	
192.13/162.81	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
192.13/162.81	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
192.13/162.81	
192.13/162.81	mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 
192.13/162.81	double_L fm_l (Branch key_r elt_r vvw (Branch key_rl elt_rl vvx 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.13/162.81	double_R (Branch key_l elt_l vux fm_ll (Branch key_lr elt_lr vuy 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.13/162.81	mkBalBranch0 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr);
192.13/162.81	mkBalBranch00 fm_L fm_R vvy vvz vwu fm_rl fm_rr True = double_L fm_L fm_R;
192.13/162.81	mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr True = single_L fm_L fm_R;
192.13/162.81	mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vvy vvz vwu fm_rl fm_rr otherwise;
192.13/162.81	mkBalBranch02 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
192.13/162.81	mkBalBranch1 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr);
192.13/162.81	mkBalBranch10 fm_L fm_R vuz vvu vvv fm_ll fm_lr True = double_R fm_L fm_R;
192.13/162.81	mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr True = single_R fm_L fm_R;
192.13/162.81	mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vuz vvu vvv fm_ll fm_lr otherwise;
192.13/162.81	mkBalBranch12 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
192.13/162.81	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
192.13/162.81	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
192.13/162.81	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
192.13/162.81	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
192.13/162.81	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
192.13/162.81	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
192.13/162.81	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
192.13/162.81	single_L fm_l (Branch key_r elt_r vwv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
192.13/162.81	single_R (Branch key_l elt_l vuw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
192.13/162.81	size_l = sizeFM fm_L;
192.13/162.81	size_r = sizeFM fm_R;
192.13/162.81	 };
192.13/162.81	
192.13/162.81	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
192.13/162.81	mkBranch which key elt fm_l fm_r = let { 
192.13/162.81	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
192.13/162.81	} in result where { 
192.13/162.81	balance_ok = True;
192.13/162.81	left_ok = left_ok0 fm_l key fm_l;
192.13/162.81	left_ok0 fm_l key EmptyFM = True;
192.13/162.81	left_ok0 fm_l key (Branch left_key yw yx yy yz) = let { 
192.13/162.81	biggest_left_key = fst (findMax fm_l);
192.13/162.81	} in biggest_left_key < key;
192.13/162.81	left_size = sizeFM fm_l;
192.13/162.81	right_ok = right_ok0 fm_r key fm_r;
192.13/162.81	right_ok0 fm_r key EmptyFM = True;
192.13/162.81	right_ok0 fm_r key (Branch right_key zu zv zw zx) = let { 
192.13/162.81	smallest_right_key = fst (findMin fm_r);
192.13/162.81	} in key < smallest_right_key;
192.13/162.81	right_size = sizeFM fm_r;
192.13/162.81	unbox :: Int  ->  Int;
192.13/162.81	unbox x = x;
192.13/162.81	 };
192.13/162.81	
192.13/162.81	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
192.13/162.81	mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
192.13/162.81	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
192.13/162.81	mkVBalBranch key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz) = mkVBalBranch3 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz);
192.13/162.81	
192.13/162.81	mkVBalBranch3 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz) = mkVBalBranch2 key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * size_l < size_r) where { 
192.13/162.81	mkVBalBranch0 key elt wv ww wx wy wz xv xw xx xy xz True = mkBranch 13 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz);
192.13/162.81	mkVBalBranch1 key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch wv ww wy (mkVBalBranch key elt wz (Branch xv xw xx xy xz));
192.13/162.81	mkVBalBranch1 key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch0 key elt wv ww wx wy wz xv xw xx xy xz otherwise;
192.13/162.81	mkVBalBranch2 key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch xv xw (mkVBalBranch key elt (Branch wv ww wx wy wz) xy) xz;
192.13/162.81	mkVBalBranch2 key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch1 key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * size_r < size_l);
192.13/162.81	size_l = sizeFM (Branch wv ww wx wy wz);
192.13/162.81	size_r = sizeFM (Branch xv xw xx xy xz);
192.13/162.81	 };
192.13/162.81	
192.13/162.81	mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
192.13/162.81	mkVBalBranch4 vzv vzw vzx vzy = mkVBalBranch3 vzv vzw vzx vzy;
192.13/162.81	
192.13/162.81	mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
192.13/162.81	mkVBalBranch5 wuu wuv wuw wux = mkVBalBranch4 wuu wuv wuw wux;
192.13/162.81	
192.13/162.81	plusFM :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
192.13/162.81	plusFM EmptyFM fm2 = fm2;
192.13/162.81	plusFM fm1 EmptyFM = fm1;
192.13/162.81	plusFM fm1 (Branch split_key elt1 vz left right) = mkVBalBranch split_key elt1 (plusFM lts left) (plusFM gts right) where { 
192.13/162.81	gts = splitGT fm1 split_key;
192.13/162.81	lts = splitLT fm1 split_key;
192.13/162.81	 };
192.13/162.81	
192.13/162.81	sIZE_RATIO :: Int;
192.13/162.81	sIZE_RATIO = 5;
192.13/162.81	
192.13/162.81	sizeFM :: FiniteMap b a  ->  Int;
192.13/162.81	sizeFM EmptyFM = 0;
192.13/162.81	sizeFM (Branch vww vwx size vwy vwz) = size;
192.13/162.81	
192.13/162.81	splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
192.13/162.81	splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
192.13/162.81	splitGT (Branch key elt yu fm_l fm_r) split_key = splitGT3 (Branch key elt yu fm_l fm_r) split_key;
192.13/162.81	
192.13/162.81	splitGT0 key elt yu fm_l fm_r split_key True = fm_r;
192.13/162.81	
192.13/162.81	splitGT1 key elt yu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
192.13/162.81	splitGT1 key elt yu fm_l fm_r split_key False = splitGT0 key elt yu fm_l fm_r split_key otherwise;
192.13/162.81	
192.13/162.81	splitGT2 key elt yu fm_l fm_r split_key True = splitGT fm_r split_key;
192.13/162.81	splitGT2 key elt yu fm_l fm_r split_key False = splitGT1 key elt yu fm_l fm_r split_key (split_key < key);
192.13/162.81	
192.13/162.81	splitGT3 (Branch key elt yu fm_l fm_r) split_key = splitGT2 key elt yu fm_l fm_r split_key (split_key > key);
192.13/162.81	
192.13/162.81	splitGT4 EmptyFM split_key = emptyFM;
192.13/162.81	splitGT4 wvu wvv = splitGT3 wvu wvv;
192.13/162.81	
192.13/162.81	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
192.13/162.81	splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
192.13/162.81	splitLT (Branch key elt yv fm_l fm_r) split_key = splitLT3 (Branch key elt yv fm_l fm_r) split_key;
192.13/162.81	
192.13/162.81	splitLT0 key elt yv fm_l fm_r split_key True = fm_l;
192.13/162.81	
192.13/162.81	splitLT1 key elt yv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
192.13/162.81	splitLT1 key elt yv fm_l fm_r split_key False = splitLT0 key elt yv fm_l fm_r split_key otherwise;
192.13/162.81	
192.13/162.81	splitLT2 key elt yv fm_l fm_r split_key True = splitLT fm_l split_key;
192.13/162.81	splitLT2 key elt yv fm_l fm_r split_key False = splitLT1 key elt yv fm_l fm_r split_key (split_key > key);
192.13/162.81	
192.13/162.81	splitLT3 (Branch key elt yv fm_l fm_r) split_key = splitLT2 key elt yv fm_l fm_r split_key (split_key < key);
192.13/162.81	
192.13/162.81	splitLT4 EmptyFM split_key = emptyFM;
192.13/162.81	splitLT4 wvy wvz = splitLT3 wvy wvz;
192.13/162.81	
192.13/162.81	unitFM :: a  ->  b  ->  FiniteMap a b;
192.13/162.81	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
192.13/162.81	
192.13/162.81	}
192.13/162.81	module Maybe where {
192.13/162.81	import qualified FiniteMap;
192.13/162.81	import qualified Main;
192.13/162.81	import qualified Prelude;
192.13/162.81	}
192.13/162.81	module Main where {
192.13/162.81	import qualified FiniteMap;
192.13/162.81	import qualified Maybe;
192.13/162.81	import qualified Prelude;
192.13/162.81	}
192.13/162.81	
192.13/162.81	----------------------------------------
192.13/162.81	
192.13/162.81	(9) LetRed (EQUIVALENT)
192.13/162.81	Let/Where Reductions:
192.13/162.81	The bindings of the following Let/Where expression
192.13/162.81	"mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
192.13/162.81	double_L fm_l (Branch key_r elt_r vvw (Branch key_rl elt_rl vvx 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.13/162.81	;
192.13/162.81	double_R (Branch key_l elt_l vux fm_ll (Branch key_lr elt_lr vuy 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.13/162.81	;
192.13/162.81	mkBalBranch0 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr);
192.13/162.81	;
192.13/162.81	mkBalBranch00 fm_L fm_R vvy vvz vwu fm_rl fm_rr True = double_L fm_L fm_R;
192.13/162.81	;
192.13/162.81	mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr True = single_L fm_L fm_R;
192.13/162.81	mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vvy vvz vwu fm_rl fm_rr otherwise;
192.13/162.81	;
192.13/162.81	mkBalBranch02 fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vvy vvz vwu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
192.13/162.81	;
192.13/162.81	mkBalBranch1 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr);
192.13/162.81	;
192.13/162.81	mkBalBranch10 fm_L fm_R vuz vvu vvv fm_ll fm_lr True = double_R fm_L fm_R;
192.13/162.81	;
192.13/162.81	mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr True = single_R fm_L fm_R;
192.13/162.81	mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vuz vvu vvv fm_ll fm_lr otherwise;
192.13/162.81	;
192.13/162.81	mkBalBranch12 fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vuz vvu vvv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
192.13/162.81	;
192.13/162.81	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
192.13/162.81	;
192.13/162.81	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
192.13/162.81	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
192.13/162.81	;
192.13/162.81	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
192.13/162.81	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
192.13/162.81	;
192.13/162.81	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
192.13/162.81	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
192.13/162.81	;
192.13/162.81	single_L fm_l (Branch key_r elt_r vwv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
192.13/162.81	;
192.13/162.81	single_R (Branch key_l elt_l vuw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
192.13/162.81	;
192.13/162.81	size_l  = sizeFM fm_L;
192.13/162.81	;
192.13/162.81	size_r  = sizeFM fm_R;
192.13/162.81	} 
192.13/162.81	"
192.13/162.81	are unpacked to the following functions on top level
192.13/162.81	"mkBalBranch6MkBalBranch5 www wwx wwy wwz key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
192.13/162.81	mkBalBranch6MkBalBranch5 www wwx wwy wwz key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 www wwx wwy wwz key elt fm_L fm_R (mkBalBranch6Size_r www wwx wwy wwz > sIZE_RATIO * mkBalBranch6Size_l www wwx wwy wwz);
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch2 www wwx wwy wwz key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch4 www wwx wwy wwz key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 www wwx wwy wwz fm_L fm_R fm_R;
192.13/162.81	mkBalBranch6MkBalBranch4 www wwx wwy wwz key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 www wwx wwy wwz key elt fm_L fm_R (mkBalBranch6Size_l www wwx wwy wwz > sIZE_RATIO * mkBalBranch6Size_r www wwx wwy wwz);
192.13/162.81	"
192.13/162.81	"mkBalBranch6Double_L www wwx wwy wwz fm_l (Branch key_r elt_r vvw (Branch key_rl elt_rl vvx fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 www wwx fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch3 www wwx wwy wwz key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 www wwx wwy wwz fm_L fm_R fm_L;
192.13/162.81	mkBalBranch6MkBalBranch3 www wwx wwy wwz key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 www wwx wwy wwz key elt fm_L fm_R otherwise;
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch01 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr True = mkBalBranch6Single_L www wwx wwy wwz fm_L fm_R;
192.13/162.81	mkBalBranch6MkBalBranch01 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr False = mkBalBranch6MkBalBranch00 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr otherwise;
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch10 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr True = mkBalBranch6Double_R www wwx wwy wwz fm_L fm_R;
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch0 www wwx wwy wwz fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch6MkBalBranch02 www wwx wwy wwz fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr);
192.13/162.81	"
192.13/162.81	"mkBalBranch6Single_R www wwx wwy wwz (Branch key_l elt_l vuw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 www wwx fm_lr fm_r);
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch1 www wwx wwy wwz fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch6MkBalBranch12 www wwx wwy wwz fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr);
192.13/162.81	"
192.13/162.81	"mkBalBranch6Size_r www wwx wwy wwz = sizeFM wwy;
192.13/162.81	"
192.13/162.81	"mkBalBranch6Single_L www wwx wwy wwz fm_l (Branch key_r elt_r vwv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 www wwx fm_l fm_rl) fm_rr;
192.13/162.81	"
192.13/162.81	"mkBalBranch6Double_R www wwx wwy wwz (Branch key_l elt_l vux fm_ll (Branch key_lr elt_lr vuy fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 www wwx fm_lrr fm_r);
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch02 www wwx wwy wwz fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch6MkBalBranch01 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch00 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr True = mkBalBranch6Double_L www wwx wwy wwz fm_L fm_R;
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch11 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr True = mkBalBranch6Single_R www wwx wwy wwz fm_L fm_R;
192.13/162.81	mkBalBranch6MkBalBranch11 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr False = mkBalBranch6MkBalBranch10 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr otherwise;
192.13/162.81	"
192.13/162.81	"mkBalBranch6MkBalBranch12 www wwx wwy wwz fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch6MkBalBranch11 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
192.13/162.81	"
192.13/162.81	"mkBalBranch6Size_l www wwx wwy wwz = sizeFM wwz;
192.13/162.81	"
192.13/162.81	The bindings of the following Let/Where expression
192.13/162.81	"let {
192.13/162.81	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
192.13/162.81	} in result where {
192.13/162.81	balance_ok  = True;
192.13/162.81	;
192.13/162.81	left_ok  = left_ok0 fm_l key fm_l;
192.13/162.81	;
192.13/162.81	left_ok0 fm_l key EmptyFM = True;
192.13/162.81	left_ok0 fm_l key (Branch left_key yw yx yy yz) = let {
192.13/162.81	biggest_left_key  = fst (findMax fm_l);
192.13/162.81	} in biggest_left_key < key;
192.13/162.81	;
192.13/162.81	left_size  = sizeFM fm_l;
192.13/162.81	;
192.13/162.81	right_ok  = right_ok0 fm_r key fm_r;
192.13/162.81	;
192.13/162.81	right_ok0 fm_r key EmptyFM = True;
192.13/162.81	right_ok0 fm_r key (Branch right_key zu zv zw zx) = let {
192.13/162.81	smallest_right_key  = fst (findMin fm_r);
192.13/162.81	} in key < smallest_right_key;
192.13/162.81	;
192.13/162.81	right_size  = sizeFM fm_r;
192.13/162.81	;
192.13/162.81	unbox x = x;
192.13/162.81	} 
192.13/162.81	"
192.13/162.81	are unpacked to the following functions on top level
192.13/162.81	"mkBranchLeft_ok wxu wxv wxw = mkBranchLeft_ok0 wxu wxv wxw wxu wxv wxu;
192.13/162.81	"
192.13/162.81	"mkBranchBalance_ok wxu wxv wxw = True;
192.13/162.81	"
192.13/162.81	"mkBranchRight_ok wxu wxv wxw = mkBranchRight_ok0 wxu wxv wxw wxw wxv wxw;
192.13/162.81	"
192.13/162.81	"mkBranchLeft_ok0 wxu wxv wxw fm_l key EmptyFM = True;
192.13/162.81	mkBranchLeft_ok0 wxu wxv wxw fm_l key (Branch left_key yw yx yy yz) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
192.13/162.81	"
192.13/162.81	"mkBranchRight_size wxu wxv wxw = sizeFM wxw;
192.13/162.81	"
192.13/162.81	"mkBranchUnbox wxu wxv wxw x = x;
192.13/162.81	"
192.13/162.81	"mkBranchLeft_size wxu wxv wxw = sizeFM wxu;
192.13/162.81	"
192.13/162.81	"mkBranchRight_ok0 wxu wxv wxw fm_r key EmptyFM = True;
192.13/162.81	mkBranchRight_ok0 wxu wxv wxw fm_r key (Branch right_key zu zv zw zx) = key < mkBranchRight_ok0Smallest_right_key fm_r;
192.13/162.81	"
192.13/162.81	The bindings of the following Let/Where expression
192.13/162.81	"let {
192.13/162.81	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
192.13/162.81	} in result"
192.13/162.81	are unpacked to the following functions on top level
192.13/162.81	"mkBranchResult wxx wxy wxz wyu = Branch wxx wxy (mkBranchUnbox wxz wxx wyu (1 + mkBranchLeft_size wxz wxx wyu + mkBranchRight_size wxz wxx wyu)) wxz wyu;
192.13/162.81	"
192.13/162.81	The bindings of the following Let/Where expression
192.13/162.81	"mkVBalBranch split_key elt1 (plusFM lts left) (plusFM gts right) where {
192.13/162.81	gts  = splitGT fm1 split_key;
192.13/162.81	;
192.13/162.81	lts  = splitLT fm1 split_key;
192.13/162.81	} 
192.13/162.81	"
192.13/162.81	are unpacked to the following functions on top level
192.13/162.81	"plusFMLts wyv wyw = splitLT wyv wyw;
192.13/162.81	"
192.13/162.81	"plusFMGts wyv wyw = splitGT wyv wyw;
192.13/162.81	"
192.13/162.81	The bindings of the following Let/Where expression
192.13/162.81	"mkVBalBranch2 key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * size_l < size_r) where {
192.13/162.81	mkVBalBranch0 key elt wv ww wx wy wz xv xw xx xy xz True = mkBranch 13 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz);
192.13/162.81	;
192.13/162.81	mkVBalBranch1 key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch wv ww wy (mkVBalBranch key elt wz (Branch xv xw xx xy xz));
192.13/162.81	mkVBalBranch1 key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch0 key elt wv ww wx wy wz xv xw xx xy xz otherwise;
192.13/162.81	;
192.13/162.81	mkVBalBranch2 key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch xv xw (mkVBalBranch key elt (Branch wv ww wx wy wz) xy) xz;
192.13/162.81	mkVBalBranch2 key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch1 key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * size_r < size_l);
192.13/162.81	;
192.13/162.81	size_l  = sizeFM (Branch wv ww wx wy wz);
192.13/162.81	;
192.13/162.81	size_r  = sizeFM (Branch xv xw xx xy xz);
192.13/162.81	} 
192.13/162.81	"
192.13/162.81	are unpacked to the following functions on top level
192.13/162.81	"mkVBalBranch3Size_r wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu = sizeFM (Branch wyx wyy wyz wzu wzv);
192.13/162.81	"
192.13/162.81	"mkVBalBranch3MkVBalBranch0 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz True = mkBranch 13 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz);
192.13/162.81	"
192.13/162.81	"mkVBalBranch3Size_l wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu = sizeFM (Branch wzw wzx wzy wzz xuu);
192.13/162.81	"
192.13/162.81	"mkVBalBranch3MkVBalBranch1 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch wv ww wy (mkVBalBranch key elt wz (Branch xv xw xx xy xz));
192.13/162.81	mkVBalBranch3MkVBalBranch1 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch3MkVBalBranch0 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz otherwise;
192.13/162.81	"
192.13/162.81	"mkVBalBranch3MkVBalBranch2 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch xv xw (mkVBalBranch key elt (Branch wv ww wx wy wz) xy) xz;
192.13/162.81	mkVBalBranch3MkVBalBranch2 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch3MkVBalBranch1 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * mkVBalBranch3Size_r wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu < mkVBalBranch3Size_l wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu);
192.13/162.81	"
192.13/162.81	The bindings of the following Let/Where expression
192.13/162.81	"let {
192.13/162.81	biggest_left_key  = fst (findMax fm_l);
192.13/162.81	} in biggest_left_key < key"
192.13/162.81	are unpacked to the following functions on top level
192.13/162.81	"mkBranchLeft_ok0Biggest_left_key xuv = fst (findMax xuv);
192.13/162.81	"
192.13/162.81	The bindings of the following Let/Where expression
192.13/162.81	"let {
192.13/162.81	smallest_right_key  = fst (findMin fm_r);
192.13/162.81	} in key < smallest_right_key"
192.13/162.81	are unpacked to the following functions on top level
192.13/162.81	"mkBranchRight_ok0Smallest_right_key xuw = fst (findMin xuw);
192.13/162.81	"
192.13/162.81	
192.13/162.81	----------------------------------------
192.13/162.81	
192.13/162.81	(10)
192.13/162.81	Obligation:
192.13/162.81	mainModule Main 
192.13/162.81	module FiniteMap where {
192.13/162.81	import qualified Main;
192.13/162.81	import qualified Maybe;
192.13/162.81	import qualified Prelude;
192.13/162.81	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
192.13/162.81	
192.13/162.81	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
192.13/162.81	}
192.13/162.81	addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
192.13/162.81	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
192.13/162.81	
192.13/162.81	addToFM0 old new = new;
192.13/162.81	
192.13/162.81	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
192.13/162.81	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
192.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	
192.13/162.81	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
192.13/162.81	addToFM_C4 vyu vyv vyw vyx = addToFM_C3 vyu vyv vyw vyx;
192.13/162.81	
192.13/162.81	emptyFM :: FiniteMap a b;
192.13/162.81	emptyFM = EmptyFM;
192.13/162.81	
192.13/162.81	findMax :: FiniteMap b a  ->  (b,a);
192.13/162.81	findMax (Branch key elt zy zz EmptyFM) = (key,elt);
192.13/162.81	findMax (Branch key elt vuu vuv fm_r) = findMax fm_r;
192.13/162.81	
192.13/162.81	findMin :: FiniteMap b a  ->  (b,a);
192.13/162.81	findMin (Branch key elt vxu EmptyFM vxv) = (key,elt);
192.13/162.81	findMin (Branch key elt vxw fm_l vxx) = findMin fm_l;
192.13/162.81	
192.13/162.81	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
192.13/162.81	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
192.13/162.81	
192.13/162.81	mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_R fm_L key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_R fm_L + mkBalBranch6Size_r key elt fm_R fm_L < 2);
192.13/162.81	
192.13/162.81	mkBalBranch6Double_L www wwx wwy wwz fm_l (Branch key_r elt_r vvw (Branch key_rl elt_rl vvx fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 www wwx fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
192.13/162.81	
192.13/162.81	mkBalBranch6Double_R www wwx wwy wwz (Branch key_l elt_l vux fm_ll (Branch key_lr elt_lr vuy fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 www wwx fm_lrr fm_r);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch0 www wwx wwy wwz fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch6MkBalBranch02 www wwx wwy wwz fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch00 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr True = mkBalBranch6Double_L www wwx wwy wwz fm_L fm_R;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch01 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr True = mkBalBranch6Single_L www wwx wwy wwz fm_L fm_R;
192.13/162.81	mkBalBranch6MkBalBranch01 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr False = mkBalBranch6MkBalBranch00 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr otherwise;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch02 www wwx wwy wwz fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch6MkBalBranch01 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch1 www wwx wwy wwz fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch6MkBalBranch12 www wwx wwy wwz fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch10 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr True = mkBalBranch6Double_R www wwx wwy wwz fm_L fm_R;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch11 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr True = mkBalBranch6Single_R www wwx wwy wwz fm_L fm_R;
192.13/162.81	mkBalBranch6MkBalBranch11 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr False = mkBalBranch6MkBalBranch10 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr otherwise;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch12 www wwx wwy wwz fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch6MkBalBranch11 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch2 www wwx wwy wwz key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch3 www wwx wwy wwz key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 www wwx wwy wwz fm_L fm_R fm_L;
192.13/162.81	mkBalBranch6MkBalBranch3 www wwx wwy wwz key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 www wwx wwy wwz key elt fm_L fm_R otherwise;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch4 www wwx wwy wwz key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 www wwx wwy wwz fm_L fm_R fm_R;
192.13/162.81	mkBalBranch6MkBalBranch4 www wwx wwy wwz key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 www wwx wwy wwz key elt fm_L fm_R (mkBalBranch6Size_l www wwx wwy wwz > sIZE_RATIO * mkBalBranch6Size_r www wwx wwy wwz);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch5 www wwx wwy wwz key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
192.13/162.81	mkBalBranch6MkBalBranch5 www wwx wwy wwz key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 www wwx wwy wwz key elt fm_L fm_R (mkBalBranch6Size_r www wwx wwy wwz > sIZE_RATIO * mkBalBranch6Size_l www wwx wwy wwz);
192.13/162.81	
192.13/162.81	mkBalBranch6Single_L www wwx wwy wwz fm_l (Branch key_r elt_r vwv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 www wwx fm_l fm_rl) fm_rr;
192.13/162.81	
192.13/162.81	mkBalBranch6Single_R www wwx wwy wwz (Branch key_l elt_l vuw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 www wwx fm_lr fm_r);
192.13/162.81	
192.13/162.81	mkBalBranch6Size_l www wwx wwy wwz = sizeFM wwz;
192.13/162.81	
192.13/162.81	mkBalBranch6Size_r www wwx wwy wwz = sizeFM wwy;
192.13/162.81	
192.13/162.81	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
192.13/162.81	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r;
192.13/162.81	
192.13/162.81	mkBranchBalance_ok wxu wxv wxw = True;
192.13/162.81	
192.13/162.81	mkBranchLeft_ok wxu wxv wxw = mkBranchLeft_ok0 wxu wxv wxw wxu wxv wxu;
192.13/162.81	
192.13/162.81	mkBranchLeft_ok0 wxu wxv wxw fm_l key EmptyFM = True;
192.13/162.81	mkBranchLeft_ok0 wxu wxv wxw fm_l key (Branch left_key yw yx yy yz) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
192.13/162.81	
192.13/162.81	mkBranchLeft_ok0Biggest_left_key xuv = fst (findMax xuv);
192.13/162.81	
192.13/162.81	mkBranchLeft_size wxu wxv wxw = sizeFM wxu;
192.13/162.81	
192.13/162.81	mkBranchResult wxx wxy wxz wyu = Branch wxx wxy (mkBranchUnbox wxz wxx wyu (1 + mkBranchLeft_size wxz wxx wyu + mkBranchRight_size wxz wxx wyu)) wxz wyu;
192.13/162.81	
192.13/162.81	mkBranchRight_ok wxu wxv wxw = mkBranchRight_ok0 wxu wxv wxw wxw wxv wxw;
192.13/162.81	
192.13/162.81	mkBranchRight_ok0 wxu wxv wxw fm_r key EmptyFM = True;
192.13/162.81	mkBranchRight_ok0 wxu wxv wxw fm_r key (Branch right_key zu zv zw zx) = key < mkBranchRight_ok0Smallest_right_key fm_r;
192.13/162.81	
192.13/162.81	mkBranchRight_ok0Smallest_right_key xuw = fst (findMin xuw);
192.13/162.81	
192.13/162.81	mkBranchRight_size wxu wxv wxw = sizeFM wxw;
192.13/162.81	
192.13/162.81	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  a ( ->  (FiniteMap a b) (Int  ->  Int)));
192.13/162.81	mkBranchUnbox wxu wxv wxw x = x;
192.13/162.81	
192.13/162.81	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
192.13/162.81	mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
192.13/162.81	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
192.13/162.81	mkVBalBranch key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz) = mkVBalBranch3 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz);
192.13/162.81	
192.13/162.81	mkVBalBranch3 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz) = mkVBalBranch3MkVBalBranch2 xv xw xx xy xz wv ww wx wy wz key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * mkVBalBranch3Size_l xv xw xx xy xz wv ww wx wy wz < mkVBalBranch3Size_r xv xw xx xy xz wv ww wx wy wz);
192.13/162.81	
192.13/162.81	mkVBalBranch3MkVBalBranch0 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz True = mkBranch 13 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz);
192.13/162.81	
192.13/162.81	mkVBalBranch3MkVBalBranch1 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch wv ww wy (mkVBalBranch key elt wz (Branch xv xw xx xy xz));
192.13/162.81	mkVBalBranch3MkVBalBranch1 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch3MkVBalBranch0 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz otherwise;
192.13/162.81	
192.13/162.81	mkVBalBranch3MkVBalBranch2 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch xv xw (mkVBalBranch key elt (Branch wv ww wx wy wz) xy) xz;
192.13/162.81	mkVBalBranch3MkVBalBranch2 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch3MkVBalBranch1 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * mkVBalBranch3Size_r wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu < mkVBalBranch3Size_l wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu);
192.13/162.81	
192.13/162.81	mkVBalBranch3Size_l wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu = sizeFM (Branch wzw wzx wzy wzz xuu);
192.13/162.81	
192.13/162.81	mkVBalBranch3Size_r wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu = sizeFM (Branch wyx wyy wyz wzu wzv);
192.13/162.81	
192.13/162.81	mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
192.13/162.81	mkVBalBranch4 vzv vzw vzx vzy = mkVBalBranch3 vzv vzw vzx vzy;
192.13/162.81	
192.13/162.81	mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
192.13/162.81	mkVBalBranch5 wuu wuv wuw wux = mkVBalBranch4 wuu wuv wuw wux;
192.13/162.81	
192.13/162.81	plusFM :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
192.13/162.81	plusFM EmptyFM fm2 = fm2;
192.13/162.81	plusFM fm1 EmptyFM = fm1;
192.13/162.81	plusFM fm1 (Branch split_key elt1 vz left right) = mkVBalBranch split_key elt1 (plusFM (plusFMLts fm1 split_key) left) (plusFM (plusFMGts fm1 split_key) right);
192.13/162.81	
192.13/162.81	plusFMGts wyv wyw = splitGT wyv wyw;
192.13/162.81	
192.13/162.81	plusFMLts wyv wyw = splitLT wyv wyw;
192.13/162.81	
192.13/162.81	sIZE_RATIO :: Int;
192.13/162.81	sIZE_RATIO = 5;
192.13/162.81	
192.13/162.81	sizeFM :: FiniteMap b a  ->  Int;
192.13/162.81	sizeFM EmptyFM = 0;
192.13/162.81	sizeFM (Branch vww vwx size vwy vwz) = size;
192.13/162.81	
192.13/162.81	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
192.13/162.81	splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
192.13/162.81	splitGT (Branch key elt yu fm_l fm_r) split_key = splitGT3 (Branch key elt yu fm_l fm_r) split_key;
192.13/162.81	
192.13/162.81	splitGT0 key elt yu fm_l fm_r split_key True = fm_r;
192.13/162.81	
192.13/162.81	splitGT1 key elt yu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
192.13/162.81	splitGT1 key elt yu fm_l fm_r split_key False = splitGT0 key elt yu fm_l fm_r split_key otherwise;
192.13/162.81	
192.13/162.81	splitGT2 key elt yu fm_l fm_r split_key True = splitGT fm_r split_key;
192.13/162.81	splitGT2 key elt yu fm_l fm_r split_key False = splitGT1 key elt yu fm_l fm_r split_key (split_key < key);
192.13/162.81	
192.13/162.81	splitGT3 (Branch key elt yu fm_l fm_r) split_key = splitGT2 key elt yu fm_l fm_r split_key (split_key > key);
192.13/162.81	
192.13/162.81	splitGT4 EmptyFM split_key = emptyFM;
192.13/162.81	splitGT4 wvu wvv = splitGT3 wvu wvv;
192.13/162.81	
192.13/162.81	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
192.13/162.81	splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
192.13/162.81	splitLT (Branch key elt yv fm_l fm_r) split_key = splitLT3 (Branch key elt yv fm_l fm_r) split_key;
192.13/162.81	
192.13/162.81	splitLT0 key elt yv fm_l fm_r split_key True = fm_l;
192.13/162.81	
192.13/162.81	splitLT1 key elt yv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
192.13/162.81	splitLT1 key elt yv fm_l fm_r split_key False = splitLT0 key elt yv fm_l fm_r split_key otherwise;
192.13/162.81	
192.13/162.81	splitLT2 key elt yv fm_l fm_r split_key True = splitLT fm_l split_key;
192.13/162.81	splitLT2 key elt yv fm_l fm_r split_key False = splitLT1 key elt yv fm_l fm_r split_key (split_key > key);
192.13/162.81	
192.13/162.81	splitLT3 (Branch key elt yv fm_l fm_r) split_key = splitLT2 key elt yv fm_l fm_r split_key (split_key < key);
192.13/162.81	
192.13/162.81	splitLT4 EmptyFM split_key = emptyFM;
192.13/162.81	splitLT4 wvy wvz = splitLT3 wvy wvz;
192.13/162.81	
192.13/162.81	unitFM :: a  ->  b  ->  FiniteMap a b;
192.13/162.81	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
192.13/162.81	
192.13/162.81	}
192.13/162.81	module Maybe where {
192.13/162.81	import qualified FiniteMap;
192.13/162.81	import qualified Main;
192.13/162.81	import qualified Prelude;
192.13/162.81	}
192.13/162.81	module Main where {
192.13/162.81	import qualified FiniteMap;
192.13/162.81	import qualified Maybe;
192.13/162.81	import qualified Prelude;
192.13/162.81	}
192.13/162.81	
192.13/162.81	----------------------------------------
192.13/162.81	
192.13/162.81	(11) NumRed (SOUND)
192.13/162.81	Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero.
192.13/162.81	----------------------------------------
192.13/162.81	
192.13/162.81	(12)
192.13/162.81	Obligation:
192.13/162.81	mainModule Main 
192.13/162.81	module FiniteMap where {
192.13/162.81	import qualified Main;
192.13/162.81	import qualified Maybe;
192.13/162.81	import qualified Prelude;
192.13/162.81	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
192.13/162.81	
192.13/162.81	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
192.13/162.81	}
192.13/162.81	addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
192.13/162.81	addToFM fm key elt = addToFM_C addToFM0 fm key elt;
192.13/162.81	
192.13/162.81	addToFM0 old new = new;
192.13/162.81	
192.13/162.81	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
192.13/162.81	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
192.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	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.13/162.81	
192.13/162.81	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.13/162.81	
192.13/162.81	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
192.13/162.81	addToFM_C4 vyu vyv vyw vyx = addToFM_C3 vyu vyv vyw vyx;
192.13/162.81	
192.13/162.81	emptyFM :: FiniteMap b a;
192.13/162.81	emptyFM = EmptyFM;
192.13/162.81	
192.13/162.81	findMax :: FiniteMap a b  ->  (a,b);
192.13/162.81	findMax (Branch key elt zy zz EmptyFM) = (key,elt);
192.13/162.81	findMax (Branch key elt vuu vuv fm_r) = findMax fm_r;
192.13/162.81	
192.13/162.81	findMin :: FiniteMap a b  ->  (a,b);
192.13/162.81	findMin (Branch key elt vxu EmptyFM vxv) = (key,elt);
192.13/162.81	findMin (Branch key elt vxw fm_l vxx) = findMin fm_l;
192.13/162.81	
192.13/162.81	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
192.13/162.81	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
192.13/162.81	
192.13/162.81	mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_R fm_L key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_R fm_L + mkBalBranch6Size_r key elt fm_R fm_L < Pos (Succ (Succ Zero)));
192.13/162.81	
192.13/162.81	mkBalBranch6Double_L www wwx wwy wwz fm_l (Branch key_r elt_r vvw (Branch key_rl elt_rl vvx 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))))))) www wwx fm_l fm_rll) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))) key_r elt_r fm_rlr fm_rr);
192.13/162.81	
192.13/162.81	mkBalBranch6Double_R www wwx wwy wwz (Branch key_l elt_l vux fm_ll (Branch key_lr elt_lr vuy 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))))))))))))) www wwx fm_lrr fm_r);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch0 www wwx wwy wwz fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch6MkBalBranch02 www wwx wwy wwz fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch00 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr True = mkBalBranch6Double_L www wwx wwy wwz fm_L fm_R;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch01 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr True = mkBalBranch6Single_L www wwx wwy wwz fm_L fm_R;
192.13/162.81	mkBalBranch6MkBalBranch01 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr False = mkBalBranch6MkBalBranch00 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr otherwise;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch02 www wwx wwy wwz fm_L fm_R (Branch vvy vvz vwu fm_rl fm_rr) = mkBalBranch6MkBalBranch01 www wwx wwy wwz fm_L fm_R vvy vvz vwu fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch1 www wwx wwy wwz fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch6MkBalBranch12 www wwx wwy wwz fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch10 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr True = mkBalBranch6Double_R www wwx wwy wwz fm_L fm_R;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch11 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr True = mkBalBranch6Single_R www wwx wwy wwz fm_L fm_R;
192.13/162.81	mkBalBranch6MkBalBranch11 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr False = mkBalBranch6MkBalBranch10 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr otherwise;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch12 www wwx wwy wwz fm_L fm_R (Branch vuz vvu vvv fm_ll fm_lr) = mkBalBranch6MkBalBranch11 www wwx wwy wwz fm_L fm_R vuz vvu vvv fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch2 www wwx wwy wwz key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch3 www wwx wwy wwz key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 www wwx wwy wwz fm_L fm_R fm_L;
192.13/162.81	mkBalBranch6MkBalBranch3 www wwx wwy wwz key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 www wwx wwy wwz key elt fm_L fm_R otherwise;
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch4 www wwx wwy wwz key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 www wwx wwy wwz fm_L fm_R fm_R;
192.13/162.81	mkBalBranch6MkBalBranch4 www wwx wwy wwz key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 www wwx wwy wwz key elt fm_L fm_R (mkBalBranch6Size_l www wwx wwy wwz > sIZE_RATIO * mkBalBranch6Size_r www wwx wwy wwz);
192.13/162.81	
192.13/162.81	mkBalBranch6MkBalBranch5 www wwx wwy wwz key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R;
192.13/162.81	mkBalBranch6MkBalBranch5 www wwx wwy wwz key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 www wwx wwy wwz key elt fm_L fm_R (mkBalBranch6Size_r www wwx wwy wwz > sIZE_RATIO * mkBalBranch6Size_l www wwx wwy wwz);
192.13/162.81	
192.13/162.81	mkBalBranch6Single_L www wwx wwy wwz fm_l (Branch key_r elt_r vwv fm_rl fm_rr) = mkBranch (Pos (Succ (Succ (Succ Zero)))) key_r elt_r (mkBranch (Pos (Succ (Succ (Succ (Succ Zero))))) www wwx fm_l fm_rl) fm_rr;
192.13/162.81	
192.13/162.81	mkBalBranch6Single_R www wwx wwy wwz (Branch key_l elt_l vuw 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)))))))))) www wwx fm_lr fm_r);
192.13/162.81	
192.13/162.81	mkBalBranch6Size_l www wwx wwy wwz = sizeFM wwz;
192.13/162.81	
192.13/162.81	mkBalBranch6Size_r www wwx wwy wwz = sizeFM wwy;
192.13/162.81	
192.13/162.81	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
192.13/162.81	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r;
192.13/162.81	
192.13/162.81	mkBranchBalance_ok wxu wxv wxw = True;
192.13/162.81	
192.13/162.81	mkBranchLeft_ok wxu wxv wxw = mkBranchLeft_ok0 wxu wxv wxw wxu wxv wxu;
192.13/162.81	
192.13/162.81	mkBranchLeft_ok0 wxu wxv wxw fm_l key EmptyFM = True;
192.13/162.81	mkBranchLeft_ok0 wxu wxv wxw fm_l key (Branch left_key yw yx yy yz) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
192.13/162.81	
192.13/162.81	mkBranchLeft_ok0Biggest_left_key xuv = fst (findMax xuv);
192.13/162.81	
192.13/162.81	mkBranchLeft_size wxu wxv wxw = sizeFM wxu;
192.13/162.81	
192.13/162.81	mkBranchResult wxx wxy wxz wyu = Branch wxx wxy (mkBranchUnbox wxz wxx wyu (Pos (Succ Zero) + mkBranchLeft_size wxz wxx wyu + mkBranchRight_size wxz wxx wyu)) wxz wyu;
192.13/162.81	
192.13/162.81	mkBranchRight_ok wxu wxv wxw = mkBranchRight_ok0 wxu wxv wxw wxw wxv wxw;
192.13/162.81	
192.13/162.81	mkBranchRight_ok0 wxu wxv wxw fm_r key EmptyFM = True;
192.13/162.81	mkBranchRight_ok0 wxu wxv wxw fm_r key (Branch right_key zu zv zw zx) = key < mkBranchRight_ok0Smallest_right_key fm_r;
192.13/162.81	
192.13/162.81	mkBranchRight_ok0Smallest_right_key xuw = fst (findMin xuw);
192.13/162.81	
192.13/162.81	mkBranchRight_size wxu wxv wxw = sizeFM wxw;
192.13/162.81	
192.13/162.81	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  a ( ->  (FiniteMap a b) (Int  ->  Int)));
192.13/162.81	mkBranchUnbox wxu wxv wxw x = x;
192.13/162.81	
192.13/162.81	mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
192.13/162.81	mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
192.13/162.81	mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
192.13/162.81	mkVBalBranch key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz) = mkVBalBranch3 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz);
192.13/162.81	
192.13/162.81	mkVBalBranch3 key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz) = mkVBalBranch3MkVBalBranch2 xv xw xx xy xz wv ww wx wy wz key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * mkVBalBranch3Size_l xv xw xx xy xz wv ww wx wy wz < mkVBalBranch3Size_r xv xw xx xy xz wv ww wx wy wz);
192.13/162.81	
192.13/162.81	mkVBalBranch3MkVBalBranch0 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz True = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))))) key elt (Branch wv ww wx wy wz) (Branch xv xw xx xy xz);
192.13/162.81	
192.13/162.81	mkVBalBranch3MkVBalBranch1 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch wv ww wy (mkVBalBranch key elt wz (Branch xv xw xx xy xz));
192.13/162.81	mkVBalBranch3MkVBalBranch1 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch3MkVBalBranch0 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz otherwise;
192.13/162.81	
192.13/162.81	mkVBalBranch3MkVBalBranch2 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz True = mkBalBranch xv xw (mkVBalBranch key elt (Branch wv ww wx wy wz) xy) xz;
192.13/162.81	mkVBalBranch3MkVBalBranch2 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz False = mkVBalBranch3MkVBalBranch1 wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu key elt wv ww wx wy wz xv xw xx xy xz (sIZE_RATIO * mkVBalBranch3Size_r wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu < mkVBalBranch3Size_l wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu);
192.13/162.81	
192.13/162.81	mkVBalBranch3Size_l wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu = sizeFM (Branch wzw wzx wzy wzz xuu);
192.13/162.81	
192.13/162.81	mkVBalBranch3Size_r wyx wyy wyz wzu wzv wzw wzx wzy wzz xuu = sizeFM (Branch wyx wyy wyz wzu wzv);
192.13/162.81	
192.13/162.81	mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
192.13/162.81	mkVBalBranch4 vzv vzw vzx vzy = mkVBalBranch3 vzv vzw vzx vzy;
192.13/162.81	
192.13/162.81	mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
192.13/162.81	mkVBalBranch5 wuu wuv wuw wux = mkVBalBranch4 wuu wuv wuw wux;
192.13/162.81	
192.13/162.81	plusFM :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
192.13/162.81	plusFM EmptyFM fm2 = fm2;
192.13/162.81	plusFM fm1 EmptyFM = fm1;
192.13/162.81	plusFM fm1 (Branch split_key elt1 vz left right) = mkVBalBranch split_key elt1 (plusFM (plusFMLts fm1 split_key) left) (plusFM (plusFMGts fm1 split_key) right);
192.13/162.81	
192.13/162.81	plusFMGts wyv wyw = splitGT wyv wyw;
192.13/162.81	
192.13/162.81	plusFMLts wyv wyw = splitLT wyv wyw;
192.13/162.81	
192.13/162.81	sIZE_RATIO :: Int;
192.13/162.81	sIZE_RATIO = Pos (Succ (Succ (Succ (Succ (Succ Zero)))));
192.13/162.81	
192.13/162.81	sizeFM :: FiniteMap b a  ->  Int;
192.13/162.81	sizeFM EmptyFM = Pos Zero;
192.13/162.81	sizeFM (Branch vww vwx size vwy vwz) = size;
192.13/162.81	
192.13/162.81	splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
192.13/162.81	splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
192.13/162.81	splitGT (Branch key elt yu fm_l fm_r) split_key = splitGT3 (Branch key elt yu fm_l fm_r) split_key;
192.13/162.81	
192.13/162.81	splitGT0 key elt yu fm_l fm_r split_key True = fm_r;
192.13/162.81	
192.13/162.81	splitGT1 key elt yu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
192.13/162.81	splitGT1 key elt yu fm_l fm_r split_key False = splitGT0 key elt yu fm_l fm_r split_key otherwise;
192.13/162.81	
192.13/162.81	splitGT2 key elt yu fm_l fm_r split_key True = splitGT fm_r split_key;
192.13/162.81	splitGT2 key elt yu fm_l fm_r split_key False = splitGT1 key elt yu fm_l fm_r split_key (split_key < key);
192.13/162.81	
192.13/162.81	splitGT3 (Branch key elt yu fm_l fm_r) split_key = splitGT2 key elt yu fm_l fm_r split_key (split_key > key);
192.13/162.81	
192.13/162.81	splitGT4 EmptyFM split_key = emptyFM;
192.13/162.81	splitGT4 wvu wvv = splitGT3 wvu wvv;
192.13/162.81	
192.13/162.81	splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
192.13/162.81	splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
192.13/162.81	splitLT (Branch key elt yv fm_l fm_r) split_key = splitLT3 (Branch key elt yv fm_l fm_r) split_key;
192.13/162.81	
192.13/162.81	splitLT0 key elt yv fm_l fm_r split_key True = fm_l;
192.13/162.81	
192.13/162.81	splitLT1 key elt yv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
192.13/162.81	splitLT1 key elt yv fm_l fm_r split_key False = splitLT0 key elt yv fm_l fm_r split_key otherwise;
192.13/162.81	
192.13/162.81	splitLT2 key elt yv fm_l fm_r split_key True = splitLT fm_l split_key;
192.13/162.81	splitLT2 key elt yv fm_l fm_r split_key False = splitLT1 key elt yv fm_l fm_r split_key (split_key > key);
192.13/162.81	
192.13/162.81	splitLT3 (Branch key elt yv fm_l fm_r) split_key = splitLT2 key elt yv fm_l fm_r split_key (split_key < key);
192.13/162.81	
192.13/162.81	splitLT4 EmptyFM split_key = emptyFM;
192.13/162.81	splitLT4 wvy wvz = splitLT3 wvy wvz;
192.13/162.81	
192.13/162.81	unitFM :: b  ->  a  ->  FiniteMap b a;
192.13/162.81	unitFM key elt = Branch key elt (Pos (Succ Zero)) emptyFM emptyFM;
192.13/162.81	
192.13/162.81	}
192.13/162.81	module Maybe where {
192.13/162.81	import qualified FiniteMap;
192.13/162.81	import qualified Main;
192.13/162.81	import qualified Prelude;
192.13/162.81	}
192.13/162.81	module Main where {
192.13/162.81	import qualified FiniteMap;
192.13/162.81	import qualified Maybe;
192.13/162.81	import qualified Prelude;
192.13/162.81	}
192.34/162.85	EOF