JavaScript STL, Part 4 - WebReference.com-

Copy this text and save into a file called "RBTree.js"

//<script type="text/javascript">//<script type="text/javascript">
//
// RBTree.js
//
// implementation of a red black tree

// logical xor of b1 and b2
function xor(b1,b2)
{
	return (b1 && !b2) || (!b1 && b2);
}

function RBTree(less)
{
	this.less = less;
	this.clear();
}
RBTree.prototype.clear = function()
{
	this.root = null;
	this.nSize = 0;
	
	// head and tail are sentinel nodes not stored in the tree
	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;
}
RBTree.prototype.insert = function(value,hint)
{
	var node = new RBTreeNode(value,this);

	// account for size
	if ( !this.nSize++ )
	{
		this.root = node;
		node.listInsert(this.head,this.tail);
		node.parent = null;
		return node;
	}

	var pos = this.root;
	
	// if hint exists, assume upper bound - 1
	if ( hint && hint.bSentinel )
	{
		if ( hint === this.head ) hint = hint.next;
		else if ( hint === this.tail ) hint = hint.prev;
		else hint = null;
	}
	if ( hint && (hint.tree === this) ) pos = hint;

	pos.insert(node, this.less);

	node.balance();

	// make root node black
	this.root.bBlack = 1;

	return node;
}

RBTree.prototype.remove = function(node)
{
	// remove the node from the tree returning the node that follows.

	// protect and serve
	if ( node.tree !== this ) return this.tail;
	
	// account for size
	if ( --this.nSize == 0 )
	{
		this.root = null;
		node.listRemove();
		return this.tail;
	}
	
	var next = node.next;
		
	// case 1: node has two children or is root
	if ( !node.parent || (node.left.bNode && node.right.bNode) )
	{
		// find inorder predecessor (or successor) and swap values
		// after deletion, value order will be preserved
		var sub = node.prev;
		if ( !sub )
		{
			sub = node.next;
			next = node;
		}
		node.item = sub.item;
		node = sub;
	}
	
	// node now has at most one child node

	// remove node from linked list
	node.listRemove();

	// p is parent of node
	var p = node.parent;

	var bLeft = (node === p.left);

	// c is child of node
	var c = node.left.bNode ? node.left : node.right;
	
	// move c into place
	c.parent = node.parent;
	if ( bLeft ) p.left = c; else p.right = c;
	
	// node is red
	if ( !node.bBlack )
	{
		// this is easy, colour c black and return
		c.bBlack = 1;
		return next;
	}
	
	// node is black, add to c and fix
	c.bBlack++;
	
	if ( c.bBlack > 1 ) c.fix();

	return next;
}

//Returns an iterator to the first element in a set that with a key that is
//greater than a specified key.
RBTree.prototype.upper_bound = function(value)
{
	if ( !this.root ) return this.tail;
	return this.root.upper_bound(value,this.less);
}

//Returns an iterator to the first element in a map that with a key value that is 
//equal to or greater than that of a specified key.
RBTree.prototype.lower_bound = function(value)
{
	if ( !this.root ) return this.tail;
	else return this.root.lower_bound(value, this.less);
}


function RBTreeNode(value,tree)
{
	this.item = value;
	this.tree = tree;
	this.bBlack = 0; // default
	this.bNode = true;
	
	// add left and right sentinel nodes
	this.left = {parent:this,bBlack:1,bLeft:true,fix:RBTreeNode.prototype.fix};
	this.right = {parent:this,bBlack:1,bLeft:false,fix:RBTreeNode.prototype.fix};
}
RBTreeNode.prototype.rightmost = function()
{
	if ( this.right.bNode ) return this.right.rightmost();
	else return this;
}
RBTreeNode.prototype.leftmost = function()
{
	if ( this.left.bNode ) return this.left.leftmost();
	else return this;
}
RBTreeNode.prototype.listInsert = function(prev,next)
{	
	this.prev = prev;
	prev.next = this;
	
	this.next = next;
	next.prev = this;
}
RBTreeNode.prototype.listRemove = function()
{
	this.next.prev = this.prev;
	this.prev.next = this.next;
}
RBTreeNode.prototype.insertChild = function(prev,next,node)
{
	node.parent = this;
	node.listInsert(prev,next);
}
RBTreeNode.prototype.insert = function(node, less)
{
	// simple binary insertion
	if ( less.fn(node.item,this.item) )
	{
		if ( this.left.bNode ) this.left.insert(node,less);
		else this.insertChild(this.prev,this,this.left = node);
	}
	else
	{
		if ( this.right.bNode ) this.right.insert(node,less);
		else this.insertChild(this,this.next,this.right = node);
	}
}
RBTreeNode.prototype.balance = function()
{
	// walk up the tree preserving the red-black rules
	
	// p is parent
	var p = this.parent;

	// case 1: this is root node or parent is black
	if ( !p || (p.bBlack != 0) ) return;
	
	// g is grand parent
	var g = p.parent;
	
	// case 1b: p is root node
	if ( !g ) return;
	
	// record whether we are the left child
	var bLeft = (this === p.left);
	
	// and whether parent is a left child
	var bPLeft = (p === g.left);
	
	// u is uncle
	var u = (bPLeft ? g.right : g.left);
	
	// case 2: parent is red, uncle is black
	if ( u.bBlack != 0 )
	{
		if ( xor(bLeft,bPLeft) )
		{
			// case 2a: parent is different handed to this
			this.rotate();
			this.rotate();
		}
		else
		{
			// case 2b: parent is same handed as this
			p.rotate();
		}
		return;
	}

	// case 3: parent is red, uncle is red
	p.bBlack = 1;
	u.bBlack = 1;
	g.bBlack = 0;
	g.balance();
}

