/* NOTE: 
   This program has been modified to be a PC_VC++ 6.0 version, you may need to 
   modify it in other OS/platforms.
 */


// hash.h

#ifndef _HASH_H_
#define _HASH_H_

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#include "BTree.h"

#define TABLE_SIZE	512

#define UPC_LENGTH	14
#define TITLE_LENGTH	30
#define DATA_LENGTH	40
#define RELDAYS_LENGTH	6
#define NUMCOPY_LENGTH	6
#define OPTYPE_LENGTH	3
#define OPPAR_LENGTH	6
#define RELDATE_LENGTH	10
#define MRECORD_LENGTH	96

static int daysToMonthNormalYear[] = { 0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365 };
static int daysToMonthLeapYear[] = { 0, 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366 };

static const char DELETION[] = "99999999999999";
static const char EMPTY[] = "00000000000000";

/*
 * A DVD record
 */
class Rec
{
public:
	
	char upc[UPC_LENGTH+1]; 		// Universal Product Code, the primary key
	char title[TITLE_LENGTH+1];	// the title of the DVD
	char data[DATA_LENGTH+1];       	// studio and director
	char relDays[RELDAYS_LENGTH+1]; 	// release days since Jan.1, 1900
	char numCopy[NUMCOPY_LENGTH+1]; 	// number of DVD copies
	char opType[OPTYPE_LENGTH+1];   	// transaction inquiries
	char opParam[OPPAR_LENGTH+1];   	// strore locations
	char relDate[RELDATE_LENGTH+1]; 	// release date (month/day/year).
	char record[MRECORD_LENGTH+2];  	// one line record of master file
	char endMarker[2];              	// endline marker

	string toString();		// return a string representation of a record
};


/*
 * A hash table
 */
class Hash {
public:
	Hash(char * fileName, int tableSiize = TABLE_SIZE);	// constructor

	~Hash();						// destructor
	
	int searchForInsert(char *upCode, int key);	// find a empty slot for insertion

	int searchForChange(char *upCode, int key);	// find the matched slot for change/deletion

	int insert(Rec &r, int key);			// insert a record

	int deleteRec(Rec &rec, int key);			// delete a record

	int getKey(char * upCode);			// return the hash key

	int readRec(Rec &rec, int key);			// read a record to memory

	int writeRec(Rec &rec, int key);			// write a record to file

	// convert relative daves into date
	void convertToDate(int days, int *y, int *m, int *d);

	// hash initial sequential master file into hash table, and put title-key into B+ tree
	void hashMaster(BTree &bt, char *masterf);		

	void print(int key);				// display a record

	void print();					// display all valid records

	int getSize() { return size; }			// return the size of the hash table

	int getNumRec() { return numRec; }			// return the number of records in the table
private:

	fstream * fs;					// the stream attached to the hash table

	int numRec;					// number of records in the table

	// the maximum number of records that hash table can hold
	int size;									

};

#endif

/*************************************************************************************************************/



// hash.cpp

#include "Hash.h"


/********************************************************************************
 * Action:                                                                      *
 *		construct a hash table object
 * Arguments:                                                                   *
 *		fileName  - the name of the file which will hold the hash table
 *		tableSize - the size of the hash table
 * Returns:                                                                     *
 *		an empty hash table 
 * Pre:                                                                         *
 *		the file either does not exist or is a text file
 * Post:                                                                        *
 *		
 ********************************************************************************/
Hash::Hash(char * file, int tableSize) { 
	fs = new fstream(file, ios::in | ios::out);
	if (!fs->is_open()) {
		cerr << "Error in opening new master file\n";
		exit(1);
	}
 
	Rec rec;
	numRec = 0;
	size = tableSize;
	// establish the new (hashed) master file
	for (int i= 0; i < size; i++)
	{
		for (int j=0; j < MRECORD_LENGTH; j++)
			rec.record[j] = '0';
		rec.record[MRECORD_LENGTH] = '\n';
		rec.record[MRECORD_LENGTH + 1] = '\0';
		fs->write(rec.record, MRECORD_LENGTH + 1);
	}
}


// destructor
Hash::~Hash() { fs->close(); }


/********************************************************************************
 * Action:                                                                      *
 *		convert a UPC into a hash key
 * Arguments:                                                                   *
 *		upc - the UPC to be converted
 * Returns:                                                                     *
 *		a valid hash key
 * Pre:                                                                         *
 *		upc is a 14 digit number
 * Post:                                                                        *
 *		
 * Algorithm:                                                                   *
 *		use the lower nine digits of upc to module the table size 
 ********************************************************************************/
int Hash::getKey(char *upc)
{
	if (strlen(upc) < 14) {
		cerr << "invalid UPC: " << upc << ". conversion of hash key failed\n";
		return (-1);
	}
	char lowerNine[10];
	for (int i = 0; i < 9; ++i)
		lowerNine[i] = upc[i+5];
	lowerNine[9] =  '\0';
	return (atoi(lowerNine) % size);
}



/********************************************************************************
 * Action:                                                                      *
 *		find a slot for insertion
 * Arguments:                                                                   *
 *		upc - the UPC of the DVD to be inserted
 *		key - the initial hash key
 * Returns:                                                                     *
 *		slot number,	if a valid slot is found
 *		-1,		if the record is alread in the table
 *		'size',		if the table is full
 * Pre:                                                                         *
 * Post:                                                                        *
 *		
 * Algorithm:                                                                   *
 *		if the initial slot is taken, jump seven slots to check if there 
 *		is a slot, and jump again if it is taken as well
 ********************************************************************************/
int Hash::searchForInsert(char * upc, int key) 
{
	Rec rec;
	int newKey = key;

	fs->seekg(static_cast<long>(key  * (MRECORD_LENGTH + 2)), ios::beg);
	fs->read(rec.upc, UPC_LENGTH);
	rec.upc[UPC_LENGTH] = '\0';

	if (strcmp(rec.upc, upc) == 0 ) {	// the record is there
		cout << "duplicate upc: " << rec.upc << endl;
		return (-1);
	}
	else if (strcmp(rec.upc, EMPTY) && strcmp(rec.upc, DELETION))
	{		// the slot is taken, find the next slot
		newKey += 7;

		while (newKey != key)
		{
			if (newKey >= size)
				newKey -= size;

			fs->seekg(static_cast<long>(newKey * (MRECORD_LENGTH + 2)), ios::beg);
			fs->read(rec.upc, UPC_LENGTH);
			rec.upc[UPC_LENGTH] = '\0';
			if (!strcmp(rec.upc, EMPTY) || !strcmp(rec.upc, DELETION))
   				break;
			else
				newKey += 7;
		}
		if (key == newKey)
			return size;
	}
	return newKey;

}


