SWE 501 - Object Oriented Programming

Queue Simulator, Version 3

#include <iostream>
#include <random>
#include <list>
#include <deque>

using namespace std;

enum {CUSTOMER_ARRIVAL, CUSTOMER_LEAVE, PRINT};

class Event {
	int type;
	double time;
	int data;

	friend ostream& operator<<(ostream&, Event&);
public:
	Event(int typ, double t, int d=0) : type(typ), time(t), data(d) {};
	double Time() {return time;};
	int Type() {return type;};
	int Data() {return data;};

};

bool comp(Event& a, Event& b) {
	return a.Time() > b.Time();
}


ostream& operator<<(ostream& out, Event& e) {
	out << e.type << " " << " " << e.time << " " << e.data;
	return out;
};

/*
struct Customer {
	int id;
	double arrival_time;
	double service_start_time;
	double finish_time;

	Customer(int _id, double t0, double t1 = 0, double t2 = 0);
	id(_id), arrival_time(t0), service_start_time(t1), finish_time(t2) {};
};
*/



double D_min = 5;
double D_max = 50;
double T_min = 0.01;
double T_max = 5;
uniform_real_distribution<double> InterArrival(T_min, T_max);
uniform_real_distribution<double> Duration(D_min, D_max);

double current_time;
mt19937 rgen;

class EventGenerator {
public:
	EventGenerator() {}
	Event operator()(int typ, double dt, int data=0) {
		return Event(typ, current_time+dt, data);
	}
};

class Server {
	deque<int> Clients;
public:
	void AddClient(int id) {
		Clients.push_back(id);
	}
	int RemoveClient(int i) {
		if (Clients.front() != i) cout << "Something wrong!" << endl;
		Clients.pop_front();
		return i;
	}

	int Front() {
		return Clients.front();
	}

	bool isEmpty() {
		return Clients.empty();
	}

};


int main() {
	vector<Event> EventHeap;
	current_time = 0.0;
	int end_time = 100.0;
	int current_id = 0;

	Server S;

	EventGenerator EvGen;

	Event e = EvGen(CUSTOMER_ARRIVAL, InterArrival(rgen), current_id);
	EventHeap.push_back(e);

	e = EvGen(PRINT, 0.0);
	EventHeap.push_back(e); push_heap (EventHeap.begin(), EventHeap.end(), comp);


	while (EventHeap.size()>0) {
		pop_heap(EventHeap.begin(), EventHeap.end(), comp);
		Event cur = EventHeap.back();
		EventHeap.pop_back();

		current_time = cur.Time();

		switch (cur.Type()) {
			case CUSTOMER_ARRIVAL:
				cout << current_time << ":" << cur.Data() << " has arrived" << endl;
				//e = EvGen(CUSTOMER_LEAVE, Duration(rgen), cur.Data());


				if (S.isEmpty()) {
					e = EvGen(CUSTOMER_LEAVE, Duration(rgen), cur.Data());
					EventHeap.push_back(e);
					push_heap (EventHeap.begin(), EventHeap.end(), comp);
				}
				S.AddClient(cur.Data());

				if (current_time<end_time) {
					current_id++;
					Event e2 = EvGen(CUSTOMER_ARRIVAL, InterArrival(rgen), current_id);
					EventHeap.push_back(e2);
					push_heap (EventHeap.begin(), EventHeap.end(), comp);
				}

			break;
			case CUSTOMER_LEAVE:
				cout << current_time << ": " << cur.Data() << " has left at time "  << endl;
				S.RemoveClient(cur.Data());
				if (not S.isEmpty()) {
					e = EvGen(CUSTOMER_LEAVE, Duration(rgen), S.Front());
					EventHeap.push_back(e);
					push_heap (EventHeap.begin(), EventHeap.end(), comp);
				}

			break;
			case PRINT:
				cout << current_time << " Print Event" << endl;
				if (current_time < end_time) {
					e = EvGen(PRINT, 10.0);
					EventHeap.push_back(e); push_heap (EventHeap.begin(), EventHeap.end(), comp);
				}
			break;
		}


	}



}

Discrete Event Simulation

Arrival Simulator, Version 2, Not finished yet


#include <iostream>
#include <random>
#include <list>
using namespace std;

enum {CUSTOMER_ARRIVAL, CUSTOMER_LEAVE};

class Event {
	int type;
	int id;
	double time;
	double data;

	friend ostream& operator<<(ostream&, Event&);
public:
	Event(int typ, int _id, double t, double d) : type(typ), id(_id), time(t), data(d) {};
	double Time() {return time;};
	int Type() {return type;};
	int Id() {return id;};
	double Data() {return data;};


};

bool comp(Event& a, Event& b) {
	return a.Time() > b.Time();
}


ostream& operator<<(ostream& out, Event& e) {
	out << e.type << " " << e.id << " " << e.time << " " << e.data;
	return out;
}

struct Customer {
	int id;
	double arrival_time;
	double service_start_time;
	double finish_time;

	Customer(int _id, double t0, double t1 = 0, double t2 = 0)
	id(_id), arrival_time(t0), service_start_time(t1), finish_time(t2) {};
};




double D_min = 5;
double D_max = 50;
double T_min = 0.01;
double T_max = 5;
uniform_real_distribution<double> InterArrival(T_min, T_max);
uniform_real_distribution<double> Duration(D_min, D_max);

class EventGenerator {
	mt19937 rgen;
	int last_id;
public:
	EventGenerator() {
		last_id = 0;
	}

	Event operator()(int typ, double t, int _id = 0) {
		switch (typ) {

		case CUSTOMER_ARRIVAL:
		{
			double d = Duration(rgen);
			double tt = t + InterArrival(rgen);
			return Event(typ, last_id++, tt, d);
			break;
		}
		case CUSTOMER_LEAVE:
			return Event(typ, _id, t, 0);
			break;
		}
	}
};


int main() {
	vector<Event> EventHeap;
	EventGenerator EvGen;

	double t = 0;
	Event e = EvGen(CUSTOMER_ARRIVAL, t);

	EventHeap.push_back(e);

	while (EventHeap.size()>0) {
		pop_heap(EventHeap.begin(), EventHeap.end(), comp);
		Event cur = EventHeap.back();
		EventHeap.pop_back();

		t = cur.Time();

		switch (cur.Type()) {
			case CUSTOMER_ARRIVAL:
				cout << cur.Id() << " has arrived at time " << t << endl;

				e = EvGen(CUSTOMER_LEAVE, t+cur.Data(), cur.Id());
				EventHeap.push_back(e);
				push_heap (EventHeap.begin(), EventHeap.end(), comp);
				if (t<100) {
					Event e2 = EvGen(CUSTOMER_ARRIVAL, t);
					EventHeap.push_back(e2);
					push_heap (EventHeap.begin(), EventHeap.end(), comp);
				}
			break;
			case CUSTOMER_LEAVE:
				cout << cur.Id() << " has left at time " << t << endl;
			break;
		}


	}



}

Discrete Event Simulation

Arrival Simulator
#include <iostream>
#include <random>
#include <list>
using namespace std;

enum {CUSTOMER_ARRIVAL};

class Event {
	int type;
	double time;
	double duration;

	friend ostream& operator<<(ostream&, Event&);
public:
	Event(int typ, double t, double d) : type(typ), time(t), duration(d) {};
};

ostream& operator<<(ostream& out, Event& e) {
	out << e.type << " " << e.time << " " << e.duration;
	return out;
}

double D_min = 5;
double D_max = 10;
double T_min = 0.01;
double T_max = 5;
uniform_real_distribution<double> InterArrival(T_min, T_max);
uniform_real_distribution<double> Duration(D_min, D_max);

class EventGenerator {
	mt19937 rgen;
	double t;
public:
	EventGenerator() {
		t = 0;
	}
	Event operator()(void) {
		double d = Duration(rgen);
		t += InterArrival(rgen);
		return Event(CUSTOMER_ARRIVAL, t, d);
	}
	Event operator()(int typ) {
		double d = Duration(rgen);
		t += InterArrival(rgen);
		return Event(typ, t, d);
	}


};


int main() {
	list<Event> elist;
	EventGenerator EvGen;

	for (int i=0; i<10; i++) {
		Event e = EvGen(CUSTOMER_ARRIVAL);
		elist.push_back(e);
		cout << e << endl;
	}

}

Refactor the code

Random Matrix Constructor

Kmeans – Improved Version

//============================================================================
// Name        : kmeans.cpp
// Author      : atc
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <fstream>
#include <vector>
#include <limits>
#include <string>

double Inf;

using namespace std;

class Matrix {
	int D;
	int N;
	vector<double> data;

public:

	Matrix(int _D, int _N = 0) {
		D = _D;
		N = _N;

		if (D*N > 0) data.resize(D*N, 0);
	}

	Matrix(string fn) {
		ifstream in(fn);
		N = 0;
		if (not in.is_open()) {
			D = 0;
			return;
		}

		double temp;
		in >> D;
		vector<double> v(D);
		int idx = 0;
		while (true)  {
			in >> temp;
			if (in.eof()) break;
			v[idx++] = temp;

			if (idx % D == 0) {
				idx = 0;
				push_back(v);
			}
		}
		in.close();

	}

	void push_back(vector<double>& x) {
		if (x.size() != D) return;

		for (auto d : x)
			data.push_back(d);

		N++;
	}

	vector<double> get_column(unsigned int n) {
		vector<double> ret(D);
		if (n>=N) {
			ret.resize(0);
			return ret;
		}

		for (int i=0; i<D; i++) ret[i] = data[n*D+i];
		return ret;
	}

	void set_column(unsigned int j, vector<double>& v) {
		if (v.size() != D or j>=N) return;

		for (int i=0; i<D; i++) data[j*D+i] = v[i];
		return;
	}

	vector<double> get_row(unsigned int r) {
		vector<double> ret(N);
		if (r>=D) {
			ret.resize(0);
			return ret;
		}

		for (int i=0; i<N; i++) ret[i] = data[D*i+r];
		return ret;
	}

	void set_row(unsigned int r, vector<double>& v) {
		if (v.size() != N or r>=D) return;

		for (int j=0; j<N; j++) data[D*j+r] = v[j];
		return;
	}

	unsigned int nrows() {return D;}
	unsigned int ncols() {return N;}

	void combine_column(unsigned int j, vector<double>& v, double lam = 1.0) {
		if (v.size() != D or j>=N) return;

		for (int i=0; i<D; i++) data[j*D+i] = data[j*D+i]*(1-lam) + v[i]*lam;
		return;

	}

	vector<double>& raw_data() {return data;};

};


ostream& operator<<(ostream& os, Matrix& M) {
	vector<double> v;
	cout << endl;
	for (unsigned int i=0; i<M.nrows(); i++) {
		v = M.get_row(i);
		for (auto d : v) cout << d << "\t";
		cout << endl;
	}
	cout << "size = " << M.nrows() << " " << M.ncols() << endl;
	return os;
}

double dist2(vector<double>& x, vector<double>& y, int D=0 ) {
	if (D==0) {
		D = x.size();
	}
	double d = 0;
	double e;
	for (int i=0; i<D; i++) { e = x[i]-y[i]; d+=e*e; }
	return d;
}

int main() {
	Inf = std::numeric_limits<double>::infinity();
	int K = 3;

	Matrix X("/Users/cemgil/Dropbox/Public/fe587/ornek2014/kmeans/src/data.txt");
	int D = X.nrows();
	cout << X;


	Matrix Means(D, K);
	for (int j=0;j<K; j++) {
		vector<double> v = X.get_column(j);
		Means.set_column(j, v);
	}

	unsigned int N = X.ncols();
	cout << Means;
	int iteration = 0;
	while (true) {
		iteration++;
		Matrix tempM(D,K);
		vector<int> counts(K, 0);

		for (int j=0; j<N; j++) {
			vector<double> x = X.get_column(j);

			double d_min = Inf;
			int idx_min = 0;
			for (int k=0; k<K; k++) {
				vector<double> m = Means.get_column(k);
				double d = dist2(x, m);
				if (d<d_min) {
					d_min = d;
					idx_min = k;
				}
			}
			cout << idx_min << " ";
			counts[idx_min]++;
			tempM.combine_column(idx_min, x, 1.0/counts[idx_min]);

		}

		cout << endl << "iter = " <<  iteration << endl;
		cout << tempM;

		if (dist2(Means.raw_data(), tempM.raw_data()) < 1E-7 ) break;
		Means = tempM;

	}

	return 0;

}

