Special Linked List

Bench.js

try {
    var LinkedList = require('./Linked').LinkedList;

} catch(err) {

}

function timeTest(name, cb, count) {

    var callbacks = cb(),
        prepare = callbacks[0],
        run = callbacks[1],
        clean = callbacks[2];

    count = count || 1000;

    var i;
    for(i = 0; i < count; i++) {
        prepare && prepare(i);
    }

    var start = Date.now();
    for(i = 0; i < count; i++) {
        run(i);
    }

    var taken = Date.now() - start;

    console.log(name + ': ' + (count * 200) + ' ops, ' + taken / (count * 200) + 'ms/op');

}

timeTest('Add array (best case)', function() {

    var lists = [],
        items = [];

    return [function(e) {

        lists[e] = [];
        items[e] = [];
        for(var i = 0, l = 200; i < l; i++) {
            var foo = { l: i, f: 2, q: 4, f: [] };
            items[e].push(foo);
        }

    }, function(e) {

        for(var i = 0, l = 200; i < l; i++) {
            lists[e].push(items[e][i]);
        }

    }];

});

timeTest('Add linked(best case)', function() {

    var lists = [],
        items = [];

    return [function(e) {

        lists[e] = new LinkedList();
        items[e] = [];
        for(var i = 0, l = 200; i < l; i++) {
            var foo = { l: i, f: 2, q: 4, f: [] };
            foo[lists[e].__id] = null;
            items[e].push(foo);
        }

    }, function(e) {

        for(var i = 0, l = 200; i < l; i++) {
            lists[e].add(items[e][i]);
        }

    }];

});


timeTest('Remove array (worst case) ', function() {

    var lists = [],
        items = [];

    return [function(e) {

        lists[e] = [];
        items[e] = [];
        for(var i = 0, l = 200; i < l; i++) {
            items[e].push({ l: i });
            lists[e].push(items[e][i]);
        }

    }, function(e) {

        for(var i = 0, l = 200; i < l; i++) {
            lists[e].splice(lists[e].indexOf(items[e][199 - i]), 1);
        }

    }];

});

//
timeTest('Remove linked (worst case)', function() {

    var lists = [],
        items = [];

    return [function(e) {

        lists[e] = new LinkedList();
        items[e] = [];
        for(var i = 0, l = 200; i < l; i++) {
            items[e].push({ l: i });
            lists[e].add(items[e][i]);
        }

    }, function(e) {

        for(var i = 0, l = 200; i < l; i++) {
            lists[e].remove(items[e][199 - i]);
        }

    }];

});

LinkedList.js

/**
  * Copyright (c) 2011 Ivo Wetzel.
  *
  * Permission is hereby granted, free of charge, to any person obtaining a copy
  * of this software and associated documentation files (the "Software"), to deal
  * in the Software without restriction, including without limitation the rights
  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  * copies of the Software, and to permit persons to whom the Software is
  * furnished to do so, subject to the following conditions:
  *
  * The above copyright notice and this permission notice shall be included in
  * all copies or substantial portions of the Software.
  *
  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  * THE SOFTWARE.
*/


/**
  * Reference supported LinkedList.
  *
  * Adds references to it's list node to the object.
  *
  * Does NOT do any error checking, it's pure performance code.
  *
  * O(1). Period.
  */
function LinkedList() {

    this.length = 0;

    this.__id = '__ln' + (++LinkedList.id);
    this.__front = null;
    this.__back = null;

    LinkedIter.call(this, this);

}

LinkedList.id = 0;

