collections
Advanced tools
This package contains JavaScript implementations of common data structures with idiomatic iterfaces, including extensions for Array and Object.
You can use these Node Packaged Modules with Node.js, Browserify,
Mr, or any compatible CommonJS module loader. Using a module loader
or bundler when using Collections in web browsers has the advantage of
only incorporating the modules you need. However, you can just embed
<script src="collections/collections.min.js"> and all of the
collections will be introduced as globals. :warning:
require("collections") is not supported.
npm install collections --save
var List = require("collections/list");
An ordered collection of values with fast insertion and deletion and forward and backward traversal, backed by a cyclic doubly linked list with a head node. Lists support most of the Array interface, except that they use and return nodes instead of integer indicies in analogous functions.
Lists have a head Node. The node type is available as Node on
the list prototype and can be overridden by inheritors. Each node
has prev and next properties.
var Set = require("collections/set");
A collection of unique values. The set can be iterated in the order
of insertion. With a good hash function for the stored values,
insertion and removal are fast regardless of the size of the
collection. Values may be objects. The equals and hash
functions can be overridden to provide alternate definitions of
"unique". Set is backed by FastSet and List.
var Map = require("collections/map");
A collection of key and value entries with unique keys. Keys may be
objects. The collection iterates in the order of insertion. Map
is backed by Set.
var MultiMap = require("collections/multi-map");
A collection of keys mapped to collections of values. The default
getDefault collection is an Array, but it can be a List or any
other array-like object. MultiMap inherits Map but overrides
the getDefault(key) provider.
var WeakMap = require("collections/weak-map");
A non-iterable collection of key value pairs. Keys must objects and
do not benefit from hash functions. Some engines already
implement WeakMap. The non-iterable requirement makes it possible
for weak maps to collect garbage when the key is no longer
available, without betraying when the key is collected. The shimmed
implementation undetectably annotates the given key and thus does
not necessarily leak memory, but cannot collect certain reference
graphs. This WeakMap shim was implemented by Mark Miller of Google.
var SortedSet = require("collections/sorted-set");
A collection of unique values stored in stored order, backed by a
splay tree. The equals and compare functions can be overridden
to provide alternate definitions of "unique".
The compare method must provide a total order of all unique
values. That is, if compare(a, b) === 0, it must follow that
equals(a, b).
var SortedMap = require("collections/sorted-map");
A collection of key value pairs stored in sorted order. SortedMap
is backed by SortedSet and the GenericMap mixin.
var LruSet = require("collections/lru-set");
A cache with the Least-Recently-Used strategy for truncating its
content when it’s length exceeds maxLength. LruSet is backed by
a Set and takes advantage of the already tracked insertion order.
Both getting and setting a value constitute usage, but checking
whether the set has a value and iterating values do not.
var LruMap = require("collections/lru-map");
A cache of entries backed by an LruSet.
var SortedArray = require("collections/sorted-array");
A collection of values stored in a stable sorted order, backed by an array.
var SortedArraySet = require("collections/sorted-array-set");
A collection of unique values stored in sorted order, backed by a plain array. If the given values are an actual array, the sorted array set takes ownership of that array and retains its content. A sorted array set performs better than a sorted set when it has roughly less than 100 values.
var SortedArrayMap = require("collections/sorted-array-map");
A collection of key value pairs stored in sorted order, backed by a sorted array set.
var FastSet = require("collections/fast-set");
A collection of unique values stored like a hash table. The
underlying storage is a Dict that maps hashes to lists of values
that share the same hash. Values may be objects. The equals and
hash functions can be overridden to provide alternate definitions
of "unique".
var FastMap = require("collections/fast-map");
A collection of key and value entries with unique keys, backed by a
set. Keys may be objects. FastMap is backed by FastSet and the
GenericMap mixin.
var Dict = require("collections/dict");
A collection of string to value mappings backed by a plain JavaScript object. The keys are mangled to prevent collisions with JavaScript properties.
var Heap = require("collections/heap");
A collection that can always quickly (constant time) report its largest value, with reasonable performance for incremental changes (logarithmic), using a contiguous array as its backing storage. However, it does not track the sorted order of its elements.
var Iterator = require("collections/iterator");
A wrapper for any iterable that implements iterate or iterator the
implements next, providing a rich lazy traversal interface.
require("collections/shim-array");
An ordered collection of values with fast random access, push, and
pop, but slow splice. The array module provides extensions so it
hosts all the expressiveness of other collections. The shim-array
module shims EcmaScript 5 methods onto the array prototype if they
are not natively implemented.
require("collections/shim-object");
Can be used as a mapping of owned string keys to arbitrary values.
The object module provides extensions for the Object constructor
that support the map collection interface and can delegate to
methods of collections, allowing them to gracefully handle both
object literals and collections.
For all of these constructors, the argument values is an optional
collection of initial values, and may be an array. If the values are
in a map collection, the the values are taken, but the keys are ignored.
The map argument is an optional collection to copy shallowly into
the new mapping. The map may be an object literal. If map
implements keys, it is treated as a mapping itself and copied.
Otherwise, if map implements forEach, it may be any collection
of [key, value] pairs.
equals(x, y), compare(x, y), and hash(value) are all optional
arguments overriding the meaning of equality, comparability, and
consistent hashing for the purposes of the collection. equals must
return a boolean. compare must return an integer with the same
relationship to zero as x to y. hash should consistently return the
same string for any given object.
The default equals operator is implemented in terms of ===, but
treats NaN as equal to itself and -0 as distinct from +0. It
also delegates to an equals method of either the left or right
argument if one exists. The default equality operator is shimmed as
Object.equals.
The default compare operator is implemented in terms of < and
>. It delegates to the compare method of either the left or
right argument if one exists. It inverts the result if it uses the
falls to the right argument. The default comparator is shimmed as
Object.compare.
The default hash operator uses toString for values and provides
a Unique Label for arbitrary objects. The default hash is
shimmed as Object.hash.
The default getDefault function is Function.noop, which returns
undefined. The fallback function is used when you get a
nonexistant value from any collection. The getDefault function
becomes a member of the collection object, so getDefault is called
with the collection as this, so you can also use it to guarantee
that default values in a collection are retained, as in MultiMap.
Where these methods coincide with the specification of an existing
method of Array, Array is noted as an implementation. Array+ refers
to shimmed arrays, as installed with the array module. Object
refers to methods implemented on the Object constructor function, as
opposed to the Object.prototype. Object+ in turn refers to methods
shimmed on the object constructor by the object module. These
functions accept the object as the first argument instead of the this
implied argument. Strikethrough indicates an implementation that
should exist but has not yet been made (Send a pull request!).
These are all of the collections:
(Array, Array+, Object+, Iterator, List, Set, Map, MultiMap, WeakMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict)
Whether a value for the given key exists.
(Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap, Dict)
Whether a value exists in this collection. This is slow for list (linear), but fast (logarithmic) for SortedSet and SortedArraySet, and very fast (constant) for Set.
(Array+, List, Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet)
The value for a key. If a Map or SortedMap lacks a key, returns
getDefault(key).
(Array+, Map, SortedMap, SortedArrayMap, WeakMap, Object+)
Gets the equivalent value, or falls back to getDefault(value).
(List, Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet)
Sets the value for a key.
(Map, MultiMap, WeakMap, SortedMap, LruMap, SortedArrayMap, FastMap, Dict)
Adds a value. Ignores the operation and returns false if an equivalent value already exists.
(Array+, List, Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet, Heap)
Aliases set(key, value), to assist generic methods used for maps,
sets, and other collections.
Copies values from another collection to this one.
(Array+, List, Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet, Heap)
Copies entries from another collection to this map. If the mapping
implements keys (indicating that it is a mapping) and forEach,
all of the key value pairs are copied. If the mapping only
implements forEach, it is assumed to contain [key, value] arrays
which are copied instead.
(Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap, Dict)
Deletes the value for a given key. Returns whether the key was found.
(Map, MultiMap, WeakMap, SortedMap, LruMap, SortedArrayMap, FastMap, Dict)
Deletes a value. Returns whether the value was found.
(Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet, Heap)
Deletes the equivalent value. Returns whether the value was found.
(Array+, List)
Deletes every value or every value for each key.
(Array+, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
Returns the position in the collection of a value, or -1 if it is
not found. Returns the position of the first of equivalent values.
For an Array this takes linear time. For a SortedArray and
SortedArraySet, it takes logarithmic time to perform a binary
search. For a SortedSet, this takes ammortized logarithmic time
since it incrementally updates the number of nodes under each
subtree as it rotates.
(Array, List, SortedSet, SortedArray, SortedArraySet)
Returns the position in the collection of a value, or -1 if it is
not found. Returns the position of the last of equivalent values.
(Array, List, SortedArray, SortedArraySet)
Finds a value. For List and SortedSet, returns the node at which
the value was found. For SortedSet, the optional equals argument
is ignored.
(Array+, List, SortedSet)
Finds the last equivalent value, returning the node at which the value was found.
(Array+, List, SortedArray, SortedArraySet)
Finds the smallest value, returning the node at which it was found, or undefined. This is fast (logarithmic) and performs no rotations.
(SortedSet)
Finds the smallest value greater than the given value. This is fast (logarithic) but does cause rotations.
(SortedSet)
Finds the smallest value greater than or equal to the given value. This is fast (logarithmic) but does cause rotations.
(SortedSet)
(SortedSet)
(SortedSet)
(SortedSet)
Adds values to the end of a collection.
(Array, List)
Adds values to their proper places in a collection. This method exists only to have the same interface as other collections.
(Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet, Heap)
Adds values to the beginning of a collection.
(Array, List)
Adds values to their proper places in a collection. This method exists only to have the same interface as other collections.
(Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet)
Removes and returns the value at the end of a collection. For a Heap, this means the greatest contained value, as defined by the comparator.
(Array, List, Set, SortedSet, LruSet, SortedArray, SortedArraySet, Heap)
Removes and returns the value at the beginning of a collection.
(Array, List, Set, SortedSet, LruSet, SortedArray, SortedArraySet)
Returns the last value in an ordered collection.
(List)
Replaces the last value in an ordered collection.
(List)
Returns an array of the values contained in the half-open interval [start, end), that is, including the start and excluding the end. For lists and arrays, both terms may be numeric positive or negative indicies. For a list, either term may be a node.
(Array, List, SortedSet, SortedArray, SortedArraySet)
Works as with an array, but for a list, the start may be an index or a node.
(Array, List, SortedArray, SortedSet, SortedArraySet)
Performs a splice without variadic arguments.
(Array+, List, SortedArray, SortedSet, SortedArraySet)
Deletes the all values.
(Array+, Object+, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
Sorts a collection in place. The comparator by only be a function. The default comparator coerces unlike types rather than fail to compare.
(Array)
Returns a collection as an array in sorted order. Accepts an
optional compare(x, y) function, by(property(x)) function, and
order indicator, -1 for descending, 1 for ascending, 0 for
stable.
Instead of a compare function, the comparator can be an object
with compare and by functions. The default compare value is
Object.compare.
The by function must be a function that accepts a value from the
collection and returns a representative value on which to sort.
(Array+, List, Set, Map, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet, Heap)
Returns an array of [key, equivalence class] pairs where every element from the collection is placed into an equivalence class if they have the same corresponding return value from the given callback.
(Array+, Object+, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap, Iterator)
Reverses a collection in place.
(Array, List)
Returns a collection of the same type with this collection's contents in reverse order.
(Array, List)
Returns an array of [index, value] pairs from the source collection, starting with the given index.
Returns a string of all the values in the collection joined.
(Array, List, Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet, Heap, Iterator)
Produces a new collection of the same type containing all the values of itself and the values of any number of other collections. Favors the last of duplicate values. For map-like objects, the given iterables are treated as map-like objects and each successively updates the result. Array is like a map from index to value. List, Set, and SortedSet are like maps from nodes to values.
(Array, Object+, Iterator, List, Set, Map, MultiMap,
SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
Returns an array of the keys.
(Object, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap, Dict)
Returns an array of the values
(Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap, Dict)
Returns an array of [key, value] pairs for each entry.
(Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap, Dict)
(Array, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
(Array, List, SortedSet, SortedMap, SortedArray, SortedArraySet,
SortedArrayMap, Heap)
Calls the callback for each value in the collection. The iteration of lists is resilient to changes to the list. Particularly, nodes added after the current node will be visited and nodes added before the current node will be ignored, and no node will be visited twice.
(Array, Object+, Iterator, List, Set, Map, MultiMap, WeakMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
(Array, Object+, Iterator, List, Set, Map, MultiMap, WeakMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
Converts any collection to an object, treating this collection as a map-like object. Array is like a map from index to value.
(Array+ Iterator, List, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap, Dict, Heap)
(Array, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
Whether every value passes a given guard. Stops evaluating the guard after the first failure. Iterators stop consuming after the the first failure.
(Array, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
Whether there is a value that passes a given guard. Stops evaluating the guard after the first success. Iterators stop consuming after the first success.
(Array, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
Whether any value is truthy.
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
Whether all values are truthy.
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
The smallest value. This is fast for sorted collections (logarithic for SortedSet, constant for SortedArray, SortedArraySet, and SortedArrayMap), but slow for everything else (linear).
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict)
The largest value. This is fast for sorted collections (logarithic for SortedSet, constant for SortedArray, SortedArraySet, and SortedArrayMap), but slow for everything else (linear).
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
Any single value, or throws an exception if there are no values. This
is very fast (constant time) for most collections. For a sorted set,
set.root.value is always very fast to access, but changes whenever you
access a value, including using has or find. In the interest of
being consistent across accesses, and only changing in response to
mutation, one returns the min of the set in logarithmic time.
(Array+, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
The one and only value, or throws an exception if there are no values or more than one value.
(Array+, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict)
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict)
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
Replicates the collection. Clones the values deeply, to the
specified depth, using the memo to resolve reference cycles. (which
must the has and set parts of the Map interface, allowing
objects for keys) The default depth is infinite and the default
memo is a WeakMap.
Object.clone can replicate object literals inheriting directly
from Object.prototype or null, or any object that implements
clone on its prototype. Any other object causes clone to throw
an exception.
The clone method on any other objects is not intended to be used
directly since they do not necessarily supply a default depth and
memo.
(Array+, Object+, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
Replicates a collection shallowly. This is used by each clone
implementation to create a new collection of the same type, with the
same options (equals, compare, hash options), but it leaves
the job of deeply cloning the values to the more general clone
method.
(Array+, Object+, List, Set, Map, MultiMap, SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict, Heap)
(Array+, Object+, List, Set, Map, MultiMap, SortedSet, SortedMap,
LruSet, LruMap, SortedArray, SortedArraySet, SortedArrayMap,
FastSet, FastMap, Dict)
(Array+, Object+, List, SortedArray, SortedArraySet)
Produces an iterator with a next method. You may elect to get
richer iterators by wrapping this iterator with an Iterator from
the iterator module. Iteration order of lists is resilient to
changes to the list.
(Array+, Iterator, List, Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet)
Returns an iterator for all values at indicies in the half-open interval [start, end), that is, greater than start, and less than end.
(Array+)
Returns an iterator for all values in the half-open interval [start, end), that is, greater than start, and less than end. The iterator is resilient against changes to the data.
(SortedSet)
Writes a tree describing the internal state of the data structure to the console.
charmap is an object that notes which characters to use to draw
lines. By default, this is the TreeLog.unicodeRound property from the
tree-log module. TreeLog.unicodeSharp and TreeLog.ascii are
alternatives. The properties are:
callback is a customizable function for rendering each node of the tree.
By default, it just writes the value of the node. It accepts the node and
a writer functions. The write function produces the line on which the
node joins the tree, and each subsequent line. The writeAbove function
can write lines before the branch.
log and logger default to console.log and console. To write
the representation to an array instead, they can be array.push and
array.
(SortedSet)
Returns an iterator for a mapping on the source values. Values are consumed on demand.
Returns an iterator for those values from the source that pass the given guard. Values are consumed on demand.
Returns an iterator that incrementally combines the respective values of the given iterations.
Returns an iterator that provides [index, value] pairs from the source iteration.
Variadic transpose.
Variadic concat.
Iterates from start to stop by step.
Iterates from start by step, indefinitely.
Repeats the given value either finite times or indefinitely.
All collections support change listeners. There are three types of changes. Property changes, map changes, and range changes.
PropertyChanges from the listen/property-changes module can
configure listeners for property changes to specific keys of any object.
With the listen/array-changes module required, PropertyChanges can
also listen to changes to the length and indexed properties of an array.
The only caveat is that watched arrays can only modify their contents
with method calls like array.push. All methods of a watched array
support change dispatch. In addition, arrays have a set method to
make setting the value at a particular index observable.
All of these functions delegate to methods of the same name if one exists on the object.
Additionally, PropertyChanges.prototype can be mixed into other
types of objects to support the property change dispatch interface. All
collections support this interface.
The listener for a property change receives the arguments value,
key, and object, just as a forEach or map callback. The
listener may alternately be a delegate object that implements one of
these methods:
A map change listener receives notifications for the creation, removal, or updates for any entry in a map data structure.
With the listen/array-changes module required, Array can also
dispatch map changes for the values at each index.
The listener for a map change receives the value, key, and
collection object as arguments, the same pattern as a forEach or
map callback. In the after change phase, a value of undefined may
indicate that the value was deleted or set to undefined. In the
before change phase, a value of undefined may indicate the the value
was added or was previously undefined.
The listener may be a delegate object with one of the following methods, in order of precedence:
The listen/map-changes module exports a map changes mixin. The
methods of MaxChanges.prototype can be copied to any collection that
needs this interface. Its mutation methods will then need to dispatch
map changes.
A range change listener receives notifications when a range of values at a particular position is added, removed, or replaced within an ordered collection.
The listener for a range change is a function that accepts plus,
minus, and index arguments. plus and minus are the values that
were added or removed at the index. Whatever operation caused these
changes is equivalent to:
var minus = collection.splice(index, minus.length, ...plus)
The listener can alternately be a delegate object with one of the following methods in order of precedence:
The following support range change dispatch:
Array with require("collections/listen/array-changes")SortedSetSortedArraySortedArraySetThe listen/range-changes module exports a range changes mixin.
The methods of RangeChanges.prototype can be copied to any collection
that needs this interface. Its mutation methods will need to dispatch
the range changes.
All descriptors are objects with the properties changeListeners
and willChangeListeners. Both are arrays of listener functions or
objects, in the order in which they were added.
Set and map are like hash tables, but not implemented with a block of
memory as they would be in a lower-level language. Most of the work of
providing fast insertion and lookup based on a hash is performed by the
underlying plain JavaScript object. Each key of the object is a hash
string and each value is a List of values with that hash. The inner
list resolves collisions. With a good hash method, the use of the
list can be avoided.
Sets and maps both have a log function that displays the internal
structure of the bucket list in an NPM-style.
┣━┳ 1
┃ ┗━━ {"key":1,"value":"a"}
┣━┳ 2
┃ ┣━━ {"key":2,"value":"c"}
┃ ┗━━ {"key":2,"value":"d"}
┗━┳ 3
┗━━ {"key":3,"value":"b"}
A binary splay tree is a balanced binary tree that rotates the most
frequently used entries toward the root such that they can be accessed the
most quickly. sorted-set and sorted-map are backed by a splay tree.
All map implementations use an underlying set implementation. Any map
can be implemented trivially atop a set by wrapping compare, equals,
or hash to operate on the key of an entry.
The sorted set has a root node. Each node has a left and right
property, which may be null. Nodes are returned by all of the "find"
functions, and provided as the key argument to callbacks.
Both sorted-set and sorted-map implement a log function which can
produce NPM-style visualizations of the internal state of the sorted
tree.
> set.log(SortedSet.ascii)
.-+ -3
| '-- -2
.-+ -1
+ 0
| .-- 1
'-+ 2
'-- 3
> set.log(SortedSet.unicodeRound)
╭━┳ -3
┃ ╰━━ -2
╭━┻ -1
╋ 0
┃ ╭━┳ 1
┃ ┃ ╰━━ 2
╰━┻ 3
The collection methods on the Object constructor all polymorphically
delegate to the corresponding method of any object that implements the
method of the same name. So, Object.has can be used to check whether
a key exists on an object, or in any collection that implements has.
This permits the Object interface to be agnostic of the input type.
Array.from creates an array from any iterable.
Array.unzip transposes a collection of arrays, so rows become columns.
Array.empty is an empty array, frozen if possible. Do not modify it.
Object.from creates an object from any map or collection. For arrays
and array-like collections, uses the index for the key.
Object.empty is an empty object literal.
Object.isObject(value) tests whether it is safe to attempt to access
properties of a given value.
Object.is(x, y) compares objects for exact identity and is a good
alternative to Object.equals in many collections.
Object.getValueOf(value) safely and idempotently returns the value of
an object or value by only calling the valueOf() if the value
implements that method.
Object.owns is a shorthand for Object.prototype.hasOwnProperty.call.
Object.can(value, name) checks whether an object implements a method
on its prototype chain. An owned function property does not qualify as
a method, to aid in distinguishing "static" functions.
Object.concat(...maps) and Object.from(entries) construct an object
by adding the entries of other objects in order. The maps can be other
objects, arrays of entries, or map alike collections.
Function.noop is returns undefined.
Function.identity returns its first argument.
Function.by(relation) creates a comparator from a relation function.
Function.get(key) creates a relation that returns the value for the
property of a given object.
Goals
More possible collections
v0.2.2
one now returns a consistent value between changes of a sorted
set.FAQs
data structures with idiomatic JavaScript collection interfaces
We found that collections demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 7 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
vlt introduced its new package manager and a serverless registry this week, innovating in a space where npm has stagnated.
Security News
Research
The Socket Research Team uncovered a malicious Python package typosquatting the popular 'fabric' SSH library, silently exfiltrating AWS credentials from unsuspecting developers.
Security News
At its inaugural meeting, the JSR Working Group outlined plans for an open governance model and a roadmap to enhance JavaScript package management.