Socket
Socket
Sign inDemoInstall

collections

Package Overview
Dependencies
Maintainers
3
Versions
76
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

collections - npm Package Compare versions

Comparing version 1.1.0 to 1.2.0

FUTURE.md

19

CHANGES.md
## v1.2.0
- Trevor Dixon fixed bugs in SortedSet find methods.
- Adds toJSON method to all collections.
- Adds deleteAll to some collections.
- Eliminate some extra work in change listener registration and dispatch by
using namespaced properties instead of a weak map, precomputing event
handler method names, and reusing an array to capture a snapshot of active
change listeners during dispatch.
- Fix SortedArrayMap isSorted flag.
- Fix Array find such that the sought value may be a wild card.
- MultiMap provides the key to the bucket maker
- Improve support for strings, maps, and arguments across implementations of
addEach
- Fix a bug in the generic join method
- Dict uses $ in mangled names instead of ~, so names are more frequently
valid identifiers. May have a performance win.
- Ignore property changes in non-configurable objects.
## v1.1.0

@@ -3,0 +22,0 @@

1

deque.js

@@ -6,3 +6,2 @@ "use strict";

var GenericOrder = require("./generic-order");
var GenericOrder = require("./generic-order");
var RangeChanges = require("./listen/range-changes");

@@ -9,0 +8,0 @@

10

dict.js

@@ -25,3 +25,6 @@ "use strict";

function mangle(key) {
return "~" + key;
// Use "$" as the mangle prefix so dictionaries of valid identifiers can
// take advantage of optimizations for objects containing only valid
// identifiers. I have not verified that this makes a difference.
return "$" + key;
}

@@ -38,3 +41,3 @@

Dict.prototype.constructClone = function (values) {
return new this.constructor(values, this.mangle, this.getDefault);
return new this.constructor(values, this.getDefault);
};

@@ -145,1 +148,4 @@

Dict.prototype.toJSON = function () {
return this.toObject();
};

14

generic-collection.js

@@ -23,2 +23,7 @@ "use strict";

}
} else if (values && typeof values.length === "number") {
// Strings
for (var i = 0; i < values.length; i++) {
this.add(values[i], i);
}
}

@@ -205,4 +210,9 @@ return this;

return this.reduce(function (result, string) {
return result + delimiter + string;
});
// work-around for reduce that does not support no-basis form
if (result === void 0) {
return string;
} else {
return result + delimiter + string;
}
}, void 0);
};

@@ -209,0 +219,0 @@

15

generic-map.js

@@ -33,2 +33,8 @@ "use strict";

}
} else if (typeof values.length === "number") {
// Array-like objects that do not implement forEach, ergo,
// Arguments
for (var i = 0; i < values.length; i++) {
this.add(values[i], i);
}
} else {

@@ -40,2 +46,7 @@ // copy other objects as map-alikes

}
} else if (values && typeof values.length === "number") {
// String
for (var i = 0; i < values.length; i++) {
this.add(values[i], i);
}
}

@@ -174,2 +185,6 @@ return this;

GenericMap.prototype.toJSON = function () {
return this.entries();
};
GenericMap.prototype.Item = Item;

@@ -176,0 +191,0 @@

3

generic-order.js

@@ -56,1 +56,4 @@

GenericOrder.prototype.toJSON = function () {
return this.toArray();
};

11

generic-set.js

@@ -33,2 +33,9 @@