RBTreeNode.prototype.rotate = function()
{
	// p is parent
	var p = this.parent;
	
	// if this is root node, we can't rotate
	if ( !p ) return;
	
	// g is grand parent
	var g = p.parent;
	
	var bLeft = (this === p.left);
	
	if ( bLeft )
	{
		p.left = this.right;
		this.right.parent = p;
		this.right = p;
	}
	else
	{
		p.right= this.left;
		this.left.parent = p;
		this.left = p;
	}
	
	// set parents
	p.parent = this;
	this.parent = g;
	if ( g ) { if ( g.left === p ) g.left = this; else g.right = this; }
	else this.tree.root = this;
	
	// swap colours
	var bBlack = p.bBlack;
	p.bBlack = this.bBlack;
	this.bBlack = bBlack;
}
RBTreeNode.prototype.fix = function()
{
	// fix any colour inconsistancy
	
	// p is parent
	var p = this.parent;
	
	if ( !p )
	{
		this.bBlack = 1;
		return;
	}
	
	// s is sibling
	var s = (this === p.left) ? p.right : p.left;
	
	// case 1: black sibling with red child
	if ( s.bBlack && s.bNode )
	{
		var n = null;
		if ( !s.left.bBlack ) n = s.left;
		else if ( !s.right.bBlack ) n = s.right;
		if ( n )
		{
			// restructure
			this.bBlack = 1;
			n.bBlack = 1;
			if ( !xor((s===p.left),(n===s.left)) )
			{
				// s and n same handed
				s.rotate();
			}
			else
			{
				// s and n different handed
				n.rotate();
				n.rotate();
			}
			return;
		}		
	}
	
	// case 2: black sibling without (red) children
	if ( s.bBlack )
	{
		// recolour
		this.bBlack = 1;
		s.bBlack = 0;
		if ( ++p.bBlack > 1 ) p.fix();
		return;
	}
	
	// case 3: red sibling --> adjustment
	s.rotate();
	this.fix();
}

//Returns node of the first element in a set that with a key that is
//greater than a specified key.
RBTreeNode.prototype.upper_bound = function(value,less)
{
	if ( !less.fn(value,this.item) )
	{
		// value >= this.item
		if ( this.right.bNode ) return this.right.upper_bound(value,less);
		else return this.next;
	}
	else
	{
		// value < this.item
		if ( this.left.bNode ) return this.left.upper_bound(value,less);
		else return this;
	}
}

//Returns node of the first element in a map that with a key value that is 
//equal to or greater than that of a specified key.
RBTreeNode.prototype.lower_bound = function(value,less)
{
	if ( less.fn(this.item,value) )
	{
		// value > this.item
		if ( this.right.bNode ) return this.right.lower_bound(value,less);
		else return this.next;
	}
	else
	{
		// value <= this.item
		if ( this.left.bNode ) return this.left.lower_bound(value,less);
		else return this;
	}
}

//</script>

Copy this text and save into a file called "JSstl.js"

//<script type="text/javascript">

function STD()
{
	// Do nothing
}

STD.prototype.map = function(less)
{
	return new STDMap(less);
}
STD.prototype.multimap = function(less)
{
	return new STDMultiMap(less);
}
STD.prototype.set = function(less)
{
	return new STDSet(less);
}
STD.prototype.multiset = function(less)
{
	return new STDMultiSet(less);
}
STD.prototype.list = function()
{
	return new STDList();
}
STD.prototype.vector = function()
{
	return new STDVector();
}
STD.prototype.deque = function()
{
	return new STDDeque();
}
STD.prototype.equal_to = 
{
	fn:function(a,b)
	{
		return a == b;
	} 
};
STD.prototype.greater = 
{
	fn:function(a,b)
	{
		return a > b;
	} 
};
STD.prototype.greater_equal = 
{
	fn:function(a,b)
	{
		return a >= b;
	} 
};
STD.prototype.less = 
{
	fn:function(a,b)
	{
		return a < b;
	} 
};
STD.prototype.less_equal = 
{
	fn:function(a,b)
	{
		return a <= b;
	} 
};
// create a reference object referencing a value
STD.prototype.ref = function(v)
{
	return {value:v};
}
// create a functor to operate on references
STD.prototype.deRef = function(ftor)
{
	return { functor:ftor, fn:function(a,b){return this.functor(a.value,b.value);}};
}

// useful function to test whether an object is an iterator
STD.prototype.isIterator = function(it,bMyType,bMine)
{
	// test whether it is an iterator, 
	// options: if it is also a list type, if it is for this list
	if ( !it ) return false;
	
	// assumes all iterators have the following property
	if ( !it.isIterator ) return false;
	
	// also that to be the same type, it has a type property
	if ( bMyType && (it.type != this.type) ) return false;
	
	// and to be contained in this, it has a container property
	if ( bMine && (it.container !== this) ) return false;
	
	return true;
}

var std = new STD();

//=============================================================================
// 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;
}
STDLinkIterator.prototype.clone = function()
{
	return new STDLinkIterator(this.container,this.node,this.bForward,this.type);
}
STDLinkIterator.prototype.isIterator = true;
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;
}
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;
}
STDLinkIterator.prototype.equal_to = function(other)
{
	return (this.node === other.node);
}
STDLinkIterator.prototype.insert = function(value)
{
	var it = this.container.insert(this,value);
	this.node = it.node;
	this.item = it.item;
}

//=============================================================================
// STDTree
// basic associative container.
// wraps RBTree to provide more STL type interface

