/************************* * * * * * * * * * * * * ***************************
    Copyright (c) 1999-2005 Ryan Bobko
                       ryan@ostrich-emulators.com

    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 2 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, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.     
************************** * * * * * * * * * * * * **************************/

#include "qhacctable.h"
#include "qhaccutils.h"

#include <algorithm>
#include <deque>
using namespace std;

/*****************************************************************/
/* QHACCTABLE                                                    */
/*   This is the basis of all data storage in QHacc. This table  */
/*   will keep an index of ids if necessary, but otherwise       */
/*   provides no search functionality. Use a QHACCTABLEINDEX to  */
/*   index arbitrary columns.                                    */
/*                                                               */
/*                                                               */
/*****************************************************************/

// these are error codes
const int QHaccTable::DUPLKEY= -1;
const int QHaccTable::NOTFOUND=-2;

const int QHaccTable::INITINIT=5;
const int QHaccTable::INITGROW=5;
const int QHaccTable::INITFREE=8;

const char * QHaccTable::ERRORS[]={ "",
																		"column key already exists",
																		"update row not found" };

const char * QHaccTable::newerror( int code ) const { return ERRORS[-code]; }

QHaccTable::QHaccTable(	int sz, const ColType * cs, const char * n,
												uint init, uint grow, uint max ) 
	: QHaccResultSet( sz, cs, init, grow ){
	
	if( n ){
		name=QString( n );
		std::ostream * str;
		if( idebug( Utils::CURIOSITY, str ) )
			*str<<"creating "<<n<<" with init="<<init
					<<"; growby="<<grow<<"; maxfree="<<max<<endl;
	}
	else name="";
	
	loading=false;
  maxFree=max;

	indexes=new QHaccTableIndex * [cols];
	for( int i=0; i<cols; i++ ) indexes[i]=0;

	pki=0;
}

QHaccTable::QHaccTable( const QHaccTable& model ) : QHaccResultSet( model ){
	name=model.name;
	//for( uint i=0; i<model.rows(); i++ ) cout<<model[i].gets()<<endl;
	//cout<<"--"<<endl;
	//for( uint i=0; i<rows(); i++ ) cout<<at( i ).gets<<endl;
	
	loading=false;
	maxFree=model.maxFree;

	if( model.pki )	pki=new QHaccTableIndex( *( model.pki ) );
	else pki=0;
	
	indexes=new QHaccTableIndex * [cols];
	for( int i=0; i<cols; i++ ){
		if( model.indexes[i] )
			indexes[i]=new QHaccTableIndex( *( model.indexes[i] ) );
		else indexes[i]=0;
	}
}

QHaccTable::QHaccTable( const QHaccResultSet& model ) 
	: QHaccResultSet( model ){
	name="";

	maxFree=INITFREE;
	loading=false;
	
	indexes=new QHaccTableIndex * [cols];
	for( int i=0; i<cols; i++ ) indexes[i]=0;

	pki=0;
}

QHaccTable& QHaccTable::operator=( const QHaccResultSet& model ) {
	if( &model!=this ){
		name="";
		for( int i=0; i<cols; i++ ) if( indexes[i] ) delete indexes[i];
		delete [] indexes;

		QHaccResultSet::operator=( model );
	
		indexes=new QHaccTableIndex * [cols];
		for( int i=0; i<cols; i++ ) indexes[i]=0;

		if( pki ) delete pki;
		pki=0;
	}
	return *this;
}

QHaccTable& QHaccTable::operator=( const QHaccTable& model ) {
	if( &model!=this ){
		name=model.name;

		for( int i=0; i<cols; i++ ) if( indexes[i] ) delete indexes[i];
		delete [] indexes;
		
		QHaccResultSet::operator=( model );

		delete pki;
		if( model.pki )	pki=new QHaccTableIndex( *( model.pki ) );
		else pki=0;

		indexes=new QHaccTableIndex * [cols];
		for( int i=0; i<cols; i++ ){
			if( model.indexes[i] )
				indexes[i]=new QHaccTableIndex( *( model.indexes[i] ) );
			else indexes[i]=0;
		}
	}
	return *this;
}


