///////////////////////////////////////////////////////////////////////////
//
// XBSDB - Cross-Browser JavaScript Database library
// Copyright (C) 2010 Alexey A.Znayev
//
// This file is part of XBSDB.
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.
//
// Alexey A.Znayev, znaeff@mail.ru
//
///////////////////////////////////////////////////////////////////////////
// This flie contains private class(es) and/or method(s) and may be changed any time
///////////////////////////////////////////////////////////////////////////
// simple index
function XBSKey(oTable,sExprFieldsX,oFields){
this.sResultCode = 'OK';
this.oTable = oTable; //object - table
this.sKeyFunction = sExprFieldsX; //correct expression for key value calculation
this.oFields = oFields; //object - used fields hash
this._aNumbersInit = new Array(); // initial sorted packed array of numbers
this._fIterator = new Function("table", "n", "return(" + this.sKeyFunction + ");"); // function - index expression
this._aNumbers; // working link
}
XBSKey.prototype.Rebuild = function(aExtNumbers){
// index rebuilding
this.sResultCode = 'OK';
var aNumbers;
if(aExtNumbers){
aNumbers = aExtNumbers;
}else{
aNumbers = this.oTable.GetRecordsAllPacked();
}
var nNumbers = aNumbers.length;
if(nNumbers > 0){
var fIterator = this._fIterator;
var oTable = this.oTable;
try{
aNumbers.sort(function(n1,n2){
var value1 = fIterator(oTable,n1);
var value2 = fIterator(oTable,n2);
if(value1 < value2){
return -1;
}else if(value1 > value2){
return 1;
}else{
return 0;
}
}
);
}catch(e){
this.sResultCode = 'KEY_NOT_BUILDED_UNKNOWN';
return false;
}
if(aNumbers && aNumbers.length == nNumbers){
if(aExtNumbers){
aExtNumbers = aNumbers;
}else{
this._aNumbersInit = aNumbers;
}
}else{
this.sResultCode = 'KEY_NOT_BUILDED_FULL';
return false;
}
}
return true;
}
XBSKey.prototype.Load = function(aNumbersInit){
// index loading
this.sResultCode = 'OK';
this._aNumbersInit = aNumbersInit; // initial sorted packed array of numbers - loaded (no checking)
return true;
}
///////////////////////////////////////////////////////////////////////
// next:
// aUpperNumbers - not packed array for upped level records to cutt off result
// aExtNumbers - packed array of external records to seek in (maybe result of previous seek in this index)
///////////////////////////////////////////////////////////////////////
// EQ
XBSKey.prototype.GetRecordsUnpackedEQ = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records == value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iFirst = this._GetIndexFirstEQ(v);
if(iFirst >= 0){
var iLast = this._GetIndexLastEQ(v);
if(iLast >= iFirst){
if(aUpperNumbers){
for(i=iFirst; i<=iLast; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes[this._aNumbers[i]] = true;
}
}
}else{
for(i=iFirst; i<=iLast; i++){
aRes[this._aNumbers[i]] = true;
}
}
}else{
this.sResultCode = 'KEY_RANGE_LOW_GR_HIGH';
return false;
}
}
}
return aRes;
}
XBSKey.prototype.GetRecordsPackedEQ = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records == value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iFirst = this._GetIndexFirstEQ(v);
if(iFirst >= 0){
var iLast = this._GetIndexLastEQ(v);
if(iLast >= iFirst){
if(aUpperNumbers){
for(i=iFirst; i<=iLast; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes.push(this._aNumbers[i]);
}
}
}else{
for(i=iFirst; i<=iLast; i++){
aRes.push(this._aNumbers[i]);
}
}
}else{
this.sResultCode = 'KEY_RANGE_LOW_GR_HIGH';
return false;
}
}
}
return aRes;
}
///////////////////////////////////////////////////////////////////////
// NE
XBSKey.prototype.GetRecordsUnpackedNE = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records != value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iFirst = this._GetIndexLastLE(v);
if(aUpperNumbers){
for(i=0; i<=iFirst; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes[this._aNumbers[i]] = true;
}
}
}else{
for(i=0; i<=iFirst; i++){
aRes[this._aNumbers[i]] = true;
}
}
var iLast = this._GetIndexFirstGR(v);
if(iLast > iFirst){ // not '>=' !
if(aUpperNumbers){
for(i=iLast; i<this._aNumbers.length; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes[this._aNumbers[i]] = true;
}
}
}else{
for(i=iLast; i<this._aNumbers.length; i++){
aRes[this._aNumbers[i]] = true;
}
}
}else{
if(iLast > 0){
this.sResultCode = 'KEY_RANGE_LOW_GREQ_HIGH';
return false;
}
}
}
return aRes;
}
XBSKey.prototype.GetRecordsPackedNE = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records != value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iFirst = this._GetIndexLastLE(v);
if(aUpperNumbers){
for(i=0; i<=iFirst; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes.push(this._aNumbers[i]);
}
}
}else{
for(i=0; i<=iFirst; i++){
aRes.push(this._aNumbers[i]);
}
}
var iLast = this._GetIndexFirstGR(v);
if(iLast > iFirst){ // not '>=' !
if(aUpperNumbers){
for(i=iLast; i<this._aNumbers.length; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes.push(this._aNumbers[i]);
}
}
}else{
for(i=iLast; i<this._aNumbers.length; i++){
aRes.push(this._aNumbers[i]);
}
}
}else{
if(iLast > 0){
this.sResultCode = 'KEY_RANGE_LOW_GREQ_HIGH';
return false;
}
}
}
return aRes;
}
///////////////////////////////////////////////////////////////////////
// LE
XBSKey.prototype.GetRecordsUnpackedLE = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records < value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iLast = this._GetIndexLastLE(v);
if(aUpperNumbers){
for(i=0; i<=iLast; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes[this._aNumbers[i]] = true;
}
}
}else{
for(i=0; i<=iLast; i++){
aRes[this._aNumbers[i]] = true;
}
}
}
return aRes;
}
XBSKey.prototype.GetRecordsPackedLE = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records < value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iLast = this._GetIndexLastLE(v);
if(aUpperNumbers){
for(i=0; i<=iLast; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes.push(this._aNumbers[i]);
}
}
}else{
for(i=0; i<=iLast; i++){
aRes.push(this._aNumbers[i]);
}
}
}
return aRes;
}
///////////////////////////////////////////////////////////////////////
// LEEQ
XBSKey.prototype.GetRecordsUnpackedLEEQ = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records <= value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iLast = this._GetIndexLastEQ(v);
if(iLast >= 0){
if(aUpperNumbers){
for(i=0; i<=iLast; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes[this._aNumbers[i]] = true;
}
}
}else{
for(i=0; i<=iLast; i++){
aRes[this._aNumbers[i]] = true;
}
}
}else{
iLast = this._GetIndexLastLE(v);
if(iLast >= 0){
if(aUpperNumbers){
for(i=0; i<=iLast; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes[this._aNumbers[i]] = true;
}
}
}else{
for(i=0; i<=iLast; i++){
aRes[this._aNumbers[i]] = true;
}
}
}
}
}
return aRes;
}
XBSKey.prototype.GetRecordsPackedLEEQ = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records <= value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iLast = this._GetIndexLastEQ(v);
if(iLast >= 0){
if(aUpperNumbers){
for(i=0; i<=iLast; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes.push(this._aNumbers[i]);
}
}
}else{
for(i=0; i<=iLast; i++){
aRes.push(this._aNumbers[i]);
}
}
}else{
iLast = this._GetIndexLastLE(v);
if(iLast >= 0){
if(aUpperNumbers){
for(i=0; i<=iLast; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes.push(this._aNumbers[i]);
}
}
}else{
for(i=0; i<=iLast; i++){
aRes.push(this._aNumbers[i]);
}
}
}
}
}
return aRes;
}
///////////////////////////////////////////////////////////////////////
// GR
XBSKey.prototype.GetRecordsUnpackedGR = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records > value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iFirst = this._GetIndexFirstGR(v);
if(iFirst >= 0){
if(aUpperNumbers){
for(i=iFirst; i<this._aNumbers.length; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes[this._aNumbers[i]] = true;
}
}
}else{
for(i=iFirst; i<this._aNumbers.length; i++){
aRes[this._aNumbers[i]] = true;
}
}
}
}
return aRes;
}
XBSKey.prototype.GetRecordsPackedGR = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records > value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iFirst = this._GetIndexFirstGR(v);
if(iFirst >= 0){
if(aUpperNumbers){
for(i=iFirst; i<this._aNumbers.length; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes.push(this._aNumbers[i]);
}
}
}else{
for(i=iFirst; i<this._aNumbers.length; i++){
aRes.push(this._aNumbers[i]);
}
}
}
}
return aRes;
}
///////////////////////////////////////////////////////////////////////
// GREQ
XBSKey.prototype.GetRecordsUnpackedGREQ = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records >= value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iFirst = this._GetIndexFirstEQ(v);
if(iFirst >= 0){
if(aUpperNumbers){
for(i=iFirst; i<this._aNumbers.length; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes[this._aNumbers[i]] = true;
}
}
}else{
for(i=iFirst; i<this._aNumbers.length; i++){
aRes[this._aNumbers[i]] = true;
}
}
}else{
iFirst = this._GetIndexFirstGR(v);
if(iFirst >= 0){
if(aUpperNumbers){
for(i=iFirst; i<this._aNumbers.length; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes[this._aNumbers[i]] = true;
}
}
}else{
for(i=iFirst; i<this._aNumbers.length; i++){
aRes[this._aNumbers[i]] = true;
}
}
}
}
}
return aRes;
}
XBSKey.prototype.GetRecordsPackedGREQ = function(v,aUpperNumbers,aExtNumbers){
// getting of array or records >= value
// v - key value
// this.sResultCode = 'OK';
var aRes = new Array(), i;
if(aExtNumbers){
this._aNumbers = aExtNumbers;
}else{
this._aNumbers = this._aNumbersInit;
}
if(this._aNumbers.length > 0){
var iFirst = this._GetIndexFirstEQ(v);
if(iFirst >= 0){
if(aUpperNumbers){
for(i=iFirst; i<this._aNumbers.length; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes.push(this._aNumbers[i]);
}
}
}else{
for(i=iFirst; i<this._aNumbers.length; i++){
aRes.push(this._aNumbers[i]);
}
}
}else{
iFirst = this._GetIndexFirstGR(v);
if(iFirst >= 0){
if(aUpperNumbers){
for(i=iFirst; i<this._aNumbers.length; i++){
if(aUpperNumbers[this._aNumbers[i]]){
aRes.push(this._aNumbers[i]);
}
}
}else{
for(i=iFirst; i<this._aNumbers.length; i++){
aRes.push(this._aNumbers[i]);
}
}
}
}
}
return aRes;
}
///////////////////////////////////////////////////////////////////////
// next:
// private methods
///////////////////////////////////////////////////////////////////////
// next:
// base methods to find 'fork' of 2 index numbers that have value existing border between
XBSKey.prototype._GetIndexFirstFork = function(v){
// seek of first index fork
// - iterator(i1) < v, iterator(i2) >= v)
// v - key value
var b1 = 0, b2 = this._aNumbers.length - 1, bx = 0, aRes = new Array();
var dbx = Math.floor((b2 - b1)/2);
do{
bx += dbx;
var v_bx = this._fIterator(this.oTable,this._aNumbers[bx]);
if(v_bx < v){ b1 = bx; dbx = Math.floor((b2 - b1)/2); }
else { b2 = bx; dbx = 0 - Math.floor((b2 - b1)/2); }
}while(b2 - b1 > 1);
aRes[0] = b1;
aRes[1] = b2;
return aRes;
}
XBSKey.prototype._GetIndexLastFork = function(v){
// seek of last index fork
// - iterator(i1) <= v, iterator(i2) > v)
// v - key value
var b1 = 0, b2 = this._aNumbers.length - 1, bx = 0, aRes = new Array();
var dbx = Math.floor((b2 - b1)/2);
do{
bx += dbx;
var v_bx = this._fIterator(this.oTable,this._aNumbers[bx]);
if(v_bx <= v){ b1 = bx; dbx = Math.floor((b2 - b1)/2); }
else { b2 = bx; dbx = 0 - Math.floor((b2 - b1)/2); }
}while(b2 - b1 > 1);
aRes[0] = b1;
aRes[1] = b2;
return aRes;
}
///////////////////////////////////////////////////////////////////////
// next:
// base methods to find first and last index numbers depending of condition
XBSKey.prototype._GetIndexFirstEQ = function(v){
// seek of first index number of record value equal given value
// v - key value
var aFork = this._GetIndexFirstFork(v);
if(aFork){
if( this._fIterator(this.oTable,this._aNumbers[aFork[0]]) == v ) { return aFork[0]; }
if( this._fIterator(this.oTable,this._aNumbers[aFork[1]]) == v ) { return aFork[1]; }
}
return -1;
}
XBSKey.prototype._GetIndexLastEQ = function(v){
// seek of last index number of record value equal given value
// v - key value
var aFork = this._GetIndexLastFork(v);
if(aFork){
if( this._fIterator(this.oTable,this._aNumbers[aFork[1]]) == v ) { return aFork[1]; }
if( this._fIterator(this.oTable,this._aNumbers[aFork[0]]) == v ) { return aFork[0]; }
}
return -1;
}
XBSKey.prototype._GetIndexFirstGR = function(v){
// seek of first index number of record value greater than given value
// v - key value
var aFork = this._GetIndexLastFork(v);
if(aFork){
if( this._fIterator(this.oTable,this._aNumbers[aFork[0]]) > v ) { return aFork[0]; }
if( this._fIterator(this.oTable,this._aNumbers[aFork[1]]) > v ) { return aFork[1]; }
}
return -1;
}
XBSKey.prototype._GetIndexLastLE = function(v){
// seek of last index number of record value less than given value
// v - key value
var aFork = this._GetIndexFirstFork(v);
if(aFork){
if( this._fIterator(this.oTable,this._aNumbers[aFork[1]]) < v ) { return aFork[1]; }
if( this._fIterator(this.oTable,this._aNumbers[aFork[0]]) < v ) { return aFork[0]; }
}
return -1;
}
|
Download
