evancz/Elm — pull request #261 by maxsnew (2013-09-19 06:26:23+00:00)
Title: Fix the Dict Library

I used the algorithm from here: http://matt.might.net/articles/red-black-delete/

Adding 2 new colors makes it a bit loosely typed, but the alternative (2 Dict types, one with only red-black and one with red-black-bblack-nblack) would involve a lot of wrapping/unwrapping for the sake of type safety.

To make sure that implementation bugs surface quickly, I decided to be as specific as possible when pattern matching so any time an invariant is broken, it should fail fast with a pattern match failure.

Also, I deleted the unused code with the idea that it can always be recovered with git later if needed.

For testing I wrote a page for randomly adding and removing k/v pairs from a Dict and after extensive clicking, no errors occurred: http://share-elm.com/sprout/523a9870e4b00f123dfa613a . It doesn't work on share-elm, but it does on my machine with this patch.