Fork me on GitHub

build status

Collections

This package contains JavaScript implementations of common data structures with idiomatic iterfaces, including extensions for Array and Object.

Constructor Arguments

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.

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.

Collection Methods

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)

Iterator

Iterator utilities

Change Listeners

All collections support change listeners. There are three types of changes. Property changes, map changes, and range changes.

Property 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:

Map Changes

A map change listener receives notifications for the creation, removal, or updates for any item 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 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.

Range 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 an object that has either a handleRangeChange or handleRangeWillChange method, depending on whether the notification is dispatched after or before the change takes effect. The arguments are the same either way, but this will be the handler object.

If the listener is neither of the above, it can be a delegate that implements a W3C-alike handleEvent(event) method. The event has these properties:

The following support range change dispatch:

The 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.

Miscellanea

Set and Map

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"}

Sorted Set and Sorted Map

A binary splay tree is a balanced binary tree that rotates the most frequently used items 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 item.

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

Object and Function Shims

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.

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.

Function.noop is returns undefined.

Function.identity returns its first argument.

References

Future work

Goals

More possible collections