You will implement a Queue class and a LFSR class. LFSR is a linear feedback shi
ID: 3802871 • Letter: Y
Question
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
Explanation / Answer
Answer:
#include<iostream>
using namespace std;
struct node
{
int info;
node *later;
}*front_end = NULL,*rear_end = NULL,*p = NULL,*node_pointer = NULL;
void push(int value)
{
node_pointer = new node;
node_pointer->info = value;
node_pointer->later = NULL;
if(front_end == NULL)
{
front_end = rear_end = node_pointer;
rear_end->later = NULL;
}
else
{
rear_end->later = node_pointer;
rear_end = node_pointer;
rear_end->later = NULL;
}
}
int remove()
{
int value;
if(front_end == NULL)
{
cout<<" queue is empty ";
}
else
{
p = front_end;
value = p->info;
front_end = front_end->later;
delete(p);
return(value);
}
}
int main()
{
int n,c = 0,value;
cout<<"Enter the number of values to be pushed into queue ";
cin>>n;
while (c < n)
{
cout<<"Enter the value to be entered into queue ";
cin>>value;
push(value);
c++;
}
cout<<" Deleted Values ";
while(true)
{
if (front_end != NULL)
cout<<remove()<<endl;
else
break;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.