//package application;
//Assignment #: 10
//Name:Raphael David
//StudentID: 1214549752
//Lab Lecture: MWF 9:40
//A linked list is a sequence of nodes with efficient
//element insertion and removal.
//This class contains a subset of the methods of the
//standard java.util.LinkedList class.


import java.util.NoSuchElementException;

public class LinkedList
{
//nested class to represent a node
private class Node
{
       public Object data;
       public Node next;
}

//only instance variable that points to the first node.
private Node first;

// Constructs an empty linked list.
public LinkedList()
{
   first = null;
}


// Returns the first element in the linked list.
public Object getFirst()
{
   if (first == null)
    {
      NoSuchElementException ex
          = new NoSuchElementException();
      throw ex;
    }
   else
      return first.data;
}

// Removes the first element in the linked list.
public Object removeFirst()
{
   if (first == null)
    {
      NoSuchElementException ex = new NoSuchElementException();
      throw ex;
    }
   else
    {
      Object element = first.data;
      first = first.next;  //change the reference since it's removed.
      return element;
    }
}

// Adds an element to the front of the linked list.
public void addFirst(Object element)
{
   //create a new node
   Node newNode = new Node();
   newNode.data = element;
   newNode.next = first;
   //change the first reference to the new node.
   first = newNode;
}

// Returns an iterator for iterating through this list.
public ListIterator listIterator()
{
   return new LinkedListIterator();
}


/*********************************************************
Add your methods here

*********************************************************/
public String toString()
{
	String result = "[ ";
	ListIterator li = this.listIterator();

	while(li.hasNext() == true) {
		result += li.next() + " ";//adds the list of objects

	}
	result += "]\n";
	return result;
}

public boolean isEmpty() {
	ListIterator li = this.listIterator();

	if(li.hasNext() == true) {// if the next element is not empty, return false
		return false;

	}
	else {
		return true;
	}

}

public void addElementAt(Object element, int index) {

	ListIterator li = this.listIterator();


	if(index < 0) {
		throw new IndexOutOfBoundsException();
	}
	for (int i = 0; i < index ; i ++) { // iterate until i reaches index
		if(li.hasNext()) {
			li.next();}
		else { // must be within bounds
			throw new IndexOutOfBoundsException();
		}

	}
	li.add(element);
}

public void removeElementAt(int index) {

	ListIterator ab = this.listIterator();
	//get size
	int size = 0;
	while(ab.hasNext() != false) {
		size++;
		ab.next();
	}
	ListIterator li = this.listIterator();
	Object temp = new Object();



	if (index != 0 && index > -1) {
		for (int i = 0; i <= index ; i ++) {
			// iterate until i reaches index
			if (li.hasNext() && index <= size) {
				li.next();
			}
			else {
				throw new IndexOutOfBoundsException();


			}
		}


		li.remove();


	}
	else {
		if(index > -1) {
		li = this.listIterator();

	//if index = 0
	//removes head by changing first to
	//temp and moving first to next index
		this.removeFirst();
		li.next();
	}
		else {
			throw new IndexOutOfBoundsException();
		}

	}

	}

public String getElement(int index) {
	ListIterator li = this.listIterator();

	//throwing errors
	// if  index is less than 0
	if ( index < 0 ) {
		throw new IndexOutOfBoundsException();
	}

	for (int i = 0; i < index ; i ++) { // iterate until i reaches index
		if(li.hasNext()) {
			li.next();
			}
		else {
			throw new IndexOutOfBoundsException();

		}
	}
	return li.next().toString();

}

public String findSmallestAndRemove() { //this one i need help w

	//if current node is smaller than the next, set equal to smallest
	//compare next node to smallest
	ListIterator li = this.listIterator();


	String smallest = "";
	String current = "";
	//String temp = "";

	int size = 0;
	while(li.hasNext() != false) {
		size++;
		li.next();
	}


	if(isEmpty()) {
		return null;
	}
	ListIterator op = this.listIterator();

	for (int i =0; i< size ; i++) {
		//if index is at zero then smallest is the current
		if(i == 0) {
			current = op.next().toString();
			smallest = current;

		}
		//then keep making the current one the next one
		else {
			current = op.next().toString();
		}

		//if the length of the current is less than the smallest, then make current smallest
		if(current.toString().compareTo(smallest.toString()) < 0 )
		{
			smallest = current;
		}

	}

	ListIterator ob = this.listIterator();
	//code to remove
	for (int i =0; i< size; i++) {
		current = ob.next().toString();
		//if curretn is the smallest, remove it
		if(current.compareTo(smallest) == 0)
		{
			ob.remove();
		}

	}


	return smallest.toString();


}

public int countHowManyStringsWithGivenLength(int length) {
	ListIterator li = this.listIterator();
	//get size
	int size = 0;
	while(li.hasNext() != false) {
		size++;
		li.next();


	}
	ListIterator counter = this.listIterator();
	//inc count if string length = parameter length
	int count = 0;
	for (int i =0; i < size; i++) {
		if(counter.next().toString().length() == length) {
			count++;
		}
	}
	return count;
}

public void duplicateFirstSome(int howMany) {

	//duplicates the howMany elements
	String temp = "";
	//need a temp variable
	//temp will be equal to the element in the array you want to copy
	//copy elemetn into temp and insert it at index
	ListIterator ab = this.listIterator();
	//get size
	int size = 0;
	while(ab.hasNext() != false) {
		size++;
		ab.next();
	}

	ListIterator li = this.listIterator();

	if(li.hasNext() && howMany <= size) {

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

			temp = li.next().toString();
			li.add(temp);

	}



	}

