From 2701ac4127cbc37e6d1069e2f5240a1e0ec1e479 Mon Sep 17 00:00:00 2001 From: jpbernardy Date: Sun, 13 Nov 2005 16:52:14 +0000 Subject: [PATCH] [project @ 2005-11-13 16:52:14 by jpbernardy] Correct handling of negative numbers in split and splitMember in IntMap and IntSet. Better documentation for insert and insertWith in Maps. --- Data/IntMap.hs | 48 +++++++++++++++++++++++++++++++++++++++++++++++- Data/IntSet.hs | 51 +++++++++++++++++++++++++++++++++++++++++++-------- Data/Map.hs | 8 ++++++++ 3 files changed, 98 insertions(+), 9 deletions(-) diff --git a/Data/IntMap.hs b/Data/IntMap.hs index 0dd6bf0..e210442 100644 --- a/Data/IntMap.hs +++ b/Data/IntMap.hs @@ -322,11 +322,19 @@ insert k x t -- right-biased insertion, used by 'union' -- | /O(min(n,W))/. Insert with a combining function. +-- @'insertWith' f key value mp@ +-- will insert the pair (key, value) into @mp@ if key does +-- not exist in the map. If the key does exist, the function will +-- insert @f new_value old_value@. insertWith :: (a -> a -> a) -> Key -> a -> IntMap a -> IntMap a insertWith f k x t = insertWithKey (\k x y -> f x y) k x t -- | /O(min(n,W))/. Insert with a combining function. +-- @'insertWithKey' f key value mp@ +-- will insert the pair (key, value) into @mp@ if key does +-- not exist in the map. If the key does exist, the function will +-- insert @f key new_value old_value@. insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> IntMap a insertWithKey f k x t = case t of @@ -804,6 +812,20 @@ partitionWithKey pred t split :: Key -> IntMap a -> (IntMap a,IntMap a) split k t = case t of + Bin p m l r + | m < 0 -> (if k >= 0 -- handle negative numbers. + then let (lt,gt) = split' k l in (union r lt, gt) + else let (lt,gt) = split' k r in (lt, union gt l)) + | otherwise -> split' k t + Tip ky y + | k>ky -> (t,Nil) + | k (Nil,t) + | otherwise -> (Nil,Nil) + Nil -> (Nil,Nil) + +split' :: Key -> IntMap a -> (IntMap a,IntMap a) +split' k t + = case t of Bin p m l r | nomatch k p m -> if k>p then (t,Nil) else (Nil,t) | zero k m -> let (lt,gt) = split k l in (lt,union gt r) @@ -820,6 +842,20 @@ splitLookup :: Key -> IntMap a -> (IntMap a,Maybe a,IntMap a) splitLookup k t = case t of Bin p m l r + | m < 0 -> (if k >= 0 -- handle negative numbers. + then let (lt,found,gt) = splitLookup' k l in (union r lt,found, gt) + else let (lt,found,gt) = splitLookup' k r in (lt,found, union gt l)) + | otherwise -> splitLookup' k t + Tip ky y + | k>ky -> (t,Nothing,Nil) + | k (Nil,Nothing,t) + | otherwise -> (Nil,Just y,Nil) + Nil -> (Nil,Nothing,Nil) + +splitLookup' :: Key -> IntMap a -> (IntMap a,Maybe a,IntMap a) +splitLookup' k t + = case t of + Bin p m l r | nomatch k p m -> if k>p then (t,Nothing,Nil) else (Nil,Nothing,t) | zero k m -> let (lt,found,gt) = splitLookup k l in (lt,found,union gt r) | otherwise -> let (lt,found,gt) = splitLookup k r in (union l lt,found,gt) @@ -855,10 +891,20 @@ foldWithKey f z t foldr :: (Key -> a -> b -> b) -> b -> IntMap a -> b foldr f z t = case t of - Bin p m l r -> foldr f (foldr f z r) l + Bin 0 m l r | m < 0 -> foldr' f (foldr' f z l) r -- put negative numbers before. + Bin _ _ _ _ -> foldr' f z t Tip k x -> f k x z Nil -> z +foldr' :: (Key -> a -> b -> b) -> b -> IntMap a -> b +foldr' f z t + = case t of + Bin p m l r -> foldr' f (foldr' f z r) l + Tip k x -> f k x z + Nil -> z + + + {-------------------------------------------------------------------- List variations --------------------------------------------------------------------} diff --git a/Data/IntSet.hs b/Data/IntSet.hs index a47244f..720b937 100644 --- a/Data/IntSet.hs +++ b/Data/IntSet.hs @@ -461,8 +461,24 @@ split :: Int -> IntSet -> (IntSet,IntSet) split x t = case t of Bin p m l r - | zero x m -> let (lt,gt) = split x l in (lt,union gt r) - | otherwise -> let (lt,gt) = split x r in (union l lt,gt) + | m < 0 -> if x >= 0 then let (lt,gt) = split' x l in (union r lt, gt) + else let (lt,gt) = split' x r in (lt, union gt l) + -- handle negative numbers. + | otherwise -> split' x t + Tip y + | x>y -> (t,Nil) + | x (Nil,t) + | otherwise -> (Nil,Nil) + Nil -> (Nil, Nil) + +split' :: Int -> IntSet -> (IntSet,IntSet) +split' x t + = case t of + Bin p m l r + | match x p m -> if zero x m then let (lt,gt) = split' x l in (lt,union gt r) + else let (lt,gt) = split' x r in (union l lt,gt) + | otherwise -> if x < p then (Nil, t) + else (t, Nil) Tip y | x>y -> (t,Nil) | x (Nil,t) @@ -475,8 +491,24 @@ splitMember :: Int -> IntSet -> (IntSet,Bool,IntSet) splitMember x t = case t of Bin p m l r - | zero x m -> let (lt,found,gt) = splitMember x l in (lt,found,union gt r) - | otherwise -> let (lt,found,gt) = splitMember x r in (union l lt,found,gt) + | m < 0 -> if x >= 0 then let (lt,found,gt) = splitMember' x l in (union r lt, found, gt) + else let (lt,found,gt) = splitMember' x r in (lt, found, union gt l) + -- handle negative numbers. + | otherwise -> splitMember' x t + Tip y + | x>y -> (t,False,Nil) + | x (Nil,False,t) + | otherwise -> (Nil,True,Nil) + Nil -> (Nil,False,Nil) + +splitMember' :: Int -> IntSet -> (IntSet,Bool,IntSet) +splitMember' x t + = case t of + Bin p m l r + | match x p m -> if zero x m then let (lt,found,gt) = splitMember x l in (lt,found,union gt r) + else let (lt,found,gt) = splitMember x r in (union l lt,found,gt) + | otherwise -> if x < p then (Nil, False, t) + else (t, False, Nil) Tip y | x>y -> (t,False,Nil) | x (Nil,False,t) @@ -505,7 +537,12 @@ map f = fromList . List.map f . toList -- > elems set == fold (:) [] set fold :: (Int -> b -> b) -> b -> IntSet -> b fold f z t - = foldr f z t + = case t of + Bin 0 m l r | m < 0 -> foldr f (foldr f z l) r + -- put negative numbers before. + Bin p m l r -> foldr f z t + Tip x -> f x z + Nil -> z foldr :: (Int -> b -> b) -> b -> IntSet -> b foldr f z t @@ -532,9 +569,7 @@ toList t -- | /O(n)/. Convert the set to an ascending list of elements. toAscList :: IntSet -> [Int] -toAscList t - = -- NOTE: the following algorithm only works for big-endian trees - let (pos,neg) = span (>=0) (foldr (:) [] t) in neg ++ pos +toAscList t = toList t -- | /O(n*min(n,W))/. Create a set from a list of integers. fromList :: [Int] -> IntSet diff --git a/Data/Map.hs b/Data/Map.hs index cafb0a1..f0b7f6f 100644 --- a/Data/Map.hs +++ b/Data/Map.hs @@ -301,11 +301,19 @@ insert kx x t EQ -> Bin sz kx x l r -- | /O(log n)/. Insert with a combining function. +-- @'insertWith' f key value mp@ +-- will insert the pair (key, value) into @mp@ if key does +-- not exist in the map. If the key does exist, the function will +-- insert @f new_value old_value@. insertWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a insertWith f k x m = insertWithKey (\k x y -> f x y) k x m -- | /O(log n)/. Insert with a combining function. +-- @'insertWithKey' f key value mp@ +-- will insert the pair (key, value) into @mp@ if key does +-- not exist in the map. If the key does exist, the function will +-- insert @f key new_value old_value@. insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a insertWithKey f kx x t = case t of -- 1.7.10.4