function STDTree()
{
}
STDTree.prototype.initialise = function()
{
	// initialise the tree.
	this.tree = new RBTree(this.less);
}
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;
STDTree.prototype.createItem = function(key)
{
	return key;
}
STDTree.prototype.begin = function()
{
	// return iterator at start of collection
	return this.iterator(this.tree.head.next);
}
STDTree.prototype.clear = function()
{
	// remove all items from collection
	this.tree = new RBTree(this.less);
}
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);
}
STDTree.prototype.empty = function()
{
	// return true if no items contained.
	return this.tree.nSize == 0;
}
STDTree.prototype.end = function()
{
	// return iterator one step beyond the last item
	return this.iterator(this.tree.tail);
}
STDTree.prototype.equal_range = function(key)
{
	// return lower and upper bounds of key
	var lb = this.lower_bound(key);
	var ub = this.upper_bound(key);
	return {first:lb,second:ub};
}
STDTree.prototype.eraseImpl = function(nBegin, nEnd)
{
	while ( nBegin !== nEnd )
	{
		nBegin = this.tree.remove(nBegin);
	}
	return nBegin;
}
STDTree.prototype.erase = function(a,b)
{
	// erase items from the collection
	if ( arguments.length == 0 ) return;

	if ( !this.isIterator(a,true,true) )
	{
		// a is a key
		var value = this.createItem(a);
		var lb = this.tree.lower_bound(value);
		var ub = this.tree.upper_bound(value);
		return this.iterator(this.eraseImpl(lb,ub));
	}
	
	// if b not specified, set it to one past a
	if ( arguments.length == 1 )
	{
		if ( !a.node.bSentinel ) return this.iterator(this.eraseImpl(a.node, a.node.next));
		else return this.end();
	}
	else
	{
		return this.iterator(this.eraseImpl(a.node, b.node));
	}
}
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);
}
STDTree.prototype.insertReturn = function(item, bIterator, bPair, bSecond)
{
	// private function to return the correct type of object for 
	// insert(). This can be either the item, an iterator to the
	// item, or a pair containing the item and a boolean value.
	if ( bIterator == undefined ) bIterator = false;
	if ( bPair == undefined ) bPair = false;
	if ( bSecond == undefined ) bSecond = false;
	if ( bIterator && bPair ) return {first:this.iterator(item),second:bSecond};
	else if ( bIterator ) return this.iterator(item);
	else return item;
}
STDTree.prototype.insertImpl = function(hint, value, bIterator, bPair)
{
	// private function to insert a value will an optionally supplied
	// hint position.

	// test hint
	if ( hint && this.less.fn(value,hint.item) ) hint = null;
	else if ( hint && !hint.next.bSentinel && this.less.fn(hint.next.item,value) ) hint = null;
	
	if ( this.bMultiContainer )
	{
		// always insert into multi container
		return this.insertReturn(this.tree.insert(value,hint),bIterator);
	}
	else
	{
		// test whether item or key is unique
		if ( !hint )
		{
			hint = this.tree.lower_bound(value);
			if ( !hint.bSentinel && !this.less.fn(value,hint.item) )
			{
				return this.insertReturn(hint, bIterator, bPair, false);
			}
			
			// by preference, chose the node just before the insertion point
			if ( !hint.bSentinel && !hint.prev.bSentinel ) hint = hint.prev;
		}
		else
		{
			if ( !this.less.fn(hint.item,value) )
			{
				return this.insertReturn(hint, bIterator, bPair, false);
			}
			if ( !hint.next.bSentinel && !this.less.fn(value,hint.next.item) )
			{
				return this.insertReturn(hint.next, bIterator, bPair, false);
			}
		}
		var node = this.tree.insert(value,hint);
		return this.insertReturn(node, bIterator, bPair, true);
	}
}
STDTree.prototype.insert = function(a,b)
{
	// insert item(s) into collection
	if ( arguments.length == 0 ) return;
	
	var node = null;
	var hint;
	if ( arguments.length == 1 )
	{
		// case 1: a is value type
		return this.insertImpl(null, a, true, true);
	}
	
	if ( this.isIterator(a) && this.isIterator(b) )
	{
		// case 2: a and b are input iterators. Insert [a,b)
		hint = null;
		a = a.clone();
		while ( !a.equal_to(b) )
		{
			hint = this.insertImpl(hint,a.item, false);
			a.increment();
		}
	}
	
	if ( this.isIterator(a,true,true) )
	{
		// case 3: a is a hint. Test and insert,
		return this.insertImpl(a.node,b,true, false);
	}
}
STDTree.prototype.key_comp = function()
{
	return this.less;
}
STDTree.prototype.lower_bound = function(key)
{
	var node = this.tree.lower_bound(this.createItem(key));
	return this.iterator(node);
}
STDTree.prototype.rbegin = function()
{
	return this.iterator(this.tree.tail.prev,false);
}
STDTree.prototype.rend = function()
{
	return this.iterator(this.tree.head,false);
}
STDTree.prototype.size = function()
{
	return this.tree.nSize;
}
STDTree.prototype.swap = function(other)
{
	var tree = this.tree;
	this.tree = other.tree;
	other.tree = tree;
	
	var less = this.less;
	this.less = other.less;
	other.less = less;
}
STDTree.prototype.upper_bound = function(key)
{
	var node = this.tree.upper_bound(this.createItem(key));
	return this.iterator(node);
}
STDTree.prototype.value_comp = function()
{
	return this.less;
}

//=============================================================================
// STDSet
// - an associative container
// - reversible
// - sorted
// - unique
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;

//=============================================================================
// STDMultiSet
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;


//=============================================================================
// STDMapLess
// helper class to STDMap
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;
//=============================================================================
// STDMap
// - a pair associative container (key and value)
// - reversible
// - sorted
// - unique
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;

STDMap_createItem = function(key,value)
{
	return {first:key,second:value};
}
STDMap_key_comp = function()
{
	return this.less.less;
}

//=============================================================================
// STDMultiMap
// - a pair associative container (key and value)
// - reversible
// - sorted
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;

//=============================================================================
// STDList
// - an ordered container
// - reversible
function STDList()
{
	this.head = {item:"head",prev:null,bSentinel:true};
	this.tail = {item:"tail",tail:null,bSentinel:true};
	this.clear();
}
STDList.prototype.type = "list";
STDList.prototype.createNode = function(item)
{
	// create a leaf node containing the item
	return {item:item,prev:null,next:null};
}
STDList.prototype.insertNode = function(node,prev,next)
{
	// insert a node between prev and next nodes
	prev.next = node;
	node.prev = prev;
	next.prev = node;
	node.next = next;
	this.nSize++;
}
STDList.prototype.removeNode = function(node)
{
	// remove a node from its current position
	node.prev.next = node.next;
	node.next.prev = node.prev;
	this.nSize--;
}
STDList.prototype.iterator = function(node,bForward)
{
	if ( arguments.length == 1 ) bForward = true;
	return new STDLinkIterator(this,node,bForward,this.type);
}
STDList.prototype.isIterator = STD.prototype.isIterator;
STDList.prototype.assign = function(a,b)
{
	// replace list contents with inputs
	this.clear();
	
	var i = this.head;
	var node;
	if ( this.isIterator(a) && this.isIterator(b) )
	{
		// insert range [a,b)
		while ( !a.equal_to(b) )
		{
			node = this.createNode(a.item);
			i.next = node;
			node.prev = i;
			i = node;	
			this.nSize++;
			a.increment();
		}
	}
	else
	{
		// insert value b, a times
		while ( a > 0 )
		{
			node = this.createNode(b);
			i.next = node;
			node.prev = i;
			i = node;	
			this.nSize++;	
		}
	}
	this.tail.prev = i;
	i.next = this.tail;
}
STDList.prototype.back = function()
{
	// return the last element (or undefined if there isn't one)
	return (this.nSize > 0) ? this.tail.prev.item : undefined;
}
STDList.prototype.begin = function()
{
	// return iterator at start of list
	return this.iterator(this.head.next);
}
STDList.prototype.clear = function()
{
	// remove all elements from list
	this.head.next = this.tail;
	this.tail.prev = this.head;
	this.nSize = 0;
}
STDList.prototype.empty = function()
{
	return this.nSize == 0;
}
STDList.prototype.end = function()
{
	return this.iterator(this.tail);
}
STDList.prototype.erase = function(begin,end)
{
	var a,b;
	a = begin.node;
	if ( this.isIterator(end) ) b = end.node;
	else b = a.next;

	var prev = a.prev;
	while ( a !== b )
	{
		this.nSize--;
		a = a.next;
	}
	prev.next = b;
	b.prev = prev;
}
STDList.prototype.front = function()
{
	// return value at start of list (or undefined if there isn't one)
	return (this.nSize > 0) ? this.head.next.item : undefined;
}
STDList.prototype.insert = function(where,a,b)
{
	var next = where.node;
	var prev = next.prev;
	// insert an item or items into the list
	if ( arguments.length == 2 )
	{
		node = this.createNode(a);
		this.insertNode(node,where.node.prev,where.node);
	}
	else
	{
		if ( this.isIterator(a) && this.isIterator(b) )
		{
			while ( !a.equal_to(b) )
			{
				node = this.createNode(a.item);
				this.insertNode(node,prev,null);
				a.increment();
			}
		}
		else
		{
			while ( a > 0 )
			{
				node = this.createNode(b);
				this.insertNode(node,prev,null);
				a--;
			}
		}
		next.prev = prev;
		prev.next = next;
	}
}
STDList.prototype.merge = function(right,less)
{
	// merge items from another list
	// both lists must already be ordered by less
	this.mergeItems(this.head,this.tail,
					this.head.next,this.tail,false,
					right.head.next,right.tail,true,
					less ? less : STD.prototype.less);
	
}
STDList.prototype.pop_back = function()
{
	// removes last element from list
	this.removeNode(this.tail.prev);
}
STDList.prototype.pop_front = function()
{
	// removes first element from list
	this.removeNode(this.head.next);
}
STDList.prototype.push_back = function(value)
{
	// add item to end of list
	var node = this.createNode(value);
	this.insertNode(node,this.tail.prev,this.tail);
}
STDList.prototype.push_front = function(value)
{
	// add item to front of list
	var node = this.createNode(value);
	this.insertNode(node,this.head,this.head.next);
}
STDList.prototype.rbegin = function()
{
	// return reverse iterator at end of list
	return this.iterator(this.tail.prev,false);
}
STDList.prototype.remove = function(value)
{
	// remove all elements that match a value
	var next;
	for ( var i = this.head.next; i != this.tail; i = next )
	{
		next = i.next;
		if ( this.equal_to.fn(i.item,value) ) this.removeNode(i);
	}
}
STDList.prototype.remove_if = function(pred)
{
	// remove all elements for which pred.fn(value) is true
	var next;
	for ( var i = this.head.next; i != this.tail; i = next )
	{
		next = i.next;
		if ( pred.fn(i.item,value) ) this.removeNode(i);
	}	
}
STDList.prototype.rend = function()
{
	// return reverse iterator at head of list
	return this.iterator(this.head,false);
}
STDList.prototype.resize = function(nSize, value)
{
	while ( nSize < this.nSize ) this.pop_back();
	while ( nSize > this.nSize ) this.push_back(value);
}
STDList.prototype.reverse = function()
{
	// swap items around
	var n = Math.floor(this.nSize / 2);
	var h = this.head.next;
	var t = this.tail.prev;
	while ( n > 0 )
	{
		var tmp = h.item;
		h.item = t.item;
		t.item = tmp;
		n--;
	}
}
STDList.prototype.size = function()
{
	return this.nSize;
}
STDList.prototype.mergeItems = function(wBefore,wAfter,aBegin,aEnd,bCountA,bBegin,bEnd,bCountB,less)
{
	var i = wBefore;
	var a = aBegin;
	var b = bBegin;
	while ( (a !== aEnd) || (b !== bEnd) )
	{	
		var bA;
		if ( a === aEnd ) bA = false;
		else if ( b === bEnd ) bA = true;
		else bA = less.fn(a,b);

		if ( bA )
		{
			i.next = a;
			a.prev = i;
			i = a;
			a = a.next;
			if ( bCountA ) this.nSize++;
		}
		else 
		{
			i.next = b;
			b.prev = i;
			i = b;
			b = b.next;
			if ( bCountB ) this.nSize++;
		}
	}
	i.next = wAfter;
	wAfter.prev = i;
}
STDList.prototype.mergeSort = function(begin,end,nCount,less)
{
	// nothing to do if zero or one items
	if ( nCount < 2 ) return;
	
	// if just two items, swap them
	if ( nCount == 2 )
	{
		var other = begin.next;
		if ( less.fn(other, begin) )
		{
			var temp = begin.item;
			begin.item = other.item;
			other.item = temp;
		}
		return;
	}
	
	// else find the mid point and recurse
	var nHalf = Math.floor(nCount/2);
	var mid = begin;
	for ( var i = 0; i < nHalf; i++ ) mid = mid.next;
	this.mergeSort(begin,mid,nHalf,less);
	this.mergeSort(mid,end,nCount-nHalf,less);
	
	// now merge the two
	this.mergeItems(begin.prev,end,begin,mid,false,mid,end,false,less);
}
STDList.prototype.sort = function(less)
{
	this.mergeSort(this.head.next,this.tail,this.nSize,less?less:STD.prototype.less);
}
STDList.prototype.splice = function(where,right,begin,end)
{
	switch ( arguments.length )
	{
	case 2:
		begin = right.begin();
		end = right.end();
		break;
	case 3:
		end = right.end();
		break;
	case 4:
		break;
	}
	var lBegin = begin.node;
	var lEnd = end.node;
	var lPrev = lBegin.prev;
	
	var wNext = where.node;
	var wPrev = wNext.prev;
	while ( lBegin !== lEnd )
	{
		var node = lBegin;
		lBegin = lBegin.next;
		this.insertNode(node,wPrev);
		wPrev = node;
		right.nSize--;
	}
	wNext.prev = wPrev;
	pPrev.next = wNext;

	lPrev.next = lEnd;
	lEnd.prev = lPrev;
}
STDList.prototype.swap = function(right)
{
	// swap contents with right
	var head = this.head;
	var tail = this.tail;
	var nSize = this.nSize;
	this.head = right.head;
	this.tail = right.tail;
	this.nSize = right.nSize;
	right.head = head;
	right.tail = tail;
	right.nSize = nSize;
}
STDList.prototype.unique = function(equal_to)
{
	if ( equal_to == undefined ) equal_to = STD.prototype.equal_to;
	// remove adjacent duplicate items
	for ( var i = this.head.next; i !== this.tail; i = i.next )
	{
		var iNext = i.next;
		while ( (iNext!==this.tail) && equal_to.fn(i.item,iNext.item) )
		{
			iNext = iNext.next;
			i.next = iNext;
			iNext.prev = i;
		}
	}
}
//=============================================================================
// STDVectorIterator
function STDVectorIterator(container, nIndex, bForward, type)
{
	this.container = container;
	this.data = container.data;
	this.bForward = bForward;
	this.type = type;

	this.setPos(nIndex);	
}
STDVectorIterator.prototype.clone = function()
{
	return new STDVectorIterator(this.container,this.getPos(),this.bForward,this.type);
}
STDVectorIterator.prototype.setPos = function(nIndex)
{
	delete this.item;
	this.nIndex = nIndex;
	if ( this.nIndex >= this.container.nEnd ) return;
	if ( this.nIndex < this.container.nBegin ) return;
	this.item = this.data[nIndex];
}
STDVectorIterator.prototype.getPos = function()
{
	return this.nIndex = Math.min(
		Math.max(this.nIndex,this.container.nBegin-1),
		this.container.nEnd);
}
STDVectorIterator.prototype.increment = function(value)
{
	if ( arguments.length == 0 ) value = 1;
	this.setPos(this.nIndex + (this.bForward ? value : -value));
}
STDVectorIterator.prototype.decrement = function(value)
{
	if ( arguments.length == 0 ) value = 1;
	this.setPos(this.nIndex + this.bForward ? -value : value);
}
STDVectorIterator.prototype.equal_to = function(it)
{
	return (this.container === it.container) &&
			(this.getPos() == it.getPos());
}
STDVectorIterator.prototype.isIterator = true;
STDVectorIterator.assign = function(value)
{
	if ( (this.nIndex < this.container.nEnd) &&
		 (this.nIndex >= this.container.nBegin) ) this.data[this.nIndex] = value;
}
STDVectorIterator.prototype.minus = function(other)
{
	return this.getPos() - other.getPos();
}
STDLinkIterator.prototype.insert = function(value)
{
	this.container.insert(this,value);
}

//=============================================================================
// STDVector
function STDVector()
{
	this.data = new Array();
	this.nBegin = 0;
	this.nEnd = 0;
	this.type = "vector";
}
STDVector.prototype.iterator = function(nPos,bForward)
{
	bForward = arguments.length == 1 ? true : bForward;
	return new STDVectorIterator(this,nPos,bForward,this.type);
}
STDVector.prototype.isIterator = STD.prototype.isIterator;
STDVector.prototype.assign = function(a,b)
{
	// replace list contents with inputs
	if ( this.isIterator(a) && this.isIterator(b) )
	{
		this.clear();
		while ( !a.equal_to(b) )
		{
			this.data.push(a.item);
			a.increment();
			this.nEnd++;
		}
	}
	else
	{
		this.data = new Array(a);
		this.nBegin = 0;
		this.nEnd = a;
		for ( var i = 0; i < a; i++ ) this.data[i] = b;
	}
}
STDVector.prototype.at = function(pos)
{
	return this.data[pos+this.nBegin];
}
STDVector.prototype.back = function()
{
	return this.data[this.nEnd-1];
}
STDVector.prototype.begin = function()
{
	return this.iterator(this.nBegin);
}
STDVector.prototype.capacity = function()
{
	return this.data.length;
}
STDVector.prototype.clear = function()
{
	this.data = new Array();
	this.nBegin = 0;
	this.nEnd = 0;
}
STDVector.prototype.empty = function()
{
	return this.data.length == 0;
}
STDVector.prototype.end = function()
{
	return this.iterator(this.nEnd);
}
STDVector.prototype.erase = function(first, last)
{
	var nFirst = first.getPos();
	if ( nFirst == this.nEnd ) return;
	var nLast;
	if ( arguments.length == 1 ) nLast = nFirst + 1;
	else nLast = last.getPos();
	
	var nCount = nLast - nFirst;
	this.data.splice(nFirst, nCount);
	this.nEnd -= nCount;
}
STDVector.prototype.front = function()
{
	return this.data[this.nBegin];
}
STDVector.prototype.insert = function(where,a,b)
{
	var nWhere = where.getPos();
	if ( arguments.length == 2 )
	{
		this.data.splice(nWhere,0,a);
		this.nEnd++;
		where.item = a;
		return where;
	}

	var aTail = this.data.splice(nWhere,this.nEnd-nWhere);	
	if ( this.isIterator(a) && this.isIterator(b) )
	{
		while ( !a.equal_to(b) )
		{
			this.data.push(a);
			this.nEnd++;
		}
	}
	else
	{
		for ( var i = 0; i < a; i++ ) this.data.push(b);
		this.nEnd += a;
	}
	for ( i in aTail ) this.data.push(aTail[i]);
}

STDVector.prototype.pop_back = function()
{
	if ( this.nEnd > this.nBegin ) delete this.data[--this.nEnd];
}
STDVector.prototype.push_back = function(value)
{
	this.data[this.nEnd++] = value;
}
STDVector.prototype.rbegin = function()
{
	return this.iterator(this.nEnd-1, false);
}
STDVector.prototype.rend = function()
{
	return this.iterator(this.nBegin-1,false);
}
STDVector.prototype.size = function()
{
	return this.nEnd - this.nBegin;
}
STDVector.prototype.swap = function(right)
{
	var data = this.data;
	var nBegin = this.nBegin;
	var nEnd = this.nEnd;
	
	this.data = right.data;
	this.nBegin = right.nBegin;
	this.nEnd = right.nEnd;
	
	right.data = data;
	right.nBegin = nBegin;
	right.nEnd = nEnd;
}

//=============================================================================
// STDDeque
function STDDeque()
{
	this.data = new Array();
	this.nBegin = 0;
	this.nEnd = 0;
	
	this.type = "deque";
	
	// add a few specialisations...
	this.push_front = STDDeque_push_front;
	this.pop_front = STDDeque_pop_front;
}

// inherit methods from STDVector
STDDeque.prototype = STDVector.prototype;

STDDeque_push_front = function(value)
{
	this.data[--this.nBegin] = value;
}
STDDeque_pop_front = function()
{
	if ( this.nEnd > this.nBegin ) delete this.data[this.nBegin++];
}

//</script>

Copy this text and save into a file called "JSstlext.js"

//<script type="text/javascript">

function STDEXT()
{
	// namespace class STDEXT
}

STDEXT.prototype.hash_map = function(hash,less)
{
	return new STDEXTHashMap(hash,less);
}
STDEXT.prototype.hash_multimap = function(hash,less)
{
	return new STDEXTHashMultiMap(hash,less);
}
STDEXT.prototype.hash_set = function(hash,less)
{
	return new STDEXTHashSet(hash,less);
}
STDEXT.prototype.hash_multiset = function(hash,less)
{
	return new STDEXTHashMultiSet(hash,less);
}
STDEXT.prototype.hash = 
{
	// standard hash behaviour is to assume value is already an integer
	fn:function(a)
	{
		return a;
	} 
};

// declare namespace stdext
var stdext = new STDEXT();

//=============================================================================
// 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()
{
}
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;
}
STDEXTHash.prototype.iterator = function(node,bForward)
{
	if ( arguments.length == 1 ) bForward = true;
	return new STDLinkIterator(this,node,bForward,this.type);	
}
STDEXTHash.prototype.isIterator = STD.prototype.isIterator;
STDEXTHash.prototype.createNode = function(item)
{
	// default behaviour; the item is the key
	return {item:item,key:item,next:null,prev:null};
}
STDEXTHash.prototype.insertNode = function(node, prev,next)
{
	// insert a node into the linked list
	node.prev = prev;
	prev.next = node;
	
	node.next = next;
	next.prev = node;
	
	// increment the count
	this.nCount++;
}
STDEXTHash.prototype.removeNode = function(node)
{
	// remove the node from the list
	node.prev.next = node.next;
	node.next.prev = node.prev;

	// decrement the count
	this.nCount--;
}
STDEXTHash.prototype.begin = function()
{
	// return iterator at start of collection
	return this.iterator(this.head.next);
}
STDEXTHash.prototype.clear = function()
{
	// remove all items from collection
	this.bucket = new Array();

	// and empty the list
	this.head.next = this.tail;
	this.tail.prev = this.head;

	// reset the count
	this.nCount = 0;
}
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;
}
STDEXTHash.prototype.empty = function()
{
	// return true if no items contained.
	return this.nCount == 0;
}
STDEXTHash.prototype.end = function()
{
	// return iterator one step beyond the last item
	return this.iterator(this.tail);
}
STDEXTHash.prototype.equal_range = function(key)
{
	// return lower and upper bounds of key
	var lb = this.lower_bound(key);
	var ub = this.upper_bound(key);
	return {first:lb,second:ub};
}
STDEXTHash.prototype.eraseImpl = function(node)
{
	var next = node.next;

	// find the array index
	var h = this.hash.fn(node.key);
	
	// if node is at head of bucket
	if ( this.bucket[h] === node )
	{
		if ( this.hash.fn(next.key) == h )
		{
			// put the next one in this bucket
			this.bucket[h] = next;
		}
		else
		{
			// empty the bucket
			delete this.bucket[h];
		}
	}
	
	// remove node from linked list
	this.removeNode(node);
	
	// return the next node in the list
	return next;
}
STDEXTHash.prototype.erase = function(a,b)
{
	var iNode, nCount;
	
	// erase items from the collection
	if ( arguments.length == 0 ) return;

	if ( !this.isIterator(a,true,true) )
	{
		// a is a key
		iNode = this.lower_bound(a).node;
		nCount = 0;
		while ( !this.less.fn(a, iNode.key) )
		{
			iNode = this.eraseImpl(iNode);
			nCount++;
		}
		return nCount;
	}
	
	// if b not specified, erase just a
	if ( arguments.length == 1 )
	{
		if ( !a.node.bSentinel )
		{
			return this.iterator(this.eraseImpl(a.node));
		}
		else return this.end();
	}
	else
	{
		iNode = a.node;
		while ( iNode !== b.node )
		{
			iNode = this.eraseImpl(iNode);
		}
		return this.iterator(iNode);
	}
}
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();
}
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 bin 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 bin, 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};
}
STDEXTHash.prototype.insertReturn = function(pair)
{
	// pair: first:node, second:bInserted
	if ( this.bMultiContainer ) return this.iterator(pair.first);
	else return {first:this.iterator(pair.first),second:pair.second};
}
STDEXTHash.prototype.insert = function(a,b)
{
	// insert item(s) into collection
	if ( arguments.length == 0 ) return;
	
	var pair = null;
	var hint;
	if ( arguments.length == 1 )
	{
		// case 1: a is value type
		return this.insertReturn(this.insertImpl(a));
	}
	
	if ( this.isIterator(a) && this.isIterator(b) )
	{
		// case 2: a and b are input iterators. Insert [a,b)
		node = a.node;
		while ( node !== b.node )
		{
			this.insertImpl(node.item);
			node = node.next;
		}
		return;
	}
	
	if ( this.isIterator(a,true,true) )
	{
		// case 3: a is a hint. Test and insert
		if ( !a.node.bSentinel )
		{
			node = this.createNode(b);
			var next = a.node.next;
			var nHint = this.hash.fn(a.node.key);
			var nIndex = this.hash.fn(node.key);
			if ( nHint == nIndex )
			{
				if ( this.bMultiContainer )
				{
					if ( !this.less.fn(node.key,a.node.key) &&
							(next.bSentinel || 
							(this.hash.fn(next.key) != nIndex) ||
							!this.less.fn(next.key,node.key)) )
					{
						// next is end or in a different hash or not less than b
						// so insert here
						this.insertNode(node,a.node,next);
						return this.iterator(node);
					}
				}
				else
				{
					if ( this.less.fn(a.node.key, node.key) &&
							(next.bSentinel || 
							(this.hash.fn(next.key) != nIndex) ||
							this.less.fn(node.key,next.key)) )
					{
						// next is end or in a different hash or not less than b
						// so insert here
						this.insertNode(node,a.node,next);
						return this.iterator(node);
					}
				}
			}
		}
		// if the attempt to use the hint failed, fall back on normal insert
		return this.iterator(this.insertImpl(b).first);
	}
}
STDEXTHash.prototype.key_comp = function()
{
	return this.less;
}
STDEXTHash.prototype.lower_bound = 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;
	}
	return this.iterator(node);
}
STDEXTHash.prototype.rbegin = function()
{
	return this.iterator(this.tail.prev, false);
}
STDEXTHash.prototype.rend = function()
{
	return this.iterator(this.head, false);
}
STDEXTHash.prototype.size = function()
{
	return this.nCount;
}
STDEXTHash.prototype.swap = function(other)
{
	// save the first element for insertion into other.
	var begin = this.head.next;
	
	// insert the contents of other into this
	this.clear();
	this.insert(other.begin(), other.end());
	
	// insert the old contents of this into other. 
	// Note: still terminated by this.end()
	other.clear();
	other.insert(this.iterator(begin), this.end());
}
STDEXTHash.prototype.upper_bound = function(key)
{
	// first element greater than 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(key, node.key) )
	{
		node = node.next;
	}
	return this.iterator(node);
}

