Home / Programming / javascript / gr / column15

The JavaScript STL (Standard Template Library). Part 3

Finally, the insert() function allows the iterator to act as an output iterator. Note that after the item has been inserted, the iterator points to the newly inserted item.

Sorted collections

The last article introduced three ordered collections; list, vector and deque. By ordered I mean that the elements are positioned within the collection in the order in which they are inserted. Sorted collections, as the name suggests, store items in some predefined order. The order is defined using the functor called "less" (see Part 1 for a discussion on functors). If one item is considered to be less than another or less.fn(item1,item2) returns true, then that item will be placed before the other. Where the collection allows duplicates, the order is undefined.

STL offers four basic sorted collections; set, map, multiset and multimap. A set is a sorted collection of unique values; a map is a collection of unique key-value pairs sorted by key. The multiset and multimap versions are like set and map but with duplicates allowed.

The most common sorting mechanism used in STL for these collections is a structure called a Red-Black Tree (there is plenty of documentation available about red-black trees on the Internet so I won't say any more about them here). The behaviour of the four collection types is encapsulated in the JavaScript class STDTree:

 

function STDTree()

{

}

 

There's nothing to do in the STDTree constructor as the construction is handled by the four "derived" collections. In fact the STDTree() function will never be called (more on this later) and is only used to attach a number of prototype properties…

 

STDTree.prototype.initialise = function()

{

  // initialise the tree.

  this.tree = new RBTree(this.less);

}

 

The STDTree object still needs to be initialized, so the initialise() function performs this task and will be called by the constructors of the "concrete" collection classes.

 

STDTree.prototype.createItem = function(key)

{

  return key;

}

At times, the STDTree code needs to be able to construct an item object from a supplied key. This is so that the tree can compare a key and an item stored within the collection. For sets and multisets, the stored items are the keys so the default version shown here which simply returns the key is sufficient. Maps and multimaps require a more complex version (see later for details).

 

STDTree.prototype.iterator = function(node,bForward)

{

  if ( arguments.length == 1 ) bForward = true;

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

}

STDTree.prototype.isIterator = STD.prototype.isIterator;

 

Like other STD collections, the STDTree supports iterators to provide access to its items. The red-black tree implementation links each item as a doubly linked list with sentinels at each end so rather then implement a new iterator class, the iterator() function reuses STDLinkIterator.

 

STDTree.prototype.lower_bound = function(key)

{

  var node = this.tree.lower_bound(this.createItem(key));

  if ( node ) return this.iterator(node);

  else return this.iterator(+1);

}

The lower_bound() function is a central concept in the STDTree code. It returns an iterator to the smallest item in the collection with a key not less than some specified value. The implementation of the red-black tree guarantees that this will complete in logarithmic time (O(log(N))).

 

STDTree.prototype.find = function(key)

{

  // return iterator pointing to matching item, or end() if not found

  var item = this.createItem(key);

  var lb = this.tree.lower_bound(item);

  if ( this.less.fn(item,lb.item) ) return this.end();

  else return this.iterator(lb);

}

The find() function returns an iterator to an item in the collection specified by a key or the end sentinel if not found. The implementation of find() uses lower_bound() to find the node. If the key value is less than the lower bound, then the item is not in the list so the end() function is used to return the end sentinel.

 

STDTree.prototype.upper_bound = function(key)

{

  var node = this.tree.upper_bound(this.createItem(key));

  if ( node ) return this.iterator(node);

  else return this.iterator(+1);

}

The upper_bound() function is very similar to lower_bound() with the exception that it returns the smallest item with a key greater than the value.

 

STDTree.prototype.count = function(key)

{

  // count the number of items that match key

  var lb = this.lower_bound(key);

  var ub = this.upper_bound(key);

  return ub.minus(lb);

}

The count() function counts how many items in the collection have a key of some specified value. This is done by finding both the upper bound and the lower bound and calculating the distance between them using the minus() function on the iterators.

The insert() function must cater to a number of different situations. Not only are there three different overloads to insert a single value, a value with a hint and a range of values, the STDTree code must also distinguish between collections that can allow duplicate keys (multiset and multimap) and those that can't (set and map).

If a hint is supplied, its tested to ensure that the new item falls between the hint and the node following the hint. If not, the hint is ignored.

Where duplicates are not allowed, insert() will first attempt to find a matching item either using the hint or the lower_bound() function. If a match is found, the new item is rejected.

 

[previous][next]