///////////////////////////////////////////////////////////////////////
//vecEx1.cpp
#include <iostream>
#include <vector>

using std::cout; using std::endl; using std::vector;

void printSize(int size, int cap){
  cout << "The size is " << size << 
    " and the capacity is " << cap << endl;
}

int main(){
  vector<int> v(1);
  v[0] = 12;
  printSize(v.size(), v.capacity());
  v.push_back(1);
  printSize(v.size(), v.capacity());
  v.push_back(2);
  printSize(v.size(), v.capacity());
  for(int i = 0; i < v.size(); i++)
    cout << "v[" << i << "] = " << v[i] << " ";
  cout << endl;
  
  v.pop_back();
  vector<int>::iterator iter = v.insert(v.begin() + 1, 17);
  cout << "Dereferenced iterator = " << *iter << endl;
  for(iter = v.begin(); iter != v.end(); iter++)
    cout << *iter << " ";
  cout << endl;
  v.clear();
  printSize(v.size(), v.capacity());

  return 0;
}
///////////////////////////////////////////////////////////////////////
//vecEx2.cpp
#include <iostream>
#include <vector>

using std::cout; using std::endl; using std::vector;

int main(){
  int nrows = 3, ncols = 2;
  vector<vector<int> > v;
  v.resize(nrows);
  for(int i = 0; i < nrows; i++){
    v[i].resize(ncols);
    for(int j = 0; j < ncols; j++)
      v[i][j] = (i + 1)*(j + 1);
  }

  for(int i = 0; i < v.size(); i++){
    for(int j = 0; j < v[i].size(); j++)
      cout << "v[" << i << "][" << j << "] = "
           << v[i][j] << " ";
    cout << endl;
  }

  return 0;
}
///////////////////////////////////////////////////////////////////////
//vecEx3.cpp
#include <iostream>
#include <vector>
#include <string>

using std::cout; using std::endl; using std::vector;
using std::string;

void printVec(vector<vector <int > > v, string s);

int main(){
  vector<vector<int> > v, v1;
  int nrows = 3, ncols = 2;
  v.resize(nrows);
  for(int i = 0; i < nrows; i++){
    v[i].resize(ncols);
    for(int j = 0; j < ncols; j++)
      v[i][j] = (i + 1)*(j + 1);
  }

  v1.assign(v.begin() + 2, v.end());
  printVec(v1, "v1");
  vector<vector<int> > v2(v);
  printVec(v2, "v2");

  return 0;
}

void printVec(vector< vector<int> > v, string s){
  cout << "The number of rows in " << s <<  " is " 
       << v.size() << endl;
  for(int i = 0; i < v.size(); i++){
    cout<< "The length of row " << i << " is " << v[i].size()
        << endl;
    for(int j = 0; j < v[i].size(); j++)
      cout << s + "[" << i << "][" << j << "] = "
           << v[i][j] << " ";
    cout << endl;
  }
}
///////////////////////////////////////////////////////////////////////
//cmSketch.cpp
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <limits>
#include <string>
#include "ranGen.h"

using std::cin; using std::ifstream; using std::cout;
using std::endl; using std::string; using std::vector;
using std::numeric_limits;

class CMS
{
  int W;
  int D;
  unsigned long Seed;
  vector<vector<int> > B;
  vector<int> a;
  vector<int> b;
  
  void insertKey(string key);
  int fnvHash(int i, string key);

public:

  CMS(int w, int d, unsigned long seed);
  ~CMS() {};
  void readData(ifstream& inFile);

  unsigned long getFreqEst(string key);
};

int CMS::fnvHash(int i, string key){
  unsigned long int h = 2166136261UL;
  for (unsigned int j = 0; j < key.length(); j++ )
    h = (h*16777619)^key[j];
  
  return (a[i]*h + b[i]) % W;
}

CMS::CMS(int w, int d, unsigned long seed): W(w), D(d), Seed(seed){
  a = vector<int> (D);
  b = vector<int> (D);
  B = vector<vector<int> >(W, vector<int>(D, 0));
  double* aAndb = new double[2*D];
  ranGen rng;
  rng.setSeed(Seed); rng.ranUnif(2*D, aAndb);
  for(int i = 0; i < D; i++) {
	a[i] = floor(W*aAndb[2*i]);
	b[i] = floor(W*aAndb[2*i + 1]);
  }
  delete [] aAndb;
}

void CMS::insertKey(string key){
  for(int i = 0; i < D; i++) 
    B[i][fnvHash(i, key)]++;
}

