From 83292a326000d1c7c5695f6cb8b8575081221cda Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Tue, 29 Jan 2019 11:49:03 -0600 Subject: Network packet processing done! Oh man, I spent so much time on this, on and off for more than 16 hours. But it was worth it in the end! Initially I didn't even noticed that there is a "what to do" part in exercise file, so I started coding following my own intuition, which wasn't too bad. I felt like I was going places and passed a few tests but failed one or two test cases. That's when things started getting difficult. I tried thinking, paper/pencil, sleeping on it, and reading forums (coursera, edx has no discussion on this when I worked on it). I then realized the "what to do" part in exercise and started following it. I should have stashed my code based on my own intuition, but I didn't. I'm learning, after all. Then my code got really messy. I added a lot of if statements and temp variables to get by, but it consistently fails on grader test case 20. That test case input is from a file, so far I haven't learned proper way of reading file as input in junit, so I started simplify my code hoping that I can pass. In the end my code simplification did work and passed the grader, but I really should learn how to use file input in JUnit, or how to feed input file. Eclipse makes that easy, but not IDEA, at least not the version of 2018.2. 2018.3 supposedly has it, but I don't know how to upgrade it safely on my Manjaro yet. Woohoo, fun stuff! --- src/main/NetworkPacket.java | 83 +++++++++++++++++++----------- src/test/NetworkPacketTest.java | 109 +++++++++++++++++++++++++++++++++++++++- 2 files changed, 163 insertions(+), 29 deletions(-) diff --git a/src/main/NetworkPacket.java b/src/main/NetworkPacket.java index 805dcf5..7aeea88 100644 --- a/src/main/NetworkPacket.java +++ b/src/main/NetworkPacket.java @@ -1,49 +1,76 @@ import java.io.IOException; import java.util.ArrayList; +import java.util.Deque; +import java.util.LinkedList; import java.util.Scanner; public class NetworkPacket { - public static class Request { - public int arrivalTime; - public int processTime; + static class Request { + int arrivalTime; + int processTime; - public Request(int arrivalTime, int processTime) { + Request(int arrivalTime, int processTime) { this.arrivalTime = arrivalTime; this.processTime = processTime; } } - public static class Response { - public boolean dropped; - public int startTime; + static class Response { + boolean dropped; + int startTime; - public Response(boolean dropped, int startTime) { + Response(boolean dropped, int startTime) { this.dropped = dropped; this.startTime = startTime; } } - public static class Buffer { - private int size; - private ArrayList finishTime = new ArrayList(); + static class Buffer { + private int capacity; + private Deque finishTime; - public Buffer(int size) { - this.size = size; + // My addition to the starter file + private int runningTimeCounter = 0; + // End of my addition to the starter file + + Buffer(int capacity) { + this.capacity = capacity; + this.finishTime = new LinkedList<>(); } - public Response processRequests(Request request) { - // write your code here - if (this.size == 0) - return new Response(false,-1); - else { + + Response processRequest(Request request) { + if (runningTimeCounter < request.arrivalTime) if (finishTime.size() == 0) + runningTimeCounter = request.arrivalTime; + else if (finishTime.getLast() < request.arrivalTime) + runningTimeCounter = request.arrivalTime; + + while (finishTime.size() > 0) { + int j = finishTime.getFirst(); + if (j <= request.arrivalTime) + finishTime.pop(); + else + break; } + + if (finishTime.size() >= capacity) { + return new Response(true, -1); + } + Response response = new Response(false, runningTimeCounter); + runningTimeCounter = runningTimeCounter + request.processTime; + if (finishTime.size() > 0) + finishTime.addLast(finishTime.getLast() + request.processTime); + else + finishTime.addLast(runningTimeCounter); + return response; } } - private static ArrayList ReadQueries(Scanner scanner) throws IOException { + + private static ArrayList ReadQueries(Scanner scanner) { int requests_count = scanner.nextInt(); - ArrayList requests = new ArrayList(); + ArrayList requests = new ArrayList<>(); for (int i = 0; i < requests_count; ++i) { int arrival_time = scanner.nextInt(); int process_time = scanner.nextInt(); @@ -52,16 +79,16 @@ public class NetworkPacket { return requests; } - public static ArrayList processRequests(ArrayList requests, Buffer buf) { + static ArrayList processRequests(ArrayList requests, Buffer buf) { ArrayList responses = new ArrayList<>(); - for (int i = 0; i < requests.size(); i++) { - responses.add(buf.processRequests(requests.get(i))); + for (Request request : requests) { + responses.add(buf.processRequest(request)); } return responses; } + private static void PrintResponses(ArrayList responses) { - for (int i = 0; i < responses.size(); ++i) { - Response response = responses.get(i); + for (Response response : responses) { if (response.dropped) { System.out.println(-1); } else { @@ -70,11 +97,11 @@ public class NetworkPacket { } } - public static void main(String[] args) throws IOException { + public static void main(String[] args) { Scanner scanner = new Scanner(System.in); - int buffer_max_size = scanner.nextInt(); - Buffer buffer = new Buffer(buffer_max_size); + int bufferMaxSize = scanner.nextInt(); + Buffer buffer = new Buffer(bufferMaxSize); ArrayList requests = ReadQueries(scanner); ArrayList responses = processRequests(requests, buffer); diff --git a/src/test/NetworkPacketTest.java b/src/test/NetworkPacketTest.java index fca3d60..aecd968 100644 --- a/src/test/NetworkPacketTest.java +++ b/src/test/NetworkPacketTest.java @@ -6,7 +6,7 @@ import static org.junit.jupiter.api.Assertions.assertEquals; import static org.junit.jupiter.api.Assertions.assertFalse; import static org.junit.jupiter.api.Assertions.assertTrue; -public class NetworkPacketTest { +class NetworkPacketTest { @Test void test() { int bufferMaxSize = 1; @@ -56,4 +56,111 @@ public class NetworkPacketTest { assertFalse(responses.get(1).dropped); assertEquals(1, responses.get(1).startTime); } + + @Test + void test4() { + int bufferMaxSize = 1; + NetworkPacket.Buffer buf = new NetworkPacket.Buffer(bufferMaxSize); + ArrayList requests = new ArrayList<>(); + requests.add(new NetworkPacket.Request(1, 0)); + ArrayList responses = NetworkPacket.processRequests(requests, buf); + assertEquals(1, responses.size()); + assertEquals(1, responses.get(0).startTime); + } + + @Test + void test5() { + int bufferMaxSize = 1; + NetworkPacket.Buffer buf = new NetworkPacket.Buffer(bufferMaxSize); + ArrayList requests = new ArrayList<>(); + requests.add(new NetworkPacket.Request(0, 1)); + requests.add(new NetworkPacket.Request(0, 0)); + ArrayList responses = NetworkPacket.processRequests(requests, buf); + assertEquals(2, responses.size()); + assertEquals(0, responses.get(0).startTime); + assertEquals(-1, responses.get(1).startTime); + } + + @Test + void test6() { + int bufferMaxSize = 2; + NetworkPacket.Buffer buf = new NetworkPacket.Buffer(bufferMaxSize); + ArrayList requests = new ArrayList<>(); + requests.add(new NetworkPacket.Request(0, 1)); + requests.add(new NetworkPacket.Request(0, 1)); + ArrayList responses = NetworkPacket.processRequests(requests, buf); + assertEquals(2, responses.size()); + assertEquals(0, responses.get(0).startTime); + assertEquals(1, responses.get(1).startTime); + } + + @Test + void test7() { + int bufferMaxSize = 2; + NetworkPacket.Buffer buf = new NetworkPacket.Buffer(bufferMaxSize); + ArrayList requests = new ArrayList<>(); + requests.add(new NetworkPacket.Request(0, 1)); + requests.add(new NetworkPacket.Request(0, 1)); + requests.add(new NetworkPacket.Request(0, 1)); + ArrayList responses = NetworkPacket.processRequests(requests, buf); + assertEquals(3, responses.size()); + assertEquals(0, responses.get(0).startTime); + assertEquals(1, responses.get(1).startTime); + assertEquals(-1, responses.get(2).startTime); + } + + @Test + void test8() { + int bufferMaxSize = 3; + NetworkPacket.Buffer buf = new NetworkPacket.Buffer(bufferMaxSize); + ArrayList requests = new ArrayList<>(); + requests.add(new NetworkPacket.Request(0, 2)); + requests.add(new NetworkPacket.Request(1, 2)); + requests.add(new NetworkPacket.Request(2, 2)); + requests.add(new NetworkPacket.Request(3, 2)); + requests.add(new NetworkPacket.Request(4, 2)); + requests.add(new NetworkPacket.Request(5, 2)); + ArrayList responses = NetworkPacket.processRequests(requests, buf); + assertEquals(6, responses.size()); + assertEquals(0, responses.get(0).startTime); + assertEquals(2, responses.get(1).startTime); + assertEquals(4, responses.get(2).startTime); + assertEquals(6, responses.get(3).startTime); + assertEquals(8, responses.get(4).startTime); + assertEquals(-1, responses.get(5).startTime); + } + + @Test + void test9() { + int bufferMaxSize = 1; + NetworkPacket.Buffer buf = new NetworkPacket.Buffer(bufferMaxSize); + ArrayList requests = new ArrayList<>(); + requests.add(new NetworkPacket.Request(0, 1)); + requests.add(new NetworkPacket.Request(1, 1)); + requests.add(new NetworkPacket.Request(2, 1)); + requests.add(new NetworkPacket.Request(3, 1)); + requests.add(new NetworkPacket.Request(3, 1)); + ArrayList responses = NetworkPacket.processRequests(requests, buf); + assertEquals(5, responses.size()); + assertEquals(0, responses.get(0).startTime); + assertEquals(1, responses.get(1).startTime); + assertEquals(2, responses.get(2).startTime); + assertEquals(3, responses.get(3).startTime); + assertEquals(-1, responses.get(4).startTime); + } + + @Test + void test10() { + int bufferMaxSize = 1; + NetworkPacket.Buffer buf = new NetworkPacket.Buffer(bufferMaxSize); + ArrayList requests = new ArrayList<>(); + requests.add(new NetworkPacket.Request(0, 1)); + requests.add(new NetworkPacket.Request(2, 1)); + ArrayList responses = NetworkPacket.processRequests(requests, buf); + assertEquals(2, responses.size()); + assertFalse(responses.get(0).dropped); + assertEquals(0, responses.get(0).startTime); + assertFalse(responses.get(1).dropped); + assertEquals(2, responses.get(1).startTime); + } } -- cgit v1.2.3