Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

some suggested documentation enhancements for range() and noDuplicates #33

Open
lsemprini opened this issue Jun 25, 2020 · 2 comments
Open

Comments

@lsemprini
Copy link

lsemprini commented Jun 25, 2020

Thank you for your awesome library...so nice to have something simple and short.

Here are some improvements to add to the documentation, BOTH in the source code and under API in README.md:

range() does not clearly explain the boundary conditions > vs >= at start and end....
OLD
   * Walk key range from `low` to `high`. Stops if `fn` returns a value.
NEW
   * Walk key range from `low` to `high` inclusive. 
   * Stops if `fn` returns a true value.
   * Walk starts (first callback) at first node >= `low`.
   * Walk ends (no callback) at first node > `high`.
   * If tree was created with !noDuplicates and tree contains 
   * more than one node with equal keys >= `low` or > `high`,
   * range() stops/starts at the first such node.

The following functions have a major caveat when noDuplicates is false:

find()
OLD
   * Find node by key
NEW
   * Find node by key.
   * WARNING: If tree was created with !noDuplicates and tree contains 
   * more than one node with `key`, returns a RANDOM node with `key`.
   * See find_ge or find_gt if duplicate order is important to you.

(I will submit the code for find_ge() and find_gt() in a separate GitHub issue)

insert()
OLD
   * Insert a node into the tree
NEW
   * Insert a node into the tree.
   * If tree was created with noDuplicates and tree already contains 
   * one or more nodes with `key`, does not insert anything and returns null.
   * Otherwise returns newly inserted node.
   * If tree was created with !noDuplicates and tree already contains 
   * one or more nodes with `key`, inserts new node before existing nodes.

remove()
OLD
   * Removes the node from the tree. If not found, returns null.
NEW
   * Removes the node from the tree. If not found, returns null.
   * WARNING: If tree was created with !noDuplicates and tree contains 
   * more than one node with `key`, removes a RANDOM node with `key`
   * and leaves the other nodes with key in the tree.
@w8r
Copy link
Owner

w8r commented Jun 25, 2020

I do agree that this is not obvious. But I guess the returned nodes in the tree with duplicates are not exactly random, they just depend on the traversal direction and insertion order.
Actually would be interesting to introduce a test for that

@lsemprini
Copy link
Author

Yup that's true they're not random in the rand() sense, but for the library user who is not aware of the implementation, it's one of those "it is implementation-defined which node you get" which is effectively the same :)

It's better to have predictable behavior if the user has chosen noDuplicates===false

FYI I just edited the OP above to add noDuplicates-related dox to range() too. I realized the same issue applies to range()

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants