w8r/avl

some suggested documentation enhancements for range() and noDuplicates

Opened this issue · 2 comments

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 commented

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

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()