@phosphor/collections

@phosphor/collections

Version 1.2.0
Published 4 years ago
89.2 kB
1 dependency
BSD-3-Clause license

Install

npm i @phosphor/collections

yarn add @phosphor/collections

pnpm add @phosphor/collections

Overview

PhosphorJS - Generic Collections

Classes

class BPlusTree

class BPlusTree<T> implements IIterable<T>, IRetroable<T> {}

A generic B+ tree.
#### Notes Most operations have O(log32 n) or better complexity.

constructor

constructor(cmp: (a: T, b: T) => number);

Construct a new B+ tree.
Parameter cmp
The item comparison function for the tree.

property cmp

readonly cmp: (a: T, b: T) => number;

The item comparison function for the tree.
#### Complexity O(1)

property first

readonly first: {};

The first item in the tree.
This is undefined if the tree is empty.
#### Complexity O(log32 n)

property isEmpty

readonly isEmpty: boolean;

Whether the tree is empty.
#### Complexity O(1)

property last

readonly last: {};

The last item in the tree.
This is undefined if the tree is empty.
#### Complexity O(log32 n)

property size

readonly size: number;

The size of the tree.
#### Complexity O(1)

method assign

assign: (items: IterableOrArrayLike<T>) => void;

Assign new items to the tree, replacing all current items.
Parameter items
The items to assign to the tree.
#### Complexity O(n log32 n)

method at

at: (index: number) => T | undefined;

Get the item at a particular index.
Parameter index
The index of the item of interest. Negative values are taken as an offset from the end of the tree.
Returns
The item at the specified index, or undefined if the index is out of range.
#### Complexity O(log32 n)

method clear

clear: () => void;

Clear the contents of the tree.
#### Complexity O(n)

method delete

delete: <U>(key: U, cmp: (item: T, key: U) => number) => T | undefined;

Delete an item which matches a particular key.
Parameter key
The key of interest.
Parameter cmp
A function which compares an item against the key.
Returns
The item removed from the tree, or undefined if no item matched the given key.
#### Complexity O(log32 n)

method get

get: <U>(key: U, cmp: (item: T, key: U) => number) => T | undefined;

Get the item which matches a key.
Parameter item
The key of interest.
Parameter cmp
A function which compares an item against the key.
Returns
The item which matches the given key, or undefined if the tree does not have a matching item.
#### Complexity O(log32 n)

method has

has: <U>(key: U, cmp: (item: T, key: U) => number) => boolean;

Test whether the tree has an item which matches a key.
Parameter key
The key of interest.
Parameter cmp
A function which compares an item against the key.
Returns
true if the tree has an item which matches the given key, false otherwise.
#### Complexity O(log32 n)

method indexOf

indexOf: <U>(key: U, cmp: (item: T, key: U) => number) => number;

Get the index of an item which matches a key.
Parameter key
The key of interest.
Parameter cmp
A function which compares an item against the key.
Returns
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)

method insert

insert: (item: T) => T | undefined;

Insert an item into the tree.
Parameter item
The item of interest.
Returns
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)

method iter

iter: () => IIterator<T>;

Create an iterator over the items in the tree.
Returns
A new iterator starting with the first item.
#### Complexity O(log32 n)

method remove

remove: (index: number) => T | undefined;

Remove an item at a particular index.
Parameter index
The index of the item to remove. Negative values are taken as an offset from the end of the tree.
Returns
The item removed from the tree, or undefined if the given index is out of range.
#### Complexity O(log32 n)

method retro

retro: () => IIterator<T>;

Create a reverse iterator over the items in the tree.
Returns
A new iterator starting with the last item.
#### Complexity O(log32 n)

method retroSlice

retroSlice: (start?: number, stop?: number) => IIterator<T>;

Create a reverse iterator for a slice of items in the tree.
Parameter start
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.
Parameter stop
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
A new reverse iterator starting with the specified item.
#### Complexity O(log32 n)

method slice

slice: (start?: number, stop?: number) => IIterator<T>;

Create an iterator for a slice of items in the tree.
Parameter start
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.
Parameter stop
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
A new iterator starting with the specified item.
#### Complexity O(log32 n)

method update

update: (items: IterableOrArrayLike<T>) => void;

Update the tree with multiple items.
Parameter items
The items to insert into the tree.
#### Complexity O(k log32 n)

class LinkedList

class LinkedList<T> implements IIterable<T>, IRetroable<T> {}

A generic doubly-linked list.

constructor

constructor();

Construct a new linked list.

property first

readonly first: {};

The first value in the list.
This is undefined if the list is empty.
#### Complexity Constant.

property firstNode

readonly firstNode: LinkedList.INode<T>;

The first node in the list.
This is null if the list is empty.
#### Complexity Constant.

property isEmpty

readonly isEmpty: boolean;

Whether the list is empty.
#### Complexity Constant.

property last

