Network packet done.

Fun exercise. Good comparison and contrast with Java.

1 files changed, 114 insertions, 74 deletions

diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 91fdf86..e76d5be 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,101 +1,141 @@
 #include <iostream>
 #include <queue>
-#include <algorithm>
 #include <vector>
 //#include <gtest/gtest.h>
 
-using std::vector;
-using std::queue;
-
-class Node;
+struct Request {
+	Request(int arrival_time, int process_time) :
+			arrival_time(arrival_time), process_time(process_time) {
+	}
 
-class Node {
-public:
-	int key;
-	Node *parent;
-	vector<Node *> children;
+	int arrival_time;
+	int process_time;
+};
 
-	Node() {
-		this->parent = NULL;
+struct Response {
+	Response(bool dropped, int start_time) :
+			dropped(dropped), start_time(start_time) {
 	}
 
-	void setParent(Node *theParent) {
-		parent = theParent;
-		parent->children.push_back(this);
-	}
+	bool dropped;
+	int start_time;
 };
 
-int treeLevelCounter(vector<Node> &nodes, int rootIndex) {
-	int levelCounter = 1;
-	queue<Node *> q;
-	int popCount = 0;
-	int childrenCount = nodes[rootIndex].children.size();
-	int grandChildrenCount = 0;
-	for (int i = 0; i < childrenCount; i++) {
-		q.push(nodes[rootIndex].children[i]);
+class Buffer {
+public:
+	Buffer(int capacity) :
+			capacity_(capacity), finish_time_() {
 	}
-	while (!q.empty()) {
-		if (popCount < childrenCount) {
-			Node *n = q.front();
-			q.pop();
-			int i = n->children.size();
-			if (i != 0) {
-				for (int j = 0; j < i; j++) {
-					q.push(n->children[j]);
-				}
-			}
-			grandChildrenCount = grandChildrenCount + i;
-			popCount = popCount + 1;
-		} else {
-			popCount = 0;
-			childrenCount = grandChildrenCount;
-			grandChildrenCount = 0;
-			levelCounter = levelCounter + 1;
+
+	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;
 		}
-	}
-	return levelCounter + 1;
-}
-int getHeight(vector<int> &a) {
-	vector<Node> nodes;
-	nodes.resize(a.size());
-	int rootIndex = 0;
-	for (size_t i = 0; i < a.size(); i++) {
-		int parentIndex = a[i];
-		if (parentIndex == -1) {
-			rootIndex = i;
-		} else {
-			nodes[i].setParent(&nodes[parentIndex]);
+		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);
+		}
+		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;
+
 	}
-	return treeLevelCounter(nodes, rootIndex);
+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));
+	}
+	return requests;
 }
 
-//TEST(GetTreeHeight, t1) {
-//    vector<int> a = {4, -1, 4, 1, 1};
-//    ASSERT_EQ(3, getHeight(a));
+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;
+}
+
+//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(GetTreeHeight, t2) {
-//    vector<int> a = {-1, 0, 4, 0, 3};
-//    ASSERT_EQ(4, getHeight(a));
+//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(GetTreeHeight, t3) {
-//    vector<int> a = {9, 7, 5, 5, 2, 9, 9, 9, 2, -1};
-//    ASSERT_EQ(4, getHeight(a));
+//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(GetTreeHeight, t4) {
-//    vector<int> a = {8, 8, 5, 6, 7, 3, 1, 6, -1, 5};
-//    ASSERT_EQ(6, getHeight(a));
+//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() {
-	size_t an;
-	std::cin >> an;
-	vector<int> a(an);
-	for (size_t i = 0; i < an; i++) {
-		std::cin >> a[i];
-	}
-	std::cout << getHeight(a) << std::endl;
+	int size;
+	std::cin >> size;
+	std::vector<Request> requests = ReadRequests();
+
+	Buffer buffer(size);
+	std::vector<Response> responses = ProcessRequests(requests, &buffer);
+
+	PrintResponses(responses);
+	return 0;
 }
+