| home / programming / javascript / gr / column17 / 1 |    [previous][next] |
|
|
|
The map, multimap, set and multiset classes introduced in Part 3 shared enough behaviour to make it worthwhile implementing a base class (called STDTree) and using a form of JavaScript inheritance that uses this implementation in the concrete classes. Similarly, hash_map, hash_multimap, hash_set and hash_multiset also behave very much the same, so the majority of their implementations will be provided by the class STDEXTHash.
The basis of the STDEXTHash implementation is the JavaScript Array. Conveniently, the return value of the hash function, an integer, works very nicely as an index into an array. The JavaScript Array class itself typically uses a form of hashing to store and retrieve elements so it's an ideal container for the STDEXTHash class.
//=============================================================================
// STDEXTHash
// basic hash based associative container.
// assumed member list:
// this.createNode() - create a node from a value with the
following members
// node.item - the item
// node.key - the key used for
hashing and comparisons
// node.next & node.prev -
initially set to null
// this.less - comparison functor to determine ordering
within a hash bucket
// this.hash - hash functor to determine to which hash
bucket a key belongs
// this.type - string identifying the class
function STDEXTHash()
{
}
Like the STDTree class, the STDEXTHash class constructor does nothing as it will never be called. Instead, an initialize function is defined that the four concrete hash classes will call from their constructors...
STDEXTHash.prototype.initialise = function(hash,less)
{
// assign appropriate hash and less functors
this.hash = hash ? hash : STDEXT.prototype.hash;
this.less = less ? less : STD.prototype.less;
// create the hash-indexed collection
this.bucket = new Array();
// add list sentinels
this.head = {item:"head",prev:null,bSentinel:true};
this.tail = {item:"tail",tail:null,bSentinel:true};
this.head.next = this.tail;
this.tail.prev = this.head;
// keep track of count
this.nCount = 0;
}
The initialize function takes a hash and less functor as arguments, if either of them is null, it substitutes standard ones in their place. Items in the hashed collection are contained within nodes which are linked together in a list structure. Sentinels are used at the head and tail to bound the elements. Finally a count is initialized to keep track of the number of elements stored within the collection.
While much of the STDEXTHash code is similar to the STDTree code, the hashed arrangement of items in the collection requires some differences...
STDEXTHash.prototype.count = function(key)
{
// count the number of items that match key
var node = this.lower_bound(key).node;
var nCount = 0;
var nHash = this.hash.fn(key);
while ( !node.bSentinel &&
(this.hash.fn(node.key) == nHash)
&&
!this.less.fn(key,node.key)
)
{
nCount++;
node = node.next;
}
return nCount;
}
The count() method counts the number of items that have a specified key. After retrieving the first node by calling this.lower_bound(key), the list is iterated through until either the node's hash value changes or its key value is greater. Since all the items stored within a single hash bucket are held in ascending order, once a node is found with a greater key, the search can stop.
STDEXTHash.prototype.find
= function(key)
{
var nIndex = this.hash.fn(key);
var node = this.bucket[nIndex];
if ( !node ) return
this.end();
while ( !node.bSentinel
&&
(this.hash.fn(node.key) == nIndex)
&&
this.less.fn(node.key,key)
)
{
node = node.next;
}
if ( (this.hash.fn(node.key) == nIndex)
&&
!this.less.fn(key, node.key) ) return this.iterator(node);
else return this.end();
}
The find method returns an iterator to the first element that matches a specified key, or end() if none exists. The first step is to calculate the hash index from the key and look inside the bucket at that index. If the bucket has items inside, the nodes are searched in sequence until either the hash value changes or the key is found.
STDEXTHash.prototype.insertImpl
= function(value)
{
var node = this.createNode(value);
var nIndex = this.hash.fn(node.key);
if ( this.bucket[nIndex] )
{
// find the first item in this bucket not less
than value
var pNode = this.bucket[nIndex];
while ( (this.hash.fn(pNode.key) == nIndex)
&&
this.less.fn(pNode.key,node.key)
)
{
pNode = pNode.next;
}
// if not multi container and key exists
already, return it
if ( !this.bMultiContainer && !this.less.fn(node.key,pNode.key) )
{
return {first:pNode,second:false};
}
// if head of bucket, adjust
bin
if ( pNode === this.bucket[nIndex] ) this.bucket[nIndex] = node;
// insert in list just before
pNode
this.insertNode(node, pNode.prev,
pNode);
}
else
{
this.bucket[nIndex] =
node;
// insert at tail of
list
this.insertNode(node, this.tail.prev,this.tail);
}
// return new node.
return {first:node,second:true};
}
Like STDTree.insertImpl(), the insertImpl() method assists the insert() method with the insertion of new elements into the collection. It first calculates the hash value and inspects the bucket at that position. If empty, then the algorithm is simple; assign the bucket to the new node and insert at the tail of the linked list.
If there are nodes in the bucket, then the new element must be inserted in order by iterating through the linked list until either the correct position is found or the list moves on to a new hash bucket. At this point, the collection must also decide whether to reject duplicate keys (hash_map and hash_set) or keep them (hash_multimap and hash_multiset). If the new element is at the head of the bucket, the bucket entry is assigned. Finally, the node is inserted into the list between the old bucket head and the previous node.
| home / programming / javascript / gr / column17 / 1 | [previous][next] |
Legal Notices, Licensing, Reprints, Permissions, Privacy Policy.
Advertise | Newsletters | Shopping | E-mail Offers | Freelance Jobs 
URL: http://webreference.com/programming/javascript/gr/column17/1