readonly last: {};

The last value in the list.
This is undefined if the list is empty.
#### Complexity Constant.

property lastNode

readonly lastNode: LinkedList.INode<T>;

The last node in the list.
This is null if the list is empty.
#### Complexity Constant.

property length

readonly length: number;

The length of the list.
#### Complexity Constant.
#### Notes This is equivalent to size.
This property is deprecated.

property size

readonly size: number;

The size of the list.
#### Complexity O(1)
#### Notes This is equivalent to length.

method addFirst

addFirst: (value: T) => LinkedList.INode<T>;

Add a value to the beginning of the list.
Parameter value
The value to add to the beginning of the list.
Returns
The list node which holds the value.
#### Complexity Constant.

method addLast

addLast: (value: T) => LinkedList.INode<T>;

Add a value to the end of the list.
Parameter value
The value to add to the end of the list.
Returns
The list node which holds the value.
#### Complexity Constant.

method assign

assign: (values: IterableOrArrayLike<T>) => void;

Assign new values to the list, replacing all current values.
Parameter values
The values to assign to the list.
#### Complexity Linear.

method clear

clear: () => void;

Remove all values from the list.
#### Complexity Linear.

method insertAfter

insertAfter: (value: T, ref: LinkedList.INode<T> | null) => LinkedList.INode<T>;

Insert a value after a specific node in the list.
Parameter value
The value to insert after the reference node.
Parameter ref
The reference node of interest. If this is null, the value will be added to the end of the list.
Returns
The list node which holds the value.
#### Notes The reference node must be owned by the list.
#### Complexity Constant.

method insertBefore

insertBefore: (value: T, ref: LinkedList.INode<T> | null) => LinkedList.INode<T>;

Insert a value before a specific node in the list.
Parameter value
The value to insert before the reference node.
Parameter ref
The reference node of interest. If this is null, the value will be added to the beginning of the list.
Returns
The list node which holds the value.
#### Notes The reference node must be owned by the list.
#### Complexity Constant.

method iter

iter: () => IIterator<T>;

Create an iterator over the values in the list.
Returns
A new iterator starting with the first value.
#### Complexity Constant.

method nodes

nodes: () => IIterator<LinkedList.INode<T>>;

Create an iterator over the nodes in the list.
Returns
A new iterator starting with the first node.
#### Complexity Constant.

method pop

pop: () => T | undefined;

Remove and return the value at the end of the list.
Returns
The removed value, or undefined if the list is empty.
#### Complexity Constant.
#### Notes This is equivalent to removeLast.

method push

push: (value: T) => void;

Add a value to the end of the list.
Parameter value
The value to add to the end of the list.
#### Complexity Constant.
#### Notes This is equivalent to addLast.

method removeFirst

removeFirst: () => T | undefined;

Remove and return the value at the beginning of the list.
Returns
The removed value, or undefined if the list is empty.
#### Complexity Constant.

method removeLast

removeLast: () => T | undefined;

Remove and return the value at the end of the list.
Returns
The removed value, or undefined if the list is empty.
#### Complexity Constant.

method removeNode

removeNode: (node: LinkedList.INode<T>) => void;

Remove a specific node from the list.
Parameter node
The node to remove from the list.
#### Complexity Constant.
#### Notes The node must be owned by the list.

method retro

retro: () => IIterator<T>;

Create a reverse iterator over the values in the list.
Returns
A new iterator starting with the last value.
#### Complexity Constant.

method retroNodes

retroNodes: () => IIterator<LinkedList.INode<T>>;

Create a reverse iterator over the nodes in the list.
Returns
A new iterator starting with the last node.
#### Complexity Constant.

method shift

shift: (value: T) => void;

Add a value to the beginning of the list.
Parameter value
The value to add to the beginning of the list.
#### Complexity Constant.
#### Notes This is equivalent to addFirst.

method unshift

unshift: () => T | undefined;

Remove and return the value at the beginning of the list.
Returns
The removed value, or undefined if the list is empty.
#### Complexity Constant.
#### Notes This is equivalent to removeFirst.

Namespaces

namespace BPlusTree

namespace BPlusTree {}

The namespace for the BPlusTree class statics.

function from

from: <T>(
    items: IterableOrArrayLike<T>,
    cmp: (a: T, b: T) => number
) => BPlusTree<T>;

Create a new B+ tree populated with the given items.
Parameter items
The items to add to the tree.
Parameter cmp
The item comparison function for the tree.
Returns
A new B+ tree populated with the given items.
#### Complexity O(n log32 n)

namespace LinkedList

namespace LinkedList {}

The namespace for the LinkedList class statics.

function from

from: <T>(values: IterableOrArrayLike<T>) => LinkedList<T>;

Create a linked list from an iterable of values.
Parameter values
The iterable or array-like object of interest.
Returns
A new linked list initialized with the given values.
#### Complexity Linear.