QHaccTable::~QHaccTable(){
	std::ostream * str;
	if( idebug( Utils::CURIOSITY, str ) )
		*str<<"destroying "<<name<<( deleter ? " and all its data" : "" )<<endl;

	for( int i=0; i<cols; i++ ) if( indexes[i] ) delete indexes[i];
	delete [] indexes;
}

bool QHaccTable::idebug( int lvl, std::ostream *& str ) const {
	return !name.isEmpty() && Utils::debug( lvl, str );
}
bool QHaccTable::ierror( int lvl, std::ostream *& str ) const {
	return !name.isEmpty() && Utils::error( lvl, str );
}
void QHaccTable::setPK( int c ){ 
	if( pki && pki->sorts( c ) ) return;
	delete pki;
	pki=new QHaccTableIndex( this, c, types[c] );
}
void QHaccTable::setName( QString s ){ name=s; }
const QString& QHaccTable::getName() const { return name; }
int QHaccTable::idcol() const { return ( pki ? pki->sorts() : -1 ); }
void QHaccTable::clear(){
	data.clear();
	data.reserve( INITFREE );
	if( pki ) pki->remake();
}

void QHaccTable::istartLoad( uint rows ){
	loading=true;
	data.reserve( rows+data.size() );
	std::ostream * str=0;
	if( idebug( Utils::CURIOSITY, str ) )
		*str<<"starting load of "<<rows<<" rows into "<<name<<endl;
}

void QHaccTable::istopLoad(){
	loading=false;
	std::ostream * str;
	remake();
	if( idebug( Utils::CURIOSITY, str ) )	*str<<"ending load of "<<name<<endl;
}

int QHaccTable::verifyRow( const TableRow& row ) const {
	//if( !name.isEmpty() ) cout<<"verifying "<<row.toString()<<endl;

	int reason=QHaccResultSet::verifyRow( row );
	if( !loading && reason==VALID && pki ){ 
		// only check for duplicate keys when not loading
		if( pki->contains( row[pki->sorts()] ) ) reason=DUPLKEY;
	}
	
	std::ostream * str=0;
	if( reason<VALID && ierror( Utils::ERROPER, str ) ){
		*str<<"INVALID: "<<newerror( reason )<<endl<<name<<": "<<row.toString()<<endl;
		//cout<<"current table (pki sorts "<<pki->sorts()<<"):"<<endl;
		//for( uint i=0; i<rows(); i++ ) cout<<at( i ).toString()<<endl;
		//cout<<"--"<<endl;
	}
	
	return reason;
}

bool QHaccTable::contains( int col, const TableCol& tc, uint& idx ) const {
	// we're only searching for pks, and luckily, we have an index for that. 
	//	if( !name.isEmpty() )	cout<<"into contains col on "<<name<<" for "<<tc.toString()<<endl;

	bool inthere=false;
	QHaccTableIndex * index=0;
	if( getIndexOn( col, index ) ){
		inthere=index->contains( col, idx );
		if( inthere ) idx=index->at( idx );
	}
	else{
		// full table search
		uint rrr=rows();
		for( uint i=0; i<rrr; i++ ){
			if( at( i )[col]==tc ){
				idx=i;
				inthere=true;
				break;
			}
		}
	}
	return inthere;
}

void QHaccTable::dropIndexOn( int col ){
	if( indexes[col] ){
		delete indexes[col];
		indexes[col]=0;
	}
}

bool QHaccTable::getIndexOn( int pos, int spos, QHaccTableIndex *& ret ) const{
	// get an index for pos if it exists return true if we find an index
	// (we don't check pki, because that can't be a composite index)
	ret=0;
	if( indexes[pos] && indexes[pos]->sorts( pos, spos ) ) ret=indexes[pos];
	return ret!=0;
}

bool QHaccTable::getIndexOn( int pos, QHaccTableIndex *& ret ) const {
	// get an index for pos if it exists return true if we find an index
	ret=0;
	if( pki && pki->sorts( pos ) ) ret=pki;
	else ret=indexes[pos];
	return ret!=0;
}