/********************************************************************************
 * Action:                                                                      *
 *		find the slot whose UPC matches 'upc'
 * Arguments:                                                                   *
 *		upc - the UPC to be matched
 *		key - the initial slot
 * Returns:                                                                     *
 *		the slot-number if a match is found, -1 otherwise
 * Pre:                                                                         *
 *		
 * Post:                                                                        *
 *		
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
int Hash::searchForChange(char *upc, int key) {
	Rec recM;
	readRec(recM, key);
	if (strcmp(recM.upc, upc) != 0)
	{	// the slot is taken, find the next available address.
		int oldKey = key;
		key += 7;

    	while (key != oldKey)
		{
			if (key >= size)
				key -= size;
	   		fs->seekg(static_cast<long>(key * (MRECORD_LENGTH + 2)), ios::beg);
	   		fs->read(recM.upc, UPC_LENGTH);
	   		recM.upc[UPC_LENGTH] = '\0';

	   		if (strcmp(recM.upc, upc) == 0 )
   	      		break;
	   		else
   				key += 7;
   	   	}
		if (key == oldKey)
			key = -1;
	}
	return key;
}


/********************************************************************************
 * Action:                                                                      *
 *		insert a DVD record into hash table at slot 'key'
 * Arguments:                                                                   *
 *		rec - the record to be inserted
 *		key - the slot number to be inserted
 * Returns:                                                                     *
 *		1 for a successful insertion, 0 otherwise
 * Pre:                                                                         *
 *		
 * Post:                                                                        *
 *		
 ********************************************************************************/
int Hash::insert(Rec &rec, int key) {
	if (writeRec(rec, key)) {
		numRec++;
		return 1;
	}
	cerr << "error in inserting Rec " << rec.toString() << " for key " << key << endl;
	return 0;
}


/********************************************************************************
 * Action:                                                                      *
 *		delete a DVD record from the hash table at slot 'key'
 * Arguments:                                                                   *
 *		rec - the record to be deleted
 *		key - the slot number to be deleted
 * Returns:                                                                     *
 *		1 for a successful deletion, 0 otherwise 
 * Pre:                                                                         *
 *		
 * Post:                                                                        *
 *		
 * Algorithm:                                                                   *
 *		mark the UPC region with 'DELETION'
 ********************************************************************************/
int Hash::deleteRec(Rec &rec, int key) {
	strcpy(rec.upc, DELETION);	// mark UPC with 9s
	if (writeRec(rec, key)) {
		numRec--;
		return 1;
	}
	cerr << "error in deleting Rec " << rec.toString() << " for key " << key << endl;
	return 0;
}


/********************************************************************************
 * Action:                                                                      *
 *		read the contents of a record from file into memory 'rec'
 * Arguments:                                                                   *
 *		rec - the object to hold the record
 *		key - the slot where the record appears in file
 * Returns:                                                                     *
 *		 for a successful reading, 0 otherwise
 * Pre:                                                                         *
 ********************************************************************************/
int Hash::readRec(Rec &rec, int key) {
	if (key >= 0 && key < size) {
		fs->seekg(key * (MRECORD_LENGTH + 2), ios::beg);
		if (fs->read(rec.upc, UPC_LENGTH) && fs->read(rec.title, TITLE_LENGTH) 
			&& fs->read(rec.data, DATA_LENGTH) && fs->read(rec.relDays, RELDAYS_LENGTH) 
			&& fs->read(rec.numCopy, NUMCOPY_LENGTH) && fs->read(rec.endMarker, 1)) {
			// mark the end of string
			rec.upc[UPC_LENGTH] = '\0';
			rec.title[TITLE_LENGTH] = '\0';
            rec.data[DATA_LENGTH] = '\0';
            rec.relDays[RELDAYS_LENGTH] = '\0';
            rec.numCopy[NUMCOPY_LENGTH] = '\0';
            rec.endMarker[1] = '\0';
			return 1;
		} else {
			cerr << "Error in reading hash master file for key: " << key << "\n";
			return 0;
		}
	}

	cerr << "invalid hash key: " << key << "in reading\n";
	return 0;
}

