// Array.bSearch(key, options)
//
// Usage
//      my_array.bSearch( {role1: value1, role2: value2, ... , roleN: valueN} )
//      my_array.bSearch( {role1: value1, role2: value2, ... , roleN: valueN}, Array.DESCENDING | Array.NUMERIC | Array.CASEINSENSITIVE )
//
// Parameters
//      key       A list of field names (roles) and their associated values of any data type to search, grouped together into a block using curly braces {}.
//      options   Optional parameters that change the search behavior. Supported options are: Array.DESCENDING, Array.NUMERIC, Array.CASEINSENSITIVE.
//
// Returns
//      Integer value representing an array row (index) in which the search key was found, or -1 when not found.
//      A warning is displayed in output window via a trace(), when search takes more than theoretical maximum of log2(n) iterations.
//
// Description
//      Extension to class Array() to search for a key in a sorted associative array using very efficient bisection algorithm.
//      Array to search can use any data type since search key and array rows are converted to strings.
//      Array must be sorted prior to using this search method.
//
// References:
//      ActionScript Array.sortOn() for details on associative array sorting and sorting options.
//      Numerical Recipes section 3.4: bisection search algorithm, www.nr.com.
//
// Author: Ron Fredericks, Embedded Components, Inc.,  ronf@EmbeddedComponents.com
// Last updated: Dec. 28, 2004
// Tested environment: Flash player version 6, and 7 (both as1 and as2).
// Copyright:  no rights reserved, no liability covered, no warranty of use given or implied, no indemnity offered, support optional.

Array.prototype.bSearch = function (key, options) {
        this.sortDESCENDING       = (options & Array.DESCENDING) ? true : false;
        this.sortNUMERIC          = (options & Array.NUMERIC) ? true : false;
        this.sortCASEINSENSITIVE  = (options & Array.CASEINSENSITIVE) ? true : false;
        this.padRole              = String.fromCharCode(31); // Use this character to delimit fields in search key and array test row.
        var iL = 0, iU = this.length-1, iM = 0; // Initialize search boundry.
        var iterations = 0;                     // The bisection search algorithm iterates about log2(Array.length) times when searching a sorted array.
        
        while (iU-iL > 1) {
                iM = (iU+iL) >> 1;                  // Bisect array's search boundary until search key is found in the array row under test, or search fails boundary conditions.
                iterations++;
                this.getRow2Test(key, iM);          // Private function, defined below, to populate this.sKey and this.tKey.
                if ( (this.sKey >= this.tKey) != this.sortDESCENDING)
                iL=iM;
                else
                iU=iM;
        }
        if ( iterations > Math.round(Math.LOG2E*Math.log(this.length)) ) {
                trace( "Warning: search took too long! \n Details: " + iterations + " iterations of outer search loop were used, \n compared to theoretical maximum of log2(array size): " + Math.round(Math.LOG2E*Math.log(this.length)) );
                trace( " Perhaps this array has not been sorted correctly, or different options should be pased to this function." );
        }
        this.getRow2Test(key, (this.sortDESCENDING ? iU: iL))   // Return with Array index position when search found.
        if ( this.sKey == this.tKey )
        return (this.sortDESCENDING ? iU: iL);
        this.getRow2Test(key, 0)
        if (this.sKey == this.tKey)
        return 0;
        this.getRow2Test(key, this.length-1)
        if (this.sKey == this.tKey)
        return this.length-1;
        return -1;                         // Return -1, when search key not found.
};
// bSearch private function builds formatted search key (this.sKey) and test row (this.tKey)
Array.prototype.getRow2Test = function (key, row) {
        this.sKey="";                     // Search key.
        this.tKey="";                     // Test row.
        for (var role in key) {
                var iPadRole = Math.max( String(key[role]).length, String(this[row][role]).length ) + 1;
                if ( typeof key[role] == "number" && this.sortNUMERIC) {
                        // NUMERIC sorted number elements must pad to the right
                        for (var p = String(key[role]).length; p<iPadRole; p++)
                        this.sKey += this.padRole;
                        for (var p = String(this[row][role]).length; p<iPadRole; p++)
                        this.tKey += this.padRole;
                        this.sKey += String(key[role])
                        this.tKey += String(this[row][role])
                }
                else {
                        // STRING sorted elements must pad to the left
                        this.sKey += String(key[role])
                        this.tKey += String(this[row][role])
                        for (var p = String(key[role]).length; p<iPadRole; p++)
                        this.sKey += this.padRole;
                        for (var p = String(this[row][role]).length; p<iPadRole; p++)
                        this.tKey += this.padRole;
                }
        }
        if (this.sortCASEINSENSITIVE) {
                this.sKey = this.sKey.toUpperCase();
                this.tKey = this.tKey.toUpperCase();
        }
};

// example...
var playList = new Array();
playList.push( {slide: 2, clip: "_level0.instance3", cue: 4000} );
playList.push( {slide: 3, clip: "_level0.instance1", cue: 5000} );
playList.push( {slide: 1, clip: "_level0.instance1", cue: 1000} );
playList.push( {slide: 10, clip: "_level0.instance2", cue: 2000} );
playList.sortOn( ["clip", "slide"], Array.DESCENDING | Array.NUMERIC | Array.CASEINSENSITIVE)
var index = playList.bSearch( {clip: "_level0.instance1", slide: 1}, Array.DESCENDING | Array.NUMERIC | Array.CASEINSENSITIVE )
if (index)
trace("clip found, with cue time: " + playList[index].cue); // clip found, with cue time: 1000
else
trace("Oops, clip not found");