vector<uint> QHaccTable::igetWhere( const TableSelect& sel ) const {
	vector<uint> indxs;
	int check=sel.check();
	if( check==TableSelect::NO ) return indxs;

	if( check==TableSelect::ALL ){
		uint rrr=rows();
		for( uint i=0; i<rrr; i++ ) indxs.push_back( i );
	}
	else if( check!=TableSelect::NO ){
		TableCol model=sel.model();
		int col=sel.column();
		
		QHaccTableIndex * useme=0;
		if( getIndexOn( col, useme ) ){ // USE INDEX
			std::ostream * str=0;
			if( idebug( Utils::CURIOSITY, str ) ){
				*str<<"using index for "<<sel.toString()<<" of "<<name<<" as type "<<types[col]<<endl;
			}

			uint s=useme->starts( model );
			uint e=useme->ends( model );

			if( check==TableSelect::NE ){
				//cout<<"    idx says to omit "<<s<<"-"<<e<<endl;
				for( uint i=0; i<s; i++ ) indxs.push_back( useme->at( i ) );
				uint lim=rows();
				for( uint i=e; i<lim; i++ )	indxs.push_back( useme->at( i ) );
			}
			else{
				uint start=0, end=rows();
					
				if( check==TableSelect::EQ ){
					start=s;
					end=e;
				}
				
				else if( check==TableSelect::GT )	start=e;
				else if( check==TableSelect::LT )	end=s;
				else if( check==TableSelect::GE ) start=s;
				else if( check==TableSelect::LE ) end=e;
				
				//cout<<"    idx says "<<s<<"/"<<e<<", but logic says "<<start<<"/"<<end<<endl;
				
				for( uint i=start; i<end; i++ )	indxs.push_back( useme->at( i ) );
			}
		}
		else{ // NO INDEX
			// we need to check every row for matches SLOW!
			std::ostream * str=0;
			if( idebug( Utils::CURIOSITY, str ) )
				*str<<"not using index for "<<sel.toString()<<" of "<<name<<" as type "<<types[col]<<endl;

			const uint LIM=rows();
			for( uint i=0; i<LIM; i++ ){
				//cout<<"  checking "<<i<<": "<<data[i][col].gets()
				//	<<" as type "<<types[col]
				//	<<" returns "<<sel.check( data[i], types[col] )<<endl;

				if( sel.check( at( i ), types[col] ) ) indxs.push_back( i );
			}
		}
	}
	return indxs;
}

auto_ptr<QHaccResultSet> QHaccTable::getWhere( const TableGet& tg,
																							 vector<TableSelect> ts,
																							 uint& retrows ) const {
	// first, get the results as normal
	uint tgsz=tg.cnt();
	auto_ptr<QHaccResultSet> temp=getWhere( ts, retrows );

	// if we aren't selecting individual columns or we failed
	// to select anything, just return what we have
	if( tgsz==0 || retrows==0 ) return temp;

	// figure out what we're going to keep
	ColType * cts=new ColType[tgsz];
	TableCol * tcs=new TableCol[tgsz];
	
	int uqcol=-1;
	for( uint i=0; i<tgsz; i++ ){
		int j=tg[i];
		if( j>=cols ){
			
			std::ostream * str=0;
			if( ierror( Utils::ERROPER, str ) )
				*str<<"cannot get column "<<j<<" from table with "<<cols
						<<" columns (using 0 instead)"<<endl;
			j=0;
		}
		cts[i]=coltype( j );
			
		// unique TableGets only have one column, so this is a short loop
		if( tg.getMod( i )==TableGet::UQ ) uqcol=j;
	}
	
	// if we want uniqueness, just make an index
	if( uqcol>=0 ){
		QHaccTable * t2=new QHaccTable( cols, types );
		QHaccTableIndex useme( temp.get(), uqcol, types[uqcol] );
		vector<uint> unique=useme.unique();

		uint vsz=unique.size();
		for( uint i=0; i<vsz; i++ )	t2->add( temp->at( useme[unique[i]] ) );
		temp.reset( t2 );
		retrows=temp->rows();
	}
	// end of uniqueness junk

	// make sure we can return something
	auto_ptr<QHaccResultSet> ret( new QHaccResultSet( tgsz, cts ) );

	// here's where we actually get the columns we want
	ret->startLoad( retrows );
	for( uint i=0; i<retrows; i++ ){
		// now that we have some rows to deal with, select
		// only the columns we're interested in
		for( uint j=0; j<tgsz; j++ ) tcs[j]=temp->at( i ).get( tg[j] );
		ret->add( TableRow( tcs, tgsz ) );
	}
	ret->stopLoad();

	delete [] cts;
	delete [] tcs;

	return ret;
}