/********************************************************************************
 * Action:                                                                      *
 *		write a DVD record into file
 * Arguments:                                                                   *
 *		rec - the record
 *		key - the slot where to be written
 * Returns:                                                                     *
 *		 for a successful written, 0 otherwise
 * Pre:                                                                         *
 *		
 * Post:                                                                        *
 *		
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
int Hash::writeRec(Rec &rec, int key) {
	if (key >= 0 && key < size) {
		fs->seekg(key * (MRECORD_LENGTH + 2), ios::beg);
		rec.upc[UPC_LENGTH] = '\0';
		rec.title[TITLE_LENGTH] = '\0';
        rec.data[DATA_LENGTH] = '\0';
        rec.relDays[RELDAYS_LENGTH] = '\0';
        rec.numCopy[NUMCOPY_LENGTH] = '\0';
        rec.endMarker[1] = '\0';

		if (fs->write(rec.upc, UPC_LENGTH) && fs->write(rec.title, TITLE_LENGTH) 
			&& fs->write(rec.data, DATA_LENGTH) && fs->write(rec.relDays, RELDAYS_LENGTH) 
			&& fs->write(rec.numCopy, NUMCOPY_LENGTH) && fs->write(rec.endMarker, 1))
			return 1;
		else {
			cerr << "Error in writing hash master file for key: " << key << "\n";
			return 0;
		}
	}

	cerr << "invalid hash key: " << key << "in writing\n";
	return 0;
}


/********************************************************************************
 * Action:                                                                      *
 *		hash all DVD records from a sequential master file into a hash  
 *		table file, and put the DVD title/hash-key into a B+ tree
 * Arguments:                                                                   *
 *		bt	- the B+ tree object
 *		masterf	- the original sequential master file
 * Returns:                                                                     *
 *		
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
void Hash::hashMaster(BTree &bt, char *masterf)
{
	// create the objects needed.
	fstream mf;
	Rec recM;
   
	mf.open(masterf, ios::in);
	if (!mf.is_open()) {
		cerr << "Error in opening master file\n";
		exit(1);
	}

	mf.seekg(0, ios::end);
	int numRecords = static_cast<int> (mf.tellg() / (MRECORD_LENGTH + 1));
	mf.seekg(0, ios::beg);
 
	// write masterfile to hashed newmaster and add title-key to B tree
	while (mf.read(recM.upc, UPC_LENGTH) && mf.read(recM.title, TITLE_LENGTH) && 
		mf.read(recM.data, DATA_LENGTH)  && mf.read(recM.relDays, RELDAYS_LENGTH) 
		&& mf.read(recM.numCopy, NUMCOPY_LENGTH) && mf.read(recM.endMarker, 1))
	{
		recM.upc[UPC_LENGTH] = '\0';
		recM.title[TITLE_LENGTH] = '\0';
		recM.data[DATA_LENGTH] = '\0';
		recM.relDays[RELDAYS_LENGTH] = '\0';
		recM.numCopy[NUMCOPY_LENGTH] = '\0';

		int key = getKey(recM.upc);
		key = searchForInsert(recM.upc, key);

		if (key > 0 && key < size) {
		// write to the newmaster and B tree
			writeRec(recM, key);
			char key_c[4];
			sprintf(key_c, "%d", key);
			key_c[3] = 0;
			TitleKey tk(recM.title, key_c);
			bt.add(tk);
		}

		else if (key == size) 	// newmaster is full
   			cout << "The newmaster file is full. No more insertion!" << endl;
	}
	mf.close();
}


/********************************************************************************
 * Action:                                                                      *
 *		convert number of days from 1900 into date
 * Arguments:                                                                   *
 *		days	- number of days (from 1900 to the release day)
 *		y		- year to be returned
 *		m		- month to be returned
 *		d		- date to be returned
 * Returns:                                                                     *
 *		the date when the DVD is released
 * Pre:                                                                         *
 *		0 < days < 62093
 * Post:                                                                        *
 *		
 ********************************************************************************/
void Hash::convertToDate(int days, int *y, int *m, int *d)
{
    int year=1900;
    int inc, daycnt=0;
    int dayInYear;
    int *daysToMonth;
    int i;

    // Find year that corresponds to days.
    while(year < 2170)
    {
        // generic leap year test 
        if (year % 400 == 0)
            inc = 366; // leap year 
        else if (year % 100 == 0)
            inc = 365; // not leap year 
        else if (year % 4 == 0)
            inc = 366; // leap year 
        else
            inc = 365; // not leap year 

        // If we added this year's days would we go over? 
        if (daycnt + inc > days)
        {
            *y = year;
            dayInYear = days - daycnt;
            break;
        }
        daycnt += inc;
        year++;
    }

    // Figure out month and day from dayInYear. 
    // First choose correct array based on leap year or not 
    daysToMonth = (inc==366)? daysToMonthLeapYear : daysToMonthNormalYear;

    for (i=0; i<12; ++i)
    {
        if (daysToMonth[i+1] > dayInYear)
        {
            *m = i;
            *d = dayInYear - daysToMonth[i] + 1;
            // + 1 since day of month starts at one. 
            break;
        }
    }
}



/********************************************************************************
 * Action:                                                                      *
 *		display the contens of record at slot 'key'
 * Arguments:                                                                   *
 *		key - the slot where the record is displayed
 *		
 ********************************************************************************/
void Hash::print(int key) {
	Rec rec;
	readRec(rec, key);

	cout << "key: " << key << ", contents: \n" << rec.toString() << endl;
}


/********************************************************************************
 * Action:                                                                      *
 *		display all valid records in the hash table
 * Arguments:                                                                   *
 *		
 * Algorithm:                                                                   *
 *		start from slot 0 with incrrement of 1, if slot i is a valid 
 *		record, call print(i) to display it
 ********************************************************************************/
void Hash::print() {
	Rec rec;
	for (int i = 0; i < size; i++) {
		readRec(rec, i);
		if (strcmp(rec.upc, EMPTY) || strcmp(rec.upc, DELETION))
			print(i);
	}
}


/********************************************************************************
 * Action:                                                                      *
 *		get a string representation of a record
 * Arguments:                                                                   *
 *		
 * Returns:                                                                     *
 *		a string representation of a record
 *
 ********************************************************************************/
string Rec::toString() { 
	upc[UPC_LENGTH] = '\0';
	data[DATA_LENGTH] = '\0';
	relDays[RELDAYS_LENGTH] = '\0';
	numCopy[NUMCOPY_LENGTH] = '\0';
	string s(upc), s1(title), s2(data), s3(relDays), s4(numCopy);
	s += s1 + s2 + s3 + s4 + "\n";
	return s; 
}


/******************************************************************************************************/




// titltKey.h

#ifndef _TITLEKEY_H_
#define  _TITLEKEY_H_

#include <string>
using namespace std;

#define		TITLE_LENGTH		30	// length of DVD title
#define		KEY_LENGTH		3	// length of hash key

/* 
 * maintain a DVD title/hash-key pair. key stands for the hash key. 
 */
class TitleKey {

	char title[TITLE_LENGTH + 1];	// the DVD title

	char key[KEY_LENGTH + 1];		// the hash key

public:	

	TitleKey(const char *tl = "", const char *k = "");	// constructor

	int compareTitle(TitleKey &other);			// compare based on title alone

	int compareTitle(char *tl);			// compare two titles directly

	int compareKey(char *k);				// compare based on keys

	int compareKey(TitleKey &other);			// compare based on keys

	int compareTitleKey(TitleKey &other);		// compare based on titles, then key

	void setTitle(const char *tl);			// set the title
	char const * getTitle() { return title; }		// get the title

	void setKey(const char * k);			// set the key
	char const * getKey() { return key; }		// get the key

	// return a string representation of this title-key
	string toString();	

};

#endif
// titleKey.cpp


#include "TitleKey.h"

/* 
 * Implementation of class TitleKey.
 */

// construct a TitleKey object
TitleKey::TitleKey(const char *tl, const char *k) {
	setTitle(tl);
	setKey(k);
}

// compare based on titles directly
int TitleKey::compareTitle(char *tl) { return (strcmp(tl, title)); }

