// SecondaryIndex.cpp
// CSI 2131 Asst 2b by Naim R. El-Far (naim@discover.uottawa.ca)
// CSI 2131 - Winter 2006 - Prof. L.M. Moura

// File:	SecondaryIndex.cpp
// Desc:	Class SecondaryIndex definitions

#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <sstream>
#include <assert.h>
#include "SecondaryIndex.h"
#include "KeyList.h"
using namespace std;

SecondaryIndex::SecondaryIndex() { //Default constructor
	indexFileName = "";
	indexFileStream;
	numberOfRecordsInIndex = 0;
	pKeyList = NULL;
}

SecondaryIndex::SecondaryIndex(string secIndexFileName, string keyListFileName) { //Filename constructor
	indexFileName = secIndexFileName;
	indexFileStream.open(indexFileName.c_str(), ios::out);
	indexFileStream.close();
	indexFileStream.open(indexFileName.c_str(), ios::in | ios::out | ios::binary);
	if (!indexFileStream) {
		cerr << endl
			 << "------------------------------------------------" << endl
			 << "Error! Specified index file could not be opened!" << endl
			 << "------------------------------------------------" << endl
			 << endl;
		exit(1);
	}
	else
		cout << "Index file " << secIndexFileName << " opened successfully." << endl;
	
	pKeyList = new KeyList(keyListFileName);

	numberOfRecordsInIndex = 0;
}

SecondaryIndex::~SecondaryIndex(){ //Destructor
	indexFileStream.close();
	delete pKeyList;
}

void SecondaryIndex::SpaceFormatLastName(string& lastName) { //Given a last name, format it so that it would adhere to the 20-character field length specified
	stringstream lastNameStream(stringstream::in | stringstream::out);
	lastNameStream << setw(20) << setiosflags(ios::left) << lastName;
	getline(lastNameStream, lastName);
}

void SecondaryIndex::Insert(string lastName, long int listStart) { //Given a last name and a list start value, insert the tuple where the file pointer currently is. Another function has to position the file pointer; this function simply inserts at the current file pointer position
	//Write last name in text mode
	indexFileStream << setw(20) << setiosflags(ios::left) << lastName;

	//Write list start value in binary mode after converting from decimal to binary number
	indexFileStream.write((char const*)(&listStart), 4);
}

void SecondaryIndex::ReadByRRN(long int RRN, string& lastName, long int& listStart) { //Given a RRN and a string and long int in which to store the read values, retrieve the last name and list start values and sotre them in the given variables
	long int entryOffset = indexFileStream.tellg();
	
	indexFileStream.clear();
	indexFileStream.seekg(RRN * SEC_INDEX_RECORD_SIZE);

	char lastNameChar[20];
	indexFileStream.read(lastNameChar, 20);
	indexFileStream.read((char*)(&listStart), 4);

	lastName = "";
	for (int i = 0 ; i < 20 ; i++)
		lastName = lastName + lastNameChar[i];

	indexFileStream.clear();
	indexFileStream.seekg(entryOffset);
}

void SecondaryIndex::WriteByRRN(long int RRN, string lastName, long int listStart) { //Store the given tuple at the given RRN position
	long int entryOffset = indexFileStream.tellg();

	indexFileStream.clear();
	indexFileStream.seekp(RRN * SEC_INDEX_RECORD_SIZE);

	Insert(lastName, listStart);

	indexFileStream.clear();
	indexFileStream.seekg(entryOffset);
}

void SecondaryIndex::ShiftIndexRecords(long int startingRRN) {
	long int entryOffset = indexFileStream.tellg();
	indexFileStream.clear();
	
	long int currentRRN = numberOfRecordsInIndex - 1;
    	
	bool done = false;
	while (!done) {
		if (startingRRN > currentRRN) 
			done = true; //No shifting necessary if inserting at the end
		else {
			string tempStudentNumber = "";
			long int tempListStart = 0;
			ReadByRRN(currentRRN, tempStudentNumber, tempListStart);
			WriteByRRN(currentRRN + 1, tempStudentNumber, tempListStart);
			currentRRN--;
			if (currentRRN == startingRRN - 1)
				done = true;
		}
	}
	
	indexFileStream.clear();
	indexFileStream.seekg(entryOffset);
}