auto_ptr<QHaccResultSet> QHaccTable::getWhere( vector<TableSelect> ts,
																							 uint& retrows ) const {
	auto_ptr<QHaccResultSet> ret( new QHaccResultSet( cols, types ) );
	
	if( !ts.empty() ){
		// we're trying to use indices to fulfill all our selections, so
		// get a list of all our rows for each selection, and then
		// cycle through the smallest vector and look for matching
		// indices in the other vectors.

		const uint TSSZ=ts.size();
		uint smallest=0, smallestrr=rows();
		vector<uint> * selections=new vector<uint>[TSSZ];

		//cout<<"calling igetwhere"<<endl;
		for( uint i=0; i<TSSZ; i++ ){
			selections[i]=igetWhere( ts[i] );

			uint rr=selections[i].size();
			if( rr<smallestrr ){
				smallest=i;    // index of smallest vector
				smallestrr=rr; // number of rows in that vector
			}
		}

		//cout<<"done with igetwheres si="<<smallest<<"; srr="<<smallestrr<<endl;
		//for( uint i=0; i<TSSZ; i++ ) cout<<i<<": "<<selections[i].size()<<endl;

		if( TSSZ>1 ){
			if( smallestrr>0 ){ // if our smallest vector has 0 elements, 
				                  // there isn't much point in looking further

				// cycle through the vectors finding the intersections...
				// we'll start with the smallest vector because that will probably
				// result in the fewest matches. 

				// matches is our current set of rows that should be included in
				// the final resultset. We seed matches with the first set

				deque<uint> matches;
				copy( selections[smallest].begin(), selections[smallest].end(),
							front_insert_iterator<deque<uint> >( matches ) );
				//cout<<"matches has "<<matches.size()<<" rows initially"<<endl;

				// now we can cycle...
				for( uint i=0; i<TSSZ; i++ ){
					if( i!=smallest ){
						// set_intersection relies on two sorted iterators
						sort( matches.begin(), matches.end() );
						sort( selections[i].begin(), selections[i].end() );

						deque<uint> matches2;
					
						set_intersection( matches.begin(), matches.end(), 
															selections[i].begin(), selections[i].end(),
															front_insert_iterator<deque<uint> >( matches2 ) );
						//cout<<"intersection leaves: "<<matches2.size()<<" rows"<<endl;
						matches=matches2;
					}
				}
				
				// at this point, matches hold the final set of indices to include,
				// so iterate over the deque and insert into the resultset
				ret->startLoad( matches.size() );
				for( deque<uint>::iterator it=matches.begin(); it!=matches.end();
							 it++ )	ret->add( at( *it ) );
				ret->stopLoad();
			} // smallestrr>0
		} // TSSZ>1
		else{
			// no hash-sorting necessary, just load
			const uint VSZ=selections[0].size();
			ret->startLoad( VSZ );
			for( uint i=0; i<VSZ; i++ ) ret->add( at( selections[0][i] ) );
			ret->stopLoad();
		}

		delete [] selections;		
	} // ts.empty()
	else ret->load( this );

	retrows=ret->rows();
	return ret;
}