class ForwardNodeIterator

class ForwardNodeIterator<T> implements IIterator<INode<T>> {}

A forward iterator for nodes in a linked list.

constructor

constructor(node: INode<T>);

Construct a forward node iterator.
Parameter node
The first node in the list.

method clone

clone: () => IIterator<INode<T>>;

Create an independent clone of the iterator.
Returns
A new independent clone of the iterator.

method iter

iter: () => IIterator<INode<T>>;

Get an iterator over the object's values.
Returns
An iterator which yields the object's values.

method next

next: () => INode<T> | undefined;

Get the next value from the iterator.
Returns
The next value from the iterator, or undefined.

class ForwardValueIterator

class ForwardValueIterator<T> implements IIterator<T> {}

A forward iterator for values in a linked list.

constructor

constructor(node: INode<T>);

Construct a forward value iterator.
Parameter node
The first node in the list.

method clone

clone: () => IIterator<T>;

Create an independent clone of the iterator.
Returns
A new independent clone of the iterator.

method iter

iter: () => IIterator<T>;

Get an iterator over the object's values.
Returns
An iterator which yields the object's values.

method next

next: () => T | undefined;

Get the next value from the iterator.
Returns
The next value from the iterator, or undefined.

class RetroNodeIterator

class RetroNodeIterator<T> implements IIterator<INode<T>> {}

A reverse iterator for nodes in a linked list.

constructor

constructor(node: INode<T>);

Construct a retro node iterator.
Parameter node
The last node in the list.

method clone

clone: () => IIterator<INode<T>>;

Create an independent clone of the iterator.
Returns
A new independent clone of the iterator.

method iter

iter: () => IIterator<INode<T>>;

Get an iterator over the object's values.
Returns
An iterator which yields the object's values.

method next

next: () => INode<T> | undefined;

Get the next value from the iterator.
Returns
The next value from the iterator, or undefined.

class RetroValueIterator

class RetroValueIterator<T> implements IIterator<T> {}

A reverse iterator for values in a linked list.

constructor

constructor(node: INode<T>);

Construct a retro value iterator.
Parameter node
The last node in the list.

method clone

clone: () => IIterator<T>;

Create an independent clone of the iterator.
Returns
A new independent clone of the iterator.

method iter

iter: () => IIterator<T>;

Get an iterator over the object's values.
Returns
An iterator which yields the object's values.

method next

next: () => T | undefined;

Get the next value from the iterator.
Returns
The next value from the iterator, or undefined.

interface INode

interface INode<T> {}

An object which represents a node in a linked list.
#### Notes User code will not create linked list nodes directly. Nodes are created automatically when values are added to a list.

property list

readonly list: LinkedList<T> | null;

The linked list which created and owns the node.
This will be null when the node is removed from the list.

property next

readonly next: INode<T> | null;

The next node in the list.
This will be null when the node is the last node in the list or when the node is removed from the list.

property prev

readonly prev: INode<T> | null;

The previous node in the list.
This will be null when the node is the first node in the list or when the node is removed from the list.

property value

readonly value: T;

The user value stored in the node.

Package Files (3)

Dependencies (1)

@phosphor/algorithm

Peer Dependencies (0)

No peer dependencies.

Badge

To add a badge like this oneto your package's README, use the codes available below.

You may also use Shields.io to create a custom badge linking to https://www.jsdocs.io/package/@phosphor/collections.

Markdown

[![jsDocs.io](https://img.shields.io/badge/jsDocs.io-reference-blue)](https://www.jsdocs.io/package/@phosphor/collections)

HTML

<a href="https://www.jsdocs.io/package/@phosphor/collections"><img src="https://img.shields.io/badge/jsDocs.io-reference-blue" alt="jsDocs.io"></a>

Updated 1 year ago.
Package analyzed in 1937 ms.
Missing or incorrect documentation? Open an issue for this package.

@phosphor/collections

Install

Overview

Index

Classes

Namespaces

Classes

class BPlusTree

constructor

Parameter cmp

property cmp

property first

property isEmpty

property last

property size

method assign

Parameter items

method at

Parameter index

Returns

method clear

method delete

Parameter key

Parameter cmp

Returns

method get

Parameter item

Parameter cmp

Returns

method has

Parameter key

Parameter cmp

Returns

method indexOf

Parameter key

Parameter cmp

Returns

method insert

Parameter item

Returns

method iter

Returns

method remove

Parameter index

Returns

method retro

Returns

method retroSlice

Parameter start

Parameter stop

Returns

method slice

Parameter start

Parameter stop

Returns

method update

Parameter items

class LinkedList

constructor

property first

property firstNode

property isEmpty

property last

property lastNode

property length

property size

method addFirst

Parameter value

Returns

method addLast

Parameter value

Returns

method assign

Parameter values

method clear

method insertAfter

Parameter value

Parameter ref

Returns

method insertBefore