You will implement a Queue class and a LFSR class. LFSR is a linear feedback shift register. A linear feedback shift register is one way of generating a sequence of numbers that appear to be random. The sequence will eventually repeat so it is a pseudo random sequence. The LFSR class will be a client of the Queue class. To initialize the LFSR object, it requires a string of ones and zeros. They are the starting contents of the queue and two integers will identify the specific values within that will be used to compute the next value of the pseudo random sequence. A peek function in the Queue class is used to retrieve the desired values out of the queue. Peek(n) returns the value stored n positions away from the front value of the queue. For example, Peek(0) give the front value, Peek(1) gives the value behind the front value and so forth. Peek will require a loop to traverse the pointer links to locate the value of interest. main.cpp is a driver program to test Queue and LFSR classes. Queue.h and lfsr.h are given. Your task is to complete the lfsr.cpp and queue.cpp file. Input files are given. You can use the given makefile to compile this program. Reference: LFSR register: https://en.wikipedia.org/wiki/Linear_feedback_shift_register

Shift Register Header File

// // lfsr.h // // Client code of queue container which implements a // pseudo-random number generator by using a queue of integers // as a linear feedback shift register // // // NOTE: // Pattern of ones and zeros repeats ine queue eventually repeats // // DO NOT MODIFY OR SUBMIT THIS FILE //

#include "queue.h"

#ifndef LFSR_H #define LFSR_H

