import java.util.NoSuchElementException;

public class LinkedListOfEmployees
{
    private class Node
    {
        private Employee data;
        private Node link;

        public Node( )
        {
             data = null;
             link = null;
        }

        public Node(Employee newData, Node linkValue)
        {
            data = newData;
            link = linkValue;
        }
      }//End of Node inner class

     /**
      If the list is altered any iterators should invoke restart or
      the iterator's behavior may not be as desired.
     */
     public class EmployeeIterator
     {
         private Node position;
         private Node previous;//previous value of position

         public EmployeeIterator()
         {
             position = head; //Instance variable head of outer class.
             previous = null;
         }

         public void restart()
         {
             position = head; //Instance variable head of outer class.
             previous = null;
         }

         public Employee next( )
         {
            if (!hasNext())
                throw new NoSuchElementException();

            Employee toReturn = (Employee)((position.data).clone());
            previous = position;
            position = position.link;
            return toReturn;
         }

         public boolean hasNext(  )
         {
            return (position != null);
         }

        /**
         Returns the next value to be returned by next().
         Throws an IllegalStateExpression if hasNext() is false.
        */
        public Employee peek()
        {
             if (!hasNext())
                throw new IllegalStateException();
             return (Employee)((position.data).clone());
        }

        /**
         Adds a node before the node at location position.
         previous is placed  at the new node.If hasNext() is
         false, then the node is added to the end of the list.
         If the list is empty, inserts node as the only node.
        */
        public void add(Employee newData)
        {
            if (position == null && previous != null)
            //if at end of list
                previous.link =
                             new Node(newData, null);
            else if (position==null || previous==null)
            //else if list is empty or position is at head node.
                LinkedListOfEmployees.this.add(newData);
            else//previous and position are located
                //at two consecutive nodes.
            {
                Node temp = new Node(newData, position);
                previous.link = temp;
                previous = temp;
            }
        }

        /**
         Deletes the node at location position and
         moves position to the "next" node.
         Throws an IllegalStateException if the  list is empty.
        */
        public void delete(  )
        {
            if (position == null)
                throw new IllegalStateException();
            else if (previous == null)
            {//remove node at head
                head = head.link;
                position = head;
            }
            else //previous and position are at two nodes.
            {
                previous.link = position.link;
                position = position.link;
            }
         }
     }//End of EmployeeIterator inner class



    private Node head;


    public EmployeeIterator iterator()
    {
        return new EmployeeIterator();
    }

    public LinkedListOfEmployees( )
    {
        head = null;
    }

    /**
     Throws a NullPointerException if other is null. Produces a completely
     independent copy with no referenes in common with otherList
    */
    public LinkedListOfEmployees(LinkedListOfEmployees otherList)
    {
         if (otherList == null)
             throw new NullPointerException( );
         if (otherList.head == null)
             head = null;
         else
             head = copyOf(otherList.head);
    }

    //Precondition: otherHead != null
    //Returns a reference to the head of a copy of the
    //list headed by otherHead. Does a deep copy.
    private Node copyOf(Node otherHead)
    {
        Node position = otherHead;//moves down other’s list.
        Node newHead; //will point to head of the copy list.
        Node end = null; //positioned at end of new growing list.
        //Create first node:
        newHead =
              new Node((Employee)((position.data).clone( )), null);
        end = newHead;
        position = position.link;

        while (position != null)
        {//copy node at position to end of new list.
            end.link =
                new Node((Employee)((position.data).clone( )), null);
            end = end.link;
            position = position.link;
        }

        return newHead;
    }

    public Object clone( )
    {
        try
        {
            LinkedListOfEmployees copy =
                              (LinkedListOfEmployees)super.clone( );
            copy.head = copyOf(this.head);
            return copy;
        }
        catch(CloneNotSupportedException e)
        {//This should not happen.
            return null; //To keep the compiler happy.
        }
    }

    /**
     Adds a node at the head of the list with the newData.
    */
    public void add(Employee newData)
    {
        head = new Node(newData, head);
    }

    /**
     Removes the head node and returns true if the list contains at least
     one node. Returns false if the list is empty.
    */
    public boolean deleteHeadNode( )
    {
        if (head != null)
        {
            head = head.link;
            return true;
        }
        else
            return false;
    }

    /**
     Returns the number of nodes in the list.
    */
    public int size( )
    {
        int count = 0;
        Node position = head;
        while (position != null)
        {
            count++;
            position = position.link;
        }
        return count;
    }

    public boolean contains(Employee target)
    {
        return (find(target) != null);
    }

    /**
     Finds the first node containing the target item, and returns a
     reference to that node. If target is not in the list, null is returned.
    */
    private Node find(Employee target)
    {
        Node position = head;
        Employee dataAtPosition;
        while (position != null)
        {
            dataAtPosition = position.data;
            if (target.equals(dataAtPosition))
                return position;
            position = position.link;
        }
        return null; //target was not found
    }

    public boolean isEmpty( )
    {
        return (head == null);
    }

    public void clear( )
    {
        head = null;
    }

    public boolean equals(Object otherList)
    {
        if (otherList == null)
            return false;
        else if (getClass( ) != otherList.getClass( ))
            return false;
        else if (size( ) != ((LinkedListOfEmployees)otherList).size( ))
            return false;
        else
            return compareLists((LinkedListOfEmployees)otherList);
    }

    //Precondition: size( ) == otherList.size( ).
    //Returns true if node by node, objects are equal.
    private boolean compareLists(LinkedListOfEmployees otherList)
    {
        boolean match = true;//so far
        Node position = head;
        Node otherPosition = otherList.head;

        while (match && position != null)
        {
              if (!position.equals(otherPosition))
                  match = false;
              position = position.link;
              otherPosition = otherPosition.link;
        }
        return match;
    }

    public void outputList( )
    {
        Node position = head;
        while (position != null)
        {
            System.out.println(position.data);
            position = position.link;
        }
    }

}