// compare two TitleKey objects based on title 
int TitleKey::compareTitle(TitleKey &other) {
	return (strcmp(title, other.getTitle()));
}

// compare based on hash keys
int TitleKey::compareKey(char *k) { return (strcmp(key, k)); }

// compare two TitleKey objects based on keys
int TitleKey::compareKey(TitleKey &other) { return (strcmp(key, other.getKey())); }

// compare two TiTleKey objects based on titles first, then hash keys
int TitleKey::compareTitleKey(TitleKey &other) {
	int v = compareTitle(other);
	if (v == 0)
		compareKey(other);
	return v;
}

// set title to the value of tl
void TitleKey::setTitle(const char *tl) {
	strncpy(title, tl, TITLE_LENGTH);
	title[TITLE_LENGTH] = 0;
}

// set the key to be the value of k
void TitleKey::setKey(const char * k) {
	strncpy(key, k, KEY_LENGTH);
	key[KEY_LENGTH] = 0;
}

// return a string representation of this title-key
string TitleKey::toString()	{
	string s(title), s1(key);
	s += " " + s1;
	return (s);
}


/******************************************************************************************************/


// BTreeNode.h


#ifndef _BTREENODE_H_
#define  _BTREENODE_H_

#include <string>
#include <iostream>
#include <fstream>
#include "TitleKey.h"
using namespace std;

#define	ORDER	5			// order of the node.

/* 
 * this is the in memory version of a B-tree node, it maintains a B+ tree node in order "ORDER".	
 */
class BTreeNode {

	// The level that this node appears on disk. Level 0 is leaf level.
	int level;

	int count;				// number of keys in this node.

	int preLeaf;				// line number of previous leaf

	int nextLeaf;				// line number of next node.

	int nextLevel[ORDER];			// pointers to my children

	TitleKey titleKey[ORDER - 1];		// title-key pair

public:

	// construct a new node at specific level.
	BTreeNode(int level, int lessOrEq, TitleKey &tk, int greater, int preL, int nextL);

	// create a new empty node in a specific level.
	BTreeNode(int l = 0);

	// adda a title/key pair to a leaf node if there is a space, otherwise 
	// split self and return the promoted key as well as the new node.
	void * add(TitleKey & tk, int lessOrEq);

	int find(TitleKey & tk);			// return index where tk shuld appear in this node.

	int findTitle(char * tl);			// return the index of given title in BTeeNode.

	int deleteTitleKey(TitleKey & tk);		// delete a title/key pair

	int getChild(int i, int &child);		// set child to the value of child[i].

	int getTitleKey(int i, TitleKey & tk);	// set tk to the value of i'th titleKey.

	int getCount() {return count;}		// return the count.

	int getLevel() {return level;}		// return the level

	void setLevel(int l) { level = l; }	// set the level of this node

	int getPrevLeaf() { return preLeaf; }	// return the pointer to previous leaf

	int getNextLeaf() { return nextLeaf; }	// return the pointer to next leaf

	void setPreLeaf(int ptr) { preLeaf = ptr; }// set the previous leaf pointer

	void setNextLeaf(int ptr) {nextLeaf = ptr; }// set the next leaf pointer

	string toString();			// return a string representation of this node.
};


/* 
 * A splitted node object: the object returned by a call to the BTreeNode::add routine in 
 * case the add causes a split. Keep the key to promote as well as the newly created node. 
 */
class SplitedNode {
public:
	TitleKey promotedTK;
	BTreeNode newNode;

	string toString();
};

#endif


/******************************************************************************************************/


// BTreeNode.cpp


#include "BTreeNode.h"


/********************************************************************************
 * Action:                                                                      *
 *		create a new ROOT on the level specified.
 * Arguments:                                                                   *
 *		l		- the level of the root
 *		lessOrEq		- pointer to left child
 *		greater		- pointer to the right child
 *		tk		- title-key pair
 * Returns:                                                                     *
 *		a (root) instance of a BTreeNode
 * Pre:                                                                         *
 *		
 * Post:                                                                        *
 ********************************************************************************/
BTreeNode::BTreeNode(int l, int lessOrEq, TitleKey &tk, int greater, int preL, int nextL) {
	level = l;	// l is 'char' level
	count = 1;	// 1 is 'int' one
	preLeaf = preL;
	nextLeaf = nextL;
	nextLevel[0] = lessOrEq;
	nextLevel[1] = greater;
	titleKey[0] = tk;
}

// construct a new node at the level specified
BTreeNode::BTreeNode(int l) {
	level = l;
	count = 0;
	preLeaf = -1;
	nextLeaf = -1;
	for (int i = 0; i < ORDER; i++)
		nextLevel[i] = 0;
}


/********************************************************************************
 * Action:                                                                      *
 *	add a title/key pair to a leaf node if there is a space, otherwise 
 *	split self and return the promoted key as well as the new node.
 * Arguments:                                                                   *
 *	tk	- the title-key pair to be added
 *	lessOrEq	- pointer to its left child
 * Returns:                                                                     *
 *	a new SplitedNode object if the adding ends up splitting, 
 *	null otherwise
 * Pre:                                                                         *
 *	the node is not empty
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
void * BTreeNode::add(TitleKey & tk, int lessOrEq) {
	SplitedNode * spNode = 0;
	int pos;				// index to place tk

	// containers for holding the nextLevel and titleKey temporarily,
	int tmpNextL[ORDER+1];	
	TitleKey tmpTK[ORDER];

	pos = find(tk);
	if ((pos < count) && (tk.compareTitleKey(titleKey[pos]) == 0))
		// it is already there
		return 0;
	
	// fill nextLevels and titleKeys into containers
	for (int i = 0; i < pos; i++) {
		tmpNextL[i] = nextLevel[i];
		tmpTK[i] = titleKey[i];
	}
	tmpNextL[pos] = lessOrEq;
	tmpTK[pos] = tk;
	for (int i = pos; i < count; i++) {		
		tmpNextL[i+1] = nextLevel[i];
		tmpTK[i+1] = titleKey[i];
	}
	tmpNextL[count+1] = nextLevel[count];

	if ((count + 1) < ORDER) {
		// simply put the contents back
		count++;
		for (int i = 0; i < count; i++) {
			nextLevel[i] = tmpNextL[i];
			titleKey[i] = tmpTK[i];
		}
		nextLevel[count] = tmpNextL[count];
	}
	else {
		// overflow, split this node into two nodes
		spNode = new SplitedNode();
		spNode->newNode.level = level;

		int mid = (ORDER - 1) / 2;
		int src, dest;

		for (src = 0; src <= mid; src++) {
			nextLevel[src] = tmpNextL[src];
			titleKey[src] = tmpTK[src];
		}
		for (src = (mid + 1), dest = 0; src < ORDER; src++, dest++) {
			spNode->newNode.nextLevel[dest] = tmpNextL[src];
			spNode->newNode.titleKey[dest] = tmpTK[src];
		}
		spNode->newNode.nextLevel[dest] = tmpNextL[src];

		spNode->newNode.count = ORDER - (mid + 1);

		if (level == 0)
			count = mid + 1;
		else
			count = mid;

		spNode->promotedTK = titleKey[mid];
	}
	return spNode;
}

/********************************************************************************
 * Action:                                                                      *
 *		find the index where tk shuld appear in this node
 * Arguments:                                                                   *
 *		tk - the title-key to be found
 * Returns:                                                                     *
 *		index i s.t. titleKey[i-1] < tk <= titleKey[i+1]
 * Pre:                                                                         *
 *		node is not empty
 ********************************************************************************/
