From fc4792aca6cb9a96e7ebce39e0416692bbe526ed Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Tue, 5 Mar 2019 14:49:08 -0600 Subject: 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 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 :)--- Sources/DataStructure.cpp | 204 +++++++++++++++++++++++++--------------------- 1 file 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 +#include +#include #include #include -#include +#include //#include -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 assigned_workers_; - vector 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 parent; +vector rank; +vector
tables; - void AssignJobs() { - // Naive algorithm - assigned_workers_.resize(jobs.size()); - start_times_.resize(jobs.size()); - vector 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 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& assigned_workers() const { - return assigned_workers_; - } - const vector& 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> 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 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 jobs = { 1, 2, 3, 4, 5 }; -// vector expected_assigned_workers = { 0, 1, 0, 1, 0 }; -// vector 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 jobs = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -// 1, 1 }; -// vector expected_assigned_workers = { 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, -// 3, 0, 1, 2, 3, 0, 1, 2, 3 }; -// vector 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); //} -- cgit v1.2.3