// KeyedCollection2.h
// template class KeyedCollection - Binary Search

#include <iostream>
#include <vector>
#include <string>
#include "customer.h"
using namespace std;

// TEMPLATE CLASS DECLARATION SECTION =======================

template <class TYPE, class KTYPE, int MAXELEMENTS=1000>
class KeyedCollection {
	private:
		vector<TYPE> CustList;
		KTYPE key;
		int maxElements;
		int numElements;
		int comparisons;
	public:
		
		 // Constructors
		KeyedCollection();
		void insert(KTYPE key, TYPE object);
		 // inserts a new object, with key value 'key', into the collection
		bool find(KTYPE key, TYPE &object);
		 // attempts to find an object with key value 'key' in the collection
		 // if not found, returns false.  if found, stores found object in reference
		 // parameter 'object' and returns true
		int getNumComparisons();
		 // returns the number of comparisons used in the last 'insert' or 'find' operation
		bool empty();
		 // returns true if collection is empty, false otherwise
};


// TEMPLATE CLASS IMPLEMENTATION SECTION =======================

template <class TYPE, class KTYPE, int MAXELEMENTS>
KeyedCollection<TYPE, KTYPE, MAXELEMENTS>::KeyedCollection()
{
	key = 0;
	numElements = 0;
	comparisons = 0;
}

template <class TYPE, class KTYPE, int MAXELEMENTS>
void KeyedCollection<TYPE, KTYPE, MAXELEMENTS>::insert(KTYPE k, TYPE o)
{
	CustList.push_back(o);
	
	for (int i = 0; i < CustList.size(); i++)
	{
		int champ = CustList[i].GetCustID();
		int place = i;
		for (int j = i + 1; j < CustList.size(); j++)
		{
			if (CustList[j].GetCustID() < champ)
			{
				champ = CustList[j].GetCustID();
				place = j;
			}
		}
		
		int temp = CustList[i].GetCustID();
		CustList[place].SetCustID(temp);
		CustList[i].SetCustID(champ);
	}
	return;
}

template <class TYPE, class KTYPE, int MAXELEMENTS>
bool KeyedCollection<TYPE, KTYPE, MAXELEMENTS>::find(KTYPE k, TYPE & o)
{
	comparisons = 0;
	int low = 0;
	int high = CustList.size() - 1;

	while (low <= high)
	{
		comparisons++;
		int mid = ((low + high) / 2);

		if (CustList[mid].GetCustID() == k)
		{
			return true;  // a match at subscript mid
			o = CustList[mid];
		}
		else if (CustList[mid].GetCustID() < key)
		{
			low = mid + 1;
		}
		else   // (key < mid)
		{
			high = mid - 1;
		}
	}
	return false;
	
}

template <class TYPE, class KTYPE, int MAXELEMENTS>
int KeyedCollection<TYPE, KTYPE, MAXELEMENTS>::getNumComparisons()
{
	return comparisons;
}

template <class TYPE, class KTYPE, int MAXELEMENTS>
bool KeyedCollection<TYPE, KTYPE, MAXELEMENTS>::empty()
{
	if (CustList.empty())
		return true;
	else
		return false;
}