int BTreeNode::find(TitleKey & tk) {
	int pos;
	for (pos = 0; pos < count; pos++) {
		if (tk.compareTitleKey(titleKey[pos]) <= 0)
			break;
	}
	return pos;
}


/********************************************************************************
 * Action:                                                                      *
 *		find the index of given title in BTeeNode
 * Arguments:                                                                   *
 *		tl - title to be found in this node
 * Returns:                                                                     *
 *		index i s.t. title[i-1] < tk <= title[i+1]
 * Pre:                                                                         *
 *		node is not empty                                                                              *
 ********************************************************************************/
int BTreeNode::findTitle(char * tl) {
	int pos;
	for (pos = 0; pos < count; pos++) {
		if (titleKey[pos].compareTitle(tl) <= 0)
			break;
	}
	return pos;
}


/********************************************************************************
 * Action:                                                                      *
 *	set child to the value of i'th pointer which points to its i'th child
 * Arguments:                                                                   *
 *	i	- index of the pointer to be assigned
 *	child	- the pointer to be set
 * Returns:                                                                     *
 *	1 for successful assignment, 0 otherwise
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
int BTreeNode::getChild(int i, int &child) {
	if (i <= count) {
		child = nextLevel[i];
		return 1;
	}
	else 
		return 0;
}


/********************************************************************************
 * Action:                                                                      *
 *		set tk to the value of i'th titleKey.
 * Arguments:                                                                   *
 *		i	- index of the titleKey to be assigned
 *		tk	- the titlekey to be set
 * Returns:                                                                     *
 *		1 for successful assignment, 0 otherwise
 *		
 ********************************************************************************/
int BTreeNode::getTitleKey(int i, TitleKey & tk) {
	if (i < count) {
		tk = titleKey[i];
		return 1;
	}
	else
		return 0;
}


/********************************************************************************
 * Action:                                                                      *
 *		return a string representation of this node.
 * Arguments:                                                                   *
 *		none	
 * Returns:                                                                     *
 *		s string that represents the contents of the node
 ********************************************************************************/
string BTreeNode::toString() {
	char level_c[2], count_c[2], preLeaf_c[4], nextLeaf_c[4], 
		child_c[ORDER][4], nextLevel_c[ORDER][4];
	string str(""), s[14];
	if (sprintf(level_c, "%d", level) && sprintf(count_c, "%d", count) &&
		sprintf(preLeaf_c, "%d", preLeaf) && sprintf(nextLeaf_c, "%d", nextLeaf)) {
		s[0] = level_c;
		s[1] = count_c;
		s[2] = preLeaf_c;
		s[3] = nextLeaf_c;
		str += "Level: " + s[0] + ", Count: " + s[1] 
			+ ", Pre: " + s[2] + ", Next: " + s[3] + "\n";
	}
	else
		cerr << "error in BTreeNode::toString(1)\n";

	for (int i = 0; i < count; i++) {
		if(sprintf(child_c[i], "%d", i) && sprintf(nextLevel_c[i], "%d", nextLevel[i])) {
			s[4+i] = child_c[i];
			s[5+i] = nextLevel[i];
			str += "child " + s[4+i] + ": " + s[5+i] + 
				", T-K: " + titleKey[i].toString() + ", ";
		}
		else
			cerr << "error in BTreeNode::toString(2)\n";
	}

	if(sprintf(child_c[count], "%d", count) && sprintf(nextLevel_c[count], "%d", nextLevel[count])) {
		s[4+2*count] = child_c[count];
		s[5+2*count] = nextLevel[count];
		str += "child " + s[4+2*count] + ": " + s[5+2*count] + "\n";
	}
	else
		cerr << "error in BTreeNode::toString(3)\n";
	return str;
}

// return a string representation of SplitedNode obj
string SplitedNode::toString() {
	string s("");
	s += "Promoted title-key: " + promotedTK.toString();
	s += "new node: " + newNode.toString();
	return s;
}

/********************************************************************************
 * Action:                                                                      *
 *		delete a title/key pair
 * Arguments:                                                                   *
 *		tk - the title-key to be deleted
 * Returns:                                                                     *
 *		1 for successful deletion, 0 otherwise
 * Pre:                                                                         *
 *		
 * Post:                                                                        *
 *		
 * Algorithm:                                                                   *
 *		
 * NOTE:                                                                        *
 *	this deletion algorithm only deletes the T-K if it is there, does not 
 *	take further action for the result of deletion (e.g., merging), even
 *	the node is empty.
 ********************************************************************************/
int BTreeNode::deleteTitleKey(TitleKey & tk) {
	int i, pos;

	pos = find(tk);

	if (tk.compareTitleKey(titleKey[pos]) != 0)
		return 0;
	
	for (i = pos; pos < count; i++) 
		titleKey[i] = titleKey[i+1];

	count--;
	return 1;
}





// BTree.h

#ifndef _BTREE_H_
#define _BTREE_H_

#include <iostream>
#include <fstream>
#include <string>
#include "BTreeNode.h"

/*
 * A secondary storage version of a B+ tree.
 */
class BTree {
	fstream * fs;	// the stream attached to the B+Tree

