Home / Programming / javascript / gr / column15

The JavaScript STL (Standard Template Library). Part 3

Concrete Classes

The STDTree class provides the base implementation of all four concrete tree based collections; set, multiset, map and multimap. All that's required now is for each "concrete" class to specify the particular properties that distinguish each one from the others.

 

function STDSet(less)

{

  // initialise map settings

  this.type = "set";

  if ( less ) this.less = less;

  else this.less = STD.prototype.less;

  this.bMultiContainer = false;

 

  // initialise STDTree settings

  this.initialise();

}

// inherit behaviour from STDTree

STDSet.prototype = STDTree.prototype;

The STDSet class implements provides the behaviour of the set collection. Its constructor argument is a "less" functor which is used to determine the ordering of items within the set. Note the last line in the code above which sets the prototype of the STDSet class to the STDTree's prototype. This has the effect of making all the functions and properties of STDSet the same as STDTree and is the closest that JavaScript gets to supporting class inheritance. All that's required in the constructor is to initialize this.less, specify this.bMultiContainer to be false and call the STDTree's initialize() function.

 

function STDMultiSet(less)

{

  // initialise map settings

  this.type = "multiset";

  if ( less ) this.less = less;

  else this.less = STD.prototype.less;

  this.bMultiContainer = true;

 

  // initialise STDTree settings

  this.initialise();

}

// inherit behaviour from STDTree

STDMultiSet.prototype = STDTree.prototype;

The STDMultiSet class is almost identical to the STDSet with the exception that this.bMultiContainer is assigned true.

The two map classes are associative containers that associate keys and values together so the items stored within these collections is made of two parts (by convention they're called "first" and "second"). By definition, the less functor used in maps and multimaps operates only on the key. There needs to be some way to translate the items (which are stored as key-value pairs) into keys or the comparisons won't work. The STDMapLess functor performs this translation.

 

function STDMapLess(less)

{

  if ( less ) this.less = less;

}

STDMapLess.prototype.fn = function(a,b)

{

  return this.less.fn(a.first,b.first);

}

STDMapLess.prototype.less = STD.prototype.less;

The constructor accepts an optional supplied less functor (the default behaviour is to use the standard version) defined to compare one key to another. This becomes the "internal" less functor. The fn() function takes the two map key-value items and extracts the keys from each and passes it into the internal less functor.

 

function STDMap(less)

{

  // add special map behaviour

  this.createItem = STDMap_createItem;

  this.key_comp = STDMap_key_comp;

  this.value_comp = STDMap_key_comp;

 

  // initialise map settings

  this.type = "map";

  this.less = new STDMapLess(less);

  this.bMultiContainer = false;

 

  // initialise STDTree settings

  this.initialise();

}

 

// inherit behaviour from STDTree

STDMap.prototype = STDTree.prototype;

The STDMap constructor looks a little different from the STDSet one. The less functor is assigned using the STDMapLess wrapper and three of the STDTree functions (createItem(), key_comp() and value_comp()) have been overridden.

 

STDMap_createItem = function(key,value)

{

  return {first:key,second:value};

}

STDMap_key_comp = function()

{

  return this.less.less;

}

The createItem() function is used by the STDTree code to generate an item from a key. The STDMap version also accepts a value argument but this will be undefined when called from the STDTree code.

The key_comp() and value_comp() functions must return the less functor that compares keys and not the STDMapLess wrapper object so a special implementation of these functions is included.

 

function STDMultiMap(less)

{

  // add special map behaviour

  this.createItem = STDMap_createItem;

  this.key_comp = STDMap_key_comp;

  this.value_comp = STDMap_key_comp;

 

  // initialise map settings

  this.type = "multimap";

  this.less = new STDMapLess(less);

  this.bMultiContainer = true;

 

  // initialise STDTree settings

  this.initialise();

}

 

// inherit behaviour from STDTree

STDMultiMap.prototype = STDTree.prototype;

The STDMultiMap constructor is almost identical to the STDMap one with the only differences being a different value to this.type and a value of true for this.bMultiContainer.

 

Conclusion

In this article I've extended the JavaScript STL from my earlier article. The iterator concept was developed further and the STDLinkedIterator was discussed. Four new sorted collections were introduced; set, multiset, map and multimap. The implementations were sufficiently similar to allow implementing most of the code in a JavaScript "base" class and use prototype assignment to inherit the behaviour for each of the four concrete classes.

In the next issue on this thread, I'll introduce the hash based collections and have a look at some generic algorithms and how they interact with the rest of the JavaScript STL.

Disclaimer

While I've endeavoured to make this code browser compatible, I've only tested it with Internet Explorer (6.0) and Netscape (7.1). As this represents a large proportion of users it is enough for the purposes of this article.

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 www.silver-daggers.co.uk for more details. He can be reached via e-mail at [email protected]

Created: March 27, 2003
Revised: February 2, 2005

URL: https://webreference.com/programming/javascript/gr/column15/1