The stack class needs to be a template class. The stack needs to dynamically create (with push) and destroy (with pop) nodes that contain the data for the stack and contain a pointer to the next entry in the stack. The node class needs to be a template class as well. We will be making the stack class a friend class of the node class.
Create the stack class and stackEntry classes. These should both be defined and implemented in stack.h.
The stackEntry class has private instance data
Type dataValue;
stackEntry< Type>* pNext;
The class stack should be a friend class of stackEntry.
Create the following protected member functions:
stackEntry(const Type &newData, stackEntry*newNext = nullptr);
virtual ~stackEntry();
virtual void next(stackEntry< Type> *pNext);
virtual Type& data();
virtual const Type& data() const;
virtual stackEntry< Type>* next();
The stack class has private instance data:
The public member functions of the stack class
stack();
stack(const stack &other);
const stack& operator=(const stack &rhs);
virtual ~stack();
const Type& top() const;
Type& top();
bool empty() const;
std::size_t size() const;
void push(const Type &value);
void pop();
void clear();
void debug() const;
void debug(std::ostream &out) const;
The stack.h file contains the friend class definition and the node class declarations. You will need to implement all of the above constructors, destructor, and member functions. You can create additional private member functions as needed for your implementation. You must not create any additional public member functions without the approval of your instructor.
Here is a brief summary of the various stack functions (listed above)
stack()
This creates a new stack and initializes the stack to no entries. The stack needs to have a count of the number of valid values currently in the stack. This will be 0 when the stack is first created.
stack(const stack &other)
This is the copy constructor. It will make copies of each of the entries in the "other" stack and add them do the new stack being created. Make sure the order of the entries is preserved in the copy.
const stack& operator=(const stack &rhs)
The assignment operator is a superset of the behavior in the stack copy constructor. You need to first remove any nodes of the stack being copied into (the this object). You then need to create copies of all of the nodes in the rhs stack and add them to the this stack, again preserving the ordering.
Make sure you return back a copy of the current (this) stack when you are done. Also make sure you check for self assignment. In the case of self assignment your assignment operator should just return without doing anything to the stack being copied into.
~stack()
This is the stack destructor. Make sure you delete all nodes in the stack. To not allow your program to have memory leaks.
const Type& top() const
This returns the top element in the stack. You can assume the stack has one or more entries. If you want you can also add an assert to your program:
#include < cassert>
// lots of code goes here
const Type& top() const
{
assert(firstNode != nullptr); // firstNode should be replaced by
// the pointer to the top of the stack.
}
Type& top()
This returns the top element in the stack. This will be the same as the code in your other top() member function. The only difference is that this returns a reference that allows the caller to change the data in the top element.
bool empty() const
Returns true if the stack is empty and false if the stack has at least one entry.
std::size_t size() const
Returns the number of entries in the stack.
void push(const Type &value)
This creates a new node that contains value and adds it to the top of the stack.
void pop()
This removes the top entry from the stack. Make sure you delete the node. If the stack is empty pop should do nothing.
void clear()
Delete all of the entries in the stack.
void debug() const
void debug(std::ostream &out) const
The debug member functions are provided. They assume the count of the number of valid entries is in a member variable named count and that the pointer to the top of the stack is named firstNode. If you use different names for these data members of the stack class you will have to update the debug(ostream &) member function.
Once you have created your stack and stackEntry classes you should thoroughly test them before you continue with the rest of the assignment. You should write your own main function (in a separate file) to do this testing.
You will not need this in your final version of the program (part 3).
Make sure you write code to thoroughly test your stack before moving on to part 2.
The queue class needs to be a template class. The queue needs to dynamically create (with push) and destroy (with pop) nodes that contain the data for the queue and contain a pointer to the next entry in the queue. The node class needs to be a template class as well. We will be making the queue class a friend class of the node class.
Create the queue class and queueEntry classes. These should both be defined and implemented in queue.h.
The queueEntry class has private instance data
Type dataValue;
queueEntry< Type>* pNext;
The class queue should be a friend class of queueEntry. Create the following protected member functions:
queueEntry(const Type &newData, queueEntry< Type> *newNext = nullptr);
virtual ~queueEntry();
virtual void next(queueEntry< Type> *pNext);
virtual Type& data();
virtual const Type& data() const;
virtual queueEntry< Type>* next();
The queue class has private instance data:
The public member functions of the queue class
queue();
~queue();
queue(const queue &other);
const queue& operator=(const queue &rhs);
const Type& front() const;
Type& front();
const Type& back() const;
Type& back();
bool empty() const;
std::size_t size() const;
void push(const Type &value);
void pop();
void clear();
void debug() const;
void debug(std::ostream &out) const;
void traverse(void (*applicationFunction) (const Type &nextItem));
The queue.h file contains the friend class definition and the node class declarations. You will need to implement all of the above constructors, destructor, and member functions. You can create additional private member functions as needed for your implementation. You must not create any additional public member functions without the approval of your instructor.
Here is a brief summary of the various stack functions (listed above)
queue()
This creates a new queue and initializes the queue to no entries. The queue needs to have a count of the number of valid values currently in the queue. This will be 0 when the queue is first created.
queue(const queue &other)
This is the copy constructor. It will make copies of each of the entries in the "other" queue and add them do the new queue being created. Make sure the order of the entries is preserved in the copy.
const queue& operator=(const queue &rhs)
The assignment operator is a superset of the behavior in the copy constructor. You need to first remove any nodes of the queue being copied into (the this object). You then need to create copies of all of the entries in the rhs queue and add them to the this queue, again preserving the ordering.
Make sure you return back a copy of the current (this) stack when you are done. Also make sure you check for self assignment. In the case of self assignment your assignment operator should just return without doing anything to the stack being copied into.
~queue()
This is the queue destructor. Make sure you delete all nodes in the queue. To not allow your program to have memory leaks.
const Type& front() const
This returns the front element in the queue. You can assume the queue has one or more entries. This is the oldest entry in the queue. If you want you can also add an assert to your program:
#include < cassert>
// lots of code goes here
const Type& front() const
{
assert(pFront != nullptr); // pFront should be replaced by
// the pointer to the front of the queue.
}
Type& front()
This returns the front (oldest) element in the queue. This will be the same as the code in your other front() member function. The only difference is that this returns a reference that allows the caller to change the data of the front element.
const Type& back() const
This returns the back element in the queue. You can assume the queue has one or more entries. This is the newest entry in the queue. If you want you can also add an assert to your program:
#include < cassert>
// lots of code goes here
const Type& back() const
{
assert(pEnd != nullptr); // pEnd should be replaced by
// the pointer to the end of the queue.
}
Type& back()
This returns the back (newest) element in the queue. This will be the same as the code in your other back() member function. The only difference is that this returns a reference that allows the caller to change the data of the back element.
bool empty() const
Returns true if the queue is empty and false if the queue has at least one entry.
std::size_t size() const
Returns the number of entries in the queue.
void push(const Type &value)
This creates a new node that contains value and adds it to the end of the queue.
void pop()
This removes the front entry from the queue. Make sure you delete the node. If the queue is empty pop should do nothing.
void clear()
Delete all of the entries in the queue.
void debug() const
void debug(std::ostream &out) const
The debug member functions are provided. They assume the count of the number of valid entries is in a member variable named count and that the pointer to the front of the queue is named pFront, and the pointer to the end of the queue is pEnd. If you use different names for these data members of the queue class you will have to update the debug(ostream &) member function.
void traverse(void (*applicationFunction) (const Type &nextItem))
The traverse function will be passed a pointer to a function by the application using the queue class. The function being passed is not part of the queue class, it is defined as part of the application using the queue. The function address passed must be a function that returns void and takes a const Type & as a parameter. So if the application creates a queue object the function could look as follows:
// This is part of the application using a queue< std::string>
void myFunction(const std::string &nextString);
// The application code to create the queue and use the traverse function could look as follows:
queue< std::string> myQueue;
myQueue.push("A");
myQueue.push("B");
myQueue.push("C");
// more code
myQueue.traverse(&myFunction); // myFunction will be called 3 times, once for "A", then "B", and finally "C"
The function must either be a stand-alone function or a static function in some application specific class.
Once you have created your queue and queueEntry classes you should thoroughly test them before you continue with the rest of the assignment. You should write your own main function (in a separate file) to do this testing.
You will not need this in your final version of the program (part 3).
Make sure you write code to thoroughly test your stack before moving on to part 3.
The menu and driver code has been written for you. The menu/driver code will make use of a new class you will create called browserSupport. This, in turn, will make use of a class url that has been partially written for you. Started code for both of these classes are defined in file browserSuport.h. The implementation is in browserSupport.cpp.
The menu/driver code is in the following files, also provided for you:
assignment5.cpp
menuList.h
menuList.cpp
command.h
browserCommand.h
browserCommand.cpp
You should not have to make any changes to the above list of files. Your code needs to be in thebrowserSupport.h file and in browserSupport.cpp. Do not have any inline functions in browserSupport.h. All of the implementation code needs to be in browserSupport.cpp.
browserSupport and url classes
These two classes are defined in browserSupport.h and implemented in browserSupport.cpp. You need to add a queue of url objects as private instance data in the browserSupport class. The code I provided calls this historyQueue. If you give your queue< url> a different name you will have to change the code I provided to you.
Here is the template code that is provided:
browserSupport.h
#ifndef BROWSERSUPPORT_H_
#define BROWSERSUPPORT_H_
#include < string>
#include < vector>
#include "stack.h"
#include "queue.h"
class url
{
private:
std::string urlText;
bool urlValid;
public:
// you need to implement these
url(const std::string &urlText);
url();
virtual ~url();
void text(const std::string &urlText);
std::string text() const;
bool valid() const;
bool operator< (const url& rhs) const;
bool operator==(const url& rhs) const;
// these are implemented for you
operator std::string() const; // this allow us to do the following:
// url myURL("utdallas.edu");
// std::string text = static_cast< std::string>(myURL);
bool operator> (const url& rhs) const { return rhs < *this; }
bool operator< =(const url& rhs) const { return !(*this > rhs); }
bool operator>=(const url& rhs) const { return !(*this < rhs); }
bool operator!=(const url& rhs) const { return !(*this == rhs); }
};
// you need to implement this
std::ostream& operator<< (std::ostream &out, const url &other);
class browserSupport
{
private:
// this is needed for displaying the histroy
static std::vector< url> *pVector;
public:
// you need to implement these
browserSupport();
virtual ~browserSupport();
url back();
url forward();
void display(const url &newURL);
std::size_t clearHistory();
std::size_t clearCache();
std::size_t maximum() const;
void maximum(std::size_t newMax);
// this is implemented for you
std::size_t history(std::vector< url> &historyURLs);
private:
// this is implemented for you
static void buildHistory(const url &nextURL);
};
#endif /* BROWSERSUPPORT_H_ */
browserSupport.cpp
#include "browserSupport.h"
#include < string>
url::operator std::string() const
{
return text();
}
std::vector< url> *browserSupport::pVector = nullptr;
void browserSupport::buildHistory(const url &nextURL)
{
if (pVector != nullptr)
{
(*pVector).push_back(nextURL);
}
}
std::size_t browserSupport::history(std::vector< url> &historyURLs)
{
historyURLs.clear();
browserSupport::pVector = &historyURLs;
historyQueue.traverse(&browserSupport::buildHistory);
browserSupport::pVector = nullptr;
return 0;
}
class url
This is a summary of the member functions of class url that you need to implement:
class url
{
private:
std::string urlText;
bool urlValid;
public:
// you need to implement these
url(const std::string &urlText)
This constructor sets the urlText and sets urlValid to true.
url()
The urlValid state needs to be false. This indicates that the url is not a valid one.
~url()
The destructor can probably be empty unless your implementation of the url class uses dynamic memory allocation.
void text(const std::string &urlText)
Sets the url text to a new value.
std::string text() const
Returns the current url text.
bool valid() const
Returns true if the url is valid (contains text) and false if invalid.
bool operator< (const url& rhs) const
Compare the urlText of this object to see if it is less than the rhs.urlText.
bool operator==(const url& rhs) const
Are the urlText values of the two objects the same?
Non-member function
std::ostream& operator<<(std::ostream &out, const url &other)
The output operator needs to output the text of the url. This does not need to be a friend class of the url class. It can, and should, use only public member function(s) to retrieve the url text.
Member functions of class url that are implemented for you
operator std::string() const
This is a cast operator. This allows you to do the following:
url myURL("utdallas.edu");
std::string text = static_cast< std::string>(myURL);
bool operator> (const url& rhs) const { return rhs < *this; }
bool operator<=(const url& rhs) const { return !(*this > rhs); }
bool operator>=(const url& rhs) const { return !(*this < rhs); }
bool operator!=(const url& rhs) const { return !(*this == rhs); }
These all make use of the two comparison operators you implemented above.
class browserSupport
The browserSupport class needs to have a queue to save the history of url objects displayed (see the display member function for additional details). The history is limited to the browser history maximum (see the maximum() and maximum(std::size_t) member functions for how this value can be changed and queried by users of the browserSupport class. The default size of 50 should be set by the constructor. You must add this history queue to your private instance data in the browserSupport class. The code provided calls this historyQueue. If you use a different name you will have to change the code provided.
The class also needs to have a stack of old url objects that we can access with the back member function. It needs to keep track of the currently displayed url. Finally you need a stack of old url objects you can access via the forward member function.
The display member function is called when the user enters a new url. The back member function is called when the user uses the back menu, and forward member function is called when the user uses the forward menu.
You need to implement the following member functions of the browserSupport class.
browserSupport()
The constructor needs to initialize the browserSupport data members. Make sure you set the maximum number of entries allowed in the browser history to 50. This is the deafult maximum value.
The current url (this needs to be a data member in your class) needs to be set to a default url object. This will be invalid.
Example. If your current url is called currentlURL this would look as follows: currentURL = url;
or in your constructor's initialization list:
: ,... , currentURL(), ...
~browserSupport()
Destroy the object. This will be empty unless you are dynamically creating objects within the browserSupport class.
url back()
pseudo-code:
If the back stack is not empty
if the current url is valid
push the current url onto the forward stack.
end if
set the current url to the top of the back stack.
pop off the url from the back stack
end if
return the current url
url forward()
The forward logic is similar to the back logic except that the back stack becomes the forward stack and the forward stack becomes the back stack.
void display(const url &newURL)
if the current url is valid it needs to be pushed onto the back stack.
The specified url becomes the current url.
The new current url needs to be checked with the back of the history queue (if it is not empty). If it is not the same it needs to be added (pushed) to the history queue.
If the history queue size is larger than the maximum history size you need to pop off the oldest value so the history queue is again at the maximum size.
Since we have a new url from the user we need to clear out the foward stack.
std::size_t clearHistory()
This needs to clear out the history queue. The current url, back stack, and forward stack do not change.
The value returned should be the number of items removed from the history queue. This needs to be the value before you clear out the history queue.
std::size_t clearCache()
Clear out the current url (set it back to a default, invalid, url). Clear out the back and forward stacks. Do not change the history queue.
The number returned should be the number of items removed from the back and forward stacks, and 0 or 1 for the current url. The value for the current url is 0 if the current url is invalid and 1 if it is valid. You need to gather this before you clear out the stacks and reset the current url.
std::size_t maximum() const
Return the maximum size of the history queue.
void maximum(std::size_t newMax)
Change the maximum size of the history queue. If the history queue is now larger than the maximum size you need to pop off entries until you are back to the maximum size.
The following browerSupport class member function and static function are implemented for you.
*`std::size_t history(std::vector &historyURLs)
static void buildHistory(const url &nextURL)