Sunday, February 3, 2008

Javascript - Creating a queue system part 1 : procedural way

We queue all the time : at the administration, at the supermarket, at school for lunch....
The first in the queue, will go out first and the last one, well, will be out the last. This is the basic system that many programs use to process commands,functions in a particular order, here the first in, first out order (FIFO). It can be used to create chained effects, delayed remote call to server, sending mails by bunch, etc. We'll see in this entry the underlyings of a queue!
(this is a very basic procedural approach, that will be improved in the next entry)

Example

Before we go on and dive into the coding of our queue system, let's see what we will be able to do with a simple example.
Each time you click on queue, you will add an elment in the queue.
Each time you click on dequeue, you will remove the last element in the queue.
When you click on the flush queue, all the elements are going to be called one after an other (when the last action has finished).
And pause, we'll just pause the queue!
You will see the number of element actually present in the queue each time you click on next in queue of flush queue:
So 0 means that there is nothing in the queue and 1,2,3 are the elements left in the queue:

 
queue dequeue next in queue flush queue pause clear

What do we queue?


A queue contains most of the time functions or commands that a program needs to execute in a FIFO order.
In javascript, a common use of queues are for chaining effects or even queueing remote server calls while offline or in a slow network context and that a call has failed...
It could also be used to trigger other functions when a certain signal is fired, like an event.Indeed, a queue is also the base of what could be our own event sytem triggering functions on demand!(observer pattern with subjects/ observers or publishers and subscribers).
As you can see queues can be very useful and indeed are!
Let's see the features a queue needs.

What are the queue features?



When you are queueing at the supermarket, you need to wait for the signal of the cashier to move forward.
Sometimes, you need to stop people from moving and pause them!
Sometimes, the cashier can ask you to go to an other place and get rid off you!
Sometimes, you just need to get rid off the entire queue because time is over!
Obviously, you need something that contains in the order they came in the clients.
Well, we are lucky because the container in Javascript, that keeps things in order they come is nothing more than an array!
Let's see:
var clients=[]; // or new Array();
clients.push('first in');
clients.push('second in');
clients.push('last in');
alert(clients[0]); 'first in'
alert(clients[1]); 'second in'
So as you can see, it was very easy to create the base of a queue!
We create an array and we just 'push' the clients as they come in!
the first client is in the slot 0 and the last one in the slot 1, as we only have 2 clients!
There is also a very useful function in Javascript in order to deal with arrays, it is the pop function that will just get rid off the last entry in the array:
var client= clients.pop();
alert(client); // 'last in'
alert(clients); // return in order : first in, second in
As you can see the pop get rid off the last element and send it back to us.
There is obviously the counter part of pop, that is, the shift function that gets rid off the first element in the queue:
var first = clients.shift();
alert(first); // 'first in'
alert(clients); // return : second in
So basically, we have all the 4 main ingredients required for a queue:
- a container : the array
- a way to add in order : push, adds element at the end of the array
- a way to remove the first element : shift
- a way to remove the last element : pop

when we add an element at the end of the queue, we say that we 'enqueue' or 'queue'.
when we remove the last element of the queue, we say that we 'dequeue' when we advance in the queue, which is to say, calling the first element in the queue and getting rid off it, we say that we 'advance' or that we call the 'next' in the queue.
When we call all the elements in the queue one after an other, we say that we 'flush' the queue.
In the end, we restart the queue from the beginning, we 'clear' the queue.

The main functions


From there we can define the main elements required:
var q=[];//our queue container
var paused=false; // a boolean flag
function queue() {}
function dequeue() {}
function next() {}
function flush() {}
function clear() {}
you may also want to 'pause' the queue. We will therefore use a boolean flag too.
Now let's see the implementation, this is going to be very straightforward:
var q      = [];
var paused = false;

function queue() {
 for(var i=0;i< arguments.length;i++)
     q.push(arguments[i]);
}
function dequeue() {
    if(!empty()) q.pop();
}
function next() {
    if(empty()) return; //check that we have something in the queue
    paused=false; //if we call the next function, set to false the paused
    q.shift()(); // the same as var func = q.shift(); func();
}
function flush () {
    paused=false;
    while(!empty()) next(); //call all stored elements
}
function empty() {  //helper function
    if(q.length==0) return true;
    return false;
}
function clear() {
    q=[];
}
And here we have our basic queue system!
let's see how we can use it:
queue(function() { alert(1)},function(){ alert(2)},function(){alert(3)});
next(); // alert 1
dequeue(); // the last function, alerting 3 is removed
flush(); // call everything, here alert 2
clear(); // the queue is already empty in that case but anyway...
You can try the above code
As you can see, it works like expected but let's say that instead of alerting something we decide to update a div...
Let's take the following function:
function updateDiv(val) {
   function delayed() {
        document.getElementById('test').innerHTML+=val;
   } 
   setTimeout(delayed,500);
}
We add a timeout to simulate an application taking time to perform.
if we rewrite our example:
queue(function() { updateDiv(1)},function(){ updateDiv(2)},function(){updateDiv(3)});
flush(); // call everything
If we keep the principle of a queue, we should have each function called one after an other, try it yourself
And it doesn't work as expected!!
Well in fact, the flush function is something that we cannot build independently of the application.
Why?
Because our flush function calls each function without even knowing if the precedent one has finished!
In order to create a queue, we need to call the next function at the end of the last executed queued function. Therefore, the queue and the application needs to be related to some extend.
We should rewrite our function like this:
function updateDiv(val) {
   function delayed() {
        document.getElementById('test').innerHTML+=val;
        next();
   } 
   setTimeout(delayed,500);
}
Now, the queue is going to be processed after the end of each function, the recursive call to the next function will create our application related flush:
queue(function() { updateDiv(1)},function(){ updateDiv(2)},function(){updateDiv(3)});
next(); // call next function that will work as a flush here
Now, if you try the above code
And it works as expected!
In fact, each application should have its own flush method.
In order to create a flush function, we need to know when the function is done to move on to the next element in the queue.
But how do I stop the queue processing or just advance one element in the queue then??
Well, we just need to change the flush function and wrap the next function like so:
function advance() {
 paused=false;
 next();
 paused=true;
}
function flush() {
 paused=false;
 next();
}
So, the advance function change the pause flag to false at the beginning and set it right away to true after calling the next function. The next function will stop at the following call as the pause flag will be set to true!
On the other hand the flush function just wrap the next function that will be called by each functions in the queue!
As you can see if some elements can be true to all queues, the flushing of a queue needs to be application aware and can hardly be generalize.
If you add a function in the queue that doesn't call the next function when it is done, your queue won't work and stop there.

Conclusion


We have built here a very basic queue system that allows us to understand the underlying process of a queue.
Javascript offers everything that we need to make it very easy like arrays, push, pop, shift functions.
Obviously these functions can have some overheads that a queue implemented at lower level won't have but the cost is not that much nowadays.

But this queue system has a real huge drawback:
our container and our pause flag is in the global space and we won't be able to have several queues running at the same time!!
Therefore we will see in the next entry an other approach that allows us to create several queue entities,objects that will keep track of their own internal state of the queue.
We will be switching from a procedural approach to an object oriented approach(OOP) and therefore see some of the advantages of this technique over this one.
We will also see how to use a queue in a real context, chaining effects!

2 comments:

Anonymous said...

can you give me full code of queue ? what if i want to change press button + instead click mouse to increase the number

queue mobile said...

thanks for a nice information. this is a very nice and pretty information.

Queue system