auto_ptr<QHaccResultSet> QHaccTable::getWhere( const TableSelect& sel,
																							 uint& retrows ) const {
  vector<TableSelect> v( 1, sel );
  auto_ptr<QHaccResultSet> rslt=getWhere( v, retrows );
  return rslt;
}

TableRow QHaccTable::getWhere( const TableSelect& sel ) const {
	TableRow ret;
	uint rr=0;
	auto_ptr<QHaccResultSet> rslt=getWhere( sel, rr );
	if( rr>0 ) ret=rslt->at( 0 );
	return ret;
}

void QHaccTable::iadd( uint ssz ){ 
	//reindex(); 
	if( !loading ){
		for( int i=0; i<cols; i++) if( indexes[i] ) indexes[i]->newvalat( ssz );
		if( pki )	pki->newvalat( ssz );
	}
}

void QHaccTable::iresize(){ remake(); }

void QHaccTable::deleteWhere( const TableSelect& sel ){
	// get the indices that need to be removed and remove them
	// all before doing any reindexing
	int check=sel.check();
	if( check==TableSelect::NO ) return;
	if( check==TableSelect::ALL ) clear();
	else{
		vector<uint> idxs=igetWhere( sel );

		const uint vsz=idxs.size();
		if( vsz>0 ){
			// the indices are sorted, so iterate from the
			// back, deleting positions as they show up
			for( vector<uint>::reverse_iterator it=idxs.rbegin(); 
					 it!=idxs.rend(); it++ ){

				//cout<<"calling remvalat for "<<*it<<endl;
				for( int i=0; i<cols; i++) 
					if( indexes[i] ) indexes[i]->remvalat( *it );
				if( pki )	pki->remvalat( *it );

				data.erase( data.begin()+*it );
			}
			//reindex();
		}
	}
}

void QHaccTable::addIndexOn( int col ){
	// create and index on a column;
	if( !indexes[col] )
		indexes[col]=new QHaccTableIndex( this, col, types[col] );
}

void QHaccTable::addIndexOn( int col, int subcol ){
	// create and index on a column;
	QHaccTableIndex * ret=0;
	if( !getIndexOn( col, subcol, ret ) ){
		indexes[col]=new QHaccTableIndex( this, col, types[col],
																			subcol, types[subcol] );
	}
}

TableCol QHaccTable::max( int col ) {
	QHaccTableIndex * idx=0;
	if( getIndexOn( col, idx ) ) return idx->max();
	else{
		TableCol hi;
		for( uint i=0; i<rows(); i++ ){
			TableRow row=at( i );
			if( row[col].compareTo( col, types[col] )>0 ) hi=row[col];
		}
		return hi;
	}
}

TableCol QHaccTable::min( int col ) {
	QHaccTableIndex * idx=0;
	if( getIndexOn( col, idx ) ) return idx->min();
	else{
		TableCol low;
		for( uint i=0; i<rows(); i++ ){
			TableRow row=at( i );
			if( row[col].compareTo( low, types[col] )<0 ) low=row[col];
		}
		return low;
	}
}

void QHaccTable::reindex(){
	if( !loading ){
		std::ostream * str=0;
		bool writer=idebug( Utils::CURIOSITY, str );
		
		for( int i=0; i<cols; i++){
			if( indexes[i] ){
				indexes[i]->reindex();
				if( writer ) *str<<"reindex called on "<<name<<"::"<<i<<endl;
			}
		}

		if( pki ){
			if( writer ) *str<<"reindex called on "<<name<<"::"<<pki->sorts()<<endl;
			pki->reindex();
		}
	}
}

void QHaccTable::remake(){
	if( !loading ){
		std::ostream * str=0;
		bool writer=idebug( Utils::CURIOSITY, str );
		for( int i=0; i<cols; i++){
			if( indexes[i] ){
				if( writer ) *str<<"remaking index on "<<name<<"::"<<i<<endl;
				indexes[i]->remake();
			}
		}
		if( pki ){
			if( writer ) *str<<"remaking index on "<<name<<"::"<<pki->sorts()<<endl;
			pki->remake();
		}
	}
}

