#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 */