| home / programming / javascript / gr / column15 / 1 |   [previous] |
|
|
|
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.
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.
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.
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 guyonroche@silver-daggers.co.uk
| home / programming / javascript / gr / column15 / 1 | [previous] |
Legal Notices, Licensing, Reprints, Permissions, Privacy Policy.
Advertise | Newsletters | Shopping | E-mail Offers | Freelance Jobs 
URL: http://webreference.com/programming/javascript/gr/column15/1
