Opened 4 years ago

Closed 4 years ago

#4242 closed bug (fixed)

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 (3)

comment:1 Changed 4 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

comment:2 Changed 4 years ago by igloo

  • Owner set to igloo

comment:3 Changed 4 years ago by igloo

  • Resolution set to fixed
  • Status changed from new to closed
  • Test Case set to datamap002

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.