	int nodeCount;	// # of nodes in an open B+Tree

	// write the node to position nodeNum	
	int writeNode(BTreeNode &btn, int nodeNum);

	// a help method for adding
	int addHelp(TitleKey & tk, int nodeNum, TitleKey & promotedtk, int & promotedLeffOrEq);

	int findLeaf(TitleKey & tk);			// find the node in leaves

	// find the leaf which may contain title 'tk'
	int findLeafForSearch(char *tl);
	
	void close();							// close the B+Tree file

	void printHeader() { cout << "Number of node: " << nodeCount << endl; }
	void print(int i);				// display a specified node
	void print();					// display the whole tree in node num order
	void printLeaves(int subtree);	// display the subtree in title order
	void printLeaves();				// display all leaves in title order
				
public:
	BTree(char *);							// constructor

	void add(TitleKey & tk);				// add to an existing B+Tree			

	int deleteTitleKey(TitleKey & tk);		// delete a keyword/key pair

	void list(TitleKey & tk);				// list all DVDs which contain tk

	// read the node, return 1 if all works well, 0 o.w.
	int readNode(BTreeNode &btn, int nodeNum);
};


/* 
 * create an iterator class. The iterator points to to certain keyword/callNum 
 * in the B+Tree leaves. We have a next keyword pair when getNext called. 
 */
class PIterator {
	BTree *bt;
	BTreeNode btn;
	int positionTitleKey;
	int position;

public:
	PIterator(BTree *bt, BTreeNode btn, int k) {}	// constructor

	int eol() {}				// check end of file

	// return the next keyword/callNum pair
	TitleKey getNext() {return 0;}		 
};


/* 
 * this class has a function serach() which returns an iterator to
 * a given location in the leaf node. 
 */
class SearchKey {

	BTree *bt;

public:
	SearchKey(BTree *btTmp) {}				// constructor
	PIterator *search(char *kw) {return 0;}	// search the title at leaf level
};

#endif

// BTree.cpp

#include "BTree.h"

/*
 * The implementation of class BTree.
 */

/********************************************************************************
 * Action:                                                                      *
 *	construct an instance of a B+ tree
 * Arguments:                                                                   *
 *	fileName - the name of the file which is either empty or contains a 
 *		   valid B+ tree
 * Returns:                                                                     *
 *		an B+ tree object
 * Pre:                                                                         *
 *		the file is either empty or contains a valid B+ tree
 * Post:                                                                        *
 *		fs points to an open B+ tree and nodeCount is set
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
BTree::BTree(char * filename) {
	fs = new fstream(filename, ios::in | ios::out | ios::binary);
	if (!fs->is_open()) {
		cerr << "error in open file\n";
		exit(1);
	}
	fs->seekg(0, ios::end);			
	nodeCount = fs->tellg() / sizeof(BTreeNode);
}


/********************************************************************************
 * Action:                                                                      *
 *		add tk to BTreeNode at nodeNum
 * Arguments:                                                                   *
 *		tk - the titleKey to be added
 *		nodeNum - the root of the subtree to add tk to
 *		promotedTK - the titleKey to be promoted
 *		promotedLessOrEq - the left child pointer if there is a promotion
 * Returns:                                                                     *
 *		1 if a titleKey/pointer pair is promoted, 0 otherwise
 * Pre:                                                                         *
 *		
 * Post:                                                                        *
 *		
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
int BTree::addHelp(TitleKey & tk, int nodeNum, \
			TitleKey & promotedTK, int & promotedLessOrEq) {
	int promote = 0;
	if (nodeNum == -1) {	// -1 is below the bottom of the tree
		promotedTK = tk;
		promotedLessOrEq = -1;
		promote = 1;
	}
	else {
		TitleKey tmpTK;
		int tmpLessOrEq;
		int child;
		BTreeNode btNode;

		readNode(btNode, nodeNum);
		btNode.getChild(btNode.find(tk), child);

		if (addHelp(tk, child, tmpTK, tmpLessOrEq)) {
			SplitedNode * spNode;
			spNode = (SplitedNode *)btNode.add(tmpTK, tmpLessOrEq);

			if(spNode != 0) {	// the node is splited
				if (btNode.getLevel() == 0) {	// btNode is a leaf
					int pre = btNode.getPrevLeaf();
					int next = btNode.getNextLeaf();

					BTreeNode tmpNode;

					if (next >= 0) {
						readNode(tmpNode, next);
						tmpNode.setPreLeaf(nodeNum);
						writeNode(tmpNode, next);
					}

					if (pre >= 0) {
						readNode(tmpNode, pre);
						tmpNode.setNextLeaf(nodeCount);
						writeNode(tmpNode, pre);
					}

					btNode.setNextLeaf(nodeNum);
					(spNode->newNode).setPreLeaf(nodeCount);
					(spNode->newNode).setNextLeaf(next);
				}
				writeNode(spNode->newNode, nodeNum);
				promotedLessOrEq = writeNode(btNode, -1);
				promotedTK = spNode->promotedTK;
				promote = 1;
				delete spNode;
			}
			else	// no split
				writeNode(btNode, nodeNum);
		}
	}
	return promote;
}


/********************************************************************************
 * Action:                                                                      *
 *		add title-key to an open B+Tree
 * Arguments:                                                                   *
 *		tk - the title-key to be added	
 * Returns:                                                                     *
 *		none
 *		
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
void BTree::add(TitleKey & tk) {
	if (nodeCount == 0) {	// Add root to the empty tree
		BTreeNode btNode(0, -1, tk, -1, -1, -1);
		writeNode(btNode, -1);
	}
	else {		// add tk to an existing tree
		TitleKey tmpTK;
		int tmpLessOrEq;
		if (addHelp(tk, 0, tmpTK, tmpLessOrEq)) {
		// root is splitted, need a new root and put the 
		// new root on the first line (line 0)
			BTreeNode btNode;
			int tmpNodeNum, rootLevel, preLeafNum;

			readNode(btNode, 0);

			rootLevel = btNode.getLevel() + 1;
			tmpNodeNum = writeNode(btNode, -1);

			// update the nextLeaf pointer if it is in leaf level
			if (btNode.getLevel() == 0) {
				preLeafNum = btNode.getPrevLeaf();
				readNode(btNode, preLeafNum);
				btNode.setNextLeaf(tmpNodeNum);
				writeNode(btNode, preLeafNum);
			}

			BTreeNode newRoot(rootLevel, tmpLessOrEq, \
				tmpTK, tmpNodeNum, -1, -1);
			writeNode(newRoot, 0);
		}
	}
}		


/********************************************************************************
 * Action:                                                                      *
 *		find the leaf level node for a given title-key pair
 * Arguments:                                                                   *
 *		tk - the titleKey to be matched	
 * Returns:                                                                     *
 *		the logical number of the node which contains tk
 * Pre:                                                                         *		
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
int BTree::findLeaf(TitleKey & tk) {
	BTreeNode btNode;
	int pos, child;

	readNode(btNode, 0);

	while(btNode.getLevel() != 0) {
		pos = btNode.find(tk);
		btNode.getChild(pos, child);
		readNode(btNode, child);
	}

	return child;
}
/********************************************************************************
 * Action:                                                                      *
 *		find the leaf level for a given title
 * Arguments:                                                                   *
 *		tl - the title of the DVD to be matched	
 * Returns:                                                                     *
 *		the logical number of the node which contains tl
 * Pre:                                                                         *		
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
int BTree::findLeafForSearch(char *tl) {
	BTreeNode btNode;
	int pos, child;

	readNode(btNode, 0);

	while(btNode.getLevel() != 0) {
		pos = btNode.findTitle(tl);
		btNode.getChild(pos, child);
		readNode(btNode, child);
	}

	return child;
}


/********************************************************************************
 * Action:                                                                      *
 *		read in the node at location 'nodeNum'
 * Arguments:                                                                   *
 *		btn	- the node to hold the contents of a 'BTreeNode'
 *		nodeNum - the logical node number of the node to be read
 * Returns:                                                                     *
 *		1 for a successful reading, 0 o.w.
 * Pre:                                                                         *
 *		the file is open
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
int BTree::readNode(BTreeNode &btn, int nodeNum) {
	int v = 0;		// the value to be returned
	if (nodeNum < nodeCount) {
		fs->seekg(nodeNum * sizeof(BTreeNode), ios::beg);
		if (fs->read((char*)&btn, sizeof(BTreeNode)))
			v = 1;
		else 
			cerr << "Error in reading file\n";
	}
	return v;
}


/********************************************************************************
 * Action:                                                                      *
 *		write a node into B+ tree file
 * Arguments:                                                                   *
 *		btn	- the node to hold the contents of a 'BTreeNode'
 *		nodeNum - the logical node number of the node to be written
 * Returns:                                                                     *
 *		1 for a successful writing, 0 o.w.
 * Pre:                                                                         *
 *		the file is open
 * Algorithm:                                                                   *
 *		write a new node to the end of the file, or to the position 
 *		specified by nodeNum otherwise
 ********************************************************************************/
