5.1. Priority Queues

Whenever pieces of data need to be arranged in order of priority, the typical solution is to use a priority queue. A standard queue is a first-in, first-out data structure: items are added at the back of the queue, wait in line, and eventually are removed from the front of the queue. A priority queue augments that methodology by inserting new values into the queue based on a priority, so a new value with a higher priority doesn't go to the back of the queue, but rather, gets inserted into an appropriate location. In a priority queue where 0 is the highest priority and 4 is the lowest, items with a priority of 3 will always be inserted into the queue before any items with a priority of 4. Likewise, items with a priority of 2 are inserted ahead of those with a priority of 3, and so on. This is the perfect paradigm for managing multiple XHR requests. Unfortunately, JavaScript doesn't have a built-in priority queue, so it's necessary to create one.

A generic priority queue can be made with a single Array object, making use of the built-in sort() method. When values are added to this custom priority queue, they are added to the array, which is then sorted. By providing a custom comparison function to the sort() method, it's possible to determine the order in which the values should appear within the array, making it perfect for assigning priorities. A comparison function has the following generic form:

function compare(oValue1, oValue2) {
    if (oValue1 < oValue2) {
        return −1;
    } else if (oValue1 > oValue 2) {
        return 1;
    } else {
        return 0;
    }
}

Very simply, a comparison function returns a negative number when the first value is less than the second (when the first should come before the second), a positive number when the first value is greater than the second (when the first should come after the second), and zero if the values are equal (don't change position in the array).

The constructor for the PriorityQueue object is:

function PriorityQueue(fnCompare) {
    this._items = new Array();
    if (typeof fnCompare == "function"){
        this._compare = fnCompare;
    }
}

This constructor accepts a single argument, fnCompare, which is a comparison function to use when determining priorities. If this argument is provided, it's assigned to the _compare property; otherwise, the default _compare() method is used (the default method is defined on the prototype). There is also a single property, items, which holds the Array object used to manage the values.

Next, the methods for the PriorityQueue need to be defined. The first method is the default _compare() method to use when one isn't supplied. Since this method isn't intended to be publicly accessible, a prioritize() method is implemented to use it:

PriorityQueue.prototype = {

    _compare : function (oValue1, oValue2) {
        if (oValue1 < oValue2) {
            return −1;
        } else if (oValue1 > oValue2) {
            return 1;
        } else {

return 0;
        }
    },

    //more code here

    prioritize : function () {
        this._items.sort(this._compare);
    }

    //more code here

};

The _compare() method is just a basic comparison function that uses the primitive values of each item to figure out which goes before which (using the less-than and greater-than operators caused a behind-the-scenes call to valueOf() on each item). When an item is added to the queue, the prioritize() method is called to ensure that items appear in the correct order. This is also important in case a value inside of the queue changes, at which point it's necessary to call prioritize() explicitly to ensure that the ordering is valid.

There are five methods that deal with the normal operation of a priority queue: get(), item(), peek(), put(), and size().

• The get() method retrieves the next item in the queue.

• item() returns an item in a given position.

• peek() gets the next item in the queue without actually removing it (just a preview of the next item).

• put() is responsible for adding a new value to the queue.

• size() simply returns the number of items in the queue.

These methods are all fairly simple:

PriorityQueue.prototype = {

    _compare : function (oValue1, oValue2) {
        if (oValue1 < oValue2) {
            return −1;
        } else if (oValue1 > oValue2) {
            return 1;
        } else {
            return 0;
        }
    },

    get : function() {
        return this._items.shift();
    },

    item : function (iPos) {
        return this._items[iPos];

},

    peek : function () {
        return this._items[0];
    },

    prioritize : function () {
        this._items.sort(this._compare);
    },

    put : function (oValue) {
        this._items.push(oValue);
        this.prioritize();
    },

    //more code here

    size: function () {
        return this._items.length;
    }
};

In the preceding code, you see all five methods in action:

• The get() method uses the array's shift() method to remove and return the first item in the array (if the array is empty, shift() returns null).

• The next method, item(), returns an item in the specified position in the queue.

• peek() just gets the first item in the array using the 0 index, which returns the value without removing it.

• The put() method is the one that adds a value to the queue. It first adds the value to the array and then calls prioritize().

• Last, the size() method simply returns the length of the array, so it's possible to tell how many items are in the queue.

The final method for the PriorityQueue object is remove(), which searches the queue for a specific value and then removes it. This can be very important if an item loses priority and no longer needs to be in the queue:

PriorityQueue.prototype = {

    _compare : function (oValue1, oValue2) {
        if (oValue1 < oValue2) {
            return −1;
        } else if (oValue1 > oValue2) {
            return 1;
        } else {
            return 0;
        }
    },

    get : function() {

return this._items.shift();
    },

    peek : function () {
        return this._items[0];
    },

    prioritize : function () {
        this._items.sort(this._compare);
    },

    put : function (oValue) {
        this._items.push(oValue);
        this._items.sort(this._compare);
    },

    remove : function (oValue) {
        for (var i=0; i < this._items.length; i++) {
            if (this._items[i] === oValue) {
                this._items.splice(i, 1);
                return true;
            }
        }
        return false;
    },

    size : function () {
        return this._items.length;
    }

};

The remove() method uses a for loop to search for a specific value in the array. The value is determined by using the identically equal operator (===) to ensure that types aren't converted when making the comparison. If the matching value is found, it is removed from the array using the splice() method and a value of true is returned; if no matching value is found, it returns false.

This PriorityQueue object is the base upon which a robust request management object can be created.