For any incoming packet, the router first searches the routing table to find the network ids that are the prefix of the packet’s destination IP address.  If there are multiple such network ids, the one that is longest will be chosen. Then the router uses the corresponding output port of the chosen network id to forward the packet to the next hop.  For example, in the above routing table, there are two network ids (i.e. “000” and “0001”) that are both the prefix for IP address “00011111000011110000111100001111”. Since “0001” is the longest prefix, it is chosen and a packet carrying this IP address of “00011111000011110000111100001111” will be forwarded to port 0 instead of port 3.  

In this assignment, we build a binary prefix tree (as shown in Figure 1) to facilitate the quick search for realizing the above router functionality.  The binary prefix tree stores the routing table information and has the following properties:

(1) It is a binary tree. Thus, each node has at most two children.  Besides pointers to its children, each node has a data field called rtentry that can be used to store the information of a routing entry, including the network id and the port number.

(2) For any node, its parent node’s network id is a prefix of this node’s network id. This means that a node’s network id is also the prefix of all its descendants’ network ids. If a node is associated with a network id that is an empty string, this empty string is the prefix of any IP address or network id. 

(3) For any node with network id of s, if it has a left child, its left child must contain a network id starting with s0. (The actual network id of the left child can be longer than s0) Similarly, if the node has a right child, the right child must contain a prefix string starting with s1.

(4) To ensure the above three properties, not all nodes are associated with a valid routing entry.  For example, the red node in the prefix tree example in Figure 1 does not hold a valid routing entry.  For such a node, the corresponding port number is set to -1 to indicate it is an invalid entry.  

(5) The tree needs to be compact. This means that you cannot create any other tree structure that satisfies properties (1), (2) and (3) and yet has a smaller number of nodes. This means that the number of those red nodes holding invalid routing entry should be kept at minimum.

Part 1.  Implement and test a TreeNode class that contains four fields: netId, port, a leftChildPtr, and a rightChildPtr. The netId is of type std::string, and the output port is an integer.  You may assume that the netId is simply formed by a sequence of ‘0’ and ‘1’ characters. Provide interface methods for this class, following the descriptions that are provided in the starter code.

Part 2.  Implement and test a PrefixTree ADT, which builds a binary prefix tree. The definitions of all methods are given in the starter code.  You can add additional helper functions if you want.  However, only the methods defined in the starter code will be directly called by the autograder in its test.  Your code must use “smart pointers” instead of “basic pointers”.  

One parameterized constructor method of PrefixTree (i.e. prefixTree(std::string filename);) will accept a file name as its input. This constructor will read the content of the text file and construct a prefix tree accordingly.  The text file includes the routing table content. Each line of the text is of the format “network id:port number\n”. A sample file named “routing_table.txt” is given in the starter code package. Your code should build a prefix tree of Figure 1’s shape based on this routing_table.txt file.  You may need to copy this file to your build directory for your program to read it.

You may assume that the input text file is properly formatted, and contains no duplicate entries.

The postOrderTravese(visit) method of PrefixTree performs a postorder traversal of the prefix tree and calls the function visit()once for each node.  Function visit() is a client defined function that performs an operation on or with the data in each visited node.   postOrderTravese returns a string.

Part 3. Implement and test two client functions visitNode() and visitRoutingEntry() to pass to the postOrderTravese() method of the prefixTree class. When visitNode() is passed,  the returned string from postOrderTravese() includes the rtEntry fields of all nodes.   The returned string must be in the same format as the routing_table.txt input file, where each line in the string is of the format “network id:port number\n”.  When visitRoutingEntry() function is passed to   postOrderTravese(), the returned string of postOrderTravese() contains all valid routing entries (i.e. routing entries with port number >=0).  The returned string must be in the same format as the input file, where each line in the string is of the format “network id:port number\n”. For example, for the tree in Figure 1, if we pass visitRoutingEntry() function to postOrderTravese(), the string that postOrderTravese() returns will  be   “0001:0\n000:3\n0100:1\n10:2\n:4\n”. If we pass visitNode() function to postOrderTravese(), the string that postOrderTravese() returns will  be    “0001:0\n000:3\n0100:1\n0:-1\n10:2\n:4\n”