GenericSet.prototype.deleteAll = function (value) {
// deleteAll is equivalent to delete for sets since they guarantee that
// only one value exists for an equivalence class, but deleteAll returns
// the count of deleted values instead of whether a value was deleted.
return +this["delete"](value);
};
GenericSet.prototype.equals = function (that, equals) {

@@ -45,2 +52,6 @@ var self = this;

GenericSet.prototype.toJSON = function () {
return this.toArray();
};
// W3C DOMTokenList API overlap (does not handle variadic arguments)

@@ -47,0 +58,0 @@

6

heap.js

@@ -42,2 +42,3 @@

// TODO variadic
Heap.prototype.push = function (value) {

@@ -217,2 +218,6 @@ this.content.push(value);

Heap.prototype.toJSON = function () {
return this.toArray();
};
Heap.prototype.makeObservable = function () {

@@ -241,1 +246,2 @@ // TODO refactor dispatchers to allow direct forwarding

};

26

list.js

@@ -40,3 +40,3 @@ "use strict";

while (at !== head) {
if (equals(at.value, value)) {
if (equals(value, at.value)) {
return at;

@@ -53,3 +53,3 @@ }

while (at !== head) {
if (equals(at.value, value)) {
if (equals(value, at.value)) {
return at;

@@ -74,3 +74,3 @@ }

// LIFO (delete removes the most recently added equivalent value)
List.prototype['delete'] = function (value, equals) {
List.prototype["delete"] = function (value, equals) {
var found = this.findLast(value, equals);

@@ -83,3 +83,3 @@ if (found) {

}
found['delete']();
found["delete"]();
this.length--;

@@ -95,2 +95,18 @@ if (this.dispatchesRangeChanges) {

List.prototype.deleteAll = function (value, equals) {
equals = equals || this.contentEquals;
var head = this.head;
var at = head.next;
var count = 0;
while (at !== head) {
if (equals(value, at.value)) {
at["delete"]();
count++;
}
at = at.next;
}
this.length -= count;
return count;
};
List.prototype.clear = function () {

@@ -428,3 +444,3 @@ var plus, minus;

Node.prototype['delete'] = function () {
Node.prototype["delete"] = function () {
this.prev.next = this.next;

@@ -431,0 +447,0 @@ this.next.prev = this.prev;

205

listen/property-changes.js

@@ -16,19 +16,19 @@ /*

require("../shim");
var WeakMap = require("weak-map");
var object_owns = Object.prototype.hasOwnProperty;
/*
Object property descriptors carry information necessary for adding,
removing, dispatching, and shorting events to listeners for property changes
for a particular key on a particular object. These descriptors are used
here for shallow property changes.
// Object property descriptors carry information necessary for adding,
// removing, dispatching, and shorting events to listeners for property changes
// for a particular key on a particular object. These descriptors are used
// here for shallow property changes. The current listeners are the ones
// modified by add and remove own property change listener methods. During
// property change dispatch, we capture a snapshot of the current listeners in
// the active change listeners array. The descriptor also keeps a memo of the
// corresponding handler method names.
//
// {
// willChangeListeners:{current, active:Array<Function>, ...method names}
// changeListeners:{current, active:Array<Function>, ...method names}
// }
{
willChangeListeners:Array(Function)
changeListeners:Array(Function)
}
*/
var propertyChangeDescriptors = new WeakMap();
// Maybe remove entries from this table if the corresponding object no longer

@@ -41,20 +41,17 @@ // has any property change listeners for any key. However, the cost of

/*
To observe shallow property changes for a particular key of a particular
object, we install a property descriptor on the object that overrides the previous
descriptor. The overridden descriptors are stored in this weak map. The
weak map associates an object with another object that maps property names
to property descriptors.
// To observe shallow property changes for a particular key of a particular
// object, we install a property descriptor on the object that overrides the previous
// descriptor. The overridden descriptors are stored in this weak map. The
// weak map associates an object with another object that maps property names
// to property descriptors.
//
// object.__overriddenPropertyDescriptors__[key]
//
// We retain the old descriptor for various purposes. For one, if the property
// is no longer being observed by anyone, we revert the property descriptor to
// the original. For "value" descriptors, we store the actual value of the
// descriptor on the overridden descriptor, so when the property is reverted, it
// retains the most recently set value. For "get" and "set" descriptors,
// we observe then forward "get" and "set" operations to the original descriptor.
overriddenObjectDescriptors.get(object)[key]
We retain the old descriptor for various purposes. For one, if the property
is no longer being observed by anyone, we revert the property descriptor to
the original. For "value" descriptors, we store the actual value of the
descriptor on the overridden descriptor, so when the property is reverted, it
retains the most recently set value. For "get" and "set" descriptors,
we observe then forward "get" and "set" operations to the original descriptor.
*/
var overriddenObjectDescriptors = new WeakMap();
module.exports = PropertyChanges;

@@ -69,10 +66,27 @@

PropertyChanges.prototype.getOwnPropertyChangeDescriptor = function (key) {
if (!propertyChangeDescriptors.has(this)) {
propertyChangeDescriptors.set(this, {});
if (!this.__propertyChangeListeners__) {
Object.defineProperty(this, "__propertyChangeListeners__", {
value: {},
enumerable: false,
configurable: true,
writable: true
});
}
var objectPropertyChangeDescriptors = propertyChangeDescriptors.get(this);
var objectPropertyChangeDescriptors = this.__propertyChangeListeners__;
if (!object_owns.call(objectPropertyChangeDescriptors, key)) {
var propertyName = String(key);
propertyName = propertyName && propertyName[0].toUpperCase() + propertyName.slice(1);
objectPropertyChangeDescriptors[key] = {
willChangeListeners: [],
changeListeners: []
willChangeListeners: {
current: [],
active: [],
specificHandlerMethodName: "handle" + propertyName + "WillChange",
genericHandlerMethodName: "handlePropertyWillChange"
},
changeListeners: {
current: [],
active: [],
specificHandlerMethodName: "handle" + propertyName + "Change",
genericHandlerMethodName: "handlePropertyChange"
}
};

@@ -84,3 +98,3 @@ }

PropertyChanges.prototype.hasOwnPropertyChangeDescriptor = function (key) {
if (!propertyChangeDescriptors.has(this)) {
if (!this.__propertyChangeListeners__) {
return false;

@@ -91,3 +105,3 @@ }

}
var objectPropertyChangeDescriptors = propertyChangeDescriptors.get(this);
var objectPropertyChangeDescriptors = this.__propertyChangeListeners__;
if (!object_owns.call(objectPropertyChangeDescriptors, key)) {

@@ -112,7 +126,7 @@ return false;

PropertyChanges.makePropertyObservable(this, key);
listeners.push(listener);
listeners.current.push(listener);
var self = this;
return function cancelOwnPropertyChangeListener() {
PropertyChanges.removeOwnPropertyChangeListener(self, key, listeners, beforeChange);
PropertyChanges.removeOwnPropertyChangeListener(self, key, listener, beforeChange);
self = null;

@@ -136,7 +150,7 @@ };

var index = listeners.lastIndexOf(listener);
var index = listeners.current.lastIndexOf(listener);
if (index === -1) {
throw new Error("Can't remove property change listener: does not exist: property name" + JSON.stringify(key));
}
listeners.splice(index, 1);
listeners.current.splice(index, 1);
};

@@ -163,25 +177,5 @@

var changeName = (beforeChange ? "Will" : "") + "Change";
var genericHandlerName = "handleProperty" + changeName;
var propertyName = String(key);
propertyName = propertyName && propertyName[0].toUpperCase() + propertyName.slice(1);
var specificHandlerName = "handle" + propertyName + changeName;
try {
// dispatch to each listener
listeners.slice().forEach(function (listener) {
if (listeners.indexOf(listener) < 0) {
return;
}
var thisp = listener;
listener = (
listener[specificHandlerName] ||
listener[genericHandlerName] ||
listener
);
if (!listener.call) {
throw new Error("No event listener for " + specificHandlerName + " or " + genericHandlerName + " or call on " + listener);
}
listener.call(thisp, value, key, this);
}, this);
dispatchEach.call(this, listeners, key, value);
} finally {

@@ -192,2 +186,29 @@ descriptor.isActive = false;

// Factored out of parent to avoid try/catch deoptimization
function dispatchEach(listeners, key, value) {
// copy snapshot of current listeners to active listeners
var active = listeners.active;
var current = listeners.current;
var index = active.length = current.length;
while (index--) {
active[index] = current[index];
}
for (var index = 0, length = active.length; index < length; index++) {
var listener = active[index];
if (current.indexOf(listener) < 0) {
return;
}
var thisp = listener;
listener = (
listener[listeners.specificHandlerMethodName] ||
listener[listeners.genericHandlerMethodName] ||
listener
);
if (!listener.call) {
throw new Error("No event listener for " + listeners.specificHandlerName + " or " + listeners.genericHandlerName + " or call on " + listener);
}
listener.call(thisp, value, key, this);
}
}
PropertyChanges.prototype.dispatchBeforeOwnPropertyChange = function (key, listener) {

@@ -226,7 +247,12 @@ return PropertyChanges.dispatchOwnPropertyChange(this, key, listener, true);

// memoize overridden property descriptor table
if (!overriddenObjectDescriptors.has(this)) {
if (!this.__overriddenPropertyDescriptors__) {
overriddenPropertyDescriptors = {};
overriddenObjectDescriptors.set(this, overriddenPropertyDescriptors);
Object.defineProperty(this, "__overriddenPropertyDescriptors__", {
value: {},
enumerable: false,
writable: true,
configurable: true
});
}
var overriddenPropertyDescriptors = overriddenObjectDescriptors.get(this);
var overriddenPropertyDescriptors = this.__overriddenPropertyDescriptors__;

@@ -260,3 +286,3 @@ if (object_owns.call(overriddenPropertyDescriptors, key)) {

if (!overriddenDescriptor.configurable) {
throw new Error("Can't observe non-configurable properties");
return;
}

@@ -347,41 +373,2 @@

PropertyChanges.prototype.makePropertyUnobservable = function (key) {
// arrays are special. we do not support direct setting of properties
// on an array. instead, call .set(index, value). this is observable.
// 'length' property is observable for all mutating methods because
// our overrides explicitly dispatch that change.
if (Array.isArray(this)) {
return;
}
if (!overriddenObjectDescriptors.has(this)) {
throw new Error("Can't uninstall observer on property");
}
var overriddenPropertyDescriptors = overriddenObjectDescriptors.get(this);
if (!overriddenPropertyDescriptors[key]) {
throw new Error("Can't uninstall observer on property");
}
var overriddenDescriptor = overriddenPropertyDescriptors[key];
delete overriddenPropertyDescriptors[key];
var state;
if (typeof this.__state__ === "object") {
state = this.__state__;
} else {
state = {};
if (Object.isExtensible(this, "__state__")) {
Object.defineProperty(this, "__state__", {
value: state,
writable: true,
enumerable: false
});
}
}
delete state[key];
Object.defineProperty(this, key, overriddenDescriptor);
};
// constructor functions

@@ -452,9 +439,1 @@

PropertyChanges.makePropertyUnobservable = function (object, key) {
if (object.makePropertyUnobservable) {
return object.makePropertyUnobservable(key);
} else {
return PropertyChanges.prototype.makePropertyUnobservable.call(object, key);
}
};

2

multi-map.js

@@ -12,3 +12,3 @@ "use strict";

Map.call(this, values, equals, hash, function getDefault(key) {
var bucket = this.bucket();
var bucket = this.bucket(key);
Map.prototype.set.call(this, key, bucket);

@@ -15,0 +15,0 @@ return bucket;

6

package.json
{
"name": "collections",
"version": "1.1.0",
"version": "1.2.0",
"description": "data structures with idiomatic JavaScript collection interfaces",
"homepage": "http://github.com/montagejs/collections",
"homepage": "http://www.collectionsjs.com",
"author": "Kris Kowal <kris@cixar.com> (http://github.com/kriskowal)",

@@ -34,3 +34,3 @@ "keywords": [

"devDependencies": {
"jasmine-node": "*",
"jasmine-node": ">=1.13.1 <1.14.0",
"istanbul": "*",

@@ -37,0 +37,0 @@ "opener": "*"

1312

README.md

@@ -24,1312 +24,6 @@ [![Build Status](https://travis-ci.org/montagejs/collections.png?branch=master)](http://travis-ci.org/montagejs/collections)

Documentation can be found at http://collectionsjs.com which in turn can be
updated at https://github.com/montagejs/collectionsjs.com.
## Collections
[![Analytics](https://ga-beacon.appspot.com/UA-51771141-2/collections/readme)](https://github.com/igrigorik/ga-beacon)
### List(values, equals, getDefault)
```javascript
var List = require("collections/list");
```
An ordered collection of values with fast insertion and deletion and
forward and backward traversal and splicing, 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.
### Deque(values, capacity)
```javascript
var Deque = require("collections/deque");
```
An ordered collection of values with fast insertion and deletion and
forward and backward traversal, backed by a circular buffer that
doubles its capacity at need. Deques support most of the Array
interface. A Deque is generally faster and produces less garbage
collector churn than a List, but does not support fast splicing.
### Set(values, equals, hash, getDefault)
```javascript
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`.
### Map(map, equals, hash, getDefault)
```javascript
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`.
### MultiMap(map, getDefault, equals, hash)
```javascript
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.
### WeakMap()
```javascript
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.
### SortedSet(values, equals, compare, getDefault)
```javascript
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)`.
### SortedMap(map, equals, compare, getDefault)
```javascript
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.
### LruSet(values, maxLength, equals, hash, getDefault)
```javascript
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.
### LruMap(map, maxLength, equals, hash, getDefault)
```javascript
var LruMap = require("collections/lru-map");
```
A cache of entries backed by an `LruSet`.
### LfuSet(values, capacity, equals, hash, getDefault)
```javascript
var LfuSet = require("collections/lfu-set");
```
A cache with the Least-Frequently-Used strategy for truncating its
content when it’s length exceeds `capacity`. It maintains the
eqivalent of a LRU for each frequency, so that the oldest, least
frequently used value is evicted first. Both getting and setting a
value constitute usage, but checking whether the set has a value and
iterating values do not.
### LfuMap(map, capacity, equals, hash, getDefault)
```javascript
var LfuMap = require("collections/lfu-map");
```
A cache of entries backed by an `LfuSet`.
### SortedArray(values, equals, compare, getDefault)
```javascript
var SortedArray = require("collections/sorted-array");
```
A collection of values stored in a stable sorted order, backed by an
array.
### SortedArraySet(values, equals, compare, getDefault)
```javascript
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.
### SortedArrayMap(values, equals, compare, getDefault)
```javascript
var SortedArrayMap = require("collections/sorted-array-map");
```
A collection of key value pairs stored in sorted order, backed by a
sorted array set.
### FastSet(values, equals, hash, getDefault)
```javascript
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".
### FastMap(map, equals, hash, getDefault)
```javascript
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.
### Dict(values, getDefault)
```javascript
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.
### Heap(values, equals, compare)
```javascript
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.
### Iterator(iterable)
```javascript
var Iterator = require("collections/iterator");
```
A wrapper for any iterable that implements `iterate` or iterator the
implements `next`, providing a rich lazy traversal interface.
### Array
```javascript
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.
### Object
```javascript
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.
## 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.
### map
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.
### equals(x, y)
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`.
### compare(x, y)
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`.
### hash(value)
The default `hash` operator uses `toString` for values and provides
a [Unique Label][] for arbitrary objects. The default hash is
shimmed as `Object.hash`.
[Unique Label]: (http://wiki.ecmascript.org/doku.php?id=harmony:weak_maps#unique_labeler)
### getDefault(key or value)
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`.
## 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, LfuSet, LfuMap, SortedArray,
SortedArraySet, SortedArrayMap, FastSet, FastMap, Dict)
### has
#### has(key)
Whether a value for the given key exists.
Collections: (Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
#### has(value, opt_equals)
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. However, SortedSet, SortedArray, and
SortedArraySet have an inherent `contentEquals` function and do not
support override, and as such will throw an exception if provided the
`equals` argument.
Collections: (Array+, List, Set, SortedSet, LruSet, SortedArray, SortedArraySet,
FastSet)
### get
#### get(key or index)
The value for a key. If a Map or SortedMap lacks a key, returns
`getDefault(key)`.
Collections: (Array+, Map, SortedMap, SortedArrayMap, WeakMap, Object+)
#### get(value, opt_equals)
Gets the equivalent value, or falls back to `getDefault(value)`.
Sorted collections and sets have an interinsic `contentEquals`, so
they do not accept an `equals` override and will throw an error if
provided one.
Collections: (List, Deque, Set, SortedSet, LruSet, SortedArray, SortedArraySet,
FastSet)
### set(key or index, value)
Sets the value for a key.
Collections: (Map, MultiMap, WeakMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
### add
#### add(value)
Adds a value. Ignores the operation and returns false if an
equivalent value already exists.
Collections: (Array+, List, Deque, Set, SortedSet, LruSet, SortedArray,
SortedArraySet, FastSet, Heap)
#### add(value, key)
Aliases `set(key, value)`, to assist generic methods used for maps,
sets, and other collections.
### addEach
#### addEach(values)
Copies values from another collection to this one.
Collections: (Array+, List, Set, SortedSet, LruSet, SortedArray, SortedArraySet,
FastSet, Heap)
#### addEach(mapping)
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.
Collections: (Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
### delete
#### delete(key)
Deletes the value for a given key. Returns whether the key was
found.
Collections: (Map, MultiMap, WeakMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
#### delete(value)
Deletes a value. Returns whether the value was found. Throws an error
if a second argument, `equals`, is provided because these collections
have an intrinsic order and `contentEquals` function.
Collections: (Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet, Heap)
#### delete(value, opt_equals)
Deletes the equivalent value. Returns whether the value was found.
Collections: (Array+, List, Deque)
### deleteEach(values or keys, opt_equals)
Deletes every value or every value for each key. If provided an
`equals` argument, it will be forwarded to the underlying `delete`
implementation, which may or may not be appropriate depending on the
collection.
Collections: (Array+, List, Deque, Set, Map, MultiMap, SortedSet, SortedMap,
LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet, SortedArrayMap,
FastSet, FastMap, Dict, Heap)
### indexOf(value)
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.
Collections: (Array, ~~List~~, Deque, SortedSet, SortedArray, SortedArraySet)
### lastIndexOf(value)
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.
Collections: (Array, ~~List~~, Deque, SortedArray, SortedArraySet)
### find(value, opt_equals, opt_startIndex)
Finds a value. For List and SortedSet, returns the node at which the
value was found. SortedSet, SortedArray, and SortedArraySet do not
support overriding their inherent `equals` or `startIndex` and will
throw an exception if provided either. A meaningful implementation
using `startIndex` or `startNode` could possibly be implemented in a
future release.
Collections: (Array+, List, Deque, SortedSet, SortedArray, SortedArraySet)
### findLast(value, opt_equals, opt_endIndex)
Finds the last equivalent value, returning the node at which the value
was found. SortedArrayn and SortedArraySet do not support overriding
its inherent `equals` or `startIndex` and will throw an exception if
provided either. A meaningful implementation using `startIndex` or
`startNode` could possibly be implemented in a future release.
Collections: (Array+, List, Deque, SortedArray, SortedArraySet)
### findLeast()
Finds the smallest value, returning the node at which it was found,
or undefined. This is fast (logarithmic) and performs no rotations.
Collections: (SortedSet)
### findLeastGreaterThan(value)
Finds the smallest value greater than the given value. This is fast
(logarithic) but does cause rotations.
Collections: (SortedSet)
### findLeastGreaterThanOrEqual(value)
Finds the smallest value greater than or equal to the given value.
This is fast (logarithmic) but does cause rotations.
Collections: (SortedSet)
### findGreatest()
Collections: (SortedSet)
### findGreatestLessThan(value)
Collections: (SortedSet)
### findGreatestLessThanOrEqual(value)
Collections: (SortedSet)
### push
#### push(...values)
Adds values to the end of a collection.
Collections: (Array, List, Deque)
#### push(...values) for non-deques
Adds values to their proper places in a collection.
This method exists only to have the same interface as other
collections.
Collections: (Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet, Heap)
### unshift
#### unshift(...values)
Adds values to the beginning of a collection.
Collections: (Array, List, Deque)
#### unshift(...values) for non-deques
Adds values to their proper places in a collection.
This method exists only to have the same interface as other
collections.
Collections: (Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet)
### pop()
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.
Collections: (Array, List, Deque, Set, SortedSet, LruSet, SortedArray,
SortedArraySet, Heap)
### shift()
Removes and returns the value at the beginning of a collection.
Collections: (Array, List, Deque, Set, SortedSet, LruSet, SortedArray,
SortedArraySet)
### peek()
Returns the next value in an deque, as would be returned by the next
`shift`.
Collections: (Array, List, Deque)
### poke(value)
Replaces the next value in an ordered collection, such that it will be
returned by `shift` instead of what was there.
Collections: (Array, List, Deque)
### peekBack()
Returns the last value in an deque, as would be returned by the next
`pop`.
Collections: (Array, List, Deque)
### pokeBack(value)
Replaces the last value in an ordered collection, such that it will be
returned by `pop` instead of what was there.
Collections: (Array, List, Deque)
### slice(start, end)
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.
Collections: (Array, List, SortedSet, SortedArray, SortedArraySet)
### splice(start, length, ...values)
Works as with an array, but for a list, the start may be an index or
a node.
Collections: (Array, List, SortedArray, SortedSet, SortedArraySet)
### swap(start, length, values)
Performs a splice without variadic arguments.
Collections: (Array+, List, SortedArray, SortedSet, SortedArraySet)
### clear()
Deletes the all values.
Collections: (Array+, Object+, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### sort(compare)
Sorts a collection in place. The comparator by only be a function.
The default comparator coerces unlike types rather than fail to
compare.
Collections: (Array)
### sorted(compare, by, order)
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.
Collections: (Array+, List, Deque, Set, Map, SortedSet, LruSet, SortedArray,
SortedArraySet, FastSet, Heap)
### group(callback, thisp, equals)
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.
Collections: (Array+, Object+, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap, Iterator)
### reverse()
Reverses a collection in place.
Collections: (Array, List)
### reversed()
Returns a collection of the same type with this collection's
contents in reverse order.
Collections: (Array, List)
### enumerate(start=0)
Returns an array of [index, value] pairs from the source collection,
starting with the given index.
### join(delimiter="")
Returns a string of all the values in the collection joined.
Collections: (Array, List, Set, SortedSet, LruSet, SortedArray, SortedArraySet,
FastSet, Heap, Iterator)
### concat(...iterables)
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.
Collections: (Array, ~~Object+~~, Iterator, List, Set, Map, MultiMap,
SortedSet, SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### keys()
Returns an array of the keys.
Collections: (Object, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
### values()
Returns an array of the values
Collections: (Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
### entries()
Returns an array of `[key, value]` pairs for each entry.
Collections: (Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
### reduce(callback(result, value, key, object, depth), basis, thisp)
Collections: (Array, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### reduceRight(callback(result, value, key, object, depth), basis, thisp)
Collections: (Array, List, Deque, SortedSet, ~~SortedMap~~, SortedArray,
SortedArraySet, ~~SortedArrayMap~~, Heap)
### forEach(callback(value, key, object, depth), thisp)
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.
Collections: (Array, Object+, Iterator, List, Deque, Set, Map, MultiMap, WeakMap,
SortedSet, SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### map(callback(value, key, object, depth), thisp)
Collections: (Array, Object+, Iterator, List, Deque, Set, Map, MultiMap, WeakMap,
SortedSet, SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### toArray()
Collections: (Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### toObject()
Converts any collection to an object, treating this collection as a
map-like object. Array is like a map from index to value.
Collections: (Array+ Iterator, List, Deque, Map, MultiMap, SortedMap, LruMap,
SortedArrayMap, FastMap, Dict, Heap)
### filter(callback(value, key, object, depth), thisp)
Collections: (Array, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### every(callback(value, key, object, depth), thisp)
Whether every value passes a given guard. Stops evaluating the
guard after the first failure. Iterators stop consuming after the
the first failure.
Collections: (Array, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### some(callback(value, key, object, depth), thisp)
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.
Collections: (Array, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### min()
The smallest value. This is fast for sorted collections (logarithic
for SortedSet, constant for SortedArray, SortedArraySet, and
SortedArrayMap), but slow for everything else (linear).
Collections: (Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict)
### max()
The largest value. This is fast for sorted collections (logarithic
for SortedSet, constant for SortedArray, SortedArraySet, and
SortedArrayMap), but slow for everything else (linear).
Collections: (Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### one()
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.
Collections: (Array+, List, Deque, Set, Map, MultiMap, SortedSet, SortedMap,
LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### only()
The one and only value, or throws an exception if there are no
values or more than one value.
Collections: (Array+, List, Deque, Set, Map, MultiMap, SortedSet, SortedMap,
LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### sum()
Collections: (Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict)
### average()
Collections: (Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict)
### flatten()
Collections: (Array+, Iterator, List, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### zip(...collections)
Collections: (Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### enumerate(zero)
Collections: (Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### clone(depth, memo)
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.
Collections: (Array+, Object+, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### constructClone(values)
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.
Collections: (Array+, Object+, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### equals(that, equals)
Collections: (Array+, Object+, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, LfuSet, LfuMap, ~~SortedArray~~, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict)
### compare(that)
Collections: (Array+, Object+, List, Deque, ~~SortedArray~~, ~~SortedArraySet~~)
### iterate
#### iterate()
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.
Collections: (Array+, Iterator, List, ~~Deque~~, Set, SortedSet, LruSet,
SortedArray, SortedArraySet, FastSet)
#### iterate(start, end)
Returns an iterator for all values at indicies in the half-open
interval [start, end), that is, greater than start, and less than
end.
Collections: (Array+)
#### iterate(start, end)
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.
Collections: (SortedSet)
### log(charmap, callback(node, write, writeAbove), log, logger)
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:
- intersection: ╋
- through: ━
- branchUp: ┻
- branchDown: ┳
- fromBelow: ╭
- fromAbove: ╰
- fromBoth: ┣
- strafe: ┃
`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`.
Collections: (SortedSet)
### Iterator
#### dropWhile(callback(value, index, iterator), thisp)
#### takeWhile(callback(value, index, iterator), thisp)
#### mapIterator(callback(value, index, iterator))
Returns an iterator for a mapping on the source values. Values are
consumed on demand.
#### filterIterator(callback(value, index, iterator))
Returns an iterator for those values from the source that pass the
given guard. Values are consumed on demand.
#### zipIterator(...iterables)
Returns an iterator that incrementally combines the respective
values of the given iterations.
#### enumerateIterator(start = 0)
Returns an iterator that provides [index, value] pairs from the
source iteration.
### Iterator utilities
#### cycle(iterable, times)
#### concat(iterables)
#### transpose(iterables)
#### zip(...iterables)
Variadic transpose.
#### chain(...iterables)
Variadic concat.
#### range(start, stop, step)
Iterates from start to stop by step.
#### count(start, step)
Iterates from start by step, indefinitely.
#### repeat(value, times)
Repeats the given value either finite times or indefinitely.
## 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.
- PropertyChanges.addOwnPropertyChangeListener(object, key, listener, before)
- PropertyChanges.removeOwnPropertyChangeListener(object, key, listener, before)
- PropertyChanges.dispatchOwnPropertyChange(object, key, value, before)
- PropertyChanges.addBeforeOwnPropertyChangeListener(object, key, listener)
- PropertyChanges.removeBeforeOwnPropertyChangeListener(object, key, listener)
- PropertyChanges.dispatchBeforeOwnPropertyChange(object, key, value)
- PropertyChanges.getOwnPropertyChangeDescriptor(object, key)
All of these functions delegate to methods of the same name if one
exists on the object.
- object.addOwnPropertyChangeListener(key, listener, before)
- object.removeOwnPropertyChangeListener(key, listener, before)
- object.dispatchOwnPropertyChange(key, value, before)
- object.addBeforeOwnPropertyChangeListener(key, listener)
- object.removeBeforeOwnPropertyChangeListener(key, listener)
- object.dispatchBeforeOwnPropertyChange(key, value)
- object.getOwnPropertyChangeDescriptor(key)
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:
- listener.handle + **key** + Change **or** WillChange
- listener.handleProperty + Change **or** WillChange
- listener.call
### Map Changes
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.
- collection.addMapChangeListener(listener, token, before)
- collection.removeMapChangeListener(listener, token, before)
- collection.dispatchMapChange(key, value, before)
- collection.addBeforeMapChangeListener(listener)
- collection.removeBeforeMapChangeListener(listener)
- collection.dispatchBeforeMapChange(key, value)
- collection.getMapChangeDescriptor()
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:
- listener.handleMap + Change **or** WillChange
- listener.handle + **token** + Map + Change **or** WillChange
- listener.call
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.
- collection.**add**RangeChange**Listener**(listener, token, before)
- collection.**remove**RangeChange**Listener**(listener, token, before)
- collection.**dispatch**RangeChange(plus, minus, index, before)
- collection.add**Before**RangeChange**Listener**(listener)
- collection.remove**Before**RangeChange**Listener**(listener)
- collection.dispatch**Before**RangeChange(plus, minus, index)
- collection.**get**RangeChange**Descriptor**()
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:
```javascript
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:
- handle + **token** + Range + Change **or** WillChange
- handleRange + Change **or** WillChange
- call
The following support range change dispatch:
- `Array` with `require("collections/listen/array-changes")`
- `SortedSet`
- `SortedArray`
- `SortedArraySet`
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 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
```
### 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.
`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.
### References
- a SplayTree impementation buried in Fedor Indutny’s super-secret
[Callgrind](https://github.com/indutny/callgrind.js). This
implementation uses parent references.
- a SplayTree implementation adapted by [Paolo
Fragomeni](https://github.com/hij1nx/forest) from the V8 project and
based on the top-down splaying algorithm from "Self-adjusting Binary
Search Trees" by Sleator and Tarjan. This does not use or require
parent references, so I favored it over Fedor Indutny’s style.
- the interface of ECMAScript harmony [simple maps and
sets](http://wiki.ecmascript.org/doku.php?id=harmony:simple_maps_and_sets)
- a SplayTree implementation from [JavaScript data
structures](derrickburns/Javascript-Data-Structures) mainted by
Derrick Burns that supports change-resilient iterators and a
comprehensive set of introspection functions.
### Future work
Goals
- make array dispatch length property changes between range changes to
be consistent with List.
- automate the generation of the method support tables in readme and
normalize declaration order
- comprehensive specs and spec coverage tests
- array set (a set, for fast lookup, backed by an array for meaningful
range changes)
- fast list splicing
- revise map changes to use separate handlers for add/delete
- revise tokens for range and map changes to specify complete alternate
delegate methods, particularly for forwarding directly to dispatch
- Make it easier to created a SortedSet with a criterion like
Function.by(Function.get('name'))
- evaluate exposing observeProperty, observeRangeChange, and observeMapChange
instead of the aEL/rEL inspired API FRB exposes today, to minimize
book-keeping and garbage collection
More possible collections
- sorted-list (sorted, can contain duplicates, perhaps backed by splay
tree with relaxation on the uniqueness invariant, or a skip list)
- sorted-multi-map (sorted, can contain duplicate entries)
- buffer (backed by a circular array, emits cull events)
- trie-set
- trie-map
- immutable-* (mutation functions return new objects that largely share
the previous version's internal state, some perhaps backed by a hash
trie)

2

set.js

@@ -98,3 +98,3 @@ "use strict";

if (this.store.has(node)) {
var node = this.store.get(node);
node = this.store.get(node);
if (this.dispatchesRangeChanges) {

@@ -101,0 +101,0 @@ this.dispatchBeforeRangeChange([], [value], node.index);

16

shim-array.js

@@ -121,6 +121,20 @@ "use strict";

define("deleteAll", function (value, equals) {
equals = equals || this.contentEquals || Object.equals;
var count = 0;
for (var index = 0; index < this.length;) {
if (equals(value, this[index])) {
this.swap(index, 1);
count++;
} else {
index++;
}
}
return count;
});
define("find", function (value, equals) {
equals = equals || this.contentEquals || Object.equals;
for (var index = 0; index < this.length; index++) {
if (index in this && equals(this[index], value)) {
if (index in this && equals(value, this[index])) {
return index;

@@ -127,0 +141,0 @@ }

7

shim-object.js

@@ -198,3 +198,3 @@ "use strict";

// copy map-alikes
if (typeof source.keys === "function") {
if (source.isMap === true) {
source.forEach(function (value, key) {

@@ -209,2 +209,7 @@ target[key] = value;

}
} else if (typeof source.length === "number") {
// arguments, strings
for (var index = 0; index < source.length; index++) {
target[index] = source[index];
}
} else {

@@ -211,0 +216,0 @@ // copy other objects as map-alikes

2

sorted-array-map.js

@@ -41,2 +41,4 @@ "use strict";

SortedArrayMap.prototype.isSorted = true;
SortedArrayMap.prototype.constructClone = function (values) {

@@ -43,0 +45,0 @@ return new this.constructor(

37

sorted-array.js

@@ -161,3 +161,32 @@ "use strict";

SortedArray.prototype.deleteAll = function (value, equals) {
if (equals) {
var count = this.array.deleteAll(value, equals);
this.length -= count;
return count;
} else {
var start = searchFirst(this.array, value, this.contentCompare, this.contentEquals);
if (start !== -1) {
var end = start;
while (this.contentEquals(value, this.array[end])) {
end++;
}
var minus = this.slice(start, end);
if (this.dispatchesRangeChanges) {
this.dispatchBeforeRangeChange([], minus, start);
}
this.array.splice(start, minus.length);
this.length -= minus.length;
if (this.dispatchesRangeChanges) {
this.dispatchRangeChange([], minus, start);
}
return minus.length;
} else {
return 0;
}
}
};
SortedArray.prototype.indexOf = function (value) {
// TODO throw error if provided a start index
return searchFirst(this.array, value, this.contentCompare, this.contentEquals);

@@ -167,2 +196,3 @@ };

SortedArray.prototype.lastIndexOf = function (value) {
// TODO throw error if provided a start index
return searchLast(this.array, value, this.contentCompare, this.contentEquals);

@@ -172,2 +202,3 @@ };

SortedArray.prototype.find = function (value, equals, index) {
// TODO throw error if provided a start index
if (equals) {

@@ -179,2 +210,3 @@ throw new Error("SortedArray#find does not support second argument: equals");

}
// TODO support initial partition index
return searchFirst(this.array, value, this.contentCompare, this.contentEquals);

@@ -190,2 +222,3 @@ };

}
// TODO support initial partition index
return searchLast(this.array, value, this.contentCompare, this.contentEquals);

@@ -300,2 +333,6 @@ };

SortedArray.prototype.toJSON = function () {
return this.toArray();
};
SortedArray.prototype.Iterator = Array.prototype.Iterator;

31

sorted-set.js

@@ -217,4 +217,7 @@ "use strict";

this.splay(value);
// assert root.value <= value
return this.root;
if (this.contentCompare(this.root.value, value) > 0) {
return this.root.getPrevious();
} else {
return this.root;
}
}

@@ -226,4 +229,7 @@ };

this.splay(value);
// assert root.value <= value
return this.root.getPrevious();
if (this.contentCompare(this.root.value, value) >= 0) {
return this.root.getPrevious();
} else {
return this.root;
}
}

@@ -235,5 +241,3 @@ };

this.splay(value);
// assert root.value <= value
var comparison = this.contentCompare(value, this.root.value);
if (comparison === 0) {
if (this.contentCompare(this.root.value, value) >= 0) {
return this.root;

@@ -249,5 +253,7 @@ } else {

this.splay(value);
// assert root.value <= value
var comparison = this.contentCompare(value, this.root.value);
return this.root.getNext();
if (this.contentCompare(this.root.value, value) <= 0) {
return this.root.getNext();
} else {
return this.root;
}
}

@@ -345,4 +351,5 @@ };

// This is the simplified top-down splaying algorithm from: "Self-adjusting
// Binary Search Trees" by Sleator and Tarjan guarantees that the root.value <=
// value if root exists
// Binary Search Trees" by Sleator and Tarjan. Guarantees that root.value
// equals value if value exists. If value does not exist, then root will be
// the node whose value either immediately preceeds or immediately follows value.
// - as described in https://github.com/hij1nx/forest

@@ -349,0 +356,0 @@ SortedSet.prototype.splay = function (value) {

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc