Socket
Socket
Sign inDemoInstall

collections

Package Overview
Dependencies
Maintainers
5
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 2.0.1 to 2.0.2

copy.js
lfu-map.js
lfu-set.js
operators.js

75

CHANGES.md

@@ -9,2 +9,77 @@

## v1.1.0
- Adds an LfuSet, a set useful as a cache with a least-frequently-used
eviction strategy.
- Fixes array `set` and `swap` for indexes outside the bounds of the existing
array, for both observed and unobserved arrays.
## v1.0.2
- Refinements on `Object.equals` and `Object.compare`. These are not
necessarily backward compatible, but should be a strict improvement:
- `Object.compare` will now return +/- Infinity for inequal strings,
rather than +/- 1 which imply that the distance between any two inequal
strings is always 1. `Object.compare` for numbers is suitable for finding
the magnitude of the difference as well as the direction.
- `Object.compare` and `Object.equals` will now delegate to either non-null,
non-undefined argument if the other argument is null or undefined.
This allows objects to be constructed that will identify themselves
as equivalent to null or undefined, for example `Any` types, useful for
testing.
- `Object.equals` will only compare object literals derrived directly from the
`Object.prototype`. All other objects that do not implement `compare` are
incomparable.
- First attempt at fixing `set`, `swap`, and `splice`, later fixed in v1.0.3.
`splice` must truncate the `start` index to the array length. `swap` and
`set` should not.
## v1.0.1
- Bug fix for filter on map-like collections.
## v1.0.0 :cake:
- Adds a Deque type based on a circular buffer of exponential
capacity. (@petkaantonov)
- Implements `peek`, `peekBack`, `poke`, and `pokeBack` on array
shim for Deque “isomorphism”.
- Fixes the cases where a change listener is added or removed during
change dispatch. Neither listener will be informed until the next
change. (@asolove)
- The property change listener system has been altered such that
once a thunk has been installed on an object, it will not be
removed, in order to avoid churn. Once a property has been
observed, it is likely to be observed again.
- Fixes `Object.equals` for comparing NaN to itself, which should
report `true` such that collections that use `Object.equals` to
identify values are able to find `NaN`. Previously, `NaN` could
get stuck in a collection permanently.
- In abstract, Collections previously identified duck types by
looking only at the prototype chain, ignoring owned properties.
Thus, an object could distinguish a property name that was being
used as a key of a record, from the same property name that was
being used as a method name. To improve performance and to face
the reality that oftentimes an owned property is in fact a method,
Collections no longer observe this distinction. That is, if an
object has a function by the appropriate name, either by ownership
or inheritance, it will be recognized as a method of a duck type.
This particularly affects `Object.equals`, which should be much
faster now.
- Fixes `Object.equals` such that property for property comparison
between objects only happens if they both descend directly from
`Object.prototype`. Previously, objects would be thus compared if
they both descended from the same prototype.
- Accommodate *very* large arrays with the `swap` shim. Previously,
the size of an array swap was limited by the size of the
JavaScript run-time stack. (@francoisfrisch)
- Fixes `splice` on an array when given a negative start index.
(@stuk)
- Some methods accept an optional `equals` or `index` argument
that may or may not be supported by certain collections, like
`find` on a `SortedSet` versus a `List`. Collections that do not
support this argument will now throw an error instead of silently
ignoring the argument.
- Fixes `Array#clone` cycle detection.
## v0.2.2

@@ -11,0 +86,0 @@

23

deque.js
"use strict";
require("./shim-object");
var GenericCollection = require("./generic-collection");
var GenericOrder = require("./generic-order");
var GenericOrder = require("./generic-order");
var ObservableRange = require("./observable-range");
var ObservableObject = require("./observable-object");
var ObservableRange = require("pop-observe/observable-range");
var ObservableObject = require("pop-observe/observable-object");
var Iterator = require("./iterator");
var copyProperties = require("./copy");
var equalsOperator = require("pop-equals");

@@ -30,6 +31,6 @@ // by Petka Antonov

Object.addEach(Deque.prototype, GenericCollection.prototype);
Object.addEach(Deque.prototype, GenericOrder.prototype);
Object.addEach(Deque.prototype, ObservableRange.prototype);
Object.addEach(Deque.prototype, ObservableObject.prototype);
copyProperties(Deque.prototype, GenericCollection.prototype);
copyProperties(Deque.prototype, GenericOrder.prototype);
copyProperties(Deque.prototype, ObservableRange.prototype);
copyProperties(Deque.prototype, ObservableObject.prototype);

@@ -354,3 +355,3 @@ Deque.prototype.maxCapacity = (1 << 30) | 0;