void CMS::readData(ifstream& inFile){
  string key; int theCount= 0, totalCount = 0; 
  while(!inFile.eof()) {
    getline(inFile, key);
    if(key == "the") theCount++;
    insertKey(key);
    totalCount++;
    if(!(totalCount%100000))
       cout << theCount << " " << getFreqEst("the") << endl;
  }
}

unsigned long CMS::getFreqEst(string key){
  unsigned long minSoFar = numeric_limits<unsigned long>::max();
  unsigned long thisCount = 0;
  for(int i = 0; i < D; i++) {
    thisCount = B[i][fnvHash(i, key)];
    if(thisCount < minSoFar) minSoFar = thisCount;
  }
  return minSoFar;
}  

int main(){
  unsigned long seed = 123;
  int w = 307;
  int d = 29;
  CMS A(w, d, seed);
  ifstream words("newWords.txt");
  A.readData(words);
  words.close();
  string key;
  while(1) {
	cout << "The word of interest? ";
	getline(cin, key);
	if(key.length() == 0) break;
	cout << "Estimated frequency is " << A.getFreqEst(key) 
	     << endl;
  }
  return 0;
}
///////////////////////////////////////////////////////////////////////
// fileIn.h
#ifndef FILEIN_H
#define FILEIN_H

#include <vector>
#include <string>

class fileIn{
  std::vector<std::vector<double> > v;
  void tokenizer(const std::string& str, 
	std::vector<std::string>& tokens);
  
public:
  
  fileIn(const char* fname);
  ~fileIn(){};
  int getVNRows(){return v.size();}
  int getVLength(int i){return v[i].size();}
  double getV(int i, int j){return v[i][j];}
};
#endif

//fileIn.cpp
#include "fileIn.h"
#include <fstream>
#include <iostream>

using std::string; using std::vector; using std::cout;
using std::endl; using std::ifstream;

fileIn::fileIn(const char* fname){
  vector<string> words;
  string line;

  ifstream in(fname);
    
  if(in.is_open()){
    while(!in.eof()){
      getline(in, line);
      if(line.length() != 0){
	tokenizer(line, words);
	if(words.size() != 0){
	  v.push_back(vector<double>());
	  for(int i = 0;i < words.size(); i++)
	    v[v.size() - 1].push_back(atof(words[i].c_str()));
	}
	words.clear();
      }
    }
  }
  else {
    cout<< "Unable to open file" << endl; 
    exit(1);
  }
}

void fileIn::tokenizer(const string& str, vector<string>& tokens){  
  string delimiters=" ";
  // Skip delimiters at beginning
  string::size_type lastPos = str.find_first_not_of(delimiters, 0);
  // Find first non-delimiter
  string::size_type pos = str.find_first_of(delimiters, lastPos);
 
  // Loop while there are tokens to be found: i.e., one of the 
  // searches for a delimiter (pos) or nondelimiter (lastPos) 
  // does not fail. 

  while(string::npos != pos || string::npos != lastPos){
    // Found a token, add it to the vector
    tokens.push_back(str.substr(lastPos, pos - lastPos));
    // Skip next set of delimiters and go to next token
    lastPos = str.find_first_not_of(delimiters, pos);
    // Find end of token or start of next delimiter
    pos = str.find_first_of(delimiters, lastPos);
  }
}
///////////////////////////////////////////////////////////////////////
//g5.h
#ifndef G5_H
#define G5_H
#include <string>
#include <vector>

class g5{
  std::string Date, Machine;
  int SetNo;
  std::string Day;
  short** pData;
  int* pFreq;
  void getFreq();

 public:  
  g5() : pData(0), pFreq(0) {}
  g5(std::string Date, std::string machine, int setNo, 
	std::string day, short** pdata);
  g5(const g5& g5Obj);
  ~g5();
 
  g5& operator=(const g5& g5Obj);
  bool operator==(const g5& g5Obj) const;

  int getFreq(int i) const {
    return pFreq[i];
  }
  std::string getDate() const {
    return Date;
  }
  void printG5() const;
};

g5::g5(std::string date, std::string machine, int setNo, 
	std::string day, short** pdata) : Date(date), 
	Machine(machine), SetNo(setNo), Day(day) {
  pFreq = new int[40];
  for(int i = 0; i < 40; i++)
    pFreq[i] = 0;

  pData = new short*[10];
  for(int i = 0; i < 10; i++){
    pData[i] = new short[5];
    for(int j = 0; j < 5; j++)
      pData[i][j] = pdata[i][j];
  }
  getFreq();
}

