Ticket #4242 (closed bug: fixed)

Opened 3 years ago

Last modified 3 years ago

Data.Map operations can produce invalid trees

Reported by: igloo Owned by: igloo
Priority: high Milestone: 7.0.1
Component: libraries (other) Version: 6.12.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty:
Test Case: datamap002 Blocked By:
Blocking: Related Tickets:

Description

With 6.13.20100801: 

Prelude Data.Map> valid $ deleteMin $ deleteMin $ fromList [ (i, ()) | i <- [0,2,5,1,6,4,8,9,7,11,10,3] ]
False

Is changing delta from 5 to 4 the right fix?

See  http://article.gmane.org/gmane.comp.lang.haskell.libraries/13444 for the original report and more details.

Change History

Changed 3 years ago by milan

I think I have proof that it is the right fix. For some comments, see  http://article.gmane.org/gmane.comp.lang.haskell.libraries/13448

Cheers, Milan

Changed 3 years ago by igloo

  • owner set to igloo

Changed 3 years ago by igloo

  • status changed from new to closed
  • testcase set to datamap002
  • resolution set to fixed

OK, thanks. Fixed: 

Sun Aug 15 14:19:54 BST 2010  Ian Lynagh <igloo@earth.li>
  * Set Data.Map's delta to 4; fixes #4242
Note: See TracTickets for help on using tickets.