Skip to content

Instantly share code, notes, and snippets.

@iahu
Created September 29, 2014 09:50
Show Gist options
  • Save iahu/c10c8c295398d78b927f to your computer and use it in GitHub Desktop.
Save iahu/c10c8c295398d78b927f to your computer and use it in GitHub Desktop.
Singly-linked lists
function List() {}
function EmptyList() {}
EmptyList.prototype = new List();
EmptyList.prototype.constructor = EmptyList;
EmptyList.prototype.toString = function() { return '()'; };
EmptyList.prototype.isEmpty = function() { return true; };
EmptyList.prototype.length = function() { return 0; };
EmptyList.prototype.push = function(x) { return new ListNode(x, this); };
EmptyList.prototype.remove = function(x) { return this; };
EmptyList.prototype.append = function(xs) { return xs; };
function ListNode(value, next) { this.v = value; this.n = next; }
ListNode.prototype = new List();
ListNode.prototype.constructor = ListNode;
ListNode.prototype.isEmpty = function() { return false; };
ListNode.prototype.toString = function() {
var n = this.n;
var r = [this.v];
while (!n.isEmpty()) {
r.push(n.v);
n = n.n;
}
return '(' + r.join(' ') + ')';
};
ListNode.prototype.head = function() { return this.v; };
ListNode.prototype.tail = function() { return this.n; };
ListNode.prototype.length = function() { return 1 + this.n.length(); };
ListNode.prototype.push = function(x) { return new ListNode(x, this); };
ListNode.prototype.remove = function(x) {
var t = this.n.remove(x);
if (x == this.v) return t;
if (t == this.n) return this;
else return new ListNode(this.v, t);
};
ListNode.prototype.append = function(xs) { return new ListNode(this.v, this.n.append(xs)); };
var assert = require('assert');
var should = require('should');
describe("Basic Tests of Functional List (javascript)", function() {
var mt, l1, l2, l3, l4;
before(function() {
mt = new EmptyList;
l1 = mt.push('a');
l2 = l1.push('b');
l3 = l1.push('c');
l4 = l3.append(l2);
});
it('Tests on the empty list.', function() {
assert(mt.length() === 0, 'Has length zero.');
assert(mt.isEmpty() === true, 'Empty list is empty.');
assert(mt.toString() === '()', 'To String on empty list.');
});
it("After pushing an 'a'", function() {
assert(l1.length() === 1, 'Length is one.');
assert(l1.isEmpty() === false, 'List no longer empty');
assert(l1.head() === 'a', 'First item in list is correct.');
assert(l1.tail().isEmpty(), 'Tail is empty.');
assert(l1.toString() === '(a)', "To String on l1.");
});
it("After pushing a 'b'", function() {
assert(l2.length() === 2, 'After two items, length is two.');
assert(l2.head() === 'b', 'Second item is in the list.');
assert(l2.tail() === l1, 'Tail of l1.push() is l1.');
assert(l2.toString() === '(b a)', 'To String on l2.');
});
it("After pushing a 'c' onto the list of just 'a'", function() {
assert(l3.length() === 2, 'After two items, length is 2');
assert(l3.head() === 'c', 'Second item is in the list.');
assert(l3.tail() === l1, 'Tail of l1.push() is l1.');
assert(l3.toString() === '(c a)', 'To String on l3');
});
it("Appending (b a) to (c a)", function() {
assert(l4.length() === 4, 'After append, have twice as many elements');
assert(l4.head() === 'c', 'Append puts this first (a)');
assert(l4.tail().head() === 'a', 'Append puts this first (b)');
assert(l4.tail().tail() === l2, 'Append leaves argument untouched.');
});
it("Removing 'a' from '(c a b a)'", function() {
assert(l4.remove('a').length() === 2, "Remove both 'a' from l4");
});
it("Removing 'b' from '(c a b a)'", function() {
assert(l4.remove('b').length() === 3, 'Length should be three');
assert(l4.remove('b').tail().tail() === l4.tail().tail().tail(), 'l4.remove l4.head() is l4.tail()');
});
it("Removing 'c' from '(c a b a)'", function() {
assert(l4.remove('c').length() === 3, 'Length should be three');
assert(l4.remove('c') === l4.tail(), 'l4.remove(first) is l4.tail()');
});
it("Removing 'a' from '(a)'", function () {
assert(l1.remove('a') === mt, 'l1.remove(first) is empty');
});
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment