nalply/rbts

Typescript red-black tree

rbts's Issues

need to add equality comparator

202 line's key !== node.key is acts like a reference comparison for an Object.
so, It is impossible to process a case where an object of the nature of a record is used as a key.

It would be better to add comparator like equalOp?: (a: K, b: K) => boolean in Tree<K, V> constructor parameter.

/** @internal */_findNode(
  key: K,
  node: Node<K, V> = this._root,
): Node<K, V> {
  while (node.ok && key !== node.key)
//                  ^^^^^^^^^^^^^^^^ --- here is problem
    node = this._less(key, node) ? node._left : node._right
  return node
}

Invariant violated

rbts/test.ts

Line 98 in 822038a

isFalse(rbt._invariantViolated(), 'invariant violated')

produces:

AssertionError: invariant violated: expected 'left is smaller (at b with depth 1)' to be false

More iteration tools

• iterate from and to
• pagination
• ...?

Run and test in the browser environment

deleteNode() throws

rbts/test.ts

Line 272 in 827af6c

rbt.deleteNode(node)

throws:

TypeError: Cannot assign to read only property '_black' of object '[object Object]'

Minor refinement in test.ts: use ok() and nil()

rbts/test.ts

Lines 12 to 16 in 25e5a34

	const isNilNode = (value: any) =>
	chai.assert(value === Node.nil, 'not a nil Node')
	const isOkNode = (value: any) =>
	chai.assert(value.constructor !== Node || value !== Node.nil,
	'not an ok Node')

use ok() and nil() with isTrue() instead

Installation fails

rbts/package.json

Line 8 in 589327d

"install": "tsc",

When installing you get tsc: command not found, probably due to the above.
https://docs.npmjs.com/cli/v8/using-npm/scripts#npm-install

Profile

Profile both in Node and in the browser.

Add repository badges

Following this Code Repository Badges Tutorial...