void QHaccTable::updateWhere( const TableSelect& sel, const TableRow& row ){
	int valid=QHaccResultSet::verifyRow( row );
	if( valid<VALID ) return;

	int check=sel.check();
	if( check!=TableSelect::NO ){

		if( check==TableSelect::ALL ) {
			uint size=data.size();
			data.clear();
			for( uint i=0; i<size; i++ ) data.push_back( new TableRow( row ) );
		}
		else{
			vector<uint> idxs=igetWhere( sel );
			for( vector<uint>::reverse_iterator it=idxs.rbegin(); 
					 it!=idxs.rend(); it++ ){
				data.erase( data.begin()+*it );
				data.insert( data.begin()+*it, new TableRow( row ) );
			}
		}
		reindex();
	}
}

void QHaccTable::updateWhere( const TableSelect& sel, 
															const TableUpdate& upds ){
	const uint LIM=upds.cnt();
	
	vector<uint> idxs=igetWhere( sel );
	const uint vsz=idxs.size();

	// update all positions that need updates
	for( uint i=0; i<vsz; i++ ){
		const uint rownum=idxs[i];
		for( uint j=0; j<LIM; j++ ) data[rownum]->set( upds[j] );
	}

	if( vsz>0 ){
		// now reindex changed columns
		for( uint i=0; i<LIM; i++ ){
			int col=upds[i].getp();
			if( indexes[col] ) indexes[col]->reindex();

			// import/export can change IDs, so we
			// might as well check pki for resort
			if( pki && pki->sorts( col ) ) pki->reindex();
		}
	}
}


/***********************************************************/
/* QHACCTABLEINDEX                                         */
/*   an index for a column in a QHACCTABLE. This works on  */
/*   any type of column, and uses a quicksort to provide   */
/*   the ordering.                                         */
/***********************************************************/
QHaccTableIndex::QHaccTableIndex( QHaccResultSet * table, int f, ColType ft, 
																	int s, ColType st ){
	init( table, f, ft, s, st );
	reindex();
}


QHaccTableIndex& QHaccTableIndex::operator=( const QHaccTableIndex& model ){
	if( &model!=this ){
		init( model.data, model.field, model.ftype,
					model.subfield, model.subtype );
		for( uint i=0; i<model.data->rows(); i++ ) lookup[i]=model.lookup[i];
	}
	return *this;
}

QHaccTableIndex::QHaccTableIndex( const QHaccTableIndex& model ) {
	init( model.data, model.field, model.ftype,
				model.subfield, model.subtype );
	for( uint i=0; i<model.data->rows(); i++ ) {
		lookup.push_back( model.lookup[i] );
	}
}

void QHaccTableIndex::init( QHaccResultSet * table, int f1, ColType f1t,
														int f2, ColType f2t ){
	data=table;

	uint rows=0;
	if( data ) rows=data->trows();

	lookup.clear();
	for( uint i=0; i<rows; i++ ) lookup.push_back( i );
	field=f1;
	ftype=f1t;
	subfield=f2;
	subtype=f2t;
}

QHaccTableIndex::~QHaccTableIndex(){}

void QHaccTableIndex::sorts( int& i, ColType& it, int& j, ColType& jt ) const {
	i=field;
	it=ftype;
	j=subfield;
	jt=subtype;
}

int QHaccTableIndex::sorts() const { return field; }
bool QHaccTableIndex::sorts( int i ) const {
	if( field==-1 ) return false;
	return( i==field );
}
bool QHaccTableIndex::sorts( int i, int j ) const { 
	if( field==-1 ) return false;
  return( i==field && j==subfield );
}

const TableRow& QHaccTableIndex::dat( uint i ) const {
	return data->at( lookup[i] );
}

uint QHaccTableIndex::at( uint i ) const { return lookup[i]; }
uint QHaccTableIndex::operator[]( uint i ) const { return lookup[i]; }

void QHaccTableIndex::remake(){ reindex(); }

// FIXME: these are globals, but I don't know how to get rid of them!
uint compara=0, scompara=0;
ColType fcomp, scomp;
int ffield, sfield;

