montagejs / collections Goto Github PK
View Code? Open in Web Editor NEWThis package contains JavaScript implementations of common data structures with idiomatic interfaces.
Home Page: http://www.collectionsjs.com
License: Other
This package contains JavaScript implementations of common data structures with idiomatic interfaces.
Home Page: http://www.collectionsjs.com
License: Other
When array-changes:set uses the swap method, the popcorn demo does not load the details for the first movie. This bug does not occur when swap() is replaced with splice().
This is partly because the call to splice does not call the method in array-changes.js but instead calls it in montage/core/range-controller.js. This outside method currently avoids the Popcorn bug but should eventually be refactored.
Sorry for creating an issue. It's more like a question actually.
I would like to understand how to create redis-like sorted sets (let's call them RSS) with the collections
ones (CSS) since they are not the same. RSS also seem that it can't be done as Sorted Map since RSS require handling of non-unique scores.
As @antirez told sorted sets in Redis are backed by skip lists.
RSS seem to be like CSS containing [score, member]
arrays in order to cover commands like ZADD, ZCOUNT, ZRANGE, ZRANGEBYSCORE, ZREMRANGEBYRANK, ZREMRANGEBYSCORE, ZREVRANGE, ZREVRANGEBYSCORE.
But some commands (that accept only the member
argument) like ZINCRBY, ZRANK, ZREM, ZREVRANK, ZSCORE seem to require an additional map from member
to score
and operations like ZREM could be done only as:
// add [score, member]
var set = new SortedSet();
var map = new Map();
set.add([score, member]);
map.set(member, score);
// delete member
set.delete([map.get(member), member]);
map.delete(member);
Is there a better way for creating RSS with collections
?
If multiple, incomparable values are added to a sorted array, and subsequently removed, the sorted array should behave effectively like a plain array with push and pop. As yet, the search functions are returning indeterminate values and adding removing values from seemingly random positions.
See: montagejs/frb#13
A "set" collection does not dispatch a rangeChange when the "clear" method is used
I'm seeing this in node 0.11.13:
TypeError: Cannot redefine property: clear
at Function.defineProperty (native)
at define (/usr/local/lib/node_modules/nex-repository/node_modules/nex-github/node_modules/q/node_modules/collections/shim-array.js:57:12)
at Object.<anonymous> (/usr/local/lib/node_modules/nex-repository/node_modules/nex-github/node_modules/q/node_modules/collections/shim-array.js:275:1)
at Module._compile (module.js:449:26)
at Object.Module._extensions..js (module.js:467:10)
at Module.load (module.js:349:32)
at Function.Module._load (module.js:305:12)
at Module.require (module.js:357:17)
at require (module.js:373:17)
at Object.<anonymous> (/usr/local/lib/node_modules/nex-repository/node_modules/nex-github/node_modules/q/node_modules/collections/shim.js:2:13)'
// dispatch to each listener
listeners.slice().forEach(function (listener) {...}
it looks like it's creating an unnecessary shallow copy
@domenic requests map.on(eventName, listener)
instead of map.addMapChangeListener(listenerWithComplicatedLogicToFigureOutItWasAnAdd)
.
This is really two issue: one is that he’d like less verbose syntax.
Second, he’d prefer to have separate event listeners for addition and deletion, instead of having to infer whether the change is an add or delete based on the value.
I read in the docs about the events emitted by the Map:
collection.addMapChangeListener(listener, token, before);
But i cannot find the functionality of the token
and before
arguments. I looked in the tests and they are not being used, no mention in the docs...
Do they serve a purpose?
On line 98 in lru-set.js "this.dispatcheRangeChange([], [value], 0);"
should be "this.dispatchRangeChange([], [value], 0);"
For any type of collection I don't see any way to count the items stored within that collection... Is using .toArray().length
the suggested way? Am i missing something? If not maybe we should add this to all collections?
Although I think naming it Array
makes the most sense considering the naming convention used by the library, doesn't it break the modular nature of it by modifying a global prototype?
https://github.com/kriskowal/collections/blob/cdcbf349ca60014eb94ec9c978d263336eac667c/set.js#L15
if (!(this instanceof Set)) {
return new Set(values, options);
}
should be
if (!(this instanceof Set)) {
return new Set(values, equals, hash);
}
Create a directory with a markdown document for each interface, collection, and method, method + collection caveat
I am trying to sort values that are sometimes incomparable with each other. The data that I am sorting resembles a tree where
var _ = require('underscore')
var SortedArray = require('collections/sorted-array');
// x has y as one of its dependencies
var x = {
uuid: 'x',
dependsOn: ['y', 'k']
}
// y should be go before x as x depends on y
var y = {
uuid: 'y',
dependsOn: ['k']
}
// z depends on k and so k must come before z
var z = {
uuid: 'z',
dependsOn: ['k']
}
// k depends on nothing
var k = {
uuid: 'k',
dependsOn: []
};
function equal(a, b) {
return (a.uuid === b.uuid)
}
function compare(a, b) {
// if they have the same uuid; then they are the same
if (a.uuid === b.uuid) {
return 0
}
// if a depends on b, then a should be after b
for (var i = 0, len = a.dependsOn.length; i < len; i++) {
var dependsOn = a.dependsOn[i];
if (dependsOn === b.uuid) {
return 1
}
}
// if b depends on a, then b should be after a
for (var i = 0, len = b.dependsOn.length; i < len; i++) {
var dependsOn = b.dependsOn[i];
if (dependsOn === a.uuid) {
return -1
}
}
// this is the edge case,
// if neither a or b depends on each other, then they don't have relative ranking
return 0
}
// this is every possible permutation - they should all sort to the same orders
// expected order k, z, y, x or k, y, z, x or k, y, x, z
// because:
// k -> z as z depends on k
// k -> y as y depends on k
// no relative ranking between z and y as they don't depend on each other
// x depends on both y and k so x will come after them
var perms = [
[x, y, z, k],
[x, y, k, z],
[x, z, y, k],
[x, z, k, y],
[x, k, y, z],
[x, k, z, y],
[y, x, z, k],
[y, x, k, z],
[y, z, x, k],
[y, z, k, x],
[y, k, x, z],
[y, k, z, x],
[z, x, y, k],
[z, x, k, y],
[z, y, x, k],
[z, y, k, x],
[z, k, x, y],
[z, k, y, x],
[k, x, y, z],
[k, x, z, y],
[k, y, x, z],
[k, y, z, x],
[k, z, x, y],
[k, z, y, x],
]
perms.forEach(function(perm) {
var s = SortedArray(perm, equal, compare)
var p = _.pluck(s.toArray(), 'uuid')
console.log(p, _.isEqual(p, ['k', 'z', 'y', 'x']) || _.isEqual(p, ['k', 'y', 'z', 'x']) || _.isEqual(p, ['k', 'y', 'x', 'z']))
})
\\ -sorted array- -test-
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'x', 'z', 'y' ] false \\ x depends on y, so it should come after y
[ 'k', 'x', 'z', 'y' ] false \\ x depends on y, so it should come after y
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'x', 'z', 'y' ] false \\ x depends on y, so it should come after y
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'y', 'z', 'x' ] true
[ 'k', 'x', 'z', 'y' ] false \\ x depends on y, so it should come after y
[ 'k', 'y', 'x', 'z' ] true
[ 'k', 'y', 'x', 'z' ] true
The iterator callback is being invoked with undefined key and value.
Here is a script that reproduces the bug:
var SortedMap = require("collections/sorted-map");
var map = new SortedMap();
map.set("key1", "value1");
map.set("key2", "value2");
map.some(function(value, key) {
console.log(key, value);
});
Will output:
undefined undefined
undefined undefined
As the title says the line:
Object.addEach(List.prototype, RangeChanges.prototype);
is missing
SortedArraySet#length doesn't update when you .pop()
and .shift()
Here's an example from the Node REPL:
> var SortedArraySet = require('collections/sorted-array-set')
undefined
> var a = new SortedArraySet()
undefined
> a.add('foo')
true
> a.add('bar')
true
> a.length
2
> a.pop()
'foo'
> a.shift()
'bar'
> a.length
2
> a.length === a.array.length
false
> a
{ array: [],
contentEquals: [Function],
contentCompare: [Function],
getDefault: [Function],
length: 2 }
>
This project is really awesome, and the v2 branch is looking good with less intrusive monkey patching. 👍
Maybe once things get a bit more stable, it would be worth pulling some of the utilities into their own modules. The main benefit is version management. So you can bump major/minor/patch versions of, say, "fast-map" independently of all the other collections. The collections
can remain backwards-compatible as an entry point to the other modules (like you're already doing with weak map).
not a big issue, but is it possible to remove the www
in front of the hostname of www.collectionsjs.com
?
Is the reason because GitHub pages can use a CDN that way?
In the example below, elements in the set are identified as unique if the name
fields are equal. Subsequently, they are sorted by the instrument
field.
It is expected for SortedArraySet#find
to return the correct indexes corresponding to the names. However, starting index 2, find()
returns -1
.
It appears that the equals()
function is not getting called for all iterations (see log output below).
This works if both equals()
and compare()
functions are referring to the same fields.
var SortedArraySet = require('collections/sorted-array-set'),
set = new SortedArraySet([],
function (a, b ) {
console.log(a.name + ' equals ' + b.name + ' : ' + (a.name === b.name));
return a.name === b.name;
},
function (a, b) {
if (a.instrument > b.instrument) { return 1; }
else if (a.instrument < b.instrument) { return -1; }
else { return 0; }
});
describe('set', function () {
it('finds an element from the collection', function () {
set.push({ name: 'John', instrument: 'rhythm' });
set.push({ name: 'Paul', instrument: 'bass' });
set.push({ name: 'George', instrument: 'lead' });
set.push({ name: 'Ringo', instrument: 'drum kit' });
expect(set.find({ name: 'Paul' })).toBe(0);
expect(set.find({ name: 'Ringo' })).toBe(1);
expect(set.find({ name: 'George' })).toBe(2);
expect(set.find({ name: 'John' })).toBe(3);
});
});
Output
LOG LOG: 'Paul equals Paul : true'
LOG LOG: 'Paul equals Paul : true'
LOG LOG: 'Ringo equals Paul : false'
LOG LOG: 'Ringo equals Ringo : true'
LOG LOG: 'George equals Paul : false'
LOG LOG: 'George equals Ringo : false'
LOG LOG: 'John equals Paul : false'
LOG LOG: 'John equals Ringo : false'
set
✗ finds an element from the collection
Expected -1 to be 2.
Error: Expected -1 to be 2.
at null.<anonymous> (/tmp/2e18f5dfdaf9e610854903b5e4d05e71bee0ebac.browserify:46805:46 <- sortedArraySet.spec.js:22:0)
Expected -1 to be 3.
Error: Expected -1 to be 3.
at null.<anonymous> (/tmp/2e18f5dfdaf9e610854903b5e4d05e71bee0ebac.browserify:46806:46 <- sortedArraySet.spec.js:23:0)
I know this isn't a Collections issue but i thought i'd ask here first...
jshint will always create a warning on my sublime editor when requiring a struct, e.g:
var Map = require('collections/map');
The above will produce this lint error: Redefinition of 'Map'
I have the same with Set... are these reserved keywords or it's a jshint issue?
Hi,
We are in process of introducing a collections
module in the NodeJs core in the future versions of NodeJs
. Instead of building a one from scratch we are thinking to take one from community which in popular and prepare it for the core.
If you are interested and have no objections in considering your module to be a contender to be moved to core, then let us know we can proceed further.
The process of moving to core will be like:
Looking forward for your views
Regards
Depending on a combination of object extensibility, writability, and configurability, failing to install a thunk on that property might be indistinguishable from succeeding. Observing an immutable property should not throw an error.
Your current Map implementation has an add function that has the illogical (value, key) parameter ordering. I believe the ordering is wrong.
Unfortunately the API has been released as is so a change to the API without regression is not possible.
Your documentation (http://www.collectionsjs.com/method/add-value-key) mentions the "gotcha" ("that does not have an obvious reason to exist") but that doesn't help the casual user who just sees the main page (http://www.collectionsjs.com/map).
It took me a few hours today to realise that a bug in my code is because the add arguments are unusually ordered within your API.
add() and set() should have distinctive meaning for maps. Add should add a new element, set should refresh the value given for an existing key.
Raising this issue against your code instead of the docs but I believe a change is needed for both the docs and the API.
I suggest deprecating "add(value, key)", adding a temporary addKV(key, value) function and also warning the user about this in the docs with bold/red text.
I'm willing to help and make such changes to your API and or documentation.
Please let me know if I'm completely wrong and if there was an engineering decision behind your unusual ordering.
Thanks!
An empty, newly-created FastSet claims to contain all single-character strings.
$ npm install collections
And run the following test code:
var FastSet = require('collections/fast-set');
var assert = require('assert');
var s = new FastSet();
assert.equal(s.has('hello'), false); // succeeds
assert.equal(s.has('h'), false); // fails, and seems to fail for any single-character string
assert.deepEqual(s.buckets.getDefault('hello').toArray(), ['h', 'e', 'l', 'l', 'o']); // succeeds
This issue is not related to code, but the documentation on www.collectionsjs.com is not visible due to the styles.css file.
https://github.com/montagejs/collections/blob/master/listen/property-changes.js#L169-174
If the listener doesn't implement any of the delegate methods, and isn't a function you get the ambiguous error Uncaught TypeError: Object #<Object> has no method 'call'
Would be nice to give a better error.
What do you think about dispatching only one rangeChange event when using the "addEach" method on a "set" collection instead of dispatching one event per item added ?
When SortedSet.findLeastGreaterThan(value) is used, and value is not in the tree, the behavior is very odd.
Same issue applies to the other variants findGreatestLessThan and findGreatestLessOrEqualThan.
Please integrate with bower for those wanting to use this on a browser
I notice you "shim" a bunch of things onto core prototypes, e.g. Object.addEach. Is that really necessary? Isn't it taboo to modify Object.prototype?
Can you at least point me to the ECMAScript standard that is planning to implement Object.addEach and all its friends? I can't find it.
I want to use your library, but honestly I get a bad feeling about all this modification of core prototypes.
Hello
var set = new Set();
set.add(1);
set.add(2);
set.add(3);
set.add(4);
var iterator = set.iterate ? set.iterate() : set.iterator();
var k = 0;
while (true) {
next = iterator.next();
console.log(next);
if (k === 0) {
set.delete(2);
set.delete(1);
set.delete(0);
}
k++;
}
set.add(1, 1);
this code prints "1; 3; 4" in FF 18 with "native" Set and
"1; 2; 3; 4" with your code
could you please document how your iteration works with modification
I had an issue (verbling/assetflow#10) in one of my libraries, were a developer has conflict problems because Collections alters the Array.prototype. I am quoting @Amptron:
Collections JS adds some methods to the Array.prototype. Since this added functionality doesn't seem to be an explicit intention of assetflow, it seems weird to have it as a dependency.
Specifically, we're using Sugar JS and Collection's Array.find method collides with Sugar's Array.find which is an unintended consequence of using assetflow.
assert = require('assert');
assert.equal(Array.prototype.find, void 0, "Prototype modified before assetflow");
require('assetflow');
assert.equal(Array.prototype.find, void 0, "Prototype modified after assetflow");
Output: Prototype modified after assetflow
What do you suggest the best course of action should be?
Hi. There seem to be circular dependencies between "generic-collection.js" and "shim-array.js": both require
each other, and apparently node.js does not handle this well. This seems to be the cause for the command
$ node demo/iterator-demo.js
to fail with the following error:
/home/brian/src/GitHub/collections/shim-array.js:61
define("addEach", GenericCollection.prototype.addEach);
^
TypeError: Cannot read property 'addEach' of undefined
at Object.<anonymous> (/home/brian/src/GitHub/collections/shim-array.js:61:46)
at Module._compile (module.js:449:26)
at Object.Module._extensions..js (module.js:467:10)
at Module.load (module.js:356:32)
at Function.Module._load (module.js:312:12)
at Module.require (module.js:362:17)
at require (module.js:378:17)
at Object.<anonymous> (/home/brian/src/GitHub/collections/generic-collection.js:3:1)
at Module._compile (module.js:449:26)
at Object.Module._extensions..js (module.js:467:10)
It seems the Array shim needs the methods on GenericCollection to be defined, but GenericCollection itself needs the Array shim in place to provide them. Node gives us a GenericCollection object with nothing defined on it until it completes, causing the error.
Presumably, this error would happen even if "iterator-demo.js" and "iterator.js" were removed, and I'm not sure why it hasn't been reported yet. But please don't remove "iterator.js" from the library, as it's the primary reason I currently want "collections".
HTH,
Brian
I'm evaluating whether or not to use this library for a project. My project may use Secure ECMAScript (SES) in the future, meaning I cannot modify any built-in prototypes. Secure ECMAScript enforces object-capability security by locking down all built-in objects (Object, Array, etc) so that they can't be modified.
Does your documentation explain how to use collections without modifying any built-in prototypes? I looked around on collectionsjs.com and only found references to how your code modifies prototypes sometimes, but I didn't find anything explaining how to explicitly avoid modifications.
Thanks in advance.
> require('collections');
Error: Cannot find module 'collections'
I think package.json needs to be updated with something like:
"main": "./collections.js"
new List([1]).some(function () { return "hello" });
should return true
, but returns "hello"
The ES6 spec has changed significantly and for the better regarding iterators since time of writing the iterator module.
https://github.com/montagejs/collections/blob/master/iterator.js
Iterators now return “iteration” objects with value
and done
. We may extend this to include index
for array iterations and node
otherwise, or simply elect to reuse nodes as iterations for lists.
Also, iterator()
as a method is a SpiderMonkey artifact we can ignore. We do not have access to an iterator symbol, so we can just use the iterate()
duck for now.
Instead of using a native object to store items, you could point the collection to an alternative data source instead. Like a memory store like this one...
http://jxcore.com/docs/jxcore-store.html
var List = require("collections/list");
List.source = jxcore.store;
var list = new List([1,2,3]);
This way, all the values are stored in the jxcore.store but accessed via the list collection. Almost like an adapter/wrapper pattern.
Hi, We are developing a huge applications with different modules, e.g. a core module which has no ui, doing background actions, only. The UI layer is build with angular. The sequence of loading those modules is core first - requires collections.js, then the other modules gets loaded.
We are using browserify to glue each module and their dependencies together. The first time I include collections.js the UI module stops working - Angular does not even bootstrap this module.
Failed to instantiate module app.ui due to:
TypeError: Can't add property $$hashKey, object is not extensible
When I remove collections.js it is working again.
I guess this has something to do with collections.js Object shim?
I'm de/serializing data structures as JSON. How would these alternate collections be used with JSON documents? For instance, if I would choose the enhanced array how would a JSON deserializer know that it should instantiate the enhanced array versus the standard array?
I'm sure this is just due to my limited knowledge of JavaScript, but the collections by themselves are not standalone.
Within the head of my html file, I include a js file that has the following line of code (as in the demo):
var SortedMap = require("jsCollections/sorted-map");
When the page loads, I get the following error on the console:
"ReferenceError: Can't find variable: require "
So, I tried different js "loaders" such as require.js and modules.js (this one from chiron). I also tried loading each "require" js file from collections in the html head in a particular order. For all of these efforts, I continue to get an error.
For modules.js, I add the following to the html head:
script src="modules.js?./myjsfile.js"
This results in the following errors:
TypeError: '[object Object]' is not a constructor (evaluating 'new SortedMap()') modules.js:445
(anonymous function) modules.js:445
(anonymous function) modules.js:349
(anonymous function) modules.js:91
(anonymous function) modules.js:493
TypeError: '[object Object]' is not a constructor (evaluating 'new SortedMap()')
If I add each require in the html head like this:
script src="jquery.js"
script src="jsCollections/sorted-map.js"
script src="jsCollections/sorted-set.js"
script src="jsCollections/reducible.js"
script src="jsCollections/operators.js"
script src="jsCollections/tree-log.js"
script src="jsCollections/abstract-map.js"
script src="myjsfile.js"
I get the following errors on the console:
ReferenceError: Can't find variable: require sorted-map.js:2
ReferenceError: Can't find variable: module sorted-set.js:2
ReferenceError: Can't find variable: module reducible.js:2
ReferenceError: Can't find variable: exports operators.js:9
ReferenceError: Can't find variable: module tree-log.js:2
ReferenceError: Can't find variable: module abstract-map.js:2
ReferenceError: Can't find variable: require myjsfile.js:1
If it helps, I'm using jquery which I load first in the html head and I'm using a webkit browser compiled with QT for Linux (Ubuntu).
I would appreciate any help that would allow me to load and run the js collections. I suppose that I need to add a js loader. I would prefer this loader to be of a minimal file size.
If the issue is not clear please let me know so that I can clarify it. As a recap, I cannot run the js collections just by themselves because of the require, module, and exports functions/variables. I need to understand what else is needed to run the js collections.
Thanks in advance.
from latest ES 6 draft, i see, that Map from ES6 should be iterated in insertion order;
test-case:
var map = new Map();
map.set(-1, 0);
map.set(1, 1);
map.set(2, 2);
map.set(3, 3);
map.forEach(function (value, key) {
console.log(key + ': ' + value);
});
/* under node.js:
1: 1
2: 2
3: 3
-1: 0
*/
should be:
-1: 0
1: 1
2: 2
3: 3
It should be easier to look up what collections implement a method and what methods are implemented by a collection. Create a micro-site that makes it easy to browse in both dimensions.
Repository http://github.com/kriskowal/collections.git (git)
Homepage http://github.com/kriskowal/collections
Bugs http://github.com/kriskowal/collections/issues
However, kriskowal doesn't have a collections repo (anymore?).
in property-changes.js, PropertyChanges.prototype.dispatchOwnPropertyChange:
var changeName = (beforeChange ? "Will" : "") + "Change";
var genericHandlerName = "handleProperty" + changeName;
var propertyName = String(key);
propertyName = propertyName && propertyName[0].toUpperCase() + propertyName.slice(1);
var specificHandlerName = "handle" + propertyName + changeName;
is expensive and repeated all the time, wasting time and created garbage, a cache should be built over time
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.