Build heap done!

It turned out it's more challenging converting Java code to C++ this
time. The for loop, commented in the code, was tricky! The while loop
was better anyway. It was good practice of doing debugging with gdb.
Once again, rewarding experience!

1 files changed, 97 insertions, 120 deletions

diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index e76d5be..f3d46be 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,141 +1,118 @@
 #include <iostream>
-#include <queue>
 #include <vector>
+#include <algorithm>
 //#include <gtest/gtest.h>
 
-struct Request {
-	Request(int arrival_time, int process_time) :
-			arrival_time(arrival_time), process_time(process_time) {
-	}
+using std::vector;
+using std::cin;
+using std::cout;
+using std::swap;
+using std::pair;
+using std::make_pair;
 
-	int arrival_time;
-	int process_time;
-};
+class HeapBuilder {
+private:
+	vector<int> data_;
+//	vector<pair<int, int> > swaps_;
+
+//	void GenerateSwaps() {
+//		swaps_.clear();
+//		// The following naive implementation just sorts
+//		// the given sequence using selection sort algorithm
+//		// and saves the resulting sequence of swaps.
+//		// This turns the given array into a heap,
+//		// but in the worst case gives a quadratic number of swaps.
+//		//
+//		for (size_t i = 0; i < data_.size(); ++i)
+//			for (size_t j = i + 1; j < data_.size(); ++j) {
+//				if (data_[i] > data_[j]) {
+//					swap(data_[i], data_[j]);
+//					swaps_.push_back(make_pair(i, j));
+//				}
+//			}
+//	}
 
-struct Response {
-	Response(bool dropped, int start_time) :
-			dropped(dropped), start_time(start_time) {
+public:
+	vector<pair<int, int>> swaps;
+	void WriteResponse() const {
+		cout << swaps.size() << "\n";
+		for (size_t i = 0; i < swaps.size(); ++i) {
+			cout << swaps[i].first << " " << swaps[i].second << "\n";
+		}
 	}
 
-	bool dropped;
-	int start_time;
-};
-
-class Buffer {
-public:
-	Buffer(int capacity) :
-			capacity_(capacity), finish_time_() {
+	void ReadData() {
+		int n;
+		cin >> n;
+		data_.resize(n);
+		for (int i = 0; i < n; ++i)
+			cin >> data_[i];
 	}
 
-	Response Process(const Request &request) {
-		// write your code here
-		if (runningTimeCounter_ < request.arrival_time) {
-			if (finish_time_.size() == 0)
-				runningTimeCounter_ = request.arrival_time;
-			else if (finish_time_.back() < request.arrival_time)
-				runningTimeCounter_ = request.arrival_time;
+	// Please note the for loop below. Initially I copied the for loop from my
+	// Java code, but it doesn't work in C++. Changing it to while loop worked!
+	// It was better with the while loop anyway, much clearer to me.
+	void UpdateSwaps(vector<int> &data) {
+		int j = (data.size() - 1) / 2;
+		while (j >= 0) {
+			siftDown(j, data);
+			j = j - 1;
 		}
-		while (finish_time_.size() > 0) {
-			int j = finish_time_.front();
-			if (j <= request.arrival_time)
-				finish_time_.pop();
-			else
-				break;
-		}
-
-		if (finish_time_.size() >= capacity_) {
-			return Response(true, -1);
+//		for (size_t i = j; i >= 0; i--) {
+//			siftDown(i, data);
+//		}
+	}
+	void siftDown(int i, vector<int> &data) {
+		int maxIndex = i;
+		size_t l = 2 * i + 1;
+		if (l < data.size() && data[l] < data[maxIndex])
+			maxIndex = l;
+		size_t r = 2 * i + 2;
+		if (r < data.size() && data[r] < data[maxIndex])
+			maxIndex = r;
+		if (i != maxIndex) {
+			swap(data[i], data[maxIndex]);
+			swaps.push_back(make_pair(i, maxIndex));
+			siftDown(maxIndex, data);
 		}
-		Response response = Response(false, runningTimeCounter_);
-		runningTimeCounter_ = runningTimeCounter_ + request.process_time;
-		if (finish_time_.size() > 0)
-			finish_time_.push(finish_time_.back() + request.process_time);
-		else
-			finish_time_.push(runningTimeCounter_);
-		return response;
-
 	}
-private:
-	size_t capacity_;
-	std::queue<int> finish_time_;
-	int runningTimeCounter_ = 0;
-};
-
-std::vector<Request> ReadRequests() {
-	std::vector<Request> requests;
-	int count;
-	std::cin >> count;
-	for (int i = 0; i < count; ++i) {
-		int arrival_time, process_time;
-		std::cin >> arrival_time >> process_time;
-		requests.push_back(Request(arrival_time, process_time));
+	void Solve() {
+		ReadData();
+//		GenerateSwaps();
+		UpdateSwaps(data_);
+		WriteResponse();
 	}
-	return requests;
-}
-
-std::vector<Response> ProcessRequests(const std::vector<Request> &requests,
-		Buffer *buffer) {
-	std::vector<Response> responses;
-	for (size_t i = 0; i < requests.size(); ++i)
-		responses.push_back(buffer->Process(requests[i]));
-	return responses;
-}
+};
 
-void PrintResponses(const std::vector<Response> &responses) {
-	for (size_t i = 0; i < responses.size(); ++i)
-		std::cout << (responses[i].dropped ? -1 : responses[i].start_time)
-				<< std::endl;
+int main() {
+//	vector<int> data = { 5, 4, 3, 2, 1 };
+//	HeapBuilder heap_builder;
+//	heap_builder.UpdateSwaps(data);
+//	heap_builder.WriteResponse();
+
+	std::ios_base::sync_with_stdio(false);
+	HeapBuilder heap_builder;
+	heap_builder.Solve();
+	return 0;
 }
 
-//TEST(ProcessRequests, t) {
-//    int bufferMaxSize = 1;
-//    Buffer buf = Buffer(bufferMaxSize);
-//    std::vector<Request> requests;
-//    std::vector<Response> responses = ProcessRequests(requests, &buf);
-//    ASSERT_EQ(0, responses.size());
-//}
-//
-//TEST(ProcessRequests, t1) {
-//    int bufferMaxSize = 1;
-//    Buffer buf = Buffer(bufferMaxSize);
-//    std::vector<Request> requests = {Request(0, 1)};
-//    std::vector<Response> responses = ProcessRequests(requests, &buf);
-//    ASSERT_EQ(1, responses.size());
-//    ASSERT_EQ(false, responses[0].dropped);
+//TEST(BuildHeap, t) {
+//	vector<int> data = {5, 4, 3, 2, 1};
+//	HeapBuilder heap_builder;
+//	heap_builder.UpdateSwaps(data);
+//    ASSERT_EQ(3, heap_builder.swaps.size());
+//    ASSERT_EQ(1, heap_builder.swaps[0].first);
+//    ASSERT_EQ(4, heap_builder.swaps[0].second);
+//    ASSERT_EQ(0, heap_builder.swaps[1].first);
+//    ASSERT_EQ(1, heap_builder.swaps[1].second);
+//    ASSERT_EQ(1, heap_builder.swaps[2].first);
+//    ASSERT_EQ(3, heap_builder.swaps[2].second);
 //}
 //
-//TEST(ProcessRequests, t2) {
-//    int bufferMaxSize = 1;
-//    Buffer buf = Buffer(bufferMaxSize);
-//    std::vector<Request> requests = {Request(0, 1), Request(0, 1)};
-//    std::vector<Response> responses = ProcessRequests(requests, &buf);
-//    ASSERT_EQ(2, responses.size());
-//    ASSERT_EQ(false, responses[0].dropped);
-//    ASSERT_EQ(0, responses[0].start_time);
-//    ASSERT_EQ(true, responses[1].dropped);
+//TEST(BuildHeap, t1) {
+//	vector<int> data = {1, 2, 3, 4, 5};
+//	HeapBuilder heap_builder;
+//	heap_builder.UpdateSwaps(data);
+//    ASSERT_EQ(0, heap_builder.swaps.size());
 //}
 //
-//TEST(ProcessRequests, t3) {
-//    int bufferMaxSize = 1;
-//    Buffer buf = Buffer(bufferMaxSize);
-//    std::vector<Request> requests = {Request(0, 1), Request(1, 1)};
-//    std::vector<Response> responses = ProcessRequests(requests, &buf);
-//    ASSERT_EQ(2, responses.size());
-//    ASSERT_EQ(false, responses[0].dropped);
-//    ASSERT_EQ(0, responses[0].start_time);
-//    ASSERT_EQ(false, responses[1].dropped);
-//    ASSERT_EQ(1, responses[1].start_time);
-//}
-
-int main() {
-	int size;
-	std::cin >> size;
-	std::vector<Request> requests = ReadRequests();
-
-	Buffer buffer(size);
-	std::vector<Response> responses = ProcessRequests(requests, &buffer);
-
-	PrintResponses(responses);
-	return 0;
-}
-