g5::g5(const g5& g5Obj) : Date(g5Obj.Date), Machine(g5Obj.Machine), 
    SetNo(g5Obj.SetNo), Day(g5Obj.Day) {

  if(g5Obj.pData !=0){
    pData = new short*[10];
    for(int i = 0; i < 10; i++){
      pData[i] = new short[5];
      for(int j = 0; j < 5; j++)
	pData[i][j] = g5Obj.pData[i][j];
    }
  }
    else pData = 0;

  if(g5Obj.pFreq != 0){
      pFreq = new int[40];
      for(int i = 0; i < 40; i++)
	pFreq[i] = g5Obj.pFreq[i];
    }
    else pFreq = 0;
}

g5& g5::operator=(const g5& g5Obj){

  this->Date = g5Obj.Date; this->Machine = g5Obj.Machine; 
  this->SetNo = g5Obj.SetNo; this->Day = g5Obj.Day;
  this->pData = new short*[10];
  for(int i = 0; i < 10; i++){
    this->pData[i] = new short[5];
    for(int j = 0; j < 5; j++)
      this->pData[i][j] = g5Obj.pData[i][j];
  }
  this->pFreq = new int[40];
  for(int i = 0; i < 40; i++)
    this->pFreq[i] = g5Obj.pFreq[i];

  return *this;
}

bool g5::operator==(const g5& g5Obj) const {

  if( this->Date == g5Obj.Date && this->Machine == g5Obj.Machine && 
      this->SetNo == g5Obj.SetNo && this->Day == g5Obj.Day &&
      this->pData == g5Obj.pData)
    return true;
  return false;
}

g5::~g5(){
  if(pData != 0){
    for(int i = 0; i < 10; i++)
      delete[] pData[i];
    delete[] pData;
  }
  if(pFreq != 0)
    delete[] pFreq;
}

void g5::getFreq(){

  for(int i = 0; i < 10; i++)
    for(int j = 0; j < 5; j++)
      pFreq[pData[i][j] - 1]++;
}


void g5::printG5() const {
  std::cout<<"Guess5 Drawings for " << Date << " used Machine "
	   << Machine << " with Ball Set " << SetNo << std::endl;
  std::cout << "The drawing results are:" << std::endl;
  for(int i = 0; i < 10; i++){
    for(int j = 0; j < 5; j++)
      std::cout << pData[i][j] << " ";
    std::cout << std::endl;
    }
}

//g5Array.h
#ifndef G5ARRAY_H
#define G5ARRAY_H

#include <iostream>
#include <vector>
#include <string>
#include "g5.h"

class g5Array{

  std::vector<std::vector<g5> > v;  
  int nDraws;

 public:

  struct const_iterator : public 
        std::iterator<std::forward_iterator_tag, g5> {
    int Index;
    const g5Array* const_pA;
    std::vector<g5>::const_iterator const_current;
    const_iterator(){}
    const_iterator(const g5Array* pa) : const_pA(pa) {}
    const g5& operator*() const {return *const_current;}
    const g5* operator->() const {return &(*const_current);}
    const_iterator& operator=(const const_iterator& iter);
    bool operator==(const const_iterator& iter) const;
    bool operator!=(const const_iterator& iter) const {
      return !(*this == iter);
    }
    const_iterator operator++();
    const_iterator operator++(int){return operator++();}
    int nextIndex();
  };

  g5Array(const char* fileName);
  bool operator==(const g5Array& gA) const {
    if(v == gA.v) return true;
    return false;
  }
  const_iterator begin() const;
  const_iterator end() const;

  double chiSquare() const;
  std::vector<g5> g5Sort() const;
  const_iterator lookUp(const std::string s) const;
};
#endif

//g5Array.cpp
#include <iostream>
#include <cmath>
#include <numeric>
#include "g5Array.h"
#include "fileIn.h"
#include "functors.h"