Example

Kmeans (INCOMPLETE YET)

#include <iostream>
#include <fstream>
#include <vector>


using namespace std;

class Matrix {
	int D;
	int N;
	vector<double> data;

public:

	Matrix(int _D, int _N = 0) {
		D = _D;
		N = _N;

		if (D*N > 0) data.resize(D*N, 0);
	}

	void push_back(vector<double>& x) {
		if (x.size() != D) return;

		for (auto d : x)
			data.push_back(d);

		N++;
	}

	vector<double> get_column(unsigned int n) {
		vector<double> ret(D);
		if (n>=N) {
			ret.resize(0);
			return ret;
		}

		for (int i=0; i<D; i++) ret[i] = data[n*D+i];
		return ret;
	}

	void set_column(unsigned int j, vector<double>& v) {
		if (v.size() != D or j>=N) return;

		for (int i=0; i<D; i++) data[j*D+i] = v[i];
		return;
	}


	vector<double> get_row(unsigned int r) {
		vector<double> ret(N);
		if (r>=D) {
			ret.resize(0);
			return ret;
		}

		for (int i=0; i<N; i++) ret[i] = data[D*i+r];
		return ret;
	}

	void set_row(unsigned int r, vector<double>& v) {
		if (v.size() != N or r>=D) return;

		for (int j=0; j<N; j++) data[D*j+r] = v[j];
		return;
	}


	unsigned int nrows() {return D;}
	unsigned int ncols() {return N;}

};


ostream& operator<<(ostream& os, Matrix& M) {
	vector<double> v;
	for (unsigned int i=0; i<M.nrows(); i++) {
		v = M.get_row(i);
		for (auto d : v) cout << d << "\t";
		cout << endl;
	}
}


int main() {
	ifstream in("/Users/cemgil/Dropbox/Public/fe587/ornek2014/kmeans/src/data.txt");
	double temp;
	int D;
	int K = 3;

	if (in.is_open()) cout << "Open" << endl; else {cout << "Not open"; return -1;}

	in >> D;

	Matrix X(D);
	vector<double> v(D);

	int idx = 0;
	while (true)  {
		in >> temp;
		if (in.eof()) break;
		v[idx++] = temp;

		if (idx % D == 0) {
			idx = 0;
			X.push_back(v);
		}
	}


	cout << X;

	Matrix M(D, K);
	for (int j=0;j<K; j++) {
		v = X.get_column(j);
		M.set_column(j, v);
	}


	cout << M;




	in.close();
	return 0;

}

Exercise

Write a function that takes a list of strings an prints them, one per line, in a rectangular frame. For example the list “World”, “in”, “a”, “frame” gets printed as:

Hello World in a frame

Programming Examples

Card Example, Improved


using namespace std;

struct Card {
	int rank;
	int suit;
	int order;

	Card(int r, int s) {

		if (r<1 or r>13) {
			cout << "Invalid Card" << endl;
			rank = suit = 0;
			return;
		}
		rank = r;
		suit = s;
		order = (s-1)*13 + r - 1;
	}

	Card(int o = 0) {
		if (o<0 or o>51) { cout << "Invalid Card"; return; }
		rank = (o%13) + 1;
		suit = (o/13) + 1;
		order = o;
	}

	void Print() {
		switch(rank) {
		case 1:
			cout << 'A';
			break;
		case 2:
		case 3:
		case 4:
		case 5:
		case 6:
		case 7:
		case 8:
		case 9:
		case 10:
			cout << rank;
			break;
		case 11:
			cout << 'J';
			break;
		case 12:
			cout << 'Q';
			break;
		case 13:
			cout << 'K';
			break;
			default:
			cout << "Invalid Rank";
			break;
		}

		switch(suit) {
		case 1: cout << "♥︎"; break;
		case 2: cout << "♠︎"; break;
		case 3: cout << "♦︎︎"; break;
		case 4: cout << "♣︎";	break;
		default: cout << "Invalid Suit";
		}

	}

};


struct Deck {
	Card card[52];
	int top;

