Description
Spring 2025
2. Testing We have provided a test suite for your llrec functions, your heap and your stack. They work similar to the previous assignment: cd hw3_tests cmake . make You only need to run cmake once, after that, if you make changes to your code you only need to run make. Change directory to llrec_tests, stack_tests, or heap_tests to access the individual test programs. The test directory is excluded by the .gitignore. If you need to download the tests (Linux/Docker only) elsewhere: wget https://bytes.usc.edu/files/cs104/sp23/grading/hw3_tests.tar.gz tar xvfz hw3_tests.tar.gz Run these commands inside your hw3 directory. Next Current layout: 1 Panel with tree 3. Linked List Split/Pivot In this problem you will practice implementing recursive functions that process linked lists. Skeleton code is provided in the hw3 folder in this assignment. There are two separate recursive functions that we will ask you to write. They are unrelated to each other (just part a, and part b of this problem), but each of the two problems below will use the following Node definition. struct Node { int val; Node *next; }; You may declare and use helper functions as you deem necessary. Remember to handle the cases when an input linked list is empty. Also, most recursive solutions are elegant. If you find yourself writing a lot of code, you likely aren’t on the right track. If you had a recursive linked list tracing problem in a prior homework, that might give you an idea of the elegance we are referring too. Part 1 – Linked List Split/Pivot Write a recursive function to split the elements of a singly-linked list into two output lists, one containing the elements less than or equal to a given number, the other containing the elements larger than the number. You must MAINTAIN the relative ordering of items from the original list when you split them into the two output lists. The original list should not be preserved. Your function must be recursive – you will get NO credit for an iterative solution. It must also run in O(n), where n is the length of the input list (and can be done with only one pass/traversal through the list). Here is the function you should implement: void llpivot (Node*& head, Node*& smaller, Node*& larger, int pivot); When this function terminates, the following holds: ● smaller is the pointer to the head of a new singly linked list containing all elements of head that were less than or equal to the pivot. ● larger is the pointer to the head of a new singly linked list containing all elements of head that were (strictly) larger than the pivot. ● the linked list head no longer exists (head should be set to NULL). Note: smaller and larger may be garbage when called (i.e. you can NOT assume they are NULL upon entry). Also you should not delete or new nodes, but just change the pointers to form the two other lists. As an example, suppose the list pointed to by head contained 2 4 8 3. If we used 5 as the pivot and called: llpivot(head, smaller, larger, 5); Then: ● head should be an empty list ● smaller should contain 2 4 3 ● larger should contain 8 See llrec.h for more details and description and then place your implementation in llrec.cpp. Next Current layout: 1 Panel with tree 4. Linked List Filter Part 2 – Linked List Filter Write a recursive function to filter/remove elements of a singly-linked list that meet a specific criteria. The criteria for removal is provided by a comparison (Comp) functor/function object that provides an operator() that takes in an int and returns a bool if the node should be removed/filtered. Filtered nodes should be deallocated. Your function must be recursive – you will get NO credit for an iterative solution. It must also run in O(n), where n is the length of the input list (and can be done with only one pass/traversal through the list). template Node* llfilter(Node* head, Comp pred); As an example, if the list pointed to by head contained: 3 6 4 9 and the Comp object’s operator() returns true for an ODD integer input, then the function should return a pointer to the list containing 6 4 (since all the odd integers would have been filtered out). Since this is a templated function (to allow for different function object types), you should put your implementation in llrec.h. See llrec.h for more details and description. Testing We have provided a skeleton file llrec-test.cpp with a main() and some helper functions that read in values from a file to create a linked list, print a linked list, and deallocate a linked list. Complete llrec-test.cpp to exercise your functions and verify behavior as you see fit. Currently, it only reads in the contents of a file and creates the corresponding linked list. You can then call your functions on that list, print results, etc. to verify the correctness of your implementation. You must update your Makefile with a target llrec-test that will compile the necessary code in the various source files including llrec-test.cpp into an executable named llrec-test. The Makefile will be used by the autochecker so if it doesn’t work then your assignment will not be autograded correctly. Once you have compiled your test program, you can run it and provide an input file. See an example below: ./llrec-test llrec-test1.in We have provided one input test file, llrec-test1.in that you can use. Feel free to create other input files and use that as input. (It would be appropriate to add/commit/push those files if you create them). Note: We will not grade your llrec-test.cpp or any input files you create. They are SOLELY for your own benefit to test your code. After submission, we will test your code with our own full test suite and assign points based on those tests. We ask that you NOT SHARE your test program or input files with other students. We want everyone to go through the exercise of considering what cases to test and then implementing those tests. Related Videos A video overview of how these functions may work and be organized is available here. Next Current layout: 1 Panel with tree 5. Templated Stack Implement a templated Stack class, Stack. It must: ● inherit from std::vector and you need to choose whether public or private inheritance is the best choice. Though composition would generally be preferable since a Stack is not truly a vector, we want you to practice with templates and inheritance. ● Support the following operations with the given signatures (see header file) Stack(); size_t size() const; bool empty() const; void push(const T& item); void pop(); T const & top() const; ● ● If top() or pop() is called when the stack is empty, you must throw std::underflow_error defined in . ● All operations must run in O(1) time. Failure to meet this requirement will result in MAJORITY of credit being deducted for this problem. ● Important Note: To call a base class function that has the same name you cannot use this->member_func() since both classes have that function and it will default to the derived version and lead to an infinite recursion. Instead, scope the call (e.g. LList::size()). ● It would probably be a good idea to write a very simple test program (e.g. stack_test.cpp) just to ensure your code can pass some basic tests. We will not grade or require separate stack tests, but there are stack tests in the test suite. Next Current layout: 1 Panel with tree 6. Functors The following is background info that will help you understand how to do the next step. If you saw the following: int x = f(); You’d think f is a function. But with the magic of operator overloading, we can make f an object and f() a member function call to operator() of the instance, f as shown in the following code: struct RandObjGen { int operator() { return rand(); } }; RandObjGen f; int r = f(); // translates to f.operator() which returns a random number by calling rand() An object that overloads the operator() is called a functor and they are widely used in C++ STL to provide a kind of polymorphism. We will use functors to make a sort algorithm be able to use different sorting criteria (e.g., if we are sorting strings, we could sort either lexicographically/alphabetically or by length of string). To do so, we supply a functor object that implements the different comparison approach. struct AlphaStrComp { bool operator()(const string& lhs, const string& rhs) { // Uses string’s built in operator< // to do lexicographic (alphabetical) comparison return lhs < rhs; } }; struct LengthStrComp { bool operator()(const string& lhs, const string& rhs) { // Uses string’s built in operator< // to do lexicographic (alphabetical) comparison return lhs.size() < rhs.size(); } }; string s1 = “Blue”; string s2 = “Red”; AlphaStrComp comp1; LengthStrComp comp2; cout << “Blue compared to Red using AlphaStrComp yields ” << comp1(s1, s2) << endl; // notice comp1(s1,s2) is calling comp1.operator() (s1, s2); cout << “Blue compared to Red using LenStrComp yields ” << comp2(s1, s2) << endl; // notice comp2(s1,s2) is calling comp2.operator() (s1, s2); This would yield the output 1 // Because “Blue” is alphabetically less than “Red” 0 // Because the length of “Blue” is 4 which is NOT less than the length of “Red (i.e. 3) We can now make a templated function (not class, just a templated function) that lets the user pass in which kind of comparator object they would like: template void DoStringCompare(const string& s1, const string& s2, Comparator comp) { cout << comp(s1, s2) << endl; // calls comp.operator()(s1,s2); } string s1 = “Blue”; string s2 = “Red”; AlphaStrComp comp1; LengthStrComp comp2; // Uses alphabetic comparison DoStringCompare(s1,s2,comp1); // Use string length comparison DoStringCompare(s1,s2,comp2); In this way, you could define a new type of comparison in the future, make a functor struct for it, and pass it in to the DoStringCompare function and the DoStringCompare function never needs to change. These comparator objects are use by the C++ STL map and set class to compare keys to ensure no duplicates are entered. template < class T, // set::key_type/value_type class Compare = less, // set::key_compare/value_compare class Alloc = allocator // set::allocator_type > class set; You could pass your own type of Comparator object to the class, but it defaults to C++’s standard less-than functor less which is simply defined as: template struct less { bool operator() (const T& x, const T& y) const {return x<y;} }; For more reading on functors, search the web or try this link Next 7. Heap Implementation Now that you have learned the basics of heaps, build your own m-ary Heap class whose public definition and skeleton code are provided in the heap.h skeleton file. Rather than specifying a specific type of heap (Min- or Max-Heap) we will pass in a Comparator object so that if the comparator object functor implements a less-than check of two items in the heap then we will have a min-heap. If the Comparator object functor implements a greater-than check of two items in the heap, we will have a max-heap. template > class Heap { public: /// Constructs an m-ary heap for any m >= 2 Heap(int m = 2, Comparator c = Comparator() ); // other stuff }; You may use the STL vector container if you wish. Of course, you MUST NOT use the STL priority_queue class or make_heap, push_heap, etc. algorithms. Notice we can provide a default template type for the Comparator so that the client doesn’t have to specify it if they are happy with the std::less (i.e. which assumes a built-in operator< is available for type T and calls it). Notice the constructor also provides default value for m and the Comparator which is a default-constructed Comparator. Default parameter values will be used if the client does not supply them. Also if a default parameter is used then all parameters after it must also have default values (i.e. default parameters must be at the end of the declaration). The last thing to note is you only supply the default value in the declaration of the function. When you define the function (i.e. write the implementation below) you would not specify the default value again but just leave the argument types/names. For example, when implementing the function you’d just define: template Heap<T,Comparator>::Heap(int m, Comparator c /* Don’t specify the default value here, only above */ ) // Your code here So with these defaults in place, the client that wants a binary min-heap with a type that has a less-than operator need only write: Heap h1; // calls the default constructor with default args: // m=2 and std::less is used as the default template type for Comparator // and std::less() (i.e. the default constructor) will be the // comparator object created by the constructor If the client wants some custom method of comparison so that they can implement a max-heap or some other alternative using a custom comparator can write: ObjAComparator c1( /* some constructor arguments as desired */ ); Heap<ObjA, ObjAComparator> h1(2, c1); Before using our tests, we recommend you write a simple test program of your own to check some simple cases that you come up with. You could push a few integers in random order and then pop them all out and ensure they are in order. You may want to try heaps of different types like int and/or string. Also, be sure it works as a min-heap and as a max-heap using different comparators. For reference if your type T has a < operator, then C++ defines a less functor which will compare the type T items using the operator<(). Similar there is a greater functor already defined by C++ that will compare using the operator>(). They are defined in the functional header (#include ) and you can look up their documentation online for further information. This is meant to save you time writing functors for types that can easily be compared using built in comparison operators. Note: You may use this Heap object in future homeworks, so test it well now! Next Current layout: 1 Panel with tree 8. Logic Simulator – Background A logic simulator is a program that reads in a digital circuit (made up of gates like AND gates, OR gates and NOT gates) and a set up inputs and then simulates over time the behavior of the circuit. Simple logic simulators work by modeling gates and the wires between them. Wires have a state (eg. ‘high’ or ‘low’ or ‘undefined’) where the state is set by a gate output or directly by the simulator. When gates change state (because one or more of their input wires changed state), this change of state is output as an event that changes the state of a wire. Events have a time and must be processed in order of their ‘time’. Wires may be connected to multiple gates and because some gates may have different propagation delays, the same event (e.g a wire changing from ‘low’ to ‘high’) may generate more than one event at different times in the future. Events need to be captured and sorted by time, thus a min-heap is an excellent data structure to use for storing the events in a logic simulator. To get an idea of what we’re trying to build for this part below is a simple circuit containing one AND gate with two inputs and one output. The output of an AND gate is only high when input A AND input B are high. Below that is a simple timing diagram (the x axis is in arbitrary integer delay units) for this circuit. You can see that as soon as both inputs are high, the output transitions to high. Next we have a simple circuit containing one OR gate. OR gates will output high when one OR the other (or both) inputs are high. Finally, we have the NOT gate where the output is the logical inverse of the output. The goal of this part of the assignment is to get a working logic simulator that uses your min-heap implementation from the previous step. Much of the implementation is done for you and we have included a Java program that can generate the timing diagrams. The Java program consumes a file with a simple header describing the signals in the timing diagram and a list of events describing when the signals change state. Next Current layout: 1 Panel with tree 9. Logic Simulator – Circuit Details For our logic simulator the top-level object is the Circuit class defined in circuit.cpp. A program wishing to simulate a circuit instantiates a Circuit object and the passes the name of a file to Circuit::parse(). The parse() function will read the circuit description and instantiate the various gates and wires required. There is also a Circuit::test() function that will directly instantiate the simple AND circuit. To simulate the circuit a program then calls Circuit::run() which will output a log of when certain wires change state. If the user calls Circuit::startUml and Circuit::endUml then the output of the program can be fed into the plantuml Java program to generate a timing diagram. The top-level Circuit object has several data members that describe the circuit: vector<Wire*> Circuit::m_wires is a vector containing pointers to the wires in the circuit. vector<Gate*> Circuit::m_gates is a vector containing pointers to the gates in the circuit. Heap Circuit::m_pq is a Heap object (your code) used as a min-heap (priority queue) to hold the events generated by the gates. A circuit is built with Wires and Gates. A Wire object maintains it’s state (high, low, undefined). If the wire has a name, then when it changes state it also outputs a log message. A wire starts out in the undefined state. A Gate object is an abstract class that has several data members: Wire* Gate::m_output a pointer to the wire connected to the gate’s input. vector<Wire*> m_inputs a vector of pointers to the wires connected to the gates inputs. Gates must be derived into specific gates that have a fixed number of inputs and perform a logic function based on the state of the input wires. For simplicity we are setting the gate delay to zero. After instantiating the wires and gates (and connecting them together), the circuit injects any startup events into the priority queue. To simulate the circuit the Circuit object calls Circuit::advance() to advance to the next set of events occurring at the same time. Each event changes the state of a wire. After all events at a particular time are processed, all of the gates are polled with Gate::update(). If the gate detects that it needs to change the state of one of it’s outputs, the gate returns an event to do so. Study the logic simulator implementation to see how it works before moving on to the tasks you must complete. Next Current layout: 1 Panel with tree 10. Logic Simulator – Tasks The logic simulator as given is almost complete. We want you to get a little experience with implementing a cool application of a heap. Your tasks: 1. In event.h write the operator() implementation for EventLess to create a functor for your heap implementation. The operator() will take two Event*’s as it’s input and needs to sort them using the Event::time data member in such a way that your heap will be a min-heap. i.e. Event’s are sorted by time. 2. Add the m_pq data member to the Circuit class. This data member must use your Heap class from the previous part of the assignment and it must use the EventLess functor. 3. In gate.h and gate.cpp add an implementation of a single input NOT gate called NotGate that derives from Gate. It should implement the following truth table: NOT(‘X’) -> ‘X’, NOT(‘0’) -> ‘1’, NOT(‘1’) -> ‘0’. Model the state change behavior to be the same as the And2Gate and Or2Gate. 4. Update the parsing code in Circuit::parse() to support adding NotGate gates. Next Current layout: 1 Panel with tree 11. Logic Simulator – Input format Here we describe the input format for the circuit files. This will help you implement adding NotGate to the code. You can also experiment with building bigger circuits. The first section describes the wires: WIRES , , , … , Where is the number of wires. through are the integer ID’s of the wires. through are the names of the wires. Names are optional. If a wire has a name, state changes for it will be logged. Next we have the gates: GATES ,,,…, ,,,…, … Where is the number of gates. There are lines describing the gates following. is the type of the gate, currently one of AND2, OR2, NOT. is the ID of the first input wire, is the ID of the 2nd input wire (if there is one) and so on for the correct number of inputs. is the ID of the output wire. Next are the bootstrap events that are used to set the initial state of the wires: INJECT ,, … ,, Where is the number of events to inject. is the first event, up to . For each event is the ID of the wire and is the state of the event. Next Current layout: 1 Panel with tree 12. Logic Simulator – Testing Examine the Makefile for your logic simulator. You can build the logic simulator with: make To run the single_and.txt circuit: ./logicsim single_and.txt This should output something similar to: To turn this into a timing diagram: ./logicsim single_and.txt > my_and.uml java -jar plantuml.jar my_and.uml Next