//=============================================================================
// STDEXTHashMap

function STDEXTHashMap(hash,less)
{
	// add special map behaviour
	this.createNode = STDEXTHashMap_createNode;
	
	// initialise hash_map settings
	this.type = "hash_map";
	this.bMultiContainer = false;

	// initialise STDEXTHash settings
	this.initialise(hash,less);
}

// inherit behaviour from STDEXTHash
STDEXTHashMap.prototype = STDEXTHash.prototype;

STDEXTHashMap_createNode = function(item)
{
	// in a map, the key is item.first
	return {item:item,key:item.first,next:null,prev:null};
}

//=============================================================================
// STDEXTHashMultiMap

function STDEXTHashMultiMap(hash,less)
{
	// add special map behaviour
	this.createNode = STDEXTHashMap_createNode;
	
	// initialise hash_multimap settings
	this.type = "hash_multimap";
	this.bMultiContainer = true;

	// initialise STDEXTHash settings
	this.initialise(hash,less);
}

// inherit behaviour from STDEXTHash
STDEXTHashMultiMap.prototype = STDEXTHash.prototype;

//=============================================================================
// STDEXTHashSet

function STDEXTHashSet(hash,less)
{
	// initialise hash_set settings
	this.type = "hash_set";
	this.bMultiContainer = false;

	// initialise STDEXTHash settings
	this.initialise(hash,less);
}

// inherit behaviour from STDEXTHash
STDEXTHashSet.prototype = STDEXTHash.prototype;

//=============================================================================
// STDEXTHashMultiSet

function STDEXTHashMultiSet(hash,less)
{
	// initialise map settings
	this.type = "hash_multiset";

	this.bMultiContainer = true;

	// initialise STDEXTHash settings
	this.initialise(hash,less);
}

// inherit behaviour from STDEXTHash
STDEXTHashMultiSet.prototype = STDEXTHash.prototype;

//</script>

Copy this text and save into a file called "stlUnitTest.html"

<html>
<head>
<script type="text/javascript" src="RBTree.js"></script>
<script type="text/javascript" src="JSstl.js"></script>
<script type="text/javascript" src="JSstlext.js"></script>
<script type="text/javascript">

var oDbg = null;
function clrdebug()
{
	if ( !oDbg ) oDbg = document.getElementById('debug');
	if ( oDbg ) oDbg.innerHTML = '';
}
function debug(txt)
{
	if ( !oDbg ) oDbg = document.getElementById('debug');
	if ( oDbg ) oDbg.innerHTML += txt + '<br>'
}

