package LinkedList_Java;

/*
 this class is certainly NOT meant to be a full-featured
   List class.  It is for demonstration of concepts only. 4 methods implemented.
   Explain: printList, exe: find. Explain: insert, exe: delete.
*/

class StringList2 { //sorted string list

    // Internally, the list of strings is represented as a linked list
    // of nodes belonging to the nested class Node.  
   private class Node {
       String item;
       Node next;
   }
   
   private Node head; 
   
   public void printList() {
      Node runner;        // For traversing the list.
      runner = head;
     
      System.out.println("\nThe list contains:");
      runner = head;
      while (runner != null) {
         System.out.print(runner.item +" ");
         runner = runner.next;
        }
   } // end printList() 
   
   public boolean find(String searchItem) {
      Node runner;    // A pointer for traversing the list.
      
      runner = head;  // Start by looking at the head of the list.
      while ( runner != null ) {
         if ( runner.item.equals(searchItem) )
            return true;
         runner = runner.next;  // Move on to the next node.
        }
      
      return false;
   } // end find()
   
   public int indexOf(String searchItem){
       int index=0;
       Node runner;    // A pointer for traversing the list.
      
      runner = head;  // Start by looking at the head of the list.
      while ( runner != null ) {
         if ( runner.item.equals(searchItem) )
            return index;
         else{
            runner = runner.next;  // Move on to the next node.
            index++;
          }
        }
      
      return -1;
    }
    
   public String get(int index){ //every call to "get" has to run from the head
       int temp=0;
       Node runner;    // A pointer for traversing the list.
      
      runner = head;  // Start by looking at the head of the list.
      while ( temp!=index ) {
            runner = runner.next;  // Move on to the next node.
            temp++;
          }
      return runner.item;
    }
    
    public void set(int index, String newItem){ //every call to "get" has to run from the head
       int temp=0;
       Node runner;    // A pointer for traversing the list.
      
      runner = head;  // Start by looking at the head of the list.
      while ( temp!=index ) {
            runner = runner.next;  // Move on to the next node.
            temp++;
          }
      runner.item=newItem;
    }
    
   public void insert(String insertItem) {
      Node newNode;          // A Node to contain the new item.
      newNode = new Node();
      newNode.item = insertItem;  // (newNode.next is null.)
      
      if ( head == null ) {
            // The new item is the first (and only) one in the list.
            // Set head to point to it.
         head = newNode;
      }
      else if ( head.item.compareTo(insertItem) >= 0 ) {
            // The new item is less than the first item in the list,
            // so it has to be inserted at the head of the list.
         newNode.next = head;
         head = newNode;
      }
      else {
            // The new item belongs somewhere after the first item
            // in the list.  Search for its proper position and insert it.
         Node runner;     // A node for traversing the list.
         Node previous;   // Always points to the node preceding runner.
         runner = head.next;   // Start by looking at the SECOND position.
         previous = head;   
         //Find the proper prosition.
         while ( runner != null && runner.item.compareTo(insertItem) < 0 ) {
            previous = runner;
            runner = runner.next;
         }
         newNode.next = runner;     // Insert newNode after previous.
         previous.next = newNode;
      }   
   }  // end insert()
   
   public boolean delete(String deleteItem) {//everyone implements this method for practice!
      if ( head == null ) {
         return false;
      }
      else if ( head.item.equals(deleteItem) ) {
         head = head.next;
         return true;
      }
      else {
         Node runner;     // A node for traversing the list.
         Node previous;   // Always points to the node preceding runner.
         runner = head.next;   // Start by looking at the SECOND list node.
         previous = head;
         while ( runner != null && runner.item.compareTo(deleteItem) < 0 ) {
            previous = runner;
            runner = runner.next;
         }
         if ( runner != null && runner.item.equals(deleteItem) ) { //Ordered linked lists
            previous.next = runner.next;
            return true;
         }
         else 
            return false;
      }   
   } // end delete()
} // end class StringList

public class LLImplementation2{
    public static void main(String args[]){
        StringList2 list = new StringList2();
        list.printList();
        list.insert("first");
        list.insert("second");
        list.insert("third");
        list.insert("fourth");
        list.insert("3.14");
        list.printList();
        if(list.find("second"))
            System.out.println("\n\n\"second\" is in the list");
        else
            System.out.println("\n\n\"second\" is not in the list");
        
        list.delete("3.14");
        list.printList();
        System.out.println("\n\nThe index of \"third\" is "+list.indexOf("third"));
        System.out.println("The index of \"tenth\" is "+list.indexOf("tenth"));
        System.out.println("\nThe string for index \"2\" is "+list.get(2));
        list.set(2, "A New String!");
        System.out.println("\nAfter the set method call, the string for index \"2\" is "+list.get(2));
    }
}