LinkedList.prototype = {

    /**
      * Add a node pointing to ref at the end of the list
      *
      * @param {Object} ref Object to be added
      */
    add: function(ref) {

        var node = ref[this.__id] = {
            ref: ref,
            next: null,
            prev: null
        };

        if (this.__front === null) {
            this.__front = node;

        } else {
            (node.prev = this.__back).next = node;
        }

        this.__back = node;
        this.length++;

    },

    /**
      * Add a node pointing to ref at the front of the list
      *
      * @param {Object} ref Object to be added
      */
    addFront: function(ref) {

        if (this.__front === null) {

            var node = ref[this.__id] = {
                ref: ref,
                next: null,
                prev: null
            };

            this.__front = this.__back = node;
            this.length++;

        } else {
            this.addBefore(ref, this.__front.ref);
        }

    },

    /**
      * Add a node pointing to ref before the node of at
      *
      * @param {Object} at Object contained in the linked list
      * @param {Object} ref Object to be added
      */
    addBefore: function(ref, at) {

        var node = ref[this.__id] = {
                ref: ref,
                next: null,
                prev: null
            },
            p = at[this.__id];

        if (p.prev === null) {
            this.__front = node;

        } else {
            (node.prev = p.prev).next = node;
        }

        (node.next = p).prev = node;

        this.length++;

    },

    /**
      * Add a node pointing to ref after the node of at
      *
      * @param {Object} at Object contained in the linked list
      * @param {Object} ref Object to be added
      */
    addAfter: function(ref, at) {

        var node = ref[this.__id] = {
                ref: ref,
                next: null,
                prev: null
            },
            p = at[this.__id];

        if (p.next === null) {
            this.__back = node;

        } else {
            (node.next = p.next).prev = node;
        }

        (node.prev = p).next = node;
        this.length++;

    },

    /**
      * Check whether the list contains the given Object.
      *
      * @param {Object} ref Object to be checked against the list
      */
    has: function(ref) {
        return !!ref[this.__id];
    },

    /**
      * Remove all objects from the list.
      */
    clear: function(ref) {

        while(this.__front) {
            this.removeFront();
        }
    },

    /**
      * Returns an array containing all objects in the list.
      */
    toArray: function() {

        var array = new Array(this.length),
            node = this.__front,
            i = 0;

        while(node) {
            array[i++] = node.ref;
            node = node.next;
        }

        return array;

    },

    /**
      * Returns a new iterator for this list.
      *
      * @returns {LinkedIter} The iterator, changing the list will invalidate it
      */
    iter: function() {
        return new LinkedIter(this);
    },

    /**
      * Removes the given object from the list.
      *
      * @param {Object} ref Object to be removed from the list.
      */
    remove: function(ref) {
        return this.__removeNode(ref[this.__id]);
    },

    /**
      * Remove the front of the list.
      */
    removeFront: function() {
        if (this.__front) {
            return this.__removeNode(this.__front);
        }
    },

    /**
      * Remove the back of the list.
      */
    removeBack: function() {
        if (this.__back) {
            return this.__removeNode(this.__back);
        }
    },

    /**
      * Removes the given object from the list.
      *
      * @param {Object} ref Object to be removed from the list.
      */
    removeBefore: function(at) {
        return this.__removeNode(at[this.__id].prev);
    },

    /**
      * Removes the given object from the list.
      *
      * @param {Object} ref Object to be removed from the list.
      */
    removeAfter: function(at) {
        return this.__removeNode(at[this.__id].next);
    },

    /**
      * Remove a node from the linked list.
      */
    __removeNode: function(node) {

        if (node === this.__front) {

            this.__front = node.next;

            if (this.__front) {
                this.__front.prev = null;
            }

            if (node === this.__back) {
                this.__back = null;
            }

        } else if (node === this.__back) {

            this.__back = node.prev;

            if (this.__back) {
                this.__back.next = null;
            }

        } else {
            (node.prev.next = node.next).prev = node.prev;
        }

        node.next = null;
        node.prev = null;
        this.length--;

        return node.ref;

    },

    /**
      * Merge sort implementation.
      *
      * @param {Function} comp Comparator
      */
    sort: function(comp) {

        this.__iter = null;

        if (this.length <= 1) {
            return;
        }

        var listSize = 1,
            numMerges,
            leftSize,
            rightSize,
            back, left,
            right, next,
            front = this.__front;

        do {

            numMerges = 0;
            left = front;
            back = front = null;

            do {

                numMerges++;
                right = left;
                leftSize = 0;
                rightSize = listSize;

                // Cut list into two halves (but don't overrun)
                while(right && leftSize < listSize) {
                    leftSize++;
                    right = right.next;
                }

                // Run through the lists appending onto what we have so far.
                while(leftSize > 0 || (rightSize > 0 && right)) {

                    // Left empty, take right OR Right empty,
                    // take left, OR compare.
                    if (leftSize && (!rightSize || !right
                                    || comp(left.ref, right.ref) < 0)) {

                        next = left;
                        left = left.next;
                        leftSize--;

                    } else {
                        next = right;
                        right = right.next;
                        rightSize--;
                    }

                    // Update pointers to keep track of where we are:
                    if (back) {
                        back.next = next;

                    } else {
                        front = next;
                    }

                    // Sort prev pointer
                    next.prev = back;
                    back = next;

                }

                // Right is now AFTER the list we just sorted
                // so start the next sort there.
                left = right;

            } while(left);

            // Terminate the list, double the list-sort size.
            back.next = null;
            listSize *= 2;

        // If we only did one merge, then we just sorted the whole list.
        } while(numMerges > 1);

        this.__back = back;
        this.__front = front;

    }

};


