Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifndef _SALIST_H
- #define _SALIST_H
- #include <cstdlib>
- #include <iostream>
- #include <fstream>
- #include <cstring>
- using namespace std;
- template <class T>
- class SAList;
- template<class T>
- class Node
- {
- //data=Stores information of almost any data type- ie. char, int, double, etc
- //prev=the current node previous node
- //next=the current node next node
- // T data_;
- // Node<T> *prev_;
- // Node<T> *next_;
- public:
- T data_;
- Node<T> *prev_;
- Node<T> *next_;
- //Functions to return addresses of next and prev nodes and also to return a
- // reference of whatever is in data. Made class SAList a friend in order to
- //use the class to manipulate data within the double link list
- Node(T);
- const Node<T>* next() const;
- const Node<T>* prev() const;
- const T& data() const;
- template <class U> friend class SAList;
- };
- template<class T>
- class SAList
- {
- //front=pointed to the front of the double link list
- //back=pointed to the back of the double link list
- // Node<T> *head;
- // Node<T> *tail;
- public:
- Node<T> *head;
- Node<T> *tail;
- SAList();
- SAList(T*, int);
- SAList(const SAList&);
- SAList<T>& operator= (SAList<T> &);
- ~SAList();
- bool isEmpty() const;
- void insert(const T& data);
- bool remove(const T& key, bool (*match)(const T&,const T&));
- bool get(T passback[], int max) const;
- Node<T>* search(const T& key, bool (*match)(const T&,const T&));
- };
- //
- template<class T>
- Node<T>::Node(T info) {
- prev_=NULL;
- next_=NULL;
- data_=info;
- }
- template<class T>
- const Node<T>* Node<T>::next() const
- {
- return next_;
- }
- template<class T>
- const Node<T>* Node<T>::prev() const
- {
- return prev_;
- }
- template<class T>
- const T & Node<T>::data() const
- {
- // data_ = data;
- return data_;
- }
- template<class T>
- SAList<T>::SAList()
- {
- head = NULL;
- tail = NULL;
- }
- template<class T>
- SAList<T>::SAList(T* info, int size)
- {
- int i; //Counter
- Node<T> *temp;
- Node<T> *add;
- for(i=0;i<=size-1;i++)
- {
- add=new Node<T>(info[i]);
- if(head==NULL)
- {
- head=add;
- // add->prev_=tail;
- temp=head;
- }
- else
- {
- if(i==(size-1))
- tail=add;
- if(temp->next_==NULL)
- {
- temp->next_=add;
- add->prev_=temp;
- temp=temp->next;
- }
- }
- }
- }
- template<class T>
- SAList<T>::SAList(const SAList<T> &right)
- {
- Node<T> *current;
- Node<T> *previous;
- head = new Node<T>(right.head->data_);
- current = right.head->next_;
- while(current != NULL) {
- Node<T>* temp = new Node<T>(current->data_);
- if(head->next_ == NULL){
- head->next_ = temp;
- temp->prev_ = head;
- previous = temp;
- }
- else{
- temp->prev_ = previous;
- previous->next_ = temp;
- previous = temp;
- }
- current = current->next_;
- }
- }
- template <class T>
- SAList<T>& SAList<T>::operator= (SAList<T> &right){
- Node<T> *cur;
- Node<T> *temp;
- Node<T> *add;
- cur = right.head;
- while(cur != NULL)
- {
- add=new Node<T>(cur->data_);
- if(this->head==NULL)
- {
- head = add;
- add->prev_ = tail;
- cur = cur->next_;
- temp = head;
- }
- else
- {
- if(cur->next_==right.tail)
- {
- temp->next_=add;
- add->prev_=temp;
- tail=temp;
- temp=temp->next_;
- cur=cur->next_;
- }
- if(temp->next_==NULL)
- {
- temp->next_=add;
- add->prev_=temp;
- temp=temp->next_;
- cur=cur->next_;
- }
- }
- }
- return *this;
- }
- template<class T>
- SAList<T>::~SAList()
- {
- Node<T> *temp;
- while(head)
- {
- temp=head;
- head=head->next_;
- delete temp;
- }
- }
- template<class T>
- bool SAList<T>::isEmpty() const
- {
- //check is used to return true or false based on whether the list is empty
- //or not
- bool check;
- if(head!=NULL)
- {
- check=false;
- }
- else
- {
- check=true;
- }
- return check;
- }
- template<class T>
- void SAList<T>::insert(const T& data)
- {
- Node<T> *add;
- Node<T> *temp;
- add=new Node<T>(data);
- if(head==NULL)
- {
- head = add;
- }
- else
- {
- temp = head;
- head = add;
- head->next_ = temp;
- temp->prev_ = head;
- }
- }
- template<class T>
- bool SAList<T>::get(T passback [], int max) const
- {
- Node<T>* temp;
- bool check;
- int i=0;
- temp = head;
- while(temp != NULL && i < (max))
- {
- passback[i]=temp->data_;
- temp=temp->next_;
- i++;
- }
- if(i == (max))
- check=true;
- else
- check=false;
- return check;
- }
- template<class T>
- Node<T>* SAList<T>::search(const T& key, bool (*match)(const T&,const T&))
- {
- Node<T> *curr;
- bool stop = false;
- curr = head;
- Node<T>* n = curr->next_;
- Node<T>* p = curr->prev_;
- while(curr != NULL && stop != true) {
- if((*match)(curr->data_,key) == true) {
- if (p != NULL) {
- if(curr != NULL) {
- p = NULL;
- head->prev_ = curr;
- n = head;
- stop = true;
- }
- else {
- curr = p;
- n = NULL;
- }
- }
- if(stop == false) {
- curr = head->next_;
- }
- }
- }
- return curr;
- }
- /* while(curr != NULL && stop != true){
- if((*match)(curr->data_,key) == true){
- temp = curr;
- if(temp->prev_ != NULL) {
- if(temp != NULL){
- temp = temp->next_;
- temp->prev_ = curr->prev_;
- temp = temp->prev_;
- temp->next_ = curr->next_;
- curr->prev_ = NULL;
- head->prev_ = NULL;
- head = curr;
- head->next_ = curr->next_;
- }
- else{
- temp = temp->prev_;
- temp->next_ = NULL;
- }
- }
- stop = true;
- if(stop == false)
- curr = curr->next_;
- }
- return curr; */
- template<class T>
- bool SAList<T>::remove(const T& key, bool (*match)(const T&,const T&))
- {
- Node<T> *curr, *temp, *removed;
- bool retval, stop;
- while(curr != NULL && stop != true){
- if((*match)(curr->data_,key) == true){
- temp = curr;
- if(temp->prev_ != NULL){
- if(temp->next_ !=NULL){
- temp = temp->next_;
- temp->prev_ = curr->prev_;
- temp = temp->prev_;
- temp->next_ = curr->next_;
- }
- else{
- temp = temp->prev_;
- temp->next_ = NULL;
- }
- }
- else{
- if(head->next_ != NULL){
- head = head->next_;
- head->prev_ = NULL;
- }
- }
- stop = true;
- removed = curr;
- if(removed != NULL){
- delete removed;
- }
- retval = true;
- }
- curr = curr->next_;
- }
- }
- #endif /* _SALIST_H */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement