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