g5Array::g5Array(const char* fileName){

  int s, drawIndex = 0;
  //initialize v
  v = std::vector<std::vector<g5> >::vector(20);
  //determine the number of draws
  fileIn fIn(fileName);
  nDraws = fIn.getVNRows()/11;
  //temporary storage for draw data
  short** pTemp = new short*[10];
  for(int i = 0; i < 10; i++)
    pTemp[i] = new short[5];

  for(int k = 0; k < nDraws; k++){
    //first copy in the draw data
    for(int i = 0; i < 10; i++){
      for(int j = 0; j < 5; j++){
	pTemp[i][j] = atoi(fIn.getV(drawIndex + 1 + i, j).c_str());
      }
    }
    
    s = atoi(fIn.getV(drawIndex, 2).c_str());
    if(fIn.getV(drawIndex, 1) == "A")
      v[s - 1].push_back(g5(fIn.getV(drawIndex, 0), 
	fIn.getV(drawIndex, 1), 
	atoi(fIn.getV(drawIndex, 2).c_str()), 
	fIn.getV(drawIndex, 3), pTemp));
    else
      v[9 + s].push_back(g5(fIn.getV(drawIndex, 0), 
	fIn.getV(drawIndex, 1), 
	atoi(fIn.getV(drawIndex, 2).c_str()), 
	fIn.getV(drawIndex, 3), pTemp));

    drawIndex += 11;
  }
  
  //memory clean-up
  for(int i = 0; i < 10; i++)
    delete[] pTemp[i];
  delete pTemp;
}

double g5Array::chiSquare() const {
 
  int* freq = new int[40];
  for(int i = 0; i < 40; i++)
    freq[i] = 0;

  sumFreq f;
  freq = std::accumulate(begin(), end(), freq, f);

  double e = 10*nDraws*5/40;
  double chiStat = 0;
  double* temp = new double[40];
  std::transform(&freq[0], &freq[40], &temp[0], 
	std::bind2nd(std::minus<double>(), e));
  std::transform(&temp[0], &temp[40], &temp[0], 
	std::bind2nd(std::divides<double>(), sqrt(e)));
  chiStat = std::inner_product(&temp[0], &temp[40], &temp[0], 0.);

  return (39./35.)*chiStat;
  }

std::vector<g5> g5Array::g5Sort() const {
  std::vector<g5> vSort(nDraws);
  std::copy(this->begin(), this->end(), vSort.begin());
  g5Less f;
  std::sort(vSort.begin(), vSort.end(), f);
 
  return vSort;
}

g5Array::const_iterator g5Array::lookUp(const std::string s) const {
 
  g5Equal f;
  
  const_iterator iter = std::find_if(begin(), end(), 
        std::bind2nd(f, s));
  return iter;
}

g5Array::const_iterator g5Array::begin() const {

  const_iterator iter;
  iter.const_pA = this; 
  if(v.empty()){
    iter.Index = 0; 
    iter.const_current = v[0].begin();
    return iter;
  }
  int i = 0;
  while(v[i].empty())
    i++;
  iter.Index = i; iter.const_current = v[i].begin();
  
  return iter;
}

g5Array::const_iterator g5Array::end() const {  
  const_iterator iter;
  iter.const_pA = this;
  if(v.empty()){
    iter.Index = 0; 
    iter.const_current = v[0].end();
    return iter;
  }
 
  int i = 19;
  while(v[i].empty())
    i--;
  iter.Index = i; iter.const_current = v[i].end(); 

  return iter;
}

//const_iterator class

g5Array::const_iterator& g5Array::const_iterator::operator=(const const_iterator& iter){
  const_current = iter.const_current;  const_pA = iter.const_pA; Index = iter.Index;
  return *this;
}
    
bool g5Array::const_iterator::operator==(const const_iterator& iter) const {
  return (const_current == iter.const_current  && const_pA == iter.const_pA 
	  && Index == iter.Index) ;
}

g5Array::const_iterator g5Array::const_iterator::operator++(){

  const_current++;
  if(const_current == const_pA->v[19].end()){
    *this = const_pA->end();
    return *this;
  }

  if(const_current == const_pA->v[Index].end()){
    Index = nextIndex();

  if(Index == -1){
    *this = const_pA->end();
    return *this;
  }

  const_current = const_pA->v[Index].begin();
  }
  return *this;
}

int g5Array::const_iterator::nextIndex(){

  int temp = Index + 1;
  while(temp < 19 && this->const_pA->v[temp].empty())
    temp++;
  
  if(const_pA->v[temp].empty())
    return -1;//all remaining slots are empty

  return temp;
}

//functors.h
#ifndef FUNCTORS_H
#define FUNCTORS_H

#include <iostream>
#include <cstdlib>
#include <string>
#include "g5.h"

struct sumFreq  : public std::binary_function<int*, g5,  int*> {
  
  sumFreq(){}

  int* operator()(int* freq, const g5& g){

    for(int i = 0; i < 40; i++)
      freq[i] += g.getFreq(i);
    return freq;
  }
};

