Standard Collections Library for TypeScript
Options
All
  • Public
  • Public/Protected
  • All
Menu

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

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Properties

getKey

getKey: (element: T) => K

Type declaration

    • (element: T): K

    • Parameters

      • element: T

      Returns K

isEqual

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

Type declaration

    • (a: T, b: T): boolean

    • Parameters

      • a: T
      • b: T

      Returns boolean

isKeyLessThan

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

Type declaration

    • (a: K, b: K): boolean

    • Parameters

      • a: K
      • b: K

      Returns boolean

onDuplicateElements

onDuplicateElements: ResolveAction

onDuplicateKeys

onDuplicateKeys: ResolveAction

Accessors

size

  • get size(): number

Methods

[Symbol.iterator]

  • [Symbol.iterator](): 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.
    see

    AddResult

    see

    delete

    Parameters

    • element: T
    • Optional hint: unknown

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

    Returns AddResult<T>

areKeysEqual

  • areKeysEqual(a: K, b: K): boolean

begin

  • begin(): null | BSNode<T>

clear

  • clear(): void

clone

  • 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

deleteAll

  • deleteAll(element: T): number

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

end

  • end(): null | BSNode<T>

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): null | 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 null | BSNode<T>

getAddHint

  • getAddHint(element: T): unknown

getGreatestLowerBound

  • getGreatestLowerBound(key: K): null | BSNode<T>

getLeastUpperBound

  • getLeastUpperBound(key: K): null | BSNode<T>

getNearest

  • getNearest(key: K): null | BSNode<T>

has

  • has(element: T): boolean

hasKey

  • hasKey(key: K): boolean

toRange

  • toRange(): BSNodeRange<T>

Legend

  • Property
  • Method
  • Accessor
  • Property
  • Method
  • Inherited property
  • Inherited method

Generated using TypeDoc