Creating A Fixed-Length Queue In JavaScript Using Arrays
Posted January 6, 2012 at 9:47 AM by Ben Nadel
The other day, I was laying in bed thinking about JavaScript Arrays. Specifically, I was thinking about an Array that would have a fixed length - something that would maintain a maximum length, even as new items were pushed onto the stack. I had envisioned creating some sort of container for "recent" data value (ex. last 50 messages). As a fun thought experiment, I wanted to see if I could extend the native Array object and then augment its access and mutation methods in order to maintain a fixed-length.
| | | | ||
| | | |||
| | | |
If an object has methods, we can easily decorate those methods, adding a layer of additional business logic. Arrays are tricky, however, since they allow for both method-based augmentation (ie. push(), pop(), etc.) and direct-index assignment (ie. settings array[index] to some value). For this experiment, I am accepting the fact that I cannot trap direct-index assignment - if the fixed-length queue is to be augmented, it should usually be done so through the use of the native Array class methods.
NOTE: JavaScript "Proxies" may allow for direct-index-assignment trapping; unfortunately, I know nothing about Proxies at this time.
To make sure that the length of the queue is maintained, I am adding wrappers around the following methods:
- push()
- splice()
- unshift()
The Array class has many more methods than this; however, I felt these were the few methods most likely to cause the length of the array to extend beyond its fixed size. The wrappers act by invoking the given class method followed by a "trimming" method. If items are unshifted onto the head of the array, excess items are removed from the tail. If items are pushed onto the tail of the array, excess items are removed from the head.
Let's take a look at some demo code:
- <!DOCTYPE html>
- <html>
- <head>
- <title>Fixed-Length Queue Data Type In JavaScript</title>
-
- <script type="text/javascript">
-
-
- // Create a constructor for the fixed-length queue. This is
- // really more of a FACTORY than a construtor since an
- // entirely tangential object is returned.
- function FixedQueue( size, initialValues ){
-
- // If there are no initial arguments, default it to
- // an empty value so we can call the constructor in
- // a uniform way.
- initialValues = (initialValues || []);
-
- // Create the fixed queue array value.
- var queue = Array.apply( null, initialValues );
-
- // Store the fixed size in the queue.
- queue.fixedSize = size;
-
- // Add the class methods to the queue. Some of these have
- // to override the native Array methods in order to make
- // sure the queue lenght is maintained.
- queue.push = FixedQueue.push;
- queue.splice = FixedQueue.splice;
- queue.unshift = FixedQueue.unshift;
-
- // Trim any initial excess from the queue.
- FixedQueue.trimTail.call( queue );
-
- // Return the new queue.
- return( queue );
-
- }
-
-
- // I trim the queue down to the appropriate size, removing
- // items from the beginning of the internal array.
- FixedQueue.trimHead = function(){
-
- // Check to see if any trimming needs to be performed.
- if (this.length <= this.fixedSize){
-
- // No trimming, return out.
- return;
-
- }
-
- // Trim whatever is beyond the fixed size.
- Array.prototype.splice.call(
- this,
- 0,
- (this.length - this.fixedSize)
- );
-
- };
-
-
- // I trim the queue down to the appropriate size, removing
- // items from the end of the internal array.
- FixedQueue.trimTail = function(){
-
- // Check to see if any trimming needs to be performed.
- if (this.length <= this.fixedSize){
-
- // No trimming, return out.
- return;
-
- }
-
- // Trim whatever is beyond the fixed size.
- Array.prototype.splice.call(
- this,
- this.fixedSize,
- (this.length - this.fixedSize)
- );
-
- };
-
-
- // I synthesize wrapper methods that call the native Array
- // methods followed by a trimming method.
- FixedQueue.wrapMethod = function( methodName, trimMethod ){
-
- // Create a wrapper that calls the given method.
- var wrapper = function(){
-
- // Get the native Array method.
- var method = Array.prototype[ methodName ];
-
- // Call the native method first.
- var result = method.apply( this, arguments );
-
- // Trim the queue now that it's been augmented.
- trimMethod.call( this );
-
- // Return the original value.
- return( result );
-
- };
-
- // Return the wrapper method.
- return( wrapper );
-
- };
-
-
- // Wrap the native methods.
- FixedQueue.push = FixedQueue.wrapMethod(
- "push",
- FixedQueue.trimHead
- );
-
- FixedQueue.splice = FixedQueue.wrapMethod(
- "splice",
- FixedQueue.trimTail
- );
-
- FixedQueue.unshift = FixedQueue.wrapMethod(
- "unshift",
- FixedQueue.trimTail
- );
-
-
-
- // -------------------------------------------------- //
- // -------------------------------------------------- //
- // -------------------------------------------------- //
- // -------------------------------------------------- //
-
-
-
- // Create a fixed queue with some values.
- var friends = FixedQueue( 3, [ "Sarah", "Kit" ] );
-
- console.log( "Initial Values" );
- console.log( friends );
-
- // Add 2 items to the head.
- friends.unshift( "Tricia", "Anna" );
-
- console.log( "Add [ Tricia, Anna ] to head." );
- console.log( friends );
-
- // Add 2 items to the tail.
- friends.push( "Kim", "Joanna" );
-
- console.log( "Add [ Kim, Joanna ] to tail." );
- console.log( friends );
-
- // Add explicit value outside array.
- friends[ 5 ] = "Nancy";
-
- console.log( "Add [ Nancy ] out of bounds (explicitly)." );
- console.log( friends );
-
- // Add another item to the tail.
- friends.push( "Becca" );
-
- console.log( "Add [ Becca ] to tail." );
- console.log( friends );
-
-
- </script>
-
- </head>
- <body>
- <!-- Left intentionally blank. -->
- </body>
- </html>
In the above code, I am creating a FixedQueue() of max-length, 3. Then, I'm using a variety of mutation methods to change the queue values. When we run the above code, we get the following console output:
Initial Values
["Sarah", "Kit"]
Add [ Tricia, Anna ] to head.
["Tricia", "Anna", "Sarah"]
Add [ Kim, Joanna ] to tail.
["Sarah", "Kim", "Joanna"]
Add [ Nancy ] out of bounds (explicitly).
["Sarah", "Kim", "Joanna", undefined, undefined, "Nancy"]
Add [ Becca ] to tail.
[undefined, "Nancy", "Becca"]
As you can see, using Array class methods like push() and unshift() maintain a max-length of 3 items. But, when we used bracket notation to explicitly set an index value outside of the fixed-length boundaries, the length breaks. If we use other class methods after the "breakage", however, the max-length of the array is, once again, restored.
This was mostly just a fun thought experiment. I love the idea of creating custom classes / data types in JavaScript. Of course, if I really wanted to get elegant, I'd proxy all of the Array methods to make sure that things like slice() and concat() returned FixedQueue() instances rather than arrays.
Reader Comments
"The other day, I was laying in bed thinking about JavaScript Arrays." - hah, i love it! :)
great blog, I just found it and will be tuning in!
I don't know, you kind of had me at "Javascript Arrays". I got very distracted, and try as I might, I read the rest of it and couldn't really concentrate on much. The fact that I have distraction problems anyway doesn't help. The reason is, a couple of years ago, I was having a problem with Javascript Arrays. I typed "Javascript Arrays" into the google search, and came up with a page about Javascript Arrays (I guess), which had a picture of a top-heavy brunette in a bikini. Now, whenever I hear (or read) the words "Javascript Arrays", the picture of that top-heavy brunette in a bikini pops into my head, and I can't concentrate on much else. :-P It's ruined me for life. (note: I can't find that same page now, it must've been taken down.)
indeed very useful. unlike coldfusion, everything needs to be built to be used in Javascript. everytime developers start coding in javascript, they would first hit google and try and grab some code.
This example certainly shows the way on how a developer can start building his own data-structures in JS. We can extend this to single linkedlist, double linkedlist, etc.
Excellent stuff !! thanks Ben.
@Ben, Pretty cool, reminds me of a similar assignment we had one of the intro CS courses in college where we had to limit the size of the array, but the index bounds weren't always 0 to n, they could be any range decided by the prof when he tested it.
Also, thanks for the article. I didn't know about the proxies in javascript, and wow are they intriguing.
@Anna, granted, your past work experiences may make you more qualified to say this than when I do, but I still love the fact that if you can't find it, it must not exist :)
@Ben, Thanks for this! I have found a use for it already. I am creating a widget that detects and fires a "shake" event (drag it left and right or up and down with the mouse) and I only want to check the last (n) direction changes to see if they fall within the (time_threshold). This needs to be constantly updated until a shake is fired or detection ceases.
@Andrew,
Thanks my man! Glad you enjoyed it :D
@Anna,
The way you described that site, it wouldn't surprise me if it was my website :P
@Ananthakrishnan,
I think building data structures is a lot of fun and can be very useful. On the one hand, it really forces you to think about how the native language works and how the native classes can be extended. But also, they can provide some really useful functionality!
@Ken,
When I took CompSci 15 (Data Structures), I think we had to all kinds of stuff with linked-lists and bi-directional lists. I'm pretty sure we were using C++ at the time. That's basically the last time I every had to compile code :D Everything these days (that I use) seems to be either interpreted (ex. JavaScript) or compiled behind the scenes (ex. ColdFusion).
I don't know much about the proxies either and from the few articles that I looked at, they seem massively complex :) Hopefully more stuff will show up on the radar.
@Alex,
Sounds awesome! That's exactly the kind of scenario I had in my head - last N instances of something. That way, you can just keep push()ing and don't have to worry about maintenance.
@Ken... :) right...if I can't find it, it doesn't exist. Oh. Wait a minute. That means there is a whole heck of a lot of stuff out there that doesn't exist (in spite of my previous abilities of being able to find a lot of stuff)
@Alex, that sound pretty cool, and something like I would be trying to do. I like those JS's where you chase the thingies around the page with the mouse. Those are always fun and interesting.
@Ben, as long as she was a brunette. :P I'm sorry, I just happen to have a thing for brunettes. :)
Cool site
Hey Ben.
This looks pretty nice. I was just about to try to do something like this for my JsTrace (jstrace.codeplex.com) object's internal message storage
Is your code under any particular license? JsTrace is dual under GPL 2 and MIT. I was wondering if I may use this in there.
If so, how would you like me to credit you?
If not, that's cool too.
Thanks for the interesting read...
Tom
P.S. I think about code in bed all the time.. thus my blog name :)
