/*
  
  Name: Owen Sullivan
  Date Submitted: 9/7/22
  Lab Section: 006
  Assignment Name: Lab 1: Linked List Based Stacks and Queues

*/

#ifndef LIST_
#define LIST_

#include <iostream>
#include <string>

#include "Node.h"

using namespace std;

// This class represents a linked list of node objects
// Do not modify anything in the class interface
template <class T>
class List {
  
  private:
    Node<T> *start; // pointer to the first node in this list
    int mySize; // size (or length) of this list

  public:
    List();
    ~List();
    int size();
    bool empty();
    void insertStart(T);
    void insertEnd(T);
    void insertAt(T, int);
    void removeStart();
    void removeEnd();
    void removeAt(int);
    T getFirst();
    T getLast();
    T getAt(int);
    int find(T);

  // Print the name and this list's size and values to stdout
  // This function is already implemented (no need to change it)
  void print(string name){
    
    cout << name << ": ";
    cout << "size = " << size();
    cout << ", values = ";
    
    Node<T> *iterator = start;
    
    while (iterator != nullptr) {
      
      cout << iterator->value << ' ';
      iterator = iterator->next;
    
    }
    
    cout << endl;
  
  }

}; // end of class interface (you may modify the code below)

// Implement all of the functions below

// Construct an empty list by initializig this list's instance variables
template <class T>
List<T>::List() {

  // Set the start node to nullptr, and set
  // mySize to 0 for counting size later on.
  
  start = nullptr;
  mySize = 0;

}

// Destroy all nodes in this list to prevent memory leaks
template <class T>
List<T>::~List() {

  // Remove each node procedurally from the end, checking
  // that the list is not empty before removing.

  while (!empty()) {

    removeStart();

  }

}

// Return the size of this list
template <class T>
int List<T>::size() {

  // This one is pretty self-explanatory, I think.

  return mySize;

}

// Return true if this list is empty
// Otherwise, return false
template <class T>
bool List<T>::empty() {

  // Check if the start node is equal to nullptr, return
  // true or false accordingly. Also self-explanatory.
  
  if (start == nullptr) {

    return true;

  } else {

    return false;

  }

}

// Create a new node with value, and insert that new node
// into this list at start
template <class T>
void List<T>::insertStart(T value) {

  // Create a placeholder node using the Node constructor (of type T), then
  // set the node after newNode to the current start node and set the
  // current start node to the placeholder newNode.

  Node<T> *newNode = new Node<T>(value);
  
  newNode->next = start;
  start = newNode;

  // Increment size
  mySize++;

}

// Create a new node with value, and insert that new node
// into this list at end
template <class T>
void List<T>::insertEnd(T value) {

  // Create a placeholder node using the Node constructor (of type T), then
  // check to make sure the list isn't empty. If the list is empty, set the
  // start node to the placeholder newNode. If the list isn't empty, create
  // a temp node with the value of the current start node and iterate through
  // the nodes in the list until the last node is reached; then, set the node
  // after the temp node to the placeholder new node.
  
  Node<T> *newNode = new Node<T>(value);

  if (empty()) {

    start = newNode;

  } else {

    Node<T> *temp = start;
    
    while (temp->next != nullptr) {

      temp = temp->next;

    }
    temp->next = newNode;

  }

  // Increment size
  mySize++;

}

// Create a new node with value <value>, and insert that new node at position j
template <class T>
void List<T>::insertAt(T value, int j) {

  // Create a placeholder node and a temp node using the Node constructor
  // (of type T), then check that you aren't trying to insert at the beginning
  // (we already have a function for that). Loop through the nodes in the list until the position
  // one less than j (because using temp->next will go to the provided position).
  // Set the node after newNode to the node after temp, then the node after
  // temp to newNode. Shifts everything down one after insertion.

  Node<T> *newNode = new Node<T>(value);
  Node<T> *temp = start;

  if (j == 0) {

    insertStart(value);

  } else {

    for (int i = 0; i < (j - 1); i++) {

      if (temp->next != nullptr) {

        temp = temp->next;

      }

    }
    newNode->next = temp->next;
    temp->next = newNode;

    // Increment size
    mySize++;

  }

}

