RapidQueue.shift() VS Array.shift() 1 (v2)

Revision 2 of this benchmark created by Kevin Yudi Utama on May 3, 2015

Description

Setup

function createCircularQueue(intialCapacity) {
        var that = {};
        var head = 0;
        var tail = 0;
        var length = 0;
        var initialCapacity = initialCapacity;
        var currentSize = (typeof initialCapacity === undefined) ? initialCapacity : 200;
        var container = [];
        container.length=currentSize;
    
        function doubling() {
                var currentSource = head;
                var currentTarget = 0;
                var newContainer = [];
                newContainer.length = 2*currentSize;
    
                while (currentTarget < currentSize) {
                        newContainer[currentTarget] = container[currentSource];
                        currentSource++;
                        currentTarget++;
                        if (currentSource == currentSize) {
                                currentSource = 0;
                        }
                }
                container = newContainer;
                head = 0;
                tail = currentSize;
                currentSize *= 2;
        }
    
        function shrink() {
                var currentSource = head;
                var currentTarget = 0;
                var newContainer = [];
                newContainer.length = currentSize/4;
    
                while (currentTarget < currentSize) {
                        newContainer[currentTarget] = container[currentSource];
                        currentSource++;
                        currentTarget++;
                        if (currentSource == currentSize) {
                                currentSource = 0;
                        }
                }
                container = newContainer;
                head = 0;
                tail = currentSize;
                currentSize /= 4;
        }
    
        that.push = function(element) {
                if (length == currentSize) {
                        doubling();
                }
                container[tail] = element;
                length++;
                tail++;
                if (tail == currentSize) {
                        tail = 0;
                }
        };
    
        that.shift = function() {
                if (length === 0) {
                        return null;
                }
                tmp = container[head];
                head++;
                length--;
                if (head == currentSize) {
                        head = 0;
                }
                if (length == currentSize/4 && length > initialCapacity) {
                        shrink();
                }
                return tmp;
        };
    
    
        that.front = function() {
                if (length === 0) {
                        return null;
                }
                return container[head];
        };
    
        that.length = function() {
                return length;
        };
    
        that.isEmpty = function() {
                return length === 0;
        };
    
        return that;
    }
    
    function createDoubleStackQueue() {
        var that = {};
        var pushContainer = [];
        var popContainer = [];
    
        function moveElementToPopContainer() {
                while (pushContainer.length !==0 ) {
                        var element = pushContainer.pop();
                        popContainer.push(element);
                }
        }
    
        that.push = function(element) {
                pushContainer.push(element);
        };
    
        that.shift = function() {
                if (popContainer.length === 0) {
                        moveElementToPopContainer();
                }
                if (popContainer.length === 0) {
                        return null;
                } else {
                        return popContainer.pop();
                }
        };
    
        that.front = function() {
                if (popContainer.length === 0) {
                        moveElementToPopContainer();
                }
                if (popContainer.length === 0) {
                        return null;
                }
                return popContainer[popContainer.length - 1];
        };
    
        that.length = function() {
                return pushContainer.length + popContainer.length;
        };
    
        that.isEmpty = function() {
                return (pushContainer.length + popContainer.length) === 0;
        };
    
        return that;
    }
    
    var queue1 = createDoubleStackQueue();
    var queue2 = createCircularQueue();
    var queue3 = []
    
    for (var i = 0;i<100000;i++) {
        queue1.push(i);
        queue2.push(i);
        queue3.push(i);
    }

Test runner

queue1.shift();

queue2.shift();

queue3.shift();

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published by Kevin Yudi Utama on May 3, 2015
• Revision 2: published by Kevin Yudi Utama on May 3, 2015