Instructions. Note the following points carefully:
1. For your data structure to be correct, we only require that the return values and printed output of all of the following function calls are correct.
2. You can reuse code submitted by you as part of Programming Evaluation 1.
3. Your data structure should support: (a) insert in worst-case O(log2 (n)) time, (b) remove in worst-case O(log2 (n)) time, and (c) next crossing in worst-case O(k log2 (n)) time, where k is the number of cars which appear in the printed output of this function call (see description below). In the above, n denotes the total number of cars currently on the highway.
4. You cannot use any in-built libraries (including standard template library). The data structure should be implemented in C++ from scratch.
5. You should use the templates feature of C++ for implementation (see Practice Lab 2).
6. Collaboration is not permitted on this assignment. Your submitted code should be completely your own. See section titled “Honor Code” in course outline already shared with you.