struct g5Less : public std::binary_function<g5, g5,  bool> {

  g5Less(){}

  bool operator ()(const g5& g1, const g5& g2){

    std::string temp1, temp2;
    temp1 = g1.getDate(); temp2 = g2.getDate();
    if(atoi(temp1.substr(0, 3).c_str()) < atoi(temp2.substr(0, 3).c_str()))
      return true;
    if(atoi(temp1.substr(0, 3).c_str()) == atoi(temp2.substr(0, 3).c_str()) 
       && atoi(temp1.substr(5, 6).c_str()) < atoi(temp2.substr(5, 6).c_str()))
      return true;
    if(atoi(temp1.substr(0, 3).c_str()) == atoi(temp2.substr(0, 3).c_str()) 
       && atoi(temp1.substr(5, 6).c_str()) == atoi(temp2.substr(5, 6).c_str()) 
       && atoi(temp1.substr(8, 9).c_str()) < atoi(temp2.substr(8, 9).c_str()))
      return true;
    return false;
  }
};

struct g5Equal : public std::binary_function<g5, std::string, bool> {
  
  g5Equal(){}

  bool operator() (const g5& g, const std::string s) const {
    if(g.getDate() == s)
      return true;
    return false;
  }
};
#endif
///////////////////////////////////////////////////////////////////////
//listEx.cpp
#include <iostream>
#include <vector>
#include <list>

using std::cout; using std::endl; using std::vector;
using std::list;

int main(){
  vector<int> v(3); 
  v[0] = 12; v[1] = 1; v[2] = 2;

  list<int> L;
  L.assign(v.begin(), v.end());
  for(list<int>::iterator iter = L.begin(); iter != L.end(); iter++){
    cout << L.front() << " ";
    L.pop_front();
  }
  cout << endl;
  cout << "Empty? " << std::boolalpha << L.empty() << endl;

  L = list<int>(3, 12);
  for(list<int>::iterator iter = L.begin(); iter != L.end(); iter++)
    cout << L.front() << " ";
  cout << endl;
  L.clear();
  cout << "Empty? " << std::boolalpha << L.empty() << endl;

  return 0;
}
///////////////////////////////////////////////////////////////////////
//indexEx.cpp
#include <iostream>
#include <list>
#include <string>
#include <cstdlib>
#include "fileIn.h"

using std::cout; using std::endl; using std::list;
using std::string; using std::ostream;

struct Date{
  int Year, Month, Day;

  Date(){}
  Date(int year, int month, int day)
    : Year(year), Month(month), Day(day) {}

  bool operator<(const Date& date) const;
  bool operator>=(const Date& date) const {
    return !(*this < date);
  }
  bool operator==(const Date& date) const;
  bool operator!=(const Date& date) const {
    return !(*this == date);
  }
};

ostream& operator<<(ostream& out, const Date& date){
  cout << date.Month << "-" << date.Day << "-" << date.Year;
  return out;
}

bool Date::operator<(const Date& date) const {
  if(Year < date.Year)
    return true;
  if(Year == date.Year && Month < date.Month)
    return true;
  if(Year == date.Year && Month == date.Month
     && Day < date.Day)
    return true;
  return false;
}

bool Date::operator==(const Date& date) const {
  if(Year == date.Year && Month == date.Month
     && Day == date.Day)
    return true;
  return false;
}
    
struct IndexData{
  Date T;
  double Value;
  IndexData(){}
  IndexData(Date t, double value) : T(t), Value(value) {}
};

std::ostream& operator<<(ostream& out, const IndexData& d){
  cout << d.T << " " << d.Value;
  return out;
}

struct IndexList{
  list<IndexData> L;

  IndexList(){}
  IndexList(fileIn fIn);

  IndexData pop_front();
  list<IndexData>::iterator lookUp(const Date& date);
  list<IndexData>::iterator insert(const IndexData& d);
};

IndexList::IndexList(fileIn fIn){
  Date tempD;
  IndexData tempI; 
  int idx1, idx2;
  for(int i = 0; i < fIn.getVNRows(); i++){
    idx1 = fIn.getV(i, 0).find_first_of("-");
    idx2 = fIn.getV(i, 0).find_last_of("-");
    tempD.Year = atoi(fIn.getV(i, 0).substr(0, idx1).c_str());
    tempD.Month = atoi(fIn.getV(i, 0).substr(idx1 + 1,
	idx2 - idx1 - 1).c_str());
    tempD.Day = atoi(fIn.getV(i, 0).substr(idx2 + 1).c_str());    
    tempI.T = tempD;
    tempI.Value = atof(fIn.getV(i, 1).c_str());
    L.push_front(tempI);
  }
}