bool compo::operator()( const TableRow * x, const TableRow * y ) const {
	compara++;
	int rslt=( *x )[ffield].compareTo( ( *y )[ffield], fcomp );
	if( sfield>-1 && rslt==0 ){
		// need a secondary comparison
		scompara++;
		rslt=( *x )[sfield].compareTo( ( *y )[sfield], scomp );
	}
	return rslt<0;
}

void QHaccTableIndex::reindex(){
	uint rws=data->rows();
	lookup.clear();
	if( data->isEmpty() ) return;
	compara=scompara=0;

	//for( uint i=0; i<rws; i++ ) lookup[i]=i;
	//if( field>-1 ) qisort( 0, rws-1 );
	//cout<<"sorted an index! size: "<<rws<<" comparisons: "<<compara<<"/"<<scompara<<endl;

	fcomp=ftype;
	ffield=field;
	scomp=subtype;
	sfield=subfield;

	mapper.clear();
	for( uint i=0; i<rws; i++ )
		mapper.insert( pair<const TableRow *, uint>( &( data->at( i ) ), i ) );

	rws=0;
	for( multimap<const TableRow *, uint, compo >::iterator iter=mapper.begin();
			 iter!=mapper.end(); iter++ ){
		lookup.push_back( iter->second );
	}
	//cout<<"sorted an index! size: "<<rws<<" comparisons: "<<compara<<"/"<<scompara<<endl;
}

void QHaccTableIndex::newvalat( uint datapos ){
	//cout<<"newvalat "<<datapos<<":"<<data->at( datapos ).toString()<<endl;
	fcomp=ftype;
	ffield=field;
	scomp=subtype;
	sfield=subfield;
	compara=scompara=0;
	mapper.insert( pair<const TableRow *, uint>( &( data->at( datapos ) ), 
																							 datapos ) );
	//cout<<"newvalat! size: "<<data->rows()<<" comparisons: "
	//<<compara<<"/"<<scompara<<endl;
	lookup.clear();
	for( multimap<const TableRow *, uint, compo>::iterator iter=mapper.begin();
			 iter!=mapper.end(); iter++ ) lookup.push_back( iter->second );
}

void QHaccTableIndex::remvalat( uint datapos ){
	// remove the index position that holds the row at position datapos in
	// the parent table. we can't quite take advantage of mapper's find function
	// because there may be duplicates in the map. instead, we just cycle through
	// lookup until we find our victim, and then erase it

	/*
	fcomp=ftype;
	ffield=field;
	scomp=subtype;
	sfield=subfield;
	compara=scompara=0;
	*/
	//TableRow row=data->at( datapos );
	//cout<<"index sorts "<<sorts()<<"; remvalat "<<datapos<<endl<<"      : "<<row.toString()<<endl;
	
	bool found=false;

	// we need to search for the right row in our map. if we get to a row that
	// is positioned later in the sort, we need to decrement the second value
	// so that it matches the new true place in the qhacctable vector
	for( multimap<const TableRow *, uint, compo>::iterator mit=mapper.begin();
			 mit!=mapper.end(); mit++ ){		
		if( mit->second==datapos ){
			//cout<<"mapper: "<<mit->first->toString()<<endl;
			
			mapper.erase( mit );
			found=true;
			break;
		}
	}
			
	if( found ){
		// we found our row and removed it; now we need to decrement all map keys
		// that reference row positions larger than our table's vector, or else
		// we'll eventually reference a row position that no longer exists.
		// while we're at it, we need to rebuild our lookup vector
		for( multimap<const TableRow *, uint, compo>::iterator mit=mapper.begin();
				 mit!=mapper.end(); mit++ ){		
			if( mit->second>=datapos )	mit->second--;
		}

		lookup.clear();
		for( multimap<const TableRow *, uint, compo>::iterator iter=mapper.begin();
				 iter!=mapper.end(); iter++ ) lookup.push_back( iter->second );
	}
}