int BTree::writeNode(BTreeNode &btn, int nodeNum) {
	int nodeN;
	if (nodeNum == -1) {		// a new node
		long bytes;
		fs->seekg(0, ios::end);
		bytes = fs->tellg();
		nodeN = (bytes + 1) / sizeof(BTreeNode);
		nodeCount++;
	}
	else {
		nodeN = nodeNum;
		fs->seekg(nodeNum * sizeof(BTreeNode), ios::beg);
	}
	if (!fs->write((char*)&btn, sizeof(BTreeNode)))
		cerr << "Error in writing file\n";

	return nodeN;
}


// close the B+Tree file
void BTree::close() { fs->close(); }

/********************************************************************************
 * Action:                                                                      *
 *		display a specified node at (logical) line number i
 * Arguments:                                                                   *
 *		i - the logical line number of the node to be displayed
 ********************************************************************************/
void BTree::print(int i) {
	BTreeNode n;
	if (readNode(n, i) ) 
		cout << "Node at line " << i << ": " << n.toString();
	else
		cerr << "can't read node " << i << endl;
}

	
/********************************************************************************
 * Action:                                                                      *
 *		display the whole tree in node number order
 * Pre:                                                                         *
 *		an open, valid B+ file
 ********************************************************************************/		
void BTree::print() {
	printHeader();
	BTreeNode node;
	for (int i = 0; i < nodeCount; i++) {
		if (readNode(node, i) ) 
			cout << node.toString();
		else
			cerr << "Error in read node " << i << endl;
	}
}


// display the subtree in title order					
void BTree::printLeaves(int subtree){}


/********************************************************************************
 * Action:                                                                      *
 *		display all leaves in title order
 * Pre:                                                                         *
 *		an open, valid B+ file
 ********************************************************************************/
void BTree::printLeaves(){
	int line = findLeafForSearch("0");
	BTreeNode node;

	do {
		if (readNode(node, line))
			cout << node.toString();
		else
			cerr << "error in read next node at " << node.getNextLeaf() << endl;
		line = node.getNextLeaf();
	} while (line > 0);
}	


/********************************************************************************
 * Action:                                                                      *
 *		delete a title/key pair
 * Arguments:                                                                   *
 *		tk - the title-key of the DVD to be deleted	
 * Returns:                                                                     *
 *		1 if the title-key is deleted, 0 otherwise
 * Algorithm:                                                                   *
 * NOTE:                                                                        *
 *	this deletion algorithm only deletes the tk if it is there, and does 
 *	not take any further action for the result of deletion: merging and 
 *	updating of this lelel and its parent's levels, even the node is empty 
 *	after the deletion		
 ********************************************************************************/
int BTree::deleteTitleKey(TitleKey & tk) {
	BTreeNode node;

	if (int leaf = findLeaf(tk)) {
		if (readNode(node, leaf) && node.deleteTitleKey(tk)) 
			return (writeNode(node, leaf));
		cerr << "Error in read or delete: " << tk.toString() << endl;
	}
	else 
		cerr << tk.toString() << " is not in the tree\n";
	return 0;
}


/********************************************************************************
 * Action:                                                                      *
 *		display all DVDs which contain tk
 * Arguments:                                                                   *
 *		tk		- the title-key of the DVD to be listed
 * Pre:                                                                         *
 *		the file is open
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
void BTree::list(TitleKey & tk) {
	int line = findLeaf(tk);
	BTreeNode node;

	while (line >= 0) {
		readNode(node, line);
		TitleKey tmp;
		for (int i = 0; i < node.getCount(); i++) {
			node.getTitleKey(i, tmp);
			if (tk.compareTitleKey(tmp))
				cout << tmp.toString();
			else
				break;
		}
		line = node.getNextLeaf();
	} 
}



////////////////////////////////////////////////////////////////////////////////////

// testBTreeHash.cpp

/*
 * process the request from the transaction file 
 */