Deque.prototype.findValue = function (value, equals, index) {
equals = equals || Object.equals;
equals = equals || equalsOperator;
// Default start index at beginning

@@ -376,3 +377,3 @@ if (index == null) {

Deque.prototype.findLastValue = function (value, equals, index) {
equals = equals || Object.equals;
equals = equals || equalsOperator;
// Default start position at the end

@@ -398,3 +399,3 @@ if (index == null) {

Deque.prototype.has = function (value, equals) {
equals = equals || Object.equals;
equals = equals || equalsOperator;
// Left to right walk

@@ -404,3 +405,3 @@ var mask = this.capacity - 1;

var offset = (this.front + index) & mask;
if (this[offset] === value) {
if (equals(value, this[offset])) {
return true;

@@ -407,0 +408,0 @@ }

45

dict.js
"use strict";
var Shim = require("./shim");
var GenericCollection = require("./generic-collection");
var GenericMap = require("./generic-map");
var ObservableObject = require("./observable-object");
var ObservableObject = require("pop-observe/observable-object");
var Iterator = require("./iterator");
var copy = require("./copy");

@@ -25,3 +26,3 @@ // Burgled from https://github.com/domenic/dict

function mangle(key) {
return "~" + key;
return "$" + key;
}

@@ -33,5 +34,5 @@

Object.addEach(Dict.prototype, GenericCollection.prototype);
Object.addEach(Dict.prototype, GenericMap.prototype);
Object.addEach(Dict.prototype, ObservableObject.prototype);
copy(Dict.prototype, GenericCollection.prototype);
copy(Dict.prototype, GenericMap.prototype);
copy(Dict.prototype, ObservableObject.prototype);

@@ -44,10 +45,3 @@ Dict.prototype.isDict = true;

Dict.prototype.assertString = function (key) {
if (typeof key !== "string") {
throw new TypeError("key must be a string but Got " + key);
}
}
Dict.prototype.get = function (key, defaultValue) {
this.assertString(key);
var mangled = mangle(key);

@@ -64,3 +58,2 @@ if (mangled in this.store) {

Dict.prototype.set = function (key, value) {
this.assertString(key);
var mangled = mangle(key);

@@ -92,3 +85,2 @@ var from;

Dict.prototype.has = function (key) {
this.assertString(key);
var mangled = mangle(key);

@@ -99,3 +91,2 @@ return mangled in this.store;

Dict.prototype["delete"] = function (key) {
this.assertString(key);
var mangled = mangle(key);

@@ -156,1 +147,23 @@ var from;

Dict.prototype.iterate = function () {
return new this.Iterator(new Iterator(this.store));
};
Dict.prototype.Iterator = DictIterator;
function DictIterator(storeIterator) {
this.storeIterator = storeIterator;
}
DictIterator.prototype.next = function () {
var iteration = this.storeIterator.next();
if (iteration.done) {
return iteration;
} else {
return new Iterator.Iteration(
iteration.value,
unmangle(iteration.index)
);
}
};

16

fast-map.js
"use strict";
var Shim = require("./shim");
var Set = require("./fast-set");
var GenericCollection = require("./generic-collection");
var GenericMap = require("./generic-map");
var ObservableObject = require("./observable-object");
var ObservableObject = require("pop-observe/observable-object");
var equalsOperator = require("pop-equals");
var hashOperator = require("pop-hash");
var copy = require("./copy");

@@ -15,4 +17,4 @@ module.exports = FastMap;

}
equals = equals || Object.equals;
hash = hash || Object.hash;
equals = equals || equalsOperator;
hash = hash || hashOperator;
getDefault = getDefault || this.getDefault;

@@ -37,5 +39,5 @@ this.contentEquals = equals;

Object.addEach(FastMap.prototype, GenericCollection.prototype);
Object.addEach(FastMap.prototype, GenericMap.prototype);
Object.addEach(FastMap.prototype, ObservableObject.prototype);
copy(FastMap.prototype, GenericCollection.prototype);
copy(FastMap.prototype, GenericMap.prototype);
copy(FastMap.prototype, ObservableObject.prototype);

@@ -42,0 +44,0 @@ FastMap.prototype.constructClone = function (values) {

31

fast-set.js
"use strict";
var Shim = require("./shim");
var Dict = require("./dict");

@@ -9,3 +8,8 @@ var List = require("./list");

var TreeLog = require("./tree-log");
var ObservableObject = require("./observable-object");
var ObservableObject = require("pop-observe/observable-object");
var hashOperator = require("pop-hash");
var equalsOperator = require("pop-equals");
var iterate = require("pop-iterate");
var arrayify = require("pop-arrayify");
var copy = require("./copy");

@@ -20,5 +24,5 @@ var object_has = Object.prototype.hasOwnProperty;

}
equals = equals || Object.equals;
hash = hash || Object.hash;
getDefault = getDefault || Function.noop;
equals = equals || equalsOperator;
hash = hash || hashOperator;
getDefault = getDefault || noop;
this.contentEquals = equals;

@@ -34,5 +38,5 @@ this.contentHash = hash;

Object.addEach(FastSet.prototype, GenericCollection.prototype);
Object.addEach(FastSet.prototype, GenericSet.prototype);
Object.addEach(FastSet.prototype, ObservableObject.prototype);
copy(FastSet.prototype, GenericCollection.prototype);
copy(FastSet.prototype, GenericSet.prototype);
copy(FastSet.prototype, ObservableObject.prototype);

@@ -118,4 +122,8 @@ FastSet.prototype.Buckets = Dict;

FastSet.prototype.toArray = function () {
return flatten(this.buckets.map(arrayify));
};
FastSet.prototype.iterate = function () {
return this.buckets.values().flatten().iterate();
return iterate(this.toArray());
};

@@ -194,1 +202,6 @@

function flatten(arrays) {
return Array.prototype.concat.apply([], arrays);
}
function noop() {}

33

generic-collection.js
"use strict";
var equalsOperator = require("pop-equals");
var compareOperator = require("pop-compare");
var cloneOperator = require("pop-clone");
var unzipOperator = require("pop-zip/pop-unzip");
module.exports = GenericCollection;

@@ -67,3 +72,3 @@ function GenericCollection() {

GenericCollection.prototype.group = function (callback, thisp, equals) {
equals = equals || Object.equals;
equals = equals || equalsOperator;
var groups = [];

@@ -88,3 +93,3 @@ var keys = [];

GenericCollection.prototype.toArray = function () {
return this.map(Function.identity);
return this.map(identity);
};

@@ -142,3 +147,3 @@

GenericCollection.prototype.min = function (compare) {
compare = compare || this.contentCompare || Object.compare;
compare = compare || this.contentCompare || compareOperator;
var first = true;

@@ -156,3 +161,3 @@ return this.reduce(function (result, value) {

GenericCollection.prototype.max = function (compare) {
compare = compare || this.contentCompare || Object.compare;
compare = compare || this.contentCompare || compareOperator;
var first = true;

@@ -207,3 +212,3 @@ return this.reduce(function (result, value) {

table.unshift(this);
return Array.unzip(table);
return unzipOperator(table);
}

@@ -218,9 +223,9 @@

GenericCollection.prototype.sorted = function (compare, by, order) {
compare = compare || this.contentCompare || Object.compare;
compare = compare || this.contentCompare || compareOperator;
// account for comparators generated by Function.by
if (compare.by) {
by = compare.by;
compare = compare.compare || this.contentCompare || Object.compare;
compare = compare.compare || this.contentCompare || compareOperator;
} else {
by = by || Function.identity;
by = by || identity;
}

@@ -247,3 +252,3 @@ if (order === undefined)

GenericCollection.prototype.clone = function (depth, memo) {
GenericCollection.prototype.clone = function (depth, memo, clone) {
if (depth === undefined) {

@@ -254,7 +259,8 @@ depth = Infinity;

}
var clone = this.constructClone();
clone = clone || cloneOperator;
var collection = this.constructClone();
this.forEach(function (value, key) {
clone.add(Object.clone(value, depth - 1, memo), key);
collection.add(clone(value, depth - 1, memo), key);
}, this);
return clone;
return collection;
};

@@ -268,3 +274,2 @@

require("./shim-array");
function identity(value) { return value; }

38

generic-map.js
"use strict";
var Object = require("./shim-object");
var ObservableMap = require("./observable-map");
var ObservableObject = require("./observable-object");
var ObservableMap = require("pop-observe/observable-map");
var ObservableObject = require("pop-observe/observable-object");
var Iterator = require("./iterator");
var equalsOperator = require("pop-equals");
var compareOperator = require("pop-compare");
var copy = require("./copy");

@@ -13,4 +15,4 @@ module.exports = GenericMap;

Object.addEach(GenericMap.prototype, ObservableMap.prototype);
Object.addEach(GenericMap.prototype, ObservableObject.prototype);
copy(GenericMap.prototype, ObservableMap.prototype);
copy(GenericMap.prototype, ObservableObject.prototype);

@@ -132,3 +134,3 @@ // all of these methods depend on the constructor providing a `store` set

GenericMap.prototype.iterate = function () {
return new GenericMapIterator(this);
return new this.Iterator(this);
};

@@ -155,3 +157,3 @@

GenericMap.prototype.values = function () {
return this.map(Function.identity);
return this.map(identity);
};

@@ -165,9 +167,4 @@

// XXX deprecated
GenericMap.prototype.items = function () {
return this.entries();
};
GenericMap.prototype.equals = function (that, equals) {
equals = equals || Object.equals;
equals = equals || equalsOperator;
if (this === that) {

@@ -188,2 +185,3 @@ return true;

GenericMap.prototype.Item = Item;
GenericMap.prototype.Iterator = GenericMapIterator;

@@ -196,12 +194,11 @@ function Item(key, value) {

Item.prototype.equals = function (that) {
return Object.equals(this.key, that.key) && Object.equals(this.value, that.value);
return equalsOperator(this.key, that.key) && equalsOperator(this.value, that.value);
};
Item.prototype.compare = function (that) {
return Object.compare(this.key, that.key);
return compareOperator(this.key, that.key);
};
function GenericMapIterator(map) {
this.map = map;
this.iterator = map.store.iterate();
this.storeIterator = new Iterator(map.store);
}

@@ -213,3 +210,3 @@

GenericMapIterator.prototype.next = function () {
var iteration = this.iterator.next();
var iteration = this.storeIterator.next();
if (iteration.done) {

@@ -219,4 +216,4 @@ return iteration;

return new Iterator.Iteration(
iteration.value[1],
iteration.value[0]
iteration.value.value,
iteration.value.key
);

@@ -226,1 +223,2 @@ }

function identity(value) { return value; }

7

generic-order.js
var Object = require("./shim-object");
var equalsOperator = require("pop-equals");
var compareOperator = require("pop-compare");

@@ -10,3 +11,3 @@ module.exports = GenericOrder;

GenericOrder.prototype.equals = function (that, equals) {
equals = equals || this.contentEquals || Object.equals;
equals = equals || this.contentEquals || equalsOperator;

@@ -30,3 +31,3 @@ if (this === that) {

GenericOrder.prototype.compare = function (that, compare) {
compare = compare || this.contentCompare || Object.compare;
compare = compare || this.contentCompare || compareOperator;

@@ -33,0 +34,0 @@ if (this === that) {

4

generic-set.js
var has = require("pop-has");
module.exports = GenericSet;

@@ -17,3 +19,3 @@ function GenericSet() {

return this.constructClone(this.filter(function (value) {
return that.has(value);
return has(that, value);
}));

@@ -20,0 +22,0 @@ };

73

heap.js

@@ -5,8 +5,10 @@

require("./observable-array");
require("./shim");
var GenericCollection = require("./generic-collection");
var ObservableObject = require("./observable-object");
var ObservableRange = require("./observable-range");
var ObservableMap = require("./observable-map");
var ObservableObject = require("pop-observe/observable-object");
var ObservableRange = require("pop-observe/observable-range");
var ObservableMap = require("pop-observe/observable-map");
var O = require("pop-observe");
var equalsOperator = require("pop-equals");
var compareOperator = require("pop-compare");
var copy = require("./copy");

@@ -21,4 +23,4 @@ // Max Heap by default. Comparison can be reversed to produce a Min Heap.

}
this.contentEquals = equals || Object.equals;
this.contentCompare = compare || Object.compare;
this.contentEquals = equals || equalsOperator;
this.contentCompare = compare || compareOperator;
this.content = [];

@@ -31,6 +33,6 @@ this.length = 0;

Object.addEach(Heap.prototype, GenericCollection.prototype);
Object.addEach(Heap.prototype, ObservableObject.prototype);
Object.addEach(Heap.prototype, ObservableRange.prototype);
Object.addEach(Heap.prototype, ObservableMap.prototype);
copy(Heap.prototype, GenericCollection.prototype);
copy(Heap.prototype, ObservableObject.prototype);
copy(Heap.prototype, ObservableRange.prototype);
copy(Heap.prototype, ObservableMap.prototype);

@@ -63,3 +65,7 @@ Heap.prototype.constructClone = function (values) {

if (this.content.length > 0) {
this.content.set(0, top);
if (this.content.set) {
this.content.set(0, top);
} else {
this.content[0] = top;
}
this.sink(0);

@@ -93,5 +99,10 @@ }

var top = this.content.pop();
this.length = this.content.length;
if (index === this.content.length)
return true;
this.content.set(index, top);
if (this.content.set) {
this.content.set(index, top);
} else {
this.content[index] = top;
}
var comparison = this.contentCompare(top, value);

@@ -103,3 +114,2 @@ if (comparison > 0) {

}
this.length--;
return true;

@@ -133,4 +143,9 @@ };

if (this.contentCompare(parent, value) < 0) {
this.content.set(parentIndex, value);
this.content.set(index, parent);
if (this.content.set) {
this.content.set(parentIndex, value);
this.content.set(index, parent);
} else {
this.content[parentIndex] = value;
this.content[index] = parent;
}
} else {

@@ -188,4 +203,9 @@ // Stop propagating if the parent is greater than the value.

if (needsSwap) {
this.content.set(index, this.content[swapIndex]);
this.content.set(swapIndex, value);
if (this.content.set) {
this.content.set(index, this.content[swapIndex]);
this.content.set(swapIndex, value);
} else {
this.content[index] = this.content[swapIndex];
this.content[swapIndex] = value;
}
index = swapIndex;

@@ -222,11 +242,20 @@ // and continue sinking

Heap.prototype.makeMapChangesObservable = function () {
this.content.observeMapChange(this, "content");
this.content.observeMapWillChange(this, "content");
this.makeChangesObservable();
this.dispatchesMapChanges = true;
};
Heap.prototype.makeRangeChangesObservable = function () {
this.content.observeRangeChange(this, "content");
this.content.observeRangeWillChange(this, "content");
this.makeChangesObservable();
this.dispatchesRangeChanges = true;
};
Heap.prototype.makeChangesObservable = function () {
if (this.dispatchesChanges) {
return;
}
O.observeMapChange(this.content, this, "content");
O.observeMapWillChange(this.content, this, "content");
this.dispatchesChanges = true;
};
Heap.prototype.handleContentRangeChange = function (plus, minus, index) {

@@ -233,0 +262,0 @@ this.dispatchRangeChange(plus, minus, index);

22

iterator.js

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

var WeakMap = require("./weak-map");
var WeakMap = require("weak-map");
var GenericCollection = require("./generic-collection");

@@ -28,2 +28,4 @@

this.next = iterable;
} else if (Object.getPrototypeOf(iterable) === Object.prototype) {
iterators.set(this, new ObjectIterator(iterable));
} else {

@@ -65,4 +67,3 @@ throw new TypeError("Can't iterate " + iterable);

// A level of indirection so a full-interface iterator can proxy for a simple
// nextable iterator, and to allow the child iterator to replace its governing
// iterator, as with drop-while iterators.
// nextable iterator.
Iterator.prototype.next = function () {

@@ -339,2 +340,17 @@ var nextable = iterators.get(this);

function ObjectIterator(object) {
this.object = object;
this.iterator = new Iterator(Object.keys(object));
}
ObjectIterator.prototype.next = function () {
var iteration = this.iterator.next();
if (iteration.done) {
return iteration;
} else {
var key = iteration.value;
return new Iteration(this.object[key], key);
}
};
Iterator.cycle = function (cycle, times) {

@@ -341,0 +357,0 @@ if (arguments.length < 2) {

57

list.js

@@ -5,9 +5,13 @@ "use strict";

var Shim = require("./shim");
var GenericCollection = require("./generic-collection");
var GenericOrder = require("./generic-order");
var ObservableObject = require("./observable-object");
var ObservableRange = require("./observable-range");
var ObservableObject = require("pop-observe/observable-object");
var ObservableRange = require("pop-observe/observable-range");
var Iterator = require("./iterator");
var equalsOperator = require("pop-equals");
var arrayify = require("pop-arrayify");
var copy = require("./copy");
var emptyArray = [];
function List(values, equals, getDefault) {

@@ -20,4 +24,4 @@ if (!(this instanceof List)) {

head.prev = head;
this.contentEquals = equals || Object.equals;
this.getDefault = getDefault || Function.noop;
this.contentEquals = equals || equalsOperator;
this.getDefault = getDefault || noop;
this.length = 0;

@@ -29,6 +33,6 @@ this.addEach(values);

Object.addEach(List.prototype, GenericCollection.prototype);
Object.addEach(List.prototype, GenericOrder.prototype);
Object.addEach(List.prototype, ObservableObject.prototype);
Object.addEach(List.prototype, ObservableRange.prototype);
copy(List.prototype, GenericCollection.prototype);
copy(List.prototype, GenericOrder.prototype);
copy(List.prototype, ObservableObject.prototype);
copy(List.prototype, ObservableRange.prototype);

@@ -44,3 +48,5 @@ List.prototype.constructClone = function (values) {

while (at !== head) {
if (equals(at.value, value)) {
// Note that the given value occurs first so that it can be a matcher
// like an Any(Number) object.
if (equals(value, at.value)) {
return at;

@@ -57,3 +63,3 @@ }

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

@@ -89,4 +95,4 @@ }

if (this.dispatchesRangeChanges) {
this.dispatchRangeChange(plus, minus, found.index);
this.updateIndexes(found.next, found.index);
this.dispatchRangeChange(plus, minus, found.index);
}

@@ -142,3 +148,3 @@ return true;

if (this.dispatchesRangeChanges) {
this.updateIndexes(start.next, start.index === undefined ? 0 : start.index + 1);
this.updateIndexes(start, start.index);
this.dispatchRangeChange(plus, minus, index);

@@ -163,3 +169,3 @@ }

if (this.dispatchesRangeChanges) {
this.updateIndexes(this.head.next, 0);
this.updateIndexes(this.head, -1);
this.dispatchRangeChange(plus, minus, 0);

@@ -202,3 +208,3 @@ }

if (this.dispatchesRangeChanges) {
this.updateIndexes(this.head.next, 0);
this.updateIndexes(this.head, -1);
this.dispatchRangeChange(plus, minus, 0);

@@ -294,3 +300,3 @@ }

}
plus = Array.from(plus);
plus = arrayify(plus);

@@ -338,5 +344,5 @@ // collect the minus array

if (start === this.head) {
this.updateIndexes(this.head.next, 0);
this.updateIndexes(this.head, -1);
} else {
this.updateIndexes(startNode.next, startNode.index + 1);
this.updateIndexes(startNode, startNode.index);
}

@@ -396,14 +402,17 @@ this.dispatchRangeChange(plus, minus, index);

List.prototype.updateIndexes = function (node, index) {
while (node !== this.head) {
do {
node.index = index++;
node = node.next;
}
} while (node !== this.head);
};
List.prototype.makeRangeChangesObservable = function () {
this.head.index = -1;
this.updateIndexes(this.head.next, 0);
ObservableRange.prototype.makeRangeChangesObservable.call(this);
this.updateIndexes(this.head, -1);
this.dispatchesRangeChanges = true;
};
List.prototype.toArray = function () {
return this.slice();
};
List.prototype.iterate = function () {

@@ -464,1 +473,3 @@ return new ListIterator(this.head);

function noop() {}

16

lru-map.js
"use strict";
var Shim = require("./shim");
var LruSet = require("./lru-set");
var GenericCollection = require("./generic-collection");
var GenericMap = require("./generic-map");
var ObservableObject = require("./observable-object");
var ObservableObject = require("pop-observe/observable-object");
var equalsOperator = require("pop-equals");
var hashOperator = require("pop-hash");
var copy = require("./copy");

@@ -15,4 +17,4 @@ module.exports = LruMap;

}
equals = equals || Object.equals;
hash = hash || Object.hash;
equals = equals || equalsOperator;
hash = hash || hashOperator;
getDefault = getDefault || this.getDefault;

@@ -39,5 +41,5 @@ this.capacity = capacity || Infinity;

Object.addEach(LruMap.prototype, GenericCollection.prototype);
Object.addEach(LruMap.prototype, GenericMap.prototype);
Object.addEach(LruMap.prototype, ObservableObject.prototype);
copy(LruMap.prototype, GenericCollection.prototype);
copy(LruMap.prototype, GenericMap.prototype);
copy(LruMap.prototype, ObservableObject.prototype);

@@ -44,0 +46,0 @@ LruMap.prototype.constructClone = function (values) {

23

lru-set.js
"use strict";
var Shim = require("./shim");
var Set = require("./set");
var GenericCollection = require("./generic-collection");
var GenericSet = require("./generic-set");
var ObservableObject = require("./observable-object");
var ObservableRange = require("./observable-range");
var ObservableObject = require("pop-observe/observable-object");
var ObservableRange = require("pop-observe/observable-range");
var equalsOperator = require("pop-equals");
var hashOperator = require("pop-hash");
var copy = require("./copy");

@@ -17,5 +19,5 @@ module.exports = LruSet;

maxLength = maxLength || Infinity;
equals = equals || Object.equals;
hash = hash || Object.hash;
getDefault = getDefault || Function.noop;
equals = equals || equalsOperator;
hash = hash || hashOperator;
getDefault = getDefault || noop;
this.store = new Set(undefined, equals, hash);

@@ -32,6 +34,6 @@ this.contentEquals = equals;

Object.addEach(LruSet.prototype, GenericCollection.prototype);
Object.addEach(LruSet.prototype, GenericSet.prototype);
Object.addEach(LruSet.prototype, ObservableObject.prototype);
Object.addEach(LruSet.prototype, ObservableRange.prototype);
copy(LruSet.prototype, GenericCollection.prototype);
copy(LruSet.prototype, GenericSet.prototype);
copy(LruSet.prototype, ObservableObject.prototype);
copy(LruSet.prototype, ObservableRange.prototype);

@@ -145,1 +147,2 @@ LruSet.prototype.constructClone = function (values) {

function noop() {}

16

map.js
"use strict";
var Shim = require("./shim");
var Set = require("./set");
var GenericCollection = require("./generic-collection");
var GenericMap = require("./generic-map");
var ObservableObject = require("./observable-object");
var ObservableObject = require("pop-observe/observable-object");
var equalsOperator = require("pop-equals");
var hashOperator = require("pop-hash");
var copy = require("./copy");

@@ -15,4 +17,4 @@ module.exports = Map;

}
equals = equals || Object.equals;
hash = hash || Object.hash;
equals = equals || equalsOperator;
hash = hash || hashOperator;
getDefault = getDefault || this.getDefault;

@@ -37,5 +39,5 @@ this.contentEquals = equals;

Object.addEach(Map.prototype, GenericCollection.prototype);
Object.addEach(Map.prototype, GenericMap.prototype); // overrides GenericCollection
Object.addEach(Map.prototype, ObservableObject.prototype);
copy(Map.prototype, GenericCollection.prototype);
copy(Map.prototype, GenericMap.prototype); // overrides GenericCollection
copy(Map.prototype, ObservableObject.prototype);

@@ -42,0 +44,0 @@ Map.prototype.constructClone = function (values) {

26

package.json
{
"name": "collections",
"version": "2.0.1",
"version": "2.0.2",
"publishConfig": {
"tag": "future"
},
"description": "data structures with idiomatic JavaScript collection interfaces",

@@ -31,14 +34,27 @@ "homepage": "http://github.com/montagejs/collections",

"dependencies": {
"mini-map": "^1.0.0",
"pop-arrayify": "^1.0.0",
"pop-clear": "^1.0.0",
"pop-clone": "^1.0.1",
"pop-compare": "^1.0.0",
"pop-equals": "^1.0.0",
"pop-has": "^1.0.0",
"pop-hash": "^1.0.0",
"pop-iterate": "^1.0.1",
"pop-observe": "^2.0.2",
"pop-swap": "^1.0.0",
"pop-zip": "^1.0.0",
"regexp-escape": "0.0.1",
"weak-map": "^1.0.4"
},
"devDependencies": {
"jasminum": "^2.0.1",
"sinon": "^1.9.0",
"istanbul": "^0.2.4",
"opener": "^1.3.0"
"jasminum": "^2.0.6",
"opener": "^1.3.0",
"sinon": "^1.9.0"
},
"scripts": {
"test": "jasminum spec && jasminum-phantom spec",
"test": "jasminum spec",
"cover": "istanbul cover spec/index.js spec && istanbul report html && opener coverage/index.html"
}
}

1696

README.md

@@ -1,2 +0,2 @@

[![Build Status](https://travis-ci.org/montagejs/collections.png?branch=master)](http://travis-ci.org/montagejs/collections)
[![Build Status](https://travis-ci.org/kriskowal/collections.png?branch=v2)](http://travis-ci.org/montagejs/collections)

@@ -9,6 +9,9 @@ # Collections

You can use these Node Packaged Modules with Node.js, [Browserify][], [Mr][],
[Mop][], 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.
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.

@@ -21,1684 +24,7 @@ ```

[Mr]: https://github.com/montagejs/mr
[Mop]: https://github.com/montagejs/mop
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`.
### 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, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict)
### has
#### has(key)
Whether a value for the given key exists.
(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.
(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)`.
(Array+, Map, SortedMap, SortedArrayMap, WeakMap, Object+)
#### get(value)
Gets the equivalent value, or falls back to `getDefault(value)`.
(List, Deque, Set, SortedSet, LruSet, SortedArray, SortedArraySet,
FastSet)
### set(key or index, value)
Sets the value for a key.
(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.
(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.
(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.
(Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
### delete
#### delete(key)
Deletes the value for a given key. Returns whether the key was
found.
(Map, MultiMap, WeakMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
#### delete(value)
Deletes a value. Returns whether the value was found.
(Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet, Heap)
#### delete(value, equals)
Deletes the equivalent value. Returns whether the value was found.
(Array+, List, Deque)
### deleteEach(values or keys)
Deletes every value or every value for each key.
(Array+, List, Deque, Set, Map, MultiMap, SortedSet, SortedMap,
LruSet, LruMap, 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.
(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.
(Array, ~~List~~, Deque, SortedArray, SortedArraySet)
### findValue(value, opt_equals)
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, Deque, SortedSet)
### findLastValue(value, opt_equals)
Finds the last equivalent value, returning the node at which the
value was found.
(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.
(SortedSet)
### findLeastGreaterThan(value)
Finds the smallest value greater than the given value. This is fast
(logarithic) but does cause rotations.
(SortedSet)
### findLeastGreaterThanOrEqual(value)
Finds the smallest value greater than or equal to the given value.
This is fast (logarithmic) but does cause rotations.
(SortedSet)
### findGreatest()
(SortedSet)
### findGreatestLessThan(value)
(SortedSet)
### findGreatestLessThanOrEqual(value)
(SortedSet)
### push
#### push(...values)
Adds values to the end of a collection.
(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.
(Set, SortedSet, LruSet, SortedArray, SortedArraySet, FastSet, Heap)
### unshift
#### unshift(...values)
Adds values to the beginning of a collection.
(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.
(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.
(Array, List, Deque, Set, SortedSet, LruSet, SortedArray,
SortedArraySet, Heap)
### shift()
Removes and returns the value at the beginning of a collection.
(Array, List, Deque, Set, SortedSet, LruSet, SortedArray,
SortedArraySet)
### peek()
Returns the next value in an deque, as would be returned by the next
`shift`.
(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.
(Array, List, Deque)
### peekBack()
Returns the last value in an deque, as would be returned by the next
`pop`.
(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.
(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.
(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.
(Array, List, SortedArray, SortedSet, SortedArraySet)
### swap(start, length, values)
Performs a splice without variadic arguments.
(Array+, List, SortedArray, SortedSet, SortedArraySet)
### clear()
Deletes the all values.
(Array+, Object+, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, 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.
(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.
(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.
(Array+, Object+, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap, Iterator)
### reverse()
Reverses a collection in place.
(Array, List)
### reversed()
Returns a collection of the same type with this collection's
contents in reverse order.
(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.
(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.
(Array, ~~Object+~~, Iterator, List, Set, Map, MultiMap,
SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### keys()
Returns an array of the keys.
(Object, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
### values()
Returns an array of the values
(Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
### entries()
Returns an array of `[key, value]` pairs for each entry.
(Object+, Map, MultiMap, SortedMap, LruMap, SortedArrayMap, FastMap,
Dict)
### reduce(callback(result, value, key, object, depth), basis, thisp)
(Array, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### reduceRight(callback(result, value, key, object, depth), basis, thisp)
(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.
(Array, Object+, Iterator, List, Deque, Set, Map, MultiMap, WeakMap,
SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### map(callback(value, key, object, depth), thisp)
(Array, Object+, Iterator, List, Deque, Set, Map, MultiMap, WeakMap,
SortedSet, SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### toArray()
(Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, 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.
(Array+ Iterator, List, Deque, Map, MultiMap, SortedMap, LruMap,
SortedArrayMap, FastMap, Dict, Heap)
### filter(callback(value, key, object, depth), thisp)
(Array, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, 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.
(Array, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
*The method `all` from version 1 was removed in version 2 in favor of
the idiom `every(Boolean)`.*
### 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.
(Array, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
*The method `any` from version 1 was removed in version 2 in favor of
the idiom `some(Boolean)`.*
### 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).
(Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, 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).
(Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, 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.
(Array+, List, Deque, Set, Map, MultiMap, SortedSet, SortedMap,
LruSet, LruMap, 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.
(Array+, List, Deque, Set, Map, MultiMap, SortedSet, SortedMap,
LruSet, LruMap, SortedArray, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### sum()
(Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict)
### average()
(Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict)
### flatten()
(Array+, Iterator, List, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### zip(...collections)
(Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### enumerate(zero)
(Array+, Iterator, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, 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.
(Array+, Object+, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, 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.
(Array+, Object+, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, SortedArray, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict, Heap)
### equals(that, equals)
(Array+, Object+, List, Deque, Set, Map, MultiMap, SortedSet,
SortedMap, LruSet, LruMap, ~~SortedArray~~, SortedArraySet,
SortedArrayMap, FastSet, FastMap, Dict)
### compare(that)
(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.
(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.
(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.
(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`.
(SortedSet)
### Iterator(iterable, start, stop, step)
*Redesigned in version 2.*
Creates an iterator from an iterable. Iterables include:
- instances of Iterator, in which case the “iterable” will be simply returned
instead of a new iterator.
- objects with an `iterate(start, stop, step)` method, in which case the
optional `start`, `stop`, and `step` arguments are forwarded. Collections
implement this iterface, including Array.
- objects with a `next()` method, which is to say existing iterators,
though this iterator will only depend on the `next()` method and provide
the much richer Iterator interface using it.
- `next()` functions.
Iterators are defined by the upcoming version of ECMAScript. The `next()` method
returns what I am calling an “iteration”, an object that has a `value` property
and an optional `done` flag. When `done` is true, the iteration signals the end
of the iterator and may be accompanied by a “return value” instead of a “yield
value”.
In addition, Iterator produces iterations with an optional `index` property. The
indexes produced by an array are the positions of each value, which are
non-contiguous for sparse arrays.
*In version 1, iterators followed the old, Pythonic protocol established in
Mozilla’s SpiderMonkey, where iterators yielded values directly and threw
`StopIteration` to terminate.*
#### dropWhile(callback(value, index, iterator), thisp)
Returns an iterator that begins with the first iteration from this iterator to
fail the given test.
#### takeWhile(callback(value, index, iterator), thisp)
Returns an iterator that ends before the first iteration from this iterator to
fail the given test.
#### iterateMap(callback(value, index, iterator))
*Renamed in version 2 from `mapIterator` in version 1.*
Returns an iterator for a mapping on the source values. Values are
consumed on demand.
#### iterateFilter(callback(value, index, iterator))
*Renamed in version 2 from `filterIterator` in version 1.*
Returns an iterator for those values from the source that pass the
given guard. Values are consumed on demand.
#### iterateZip(...iterables)
*Introduced in version 2.*
Returns an iterator that incrementally combines the respective
values of the given iterations, first including itself.
#### iterateUnzip()
*Introduced in version 2.*
Assuming that this is an iterator that produces iterables, produces an iteration
of the reslective values from each iterable.
#### iterateConcat(...iterables)
*Renamed in version 2 from `concat` in version 1.*
Creates an iteration that first produces all the values from this iteration,
then from each subsequent iterable in order.
#### iterateFlatten()
*Introduced in version 2.*
Assuming that this is an iterator that produces iterables, creates an iterator
that yields all of the values from each of those iterables in order.
#### iterateEnumerate(start = 0)
*Renamed in version 2 from `enumerateIterator` in version 1.*
Returns an iterator that provides [index, value] pairs from the
source iteration.
#### recount(start=0)
*Introduced in version 2.*
Produces a new version of this iteration where the indexes are recounted. The
indexes for sparse arrays are not contiguous, as well as the iterators produced
by `filter`, `cycle`, `flatten`, and `concat` that pass iterations through
without alteration from various sources. `recount` smoothes out the sequence.
### Iterator utilities
#### cycle(iterable, times=Infinity)
Produces an iterator that will cycle through the values from a given iterable
some number of times, indefinitely by default. The given iterable must be able
to produce the sequence of values each time it is iterated, which is to say, not
an iterator, but any collection would do.
#### unzip(iterables)
Transposes a two dimensional iterable, which is to say, produces an iterator
that will yield a tuple of the respective values from each of the given
iterables.
#### zip(...iterables)
Transposes a two dimensional iterable, which is to say, produces an iterator
that will yield a tuple of the respective values from each of the given
iterables. `zip` differs from `unzip` only in that the arguments are variadic.
#### flatten(iterables)
*Renamed in version 2 from `concat` in version 1.*
Returns an iterator that will produce all the values from each of the given
iterators in order.
#### concat(...iterables)
*Renamed in version 2 from `chain` in version 1.*
Returns an iterator that will produce all the values from each of the given
iterators in order. Differs from `flatten` only in that the arguments are
variadic.
#### range(length)
Iterates `length` numbers starting from 0.
#### range(start, stop, step=1)
Iterates numbers from start to stop by step.
#### count(start, step)
Iterates numbers from start by step, indefinitely.
#### repeat(value, times)
Repeats the given value either finite times or indefinitely.
## Change Observers
*Introduced in version 2.*
All collections support change observers. There are three types of changes.
Property changes, range changes, and map changes. Whether a collection supports
a kind of change can be inferred by the existence of an `observe*` method
appropriate to the kind of change, `observeRangeChange` for example.
#### Observers
The `observe*` methods all return “observer” objects with some overlapping
interface. Most importantly, an “observer” has a `cancel()` method that will
remove the observer from the queue of observers for its corresponding object and
property name. To reduce garbage collection churn, the observer may be reused,
but if the observer is canceled during change dispatch, it will not be recycled
until all changes have been handled. Also, if an observer is cancelled during
change dispatch, it will be passed over. If an observer is created during change
dispatch, it will also be passed over, to be informed of any subsequent changes.
The observer will have a `handlerMethodName` property, based on a convention
that take into account all the parameters of the change observer and what
methods are available on the handler, such as `handleFooPropertyWillChange` or
simply null if the handler is a function. This method name can be overridden if
you need to break from convention.
The observer will also have a `dispatch` method that you can use to manually
force a change notification.
The observer will have a `note` property, as provided as an argument to the
observe method. This value is not used by the change observer system, but is
left for the user, for example to provide helpful information for inspecting why
the observer exists and what systems it participates in.
The observer will have a `childObserver` property. Handlers have the option of
returning an observer, if that observer needs to be canceled when this observer
notices a change. This facility allows observers to “stack”.
All kinds of changes have a `get*ChangeObservers` method that will return an
array of change observers. This function will consistently return the same array
for the same arguments, and the content of the array is itself observable.
#### Handlers
A handler may be an object with a handler method or a function. Either way, the
change observer will dispatch an argument pattern to the observer including both
the new and old values associated with the change and other parameters that
allow generic handlers to multiplex changes from multiple sources. See the
specific change observer documentation for details about the argument pattern
and handler method name convention.
Again, a handler has the option of returning an observer. This observer will be
canceled if there is a subsequent change. So for example, if you are observing
the "children" property of the "root" property of a tree, you would be able to
stack the "children" property observer on top of the "root" property observer,
ensuring that the children property observer does not linger on old roots.
If a handler throws an exception, it will not corrupt the state of the change
notification system, but it may corrupt the state of the observed object and the
assuptions of the rest of the program. Such errors are annotated by the change
dispatch system to increase awareness that all such errors are irrecoverable
programmer errors.
#### Capture
All observers support “change” and “will change” (“capture”) phases. Both phases
receive both the old and new values, but in the capture phase, the direct
interrogation of the object being observed will show that the change has not
taken effect, though change observers do not provide a facility for preventing a
change and throwing exceptions can corrupt the state of involved collections.
All “will change” methods exist to increase the readability of the program but
simply forward a true “capture” argument to the corresponding “change” method.
For example, `map.observeMapWillChange(handler)` just calls
`map.observeMapChange(handler, null, null, true)`, eliding the `name` and `note`
arguments not provided.
### Property Changes
The `observable-object` module provides facilities for observing changes to
properties on arbitrary objects, as well as a mix-in prototype that allows any
collection to support the property change observer interface directly. The
`observable-array` module alters the `Array` in this context to support the
property observer interface for its `"length"` property and indexed properties
by number, as long as those properties are altered by a method of the array
(which is to say, *caveat emptor: direct assignment to a property of an array is
not observable*). This shim does not introduce any overhead to arrays that are
not observed.
```javascript
var ObservableObject = require("collections/observable-object");
ObservableObject.observePropertyChange(object, name, handler, note, capture);
ObservableObject.observePropertyWillChange(object, name, handler, note, capture);
ObservableObject.dispatchPropertyChange(object, plus, minus);
ObservableObject.dispatchPropertyWillChange(object, plus, minus);
ObservableObject.getPropertyChangeObservers(object, name, capture)
ObservableObject.getPropertyWillChangeObservers(object, name, capture)
ObservableObject.makePropertyObservable(object, name);
ObservableObject.preventPropertyObserver(object, name);
```
All of these methods delegate to methods of the same name on an object if one
exists, making it possible to use these on arbitrary objects as well as objects
with custom property observer behavior. The property change observer interface
can be imbued on arbitrary objects.
```javascript
Object.addEach(Constructor.prototype, ObservableObject.prototype);
var object = new Constructor();
object.observePropertyChange(name, handler, note, capture);
object.observePropertyWillChange(name, handler, note);
object.dispatchPropertyChange(plus, minus, capture);
object.dispatchPropertyWillChange(plus, minus);
object.getPropertyChangeObservers(name, capture)
object.getPropertyWillChangeObservers(name)
object.makePropertyObservable(name);
object.preventPropertyObserver(name);
```
`observePropertyChange` and `observePropertyWillChange` accept a property
`name` and a `handler` and returns an `observer`.
#### Handlers
The arguments to a property change handler are:
- `plus`: the new value
- `minus`: the old value
- `name` (`observer.propertyName`, the `name` argument to
`observePropertyChange`)
- `object` (`observer.object`, the `object` given to `observePropertyChange`)
- `this` is the `handler` or undefined if the handler is a callable.
The prefereed handler method name for a property change observer is composed:
- `"handle"`
- `name`, with the first character capitalized
- `"Property"`
- `"Will"` if `capture`
- `"Change"`
*The specific handler method name differs from those constructed by version 1,
in that it includes the term, `"Property"`. Thus, all observer handler method
names now receive a complete description of the kind of change, at the expense
of some verbosity.*
If this method does not exist, the method name falls back to the generic without
the property name:
- `"handle"`
- `"Property"`
- `"Will"` if `capture`
- `"Change"`
Otherwise, the handler must be callable, implementing `handler.call(this, plus,
minus, name, object)`, but not necessarily a function.
#### Observers
A property change observer has properties in addition to those common to all
observers.
- `propertyName`
- `value` the last value dispatched. This will be used if `minus` is not given
when a change is dispatched and is otherwise is useful for inspecting
observers.
#### Observability
Property change observers use various means to make properties observable. In
general, they install a “thunk” property on the object that intercepts `get` and
`set` calls. A thunk will never be installed over an existing thunk.
Observers take great care to do what makes sense with the underlying property
descriptor. For example, different kinds of thunks are installed for descriptors
with `get` and `set` methods than those with a simple `value`. If a property is
read-only, either indicated by `writable` being false or `get` being provided
without a matching `set`, no thunk is installed at all.
If a property is ostensibly immutable, for lack of a `set` method, but the value
returned by `get` does in fact change in response to exogenous changes, those
changes may be rigged to dispatch a property change manually, using one of the
above `dispatch` methods.
To avoid installing a thunk on every instance of particular constructor,
`makePropertyObservable` can be applied to a property of a prototype. To avoid
installing a thunk on a property at all, `preventPropertyObserver` can be
applied to either an instance or a prototype.
Properties of an `Array` cannot be observed with thunks, so the
`observable-array` module adds methods to the Array prototype that allow it to
be transformed into an observed array on demand. The transformation involves
replacing all the methods that modify the content of the array with versions
that report the changes. The observable array interface is installed either by
subverting the prototype of the instance, or by redefining these methods
directly onto the instance if the prototype is not mutable.
### Range Changes
Many collections represent a contiguous range of values in a fixed order. For
these collections, range change observation is available.
- `Array` with `require("collections/observable-array")`
- `List`&dagger;
- `Deque`
- `Set`&dagger;
- `SortedSet`
- `SortedArray`
- `SortedArraySet`
- `Heap`
*&dagger;Note that with `List` and `Set`, observing range changes often
nullifies any performance improvment that might be gained using them instead of
an array, deque, or array-backed set.*
`SortedSet` can grow to absurd proportions and still quickly dispatch range
change notifications at any position, owing to an algorithim that can
incrementally track the index of each node in time proportional to the logarithm
of the size of the collection.
The `observe-range-changes` module exports a **mixin** that provides the range
change interface for a collection.
```javascript
collection.observeRangeChange(handler, name, note, capture)
collection.observeRangeWillChange(handler, name, note)
collection.dispatchRangeChange(plus, minus, index, capture)
collection.dispatchRangeWillChange(plus, minus, index)
collection.getRangeChangeObservers(capture)
collection.getRangeWillChangeObservers()
collection.makeRangeChangeObservable()
```
The `name` is optional and only affects the handler method name computation.
The convention for the name of a range change handler method name is:
- `"handle"`
- `name` with the first character capitalized, if given, and only if the
resulting method name is available on the handler.
- `"Range"`
- `"Will"` if `capture`
- `"Change"`
The arguments of a range change are:
- `plus`: values added at `index`
- `minus`: values removed at `index` before `plus` was added
- `index`
- `collection`
The `makeRangeChangeObservable` method is overridable if a collection needs to
perform some operations apart from setting `dispatchesRangeChanges` in order to
become observable. For example, a `Set` has to establish observers on its own
`order` storage list.
### Map Changes
*Note: map change observers are very different than version 1 map change
listeners.*
Many collections represent a mapping from keys to values, irrespective of order.
For most of these collections, map change observation is available.
- `Array` with `require("collections/observable-array")`
- `Map`
- `FastMap`
- `LruMap`
- `SortedMap`
- `SortedArrayMap`
- `Dict`
- `Heap` only for key 0
```javascript
collection.observeMapChange(handler, name, note, capture)
collection.observeMapWillChange(handler, name, note)
collection.dispatchMapChange(plus, minus, index, capture)
collection.dispatchMapWillChange(plus, minus, index)
collection.getMapChangeObservers(capture)
collection.getMapWillChangeObservers()
collection.makeMapChangeObservable()
```
The `name` is optional and only affects the handler method name computation.
The convention for the name of a range change handler method name is:
- `"handle"`
- `name` with the first character capitalized, if given, and only if the
resulting method name is available on the handler.
- `"Map"`
- `"Will"` if `capture`
- `"Change"`
The arguments of a range change are:
- `plus`: the new value
- `minus`: the old value
- `key`
- `type`: one of `"create"`, `"update"`, or `"delete"`
- `collection`
The `makeMapChangeObservable` method is overridable if a collection needs to
perform some operations apart from setting `dispatchesMapChanges` in order to
become observable.
## Change Listeners
*The change listener interface exists in version 1, but has been replaced with
Change Observers in version 2.*
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
- rearchitect ordered collections in terms of iteration instead of reduction,
at least for methods that short circuit like some and every
- eliminate any/all
- comprehensive specs and spec coverage tests
- fast list splicing
- Make it easier to created a SortedSet with a criterion like
Function.by(Function.get('name'))
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)
- array-set (a set, for fast lookup, backed by an array for meaningful
range changes)

29

set.js
"use strict";
var Shim = require("./shim");
var List = require("./list");

@@ -8,4 +7,7 @@ var FastSet = require("./fast-set");

var GenericSet = require("./generic-set");
var ObservableObject = require("./observable-object");
var ObservableRange = require("./observable-range");
var ObservableObject = require("pop-observe/observable-object");
var ObservableRange = require("pop-observe/observable-range");
var equalsOperator = require("pop-equals");
var hashOperator = require("pop-hash");
var copy = require("./copy");

@@ -18,5 +20,5 @@ module.exports = Set;

}
equals = equals || Object.equals;
hash = hash || Object.hash;
getDefault = getDefault || Function.noop;
equals = equals || equalsOperator;
hash = hash || hashOperator;
getDefault = getDefault || noop;
this.contentEquals = equals;

@@ -45,6 +47,6 @@ this.contentHash = hash;

Object.addEach(Set.prototype, GenericCollection.prototype);
Object.addEach(Set.prototype, GenericSet.prototype);
Object.addEach(Set.prototype, ObservableObject.prototype);
Object.addEach(Set.prototype, ObservableRange.prototype);
copy(Set.prototype, GenericCollection.prototype);
copy(Set.prototype, GenericSet.prototype);
copy(Set.prototype, ObservableObject.prototype);
copy(Set.prototype, ObservableRange.prototype);

@@ -164,2 +166,6 @@ Set.prototype.Order = List;

Set.prototype.toArray = function () {
return this.order.toArray();
};
Set.prototype.iterate = function () {

@@ -176,4 +182,5 @@ return this.order.iterate();

this.order.makeRangeChangesObservable();
ObservableRange.prototype.makeRangeChangesObservable.call(this);
};
function noop() {}

16

sorted-array-map.js
"use strict";
var Shim = require("./shim");
var SortedArraySet = require("./sorted-array-set");
var GenericCollection = require("./generic-collection");
var GenericMap = require("./generic-map");
var ObservableObject = require("./observable-object");
var ObservableObject = require("pop-observe/observable-object");
var equalsOperator = require("pop-equals");
var compareOperator = require("pop-compare");
var copy = require("./copy");

@@ -15,4 +17,4 @@ module.exports = SortedArrayMap;

}
equals = equals || Object.equals;
compare = compare || Object.compare;
equals = equals || equalsOperator;
compare = compare || compareOperator;
getDefault = getDefault || this.getDefault;

@@ -38,5 +40,5 @@ this.contentEquals = equals;

Object.addEach(SortedArrayMap.prototype, GenericCollection.prototype);
Object.addEach(SortedArrayMap.prototype, GenericMap.prototype);
Object.addEach(SortedArrayMap.prototype, ObservableObject.prototype);
copy(SortedArrayMap.prototype, GenericCollection.prototype);
copy(SortedArrayMap.prototype, GenericMap.prototype);
copy(SortedArrayMap.prototype, ObservableObject.prototype);

@@ -43,0 +45,0 @@ SortedArrayMap.prototype.constructClone = function (values) {

8

sorted-array-set.js
"use strict";
var Shim = require("./shim");
var SortedArray = require("./sorted-array");
var GenericSet = require("./generic-set");
var ObservableObject = require("./observable-object");
var ObservableObject = require("pop-observe/observable-object");
var copy = require("./copy");

@@ -24,4 +24,4 @@ module.exports = SortedArraySet;

Object.addEach(SortedArraySet.prototype, GenericSet.prototype);
Object.addEach(SortedArraySet.prototype, ObservableObject.prototype);
copy(SortedArraySet.prototype, GenericSet.prototype);
copy(SortedArraySet.prototype, ObservableObject.prototype);

@@ -28,0 +28,0 @@ SortedArraySet.prototype.isSorted = true;

68

sorted-array.js

@@ -5,7 +5,12 @@ "use strict";

var Shim = require("./shim");
var GenericCollection = require("./generic-collection");
var ObservableObject = require("./observable-object");
var ObservableRange = require("./observable-range");
var Iterator = require("./iterator");
var ObservableObject = require("pop-observe/observable-object");
var ObservableRange = require("pop-observe/observable-range");
var equalsOperator = require("pop-equals");
var compareOperator = require("pop-compare");
var hasOperator = require("pop-has");
var iterateOperator = require("pop-iterate");
var clear = require("pop-clear");
var swap = require("pop-swap/swap");
var copy = require("./copy");

@@ -22,5 +27,5 @@ function SortedArray(values, equals, compare, getDefault) {

}
this.contentEquals = equals || Object.equals;
this.contentCompare = compare || Object.compare;
this.getDefault = getDefault || Function.noop;
this.contentEquals = equals || equalsOperator;
this.contentCompare = compare || compareOperator;
this.getDefault = getDefault || noop;

@@ -34,5 +39,5 @@ this.length = 0;

Object.addEach(SortedArray.prototype, GenericCollection.prototype);
Object.addEach(SortedArray.prototype, ObservableObject.prototype);
Object.addEach(SortedArray.prototype, ObservableRange.prototype);
copy(SortedArray.prototype, GenericCollection.prototype);
copy(SortedArray.prototype, ObservableObject.prototype);
copy(SortedArray.prototype, ObservableRange.prototype);

@@ -112,5 +117,9 @@ SortedArray.prototype.isSorted = true;

SortedArray.prototype.has = function (value) {
var index = search(this.array, value, this.contentCompare);
return index >= 0 && this.contentEquals(this.array[index], value);
SortedArray.prototype.has = function (value, equals) {
if (equals) {
return hasOperator(this.array, value, equals);
} else {
var index = search(this.array, value, this.contentCompare);
return index >= 0 && this.contentEquals(this.array[index], value);
}
};

@@ -130,3 +139,3 @@

if (this.dispatchesRangeChanges) {
this.dispatchBeforeRangeChange([value], [], index);
this.dispatchRangeWillChange([value], [], index);
}

@@ -145,3 +154,3 @@ this.array.splice(index, 0, value);

if (this.dispatchesRangeChanges) {
this.dispatchBeforeRangeChange([], [value], index);
this.dispatchRangeWillChange([], [value], index);
}

@@ -184,7 +193,11 @@ this.array.splice(index, 1);

SortedArray.prototype.pop = function () {
return this.array.pop();
var value = this.array.pop();
this.length = this.array.length;
return value;
};
SortedArray.prototype.shift = function () {
return this.array.shift();
var value = this.array.shift();
this.length = this.array.length;
return value;
};

@@ -212,7 +225,8 @@

var minus = this.slice(index, index + length);
plus = plus || [];
if (this.dispatchesRangeChanges) {
this.dispatchBeforeRangeChange(plus, minus, index);
this.dispatchRangeWillChange(plus, minus, index);
}
this.array.splice(index, length);
this.addEach(plus);
swap(this.array, index, length, plus);
this.length += plus.length - length;
if (this.dispatchesRangeChanges) {

@@ -251,3 +265,3 @@ this.dispatchRangeChange(plus, minus, index);

SortedArray.prototype.one = function () {
return this.array.one();
return this.array[0];
};

@@ -259,6 +273,6 @@

minus = this.array.slice();
this.dispatchBeforeRangeChange([], minus, 0);
this.dispatchRangeWillChange([], minus, 0);
}
this.length = 0;
this.array.clear();
clear(this.array);
if (this.dispatchesRangeChanges) {

@@ -270,14 +284,14 @@ this.dispatchRangeChange([], minus, 0);

SortedArray.prototype.equals = function (that, equals) {
return this.array.equals(that, equals);
return equalsOperator(this.array, that, equals);
};
SortedArray.prototype.compare = function (that, compare) {
return this.array.compare(that, compare);
return compareOperator(this.array, that, compare);
};
SortedArray.prototype.iterate = function (start, stop, step) {
return new this.Iterator(this.array, start, stop, step);
return iterateOperator(this.array, start, stop, step);
};
SortedArray.prototype.Iterator = Iterator;
function noop() {}

16

sorted-map.js
"use strict";
var Shim = require("./shim");
var SortedSet = require("./sorted-set");
var GenericCollection = require("./generic-collection");
var GenericMap = require("./generic-map");
var ObservableObject = require("./observable-object");
var ObservableObject = require("pop-observe/observable-object");
var equalsOperator = require("pop-equals");
var compareOperator = require("pop-compare");
var copy = require("./copy");

@@ -15,4 +17,4 @@ module.exports = SortedMap;

}
equals = equals || Object.equals;
compare = compare || Object.compare;
equals = equals || equalsOperator;
compare = compare || compareOperator;
getDefault = getDefault || this.getDefault;

@@ -38,5 +40,5 @@ this.contentEquals = equals;

Object.addEach(SortedMap.prototype, GenericCollection.prototype);
Object.addEach(SortedMap.prototype, GenericMap.prototype);
Object.addEach(SortedMap.prototype, ObservableObject.prototype);
copy(SortedMap.prototype, GenericCollection.prototype);
copy(SortedMap.prototype, GenericMap.prototype);
copy(SortedMap.prototype, ObservableObject.prototype);

@@ -43,0 +45,0 @@ SortedMap.prototype.constructClone = function (values) {

54

sorted-set.js

@@ -5,9 +5,11 @@ "use strict";

var Shim = require("./shim");
var GenericCollection = require("./generic-collection");
var GenericSet = require("./generic-set");
var ObservableObject = require("./observable-object");
var ObservableRange = require("./observable-range");
var ObservableObject = require("pop-observe/observable-object");
var ObservableRange = require("pop-observe/observable-range");
var Iterator = require("./iterator");
var TreeLog = require("./tree-log");
var equalsOperator = require("pop-equals");
var compareOperator = require("pop-compare");
var copy = require("./copy");

@@ -18,5 +20,5 @@ function SortedSet(values, equals, compare, getDefault) {

}
this.contentEquals = equals || Object.equals;
this.contentCompare = compare || Object.compare;
this.getDefault = getDefault || Function.noop;
this.contentEquals = equals || equalsOperator;
this.contentCompare = compare || compareOperator;
this.getDefault = getDefault || noop;
this.root = null;

@@ -30,6 +32,6 @@ this.length = 0;

Object.addEach(SortedSet.prototype, GenericCollection.prototype);
Object.addEach(SortedSet.prototype, GenericSet.prototype);
Object.addEach(SortedSet.prototype, ObservableObject.prototype);
Object.addEach(SortedSet.prototype, ObservableRange.prototype);
copy(SortedSet.prototype, GenericCollection.prototype);
copy(SortedSet.prototype, GenericSet.prototype);
copy(SortedSet.prototype, ObservableObject.prototype);
copy(SortedSet.prototype, ObservableRange.prototype);

@@ -201,4 +203,7 @@ SortedSet.prototype.isSorted = true;

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

@@ -210,4 +215,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;
}
}

@@ -219,5 +227,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;

@@ -233,5 +239,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;
}
}

@@ -329,4 +337,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

@@ -762,1 +771,2 @@ SortedSet.prototype.splay = function (value) {

function noop() {}
observable-array.js
observable-map.js
observable-object.js
observable-range.js
shim-array.js
shim-function.js
shim-object.js
shim-regexp.js
shim.js
.travis.yml

Sorry, the diff of this file is not supported yet

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