Class TreeIndex<T, K>

An indexed collection that is backed by the recommended implementation that strikes a balance between fast storage and fast retrieval of elements. You may assume that most operations are at least within O(log(n)) and that all elements are ordered from smallest to largest.

import { TreeIndex } from "scl";

interface Person {
  firstName: string
  email: string,
  age: number,
}

const personsSortedByAge = new TreeIndex<Person, number>([
  {
    firstName: 'Jack',
    email: 'jack.smith@gmail.com',
    age: 34
  },
  {
    firstName: 'Bob',
    email: 'thebobman@gmail.com',
    age: 17
  },
  {
     firstName: 'Jessie',
     email: 'jessie@gmail.com',
     age: 25
  },
  {
    firstName: 'Anna',
    email: 'anna@outlook.com',
    age: 58
  }
]);

const jack = personsSortedByAge.findKey(34);

// The following will return Jessie (aged 25)
const oldestPersonYoungerThan30 = personsSortedByAge.lowerKey(30)

// This will print names in the following order:
// Bob (aged 17)
// Jessie (aged 25)
// Jack (aged 34)
// Anna (aged 58)
for (const person of personsSortedByAge) {
  console.log(person.fullName);
}

See

AVLTreeIndex

Type Parameters

  • T
  • K = T

Hierarchy (View Summary)

Constructors

constructor

Properties

getKey isEqual isKeyLessThan onDuplicateElements onDuplicateKeys

Accessors

size

Methods

[iterator] add areKeysEqual begin clear clone delete deleteAll deleteAt deleteKey end equalKeys findKey getAddHint getGreatestLowerBound getLeastUpperBound getNearest has hasKey toRange

Constructors

constructor

Properties

getKey

getKey: (element: T) => K

isEqual

isEqual: (a: T, b: T) => boolean

isKeyLessThan

isKeyLessThan: (a: K, b: K) => boolean

onDuplicateElements

onDuplicateElements: ResolveAction

onDuplicateKeys

onDuplicateKeys: ResolveAction

Accessors

size

  • get size(): number

  • Count the amount of elements in the collection.

    ⚠️ In most cases, this should be an O(1) operation. However, there are cases where this can be an O(n) operation. Therefore, it is recommended to always cache the result in a local variable.

    Returns number

Methods

[iterator]

  • "[iterator]"(): Generator<T, void, unknown>

  • Returns an object which is able to sift through the values in this collection.

    The order by which the elements are traversed depends on the kind of collection. For unordered collections, the iteration order is unspecified and may even differ between two iterations on the same collection.

    Returns Generator<T, void, unknown>

add

  • add(element: T, hint?: unknown): AddResult<T>

  • Add a new element to the index. Whether the element is ignored, replaced or whether an error is thrown depends on the value passed to onDuplicateKeys and onDuplicateElements.

    This operation takes O(log(n)) time.

    The function will first attempt to apply onDuplicateElements and if that didn't do anything special it will continue with onDuplicateKeys.

    The return value of the function depends on whether element was added, ignored or replaced:

    • The element was added to the index. The method returns true with a cursor pointing to the newly added element.
    • The element was replaced. The method returns true with a cursor pointing to the location where the element was replaced.
    • The element was ignored. The method returns false with a cursor pointing to the location of the element in the index that forced this element to be ignored.

    Parameters

    • element: T
    • Optionalhint: unknown

      A transparent object obtained with RBTreeIndex.getAddHint that can speed up the insertion process.

    Returns AddResult<T>

    See

areKeysEqual

begin

clear

  • clear(): void

  • Remove all elements from this collection, effectively setting the collection to the empty collection.

    Returns void

clone

  • clone(): RBTreeIndex<T, K>

  • Make a shallow copy of this tree so that the new tree contains the exact same elements but inserting and removing elements will not change the original tree.

    import { RBTreeIndex } from "scl";

    const index = new RBTreeIndex<number>([1, 2, 3]);

    const cloned = index.clone();

    cloned.delete(2);

    assert(cloned.size === 2);

    assert(index.size === 3);

    This method currently takes O(n.log(n)) time.

    Returns RBTreeIndex<T, K>

delete

  • delete(element: T): boolean

  • Remove an element from the collection. If multiple elements are matched, the collection picks one of them.

    Parameters

    • element: T

    Returns boolean

    true if the element was found, false otherwise.

deleteAll

  • deleteAll(element: T): number

  • Remove an element from the collection. If multiple elements are matched, the collection removes all of them.

    Parameters

    • element: T

    Returns number

    The amount of elements that was removed.

deleteAt

  • deleteAt(node: RBNode<T>): void

  • Delete an element from the tree by providing its location in the tree with an RBTreeIndexCursor.

    This method takes O(log(n)) time. It is slightly faster than deleting the element by key due to the fact that a search for the node has already been done.

    Parameters

    • node: RBNode<T>

    Returns void

deleteKey

  • deleteKey(key: K): number

  • Delete a pair from the underlying collection that has the given key as key.

    Returns the amount of items that have been deleted.

    Parameters

    • key: K

    Returns number

end

equalKeys

  • equalKeys(key: K): BSNodeRange<T>

  • Get a range of elements that contain the given key. The range may be empty if no elements with the requested key were found.

    const aged32 = personsSortedByAge.equalKeys(32);

    // There are no people who are exactly 32 years old
    assert(aged32.size === 0);

    for (const person of personsSortedByAge.equalKeys(17)) {
      console.log(`${person.firstName} is 17 years old.`);
    }

    Parameters

    • key: K

      The key that should be searched for

    Returns BSNodeRange<T>

    A range of elements that contain the given key

findKey

  • findKey(key: K): undefined | BSNode<T>

  • This method always returns the topmost node that contains the given key, which means that calling next() on the result will always return a node with the same key if there is any.

    This method takes O(log(n)) time.

    Parameters

    • key: K

      The key to search for.

    Returns undefined | BSNode<T>

getAddHint

  • getAddHint(element: T): unknown

  • Returns a transparent object that can be used as an argument to add to speed up things. Generally, you don't have to use this method.

    Parameters

    • element: T

    Returns unknown

getGreatestLowerBound

getLeastUpperBound

getNearest

has

  • has(element: T): boolean

  • Checks if the collection holds the given element.

    Parameters

    • element: T

      The element to check membership of.

    Returns boolean

    True if the collections holds the given element, false otherwise.

hasKey

  • hasKey(key: K): boolean

  • Checks whether there a pair in this collection that has the given key.

    Parameters

    • key: K

    Returns boolean

toRange

Settings

Member Visibility

On This Page

Constructors
Properties
Accessors
Methods