Code-Only: Client-Side OO Javascript Vector Chance Tree for probability selection.
/*
Copyright (c) 2004 DigiTec Web Consultants, LLC. All rights reserved.
The use of this software is for test and performance purposes only.
You may not use this software in any commercial applications without
the express permission of the copyright holder. You may add to or
modify the code contained here-in to cause it to run slower without
contacting the copyright holder, however, any attempts to make this
code run faster should be documented on:
http://weblogs.asp.net/justin_rogers/articles/248367.aspx
I reserve the right to change or modify the publicly available version
of this code at any time. I will not provide version protection, so
if you have reliance on a particular build of this software, then make
your own back-ups.
You must laugh, at least a little, when reading this licensing agreement,
unless of course you don't have a sense of humor. In all seriousness,
excluding the laughter, laughter in itself does not void this license
agreement, nor compromise it's ability to legally bind you.
You must not remove this notice, or any other, from this software.
*/
function Chance(growthWeight, currentWeight, item) {
this.GrowthWeight = growthWeight;
this.CurrentWeight = currentWeight;
this.Item = item;
}
function VectorChanceTree() {
this.chances = new Array();
this.AddChance = addChance;
this.Get = get;
this.Take = take;
this.FindNode = findNode;
this.ModifyChances = modifyChances;
}
function addChance(chance, item) {
var index = this.chances.length;
this.chances.push(new Chance(chance, chance, item));
while(index > 0) {
index = (index - 1) >> 1;
this.chances[index].GrowthWeight += chance;
}
}
function get() {
if ( this.chances.length == 0 ) { return null; }
return this.chances[this.FindNode(Math.floor(Math.random()*this.chances[0].GrowthWeight))].Item;
}
function take() {
if ( this.chances.length == 0 ) { return null; }
var prob = Math.floor(Math.random()*this.chances[0].GrowthWeight);
var index = this.FindNode(prob);
var chance = this.chances[index];
this.ModifyChances(index, -chance.CurrentWeight);
return chance.Item;
}
function findNode(chance) {
var index = 0; var prior = 0;
while(true) {
prior += this.chances[index].CurrentWeight;
if ( chance < prior ) { return index; }
index = (index << 1) + 1;
if ( chance >= (prior + this.chances[index].GrowthWeight) ) {
prior += this.chances[index].GrowthWeight; index++;
}
}
}
function modifyChances(index, modifyBy) {
var priorGrowth = this.chances[index].GrowthWeight;
if ( (this.chances[index].CurrentWeight + modifyBy) <= 0 ) {
var last = this.chances.length - 1;
var swapIndex = last;
while(swapIndex > 0) {
swapIndex = (swapIndex - 1) >> 1;
this.chances[swapIndex].GrowthWeight -= this.chances[last].CurrentWeight;
}
priorGrowth = this.chances[index].GrowthWeight;
this.chances[index] = this.chances[last];
this.chances = this.chances.slice(0, last);
if ( last != index ) {
this.chances[index].GrowthWeight = this.chances[index].CurrentWeight;
var son = (index << 1) + 1;
if ( son < last ) { this.chances[index].GrowthWeight += this.chances[son++].GrowthWeight; }
if ( son < last ) { this.chances[index].GrowthWeight += this.chances[son].GrowthWeight; }
} else {
return;
}
} else {
this.chances[index].CurrentWeight += modifyBy;
this.chances[index].GrowthWeight += modifyBy;
}
var feedWeight = this.chances[index].GrowthWeight - priorGrowth;
if ( feedWeight != 0 ) {
while(index > 0) {
index = (index - 1) >> 1;
this.chances[index].GrowthWeight += feedWeight;
}
}
}