Merging tables done!

Lots of fun getting this one. I modified the starter code significantly,
so it's more like my Java code (I did deviate away with setID as int).
I'm happy for 2 things:
1. Learned and practiced again of passing by reference and modifying
vector<Table> elements through address
2. Debugging googletests with Eclipse, I tried it and it worked. I had
to click forward a few steps before I can really see variables and their
changes in the debugger. Very nice :)

1 files changed, 111 insertions, 93 deletions

diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 6085971..2c444df 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,117 +1,135 @@
-#include <iostream>
+#include <cstdio>
+#include <cstdlib>
 #include <vector>
 #include <algorithm>
-#include <queue>
+#include <iostream>
 //#include <gtest/gtest.h>
 
-using std::vector;
 using std::cin;
 using std::cout;
-using std::pair;
-using std::make_pair;
-
-class JobQueue {
-private:
+using std::endl;
+using std::max;
+using std::vector;
 
-	vector<int> assigned_workers_;
-	vector<long long> start_times_;
+struct Table {
+	int numberOfRows;
+	int setID;
 
-	void WriteResponse() const {
-		for (size_t i = 0; i < jobs.size(); ++i) {
-			cout << assigned_workers_[i] << " " << start_times_[i] << "\n";
-		}
+	Table(int numberOfRows, int setID) :
+			numberOfRows(numberOfRows), setID(setID) {
 	}
+};
 
-	void ReadData() {
-		int m;
-		cin >> num_workers >> m;
-		jobs.resize(m);
-		for (int i = 0; i < m; ++i)
-			cin >> jobs[i];
-	}
+int maximumNumberOfRows = -1;
+vector<int> parent;
+vector<int> rank;
+vector<Table> tables;
 
-	void AssignJobs() {
-		// Naive algorithm
-		assigned_workers_.resize(jobs.size());
-		start_times_.resize(jobs.size());
-		vector<long long> next_free_time(num_workers, 0);
-		for (size_t i = 0; i < jobs.size(); ++i) {
-			int duration = jobs[i];
-			int next_worker = 0;
-			for (int j = 0; j < num_workers; ++j) {
-				if (next_free_time[j] < next_free_time[next_worker])
-					next_worker = j;
-			}
-			assigned_workers_[i] = next_worker;
-			start_times_[i] = next_free_time[next_worker];
-			next_free_time[next_worker] += duration;
-		}
-	}
+int find(int i) {
+	if (i != parent[i])
+		parent[i] = find(parent[i]);
+	return parent[i];
+}
 
-public:
-	int num_workers;
-	vector<int> jobs;
-	void Solve() {
-		ReadData();
-		AssignJobsImproved();
-		WriteResponse();
+void unite(int destination, int source) {
+	int destination_id = find(destination);
+	int source_id = find(source);
+	if (destination_id == source_id)
+		return;
+	if (rank[destination_id] > rank[source_id])
+		parent[source_id] = destination_id;
+	else {
+		parent[destination_id] = source_id;
+		if (rank[destination_id] == rank[source_id])
+			rank[source_id] = rank[source_id] + 1;
 	}
-	const vector<int>& assigned_workers() const {
-		return assigned_workers_;
-	}
-	const vector<long long>& start_times() const {
-		return start_times_;
+}
+
+void merge(int destination, int source) {
+	int d = find(destination);
+	int s = find(source);
+	Table* realDestination = &tables[d];
+	Table* realSource = &tables[s];
+	if (d == s) {
+		return;
 	}
+	maximumNumberOfRows = max(maximumNumberOfRows,
+			tables[realDestination->setID].numberOfRows + tables[realSource->setID].numberOfRows);
+	realDestination->numberOfRows = tables[realDestination->setID].numberOfRows
+			+ tables[realSource->setID].numberOfRows;
+	realSource->numberOfRows = 0;
+	realSource->setID = d;
+	realDestination->setID = d;
+	unite(destination, source);
+}
 
-	void AssignJobsImproved() {
-		std::priority_queue<pair<long, int>> pq;
-		assigned_workers_.resize(jobs.size());
-		start_times_.resize(jobs.size());
+int main() {
+	int n, m;
+	cin >> n >> m;
 
-		for (size_t i = 0; i < num_workers; ++i) {
-			pq.push(make_pair(0, -i));
-		}
+	parent.resize(n);
+	rank.resize(n);
+//	tables.resize(n);
+	for (int i = 0; i < n; i++) {
+		int numberOfRows;
+		cin >> numberOfRows;
+		tables.push_back(Table(numberOfRows, i));
+//		tables[i] = Table(numberOfRows, i);
+		parent[i] = i;
+		rank[i] = 0;
+		maximumNumberOfRows = max(maximumNumberOfRows, numberOfRows);
+	}
+
+	for (int i = 0; i < m; i++) {
+		int destination, source;
+		cin >> destination >> source;
+		--destination;
+		--source;
 
-		for (size_t i = 0; i < jobs.size(); ++i) {
-			pair<long, int> l = pq.top();
-			pq.pop();
-			start_times_[i] = -l.first;
-			assigned_workers_[i] = -l.second;
-			pq.push(make_pair(l.first - jobs[i], l.second));
-		}
+		merge(destination, source);
+		cout << maximumNumberOfRows << endl;
 	}
-};
 
-int main() {
-  std::ios_base::sync_with_stdio(false);
-  JobQueue job_queue;
-  job_queue.Solve();
-  return 0;
+	return 0;
 }
 
-//TEST(ParralelProcessing, t) {
-//	vector<int> jobs = { 1, 2, 3, 4, 5 };
-//	vector<int> expected_assigned_workers = { 0, 1, 0, 1, 0 };
-//	vector<long long> expected_start_times = { 0, 0, 1, 2, 4 };
-//	JobQueue jq;
-//	jq.num_workers = 2;
-//	jq.jobs = jobs;
-//	jq.AssignJobsImproved();
-//	ASSERT_EQ(expected_assigned_workers, jq.assigned_workers());
-//	ASSERT_EQ(expected_start_times, jq.start_times());
+//TEST(MergingTables, t) {
+//    maximumNumberOfRows = 1;
+//    rank = {0, 0, 0, 0, 0};
+//    parent = {0, 1, 2, 3, 4};
+//    tables = {Table(1, 0), Table(1, 1), Table(1, 2), Table(1, 3), Table(1, 4)};
+//
+//    merge(2, 4);
+//    ASSERT_EQ(2, maximumNumberOfRows);
+//
+//    merge(1, 3);
+//    ASSERT_EQ(2, maximumNumberOfRows);
+//
+//    merge(0, 3);
+//    ASSERT_EQ(3, maximumNumberOfRows);
+//
+//    merge(4, 3);
+//    ASSERT_EQ(5, maximumNumberOfRows);
+//
+//    merge(4, 2);
+//    ASSERT_EQ(5, maximumNumberOfRows);
 //}
 //
-//TEST(ParralelProcessing, t1) {
-//	vector<int> jobs = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
-//			1, 1 };
-//	vector<int> expected_assigned_workers = { 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2,
-//			3, 0, 1, 2, 3, 0, 1, 2, 3 };
-//	vector<long long> expected_start_times = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2,
-//			2, 3, 3, 3, 3, 4, 4, 4, 4 };
-//	JobQueue jq;
-//	jq.num_workers = 4;
-//	jq.jobs = jobs;
-//	jq.AssignJobsImproved();
-//	ASSERT_EQ(expected_assigned_workers, jq.assigned_workers());
-//	ASSERT_EQ(expected_start_times, jq.start_times());
+//TEST(MergingTables, t1) {
+//    maximumNumberOfRows = 10;
+//    rank = {0, 0, 0, 0, 0, 0};
+//    parent = {0, 1, 2, 3, 4, 5};
+//    tables = {Table(10, 0), Table(0, 1), Table(5, 2), Table(0, 3), Table(3, 4), Table(3, 5)};
+//
+//    merge(5, 5);
+//    ASSERT_EQ(10, maximumNumberOfRows);
+//
+//    merge(5, 4);
+//    ASSERT_EQ(10, maximumNumberOfRows);
+//
+//    merge(4, 3);
+//    ASSERT_EQ(10, maximumNumberOfRows);
+//
+//    merge(3, 2);
+//    ASSERT_EQ(11, maximumNumberOfRows);
 //}