spacer

Webref WebRef   Sitemap · Experts · Tools · Services · Newsletters · About i.com

home / programming / javascript / gr / column13 / 1 To page 1current page
[previous]

Subject Matter Expert - Managed Services (PA)
Next Step Systems
US-PA-Wayne

Justtechjobs.com Post A Job | Post A Resume
Developer News
News Flash: Adobe Has iPhone Workaround
Adobe's Flash 10.1 Goes Mobile (Minus iPhone)
A Salute to Visionary CEOs


The JavaScript STL (Standard Template Library). Part 1

References

A reference in C++ is a kind of pointer variable; it points to (or references) a value in the computer’s memory. A C++ reference can be designed to reference any kind of value, which makes it a powerful tool for passing values inside a program without the burden of copying the value each time. A referenced value may also be modified through the reference, which allows functions to modify the values of arguments passed to them.

JavaScript variables can be thought of as references to objects. Even the simple types like Numbers, Strings and Booleans are modeled as objects with methods such as toString() and valueOf(). These simple types are immutable since there is no way to modify the value once it has been created; the illusion of changing variable values is maintained by creating a new ‘instance’ for each new value (in practice, JavaScript would be actually implemented this way but it's still useful to think in terms of the model).

To support the flexibility of references in the JavaScript STL, I considered two options; introduce a Reference class that would contain each value the calling code produces or provide mutator functions at every level to allow values to be changed. I decided to use the Reference class as it would give programmers the choice on whether to use them or not.

JavaScript STL 101

The most popular part of STL and indeed the first thing most people think of in STL is collections. The STL provides a rich assortment of collections with varying properties able to suit most situations. With consistency and standards in mind, STL collections have similar interfaces where methods of different collections do the same thing, in fact, they are identical. For example: the push_back(value) method, which appends a value to the end of the collection is supported on the three unsorted collections vector, deque and list. Any code that uses this function would work equally well with each type of collection, freeing the programmer to choose the container to fit the situation and even interchanging them at runtime.

The STL list is a linked list of values, which has been optimized for fast inserts and deletes both at the ends and anywhere in between, but it's not indexed so searching for items stored within the list will potentially require iterating over all elements in the list. On the other hand, the STL vector is organized as an array and optimized for random access to all its elements. It still offers fast inserts and deletes at the end of the vector but inserting and deleting anywhere else will suffer (since many as N items may need to be moved to make room for the new ones).

All STL collections provide iterators that (as the name suggests) allows for iterating through a range in the collection in some order. Ranges are written using the notation [first,last) which means starting with the element 'first' and include all elements up to but not including 'last.' This convention mirrors the standard for() loop in C++ and JavaScript where the starting value and one more than the last value are specified.

 
// a for() loop from zero, up to but not including ten: [0,10)
for ( i = 0; i < 10; i++ )

The STL containers implement the begin() method for the first element in the collection and end() for the upper bound. A for() loop can now be written that iterates through all elements in an STL collection:

 
// iterate through all elements in myList from begin(), up to but
// not including end()
for ( i = myList.begin(); !i.equal_to(myList.end()); i.increment() )

The code

At the head of the code is a class called "STD" that provides access to the JavaScript STL features.
 
// simulate the std namespace
function STD()
{
}
 
STD.prototype.list = function()
{
  return new STDList();
}
STD.prototype.vector = function()
{
  return new STDVector();
}
 

An instance of this class is created and named "std", which offers a runtime equivalent of the C++ namespace "std".

var std = new STD();

The features and functionality of the JavaScript STL code can be accessed as members attached to this instance. For example:

 
// create a new list
var myList = std.list();
 
// create a new vector
var myVector = std.vector();

Passing functions as arguments is a fundamental aspect of the STL. It makes sorting possible where the ordering is not obvious or could be arbitrary. The STL has gone one step further and built a specialized object often called a function object or “functor” for short. A functor is quite simply an object that has a function. I have included the following generic functors in the STD definition:

 
STD.prototype.equal_to =
{
  fn:function(a,b)
  {
     return a == b;
  }
};
STD.prototype.greater =
{
  fn:function(a,b)
  {
     return a > b;
  }
};
STD.prototype.greater_equal =
{
  fn:function(a,b)
  {
     return a >= b;
  }
};
STD.prototype.less =
{
  fn:function(a,b)
  {
     return a < b;
  }
};
STD.prototype.less_equal =
{
  fn:function(a,b)
  {
     return a <= b;
  }
};

The functors defined above are commonly used throughout the STL. To keep these functors as simple as possible, they all operate on two inputs and return a boolean value. This helps simplify other parts of the STL framework and can also improve performance. Many of the methods and algorithms in STL (e.g. sort) depend on using functors like these ones.

One big advantage of passing an object in place of a function pointer is that other information that may be relevant to the function can be bundled along with it. For example, say it was necessary to order a list of numbers according to how close they are to a given target and the target is not known until the program is run.

 
// ProximityFunctor: ranks values according to how close
// they are to some arbitrary target
function ProximityFunctor(target)
{
  this.target = target;
}
ProximityFunctor.prototype.fn = function(a,b)
{
  return Math.abs(a-this.target) < Math.abs(b-this.target);
}

The STDReference class allows values inside a collection to be modified without requiring internal knowledge of the collection:

 
STD.prototype.ref = function(value)
{
  return new STDReference(value);
}
 
//===========================================================
// STDReference
// - A reference to some value
// when it is necessary to modify the values contained inside
// a collection use this object
function STDReference(value)
{
  this.value = value;
}

Next week we'll look at The List Collection, The Vector Collection and The Deque Collection. Part two will also feature a download of the code. After part two, future installments will introduce more collections from the STL repertoire and delve deeper into how iterators can do more than just iterate.

About the Author

Guyon Roche is a freelance web developer in London, Great Britain. He specializes in Windows platforms with an interest in bridging the gaps between different technologies, visit http://www.silver-daggers.co.uk/ for more details. He can be reached via e-mail at guyon.roche@btinternet.com

home / programming / javascript / gr / column13 / 1 To page 1current page
[previous]

internet.commediabistro.comJusttechjobs.comGraphics.com

Search:

WebMediaBrands Corporate Info

Legal Notices, Licensing, Reprints, Permissions, Privacy Policy.
Advertise | Newsletters | Shopping | E-mail Offers | Freelance Jobs

webref The latest from WebReference.com Browse >
Building a Banking Application Home Page with OOP · Mixing Scripting Languages · Review: phpFox, a Social Networking CMS with all the Bells and Whistles
Sitemap · Experts · Tools · Services · Email a Colleague · Contact FREE Newsletters 
 The latest from internet.com
Enterprise 2.0: Social Networking in the Cloud · BroadSoft Marketplace Hastens Pace of Telephony Innovation · Review: HTC Hero for Sprint

Created: March 27, 2003
Revised: August 22, 2005

URL: http://webreference.com/programming/javascript/gr/column13/1