Functional Red-Black Tree

var createTree = require("functional-red-black-tree");

var createTree = require("functional-red-black-tree");

// Create a tree with default comparison
var t1 = createTree();

// Insert some items
var t2 = t1.insert(1, "foo");
var t3 = t2.insert(2, "bar");

// Remove something  
var t4 = t3.remove(1);

// Access values
console.log(t3.get(1)); // "foo"
console.log(t4.get(1)); // undefined

// Iterate over tree
t3.forEach(function(key, value) {
  console.log(key, value);
});

/**
 * Creates an empty functional tree
 * @param {function} [compare] - Optional comparison function (same semantics as Array.sort())
 * @returns {RedBlackTree} An empty tree ordered by compare function
 */
function createTree(compare);

// Number of items in the tree
tree.length;

// Sorted array of all keys in the tree
tree.keys;

// Array of all values in the tree  
tree.values;

// Root node of the tree (or null if empty)
tree.root;

// Iterator pointing to first element
tree.begin;

// Iterator pointing to last element
tree.end;

/**
 * Creates a new tree with the key-value pair inserted
 * @param {*} key - Key of the item to insert
 * @param {*} value - Value of the item to insert
 * @returns {RedBlackTree} New tree with key and value inserted
 */
tree.insert(key, value);

/**
 * Removes the first item with key from tree
 * @param {*} key - Key of the item to remove
 * @returns {RedBlackTree} New tree with the given item removed if it exists
 */
tree.remove(key);

/**
 * Retrieves the value associated to the given key
 * @param {*} key - Key of the item to look up
 * @returns {*} The value of the first node associated to key, or undefined
 */
tree.get(key);

/**
 * Returns an iterator pointing to the first item with key
 * @param {*} key - Key to search for
 * @returns {RedBlackTreeIterator} Iterator at the element, or invalid iterator if not found
 */
tree.find(key);

/**
 * Find the first item in the tree whose key is >= key
 * @param {*} key - Key to search for
 * @returns {RedBlackTreeIterator} Iterator at the given element
 */
tree.ge(key);

/**
 * Finds the first item in the tree whose key is > key
 * @param {*} key - Key to search for
 * @returns {RedBlackTreeIterator} Iterator at the given element
 */
tree.gt(key);

/**
 * Finds the last item in the tree whose key is < key
 * @param {*} key - Key to search for
 * @returns {RedBlackTreeIterator} Iterator at the given element
 */
tree.lt(key);

/**
 * Finds the last item in the tree whose key is <= key
 * @param {*} key - Key to search for
 * @returns {RedBlackTreeIterator} Iterator at the given element
 */
tree.le(key);

/**
 * Finds an iterator starting at the given position index
 * @param {number} position - Index at which the iterator gets created
 * @returns {RedBlackTreeIterator} Iterator starting at position
 */
tree.at(position);

/**
 * Walks a visitor function over the nodes of the tree in order
 * @param {function} visitor - Callback that gets executed on each node (key, value)
 * @param {*} [lo] - Optional start of the range to visit (inclusive)
 * @param {*} [hi] - Optional end of the range to visit (non-inclusive)
 * @returns {*} The last value returned by the callback
 */
tree.forEach(visitor, lo, hi);

var tree = createTree().insert(1, "a").insert(2, "b").insert(3, "c");

// Visit all nodes
tree.forEach(function(key, value) {
  console.log(key, value);
});

// Visit range [1, 3)
tree.forEach(function(key, value) {
  console.log(key, value);
}, 1, 3);

// Early termination
tree.forEach(function(key, value) {
  if (key === 2) return true; // Stop iteration
  console.log(key, value);
});

// Iterator properties
iter.valid;     // boolean - Checks if the iterator is valid
iter.key;       // * - The key of the item referenced by the iterator
iter.value;     // * - The value of the item referenced by the iterator
iter.node;      // RBNode|null - The node at the iterator's current position
iter.tree;      // RedBlackTree - The tree associated to the iterator
iter.index;     // number - Returns the position of this iterator in the sequence
iter.hasNext;   // boolean - True if iterator is not at the end of the sequence
iter.hasPrev;   // boolean - True if iterator is not at the beginning of the sequence

/**
 * Makes a copy of the iterator
 * @returns {RedBlackTreeIterator} New iterator copy
 */
iter.clone();

/**
 * Removes the item at the position of the iterator
 * @returns {RedBlackTree} New binary search tree with iter's item removed
 */
iter.remove();

/**
 * Updates the value of the node in the tree at this iterator
 * @param {*} value - New value for the node
 * @returns {RedBlackTree} New binary search tree with the corresponding node updated
 * @throws {Error} Throws "Can't update empty node!" if iterator is invalid
 */
iter.update(value);

/**
 * Advances the iterator to the next position
 */
iter.next();

/**
 * Moves the iterator backward one element
 */
iter.prev();

var tree = createTree().insert(1, "a").insert(2, "b").insert(3, "c");

// Forward iteration
var iter = tree.begin;
while(iter.valid) {
  console.log(iter.key, iter.value);
  iter.next();
}

// Backward iteration
var iter = tree.end;
while(iter.valid) {
  console.log(iter.key, iter.value);
  iter.prev();
}

// Iterator modification
var newTree = tree.begin.update("modified");
var newTree2 = tree.find(2).remove();

// Node properties
node.key;    // * - The key associated to the node
node.value;  // * - The value associated to the node  
node.left;   // RBNode|null - The left subtree of the node
node.right;  // RBNode|null - The right subtree of the node

/**
 * Red-black tree class
 */
function RedBlackTree(compare, root) {
  this._compare = compare;
  this.root = root;
}

/**
 * Tree node class
 */
function RBNode(color, key, value, left, right, count) {
  this._color = color;
  this.key = key;
  this.value = value;
  this.left = left;
  this.right = right;
  this._count = count;
}

/**
 * Iterator class for traversing tree
 */
function RedBlackTreeIterator(tree, stack) {
  this.tree = tree;
  this._stack = stack;
}

/**
 * Default comparison function
 * @param {*} a - First value to compare
 * @param {*} b - Second value to compare  
 * @returns {number} -1 if a < b, 1 if a > b, 0 if equal
 */
function defaultCompare(a, b) {
  if(a < b) return -1;
  if(a > b) return 1;
  return 0;
}

// Custom string comparison (case-insensitive)
var tree = createTree(function(a, b) {
  a = a.toLowerCase();
  b = b.toLowerCase();
  if(a < b) return -1;
  if(a > b) return 1;
  return 0;
});

// Numeric comparison for objects
var tree = createTree(function(a, b) {
  return a.priority - b.priority;
});

var tree = createTree();
// ... populate tree ...

// Find all items between 10 and 20 (inclusive)
var results = [];
tree.forEach(function(key, value) {
  results.push({key: key, value: value});
}, 10, 21);

// Get iterator range
var start = tree.ge(10);  // First element >= 10
var end = tree.gt(20);    // First element > 20

var t1 = createTree().insert(1, "a").insert(2, "b");
var t2 = t1.insert(3, "c");  // t1 is unchanged
var t3 = t1.remove(1);       // Both t1 and t2 are unchanged

// Can iterate over previous versions while modifying
t1.forEach(function(key, value) {
  console.log("t1:", key, value);
});

t2.forEach(function(key, value) {
  console.log("t2:", key, value);
});