package list;
import java.io.*;

/* Node defines an object with two fields, one for an id and the other for a reference to the next node in the list. */
public class Node
{
     private String id;
     private Node  next;

     public Node (String id)
     {     this.id = id;
            next = null;
     } // constructor
 
     protected Node getNext () { return next;} // method getNext

     protected void setNext (Node next) { this.next = next; } // method setNext

     protected String getId () {return id;} // method getId
 
     protected void setId (String id) {this.id = id; } // method setID

     public void displayNode (PrintStream outfile) {outfile.println ("ID: " + id); } // displayNode
} //  class Node

import java.io.*;
package list;

// An interface that defines all the public methods in the ListClass.
interface ListInterface
{
 public boolean listIsEmpty ();
 public void insertInList (Node newNode);
 public void outputList (PrintStream outfile);
 public Node deleteFromList (String keyId);
 public Node  findNode (String keyId);
}// interface ListInterface

// ListClass contains methods and data declarations for a linked list.
public class ListClass implements ListInterface
{
     private Node listHead; // Head of the list.

     public ListClass () {listHead = null;} // ListClass ()

     private Node getListHead () { return listHead;} // method getListHead
 
     // Returns true if the list is empty, false otherwise.
     public boolean listIsEmpty ()
     {
          if (listHead == null) return true;
          else return false;
     } // method listIsEmpty

     // Inserts a new id into the list in order.
     public void insertInList (Node newNode)
     {
          Node  current,  previous;
          newNode.setNext (null);
          if (listHead == null) listHead = newNode; // The list is empty.
          else // The list is not empty.
          {
               current = listHead;
               previous = listHead;
               // Find the location (between previous and current) to insert the new node.
               while ((current != null) && (current.getId ().compareTo (newNode.getId ()) < 0))
               {
                    previous = current;
                    current = current.getNext ();
               }
               if (current == listHead) // The new node is inserted at the front of the list.
               {
                    newNode.setNext (listHead);
                    listHead = newNode;
               }
               else // The new node goes either in the middle or at the end of the list.
               {
                    previous.setNext (newNode);
                    newNode.setNext (current);
               }
          }
     } // method insertInList

     // Print the list to an output file, either the screen or a disk.
     public void outputList (PrintStream outfile)
     {
          Node  tempNode = listHead;
          while (tempNode != null)
          {
               tempNode.displayNode (outfile);
               tempNode = tempNode.getNext ();
          }
          outfile.println ();
     } // method outputList

     /* Remove a node from the list. If the list is empty or the id is not found, return false, otherwise remove the node from the list and return true. */
     public Node deleteFromList (String keyId)
     {
          Node  previous,  current;
          boolean found = false;
          if (listHead == null) // The list is empty.
          {
               System.out.println ("Error - attempt to delete from an empty list.");
               return null;
          }
          else // The list is not empty.
          {
               current = listHead;
               previous = listHead;
               /* Find the id in the list, if it is there.  Keep a pointer,  previous, to the node in the list immediately preceding the one where the id is found. */
               while (!found && (current != null))
                if (current.getId ().equals (keyId)) // The id is found at current.
                     found = true;
                else // The id has not yet been found.
                {
                      previous = current;
                     current = current.getNext ();
                }
               if (!found)
               {
                    System.out.println ("Error - not in the list" );
                    return null;
               }
               else /* The id was found at current with previous pointing  to the node immediately preceding current. */
               {
                    if (current == listHead)   // The id was found at the front of the list.
                         listHead = listHead.getNext ();
                    else   // The id was found after the first node.
                         previous.setNext (current.getNext ());
                    return current;
               }
          }
     } // method deleteFromList

     /* This returns a pointer to the node containing the keyId.  If  keyId is not in the list, it returns null. */
     public Node  findNode (String keyId)
     {
          Node  tempNode = listHead;
          boolean found = false;
          while (!found && (tempNode != null))
               if (tempNode.getId ().equals (keyId))  // The id was found at tempNode.
                    found = true;
               else   // The id has not yet been found, move tempNode on to the next node.
                    tempNode = tempNode.getNext ();
          if (!found)
          {
               System.out.println ("Error - the id was not found in the list." );
               return null;
          }
          else return tempNode;
     } // method findNode
} // class ListClass

/* This class reads data from a file and stores it in a linked list.  It then displays the data on the screen, finds an ID, deletes a node, and then stores the data in a second file. */

import java.io.*;
import list.ListClass;
import list.Node;

class TestList
{
     public static void main (String [] args)
     {
          ListManager manager = new ListManager ();
          manager.fillList ();
          manager.displayList ();
          manager.findNode ();
          manager.deleteNode ();
          manager.storeList ();
     }
} // class TestList

class ListManager
{
     private Node listHead;
     private ListClass nodeList;
     private int numberOfNodes;
 
     ListManager ()
     {
          nodeList = new ListClass ();
          listHead = null;
          numberOfNodes = 0;
     } // constructor
 
     // Method to read data from a file into the list.
     public void fillList ()
     {
          try
          {
               BufferedReader stdin = new BufferedReader (new InputStreamReader (System.in));
               System.out.print ("File Name: ");
               String fileName = stdin.readLine ();
               BufferedReader infile = new BufferedReader (new InputStreamReader (new FileInputStream (fileName)));
               Node nextNode;
               String id = infile.readLine ();
               while (id != null)
               {
                    nextNode = new Node (id);
                    nodeList.insertInList (nextNode);
                    numberOfNodes ++;
                    id = infile.readLine ();
               } // while
               infile.close ();
          } catch (IOException e) {System.out.println ("File not found");}
     } // method fillList
 
     // Method to display the entire list on the screen.
     public void displayList ()
     {
         nodeList.outputList (System.out);
     } // method displayList
 
     // Method used to read the ID to be located and then call the findNode method.
     public void findNode ()
     {
           try
          {
                 BufferedReader stdin = new BufferedReader (new InputStreamReader (System.in));
                 System.out.print ("ID to Find: ");
                 String id = stdin.readLine ();
                 Node foundNode = nodeList.findNode (id);
                 if (foundNode == null) System.out.println ("ID not found.");
                else foundNode.displayNode (System.out);
          } catch (IOException e) {System.out.println ("File Error. ");}
     } // method findNode
 
     // Method to read the ID to be removed from the list and then call deleteFromList
     public void deleteNode ()
     {
          try
          {
               BufferedReader stdin = new BufferedReader (new InputStreamReader (System.in));
               System.out.print ("ID to Remove: ");
               String id = stdin.readLine ();
               boolean deleted = nodeList.deleteFromList (id);
               if (deleted) System.out.println ("ID removed from list.");
               else System.out.println ("ID not in list.");
          } catch (IOException e) {System.out.println (“File Error.”);}
     } // method deleteNode

     public void storeList ()
     {
             try
             {
                   BufferedReader stdin = new BufferedReader (new InputStreamReader (System.in));
                   System.out.print ("Output File Name: ");
                   String outFileName = stdin.readLine ();
                   PrintStream outfile = new PrintStream  (new FileOutputStream (outFileName));
                   nodeList.outputList (outfile);
                   outfile.close ();
          } catch (IOException e)  {System.out.println ("File name not given.");}
     } // method storeList
} // class ListManager