#ifndef LINKED_LIST_CS197
#define LINKED_LIST_CS197

#include <cassert>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <iostream> //cin, cout, <, >
#include <stdarg.h>

using namespace std;

template<typename T>
class LinkedList {
private:
  class iterator {
    void operator++() const {
      // Does nothing right now
    }

    // Need to add data structures internal to the iterator here
  };

  // This class is basically complete. You shouldn't need to modify it.
  class Node {
  public:
    Node() { next = NULL; prev = NULL; }
    ~Node() {}
  public :
    Node *next;
    Node *prev;
    T data;
  };

  // Add internal strcutures for the list here

public:
  LinkedList();
  ~LinkedList();
   /* -References to the first and last
   */
  Node *first;
  Node *last;
  Node* curr;
  int sizeCounter;
  // methods -- note that the return values are of type T. Don't return a Node!
  void append(T item);
  T get(int idx);
  void insert(int idx, T item);
  void map(T (*pf)(T item));
  T remove(int index);
  int size();
  void unshift(T item);
  void displayForward();

  // Iterator methods - not very interesting right now

  // These need to return new iterators to the beginning, and AFTER the
  // end of, the sequence, respectively.
  const iterator begin() {
    return NULL;
  }

  const iterator end() {
    return NULL;
  }
};

// This returns a new, empty Linked List.
template <typename T>
LinkedList<T>::LinkedList() {
    this->curr = new Node();
    this->sizeCounter = 0;
    first = this->curr;
}

// Deletes the Linked List. It's not your job to call delete on the
// T item directly because you don't know what it is, but you are still responsible
// for any internal data strcutures you may have allocated.
template <typename T>
LinkedList<T>::~LinkedList() {
}

// Adds an item to the end of the sequence (after the tail).
// If the list is empty, then the appended item becomes the head AND the tail.
template <typename T>
void LinkedList<T>::append(T item) {

    Node* temp = new Node();

    if(sizeCounter == 0)
    {
        this->curr->data = item;
        this->curr->next = new Node(); // create a new next node, i dont think this is necessary but w/e works man
        this->curr = this->curr->next;
        first = this->curr;
        ++sizeCounter;
    }
    else
    {
   // cout<<"|"<<item;
    while(this->curr->next != NULL)
        this->curr = this->curr->next;


    temp = this->curr; //temp to copy current node to so that it can be ref to by prev in the next node

    this->curr->next = new Node(); // create a new next node, i dont think this is necessary but w/e works man

    this->curr = this->curr->next;  //increment to the next empty node

    //TO make sure this is not the first node so we don't create a prev ref for it
    this->curr->prev = new Node(); //set prev node ref
    this->curr->prev = temp;
    this->curr->data = item; //set the data item
//       cout<<"->"<<this->curr->data<<" ";;
//   cout<<"Prev was:"<<this->curr->prev->data<<"|";

    ++sizeCounter;
    }
}

// Returns the item at position idx (0 returns the head).
// You should perform a range check before servicing the request.
template <typename T>
T LinkedList<T>::get(int idx) {

    assert(idx >= 0 && idx < sizeCounter);

    this->curr = first;

    for(int i = 0; i<idx; i++)
        this->curr = this->curr->next;

        return this->curr->data;
}

// Inserts an item at position idx. If idx is off the end of the sequence,
// it should just append to the end of the sequence. A negative index number
// results in an unshift.
template <typename T>
void LinkedList<T>::insert(int idx, T item) {
    this->curr = first;
    if(idx >= 0 && idx < sizeCounter)
    {
        for(int i = 0; i<idx; i++)
            this->curr = this->curr->next;
        this->curr->data = item;
    }
    else if(idx < 0){unshift(item);}
    else if(idx >= sizeCounter){append(item);}
}

// Executes the provided function pointer over all
// elements in the sequence. Each item should be modified in place.
template <typename T>
void LinkedList<T>::map(T (*pf)(T item)) {
    this->curr = first;
    this->curr->data = (*pf)(this->curr->data);
    while(this->curr->next != NULL)
    {
        this->curr = this->curr->next;
        this->curr->data = (*pf)(this->curr->data);
    }

}

// Removes the item at position 'index'. The removed item should be
// returned.
// A range check should be performed before servicing the request,
// therefore this method always returns a value.
template <typename T>
T LinkedList<T>::remove(int index) {
   T removedItem;
    assert(index >= 0 && index < sizeCounter);
    this->curr = first;
    for(int i = 0; i<index; i++)
       this->curr = this->curr->next;

    removedItem = this->curr->data;
    if(this->curr->prev != NULL)
    {
        Node* temp = this->curr->next;
        this->curr = this->curr->prev;
        this->curr->next = temp;
    }
        else
            this->curr = this->curr->next;
    --sizeCounter;
            return removedItem;
}

// Returns the number of items in the sequence. This should
// complete in constant time.
template <typename T>
int LinkedList<T>::size() {
    return sizeCounter;
}

// Behaves like append, but inserts the item at the front of the sequence.
// Therefore the unshifted item becomes the new head of the sequence.
template <typename T>
void LinkedList<T>::unshift(T item) {
    Node* temp = new Node();
    this->curr = first;
    this->curr->prev = new Node();
    this->curr = this->curr->prev;
    this->curr->data = item;
    this->curr->next = first;

    temp = this->curr;
    first->prev = temp;
    first = temp;
    sizeCounter++;
}
/*  Editional method to display all items of linked list
 */
template <typename T>
void LinkedList<T>::displayForward() {
    cout<<"List (first-->last): ";
    this->curr = first;

    while(this->curr != NULL)
    {
        cout<<" "<<this->curr->data;
        this->curr = this->curr->next;
    }
    cout<<endl;
}
#endif