Socket
Socket
Sign inDemoInstall

collections

Package Overview
Dependencies
Maintainers
2
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 0.0.2 to 0.0.3

demo/all.js
demo/array-demo.js
demo/hash-demo.js
demo/iterator-demo.js
demo/list-demo.js
demo/log-demo.js
demo/map-demo.js
demo/object-demo.js
demo/observable-array-demo.js
demo/observable-object-demo.js
demo/set-demo.js
demo/sorted-map-demo.js
demo/sorted-set-demo.js
demo/weak-map-demo.js
observable-array.js
observable-object.js
spec/observable-array-spec.js
spec/observable-object-spec.js

40

array.js

@@ -18,7 +18,12 @@

Array.from = function (values) {
var array = [];
array.addEach(values);
return array;
};
Array.prototype.constructClone = function constructClone(values) {
var clone = new this.constructor();
if (values) {
values.forEach(this.push, this);
}
clone.addEach(values);
return clone;
};

@@ -41,6 +46,4 @@

Array.prototype.add = function (value, equals) {
if (!this.has(value, equals)) {
this.push(value);
}
Array.prototype.add = function (value) {
this.push(value);
};

@@ -57,2 +60,3 @@

equals = equals || this.contentEquals || Object.equals || Operators.equals;
console.log(equals);
for (var index = 0; index < this.length; index++) {

@@ -96,2 +100,4 @@ if (index in this && equals(this[index], value)) {

Array.prototype.sorted = Reducible.sorted;
Array.prototype.reversed = Reducible.reversed;
Array.prototype.clone = Reducible.clone;

@@ -119,4 +125,2 @@ Array.prototype.count = function () {

Array.prototype.clone = Reducible.clone;
Array.prototype.wipe = function () {

@@ -127,1 +131,19 @@ this.length = 0;

Array.prototype.iterate = function (start, end) {
return new ArrayIterator(this, start, end);
};
function ArrayIterator(array, start, end) {
this.array = array;
this.start = start == null ? 0 : start;
this.end = end;
};
ArrayIterator.prototype.next = function () {
if (this.start === (this.end == null ? this.array.length : this.end)) {
throw StopIteration;
} else {
return this.array[this.start++];
}
};

77

list.js

@@ -20,7 +20,8 @@

List.prototype.find = function find(value) {
List.prototype.find = function find(value, equals) {
equals = equals || this.contentEquals;
var head = this.head;
var at = head.next;
while (at !== head) {
if (this.contentEquals(at.value, value)) {
if (equals(at.value, value)) {
return at;

@@ -32,7 +33,8 @@ }

List.prototype.findLast = function (value) {
List.prototype.findLast = function (value, equals) {
equals = equals || this.contentEquals;
var head = this.head;
var at = head.prev;
while (at !== head) {
if (this.contentEquals(at.value, value)) {
if (equals(at.value, value)) {
return at;

@@ -44,8 +46,8 @@ }

List.prototype.has = function has(value) {
return !!this.find(value);
List.prototype.has = function has(value, equals) {
return !!this.find(value, equals);
};
List.prototype.get = function get(value) {
var found = this.find(value);
List.prototype.get = function get(value, equals) {
var found = this.find(value, equals);
if (found) {

@@ -61,4 +63,4 @@ return found.value;

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

@@ -121,11 +123,45 @@ found['delete']();

// an internal utility for coercing index offsets to nodes
List.prototype.scan = function (at, alt) {
var head = this.head;
if (typeof at === "number") {
var count = at;
if (count >= 0) {
at = head.next;
while (count) {
count--;
at = at.next;
if (at == head) {
break;
}
}
} else {
at = head;
while (count < 0) {
count++;
at = at.prev;
if (at == head) {
break;
}
}
}
return at;
} else {
return at || alt;
}
};
// at and end may both be positive or negative numbers (in which cases they
// correspond to numeric indicies, or nodes)
List.prototype.slice = function (at, end) {
var sliced = [];
var head = this.head;
at = at || head.next;
end = end || head;
while (at !== end) {
at = this.scan(at, head.next);
end = this.scan(end, head);
while (at !== end && at !== head) {
sliced.push(at.value);
at = at.next;
}
return sliced;

@@ -140,3 +176,3 @@ };

var swapped = [];
at = at || this.head.next;
at = this.scan(at, this.head.next);
while (length--) {

@@ -156,2 +192,13 @@ swapped.push(at.value);

List.prototype.reverse = function () {
var at = this.head;
do {
var temp = at.next;
at.next = at.prev;
at.prev = temp;
at = at.next;
} while (at !== this.head);
return this;
};
// TODO account for missing basis argument

@@ -200,2 +247,3 @@ List.prototype.reduce = function (callback, basis /*, thisp*/) {

List.prototype.sorted = Reducible.sorted;
List.prototype.reversed = Reducible.reversed;
List.prototype.clone = Reducible.clone;

@@ -219,3 +267,2 @@

List.prototype.one = function one() {

@@ -222,0 +269,0 @@ if (this.head === this.head.next) {

3

operators.js

@@ -39,2 +39,5 @@

}
if (typeof a !== typeof b) {
return 0;
}
return a > b ? 1 : a < b ? -1 : 0;

@@ -41,0 +44,0 @@ };

17

package.json
{
"name": "collections",
"version": "0.0.2",
"version": "0.0.3",
"description": "data structures with idiomatic JavaScript collection interfaces",

@@ -8,8 +8,9 @@ "homepage": "http://github.com/kriskowal/collections",

"keywords": [
"collections",
"data structures",
"observable",
"list",
"set",
"map",
"set",
"splay",
"tree",
"data structures",
"collections"
"splay"
],

@@ -31,3 +32,5 @@ "bugs": {

"dependencies": {},
"devDependencies": {}
"devDependencies": {
"jasmine-node": "*"
}
}

229

README.md

@@ -5,3 +5,4 @@

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

@@ -41,2 +42,19 @@ - `List(values, equals)`: an ordered collection of values with fast

traversal interface.
- `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 `array-shim` module shims EcmaScript 5 methods onto the array
prototype if they are not natively implemented. The
`observable-array` module provides methods for watching shallow
content changes and length property changes provided that the
developer is willing to degrade the performance of mutation
functions for *the particular observed array*. Observability does
not degrade the performance of mutations for non-observed arrays.
- `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. The
`observable-object` module provides methods for observing changes to
owned properties using getters and setters.

@@ -93,6 +111,6 @@ For all of these constructors, the argument `values` is an optional

Where these methods coincide with the specification of an existing
method of Array, Array is noted as an implementation. `Array*` refers
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
opposed to the `Object.prototype`. `Object+` in turn refers to methods
shimmed on the object constructor by the `object` module. These

@@ -104,6 +122,6 @@ functions accept the object as the first argument instead of the `this`

key exists.
- `has(value, opt_equals)`: (List, Set, SortedSet, Array*, Object*)
- `has(value, opt_equals)`: (List, Set, SortedSet, Array+, Object+)
whether a value exists. collection. This is slow for list
(linear), but fast (logarithmic) for Set and SortedSet.
- `get(key)`: (Map, SortedMap, WeakMap, Array*, Object*) the value for
- `get(key)`: (Map, SortedMap, WeakMap, Array+, Object+) the value for
a key. If a Map or SortedMap lacks a key, returns

@@ -113,22 +131,22 @@ `getDefault(key)`.

- `get(value)`: (List, Set, SortedSet) gets the equivalent value, or
falls back to `getDefault(value).
falls back to `getDefault(value)`.
- `getDefault(key)`: (List, Set, SortedSet) returns undefined.
- `set(key, value)`: (Map, SortedMap, WeakMap, Array*, Object*) sets
- `set(key, value)`: (Map, SortedMap, WeakMap, Array+, Object+) sets
the value for a key.
- `add(value)`: (List, Set, SortedSet) adds a value. Sets silently
drop the value if an equivalent value already exists.
- `add(value, key)`: (Map, SortedMap, Array*) sets the value for a
- `add(value, key)`: (Map, SortedMap, Array+) sets the value for a
key, convenient in conjunction with `forEach` due to the callback
argument order.
- `addEach(values)`: (List, Set, Map, SortedSet, SortedMap, Array*)
- `addEach(values)`: (List, Set, Map, SortedSet, SortedMap, Array+)
adds all values or key value pairs to this collection. Works for
arrays and objects as well as any other collection.
- `delete(key)`: (Map, SortedMap, WeakMap, Array*) deletes the value
- `delete(key)`: (Map, SortedMap, WeakMap, Array+) deletes the value
for a given key. Returns whether the key was found.
- `delete(value)`: (List, Set, SortedSet) deletes a value. Returns
whether the value was found.
- `find(value, opt_equals)`: (List, SortedSet, Array*) finds a value.
- `find(value, opt_equals)`: (List, SortedSet, Array+) finds a value.
For List and SortedSet, returns the node at which the value was
found. For SortedSet, the optional `equals` argument is ignored.
- `findLast(value, opt_equals)`: (List, Array*) finds the last
- `findLast(value, opt_equals)`: (List, Array+) finds the last
equivalent value, returning the node at which the value was found.

@@ -151,8 +169,37 @@ - `findLeast()`: (SortedSet) finds the smallest value, returning the

- `unshift(...values)`: (Array, List)
- `slice(start, end)`: (Array, List)
- `splice(start, length, ...values)`: (Array, List)
- `swap(start, length, values)`: (List, Array*) performs a splice
- `slice(start, end)`: (Array, List) returns an array of the values
contained in the half-open interval [start, end), that is, including
the start and excluding the end. For lists and arrays, both terms
may be numeric positive or negative indicies. For a list, either
term may be a node.
- `splice(start, length, ...values)`: (Array, List) Works as with an
array, but for a list, the start may be an index or a node.
- `swap(start, length, values)`: (List, Array+) performs a splice
without variadic arguments.
- `wipe()`: (List, Set, Map, SortedSet, SortedMap, Array*, Object*)
- `wipe()`: (List, Set, Map, SortedSet, SortedMap, Array+, Object+)
Deletes the all values.
- `sort(opt_compare)`: (Array) sorts a collection in place. The
comparator by only be a function. The default comparator coerces
unlike types rather than fail to compare.
- `sorted(opt_compare, opt_by, opt_order)`: (List, Set, Map,
SortedSet, SortedMap, Array+) returns a sorted version of the
collection as an array. Of map-like objects, only the values are
produced. Accepts an optional comparator, relation, and order. The
comparator may be a function that compares two arguments returning a
number relative to zero indicating the direction of the comparison,
where zero means either equal or incomparable. The comparator may
alternately be an object with `{compare, by}` properties. The
default comparator is `Object.compare` if shimmed by the `object`
module, or the simple `compare` function provided by the `operators`
module which delegates polymorphically to `compare` methods of
either operand, or falls back to `>` and `<` but only for like
types. The `by` relation returns a mapped value for a value in the
collection on by which to compare values. `sorted` uses the `by` to
compute the mapping exactly once, instead of once or twice as can
happen in the course of sorting. The optional order property can be
specified as `-1` for descending order, defaults to `1` for
ascending, and `0` results in a stable sort, changing nothing.
- `reverse()`: (Array, List) reverses a collection in place.
- `reversed()`: (Array, List) returns a collection of the same type
with this collection's contents in reverse order.
- `concat(...iterables)`: (Array, Iterator, List, Set, Map, SortedSet,

@@ -167,3 +214,3 @@ SortedMap) Produces a new collection of the same type containing all

- `keys()`: (Map, SortedMap, Object) returns an array of the keys
- `values()`: (Map, SortedMap, Object*) returns an array of the values
- `values()`: (Map, SortedMap, Object+) returns an array of the values
- `items()`: (Map, SortedMap, Object) returns an array of `[key, value]`

@@ -176,8 +223,12 @@ pairs for each item

- `forEach(callback(value, key, object, depth), thisp)`: (Array,
Iterator, List, Set, Map, SortedSet, SortedMap, Object*)
Iterator, List, Set, Map, SortedSet, SortedMap, Object+) 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.
- `map(callback(value, key, object, depth), thisp)`: (Array, Iterator,
List, Set, Map, SortedSet, SortedMap, Object*)
List, Set, Map, SortedSet, SortedMap, Object+)
- `toArray()`: (Iterator, List, Set, Map, SortedSet, SortedMap,
Array*)
- `toObject()`: (Iterator, Map, SortedMap, Array*) converts any
Array+)
- `toObject()`: (Iterator, Map, SortedMap, Array+) converts any
collection to an object, treating this collection as a map-like

@@ -195,30 +246,30 @@ object. Array is like a map from index to value.

Iterators stop consuming after the first success.
- `any()`: (Iterator, List, Set, Map, SortedSet, SortedMap, Array*)
- `any()`: (Iterator, List, Set, Map, SortedSet, SortedMap, Array+)
whether any value is truthy
- `all()`: (Iterator, List, Set, Map, SortedSet, SortedMap, Array*)
- `all()`: (Iterator, List, Set, Map, SortedSet, SortedMap, Array+)
whether all values are truthy
- `min()`: (Iterator, List, Set, Map, SortedSet, SortedMap, Array*)
- `min()`: (Iterator, List, Set, Map, SortedSet, SortedMap, Array+)
the smallest value. This is fast for sorted collections
(logarithic), but slow for everything else (linear).
- `max()`: (Iterator, List, Set, Map, SortedSet, SortedMap, Array*)
- `max()`: (Iterator, List, Set, Map, SortedSet, SortedMap, Array+)
the largest value. This is fast for sorted collections
(logarithic), but slow for everything else (linear).
- `one()`: (List, SortedSet, Array*) any single value, or throws an
- `one()`: (List, SortedSet, Array+) any single value, or throws an
exception if there are no values. This is very fast (constant) for
all collections. For a sorted set, the value is not deterministic.
- `only()`: (List, SortedSet, Array*) the one and only value, or
- `only()`: (List, SortedSet, Array+) the one and only value, or
throws an exception if there are no values or more than one value.
- `count()`: (List, Set, Map, SortedSet, SortedMap, Array*)
- `sum()`: (Iterator, List, Set, Map, SortedSet, SortedMap, Array*)
- `count()`: (List, Set, Map, SortedSet, SortedMap, Array+)
- `sum()`: (Iterator, List, Set, Map, SortedSet, SortedMap, Array+)
- `average()`: (Iterator, List, Set, Map, SortedSet, SortedMap,
Array*)
Array+)
- `flatten()`: (Iterator, List, Set, Map, SortedSet, SortedMap,
Array*)
Array+)
- `zip(...collections)`: (List, Set, Map, SortedSet, SortedMap,
Array*)
Array+)
- `enuemrate(zero)`: (Iterator, TODO List, Set, Map, SortedSet,
SortedMap, Array*)
- `sorted(compare)`: (List, Set, Map, Array*)
- `clone(depth, memo)`: (List, Set, Map, SortedSet, SortedMap, Array*,
Object*)
SortedMap, Array+)
- `sorted(compare)`: (List, Set, Map, Array+)
- `clone(depth, memo)`: (List, Set, Map, SortedSet, SortedMap, Array+,
Object+)
replicates the collection. If `Object.clone` is shimmed, clones the

@@ -229,3 +280,3 @@ values deeply, to the specified depth, using the given memo to

- `constructClone(values)`: (Iterator, List, Set, Map, SortedSet,
SortedMap, Array*) replicates a collection shallowly. This is used
SortedMap, Array+) replicates a collection shallowly. This is used
by each `clone` implementation to create a new collection of the

@@ -235,9 +286,16 @@ same type, with the same options (`equals`, `compare`, `hash`

more general `clone` method.
- `equals(that)`: (List, Set, Array*, TODO SortedSet, Map, SortedMap)
- `compare(that)`: (Object*, TODO)
- `iterate()`: (List, Set, SortedSet, SortedMap, TODO Array*)
- `iterate(start, end)`: (SortedSet, TODO List) 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.
- `equals(that)`: (List, Set, Array+, TODO SortedSet, Map, SortedMap)
- `compare(that)`: (Object+, TODO)
- `iterate()`: (List, Set, SortedSet, SortedMap, Array+)
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.
- `iterate(start, end)`: (Array+) returns an iterator for all values
at indicies in the half-open interval [start, end), that is, greater
than start, and less than end.
- `iterate(start, end)`: (SortedSet) 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.
- `log(charmap, stringify)`: (Set, Map, SortedSet) writes a tree

@@ -248,2 +306,3 @@ describing the internal state of the data structure to the console.

### Iterator

@@ -260,2 +319,3 @@

### Iterator utilities

@@ -273,2 +333,58 @@

### Observers
Listen for individual property changes on an object. The listener may
be a function or a delegate.
- `Object.addOwnPropertyChangeListener(object, key, listener, beforeChange)`
- `Object.removeOwnPropertyChangeListener(object, key, listener, beforeChange)`
- `Object.addBeforeOwnPropertyChangeListener(object, key, listener)`
- `Object.removeBeforeOwnPropertyChangeListener(object, key, listener)`
The arguments to the listener are `(value, key, object)`, much like a
`forEach` callback. The `this` within the listener is the listener
object itself. The dispatch method must be one of these names, favoring
the most specific provided.
- `handle` + key (TwoHump) + (`Change` or `WillChange` before change),
for example, `handleFooWillChange` for `foo`.
- `handleOwnPropertyChange` or `handleOwnPropertyWillChange` before
change
- `handleEvent`
- function
Listen for ranged content changes on arrays. The location of the change
is where the given arrays of content are removed and added. For
unordered collections like sets, the location would not be defined.
Content changes are not yet implemented for other collections.
- `array.addContentChangeListener(listener, beforeChange)`
- `array.removeContentChangeListener(listener, beforeChange)`
- `array.addBeforeContentChangeListener(listener)`
- `array.removeBeforeContentChangeListener(listener)`
The arguments to the listener are `(plus, minus, at)`, which are arrays
of the added and removed values, and optionally the location of the
change for ordered collections (lists, arrays). For a list, the
position is denoted by a node. The dispatch method must be one of these
names, favoring the most specific provided.
- `handleContentChange` or `handleContentWillChange` if before change
- `handleEvent`
- function
Listen for content changes from each position within an array, including
changes to and from undefined. Content changes must be emitted by
method calls on an array, so use `array.set(index, value)` instead of
`array[index] = value`.
- `array.addEachContentChangeListener(listener, beforeChange)`
- `array.removeEachContentChangeListener(listener, beforeChange)`
- `array.addBeforeEachContentChangeListener(listener)`
- `array.removeBeforeEachContentChangeListener(listener)`
The listener is a listener as for property changes.
## List

@@ -286,2 +402,3 @@

## Set and Map

@@ -310,2 +427,3 @@

## Sorted Set and Sorted Map

@@ -428,3 +546,4 @@

- docs
- shallow change dispatch and listeners
- shallow change dispatch and listeners for all collections (needed:
List, Set, SortedSet)
- alternative module systems song and dance

@@ -440,4 +559,8 @@ - optional new on constructors

More collections
More possible collections
- lru-set (least recently used cache)
- lru-map
- arc-set (adaptive replacement cache)
- arc-map
- sorted-list (sorted, can contain duplicates, perhaps backed by splay

@@ -459,18 +582,4 @@ tree with relaxation on the uniqueness invariant)

trie)
- lru-set (least recently used cache)
- lru-map
- arc-set (adaptive replacement cache)
- arc-map
Consolidate shims from ES5-Shim and elsewhere
- weak-map-shim
- object-shim
- object-sham
- array-shim
- array-sham
- date-shim
- array heap implementation
- binary heap implementation

4

reducible.js

@@ -206,2 +206,6 @@

Reducible.reversed = function () {
return this.constructClone(this).reverse();
};
Reducible.clone = function (depth, memo) {

@@ -208,0 +212,0 @@ if (depth === undefined) {

demos.js
hash-demo.js
iterator-demo.js
list-demo.js
log-demo.js
map-demo.js
object-demo.js
set-demo.js
sorted-map-demo.js
sorted-set-demo.js
weak-map-demo.js
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