// Remove node at start
// Make no other changes to list
template <class T>
void List<T>::removeStart() {

  // Set the value of the start node to the node after start. This removes
  // the current start node without the need to manually shift every
  // following node back one (which I, an idiot, originally tried).
  
  if (empty()) {

    return;

  }
  
  Node<T> *temp = start;
  
  start = start->next;

  delete temp;

  // Decrement size
  mySize--;

}

// Remove node at end
// Make no other changes to list
template <class T>
void List<T>::removeEnd() {

  // Create a temp node and loop through the nodes in the list until
  // the node after the node after the temp node (confusing, but this
  // gives you the node immediately prior to the last node which is
  // nullptr). Then, set the node after temp to nullptr. This erases
  // the last node.

  if (empty()) {

    return;

  }
  
  Node<T> *temp = start;

  if (temp->next != nullptr) {

    while (temp->next->next != nullptr) {

      temp = temp->next;

    }

    delete temp->next;

    temp->next = nullptr;

    // Decrement size
    mySize--;

  } else {

    removeStart();

  }

}

// Remove node at position j
// Make no other changes to list
template <class T>
void List<T>::removeAt(int j) {

  // Create a temp node and loop through the nodes in the list until
  // the node before the node at position j (same situation as in 
  // insertAt()). Set the node after temp to the node after the node
  // after temp (a mouthful, again). This shifts all nodes after the
  // deleted one up by one.
  
  Node<T> *temp = start;
  Node<T> *temp2;

  if (j == 0) {

    removeStart();

  } else if (j > mySize) {
    
    removeEnd();

  } else {

    for (int i = 0; i < (j - 1); i++) {

      if (temp->next != nullptr) {

        temp = temp->next;

      }

    }
    
    temp2 = temp->next;

    temp->next = temp->next->next;

    delete temp2;

    // Decrement size
    mySize--;

  }

}

// Return the value of the first node in the Linked List,
// If no first node, return the default constructed value: T()
template <class T>
T List<T>::getFirst() {

  // Check that list isn't empty, then return the value of the start
  // node if not.
  
  if (!empty()) {

    return start->value;

  } else {

    return T();

  }

}

// Return the value of the last node in the Linked List,
// If no first node, return the default constructed value: T()
template <class T>
T List<T>::getLast() {

  // Check that the list isn't empty, then if not create a temp node
  // and loop through until the last node in the list. Then, return
  // the value of the temp node (the last value).
  
  if (!empty()) {

    Node<T> *temp = start;

    while (temp->next != nullptr) {

      temp = temp->next;

    }
    return temp->value;

  } else {

    return T();

  }

}

// Return the value of the node at position j in the Linked List,
// If no first node, return the default constructed value: T()
template <class T>
T List<T>::getAt(int j) {

  // Check that the list isn't empty, then if not create a temp node
  // and loop through until the node at position j. Then, return
  // the value of the temp node (the value at position j).
  
  if (!empty()) {

    Node<T> *temp = start;

    for (int i = 0; i < j; i++) {

      temp = temp->next;

    }
    return temp->value;

  } else {

    return T();

  }

}

// Return the position of the (first) node whose value is equal to the key
// Otherwise, return -1
template <class T>
int List<T>::find(T key) {

  // Create a temp node and a counter that holds the current position
  // in the loop, then loop through each node in the list until the
  // value of the temp node matches the provided key. If there's a
  // match, return it. If not, increment the pos counter. If by the
  // end of the loop there isn't a match, return -1.
  
  Node<T> *temp = start;
  int pos = 0;

  while (temp->next != nullptr) {

    if (temp->value == key) {

      return pos;

    } else {

      pos++;

    }
    temp = temp->next;

  }

  return -1;

}

#endif