qiao / fingertree.js Goto Github PK
View Code? Open in Web Editor NEWImplementation of Finger Tree in JavaScript.
fingertree.js's People
Contributors
Stargazers
Watchers
fingertree.js's Issues
Errors handling laziness in Deep.concat() and app3()
Deep.concat and app3() both do instanceof checks on their arguments and then access properties in them. You need to force the arguments if they're lazy, otherwise they fail the instanceof checks and default case in app3() fails on a property access.
For my CoffeeScript version, I just added a force method to FingerTree that returns this. Then, at the top of Deep.concat() and app3(), I just reassigned the arguments to be their forced versions.
incorrect behavior when implementing simple priority queue
Here is my max-priority queue test.
It should sort [1,3,2,9,7] into [9,7,3,2,1] and print it out.
var FingerTree = require('fingertree');
// Create a finger-tree with a custom measurer.
var measurer = {
identity: function () {
return -Infinity;
},
measure: function (x) {
return x;
},
sum: function (a, b) {
return Math.max(a, b);
}
};
var maxTree = FingerTree.fromArray([1, 3, 2, 9, 7], measurer);
var i = 1;
while(!maxTree.isEmpty()) {
//console.log("tree: ",JSON.stringify(maxTree.toJSON(),null,2));
var split = maxTree.splitTree(function(measure) {
return measure>=maxTree.measure()
},-Infinity);
console.log(i+") "+split.mid+"; max:"+maxTree.measure()+" left:"+split.left.measure()+" right:"+split.right.measure());
//console.log("left: ",JSON.stringify(split.left.toJSON(),null,2));
//console.log("right: ",JSON.stringify(split.right.toJSON(),null,2));
maxTree = split.left.concat(split.right)
i++;
}But it prints
1) 9; max:9 left:3 right:7
2) 7; max:7 left:3 right:2
3) 3; max:3 left:1 right:2
4) 2; max:2 left:1 right:2
5) 2; max:2 left:1 right:-Infinity
6) 1; max:1 left:-Infinity right:-Infinity
So I consider there is some bug in splitTree when item actually does not get removed from left/right subtree. You can uncomment console.log and you will see that after removing 7 the element 2 is both in right subtree and left subtree. Therefore it is printed twice, while source array contained only single element "2".
Could you please comment what I'm doing wrong??
Regards, mikhail.
bug in `nodes`
It there a reason why it is assumed that xs.length <= 8 here? There is no such assumption in Hinze and Paterson.
const FingerTree = require( 'fingertree' ) ;
let X = FingerTree.fromArray( [ ] ) ;
for ( let i = 0 ; i < ( 4 * 4 + 4 ) ; ++i ) X = X.addLast( i ) ;
let Y = FingerTree.fromArray( [ ] ) ;
for ( let i = 0 ; i < ( 4 * 4 + 4 ) ; ++i ) Y = Y.addFirst( i ) ;
X.concat( Y ).measure( )
Error: invalid number of nodes
at nodes (/home/aureooms/node_modules/fingertree/src/fingertree.js:994:22)
at DelayedFingerTree.thunk (/home/aureooms/node_modules/fingertree/src/fingertree.js:963:35)
at DelayedFingerTree.force (/home/aureooms/node_modules/fingertree/src/fingertree.js:794:24)
at DelayedFingerTree.measure (/home/aureooms/node_modules/fingertree/src/fingertree.js:810:17)
at FingerTree.Deep.measure (/home/aureooms/node_modules/fingertree/src/fingertree.js:576:52)
at DelayedFingerTree.measure (/home/aureooms/node_modules/fingertree/src/fingertree.js:810:25)
at FingerTree.Deep.measure (/home/aureooms/node_modules/fingertree/src/fingertree.js:576:52)
at repl:1:15
at REPLServer.defaultEval (repl.js:164:27)
at bound (domain.js:250:14)Method missing: DelayedFingerTree.toArray()
DelayedFingerTree.prototype.toArray = function() {
return this.force().toArray();
}
DealyedFingerTree missing some methods
It needs concat, takeUntil, and dropUntil.
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.