Options
All
  • Public
  • Public/Protected
  • All
Menu

Class BPlusTree<T>

A generic B+ tree. The namespace for the BPlusTree class statics.

Notes

Most operations have O(log32 n) or better complexity.

deprecated

This class will be removed in @lumino/collections@^2.0.0

deprecated

This namespace will be removed in @lumino/collections@^2.0.0

Type parameters

  • T

Hierarchy

  • BPlusTree

Implements

  • IIterable<T>
  • IRetroable<T>

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

  • Construct a new B+ tree.

    Parameters

    • cmp: function

      The item comparison function for the tree.

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

        • Parameters

          • a: T
          • b: T

          Returns number

    Returns BPlusTree

Properties

Private _root

_root: Private.Node<T> = new Private.LeafNode<T>()

cmp

cmp: function

The item comparison function for the tree.

Complexity

O(1)

Type declaration

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

    • Parameters

      • a: T
      • b: T

      Returns number

Accessors

first

  • get first(): T | undefined

  • The first item in the tree.

    This is undefined if the tree is empty.

    Complexity

    O(log32 n)

    Returns T | undefined

isEmpty

  • get isEmpty(): boolean

last

  • get last(): T | undefined

  • The last item in the tree.

    This is undefined if the tree is empty.

    Complexity

    O(log32 n)

    Returns T | undefined

size

  • get size(): number

Methods

assign

  • assign(items: IterableOrArrayLike<T>): void

  • Assign new items to the tree, replacing all current items.

    Parameters

    • items: IterableOrArrayLike<T>

      The items to assign to the tree.

      Complexity

      O(n log32 n)

    Returns void

at

  • at(index: number): T | undefined

  • Get the item at a particular index.

    Parameters

    • index: number

      The index of the item of interest. Negative values are taken as an offset from the end of the tree.

    Returns T | undefined

    The item at the specified index, or undefined if the index is out of range.

    Complexity

    O(log32 n)

clear

  • clear(): void

delete

  • delete<U>(key: U, cmp: function): T | undefined

  • Delete an item which matches a particular key.

    Type parameters

    • U

    Parameters

    • key: U

      The key of interest.

    • cmp: function

      A function which compares an item against the key.

        • (item: T, key: U): number

        • Parameters

          • item: T
          • key: U

          Returns number

    Returns T | undefined

    The item removed from the tree, or undefined if no item matched the given key.

    Complexity

    O(log32 n)

get

  • get<U>(key: U, cmp: function): T | undefined

  • Get the item which matches a key.

    Type parameters

    • U

    Parameters

    • key: U
    • cmp: function

      A function which compares an item against the key.

        • (item: T, key: U): number

        • Parameters

          • item: T
          • key: U

          Returns number

    Returns T | undefined

    The item which matches the given key, or undefined if the tree does not have a matching item.

    Complexity

    O(log32 n)

has

  • has<U>(key: U, cmp: function): boolean

  • Test whether the tree has an item which matches a key.

    Type parameters

    • U

    Parameters

    • key: U

      The key of interest.

    • cmp: function

      A function which compares an item against the key.

        • (item: T, key: U): number

        • Parameters

          • item: T
          • key: U

          Returns number

    Returns boolean

    true if the tree has an item which matches the given key, false otherwise.

    Complexity

    O(log32 n)

indexOf

  • indexOf<U>(key: U, cmp: function): number

  • Get the index of an item which matches a key.

    Type parameters

    • U

    Parameters

    • key: U

      The key of interest.

    • cmp: function

      A function which compares an item against the key.

        • (item: T, key: U): number

        • Parameters

          • item: T
          • key: U

          Returns number

    Returns number

    The index of the item which matches the given key. A negative value means that a matching item does not exist in the tree, but if one did it would reside at -index - 1.

    Complexity

    O(log32 n)

insert

  • insert(item: T): T | undefined

  • Insert an item into the tree.

    Parameters

    • item: T

      The item of interest.

    Returns T | undefined

    If the given item matches an existing item in the tree, the given item will replace it, and the existing item will be returned. Otherwise, this method returns undefined.

    Complexity

    O(log32 n)

iter

  • iter(): IIterator<T>

  • Create an iterator over the items in the tree.

    Returns IIterator<T>

    A new iterator starting with the first item.

    Complexity

    O(log32 n)

remove

  • remove(index: number): T | undefined

  • Remove an item at a particular index.

    Parameters

    • index: number

      The index of the item to remove. Negative values are taken as an offset from the end of the tree.

    Returns T | undefined

    The item removed from the tree, or undefined if the given index is out of range.

    Complexity

    O(log32 n)

retro

  • retro(): IIterator<T>

  • Create a reverse iterator over the items in the tree.

    Returns IIterator<T>

    A new iterator starting with the last item.

    Complexity

    O(log32 n)

retroSlice

  • retroSlice(start?: undefined | number, stop?: undefined | number): IIterator<T>

  • Create a reverse iterator for a slice of items in the tree.

    Parameters

    • Optional start: undefined | number

      The index of the first item, inclusive. This should be > stop. Negative values are taken as an offset from the end of the tree. The default is size - 1.

    • Optional stop: undefined | number

      The index of the last item, exclusive. This should be < start. Negative values are taken as an offset from the end of the tree. The default is -size - 1.

    Returns IIterator<T>

    A new reverse iterator starting with the specified item.

    Complexity

    O(log32 n)

slice

  • slice(start?: undefined | number, stop?: undefined | number): IIterator<T>

  • Create an iterator for a slice of items in the tree.

    Parameters

    • Optional start: undefined | number

      The index of the first item, inclusive. This should be < stop. Negative values are taken as an offset from the end of the tree. The default is 0.

    • Optional stop: undefined | number

      The index of the last item, exclusive. This should be > start. Negative values are taken as an offset from the end of the tree. The default is size.

    Returns IIterator<T>

    A new iterator starting with the specified item.

    Complexity

    O(log32 n)

update

  • update(items: IterableOrArrayLike<T>): void

  • Update the tree with multiple items.

    Parameters

    • items: IterableOrArrayLike<T>

      The items to insert into the tree.

      Complexity

      O(k log32 n)

    Returns void

Static from

  • from<T>(items: IterableOrArrayLike<T>, cmp: function): BPlusTree<T>

  • Create a new B+ tree populated with the given items.

    Type parameters

    • T

    Parameters

    • items: IterableOrArrayLike<T>

      The items to add to the tree.

    • cmp: function

      The item comparison function for the tree.

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

        • Parameters

          • a: T
          • b: T

          Returns number

    Returns BPlusTree<T>

    A new B+ tree populated with the given items.

    Complexity

    O(n log32 n)

Generated using TypeDoc