| home / programming / javascript / gr / column14 / 1 |   [next] |
|
|
|
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 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.
| home / programming / javascript / gr / column14 / 1 | [next] |
Jupitermedia Corporation has two divisions: Jupiterimages and JupiterOnlineMedia
Legal Notices, Licensing, Reprints, Permissions, Privacy Policy.
Advertise | Newsletters | Tech Jobs | Shopping | E-mail Offers
Created: March 27, 2003
Revised: August 29, 2005
URL: http://webreference.com/programming/javascript/gr/column14/1