Starter code. The files that you will use here are similar in format to previous assignments.  

CMakeLists.txt:  Do not change this file, and do not submit it. This file is used by CMake to create a VS project named hw5_test. It creates other VS projects also, but hw5_test is the primary one that you will work with to develop code.

catch.hpp: Do not change this file, and do not submit it.  It is needed by the Catch utility. (The autograder appears to be sensitive to particular versions of this file.)

treeNode.h  and treeNode.cpp: These files will contain your implementation of the treeNode class.

prefixTree.h  and prefixTree.cpp: These files will contain your implementation of the prefixTree class.

hw5_datarecord.h  and hw5_datarecord.cpp: These files will contain your client functions  visitNode() and visitRoutingEntry()  that perform the data  processing of each node.

hw5_test.cpp: You must create tests for the Catch utility in this file. You must submit this file to the autograder. If you develop good, extensive tests of your C++ code here, you will find and fix bugs before submitting to the autograder.

hw5_main.cpp: This file is for your (optional) use only. Do not submit this file. It is here in case you would like to create your own main() function to experiment with your other code.

routing_table.txt: This file is for your (optional) use only. Do not submit this file. It is here to help you to make sure that your prefix tree is properly constructed. You prefix tree constructed based on this file should be the same as Figure 1.  You may need to copy this file to your build directory for your program to read it.

You should not change any public methods’ definition in the starter code.  You may make changes to the definition of the protected methods in *.h or even completely remove them. By allowing you to submit them, you are being given some flexibility in how you develop your code.

Additional requirements: At the beginning of all your *.h and *.cpp files , place comment blocks similar to the following:

////////////////////////////////////////////////////////

// ECE 2574, Homework 5, Jane Doe ß your name here

//

// File name:   hw5_test.cpp ß File name here

// Description: (Describe the purpose of this file)

// Date:        5/8/2019  ß completion date here

//

Add appropriate comments throughout all of the code that you modify or create.

Online testing:  We will continue to use the INGInious autograding system to determine the major portion of your grade for this assignment. To use the autograder, place the following C++ source files into a single zip file:

treeNode.h, treeNode.cpp, prefixTree.h, prefixTree.cpp, hw5_datarecord.h,  hw5_datarecord.cpp, hw5_test.cpp

The zip archive must contain these files only, without any directories. A suggested file name for the zip archive is hw5_name.zip, where name is your family name.  

Submit your zip file to the INGInious autograder at https://grader.ece.vt.edu. It will attempt to compile and run the tests that you have formulated in hw5_test.cpp, and the autograder will also run some “instructor” tests. A grade will be reported to you, proportional to the number of tests that have executed correctly. You can submit to the autograder as many times as you like, but it will limit you to 4 submissions every hour. This limit is to discourage people from using it as their only compiler and overloading the machine. Your grade will be based on your last submission to the autograder.

Submission to Canvas:  After you are satisfied with your code based on your autograded results and addressing the requirements, upload the same zip file (as described above) to Canvas at the HW5 assignment link. You do not need to submit any other files or directories.

Be careful to verify that you have uploaded the correct files to Canvas. After you have uploaded your zip file, it is suggested that you also download it from Canvas and verify that it is correct.

Grading:  There are 100 points allocated to this assignment, and most of the grade will be determined by the autograder.

· Correctly submitting the required files to INGInious and to Canvas: 5 points

· Your tests compile: 0 points

· Your tests pass: 15 points (proportional)

· Instructor's tests compile with your code: 0 points

· Instructor's tests pass: 50 points (proportional)

· No memory leaks (checked by autograder using valgrind): 10 points 

· Good test coverage (checked by autograder using lcov): 10  points

· Good coding style (tentative grade assigned by autograder; TA or instructor has

the option of changing this part of the grade later): 10 points

Please note that your most recent submission to INGInious determines the autograded portion of your grade.