/**
  * Iterator for a LinkedList
  */
function LinkedIter(list) {

    this.__iter = null;
    this.__front = list.__front;
    this.__back = list.__back;

}

LinkedIter.prototype = {

    /**
      * Reset the iterator to the start of the list.
      */
    begin: function() {
        this.__iter = {
            next: this.__front
        };
    },

    /**
      * Reset the iterator to the start of the list.
      */
    end: function() {
        this.__iter = {
            prev: this.__back
        };
    },

    /**
      * Return the next object in the list.
      *
      * @returns {Object|null} Next object or null in case there are no more
      */
    next: function() {

        if ((this.__iter = this.__iter.next)) {
            return this.__iter.ref;

        } else {
            return null;
        }

    },

    /**
      * Return the previous object in the list.
      *
      * @returns {Object|null} Previous object or null in case there are no more
      */
    prev: function() {

        if ((this.__iter = this.__iter.prev)) {
            return this.__iter.ref;

        } else {
            return null;
        }

    }

};

LinkedList.prototype.begin = LinkedIter.prototype.begin;
LinkedList.prototype.end = LinkedIter.prototype.end;
LinkedList.prototype.next = LinkedIter.prototype.next;
LinkedList.prototype.prev = LinkedIter.prototype.prev;

exports.LinkedList = LinkedList;

LinkedListUnit.js

var LinkedList = require('./Linked').LinkedList;

function testList(tests, check) {

    return function(test) {

        var list = new LinkedList(),
            a = { a: true }, b = { b: true },
            c = { c: true }, d = { d: true };

        test.expect(tests + 3);
        check.call(test, list, a, b, c, d);
        test.equal(list.length, 0, 'List should have 0 objects');

//        test.ok(!a.hasOwnProperty(list.__id), 'a should no longer have list id');
//        test.ok(!b.hasOwnProperty(list.__id), 'b should no longer have list id');
//        test.ok(!c.hasOwnProperty(list.__id), 'c should no longer have list id');
//        test.ok(!d.hasOwnProperty(list.__id), 'd should no longer have list id');

        test.equal(list.__front, null, 'List front is null');
        test.equal(list.__back, null, 'List back is null');

        test.done();

    };

}

exports.sort = testList(3, function(list, a, b, c, d) {

    a.value = 3;
    b.value = 2;
    c.value = 4;
    d.value = -1;

    list.add(a);
    list.add(b);
    list.add(c);
    list.add(d);

    list.sort(function(a, b) {
        return a.value - b.value;
    });

    this.deepEqual(list.toArray(), [d, b, a, c], 'List objects are sorted');

    this.equal(list.__front.ref, d, 'List front is d');
    this.equal(list.__back.ref, c, 'List back is c');

    list.clear();

});


exports.iterate = testList(10, function(list, a, b, c, d) {

    list.add(a);
    list.add(b);
    list.add(c);
    list.add(d);

    var obj,
        check = [a, b, c, d];

    list.begin();
    while((obj = list.next())) {
        this.equal(check.shift(), obj, 'Correct next object returned');
    }

    this.equal(check.length, 0, '4 iterations performed');

    check = [d, c, b, a];
    list.end();
    while((obj = list.prev())) {
        this.equal(check.shift(), obj, 'Correct previous object returned');
    }

    this.equal(check.length, 0, '4 iterations performed');

    list.clear();

});


exports.testClearHas = testList(6, function(list, a, b, c, d) {

    list.add(a);
    list.add(b);
    list.add(c);
    list.add(d);

    this.ok(list.has(a), 'List should contain a');
    this.ok(list.has(b), 'List should contain b');
    this.ok(list.has(c), 'List should contain c');
    this.ok(list.has(d), 'List should contain d');

    this.equal(list.length, 4, 'List should have 4 objects');
    this.deepEqual(list.toArray(), [a, b, c, d],
                    'List objects order matches insertion order');

    list.clear();

});

exports.testToArray = testList(1, function(list, a, b, c, d) {

    list.add(a);
    list.add(b);
    list.add(c);
    list.add(d);

    this.deepEqual(list.toArray(), [a, b, c, d],
                    'List objects order matches insertion order');

    list.clear();

});