uint QHaccTableIndex::starts( const TableCol& col ) const {
	// return the position where the given TableCol
	// starts. if a perfect match can't be found, 
	// return the position where the col would be inserted
	if( data->isEmpty() || field==-1 ) return 0;
	/*
	cout<<"into starts for "<<col.gets()<<endl;
	uint r=data->rows(); 
	if( r>100 ) r=60;
	cout<<"in "<<r<<" data rows"<<endl;
	for( uint i=0; i<r; i++ )
		cout<<i<<":  "<<data->at( i ).get( field ).gets()<<endl;
	cout<<"--"<<endl;
	*/
	int start=-1, end=( int )data->rows();
	int idx=0;
	compara=0;
	while( end-start>1 ){
		idx=( start+end )/2;
		//cout<<"s="<<start<<"; e="<<end<<"; idx="<<idx
		//<<"; data="<<dat( idx).get( field ).gets()<<endl;
		if( dat( idx ).get( field ).compareTo( col, ftype )<0 ) start=idx;
		else end=idx;
		compara++;
	}
	idx=end;
	//cout<<"start found in "<<compara<<" compares"<<endl;
	//if( idx<data->rows() && dat( idx ).get( field )!=col ) idx--;
	//cout<<" returning "<<idx<<endl;
	return idx;
}

uint QHaccTableIndex::ends( const TableCol& col ) const {
	// find the end position of the given TableCol. 
	// if a perfect match can't be found, return 
	// the position before the first position that is
	// greater than the given TableCol
	if( data->isEmpty() || field==-1 ) return data->rows();

	//uint r=data->rows(); 
	//cout<<"into ends for "<<col.gets()<<endl;
	//cout<<"in "<<r<<" data rows"<<endl;
	//for( uint i=0; i<r; i++ )
	//	cout<<i<<":  "<<dat( i ).get( field ).gets()<<endl;
	//cout<<"--"<<endl;

	int start=-1, end=( int )data->rows();
	int idx=0;
	compara=0;
	while( end-start>1 ){
		idx=( start+end )/2;
		//cout<<"s="<<start<<"; e="<<end<<"; idx="<<idx
		//		<<"; data="<<dat( idx).get( field ).gets()<<endl;
		if( dat( idx ).get( field ).compareTo( col, ftype )>0 ) end=idx;
		else start=idx;
		compara++;
	}
	idx=start;
	//if( idx==-1 || dat( idx ).get( field )==col ) idx++;
	idx++;
	//cout<<"ends returning "<<idx<<endl;
	//cout<<"end found in "<<compara<<" compares"<<endl;
	return idx;
}

bool QHaccTableIndex::contains( const TableCol& col ) const {
	uint junk=0;
	return contains( col, junk );
}

bool QHaccTableIndex::contains( const TableCol& col, uint& idx ) const {
	// if we're not keeping an index, we can't tell what we have,
	// but we probably don't care about duplicates, so it doesn't matter
	//cout<<"into index contains for ("<<field<<" as "<<ftype<<") "<<col.gets()<<endl;
	if( field==-1 || data->isEmpty() ) return false;

	idx=starts( col );

	//if( idx<data->rows() ){
	//cout<<"starts is "<<idx<<"; dat("<<idx<<") is "<<dat( idx ).get( field ).gets()<<"; col is "<<col.gets()<<"; equal? "<<( dat( idx ).get( field )==col ? "yes" : "no" )<<endl;
	//}

	if( idx<data->rows() ) return ( dat( idx ).get( field )==col );
	else return false;
}

vector<uint> QHaccTableIndex::unique() const {
	uint end=data->rows();

	uint curloc=0;	
	vector<uint> ret;
	while( curloc<end ){
		ret.push_back( curloc );
		curloc=ends( dat( curloc ).get( field ) );
	}
	return ret;
}

TableCol QHaccTableIndex::max() const {
	if( field==-1 || data->isEmpty() ) return TableCol();
	return dat( data->rows()-1 ).get( field );
}

TableCol QHaccTableIndex::min() const {
	if( field==-1 || data->isEmpty() ) return TableCol();
	return dat( 0 ).get( field );
}