/*
 * CSI2131 Winter 2005
 *
 * Assignment#2 Solution : Implementation of The Index class
 *
 * Shantanu Das 
 */


#include "Index.h"


int Index::resize(unsigned int sz){		//private method for increasing the size of the array.
	if (sz <= size) return size;			//size is already big enough, do nothing
	
	struct ind_item *NewArr = new ind_item[sz];     //allocate new array
	if(NewArr==NULL)  {
		cerr<<"Error: Can't allocate memory..."<<endl; 
		exit(1);
	}
	for(int i=0;i<size;i++)				// copy exisitng elements to new array
		NewArr[i]=Array[i];
	size = sz;							// change size
	delete[] Array;						// delete the old array	
	Array = NewArr;	
	return size;
}


Index::Index() 					// creates an empty index 
{
	Array = new ind_item[minsize];		//initially allocate array of minsize
	if(Array==NULL)  {
		cerr<<"Error: Can't allocate memory..."<<endl; 
		exit(1);
	}
	size = minsize;						
	last = -1;							// no entries in index yet
}


Index::~Index() 
{ 
	delete[] Array;
}

int Index::insert(long k, long ofs)
{
	if(last==(size-1))				// if array filled up, double the size
		resize(2*size);
	last++;
	int i;
	for(i=last-1;i>=0 && (Array[i].key > k);i--)	//go to the correct position
		Array[i+1]=Array[i];
	Array[i+1].key=k;				// insert new entry in the correct position	
	Array[i+1].offset=ofs;
	return (last+1);				// returns the current size of index.
}


long Index::search(long k)			// binary search for the key k 
{							// returns the offset, if found; returns -1 otherwise.
	int low=0;
	int high=last;
	int i;
	while( low <= high ){
		i=(low+high)/2;
		if(k < Array[i].key)			// key k is in the first half
			high = i-1;
		else if(k > Array[i].key)		// key k is in the second half
			low = i+1;
		else 
			return Array[i].offset;		// found key k
	}
	return -1;							// Not found

}