//<script type="text/javascript">
//
// JavaScript STL
//
// Free Software Licence:
// This software is intended for free use for personal and comercial use.
// No Warranty:
// Because this software is licenced free of charge, there is no warranty
// expressed or implied for any code contained within this file.
// Guyon Roche
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 =
{
// standard equal_to behaviour is to use == operator
fn:function(a,b)
{
return a == b;
}
};
STD.prototype.greater =
{
// standard greater behaviour is to use > operator
fn:function(a,b)
{
return a > b;
}
};
STD.prototype.greater_equal =
{
// standard greater_equal behaviour is to use >= operator
fn:function(a,b)
{
return a >= b;
}
};
STD.prototype.less =
{
// standard less behaviour is to use < operator
fn:function(a,b)
{
return a < b;
}
};
STD.prototype.less_equal =
{
// standard less_equal behaviour is to use <= operator
fn:function(a,b)
{
return a <= b;
}
};
STD.prototype.hash =
{
// standard hash behaviour is to assume value is already an integer
fn:function(a)
{
return a;
}
};
// 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;
//=============================================================================
// 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;
}
// 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;
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]);
}
