Source: LinkedDeque.js

(function () {
    "use strict";
    /**
     * @class LinkedDeque
     * @classdesc A Deque using linked nodes instead of standard javascript Array. In addition the Deque can be
     * optionally capacity constrained, if unspecified, the value is set to Number.MAX_VALUE.
     * Standard javascript Array's shift, unshift, push and pop operations are implemented for linked nodes.
     *
     * [Reference: LinkedBlockingDeque in Oracle JDK](http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/LinkedBlockingDeque.html)
     * @param capacity {Number=} set to Number.MAX_VALUE if not provided
     * @desc
     * #### Example -
     * ```js
     * var LinkedDeque = require("dsjslib").LinkedDeque
     * var ldq=new LinkedDeque(100)
     * ```
     */
    function LinkedDeque(capacity) {
        this._capacity = typeof capacity === 'number' ? capacity : Number.MAX_VALUE;
        this._tail = this._head = null;
        this._size = 0;
    }

    /**
     * Nodes of a doubly linked list
     * @param prev
     * @param obj
     * @param next
     * @private
     * @constructor
     */
    function QEntry(prev, obj, next) {
        if (typeof obj === 'undefined' || obj === null) {
            throw new Error('Null or Undefined values are not supported');
        }
        this.item = obj;
        this.prev = prev;
        this.next = next;
    }

    /**
     * Add item to the head of the Deque. Equivalent to ldq.offerFirst(item).
     * Returns true if obj was successfully added, false if it failed (for example, if the Deque is at
     * full capacity.
     * @memberOf LinkedDeque.prototype
     * @instance
     * @type {Function}
     * @returns {Boolean}  true if obj was successfully added, false otherwise
     */
    LinkedDeque.prototype.unshift = function (item) {
        if (this._size >= this._capacity)return false;
        var head = this._head,
            entry = new QEntry(null, item, head);
        if (!this._tail) {
            this._tail = entry;
        } else {
            head.prev = entry;
        }
        this._head = entry;
        this._size++;
        return true;
    };
    /**
     * Equivalent to {@link LinkedDeque#unshift}
     * @memberOf LinkedDeque.prototype
     * @instance
     * @returns {Boolean}  true if obj was successfully added, false otherwise
     */
    LinkedDeque.prototype.offerFirst = LinkedDeque.prototype.unshift;

    /**
     * Add item to the tail of the Deque. Equivalent to ldq.offerLast(item).
     * Returns true if obj was successfully added, false if it failed (for example, if the Deque is at
     * full capacity.
     * @memberOf LinkedDeque.prototype
     * @instance
     * @type {Function}
     * @returns {Boolean}  true if obj was successfully added, false otherwise
     * */
    LinkedDeque.prototype.push = function (item) {
        if (this._size >= this._capacity)return false;
        var tail = this._tail,
            entry = new QEntry(tail, item, null);
        if (!this._head) {
            this._head = entry;
        } else {
            tail.next = entry;
        }
        this._tail = entry;
        this._size++;
        return true;
    };

    /**
     * Equivalent to {@link LinkedDeque#push}
     * @memberOf LinkedDeque.prototype
     * @instance
     * @returns {Boolean}  true if obj was successfully added, false otherwise
     */
    LinkedDeque.prototype.offerLast = LinkedDeque.prototype.push;

    /**
     * Returns and removes the element at the head of the Deque.
     * Returns null if there is no such element
     * Equivalent to {@link LinkedDeque#pollFirst}
     * @memberOf LinkedDeque.prototype
     * @instance
     * @returns {*} Returns and removes the element at the head of the Deque, null if no such element
     */
    LinkedDeque.prototype.shift = function () {
        if (this._size <= 0)return null;
        var ret = this._head,
            next = ret.next;
        if (!next) {
            this._head = this._tail = null;
        } else {
            next.prev = null;
            ret.next = null;
        }
        this._head = next;
        this._size--;
        return ret.item;
    };

    /**
     * Equivalent to {@link LinkedDeque#shift}
     * @memberOf LinkedDeque.prototype
     * @instance
     * @returns {*} Returns and removes the element at the head of the Deque, null if no such element
     */
    LinkedDeque.prototype.pollFirst = LinkedDeque.prototype.shift;

    /**
     * Returns and removes the element at the tail of the Deque.
     * Returns null if there is no such element
     * Equivalent to {@link LinkedDeque#pop}
     * @memberOf LinkedDeque.prototype
     * @instance
     * @returns {*} Returns and removes the element at the tail of the Deque, null if no such element
     */
    LinkedDeque.prototype.pollLast = function () {
        if (this._size <= 0)return null;
        var ret = this._tail,
            prev = ret.prev;
        if (!prev) {
            this._head = this._tail = null;
        } else {
            prev.next = null;
            ret.prev = null;
        }
        this._tail = prev;
        this._size--;
        return ret.item;
    };

    /**
     * Equivalent to {@link LinkedDeque#pollLast}
     * @memberOf LinkedDeque.prototype
     * @instance
     * @returns {*} Returns and removes the element at the tail of the Deque, null if no such element
     */
    LinkedDeque.prototype.pop =
        LinkedDeque.prototype.pollLast;

    /**
     * Returns an array containing all of the elements in this Deque,
     * in proper sequence (from first to last element).
     * The returned array has no links/pointers to the Deque.
     * No items are removed from the Deque
     * @memberOf LinkedDeque.prototype
     * @instance
     * @returns {Array}
     */
    LinkedDeque.prototype.toArray = function () {
        var head = this._head,
            arr = [];
        while (head) {
            arr.push(head.item);
            head = head.next;
        }
        return arr;
    };
    /**
     * Removes all elements from the deque
     * @memberOf LinkedDeque.prototype
     * @instance
     *
     */
    LinkedDeque.prototype.clear = function () {
        var first = this._head,
            next = first;
        while (next) {
            first.prev = null;
            next = first.next;
            first.next = null;
        }
        delete this._head;
        delete this._tail;
        this._head = this._tail = null;
        this._size = 0;
    };

    /**
     * @memberOf LinkedDeque.prototype
     * @instance
     * @returns {Number} size of the array
     */
    LinkedDeque.prototype.size = function () {
        return this._size;
    };


    module.exports = LinkedDeque;

}());