Bug in Data.Map

[Tyson Whitehead]

On August 4, 2010 05:33:15 Milan Straka wrote:
> If the rebalancing is done in the case of broken balance, ie. in
> sizeR > delta*sizeL, there is a simple counterexample (you will need
> fixed-width font):
>    2                                                          (A)
> 1     5
>      4 6
>     3   7
> 
> and delete 1.

Urk.  I see where the problem is.  The first equation on page 27 gives the 
state of things once they are out of balance in conjunction with Fig 6.

  n + alpha n + 1 = wx + 1

In other words, an element has been added to the right side (containing n + 
alpha n + 1) items so it now contains one more item than w times the x items 
on the left side.  The equalities and such that follow ensure a re-balance 
will always fix this situation.

What they don't show, however, is what happens if things get out of balance in 
by deleting an item from the left-hand side.  In this case, the right side can 
windup exceed the left by anywhere up to w times (i.e., as in your example).  
The required fix is to redo all the inequalities using

  n + alpha n + 1 = wx + e,

for e = 1, 2, ..., w (in most cases only e = w will also need checking).

Cheers!  -Tyson

PS:  In short, unless I'm missing something, Adam only gave a proof/conditions 
for insertion.  The deletion case still needs to be done.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part.
Url : http://www.haskell.org/pipermail/libraries/attachments/20100804/ab622b5d/attachment.bin