function displayRange(sTitle, display, iBegin, iEnd)
{
	debug(sTitle);
	for ( i = iBegin; !i.equal_to(iEnd); i.increment() )
	{
		debug(display(i.item));
	}
}
// JavaScript function max returns the greater of two values
function max(left,right)
{
	return left < right ? right : left;
}
var mapItems = [
	{first:5,second:"five"},
	{first:7,second:"seven"},
	{first:3,second:"three"},
	{first:9,second:"nine"},
	{first:1,second:"one"},
	{first:1,second:"uno"},
	{first:1,second:"une"},
	{first:4,second:"four"}
];
function mapItemDisplay(item)
{
	return "{first:" + item.first + ", second:" + item.second + "}";
}
var genItems = [5,7,3,9,1,1,1,4];
function genItemDisplay(item)
{
	return item.toString();
}
function testSTL(c,title,displayItem,aItems,bMulti)
{
	// test a STL collection
	//   c: the collection to test
	//   title: the title of this test
	//   displayItem: a function that will display items
	//   aItems: an array of items
	//   bMulti: whether the collection is a multi collection or not.
	clrdebug();
	debug(title);
	
	var nItem = 0;
	c.insert(aItems[nItem++]);
	c.insert(aItems[nItem++]);
	c.insert(aItems[nItem++]);
	c.insert(aItems[nItem++]);
	c.insert(aItems[nItem++]);

	var item = aItems[nItem++];
	debug("attempt to insert " + displayItem(item));
	var rt = c.insert(item);
	if ( !bMulti )
	{
		if ( rt.second ) debug("   inserted");
		else debug("   already inserted, item = " + displayItem(rt.first.item));
	}
	item = aItems[nItem++];
	debug("second attempt to insert " + displayItem(item));
	var it1 = bMulti ? rt : rt.first;
	var it = c.insert(it1,item);
	debug("   result = " + displayItem(it.item));
	debug("c.count(1) = " + c.count(1));
	
	displayRange("forwards", displayItem, c.begin(), c.end());
	displayRange("backwards", displayItem, c.rbegin(), c.rend());

	var iThree = c.find(3);
	debug("c.find(3) = " + displayItem(iThree.item));
	
	c.insert(iThree,aItems[nItem++]);
	displayRange("4 After 3", displayItem, c.begin(), c.end());
	
	var iFind = c.find(4);
	debug("c.find(4) = " + (iFind.equal_to(c.end()) ? "c.end()" : displayItem(iFind.item)) );
	
	c.erase(3);
	displayRange("3 removed", displayItem, c.begin(), c.end());

	iFind = c.find(3);
	debug("c.find(3) = " + (iFind.equal_to(c.end()) ? "c.end()" : displayItem(iFind.item)) );
	
	debug("c.count(3) = " + c.count(3));
	debug("c.count(5) = " + c.count(5));
	debug("c.size() = " + c.size());
	
	var lb = c.lower_bound(3);
	debug("c.lower_bound(3) = " + (lb.equal_to(c.end()) ? "c.end()" : displayItem(lb.item)) );

	lb = c.lower_bound(5);
	debug("c.lower_bound(5) = " + (lb.equal_to(c.end()) ? "c.end()" : displayItem(lb.item)) );

	var ub = c.upper_bound(3);
	debug("c.upper_bound(3) = " + (ub.equal_to(c.end()) ? "c.end()" : displayItem(lb.item)) );

	lb = c.upper_bound(5);
	debug("c.upper_bound(5) = " + (ub.equal_to(c.end()) ? "c.end()" : displayItem(lb.item)) );
}


function testSTLMap()
{
	testSTL(std.map(),"Map",mapItemDisplay,mapItems,false);
}
function testSTLMultiMap()
{
	testSTL(std.multimap(),"MultiMap",mapItemDisplay,mapItems,true);
}
function testSTLSet()
{
	testSTL(std.set(),"Set",genItemDisplay,genItems,false);
}
function testSTLMultiSet()
{
	testSTL(std.multiset(),"MultiSet",genItemDisplay,genItems,true);
}
function testSTLVector()
{
	clrdebug();
	var v = std.vector();
	
	v.push_back("one");
	v.push_back("three");
	v.push_back("five");
	v.push_back("seven");
	v.push_back("nine");

	displayRange("forwards", genItemDisplay, v.begin(), v.end());
	displayRange("backwards", genItemDisplay, v.rbegin(), v.rend());

	var it = v.begin();
	it.increment();
	v.insert(it,"two");
	displayRange("after two", genItemDisplay, v.begin(), v.end());

	debug("v.size() = " + v.size());
	debug("v.front() = " + v.front());
	debug("v.back() = " + v.back());

}
function testSTLList()
{
	clrdebug();
	var l = std.list();
	
	l.push_back("one");
	l.push_back("three");
	l.push_back("five");
	l.push_back("seven");
	l.push_back("nine");

	displayRange("forwards", genItemDisplay, l.begin(), l.end());
	displayRange("backwards", genItemDisplay, l.rbegin(), l.rend());

	var it = l.begin();
	it.increment();
	l.insert(it,"two");
	displayRange("after two", genItemDisplay, l.begin(), l.end());

	debug("l.size() = " + l.size());
	debug("l.front() = " + l.front());
	debug("l.back() = " + l.back());

	l.sort();
	displayRange("after sort", genItemDisplay, l.begin(), l.end());
	
}
function testSTLEXTHashSet()
{
	testSTL(stdext.hash_set(),"Hashed Set",genItemDisplay,genItems,false);
}
function testSTLEXTHashMultiSet()
{
	testSTL(stdext.hash_multiset(),"Hashed MultiSet",genItemDisplay,genItems,true);
}
function testSTLEXTHashMap()
{
	testSTL(stdext.hash_map(),"Hashed Map",mapItemDisplay,mapItems,false);
}
function testSTLEXTHashMultiMap()
{
	testSTL(stdext.hash_multimap(),"Hashed MultiMap",mapItemDisplay,mapItems,true);
}
</script>
</head>
<body>

<button onclick="testSTLMap();">Map Test</button>
<button onclick="testSTLMultiMap();">MultiMap Test</button>
<button onclick="testSTLSet();">Set Test</button>
<button onclick="testSTLMultiSet();">MultiSet Test</button>
<br>
<button onclick="testSTLList();">List Test</button>
<button onclick="testSTLVector();">Vector Test</button>
<br>
<button onclick="testSTLEXTHashSet();">HashSet Test</button>
<button onclick="testSTLEXTHashMultiSet();">HashMultiSet Test</button>
<button onclick="testSTLEXTHashMap();">HashMap Test</button>
<button onclick="testSTLEXTHashMultiMap();">HashMultiMap Test</button>

<div id="debug"></div>
</body>
</html>