Today at work a problem presented itself and the solution gave me pause. I works and the concepts are not foreign to me, but still it feels dirty. I even asked co-worker, what his approach to this problem was and he had the same first approach as I did.
Lets start with a review:
Just so we are all on the same page lets review some of the data structures we will be discussing.
Stack - a stack represents a last in first out (LIFO) data structure that uses the methods push() and pop() to add and remove elements from the structure.
Queue - a queue represents a first in first out (FIFO) data structure that uses the methods enqueue() and dequeue() to add and remove elements from the structure.
The task:
A dialog has an ordered list of check boxes. When the dialog is shown the state of the check boxes should be preserved such that if the user clicks the cancel button the list will revert to its previous state discarding any changes the user has made.
This task should be done in JavaScript to avoid going to the server since no change was made. The approach: I need to be able to add items to a list. Done!
But, I am too clever for my own good. Instead of just adding the items to a list and iterating over the collection with a for loop, in a split second I decided the best approach would be to use a queue.
I know I can't use a stack because the elements in the stack come out in reverse order. That solution would work but that would require me to iterate the check boxes from the end to the beginning instead of from beginning to end when it came time to restoring their state.
That is ugly, unnecessary and might cause maintainability issues when we have to go back and look at the code in the future. Using a queue would let me add elements (enqueue) and when it came time to removing them I could just take them off (dequeue) in order. I could continue to dequeue until there were no more elements. Brilliant!
But wait... The problem: JavaScript does not support the queue as a data type. However, JavaScript supports the array data type and both the queue and stack can be simulated using methods already defined on the array object, namely:
- pop() - Removes the last element of an array, returns that element
- push() - Adds new elements to the end of an array, returns the new length
- shift() - Removes the first element of an array, returns that element
- unshift() - Adds new elements to the beginning of an array, returns the new length
The realization:
Wait, there it is did you catch it? I've been talking about these data structures and the methods used to control them pop() and push(), enqueue() and dequeue(). Then along came shift() and unshift(). You might already know that what is represented by this collection of functions is known as a double-ended queue or a deque (pronounced deck).
Deque -a deque represents a data structure where elements can be added to or removed from either the front or back.
Really the stack and queue can be considered specializations of deques, and can be implemented using deques.
The gripe:
So up to this point I've only really only talked about some data structures and there seems to be no real problem here right?
Well lets examine the following code:
var checkMarks = [];
var intialCheckStates = [];
//Save the initial state
for (var i = 0; i < checkMarks.length; i++) {
intialCheckStates.push(checkMarks[i]);
}
//later on restore the state
for (var i = 0; i < intialCheckStates.length; i++) {
var check = checkMarks.shift();//remove the first element
}
The nomenclature here is what kills me. It feels dirty and unclean because the terminology shift has connotation to a programmer. The shift operator operates on the binary representation of an integer. The digits are moved, or shifted, to the left or right (see
Bit Shifts).
I can understand and visualize why the name shift might be used, after all, the elements of the array are in fact being shifted. I even looked up how different languages name these functions (see
Operations).
Ada, C++, Python, and Java get it right. Even PHP had the sense to call the operations array_shift and array_unshift. I think it helps in the confusion. So lets just call a duck a duck. What we really have is an array that supports arbitrary inserts and removal. We don't really have any other data structure. Just a pig in makeup.
The solution:
So, what is the right answer? Well the previous code block works and does the job just fine. I added a comment so as to not confuse my co-workers when they have to maintain this code. So I should just move happily on my way. Right?
Well, for now that is the way I chose to go. However the future solution for this block of code will be actually implement the data structure with the appropriate methods. The following code properly encapsulates the Queue data structure and makes sense to me.
function Queue() {
this.Elements = [];
this.Count = 0;
};
Queue.prototype.Enqueue = function (element) {
this.Elements.push(element);
this.Count++;
};
Queue.prototype.Dequeue = function () {
var element = this.Elements.shift();
this.Count--;
return element;
};
Queue.prototype.Peek = function () {
return this.Elements[this.Elements.length];
};
Queue.prototype.Count = function () {
return this.Count;
};
var checkMarks = [];
var intialCheckStates = new Queue();
//Save the initial state
for (var i = 0; i < checkMarks.length; i++) {
intialCheckStates .Enqueue(checkMarks[i]);
}
//later on restore the state
while (intialCheckStates.Count > 0) {
var check = intialCheckStates .Dequeue();
}
Of course, I find issues with this implementation as well:
- How will we maintain this, inline or in its own source file?
- Does this make the code any easier to read or does it just bloat the code with a class that is just a wrapper around a single function because I don't like the method's name.
Alas, such is the existence of a persnickety programmer.
