Strok
12-30-2004, 05:36 AM
test
// 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");
// 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");