The JavaScript STL (Standard Template Library). Part 2 | WebReference

The JavaScript STL (Standard Template Library). Part 2

The JavaScript STL (Standard Template Library). Part 2

The list collection

The list collection is organized as a linked list of nodes that hold references to the values stored in the list (see graphic).

The head and tail nodes act as sentinels which simplifies the code. They also act as convenient places to represent one position past the last item in the list as required by the end() and rend() properties.

 


//=============================================
// STDList
// - an ordered container
// - reversible
function STDList()
{
  this.head = {item:"head",prev:null,bSentinel:true};
  this.tail = {item:"tail",tail:null,bSentinel:true};
  this.clear();
}
STDList.prototype.type = "list";
STDList.prototype.createNode = function(item)
{
  // create a node containing the item
  return {item:item,prev:null,next:null};
}
STDList.prototype.clear = function()
{
  // remove all elements from list
  this.head.next = this.tail;
  this.tail.prev = this.head;
  this.nSize = 0;
}

The list constructor initializes itself with head and tail sentinel nodes. They are not counted as part of the list as they don't represent values. Values are stored in the list using "container" nodes so that the forward and backward links may be maintained without modifying the value in any way which can be important if the value is stored in more than one list. A "type" property is initialized in the prototype which identifies the class of container and is useful for work with iterators.

 


STDList.prototype.insertNode = function(node,prev,next)
{
  // insert a node between prev and next nodes
  prev.next = node;
  node.prev = prev;
  next.prev = node;
  node.next = next;
  this.nSize++;
}
STDList.prototype.removeNode = function(node)
{
  // remove a node from its current position
  node.prev.next = node.next;
  node.next.prev = node.prev;
  this.nSize--;
}

The insertNode() and removeNode() methods provide the means to add and remove nodes from any position. Notice how having head and tail sentinels ensures that every value node will have a previous and a next node so there is no need to test these values.

 
STDList.prototype.iterator = function(node,bForward)
{
  if ( arguments.length == 1 ) bForward = true;
  return new STDLinkIterator(this,node,bForward,this.type);
}  
STD.prototype.isIterator = function(it,bMyType,bMine)
{
  // test whether it is an iterator,
  // options: if it is also a list type, if it is for this list
  if ( !it ) return false;
 
  // assumes all iterators have the following property   if ( !it.isIterator ) return false;
 
  // also that to be the same type, it has a type property
  if ( bMyType && (it.type != this.type) ) return false;
 
  // and to be contained in this, it has a container property
  if ( bMine && (it.container !== this) ) return false;
 
  return true;
}
STDList.prototype.isIterator = STD.prototype.isIterator;
 

The iterator() and isIterator() methods are convenient methods for creating and testing for an iterator. By convention, the JavaScript STL iterators all contain "isIterator" and "type" properties so that the generic function STD.prototype.isIterator may be used to identify them.

The isIterator() method is used extensively in the JavaScript STL code to implement the function overloading used extensively by collections. As an example, take the assign() method. This function takes two arguments named "a" and "b" which can represent either a range [a,b) or a count "a" of "b" values. A quick test at the start of the function using isIterator() on "a" and "b" is sufficient to distinguish which version of the function the caller intends:

 


STDList.prototype.assign = function(a,b)
{
  // replace list contents with inputs
  <code removed for brevity >
  if ( this.isIterator(a) && this.isIterator(b) )
  {
     // insert range [a,b)
     <code removed for brevity >
  }
  else
  {
     // insert value b, a times
     <code removed for brevity>
  }
}

Since the rest of the STDList code doesn't have any major surprises, I will move on to the next container. For further information on the list, please refer to the source code.

The vector collection

The vector collection is modeled as an array of values, although unlike the JavaScript array, the items are contiguous; there are no gaps in the indexes. Items may be added and removed quickly from the end of the vector but performance can be poor when inserted or removed from anywhere else. The main advantage with the vector is the ability to access values randomly using the numerical index.

 


//=============================================
// STDVector
function STDVector()
{
  this.data = new Array();
  this.nBegin = 0;
  this.nEnd = 0;
  this.type = "vector";
}

The STDVector constructor creates a new JavaScript Array object and initializes the begin and end positions to zero. These positions control how values are accessed in the vector and are also used to determine the number of elements stored.

 


STDVector.prototype.iterator = function(nPos,bReverse)
{
  bForward = arguments.length == 1 ? true : bForward;
  return new STDVectorIterator(this,nPos,bForward,this.type);
}
STDVector.prototype.isIterator = STD.prototype.isIterator;

As with the list, the vector also implements iterator() and isIterator() methods which work in comparable ways to the list versions.

STDVector.prototype.at = function(pos)
{
  return this.data[pos+this.nBegin];
}

The specific advantage of the vector over the list is the ability to randomly access each item by position. The at() method demonstrates this:

STDVector.prototype.push_back = function(value)
{
  this.data[this.nEnd++] = value;
}
STDVector.prototype.pop_back = function()
{
  if ( this.nEnd > this.nBegin ) delete this.data[--this.nEnd];
}

The only way to add and remove elements efficiently to/from a vector is at the end. The methods push_back() and pop_back() provide this functionality using the same interface as used in the list. Inserting elements anywhere else requires many of the items already in the vector to be moved to a different position.

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

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