package labs.linkedlists;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Singly-linked list implementation of the CS 240 List interface.
 *
 * This interface stores a head reference, but no tail. Therefore adding or
 * removing items at the end of the list will require O(n) steps.
 *
 * @author CS 240 Instructors and ???
 *
 */
public class SinglyLinkedList<E> implements SimpleList<E> {

  private Node head;
  private int size;

  /**
   * Private inner Node class.
   */
  private class Node {

    private Node next;
    private E item;

    public Node(Node next, E item) {
      this.next = next;
      this.item = item;
    }
  }

  /**
   * Construct an empty list.
   */
  public SinglyLinkedList() {
    head = null;
    size = 0;
  }

  /**
   * Helper method for obtaining the Node at a particular index. Helpful for get
   * and add. This method has a Theta(n) time complexity, so it should be used
   * sparingly.
   * 
   * @throws IndexOutOfBoundsException if the provided index is out of bounds.
   */
  private Node getNode(int index) {

    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }

    // UNFINISHED
    //
    // This should be implemented by creating a local variable named something like
    // "curNode" that will be initialized to the head of the list. Use a for loop to
    // step forward the desired number of times by repeatedly assigning curNode.next
    // to curNode.
    //
    // Do NOT modify the head reference directly.
    

    return null;
  }

  @Override
  public E get(int index) {
    return getNode(index).item;
  }

  @Override
  public void add(E item) {

    // UNFINISHED
    //
    // You can use getNode to obtain the last node in the list (what index is it at?)
    // and then modify its .next reference.
    //
    // However, if the list is empty (aka head is null), you should make a new head
    // node instead of using getNode.
    //
    // Don't forget to update the list size for both cases!

    
  }

  @Override
  public void addFirst(E item) {
    head = new Node(head, item);
    size++;
  }

  @Override
  public boolean contains(E item) {

    // UNFINISHED
    //
    // Perform a sequential search over the nodes in the list starting at the head.
    // Again, you should have a loop just like in getNode.
    //
    // Don't forget to compare the items in the nodes using .equals, not ==.

    
    return false;
  }

  @Override
  public void clear() {
    head = null;
    size = 0;
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public Iterator<E> iterator() {
    return new SinglyLinkedListIterator();
  }

  private class SinglyLinkedListIterator implements Iterator<E> {

    // UNFINISHED
    //
    // You should have a single Node as an instance variable. This reference will be
    // used to keep track of your position during iteration.
    //
    // Do NOT store an index variable.

    


    @Override
    public boolean hasNext() {

      // UNFINISHED
      //
      // Has this iterator reached the end of the list?

      return false;
    }

    @Override
    public E next() {

      // UNFINISHED
      //
      // Don't forget to throw a NoSuchElementException if there are no more elements
      // to return.

      return null;
    }
  }

  @Override
  public void remove(int index) {

    // UNFINISHED
    //
    // This method is a bit more complicated than the others. You will need to
    // consider three cases:
    //
    // 1. If the list is empty, you should throw a NoSuchElementException.
    //
    // 2. If you're trying to remove the first item in the list (index 0), make
    // sure to update the head reference!
    //
    // 3. In the general case, you will need to find the node BEFORE the node that
    // needs to be removed. This is because you will need to update the next
    // reference of the predecessor to point to the node AFTER the node that needs
    // to be removed.

    
  }

  @Override
  public String toString() {

    // FOR YOUR REFERENCE:

    StringBuilder sb = new StringBuilder();

    Node cur = head;
    while (cur != null) {
      sb.append(cur.item);
      sb.append(", ");
      cur = cur.next;
    }

    // Remove the last comma and space
    if (size > 0) {
      sb.setLength(sb.length() - 2);
    }

    // Add brackets
    sb.insert(0, "[");
    sb.append("]");

    return sb.toString();
  }
}