#include <iostream>
#include <fstream>

#include "Hash.h"
#include "BTree.h"

enum {insertion = 1, deletion = 2, changeInfo = 3, listInfo = 4, ship = 5, listTitle = 6};


/********************************************************************************
 * Action:                                                                      *
 *	process the transaction file and update the new (hashed) master 
 *	file and the B+ tree file, exception case will go to the errorfile
 * Arguments:                                                                   *
 *	hash	- the hash table
 *	bt	- the B+ tree object
 *	transf	- the transaction file
 *	errorf	- the error log
 * Pre:                                                                         *
 *	hash and bt are open and valid hash and B+ tree files	
 * Algorithm:                                                                   *
 *		
 ********************************************************************************/
void processTrans(Hash hash, BTree bt, char *transf, char *errorf)
{   
   // create the objects needed.
   fstream tf, erf;
   Rec recM, recT;
   
   tf.open(transf, ios::in);
   erf.open(errorf, ios::out);
   if (!erf.is_open() || !tf.is_open()) {
		cerr << "Error in opening files(2)\n";
		exit(1);
	}

   tf.seekg(0, ios::end);
   int numRecords = static_cast<int> (tf.tellg() / (MRECORD_LENGTH + 1));
   tf.seekg(0, ios::beg);
   
   // read the records of transaction file one by one and process it according to the operation type
   while (tf.read(recT.upc, UPC_LENGTH) && tf.read(recT.title, TITLE_LENGTH) && 
	   tf.read(recT.data, DATA_LENGTH) && tf.read(recT.relDays, RELDAYS_LENGTH) 
	   && tf.read(recT.numCopy, NUMCOPY_LENGTH) && tf.read(recT.opType, OPTYPE_LENGTH) 
	   && tf.read(recT.opParam, NUMCOPY_LENGTH) && tf.read(recT.endMarker, 1))
   {
   	recT.upc[UPC_LENGTH] = '\0';
	recT.title[TITLE_LENGTH] = '\0';
   	recT.data[DATA_LENGTH] = '\0';
   	recT.relDays[RELDAYS_LENGTH] = '\0';
   	recT.numCopy[NUMCOPY_LENGTH] = '\0';
   	recT.opType[OPTYPE_LENGTH] = '\0';
   	recT.opParam[NUMCOPY_LENGTH] = '\0';
   	recT.endMarker[1] = '\0';

   	int key = hash.getKey(recT.upc);
   	int type = atoi(recT.opType);

   	hash.readRec(recM, key);

	if (type > insertion && type <= listTitle)
   	{
		key = hash.searchForChange(recT.upc, key);
			if (key >= 0 && key < hash.getSize()) {
				char key_c[4];
				sprintf(key_c, "%d", key);
				key_c[3] = 0;
				TitleKey tk(recM.title, key_c);
            	switch(type)
            	{             
				case deletion:
					hash.deleteRec(recM, key);
					bt.deleteTitleKey(tk);	// bTree.delete is not complete
   					break;
	      
				case changeInfo:
					hash.writeRec(recT, key);
					bt.deleteTitleKey(tk);	// bTree.delete is not complete
					bt.add(tk);
					break;

				case listInfo:
					int y, m, d;
					hash.convertToDate(atoi(recM.relDays), &y, &m, &d);
					sprintf(recM.relDate, "%2d%c%2d%c%4d", m, '/', d, '/', y);
					erf << "information of item " << recM.upc << ":\n" << 
                           recM.toString() << "**" << recM.relDate << 
						   "**" << recM.numCopy << "\n\n";
					break;

				case ship:						// ship DVDs.
					int newNumC;
						newNumC = atoi(recM.numCopy) - atoi(recT.numCopy);
					if(newNumC < 0)
					{// tell to purchase more copies.
   		   				sprintf(recM.numCopy, "%06d", 0);
   		   				erf << "Location " << recT.opParam << " need " << -newNumC << 
   		   					" more copies for item " << recT.upc << "\n\n";
					} else
   						sprintf(recM.numCopy, "%06d", newNumC);
                	
                	hash.writeRec(recM, key);
					break;

				case listTitle:
					bt.list(tk);
					break;
				}
			}
	  
		else // the record is not in masterfile.
   	 		erf << "Item " << recT.upc << " is not in masterfile\n\n";
}
	
	else if (type == insertion) 	// insertion.
	{
   		key = hash.searchForInsert(recT.upc, key);
	   
		if (key >= 0 && key < hash.getSize()) {
			hash.writeRec(recT, key);
			char key_c[4];
			sprintf(key_c, "%d", key);
			key_c[3] = 0;
			TitleKey tk(recM.title, key_c);
			bt.add(tk);
		}
			
		else if (key == -1)
      			erf << "Item " << recT.upc << "is already in the newmasterfile. Insertion failed!\n\n";

   		else // newmaster is full	   
      			erf << "The newmaster file is full. No more insertion!" << endl;
	}

	else	// Wrong operation type.
   		erf << "Wrong operation type for item " << recT.upc << "\n\n";
    }
    tf.close();
    erf.close();
}


// test driver, you may add more functions for testing purposes
int main ()
{   
	// create the hash and B tree objects
	Hash hash("newM.txt");

	BTree bTree("b_tree.txt");
    
	// process the original master file
	hash.hashMaster(bTree, "masterfile.txt");
     
	// get the transfiles to be processed.      
  	processTrans(hash, bTree, "trans.txt", "erFile.txt"); 

	return 0; 
}

// use this only when input file names from command line
/*
int main (int argc, char *argv[])
{   
	// ensure to get correct number of arguments.   
	if(argc != 6) {

		cerr << " Usage: BTree masterfile transfile newmaster btidx errorfile" << endl;
		return 1;   
	}
   
	// get the files to be processed.    
	Hash hash(argv[3]);
	BTree bTree(argv[4]);

	// create the hashed master file and the BTree index file.        
	hash.hashMaster(bTree, argv[3]);
     
	// get the transfiles to be processed.      
	processTrans(hash, argv[2], argv[5]); 

	return 0; 
}*/