🔍 @aureooms/js-search-tree-spec

Search tree specification for JavaScript. See docs. Parent is @aureooms/js-bst.

// eslint-disable-next-line ava/use-test
import ava from 'ava' ;
import * as spec from '@aureooms/js-search-tree-spec' ;

spec.test(
  ava ,
  {
    name: "DummySearchTree" , // Name for the implementation
    empty: compare => new spec.DummySearchTree(compare) , // Return an empty search tree using `compare` to order keys
    from: (compare, iterable) => spec.DummySearchTree.from(compare, iterable) , // Return a search tree using `compare` to order keys initialized with the values in iterable
  } ,
  {
    length : true , // Do the implementations maintain a `length` property?
    lengths : [0, 1, 16, 17, 31, 32, 33, 63, 64, 65] , // Tree sizes to test.
  }
) ;

📰 Description

This package contains a specification test suite for search tree implementations such as @aureooms/js-red-black-tree, @aureooms/js-splay-tree, and @aureooms/js-avl-tree.

👩‍🏫 Specification

⚖️ Definition of a `Ternary Comparator`

We choose to parameterize trees using ternary comparator functions rather that key functions (as is done in Python for instance).

Comparator = ( x , x ) -> Number
Key = ( x ) -> String

compare( a , b ) < 0 <=> key( a ) < key( b )
compare( a , b ) = 0 <=> key( a ) = key( b )
compare( a , b ) > 0 <=> key( a ) > key( b )

Example of a `Ternary Comparator`

The following Comparator orders instances of String.

const compare = (a, b) => a < b ? -1 : a > b ? 1 : 0;

Exposed tree constructors

No surprises here:

const { from , empty } = SearchTree ;

`empty(Comparator) -> SearchTree`

Create an empty search tree from a comparator function.

let tree = empty( compare ) ;

`from(Comparator, Iterable) -> Tree`

Create a search tree from a comparator function and an iterable.

let tree = from( compare , 'abc' ) ;

`Tree#length -> Number` (optional)

Returns the number of elements in the tree.

if ( tree.length > 1 ) ...

`Tree#isEmpty() -> Boolean`

Returns true if the tree is empty, false otherwise.

return tree.isEmpty() ? 'empty' : 'not empty' ;

`Tree#has(x) -> Boolean`

Returns true if the tree contains given element.

if (tree.has(x)) ...

Insertion

`Tree#insert(x) -> Reference`

Insert given element in the tree and returns optional reference.

tree.insert('abc');

Could also be called Tree#add instead.

Update

`Tree#update(x) -> Reference`

Update given element in the tree and returns optional reference.

tree.insert({key: 'abc', value: 0});
tree.update({key: 'abc', value: 123});

Removal

`Tree#removeFirst(x) -> Boolean`

Remove first occurrence of element. Returns optional boolean indicating if an element was removed.

tree.insert('x');
tree.insert('x');
tree.removeFirst('x');

`Tree#removeLast(x) -> Boolean`

Remove last occurrence of element. Returns optional boolean indicating if an element was removed.

tree.insert('x');
tree.insert('x');
tree.removeLast('x');

`Tree#removeAll(x) -> Boolean`

Remove all occurrences of element. Returns optional boolean indicating if an element was removed.

tree.insert('x');
tree.insert('x');
tree.removeAll('x');

`Tree#remove(x) -> Boolean`

Alias for Tree#removeFirst.

`Tree#delete(ref)`

Remove element given reference.

let ref = tree.insert('abc');
tree.delete(ref);

Could also be called Tree#unlink instead. Leaving Tree#delete as an alias for Tree#removeFirst or Tree#removeAll to mimic the Set API.

Searching

`Tree#find(x) -> x`

`Tree#predecessor(x) -> x`

`Tree#successor(x) -> x`

`Tree#leftMost() -> x`

`Tree#rightMost() -> x`

Merging

`Tree#meld(other)`

Merge two trees. Merged trees are destroyed.

let a = from(compare, 'abc');
let b = from(compare, '123');
a.meld(b);

Split

`Tree#split(x) -> [Tree, x, Tree]`

Split a tree at x such that

const [left, key, right] = tree.split(x);
assert(compare(key, x) === 0);
assert(isBinarySearchTree({key, left, right}));

Visit

`Tree#[Symbol.iterator]() -> Iterator`

`Tree#items() -> Iterator`

Alias for Tree#[Symbol.iterator]().

`Tree#reversed() -> Iterator`

`Tree#rangeIE(left, right) -> Iterator`

`Tree#rangeII(left, right) -> Iterator`

`Tree#rangeEI(left, right) -> Iterator`

`Tree#rangeEE(left, right) -> Iterator`

`Tree#range(left, right) -> Iterator`

Alias for Tree#rangeIE(left, right) -> Iterator.

Name		Name	Last commit message	Last commit date
Latest commit History 290 Commits
doc		doc
src		src
test/src		test/src
.codacy.yml		.codacy.yml
.codeclimate.yml		.codeclimate.yml
.esdoc.json		.esdoc.json
.gitignore		.gitignore
.travis.yml		.travis.yml
LICENSE		LICENSE
README.md		README.md
package.json		package.json
renovate.json		renovate.json
yarn.lock		yarn.lock

License

make-github-pseudonymous-again/js-search-tree-spec

Folders and files

Latest commit

History

Repository files navigation

🔍 @aureooms/js-search-tree-spec

📰 Description

👩‍🏫 Specification

⚖️ Definition of a Ternary Comparator

Example of a Ternary Comparator

Exposed tree constructors

empty(Comparator) -> SearchTree

from(Comparator, Iterable) -> Tree

Tree#length -> Number (optional)

Tree#isEmpty() -> Boolean

Tree#has(x) -> Boolean

Insertion

Tree#insert(x) -> Reference

Update

Tree#update(x) -> Reference

Removal

Tree#removeFirst(x) -> Boolean

Tree#removeLast(x) -> Boolean

Tree#removeAll(x) -> Boolean

Tree#remove(x) -> Boolean

Tree#delete(ref)

Searching

Tree#find(x) -> x

Tree#predecessor(x) -> x

Tree#successor(x) -> x

Tree#leftMost() -> x

Tree#rightMost() -> x

Merging

Tree#meld(other)

Split

Tree#split(x) -> [Tree, x, Tree]

Visit

Tree#[Symbol.iterator]() -> Iterator

Tree#items() -> Iterator

Tree#reversed() -> Iterator

Tree#rangeIE(left, right) -> Iterator

Tree#rangeII(left, right) -> Iterator

Tree#rangeEI(left, right) -> Iterator

Tree#rangeEE(left, right) -> Iterator

Tree#range(left, right) -> Iterator

About

Resources