IndexData IndexList::pop_front(){
  IndexData d;
  if(!L.empty()){
    d = L.front();
    L.pop_front();
    return d;
  }
  return IndexData();
}

list<IndexData>::iterator IndexList::lookUp(const Date& date){
  list<IndexData>::iterator iter = L.begin();
  while(iter->T != date && iter != L.end())
    iter++;
  return iter;
}
  
list<IndexData>::iterator IndexList::insert(const IndexData& d){
  list<IndexData>::iterator iter = L.begin();
  while(iter->T >= d.T && iter != L.end())
    iter++;
  if(iter == L.end())
    L.push_back(d);
  else
    L.insert(iter, d);
  return iter;
}

int main(){
  IndexList C(fileIn("index.txt"));
  Date tempD; 
  IndexData tempI;
  tempD.Year = 1952; tempD.Month = 05; tempD.Day = 29;
  tempI.T = tempD; tempI.Value =  2490.794985197;
  list<IndexData>::reverse_iterator riter(C.insert(tempI));
  riter--;
  while(riter != C.L.rend()){
    cout << *riter << endl;
    riter++;
  }
  
  return 0;
}
///////////////////////////////////////////////////////////////////////
//chainHash.cpp
#include <iostream>
#include <cmath>
#include <utility>
#include <vector>
#include <list>

using std::cout; using std::endl; using std::pair;
using std::vector; using std::list;

template<class Key, class Data> 
class chainHash {
  int tableSize, Size;
  vector<list<pair<Key, Data> > > Table;
  int hash(Key a) const;

public:

 chainHash(int tablesize) : tableSize(tablesize), Size(0) {
    Table.resize(tableSize);
  }
  struct iterator{
    chainHash* pCH;
    int Index;
    typename list<pair<Key, Data> >::iterator current;
    iterator(){}
    iterator (chainHash<Key, Data>* pch, int index, 
	typename list<pair<Key, Data> >::iterator iter)
        : pCH(pch), Index(index), current(iter){}
    pair<Key, Data>& operator*() const;
    pair<Key, Data>* operator->() const;
    bool operator==(const iterator& iter) const;
    bool operator!=(const iterator& iter) const;
    iterator operator++();
    iterator operator++(int){return operator++();}
    void nextBucket();
  };

  iterator insert(pair<Key, Data> a);
  iterator lookUp(Key a);
  iterator begin();
  iterator end();
  int getSize() const {return Size;}
  int getTableSize() const {return tableSize;}
};

template<class Key, class Data> int 
        chainHash<Key, Data>::hash(Key a) const { 
  return ((int) floor(a)) % tableSize; 
}

template<class Key, class Data> 
        typename chainHash<Key, Data>::iterator 
        chainHash<Key, Data>::insert(pair<Key, Data> a){
  int index = hash(a.first);
  Table[index].push_front(a);
  iterator iter(this, index, Table[index].begin());
  Size++;
  return iter;
}

template<class Key, class Data> 
        typename chainHash<Key, Data>::iterator 
        chainHash<Key, Data>::lookUp(Key a) {
  int index = hash(a);
  typename chainHash<Key, Data>::iterator 
    iter(this, index, Table[index].begin());
  while(iter->first != a && iter.current != Table[index].end())
    iter++;
  
  return iter;
}

template<class Key, class Data> 
        typename chainHash<Key, Data>::iterator 
        chainHash<Key, Data>::begin(){
  iterator iter;
  iter.pCH = this;
  //start the search in a bucket with index 0
  iter.Index = -1;
  //now set Index and current
  iter.nextBucket();
  return iter;
}

template<class Key, class Data> 
        typename chainHash<Key, Data>::iterator 
        chainHash<Key, Data>::end(){  
  iterator iter;
  iter.pCH = this;
  iter.Index = -1;
  iter.current = Table[0].end();
  return iter;
}

template <class Key, class Data> pair<Key, Data>& 
        chainHash<Key, Data>::iterator::operator*() const {
  return *current;
}

template <class Key, class Data> pair<Key, Data>* 
        chainHash<Key, Data>::iterator::operator->() const {
  return &(*current);
}
  
template <class Key, class Data> bool 
        chainHash<Key, Data>::iterator::operator==(
	const iterator& iter) const {
  return (current == iter.current && Index == iter.Index 
	  && pCH == iter.pCH);
}