void SecondaryIndex::Addition(string lastName, string studentNumber, long int byteOffset) {
	//Housekeeping
	indexFileStream.clear();

	//Convert to canonical form
	CapitalizeLastName(lastName);
	
	//Look for an entry with the same last name in the index
	bool		foundLastNameInIndex = false;
	long int	foundListStart = -1;
	long int	foundRRN = -2;
	for (int i = 0 ; i < numberOfRecordsInIndex ; i++) {
		string retrievedLastName = "";
		long int retrievedListStart = -1;
		ReadByRRN(i, retrievedLastName, retrievedListStart);
		string formattedLastName = lastName;
		SpaceFormatLastName(formattedLastName);
		if (retrievedLastName.compare(formattedLastName) == 0) {
			foundLastNameInIndex = true;
			foundListStart = retrievedListStart;
			foundRRN = i;
			break;
		}
	}
	
	//If there is no entry with the same last name
	if (!foundLastNameInIndex) {
		long int	positionWhereToInsert = -1; //Holds the RRN for the record to be inserted in alphabetical order
		bool		positionWhereToInsertFound = false;
		for (int i = 0 ; i < numberOfRecordsInIndex && !positionWhereToInsertFound ; i++) {
			string retrievedLastName = "";
			long int retrievedListStart = -1;
			ReadByRRN(i, retrievedLastName, retrievedListStart);
			if (retrievedLastName.compare(lastName) == 0) { //If the retrieved last name is identical to the one we are inserting, then something's wrong since we can't have duplicates
				cerr << endl
				 	 << "-------------------------------------------" << endl
					 << "Error! Duplicates found in secondary index!" << endl
					 << "-------------------------------------------" << endl
					 << endl;
				exit(1);
			}
			else if (retrievedLastName.compare(lastName) < 0) {} //Otherwise if the retrieved last name is alphabetically less than the given one, then keep proceeding
			else if (retrievedLastName.compare(lastName) > 0) { //If we're retrieving a record alphabetically greater than the given record, then this is where we want to insert the new record
				positionWhereToInsertFound	= true;
				positionWhereToInsert = i;
				break;
			}
		}
		if (!positionWhereToInsertFound) { //At this point, if we've gone through all the records and none of them is greater than the given last name, then we must insert the given last name at the end of the index
			positionWhereToInsert = numberOfRecordsInIndex;
		}
		
		assert(positionWhereToInsert != -1); //Make sure we have found a valid value where to insert the new data

		ShiftIndexRecords(positionWhereToInsert); //Make room for the record to be inserted in the secondary index
		long int newRecordListStart = pKeyList->numberOfKeysInList; //A new record in the secondary index needs a new entry in the key list
		pKeyList->WriteByRRN(newRecordListStart, studentNumber, -1); //Insert the record at the end of the key list (at the end since it is for a brand new last name)
		pKeyList->IncrementNumberOfKeys(); //Increment the number of keys in the key list
		WriteByRRN(positionWhereToInsert, lastName, newRecordListStart); //Insert the record in the correct RRN position
		numberOfRecordsInIndex++; //Increment the number of records in the secondary index
	}

	//Otherwise, if there is an entry with the same last name
	else {
		long int	newListHead = pKeyList->InsertIntoInvertedList(foundListStart, studentNumber);
		if (newListHead != foundListStart) { //If we inserted at the beginning of a list thereby changing the list head
			string retrievedLastName = "";
			long int retrievedListStart = -1;
			ReadByRRN(foundRRN, retrievedLastName, retrievedListStart);
			WriteByRRN(foundRRN, retrievedLastName, newListHead);
		}
	}
}

void SecondaryIndex::PrintIndex(ostream& str) {
	str << setw(20) << setiosflags(ios::left) << "Last Name" << '\t' << setw(10) << setiosflags(ios::left) << "List Start" << endl
		<< setw(20) << setiosflags(ios::left) << "---------" << '\t' << setw(10) << setiosflags(ios::left) << "----------" << endl;
	
	string lastName = "";
	long int listStart = -2;
	for (int i = 0 ; i < numberOfRecordsInIndex ; i++) {
		ReadByRRN(i, lastName, listStart);
		str << setw(20) << setiosflags(ios::left) << lastName << '\t' << setw(10) << setiosflags(ios::left) << listStart << endl;
	}
	str << "--END OF SEC INDEX--" << endl
		<< endl;
}

long int SecondaryIndex::BinarySearch(string givenLastName) {
	//Convert to canonical form
	CapitalizeLastName(givenLastName);
	
	long int entryPoint = indexFileStream.tellg();
	indexFileStream.clear();
	
	long int low = 0; //Lower bound of the binary search
	long int high = numberOfRecordsInIndex - 1; //Higher bound of the binary search
	
	string		retrievedLastName	= "";
	long int	retrievedListStart	= -1;
	SpaceFormatLastName(givenLastName);
	
	while (low <= high) {
		long int guess = (high + low) / 2;
		ReadByRRN(guess, retrievedLastName, retrievedListStart);
		if (retrievedLastName.compare(givenLastName) == 0) {
			indexFileStream.clear();
			indexFileStream.seekg(entryPoint);
			return retrievedListStart; //Found
		}
		else if (retrievedLastName.compare(givenLastName) > 0)
			high = guess - 1;
		else //if (retrievedStudentNumberInt < givenStudentNumberInt)
			low = guess + 1;
	}
	indexFileStream.clear();
	indexFileStream.seekg(entryPoint);
	return -1; //If we reach this point, then no matching record was found
}

void SecondaryIndex::CapitalizeLastName(string& lastName) {
	for (unsigned int i = 0 ; i < lastName.size() ; i++) {
		if (lastName[i] >= 97 && lastName[i] <= 122) //Capitalize only lower case letters
			lastName[i] = lastName[i] - 32;
	}
}