class LFSR { private: Queue q; // Queue object

int t1, t2; // Tap index values - two integers (peek offsets from front of queue)

bool XOR(int a, int b); // XOR(...) // Exclusive OR function // a | b | a XOR b // ---------------- // 0 | 0 | 0 // 0 | 1 | 1 // 1 | 0 | 1 // 1 | 1 | 0

public: LFSR(string seed, int tap1, int tap2); // LFSR(...) // Initializes t1 and t2 to tap1 and tap2, respectively // and parses seed string to loading queue with starting values void NextState(); // NextState() // Iterator method computes and queues next pseudo-random number in sequence // Algorithm // (1) temp = Peek(tap1) XOR Peek(tap2) // (2) Dequeue // (3) Enqueue(temp) void Print() // Print() -- DO NOT MODIFY OR RELOCATE THIS FUNCTION { int k = 0; int num = q.Size(); while (k < num) { int temp = q.Front(); q.Dequeue(); q.Enqueue(temp); cout << temp; k++; } } };

#endif

Main File

// main.cpp

// Driver program which is used to test each // class member function. // // DO NOT MODIFY OR SUBMIT THIS FILE //

#include #include #include #include #include "queue.h" #include "lfsr.h"

using namespace std;

void Bar(int n); // Prototype for Bar function

int main(int argc, char* argv[]) { ifstream inputs; // Input file for commands char op, ch; // Hold operation and optional char input Queue* queuePtr = NULL; // Will point to Queue object LFSR* lfsrPtr = NULL; // Will point to LFSR object string comment; // Stores comment read from input file int n; // Integer temporary variable string seed; // Stores seed value int tap1, tap2; // Store tap index values // Output usage message if one input file name is not provided switch (argc) { case 2: // Correct number of command line arguments break;

default: // Incorrect number of command line arguments cout << "Usage: program04 "; return 1; } // Attempt to open input file -- terminate if file does not open inputs.open(argv[1]); if (!inputs) { cout << "Error - unable to open input file" << endl; return 1; }

Bar(60); // Output long bar

// Process comment line from input file getline(inputs, comment); // Input file header comment cout << endl << comment << endl << endl; // Output file header comment

// Process commands from input file inputs >> op; // Attempt to input first command while (inputs) { switch (op) { case '#': // Test file comment getline(inputs, comment); // Input and echo the comment appearing in the test file cout << '#'<< comment << endl; break;

case '~': // Print Bar Bar(40); // Output short bar break;

case 'c': // Constructor inputs >> op; try { if (op == 'Q') { cout << "Queue::Queue() -- Status = "; queuePtr = new Queue; cout << "Completed" << endl; } else if (op == 'L') { inputs >> seed >> tap1 >> tap2; cout << "LFSR::LFSR(" << seed << ", " << tap1 << ", " << tap2 << ") -- Status = "; lfsrPtr = new LFSR(seed, tap1, tap2); cout << "Completed" << endl; } } catch ( std::bad_alloc ) { cout << "Failed Constructor: Terminating now..." << endl; return 1; } break;

case '+': // Enqueue inputs >> n;

if (queuePtr != NULL) { cout << "Queue::Enqueue('" << n << "') -- Status = "; } else if (lfsrPtr != NULL) { cout << "LFSR::Enqueue('" << n << "') -- Status = "; }

if (queuePtr != NULL) { try { queuePtr->Enqueue(n); cout << "Completed" << endl; } catch (QueueFull) { cout << "Failed QueueFull" << endl; }; } else { cout << "Failed" << endl; } break;

case '-': // Dequeue if (queuePtr != NULL) { cout << "Queue::Dequeue() -- Status = "; } else if (lfsrPtr != NULL) { cout << "LFSR::Dequeue() -- Status = "; }

if (queuePtr != NULL) { try { queuePtr->Dequeue(); cout << "Completed" << endl; } catch (QueueEmpty) { cout << "Failed QueueEmpty" << endl; }; } else { cout << "Failed" << endl; } break;

case 'f': // Front if (queuePtr != NULL) { cout << "Queue::Front() -- Status = "; } else if (lfsrPtr != NULL) { cout << "LFSR::Front() -- Status = "; }

if (queuePtr != NULL) { try { n = queuePtr->Front(); cout << "Completed, Value = " << n << endl; } catch (QueueEmpty) { cout << "Failed QueueEmpty" << endl; } } else { cout << "Failed" << endl; } break;

case 'r': // Rear if (queuePtr != NULL) { cout << "Queue::Rear() -- Status = "; } else if (lfsrPtr != NULL) { cout << "LFSR::Rear() -- Status = "; }

if (queuePtr != NULL) { try { n = queuePtr->Rear(); cout << "Completed, Value = " << n << endl; } catch (QueueEmpty) { cout << "Failed QueueEmpty" << endl; } } else { cout << "Failed" << endl; } break;

case 'e': // IsEmpty if (queuePtr != NULL) { cout << "Queue::IsEmpty() -- Status = "; } else if (lfsrPtr != NULL) { cout << "LFSR::IsEmpty() -- Status = "; }

if (queuePtr != NULL) { if (queuePtr->IsEmpty()) cout << "Empty" << endl; else cout << "Not Empty" << endl; } else { cout << "Failed" << endl; } break;

case 'm': // MakeEmpty if (queuePtr != NULL) { cout << "Queue::MakeEmpty() -- Status = "; } else if (lfsrPtr != NULL) { cout << "LFSR::MakeEmpty() -- Status = "; }

if (queuePtr != NULL) {; queuePtr->MakeEmpty(); cout << "Completed" << endl; } else { cout << "Failed" << endl; } break; case 'l': // Size/Length if (queuePtr != NULL) { cout << "Queue::Size() -- " << queuePtr->Size()<< endl; } break;

case 'n': // NextState if (lfsrPtr != NULL) { try { cout << "LFSR::NextState() -- "; lfsrPtr->NextState(); cout << "Completed" << endl; } catch (...) { cout << "Failed" << endl; } } break;

case '?': // Peek inputs >> n; cout << "Queue::Peek(" << n << ") -- "; if (queuePtr != NULL) { try { cout << queuePtr->Peek(n) << endl; } catch (QueueEmpty) { cout << "Failed QueueEmpty" << endl; } catch (QueueInvalidPeek) { cout << "Failed QueueInvalidPeek" << endl; } } break;

case 'p': // Print if (queuePtr != NULL) { cout << "Queue::PrintQ() -- "; queuePtr->PrintQ(); cout << endl; } else if (lfsrPtr != NULL) { cout << "LFSR::Print() -- "; lfsrPtr->Print(); cout << endl; }

break; case 'd': // Destructor try { if (queuePtr != NULL) { cout << "Queue::~Queue() -- Status = "; delete queuePtr; queuePtr = NULL; cout << "Completed" << endl; } else if (lfsrPtr != NULL) { cout << "LFSR::~LFSR() -- Status = "; delete lfsrPtr; lfsrPtr = NULL; cout << "Completed" << endl; } } catch (...) { cout << "Failed Destructor : Terminating now..." << endl; return 1; } break;

default: // Error cout << "Error - unrecognized operation : Terminating now..."<< endl; return 1; break; } inputs >> op; // Attempt to input next command } cout << endl; Bar(60); // Output long bar

return 0; } // End main()

void Bar(int n) // Bar() -- prints horizontal bar { for(int k = 0; k < n; k++) cout << '#'; cout << endl; } // End Bar()

Queue Header FIle

// // queue.h // // Queue class is a circular linked list implementation of the queue abstract data type // // DO NOT MODIFY OR SUBMIT THIS FILE //

#ifndef QUEUE_H #define QUEUE_H

#include using namespace std;

// // Exception classes // class QueueEmpty { /* Empty error class */ }; // Exception class for empty queue condition

class QueueFull { /* Empty error class */ }; // Exception class for full queue condition

class QueueInvalidPeek { /* Empty error class */ }; // Exception class for invalid queue peek condition

// // Queue Node Structure // struct Node // Linked circular queue node structure { int data; // Field for storing data in the queue node Node* nextPtr; // Points to successor node (node following current node) };

// // Queue class declaration // class Queue // Linked circular queue { private: Node* rearPtr; // Points to rear of queue int count; // Number of values stored in queue public: /********** Start of functions you must implement for Queue **************/ // Implement the following nine public functions in the file named queue.cpp Queue(); // Queue() // Initializes all private variables to indicate an empty queue ~Queue(); //~Queue() // Deallocates all queue nodes void MakeEmpty(); // MakeEmpty() // Deallocates all queue nodes and returns queue to empty ready-to-use state void Enqueue(int n); // Enqueue() // Adds value n to rear of queue and increments count. // If queue is already full, throws QueueFull exception

void Dequeue(); // Dequeue() // Removes front value from queue and decrements count. // If queue is empty, throws QueueEmpty exception

int Front() const; // Front() // Returns integer from front of queue // If queue is empty, throws QueueEmpty exception // DOES NOT MODIFY THE QUEUE

int Rear() const; // Rear() // Returns integer from rear of queue // If queue is empty, throws QueueEmpty exception // DOES NOT MODIFY THE QUEUE

int Peek(int n) const; // Peek() // Returns integer n positions from front of queue // If queue is empty, throws QueueEmpty // If position n does not exist, throws QueueInvalidPeek // DOES NOT MODIFY THE QUEUE bool IsFull() const; // IsFull() // Returns true if queue is full. Returns false otherwise. DOES NOT MODIFY THE QUEUE bool IsEmpty() const; // IsEmpty() // Returns true if queue is empty. Returns false otherwise. DOES NOT MODIFY THE QUEUE int Size() const; // Size() // Returns number of items stored in queue. DOES NOT MODIFY THE QUEUE

/*********** End of functions you must implement for Queue ***************/ void PrintQ() const // PrintQ() -- DO NOT MODIFY OR RELOCATE THIS FUNCTION // Prints contents of queue front to rear without modifying its contents { cout << "Front { "; if (rearPtr != NULL) { Node* tempPtr = rearPtr->nextPtr; int n = 0; while (n < count) { cout << tempPtr->data << ' '; n++; tempPtr = tempPtr->nextPtr; } } cout << "} Rear"; } // End Print() };

#endif

//input 01

# p04input1.txt -- Test Queue class member functions Queue(), ~Queue(), IsEmpty(), Enqueue(), Dequeue(), Front(), Rear()

# Test Queue(), ~Queue() c Q p d

~

# Test Queue(), ~Queue(), IsEmpty() c Q e d

~

# Test Enqueue(), IsEmpty(), Front(), Rear() c Q p e f r + 1 p e f r + 2 p e f r + 3 p e f r + 4 p e f r + 5 p e f r d

~

# Test Enqueue(), Dequeue(), Front(), Rear() c Q - f r + 1 + 2 + 3 + 4 + 5 + 6 p - - p f r + 7 + 8 p f r - - - p f r - - - p f r - d

~

//Input2

# Test Queue class member functions MakeEmpty(), Peek(), Size()

# Test MakeEmpty() c Q e m + 1 + 2 + 3 + 4 + 5 + 6 p e m p e + 7 + 8 p m p d

~

# Test Peek() c Q e + 1 + 2 + 3 + 4 + 5 + 6 p ? 0 ? 1 ? 2 ? 3 ? 4 ? 5 ? 6 p + 7 + 8 ? 6 ? 7 ? 8 p m ? 0 p d

~

# Test Size() c Q p l + 1 l + 2 l + 3 l + 4 l + 5 l + 6 l p - - p l - l p + 7 + 8 p l m p l d

//Input3

# Test LFSR class member functions

# Test LFSR(), ~LFSR() c L 01 0 1 p d

~

# Test LFSR(), ~LFSR() c L 001 0 1 p d

~

# Test LFSR(), ~LFSR() c L 0001 2 3 p d

~

# Test NextState() c L 01 0 1 p n p n p n p n p n p d

~

# Test NextState() c L 00 0 1 p n p n p n p n p n p d

~

# Test NextState() c L 001 0 1 p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p d

~

# Test NextState() c L 0001 2 3 p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p d

~

# Test NextState() c L 0001 0 1 p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p d

~

# Test NextState() c L 00000001 0 1 p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p n p d

Make Files: CC=g++ #CC=g++ -fprofile-arcs -ftest-coverage

project04: main.o lfsr.o queue.o $(CC) main.o lfsr.o queue.o -o project04

main.o: main.cpp lfsr.h $(CC) -c main.cpp

lfsr.o: lfsr.cpp lfsr.h $(CC) -c lfsr.cpp

queue.o: queue.cpp queue.h lfsr.h $(CC) -c queue.cpp

clean: rm *.o *.gcda *.gcno *.gcov project04