template <class Key, class Data> bool 
        chainHash<Key, Data>::iterator::operator!=(
	const iterator& iter) const {
  return !(*this == iter);
}

template <class Key, class Data>
        typename chainHash<Key, Data>::iterator 
        chainHash<Key, Data>::iterator::operator++(){
  if(*this == pCH->end())
    return *this;

  current++;
  if(current == pCH->Table[Index].end())
    nextBucket();
  if(Index == -1)
    return pCH->end();
  else
    return *this;
}

template <class Key, class Data> void 
        chainHash<Key, Data>::iterator::nextBucket(){
  for(int i = Index + 1; i < pCH->tableSize; i++)
    if(!pCH->Table[i].empty()){
      Index = i;
      current = pCH->Table[i].begin();
      return;
    }
  
  //no empty buckets were found
  Index = -1; current = pCH->Table[0].end();
}      


int main(){
  chainHash<double, int> cH(3);
  cout << "The table size is " << cH.getTableSize() << endl;

  for(int i = 0; i < 10; i++)
    cH.insert(pair<double, int>(sqrt(i), i*i));
  cout << "The number of objects in the container is " << 
    cH.getSize() << endl;
  
  chainHash<double, int>::iterator iter = cH.lookUp(sqrt(5));
  cout << iter.Index << " " << iter->first << " " 
       << iter->second << endl;
  iter++;
  cout << iter.Index << " " << iter->first << " " 
       << iter->second << endl;  

  for(iter = cH.begin(); iter != cH.end(); iter++)
    cout << iter.Index << " " << iter->first << endl;
 
  return 0;
}
///////////////////////////////////////////////////////////////////////
//customer.h
struct Customer{
  int Arrive;
  bool Gold;
  Customer(int t = 0, bool gold = 0) : Arrive(t), Gold(gold) {}

  bool operator<(const Customer& x) const;
};

bool Customer::operator<(const Customer& x) const {
  if(Gold == 0 && x.Gold == 0 ||
     Gold == 1 && x.Gold == 1){
    if(Arrive < x.Arrive)//give earlier arrival higher priority
      return false;
    else
      return true;
  }

  if(Gold == 0 && x.Gold == 1)
    return true;
  if(Gold == 1 && x.Gold == 0)
    return false;
}


std::ostream& operator<<(std::ostream& out, const Customer& x){
  out << "Arrival time = " <<  x.Arrive << " Gold = " <<
    std::boolalpha << x.Gold << std::endl;
  return out;
}  

//server.h

struct Server{
  bool Busy;
  int serviceTime;
  Server(){
    Busy = 0; serviceTime = 0;
  }
};

std::ostream& operator<<(std::ostream& out, Server& s) {
  out << " busy = " <<  std::boolalpha << s.Busy << 
    " service time = " << s.serviceTime << std::endl;
  return out;
}

//MMNQueue.cpp
#include <iostream>
#include <cmath>
#include <queue>
#include "ranGen.h"
#include "customer.h"
#include "server.h"

using std::cout; using std::endl;
using std::ostream;

class MMNQueue{
  
  std::priority_queue<Customer> Q;
  Server* pS;//array of servers
  ranGen Rng;//random number generator
  void upDate(int t);
  int rPoisson();
  double rExp(double lambda);
  bool isGold();
  void upDateServers();
  int freeServer();

  //simulation parameters  
  int runTime, nServers;
  double lambdaC, lambdaT, goldProb;
  unsigned long Seed;

  //statistics
  int totalTime, numberCustomers;

public:

  MMNQueue(int runtime, int nservers, double lambdac,
        double lambdat, double goldprob, unsigned long seed) : 
        runTime(runtime), nServers(nservers), lambdaC(lambdac), 
        lambdaT(lambdat), goldProb(goldprob), Seed(seed){

    totalTime = 0; numberCustomers = 0;
    pS = new Server[nServers];
    Rng = ranGen();
    Rng.setSeed(Seed);
  }

  ~MMNQueue(){
    delete[] pS;
  }
  
  double runSimulation();
};

double MMNQueue::runSimulation(){
  for(int t = 0; t < runTime; t++){
    cout << "For time = " << t << endl;
    upDate(t);
    cout << "queue size " << Q.size() << endl;
    cout << endl;
  }

  while(!Q.empty()){//may be some people still in the queue
    totalTime += runTime - Q.top().Arrive;
    Q.pop();
  }

  return ((double)totalTime/(double)numberCustomers);  
}

