Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

algorithmic

Package Overview
Dependencies
Maintainers
1
Versions
8
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

algorithmic - npm Package Compare versions

Comparing version 0.0.6 to 0.0.7

lib/getSubsetsRecursion.js

15

lib/atoi.js

@@ -6,13 +6,8 @@ // Generated by CoffeeScript 1.4.0

atoi = function(string) {
var array, character, digit, number, _i, _len;
array = string.split('');
var character, number, _i, _len, _ref;
number = 0;
for (_i = 0, _len = array.length; _i < _len; _i++) {
character = array[_i];
number *= 10;
digit = character - '0';
if (digit < 0 && digit > 9) {
return null;
}
number += digit;
_ref = string.split('');
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
character = _ref[_i];
number = number * 10 + (character - '0');
}

@@ -19,0 +14,0 @@ return number;

2

lib/BitArray.js

@@ -28,3 +28,3 @@ // Generated by CoffeeScript 1.4.0

_results = [];
for (i = _i = 0, _ref = size >> 5; 0 <= _ref ? _i <= _ref : _i >= _ref; i = 0 <= _ref ? ++_i : --_i) {
for (i = _i = 1, _ref = (size - 1 >> 5) + 1; _i <= _ref; i = _i += 1) {
_results.push(0);

@@ -31,0 +31,0 @@ }

3

lib/createMinimalBstFromSortedArray.js

@@ -18,4 +18,3 @@ // Generated by CoffeeScript 1.4.0

}
middle = (start + end) >> 1;
node = new Node(array[middle]);
node = new Node(array[middle = (start + end) >> 1]);
node.left = createMinimalBst(array, start, middle - 1);

@@ -22,0 +21,0 @@ node.right = createMinimalBst(array, middle + 1, end);

32

lib/getBalancedParentheses.js

@@ -5,19 +5,19 @@ // Generated by CoffeeScript 1.4.0

getBalancedParens = function(count) {
var recurse, result;
result = [];
recurse = function(left, right, string) {
if (left === 0 && right === 0) {
return result.push(string);
} else {
if (left > 0) {
recurse(left - 1, right, string + '(');
}
if (right > left) {
return recurse(left, right - 1, string + ')');
}
getBalancedParens = function(left, visit, right, string) {
if (right == null) {
right = left;
}
if (string == null) {
string = '';
}
if (left === 0 && right === 0) {
return visit(string);
} else {
if (left > 0) {
getBalancedParens(left - 1, visit, right, string + '(');
}
};
recurse(count, count, '');
return result;
if (right > left) {
return getBalancedParens(left, visit, right - 1, string + ')');
}
}
};

@@ -24,0 +24,0 @@

18

lib/getNthToLastElementOfSinglyLinkedList.js
// Generated by CoffeeScript 1.4.0
(function() {
var getNthToLastElementOfSinglyLinkedList;
var getNthToLastElementOfList;
getNthToLastElementOfSinglyLinkedList = function(list, nthToLastElement) {
var front, i, rear, _i;
front = rear = list;
for (i = _i = 1; 1 <= nthToLastElement ? _i <= nthToLastElement : _i >= nthToLastElement; i = 1 <= nthToLastElement ? ++_i : --_i) {
front = front.next;
getNthToLastElementOfList = function(head, n) {
var i, rear, _i;
rear = head;
for (i = _i = 1; 1 <= n ? _i <= n : _i >= n; i = 1 <= n ? ++_i : --_i) {
head = head.next;
}
while (front !== null) {
front = front.next;
while (head !== null) {
head = head.next;
rear = rear.next;

@@ -18,4 +18,4 @@ }

module.exports = getNthToLastElementOfSinglyLinkedList;
module.exports = getNthToLastElementOfList;
}).call(this);

10

lib/getSubsets.js

@@ -5,5 +5,5 @@ // Generated by CoffeeScript 1.4.0

getSubsets = function(array) {
var bits, i, pos, result, subset, _i, _ref;
result = [];
getSubsets = function(array, visit) {
var bits, i, pos, subset, _i, _ref, _results;
_results = [];
for (i = _i = 0, _ref = (1 << array.length) - 1; 0 <= _ref ? _i <= _ref : _i >= _ref; i = 0 <= _ref ? ++_i : --_i) {

@@ -20,5 +20,5 @@ pos = 0;

}
result.push(subset);
_results.push(visit(subset));
}
return result;
return _results;
};

@@ -25,0 +25,0 @@

79

lib/graphTraversals.js
// Generated by CoffeeScript 1.4.0
(function() {
var Queue, Stack, addUnvisited, bfs, getShortestPath, getShortestPathBacktrack, postorder, preorder,
var Queue, Stack, addUnvisited, addUnvisitedToPrior, bfs, getPathByBacktracking, getShortestPath, getShortestPathBacktrack, postorder, preorder,
__indexOf = [].indexOf || function(item) { for (var i = 0, l = this.length; i < l; i++) { if (i in this && this[i] === item) return i; } return -1; };

@@ -12,5 +12,5 @@

addUnvisited = function(vertices, visited, addCallback) {
addUnvisited = function(adjacents, visited, add) {
var vertex, _i, _len, _ref, _results;
_ref = vertices || [];
_ref = adjacents || [];
_results = [];

@@ -21,3 +21,3 @@ for (_i = 0, _len = _ref.length; _i < _len; _i++) {

visited.push(vertex);
_results.push(addCallback(vertex));
_results.push(add(vertex));
} else {

@@ -30,7 +30,6 @@ _results.push(void 0);

bfs = function(graph, startVertex, visit) {
bfs = function(graph, start, visit) {
var queue, vertex, visited, _results;
queue = new Queue;
queue.enqueue(startVertex);
visited = [startVertex];
visited = [start];
queue = new Queue(visited);
_results = [];

@@ -46,5 +45,5 @@ while (vertex = queue.dequeue()) {

preorder = function(graph, startVertex, visit) {
preorder = function(graph, start, visit) {
var recurse, visited;
visited = [startVertex];
visited = [start];
recurse = function(vertex) {

@@ -54,8 +53,8 @@ visit(vertex);

};
return recurse(startVertex);
return recurse(start);
};
postorder = function(graph, startVertex, visit) {
postorder = function(graph, start, visit) {
var recurse, visited;
visited = [startVertex];
visited = [start];
recurse = function(vertex) {

@@ -65,3 +64,3 @@ addUnvisited(graph[vertex], visited, recurse);

};
return recurse(startVertex);
return recurse(start);
};

@@ -71,5 +70,4 @@

var path, queue, vertex, visited;
queue = new Queue;
queue.enqueue([start]);
visited = [start];
queue = new Queue([visited.slice()]);
while (path = queue.dequeue()) {

@@ -91,23 +89,11 @@ vertex = path[path.last];

getShortestPathBacktrack = function(graph, start, end) {
var adjacent, parent, path, queue, vertex, _i, _len, _ref;
queue = new Queue;
queue.enqueue(start);
parent = {};
parent[start] = null;
var prior, queue, vertex;
queue = new Queue([start]);
prior = {};
prior[start] = null;
while (vertex = queue.dequeue()) {
if (vertex === end) {
path = [end];
while ((vertex = parent[vertex]) !== null) {
path.push(vertex);
}
return path.reverse();
return getPathByBacktracking(end, prior);
}
_ref = graph[vertex] || [];
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
adjacent = _ref[_i];
if (!(adjacent in parent)) {
parent[adjacent] = vertex;
queue.enqueue(adjacent);
}
}
addUnvisitedToPrior(vertex, graph[vertex], prior, queue);
}

@@ -117,2 +103,27 @@ return false;

addUnvisitedToPrior = function(vertex, adjacents, prior, queue) {
var adjacent, _i, _len, _ref, _results;
_ref = adjacents || [];
_results = [];
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
adjacent = _ref[_i];
if (!(adjacent in prior)) {
prior[adjacent] = vertex;
_results.push(queue.enqueue(adjacent));
} else {
_results.push(void 0);
}
}
return _results;
};
getPathByBacktracking = function(vertex, prior) {
var path;
path = [vertex];
while ((vertex = prior[vertex]) != null) {
path.push(vertex);
}
return path.reverse();
};
exports.bfs = bfs;

@@ -119,0 +130,0 @@

26

lib/isBst.js

@@ -10,20 +10,12 @@ // Generated by CoffeeScript 1.4.0

isBstPreorder = function(node, min, max) {
var recurse;
recurse = function(node, min, max) {
var key;
if (node === null) {
return true;
}
key = node.key;
return (min < key && key < max) && recurse(node.left, min, key) && recurse(node.right, key, max);
};
var key;
if (node === null) {
return false;
} else {
return recurse(node, min, max);
return true;
}
key = node.key;
return (min < key && key < max) && isBstPreorder(node.left, min, key) && isBstPreorder(node.right, key, max);
};
isBstInorder = function(node) {
var previous, ret, setPrevious;
var checkWithPrevious, previous, setPrevious;
previous = null;

@@ -33,10 +25,8 @@ setPrevious = function(leftMostChild) {

};
ret = inorderWithLeftMostChild(node, setPrevious, function(node) {
checkWithPrevious = function(node) {
if (node.key < previous.key) {
return false;
} else {
return null;
}
});
if (ret === false) {
};
if (inorderWithLeftMostChild(node, setPrevious, checkWithPrevious) === false) {
return false;

@@ -43,0 +33,0 @@ } else {

18

lib/prototypes.js

@@ -11,2 +11,20 @@ // Generated by CoffeeScript 1.4.0

Array.prototype.add = function(item) {
this.push(item);
return this;
};
Array.prototype.flatten = function() {
var array, item, ret, _i, _j, _len, _len1;
ret = [];
for (_i = 0, _len = this.length; _i < _len; _i++) {
array = this[_i];
for (_j = 0, _len1 = array.length; _j < _len1; _j++) {
item = array[_j];
ret.push(item);
}
}
return ret;
};
Array.prototype.max = function(comparator) {

@@ -13,0 +31,0 @@ var key, ret, _i, _ref;

9

lib/Queue.js

@@ -9,4 +9,11 @@ // Generated by CoffeeScript 1.4.0

function Queue() {
function Queue(array) {
var item, _i, _len;
this.front = this.rear = null;
if (array) {
for (_i = 0, _len = array.length; _i < _len; _i++) {
item = array[_i];
this.enqueue(item);
}
}
}

@@ -13,0 +20,0 @@

4

lib/SinglyLinkedListNode.js

@@ -7,5 +7,5 @@ // Generated by CoffeeScript 1.4.0

function SinglyLinkedListNode(value) {
function SinglyLinkedListNode(value, next) {
this.value = value;
this.next = null;
this.next = next != null ? next : null;
}

@@ -12,0 +12,0 @@

23

lib/sorts.js

@@ -31,8 +31,8 @@ // Generated by CoffeeScript 1.4.0

bucketSort = function(array, bucketCount) {
var bucket, buckets, cursor, i, index, max, _i, _j, _len, _len1;
max = Math.max.apply(Math, array) + 1;
var bucket, buckets, cursor, i, max, _i, _len;
max = array.max() + 1;
buckets = (function() {
var _i, _results;
_results = [];
for (i = _i = 1; 1 <= bucketCount ? _i <= bucketCount : _i >= bucketCount; i = 1 <= bucketCount ? ++_i : --_i) {
for (i = _i = 1; _i <= bucketCount; i = _i += 1) {
_results.push([]);

@@ -44,10 +44,13 @@ }

cursor = array[_i];
index = floor(cursor / max * bucketCount);
buckets[index].push(cursor);
buckets[floor(cursor / max * bucketCount)].push(cursor);
}
for (_j = 0, _len1 = buckets.length; _j < _len1; _j++) {
bucket = buckets[_j];
insertionSort(bucket);
}
return [].concat.apply([], buckets);
return ((function() {
var _j, _len1, _results;
_results = [];
for (_j = 0, _len1 = buckets.length; _j < _len1; _j++) {
bucket = buckets[_j];
_results.push(insertionSort(bucket));
}
return _results;
})()).flatten();
};

@@ -54,0 +57,0 @@

14

lib/Stack.js

@@ -9,4 +9,11 @@ // Generated by CoffeeScript 1.4.0

function Stack() {
function Stack(array) {
var item, _i, _len;
this.head = null;
if (array) {
for (_i = 0, _len = array.length; _i < _len; _i++) {
item = array[_i];
this.push(item);
}
}
}

@@ -27,6 +34,3 @@

Stack.prototype.push = function(value) {
var node;
node = new Node(value);
node.next = this.head;
return this.head = node;
return this.head = new Node(value, this.head);
};

@@ -33,0 +37,0 @@

69

lib/treeTraversals.js
// Generated by CoffeeScript 1.4.0
(function() {
var Queue, Stack, inorder, inorderWithLeftMostChild, iterativeInorder, iterativePreorder, leftMostChild, levelorder, postorder, preorder;
var Queue, Stack, inorder, inorderWithLeftMostChild, iterativeInorder, iterativeInorderReturn, iterativePreorder, leftMostChild, levelorder, postorder, preorder;

@@ -45,6 +45,6 @@ Queue = require('./Queue');

visit(node);
if (node.left !== null) {
if (node.left != null) {
queue.enqueue(node.left);
}
if (node.right !== null) {
if (node.right != null) {
_results.push(queue.enqueue(node.right));

@@ -63,11 +63,10 @@ } else {

}
stack = new Stack;
stack.push(root);
stack = new Stack([root]);
_results = [];
while (node = stack.pop()) {
visit(node);
if (node.right !== null) {
if (node.right != null) {
stack.push(node.right);
}
if (node.left !== null) {
if (node.left != null) {
_results.push(stack.push(node.left));

@@ -85,11 +84,12 @@ } else {

_results = [];
while (!stack.empty() || node) {
if (node) {
while (true) {
while (node !== null) {
stack.push(node);
_results.push(node = node.left);
} else {
node = stack.pop();
visit(node);
_results.push(node = node.right);
node = node.left;
}
if (stack.empty()) {
break;
}
visit(node = stack.pop());
_results.push(node = node.right);
}

@@ -99,4 +99,25 @@ return _results;

iterativeInorderReturn = function(node, visit, stack) {
var ret;
if (stack == null) {
stack = new Stack;
}
while (true) {
while (node !== null) {
stack.push(node);
node = node.left;
}
if (stack.empty()) {
break;
}
node = stack.pop();
if ((ret = visit(node)) != null) {
return ret;
}
node = node.right;
}
};
inorderWithLeftMostChild = function(node, leftMostChild, visit) {
var ret, stack;
var stack;
stack = new Stack;

@@ -109,16 +130,4 @@ while (true) {

}
node = stack.pop();
leftMostChild(node);
while (!stack.empty() || node) {
if (node) {
stack.push(node);
node = node.left;
} else {
node = stack.pop();
if ((ret = visit(node)) !== null) {
return ret;
}
node = node.right;
}
}
leftMostChild(node = stack.pop());
return iterativeInorderReturn(node, visit, stack);
};

@@ -138,4 +147,6 @@

exports.iterativeInorderReturn = iterativeInorderReturn;
exports.inorderWithLeftMostChild = inorderWithLeftMostChild;
}).call(this);

10

package.json

@@ -5,3 +5,3 @@ {

"author": "Chris Khoo",
"version": "0.0.6",
"version": "0.0.7",
"main": "lib/algorithmic.js",

@@ -21,5 +21,9 @@ "licenses": [

},
"dependencies": {
"benchit": "0.0.1"
"scripts": {
"test": "cake test"
},
"devDependencies": {
"coffee-script": "~1.4.0",
"mocha": "~1.7.4"
}
}

25

README.md

@@ -0,1 +1,3 @@

[![Build Status](https://travis-ci.org/khoomeister/algorithmic.png)](https://travis-ci.org/[khoomeister/algorithmic)
Algorithmic

@@ -7,23 +9,2 @@ ===========

Benchmarks
----------
For fun, I did some sort benchmarks to compare sorting algorithms.
**benchSortsBig.coffee (10,000 integers)**
bubble sort elapsed: 493ms
bucket sort elapsed: 2ms
insertion sort elapsed: 140ms
mergesort elapsed: 16ms
quicksort elapsed: 11ms
in-place quicksort elapsed: 1ms
selection sort elapsed: 233ms
v8 sort elapsed: 3ms
**benchSortsBig.coffee (10 million integers)**
bucket sort (10,000 buckets) elapsed: 7419ms
bucket sort (100,000 buckets) elapsed: 2939ms
bucket sort (1,000,000 buckets) elapsed: 3480ms
in-place quicksort elapsed: 1834ms
v8 sort elapsed: 2922ms
Enjoy!
Enjoy!
bench/benchSorts.coffee
bench/benchSortsBig.coffee
bench/helpers.coffee
lib/BitSet.js
lib/isValidBst.js
test/atoiTest.coffee
test/BinaryHeapTest.coffee
test/BinaryTreeNodeTest.coffee
test/binaryTreeToLevelsTest.coffee
test/BitArrayTest.coffee
test/bitOperationsTest.coffee
test/bitSwapsRequiredTest.coffee
test/createMinimalBstFromSortedArrayTest.coffee
test/createTreeFromPreorderAndInorderTest.coffee
test/deleteBstNodeTest.coffee
test/fibonacciTest.coffee
test/getBalancedParenthesesTest.coffee
test/getNthToLastElementOfSinglyLinkedListTest.coffee
test/getPermutationsTest.coffee
test/getSubsetsRecursionTest.coffee
test/getSubsetsTest.coffee
test/graphTraversalsTest.coffee
test/helpers.coffee
test/isBstTest.coffee
test/isPowerOfTwoTest.coffee
test/isStringRotationTest.coffee
test/itoaTest.coffee
test/lookupBstTest.coffee
test/lookupRotatedSortedArrayTest.coffee
test/lowestCommonAncestorTest.coffee
test/MinStackTest.coffee
test/mocha.opts
test/nWayMergeTest.coffee
test/prototypesTest.coffee
test/QueueTest.coffee
test/rotateSquareMatrixRightTest.coffee
test/setBitsBetweenTest.coffee
test/sortStackTest.coffee
test/sortsTest.coffee
test/StackTest.coffee
test/treeBalanceFactorTest.coffee
test/treeNodeHeightTest.coffee
test/treeNodeLeftMostChildTest.coffee
test/treeNodePredecessorTest.coffee
test/treeNodeRightMostChildTest.coffee
test/treeNodeSuccessorTest.coffee
test/treeRotateLeftTest.coffee
test/treeRotateRightTest.coffee
test/treeTraversalsTest.coffee
test/TwoStackQueueTest.coffee
.npmignore

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