	li = this.listIterator();
	if (howMany > size) {
		for (int i = 0;i <  size; i++) {

					temp = li.next().toString();
					li.add(temp);

	}
	}



}
//nested class to define its iterator
private class LinkedListIterator implements ListIterator
{
   private Node position; //current position
   private Node previous; //it is used for remove() method

   // Constructs an iterator that points to the front
   // of the linked list.

   public LinkedListIterator()
   {
      position = null;
      previous = null;
   }

  // Tests if there is an element after the iterator position.
  public boolean hasNext()
   {
      if (position == null) //not traversed yet
       {
          if (first != null)
             return true;
          else
             return false;
       }
      else
        {
           if (position.next != null)
              return true;
           else
              return false;
        }
   }

   // Moves the iterator past the next element, and returns
   // the traversed element's data.
   public Object next()
   {
      if (!hasNext())
       {
        NoSuchElementException ex = new NoSuchElementException();
        throw ex;
       }
      else
       {
         previous = position; // Remember for remove

         if (position == null)
            position = first;
         else
            position = position.next;

         return position.data;
       }
   }

   // Adds an element after the iterator position
   // and moves the iterator past the inserted element.
   public void add(Object element)
   {
      if (position == null) //never traversed yet
      {
         addFirst(element);
         position = first;
      }
      else
      {
         //making a new node to add
         Node newNode = new Node();
         newNode.data = element;
         newNode.next = position.next;
         //change the link to insert the new node
         position.next = newNode;
         //move the position forward to the new node
         position = newNode;
      }
      //this means that we cannot call remove() right after add()
      previous = position;
   }

   // Removes the last traversed element. This method may
   // only be called after a call to the next() method.
   public void remove()
   {
      if (previous == position)  //not after next() is called
       {
         IllegalStateException ex = new IllegalStateException();
         throw ex;
       }
      else
       {
        if (position == first)
         {
           removeFirst();
         }
        else
         {
           previous.next = position.next; //removing
         }
        //stepping back
        //this also means that remove() cannot be called twice in a row.
        position = previous;
   }
   }

   // Sets the last traversed element to a different value.
   public void set(Object element)
   {
      if (position == null)
       {
         NoSuchElementException ex = new NoSuchElementException();
         throw ex;
       }
      else
       position.data = element;
   }
} //end of LinkedListIterator class
} //end of LinkedList class