search

frptools / collectable

High-performance immutable data structures for modern JavaScript and TypeScript applications. Functional interfaces, deep/composite operations API, mixed mutability API, TypeScript definitions, ES2015 module exports.
MIT License
273 stars 14 forks source link

RBT(fix): update node values when swapping contents; fixes #44 #46

Closed not-an-aardvark closed 7 years ago

not-an-aardvark commented 7 years ago

When rebalancing a red-black tree, the swapNodeContents method is used to exchange the contents of two nodes. Previously, the method was only transferring the key of the upper node without transferring the value, resulting in an incorrect node with the key of one entry and the value of another. This commit ensures that both the key and the value are swapped.

not-an-aardvark commented 7 years ago

This is rebased and should be ready to merge, except that the build is failing (presumably for the same reasons as https://github.com/frptools/collectable/issues/44#issuecomment-314394859).

axefrog commented 7 years ago

Before I consider this PR, could you check my other response? An understanding of the mutation context is pretty important before making changes related to mutability.

not-an-aardvark commented 7 years ago

I read through the other response a few times. It seems to make sense to me on a conceptual level (and it's a pretty interesting way of handling mutability), although I think I would probably understand it better by working with it in the code.

You mentioned "changes related to mutability" -- would you say this change relates to mutability? I had thought this change was orthogonal since the bug applies to the immutable API as well, but of course, you would know better than I would.

axefrog commented 7 years ago

Thanks, merged and published.

axefrog commented 7 years ago

Sorry re: my earlier comment, I was in a hurry and was just waiting in general until you'd absorbed that info before reviewing the PR.