TypeError in BST successor/predecessor-methods when used at boundaries

[akloeber]

Under special circumstances there is a type error thrown when the successor/predecessor methods of BST are invoked at the boundaries (i.e. first or last key):

TypeError: Cannot read property 'leftChild' of null
    at BinarySearchTree.predecessorNode (/Users/aske/Repos/dsjslib/lib/BinarySearchTree.js:161:45)
    at BinarySearchTree.predecessor (/Users/aske/Repos/dsjslib/lib/BinarySearchTree.js:191:25)
    ...

If the values are inserted in chronological order successor() on the last key returns null but predecessor() on the first key provokes the error. If the values are inserted in anti-chronological order the behavior is the other way around.

I will issue a pull request for TestBST.js that reproduces this behavior.

[monmohan]

Fixed with https://github.com/monmohan/dsjslib/commit/5d3cfa1934009c3dd5c7f8a9bdaff150dde28dab

[akloeber]

It's been a while now. Can you please push a new version to npm? This renders successor/predecessor unusable and there is no workaround. min/max won't work neither under certain conditions (e.g. same TypeError thrown when invoked on empty tree).

[monmohan]

Sure. I think I have fixed it but not pushed to npm. Let me do that :)

On Thu Nov 13 2014 at 3:12:34 PM Andreas Klöber notifications@github.com wrote:

It's been a while now. Can you please push a new version to npm? This renders successor/predecessor unusable and there is no workaround. min/max won't work neither under certain conditions (e.g. same TypeError thrown when invoked on empty tree).

— Reply to this email directly or view it on GitHub https://github.com/monmohan/dsjslib/issues/7#issuecomment-62850602.

[akloeber]

Thanks that would be great as your commit 5d3cfa1 fixes all those issues.

[monmohan]

Hello, I just did a couple of modifications and also pushed this to npm. Can you please check it this is fine.. I am actually travelling and many times dont have access to network.. Thanks Monmohan

On Thu, Nov 13, 2014 at 3:56 PM, Andreas Klöber notifications@github.com wrote:

Thanks that would be great as your commit 5d3cfa1 https://github.com/monmohan/dsjslib/commit/5d3cfa1934009c3dd5c7f8a9bdaff150dde28dab fixes all those issues.

— Reply to this email directly or view it on GitHub https://github.com/monmohan/dsjslib/issues/7#issuecomment-62853799.

[akloeber]

Good job, with v0.6.14 all tests pass.

[monmohan]

Thanks. I am also trying to understand how the library can be made more useful so please let me know if you are folks you know and are using it have suggestions. Monmohan

On Fri, Nov 14, 2014 at 2:43 AM, Andreas Klöber notifications@github.com wrote:

Good job, with v0.6.14 all tests pass.

— Reply to this email directly or view it on GitHub https://github.com/monmohan/dsjslib/issues/7#issuecomment-62943717.

[akloeber]

Well, one thing that is definitely missing with regard to a complete API is a simple size() method. We are using our own thin wrapper around AVLTree so this is not an issue for us but it should be a quick win for you to add. Furthermore we have implemented an ES6-style iterator (see http://wiki.ecmascript.org/doku.php?id=harmony:iterators) to iterate through the elements via for-of in ascending order which would make sense to be provided directly. Another useful feature would be a pair of methods to get the element next to a given key even if there is no element with exactly that key (may be called before() resp. after()) whereas successor() and predecessor() should return null on keys that are not present in the set. I could raise issues if other features that might be useful come into my mind.

[monmohan]

Thanks . I will definitely try to address these . Please do raise issues when you think that something is missing which should ideally be provided by library . It would also be good to have feedback on other data structures you are using or any missing data structure that you require but is not present in the library

Sent from my iPhone

On 18 Nov 2014, at 3:29 am, Andreas Klöber notifications@github.com wrote:

Well, one thing that is definitely missing with regard to a complete API is a simple size() method. We are using our own thin wrapper around AVLTree so this is not an issue for us but it should be a quick win for you to add. Furthermore we have implemented an ES6-style iterator (see http://wiki.ecmascript.org/doku.php?id=harmony:iterators) to iterate through the elements via for-of in ascending order which would make sense to be provided directly. Another useful feature would be a pair of methods to get the element next to a given key even if there is no element with exactly that key (may be called before() resp. after()) whereas successor() and predecessor() should return null on keys that are not present in the set. I could raise issues if other features that might be useful come into my mind.

— Reply to this email directly or view it on GitHub.