#ifndef _LINKEDLIST_H_
#define _LINKEDLIST_H_
#include <stdexcept>
using namespace std;
class EmptyListException : public logic_error {
public:
EmptyListException(const string& what_arg ) throw() :
logic_error ("Empty list exception: " + what_arg) {}}
;
template <class T>
class Node {
private:
T data;
Node* next;
public:
Node(T d, Node* n = NULL) : data(d), next(n) {}
T& getData() { return data;}
Node*& getNext() { return next;}
};
template <class T>
class LinkedList {
protected:
Node<T>* head; // Beginning of list
Node<T>* tail; // End of list
int count; // Number of nodes in list
public:
LinkedList(void) : head(NULL), tail(NULL), count(0) {}
LinkedList(const LinkedList<T>& src); // Copy constructor
virtual ~LinkedList(void); // Destructor
virtual T& front(void) {
if (head == NULL) {
throw EmptyListException("front()");
}
return head->getData();
}
virtual T& back(void) {
if (tail == NULL) {
throw EmptyListException("back()");
}
return tail->getData();
}
virtual int size(void) {
return count;
}
virtual bool empty(void) {
return count == 0;
}
virtual void push_front(T); // Insert element at beginning
virtual void push_back(T); // Insert element at end
virtual void pop_front(void); // Remove element from beginning
virtual void pop_back(void); // Remove element from end
virtual void dump(void); // Output contents of list
};
// Copy constructor
template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& src) :
count(0), head(NULL), tail(NULL) {
Node<T>* current = src.head;
while (current != NULL) {
this->push_back(current->getData());
current = current->getNext();
}
}
// Destructor
template <class T>
LinkedList<T>::~LinkedList(void) {
while (!this->empty()) {
this->pop_front();
}
}
// Insert an element at the beginning
template <class T>
void LinkedList<T>::push_front(T d) {
Node<T>* new_head = new Node<T>(d, head);
if (this->empty()) {
head = tail = new_head;
}
else {
head = new_head;
}
count++;
}
// Insert an element at the end
template <class T>
void LinkedList<T>::push_back(T d) {
Node<T>* new_tail = new Node<T>(d, NULL);
if (this->empty()) {
head = new_tail;
}
else {
tail->getNext() = new_tail;
}
tail = new_tail;
count++;
}
// Remove an element from the beginning
template <class T>
void LinkedList<T>::pop_front(void) {
if (head == NULL) {
throw EmptyListException("pop_front()");
}
Node<T>* old_head = head;
if (this->size() == 1) {
head = NULL;
tail = NULL;
}
else {
head = head->getNext();
}
delete old_head;
count--;
}
// Remove an element from the end
template <class T>
void LinkedList<T>::pop_back(void) {
if (tail == NULL) {
throw EmptyListException("pop_back()");
}
Node<T>* old_tail = tail;
if (this->size() == 1) {
head = NULL;
tail = NULL;
}
else {
// Traverse the list
Node<T>* current = head;
while (current->getNext() != tail) {
current = current->getNext();
}
// Unlink and reposition
current->getNext() = NULL;
tail = current;
}
delete old_tail;
count--;
}
// Display the contents of the list
template <class T>
void LinkedList<T>::dump(void) {
cout << "(";
if (head != NULL) {
Node<T>* current = head;
while (current->getNext() != NULL) {
cout << current->getData() << ", ";
current = current->getNext();
}
cout << current->getData();
}
cout << ")" << endl;
}
#endif
#ifndef _ENHANCELINKLIST_H_
#define _ENHANCELINKLIST_H_
#include "LinkedList.h"
template<typename T>
class EnhancedLinkedList: public LinkedList<T>
{
public:
T& find_first (const T& key);
//Method find_first should search the EnhancedLinkedList for the first
//occurrence of an item that matches the value in the parameter key.
//It should return a reference to the first matching item.
//If the invoking EnhancedLinkedList object is empty or no item is found
//that matches the parameter, a ListItemNotFoundException should be thrown.
//You will have to define this exception
//(Hint: define this exception much the same way that the
//EmptyListException exception is defined in LinkedList.h).
EnhancedLinkedList find_all (const T& key);
//Method find_all should search the invoking EnhancedLinkedList
//for all elements that match the value in the parameter key.
//It should return an EnhancedLinkedList object containing
//copies of all the items that match the parameter key.
//If the invoking EnhancedLinkedList object is empty or
//no item is found that matches the parameter,
//this function should return an empty EnhancedLinkedList.
void remove_first (const T& key);
//Method remove_first should remove the first element from the
//invoking EnhancedLinkedList whose data item matches the parameter key.
//If the invoking EnhancedLinkedList object is empty or no item is found
//that matches the parameter, this function should do nothing.
//Remember to leave no memory leaks.
void remove_all (const T& key);
//Method remove_all should remove all elements from the invoking
//EnhancedLinkedList whose data items match the parameter key.
//If the invoking EnhancedLinkedList object is empty or no item is found
//that matches the parameter, this function should do nothing.
//Remember to leave no memory leaks.
};
template<typename T>
T& EnhancedLinkedList<T>::find_first(const T& key)
{
Node<T>* temp = this->head;
if(temp == NULL)
throw EmptyListException("Find first emptylist");
while(NULL != temp->getNext())
{
if(temp->getData()==key)
return temp->getData();
else
temp=temp->getNext();
}
throw EmptyListException("Find first not found");
}
template<typename T>
EnhancedLinkedList<T>
EnhancedLinkedList<T>::find_all(const T& key)
{
EnhancedLinkedList<T> resualt;
Node<T>* temp = this->head;
while(NULL != temp)
{
if(temp->getData()==key)
resualt.push_back(temp->getData());
temp=temp->getNext();
}
end:
return resualt;
}
template<typename T>
void
EnhancedLinkedList<T>::remove_first(const T& key)
{
EnhancedLinkedList<T> list;
while(NULL!=this->head)
{
if(this->head->getData()!=key)
list.push_front(this->head->getData());
else{
T* temp = this->front();
this->pop_front();
delete temp;
break;
}
this->pop_front();
}
while(list.head!=NULL)
{
this->push_front(list.front());
list.pop_front();
}
}
template<typename T>
void
EnhancedLinkedList<T>::remove_all(const T& key)
{
EnhancedLinkedList<T> list;
while(NULL!=this->head)
{
if(this->head->getData()!=key){
list.push_front(this->head->getData());
this->pop_front();
}
else{
T* temp = this->front();
this->pop_front();
delete temp;
}
}
while(list.head!=NULL)
{
this->push_front(list.front());
list.pop_front();
}
}
#endif //_ENHANCELINKLIST_H_