/* the main purpose of this lab is to learn how to use recursion to prcesses lists.*/

public  class SinglyLinkedList<E extends Comparable<E>> {

    private static class Node<E> {
        private E value;
        private  Node<E> next;

        private Node(E value,Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    // Instance variable
    private Node<E> head;

    // ----------------------------------------------------------
    // SinglyLinkedList methods
    // ----------------------------------------------------------
    /* returns true if the list is empty*/
   
    public boolean isEmpty() {
        return head == null;
    }

    public void addfirst(E item) {
    //this method will be use to populate the list
        if (item == null) {
            throw new NullPointerException("Illegal argument");
        }

        head = new Node<E>(item, head);
    }

/********************************************************************************/
    //The recursive method  size  returns the number of nodes in the list
    // ----------------------------------------------------------
    public int size(){
       // the public size method calls a private recursive method size starting from head
        return size(head);

    }
    private int size(Node <E> p){
         //complete this method

    }
    /********************************************************************************/
    //The recursive method  get returns the element at position index (first element is at position 0)
    // ----------------------------------------------------------
    public E get( int index ){
        if ( index < 0 )
            return null;
        else
            return .....;// make a call to the private recursive method
    }
    private E get( Node<E> p, int index ) {
       
    }   
    /********************************************************************************/
    //The recursive method  contains returns true if the list contains value
    // ----------------------------------------------------------
    public boolean contains( E value ){
        //conplete this method
    }
    private boolean contains( Node<E> p, E value ) {
        //complete this method
    }       
   
/******************************************************************************************************************/
//The recursive method  countGreaterThan returns the number of nodes  that are larger than a given value threshold in the list
    // ----------------------------------------------------------
    public int countGreaterThan(E threshold) {
      //complete this method
    }

    private int countGreaterThan(E threshold, Node<E> node){
        if (node == null)
            return 0;
        if(node.value.compareTo(threshold) >= 1)
            return ;//return the correct value
        else 
            return countGreaterThan(threshold, node.next);
    }
   
/******************************************************************************************************************/
//The recursive method  findMax returns the maximum value in the list
    // ----------------------------------------------------------
     
    public E findMax() {
         
          if ( head == null ){
              return null;
          }
          else{
                return findMax( head );
           
            }
    }
    private E findMax( Node<E> p ) {
        //complete this method
    }
   
        /*******************************************************************************/
        //A recursive method  to remove  the first occurence of element o
        ///////////////////////////////////////////////////////////////////   
    public void remove( E o ) {
        if ( head!= null){
            if(head.value.compareTo(o) ==0) {
                Node <E> temp=head;
                temp.value=null;
                temp.next=null;
                head = head.next;
            }
            else remove( head, o );
        }
    }
    private void remove( Node<E> p, E o ) {
        if ( p.next == null ){
             return; // we could not find o in the list
        }
        if (p.next.value.compareTo( o )==0 ) {
            Node <E> temp=p.next;
            p.next = p.next.next;
            temp.value=null;
            temp.next=null;
            return;
        }
        else{
              ;// complete this method to keep searching for more to delete
        };
       
    }
/********************************************************************************/
    //A recursive method  duplicate that returns a new list which is similar to the current list but with one item duplicated
    //////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public SinglyLinkedList<E> duplicate(E item) {
        return duplicate(item, head);
    }

    private SinglyLinkedList<E>  duplicate(E item, Node<E> node){
       //complete this method
    }
//______________________________________________________________________________________
    //storeGreaterThan returns a list with only the elements that are larger than  the threshold
//////////////////////////////////////////////////////////////////////////   
    public SinglyLinkedList<E> storeGreaterThan(E threshold) {
        return storeGreaterThan(threshold, head);
    }

    private SinglyLinkedList<E> storeGreaterThan(E threshold, Node<E> node){
        if (node == null)
            return new SinglyLinkedList<E>();
        else{
           //complete this method
       
        return result;
        }
    }
   
 
/************************************************************************/
    @Override
    the method equals compares two lists and returns true if they contain the same elements
   
    ///////////////////////////////////////////////////////
    public boolean equals(Object obj) {
        if (!(obj instanceof SinglyLinkedList<?>)) {
            return false;
        }
        if(obj== this){
        return true;}
        else
        return equals((SinglyLinkedList<?>) obj);
    }
     public boolean equals(SinglyLinkedList<E> other) {
      return equals(this.head, other.head);
     }

    private boolean equals(Node <E> p, Node <E> q){
     if(p==null){
       if( q== null){
       return true;
       }
       else{
       return false;
       }
     }
       else{
       if(p.value.compareTo(q.value)==0)
         return equals(p.next, q.next);
        else
        return false;
       }
    }
       
        
    @Override
    public String toString() {
        return "{" +(mytoString(head)) + "}";
    }

    private String mytoString(Node<E> p) {

        String result = "";

        if (p != null) {
               if(p.next!=null){
                    result = p.value + "," + mytoString(p.next);
               }else{
                       result = ""+p.value ;
                  
               }
           
        }

        return result;
    }
   
   
    ///////////////////////////////////////////////////////////
    /*testing your methods*/
    public static void main (String [] arguments) {
        SinglyLinkedList<Integer>  mylist= new SinglyLinkedList<Integer>();
        SinglyLinkedList<Integer>  yourlist= new SinglyLinkedList<Integer>();
        System.out.println (mylist);
        mylist.addfirst(15);
        mylist.addfirst(17);
        mylist.addfirst(3);
        mylist.addfirst(22);
        mylist.addfirst(90);
        mylist.addfirst(12);   
        mylist.addfirst(38);
        mylist.addfirst(25);
        System.out.println ("Here is my list: "+mylist);
       
        //uncomment all the following statements as you finish implementing the corresponding methods.
        //System.out.println ("the size of my list is: "+ mylist.size());
        //System.out.println ("if you are wondering if the list contains 22 the answer is "+ mylist.contains(22 ));
        //System.out.println ("if you are wondering if the list contains 23 the answer is "+ mylist.contains(23 ));
        //System.out.println ("if you are wondering about the element at postition 4, it is:  "+ mylist.get(4 ));
        //System.out.println ("if you are wondering about the element at postition 0, it is:  "+ mylist.get(0 ));
       
        //System.out.println ("the number of elements larger than 10 is "+ mylist.countGreaterThan(10));
        //System.out.println ("the number of elements larger than 30 is "+ mylist.countGreaterThan(30));
        //System.out.println ("the largest element is                  "+ mylist.findMax());
        //yourlist=mylist.duplicate(90);
        //System.out.println ("Here is your new list with 90 duplicated: "+yourlist);
        //System.out.println ("if you are wondering if your list is similar to mine, the answer is:" +mylist.equals(yourlist));
        //System.out.println ("if you are wondering if my list is similar to your, the answer is:" +yourlist.equals(mylist));
        //yourlist.remove(90);
        //System.out.println ("Here is your new list with 90 removed: "+yourlist);
        //System.out.println ("if you are wondering if your list is similar to mine, the answer is:" +mylist.equals(yourlist));
        //System.out.println ("if you are wondering if my list is similar to your, the answer is:" +yourlist.equals(mylist));
        //System.out.println ("Here is your new list: "+yourlist);
         //yourlist=yourlist.storeGreaterThan(20);
         //System.out.println ("Here is your new list with only the numbers that are larger than 20: "+yourlist);
        
    }
       
}