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