exports.testAddRemove = testList(4, function(list, a, b, c, d) {

    list.add(a);
    list.add(b);
    this.deepEqual(list.toArray(), [a, b],
                    'List objects order matches insertion order');
    list.add(c);
    list.add(d);

    this.equal(list.length, 4, 'List should have 4 objects');
    this.deepEqual(list.toArray(), [a, b, c, d],
                    'List objects order matches insertion order');

    list.remove(a);
    list.remove(b);

    this.deepEqual(list.toArray(), [c, d],
                    'List objects order matches removal order');

    list.remove(c);
    list.remove(d);

});


exports.testAddRemoveFront = testList(8, function(list, a, b, c, d) {

    list.addFront(a);
    list.addFront(b);
    this.deepEqual(list.toArray(), [b, a],
                    'List objects order matches insertion order');
    list.addFront(c);
    list.addFront(d);

    this.equal(list.length, 4, 'List should have 4 objects');
    this.deepEqual(list.toArray(), [d, c, b, a],
                    'List objects order matches insertion order');

    this.equal(list.removeFront(), d, 'First item removed is d');
    this.equal(list.removeFront(), c, 'Second item removed is c');

    this.deepEqual(list.toArray(), [b, a],
                    'List objects order matches removal order');

    this.equal(list.removeFront(), b, 'Third item removed is b');
    this.equal(list.removeFront(), a, 'Fourth item removed is a');

});


exports.testAddRemoveBack = testList(8, function(list, a, b, c, d) {

    list.add(a);
    list.add(b);
    this.deepEqual(list.toArray(), [a, b],
                    'List objects order matches insertion order');
    list.add(c);
    list.add(d);

    this.equal(list.length, 4, 'List should have 4 objects');
    this.deepEqual(list.toArray(), [a, b, c, d],
                    'List objects order matches insertion order');

    this.equal(list.removeBack(), d, 'First item removed is d');
    this.equal(list.removeBack(), c, 'Second item removed is c');

    this.deepEqual(list.toArray(), [a, b],
                    'List objects order matches removal order');

    this.equal(list.removeBack(), b, 'Third item removed is b');
    this.equal(list.removeBack(), a, 'Fourth item removed is a');

});


exports.testAddRemoveBefore = testList(10, function(list, a, b, c, d) {

    list.add(a);

    list.addBefore(b, a);
    this.deepEqual(list.toArray(), [b, a],
                    'List object order matches insertion order');

    list.addBefore(c, b);
    this.deepEqual(list.toArray(), [c, b, a],
                    'List objects order matches insertion order');

    list.addBefore(d, a);
    this.deepEqual(list.toArray(), [c, b, d, a],
                    'List objects order matches insertion order');

    this.equal(list.removeBefore(d), b, 'First item removed is b');
    this.deepEqual(list.toArray(), [c, d, a],
                    'List objects order matches removal order');

    this.equal(list.removeBefore(a), d, 'Second item removed is d');
    this.deepEqual(list.toArray(), [c, a],
                    'List objects order matches removal order');

    this.equal(list.removeBefore(a), c, 'Third item removed is c');
    this.deepEqual(list.toArray(), [a],
                    'List objects order matches removal order');


    this.equal(list.removeFront(), a, 'Fourth item removed is a');

});


exports.testAddRemoveAfter = testList(10, function(list, a, b, c, d) {

    list.add(a);

    list.addAfter(b, a);
    this.deepEqual(list.toArray(), [a, b],
                    'List objects order matches insertion order');

    list.addAfter(c, a);
    this.deepEqual(list.toArray(), [a, c, b],
                    'List objects order matches insertion order');

    list.addAfter(d, c);
    this.deepEqual(list.toArray(), [a, c, d, b],
                    'List objects order matches insertion order');


    this.equal(list.removeAfter(d), b, 'First item removed is b');
    this.deepEqual(list.toArray(), [a, c, d],
                    'List objects order matches removal order');

    this.equal(list.removeAfter(a), c, 'Second item removed is c');
    this.deepEqual(list.toArray(), [a, d],
                    'List objects order matches removal order');

    this.equal(list.removeAfter(a), d, 'Third item removed is d');
    this.deepEqual(list.toArray(), [a],
                    'List objects order matches removal order');

    this.equal(list.removeBack(), a, 'Fourth item removed is a');

});