Buglet in Data.IntSet.split and Data.IntSet.splitMember, patch included.

[Arthur van Leeuwen]

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 at 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<y         -> (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<y       -> (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<y       -> (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<y       -> (Nil,False,t)
----- 8< --- ereh tuc --- >8 -----

Hope this helps. :)

Doei, Arthur.

-- 
   /\    / |       arthurvl at 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