	Deck() {
		for (int i = 0; i<52; i++) {
			card[i] = Card(i);
		}
		top = 51;
	}

	void Shuffle() {
		for (int i=51; i>=0; i--) {
			int idx = random() % (i+1);
			Card temp = card[idx];
			card[idx] = card[i];
			card[i] = temp;
		}
		top = 51;
	}

	Card nextCard() {
		if (top>=0)
			return card[top--];
		else {
			cout << "Deck Empty!!" << endl;
			return card[0];
		}
	}

	void Print() {
		for (int i = 0; i<=top; i++) {
			card[i].Print();
			cout << ' ';
		}
	}

};

const int CAPACITY = 4;

struct Pile {
	Card card[CAPACITY];
	int top;

	Pile() {
		top = -1;
	}

	bool isEmpty() {
		return top == -1;
	}

	int addCard(Card& c) {
		if (top >= CAPACITY) return -1;
		card[++top] = c;
		return 0;
	}

	Card nextCard() {
		if (top>=0) return card[top--];
		else {
			cout << "Pile Empty!" << endl;
			return card[0];
		}
	}

	void print() {
		for (unsigned int i=0; i<=top; i++) {
			card[i].Print();
			cout << ' ';
		}
	}

};



int main() {

	Card c;

	srandom(time(0));

	int success = 0;

	for (int epoch=1; epoch<=100000; epoch++) {
	Pile pile[13];

	Deck d;
	d.Shuffle();
//	d.Print();
//	cout &lt;&lt; '
';

	for (int j=0; j<4; j++) {
		for (int i=0; i<13; i++) {
			c = d.nextCard();
			pile[i].addCard(c);

//			cout &lt;&lt; i+1 &lt;&lt; '	';
//			pile[i].print();
//			cout &lt;&lt; endl;
		}
//		cout &lt;&lt; "-------" &lt;&lt; endl;
	}

	int total_played = 0;
	int idx = 12;
	while (!pile[idx].isEmpty()) {
		c = pile[idx].nextCard();
		total_played++;
		idx = c.rank - 1;
		// cout &lt;&lt; idx &lt;&lt; endl;
	}
	success += ((total_played == 51) ? 1 : 0);

	cout << double(success)/epoch  << endl;

	}

	return 0;
}

Card Example


#include <iostream>
#include <cstdlib>
#include <ctime>


using namespace std;

struct Card {
	int rank;
	int suit;
	int order;

	Card(int r, int s) {

		if (r<1 or r>13) {
			cout << "Invalid Card" << endl;
			rank = suit = 0;
			return;
		}
		rank = r;
		suit = s;
		order = (s-1)*13 + r - 1;
	}

	Card(int o = 0) {
		if (o<0 or o>51) { cout << "Invalid Card"; return; }
		rank = (o%13) + 1;
		suit = (o/13) + 1;
		order = o;
	}

	void Print() {
		switch(rank) {
		case 1:
			cout << 'A';
			break;
		case 2:
		case 3:
		case 4:
		case 5:
		case 6:
		case 7:
		case 8:
		case 9:
		case 10:
			cout << rank;
			break;
		case 11:
			cout << 'J';
			break;
		case 12:
			cout << 'Q';
			break;
		case 13:
			cout << 'K';
			break;
			default:
			cout << "Invalid Rank";
			break;
		}

		switch(suit) {
		case 1: cout << "♥︎"; break;
		case 2: cout << "♠︎"; break;
		case 3: cout << "♦︎︎"; break;
		case 4: cout << "♣︎";	break;
		default: cout << "Invalid Suit";
		}

	}

};


struct Deck {
	Card card[52];

	Deck() {
		for (int i = 0; i<52; i++) {
			card[i] = Card(i);
		}

	}

	void Shuffle(unsigned int seed = 0) {
		if (seed) srandom(seed);
		for (int i=51; i>0; i--) {
			int idx = random() % (i+1);
			Card temp = card[idx];
			card[idx] = card[i];
			card[i] = temp;
		}

	}


	void Print() {
		for (int i = 0; i<52; i++) {
			card[i].Print();
			cout << ' ';
		}
	}

};

int main() {
	Deck d;

	d.Shuffle(time(0));
	d.Print();


}