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;
        }
    }
}

Published Tuesday, October 26, 2004 10:34 PM by Justin Rogers
Filed under:

Comments

No Comments