/******************************************************************************
  *  Name:
  *  NetID:
  *  Precept:
  * 
  *  PList - Popularity List: Linked List Version
  *          list where the most recently accessed or added entry
  *          is always on top.
  *          
  *  Dependencies: Entry, StdOut
  *****************************************************************************/

public class PList {
    // instance variables
    private Node top;       // top of the list
    
    // inner class
    private class Node {
        private Entry en;   // Entry holds name and number
        private Node next;  // next entry on the list
    }
    
    // do-nothing constructor
    public PList() {
        top = null;
    }
        
    // add entry to top of list
    public void add(String name, String num) {
        // construct the Entry, pack it in a Node
        Entry newEntry = new Entry(name, num);
        Node newNode = new Node();
        newNode.en = newEntry;

        // insert at top of list (point to old top, become new top)
        newNode.next = top;
        top = newNode;
    }
    
    // output the list
    public void show() {
        if (top == null) {
            StdOut.println("empty PList");
            return;
        }
        // not empty, output the list, t travels the list
        for (Node t = top; t != null; t = t.next) {
            StdOut.println(t.en);
        }
    }
    
    // move entry with name to top of list, return number
    // return null if not there
    public String find(String name) {
        // special case for empty list
        if (top == null) return null;
        
        // special case for top entry (no moving needed)
        if (top.en.equals(name)) return top.en.getNum();
        
        // find your entry, keep track of previous node 
        for (Node prev = top; prev.next != null; prev = prev.next) {
            Node current = prev.next;
            if (current.en.equals(name)) {
                // remove from current position
                prev.next = current.next;
                // move to top
                current.next = top;
                top = current;
                //return number
                return current.en.getNum();
            }
        }
        
        // if you get to here, entry not found
        return null;
    }
        
    //remove and return Entry from list
    public Entry cut(String name) {
        // use find() to move Entry to top of list
        String found = find(name);
        if (found == null)
            throw new RuntimeException(name + "not found");
        // return Entry after you remove it from list
        Entry toBeCut = top.en;
        top = top.next;
        return toBeCut;
    }
    
    // update num or add entry to list
    public void update(String name, String num) {
        // Is it already on list?
        String found = find(name);
        if (found != null) {
            // if there, cut it
            cut(name);    
        }
        // either way, add new version
        add(name, num);
        return;
    }
    
    // test main
    public static void main(String[] args) {
        PList list = new PList();
        list.add("Doug", "6092586314");
        list.add("Donna", "6092581978");
        list.add("Christopher", "6092585388");
        list.add("Maia", "6092586484");
        list.add("Chris", "6092582038");
        StdOut.println("Entire list:");
        list.show();
        StdOut.println("===========================");
        
        list.update("Maia", "6092588888");
        list.cut("Chris");
        StdOut.println("Doug " + list.find("Doug"));
        StdOut.println("Maria " + list.find("Maria"));
        StdOut.println("===========================");
        
        StdOut.println("Updated list:");
        list.show();
    }           
}