Opened 9 years ago

Closed 9 years ago

Last modified 44 years ago

#374 closed bug (Fixed)

IntMap.split wrong split

Reported by: nobody Owned by: nobody
Priority: normal Milestone:
Component: hslibs/data Version: 6.4
Keywords: Cc:
Operating System: Architecture:
Type of failure: Difficulty:
Test Case: Blocked By:
Blocking: Related Tickets:

Description

"keys $ split 5 $ theMap" sometimes returns values  
greater 5.  
  
I am still trying to pinpoint the bug, but since it  
shows itself only deep inside a complicated 
structure, I have  
problems doing so.  
One pointer might be, that my values are partially  
evaluated functions, but this is only a guess.  
  
(Changing the data structure to Data.Map restores 
normal operation in my algorithm) 
 
Christian  
  
choener@cebitec.uni-bielefeld.de  
  

Change History (4)

comment:1 Changed 9 years ago by nobody

Logged In: NO 

Of course, it is with (fst) (and the Intmap contains more  
than one element, three in my case)  
  
"keys $ fst $ split 5 $ theMap"  
  
Christian 
choener@... 

comment:2 Changed 9 years ago by pkturner

Logged In: YES 
user_id=22153

Thanks to a simple reproduction of the bug by Malcolm
Wallace, I was able to track it down. The bug is right there
in split.  Data/IntMap.hs needs:

***************
*** 750,755 ****
--- 750,756 ----
  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)
          | otherwise -> let (lt,gt) = split k r in (union l
lt,gt)
        Tip ky y
***************
*** 764,769 ****
--- 765,771 ----
  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)
        Tip ky y

comment:3 Changed 9 years ago by simonpj

Logged In: YES 
user_id=50165

Fixed by Scott Turner and Malcolm Wallace

comment:4 Changed 9 years ago by simonpj

  • Status changed from assigned to closed
Note: See TracTickets for help on using tickets.