void MMNQueue::upDate(int t){
  upDateServers();

  int serverIndex = 0;
  //number of new customers that arrived in last minute
  int numberNew = rPoisson();
  cout << "number of new customers " << numberNew << endl; 
  
  //serve as many as possible right away
  while(freeServer() != -1 && Q.empty() && numberNew > 0){
    serverIndex = freeServer();
    pS[serverIndex].Busy = 1;
    pS[serverIndex].serviceTime = ceil(rExp(lambdaT));
    numberNew--;
  }

  Customer temp;
  if(numberNew > 0){//add to the queue
    for(int i = 0; i < numberNew; i++){
      temp = Customer(t, isGold());
      cout << "New waiting customer has " << temp;
      Q.push(temp);
    }
    numberCustomers += numberNew;
  }
  
  while(freeServer() != -1 && !Q.empty()){
    serverIndex = freeServer();
    pS[serverIndex].Busy = 1;
    pS[serverIndex].serviceTime = ceil(rExp(lambdaT));

    totalTime += t - Q.top().Arrive;
    cout << "Customer being served has " << Q.top();
    Q.pop();//remove customer
  }
}  

int MMNQueue::rPoisson(){
  double sum = rExp(1./lambdaC);
  int numberNew = 0;
  while(sum < 1){
    numberNew++;
    sum += rExp(1./lambdaC);
  }

  return numberNew;
}
    
double MMNQueue::rExp(double lambda){
  double u = 0.;
  Rng.ranUnif(1, &u);
  return (-lambda*log(1. - u));
}

bool MMNQueue::isGold(){
  double u = 0.;
  Rng.ranUnif(1, &u);
  if(u < goldProb)
    return true;
  return false;
}

int MMNQueue::freeServer(){

  int serverIndex = 0;
  while(pS[serverIndex].Busy && serverIndex < nServers - 1)
    serverIndex++;

  if(pS[serverIndex].Busy)
    return -1;
  else
    return serverIndex;
}

void MMNQueue::upDateServers(){
  for(int i = 0; i < nServers; i++){
    if(pS[i].serviceTime > 0)
      pS[i].serviceTime--;//reduce remaining service time
    if(pS[i].serviceTime == 0)
      pS[i].Busy = 0;//free server for new customer
  }  
}

int main(){
  MMNQueue bSim(10, 4, 4, 2, .1, 123);
  cout << bSim.runSimulation() << endl;  
  return 0;
}
///////////////////////////////////////////////////////////////////////
//mapEx.cpp
#include <iostream>
#include <utility>
#include <map>

using std::cout; using std::endl; using std::map; using std::pair;

int main(){

  map<int, int> m;
  m.insert(pair<int, int> (4, 4)); m.insert(pair<int, int> (0, 2));
  cout << m[0] << endl;
  m[0] = 1;
  cout << m[0] << endl;
  m[1] = 2;
  cout << m[1] << endl;
  m[3] = 1; m[2] = 11; m[6] = 5; m[7] = 4; m[5] = 5; m[21] = -3;
  m[-15] = 99; m[-16] = 5; m[-3] = 3; m[-1] = 9; m[-2] = 14;

  map<int, int>::iterator iter;
  for(iter = m.begin(); iter != m.end(); iter++)
    cout << iter->first << " ";
  cout << endl;
  iter = m.find(-2);
  cout << iter->second << endl;
  m.erase(iter); m.erase(-16); m.erase(-15); m.erase(-1);

  map<int, int>::reverse_iterator riter;
  for(riter = m.rbegin(); riter != m.rend(); riter++)
    cout << riter->first << " ";
  cout << endl;
  return 0;
}
///////////////////////////////////////////////////////////////////////
//driverG5.cpp
#include <iostream>
#include <string>
#include "g5Array.h"

int main(){
  g5Array g5A("guess5.txt");
  std::cout << "Chi-square results" << std::endl;
  std::cout << g5A.chiSquare() << std::endl;  
  std::vector<g5> vSort = g5A.g5Sort();
  std::cout << "Sorting results" << std::endl;
  for(int i = 0; i < 3; i++)
  vSort[i].printG5();
  std::cout << std::endl;
  std::cout << "Lookup  results" << std::endl;
  g5Array::const_iterator iter 
    = g5A.lookUp(std::string("1952-04-14"));
  iter->printG5();

  return 0;
}
///////////////////////////////////////////////////////////////////////