Hello mailinglist-members, on the #haskell IRC channel Ketil Z. Malde noted that Data.IntSet.split failed on the case

let m = 1000000 in Data.IntSet.split (16*m) $ Data.IntSet.fromList $ map (*m) [17,18,19,30,40]

so Bertram Felgenhauer (int-e@gmx.de) and I set out to fix that, noting along the way that Data.IntSet.splitMember was broken as well, and that negative numbers were not handled correctly either. The following patch fixes the problems: ----- 8< --- cut here --- >8 ----- --- IntSet.hs 2005-10-27 17:18:15.000000000 +0200 +++ FixedIntSet.hs 2005-10-27 17:59:49.000000000 +0200 @@ -35,7 +35,7 @@ -- (32 or 64). ------------------------------------------------------------------------ ----- -module Data.IntSet ( +module IntSet ( -- * Set type IntSet -- instance Eq,Show @@ -454,8 +454,23 @@ 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) + | 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) @@ -468,8 +483,23 @@ 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) + | 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) ----- 8< --- ereh tuc --- >8 ----- Hope this helps. :) Doei, Arthur. -- /\ / | arthurvl@cs.uu.nl | Work like you don't need the money /__\ / | A friend is someone with whom | Love like you have never been hurt / \/__ | you can dare to be yourself | Dance like there's nobody watching