Home / Programming / javascript / gr / column15

The JavaScript STL (Standard Template Library) Part 3

In the first article, I introduced a JavaScript implementation of the C++ Standard Template Library and outlined three of the collections; list, vector and deque. In this article I delve deeper into the magic of iterators and introduce a new class of sorted collection that includes set, map, multiset and multimap.

Iterators can do more than just iterate

Previously we discovered how iterators are used in STL to identify an item or position or ranges of items within a collection. They still have a few tricks up their sleeves.

In principle, iterators can be thought of as pointers in that they point an item or position within a collection. In C++, pointers have a well defined "pointer arithmetic" that controls how pointers behave when used. To illustrate this behaviour and how it applies to STL, I will use iterators. Imagine that in a collection, each item can be labelled with a number to identify its position. The item at the front of the collection would have position 0, the second item has position 1 and so on. Incrementing the position moves forward to the next item in the collection and decrementing moves backwards to the previous item. Adding or subtracting a number N either moves N positions forwards or backwards within the collection (like incrementing or decrementing N times). Finally, subtracting one position from another results in the iterative distance between two positions or the number of increments or decrements required to get from one position to the other.

The C++ STL identifies a number of categories of iterator to reflect the behaviour that the iterator was designed to support; output, input, forward, bi-directional and random access. Output iterators provide a destination to store new data. An insert method allows a new item to be inserted at the current position. Input iterators provide a source of data. Forward iterators may be incremented, bi-directional iterators may be incremented and decremented and random access iterators allow increments and decrements over multiple positions.

The JavaScript STL supports the above behaviour using the following interface:

collection.begin()	The first position in the collection
collection.end()	One past the last position in the collection
iterator.increment()	Move one position forwards. Necessary for forwards iterators.
iterator.increment(N)	Move N positions forwards. Necessary for random access iterators.
iterator.decrement()	Move one position backwards. Necessary for bi-directional iterators.
iterator.decrement(N)	Move N positions backwards. Necessary for random access iterators.
iterator.minus(it)	Calculate the distance between one iterator and another. Necessary for random access iterators.
iterator.item	The item pointed to by the iterator. Necessary for input iterators.
iterator.insert()	A function to insert a new item at the position pointed to by the iterator. Necessary for output iterators.

While most of the collections in STL support iterators that fit most of those categories, it's useful to consider when using iterators in various contexts, especially when non-standard iterators are used. For example, a range of values may be inserted into a list using the following syntax:

 

// insert a range of values into a list

myList.insert(itBegin, itEnd);

So long as the input arguments "itBegin" and "itEnd" support all the behaviour of input iterators, the list will happily start with the value at itBegin, and increment until it reaches a position equal to itEnd. Consider the following example…

 

function DiceIterator(nValue)

{

  // generates random numbers from 1 to 6

  if ( arguments.count == 1 ) this.item = nValue;

  else this.item = Math.floor(Math.random() * 6) + 1;

}

DiceIterator.prototype.isIterator = true;

DiceIterator.prototype.increment()

{

  this.item = Math.floor(Math.random() * 6) + 1;

}

DiceIterator.prototype.equal_to(other)

{

  return this.item == other.item;

}

This iterator satisfies the conditions for a forwards input iterator; it supports an increment() method and maintains an item property. Imagine we needed to simulate a set of random dice rolls up to (but not including) a six:

 

var itBegin = new DiceIterator;

var itEnd = new DiceIterator(6);

myList.insert(itBegin, itEnd);

The DiceIterator makes this task almost trivial. The code above creates two iterators; itBegin is the input iterator which is used to generate the dice roll sequence, itEnd is the sentinel and identifies when to terminate the insertion. The call to myList.insert() does the rest.

STDLinkIterator

In a previous issue, I briefly introduced the STDLinkIterator class, which is used by the STDList collection to iterate over the items in a list. Let's have a closer look at how it works:

// STDLinkIterator

// An iterator for linked nodes

function STDLinkIterator(container,node,bForward,type)

{

  this.container = container;

  this.node = node;

  this.bForward = bForward;

  this.type = type;

 

  this.item = node.item;

}

 

The constructor of the STDLinkIterator requires a container, the node containing the item, a Boolean value to indicate which direction the iterator goes and a type.

 

STDLinkIterator.prototype.clone = function()

{

  return new STDLinkIterator(this.container,this.node,this.bForward,this.type);

}

 

Sometimes its useful to make a copy of an iterator, for example, while iterating through a list, a few of the iterator positions may be saved (copied) for use later. The clone() function is the best way to achieve this.

 

STDLinkIterator.prototype.isIterator = true;

All iterators in the JavaScript STL need to support an isIterator property so that overloaded functions or methods can distinguish between iterators and other types.

 

STDLinkIterator.prototype.incImpl = function(pos, nIncrement, bF)

{

  if ( bF ) while ( nIncrement-- && pos.next ) pos = pos.next;

  else while ( nIncrement-- && pos.prev ) pos = pos.prev;

  return pos;

}

STDLinkIterator.prototype.increment = function(nIncrement)

{

  if ( arguments.length == 0 ) nIncrement = 1;

  this.node = this.incImpl(this.node, nIncrement, this.bForward);

  this.item = this.node.item;

}

STDLinkIterator.prototype.decrement = function(nDecrement)

{

  if ( arguments.length == 0 ) nDecrement = 1;

  this.node = this.incImpl(this.node, nDecrement, !this.bForward);

  this.item = this.node.item;

}

Increments and decrements are the most basic operation of an iterator. The incImpl() function provides the implementation for the increment() and decrement() functions. While the STDLinkIterator is not specifically a random access iterator, it does support increments and decrements over more than one position at a time. However, the time order for such operations is linear (O(N)).

 

STDLinkIterator.prototype.minus = function(other)

{

  var n = 0;

  var pos = other.node;

  while ( (pos !== this.node) && !pos.bSentinel )

  {

     n++;

     pos = this.incImpl(pos, 1, this.bForward);

  }

  return n;

}

 

The STDLinkIterator also supports a minus() function, which measures the number of increments required to move from one position to another. Like the increment and decrement, this operation is linear and may involve iterating over the whole collection.

 

STDLinkIterator.prototype.equal_to = function(other)

{

  return (this.node === other.node);

}

The equal_to() function is used to test whether one iterator is pointing to the same item as another. This is particularly important for loops that are terminated by comparing whether an iterator is at the end or not.

 

STDLinkIterator.prototype.insert = function(value)

{

  var it = this.container.insert(this,value);

  this.node = it.node;

  this.item = it.item;

}

 

[next]