/* File: Index.java
 * Author: Wayne Snyder
 * Date: 4/3/15
 * Purpose: This is an ADT to store records which contain 
 *         a key, date, and a list of values (all Strings); the list of values
 *         is a linked list, and the records are stored in a binary search tree. 
 */

package hw7;

import java.io.*;
import java.util.*;

public class Index { 
  
  // Nodes for linked lists of values
  private  class Node {
    String value;
    Node next;
    
    public Node(String v) {
      value = v;
    }
    
    public Node(String v, Node x) {
      value = v;
      next = x;
    }
    
    public String toString() {
      return arrayToString(this); 
    }
  }
  
  private String arrayToString(Node p) {
    if(p==null)
      return "[]";
    else
      return "[" + arrayToStringH(p); 
  }
  
  private String arrayToStringH(Node p) {
    if(p == null)
      return "]";
    else if(p.next == null)
      return p.value + "]";
    else
      return p.value + ";" + arrayToStringH(p.next); 
  }
  
  // nodes for the binary tree
  private class TreeNode {
    String key;
    Node values;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(String n) {
      key = n;
    }
    
    public TreeNode(String n, Node vals) {
      key = n;
      values = vals;
    }
    
    public String toString() {
      if(values == null)
        return key + ":[]";
      else
        return key + ":" + values.toString(); 
    }
  }
  
  
  private TreeNode root = null;
  
  // Standard utility methods
  
  
  // Size is number of nodes in the tree
  public int size() {
    return size(root);
  }
  
  private int size(TreeNode t) {
    if (t == null)
      return 0;
    else
      return 1 + size(t.left) + size(t.right);
  }
  
  // Height of a binary tree is number of links in longest path, note that
  //     empty tree has height -1.
  
  public int height() {
    return height(root);
  }
  
  private int height(TreeNode t) {
    if (t == null)
      return -1;
    else 
      return 1 + Math.max( height(t.left), height(t.right) ); 
  }
  
  public void printTree() {
    printTree(root, "");  
  }
  
  private void printTree(TreeNode t, String indent) {
    if(t != null) {
      printTree(t.right, indent + "\t");
      System.out.println(indent + t); 
      printTree(t.left, indent + "\t"); 
    }
  }
  
  public void printTreeKeys() {
    printTreeKeys(root, "");  
  }
  
  private void printTreeKeys(TreeNode t, String indent) {
    if(t != null) {
      printTreeKeys(t.right, indent + "\t");
      System.out.println(indent + t.key); 
      printTreeKeys(t.left, indent + "\t"); 
    }
  }
  
  
  // Interface methods
  
  public void insert(String key) {
    root = insertH(key, null, root); 
  }
  
  public void insert(String key, String val) {
    root = insertH(key, val, root); 
  }
  
  private TreeNode insertH(String key, String value, TreeNode t) {
    
    if (t == null) {
      if(value == null)
        return new TreeNode( key );
      else
        return new TreeNode(key, new Node(value,null) );
    }
    else if (key.compareTo(t.key) < 0) {
      t.left = insertH(key, value, t.left);
      return t;
    } else if (key.compareTo(t.key) > 0) {
      t.right = insertH(key, value, t.right);
      return t;
    }
    else if(value == null)
      return t; 
    else{                                   // for duplicates just add to values
      t.values = insertLL(value,t.values); 
      return t;
    }
  }
  
  public void insert(String key, String[] values) {
    root = insertArrayH(key, values, root); 
  }
  
  private TreeNode insertArrayH(String key, String[] values, TreeNode t) {
    
    if (t == null) {
      TreeNode p = new TreeNode(key);
      for(int i = 0; i < values.length; ++i) {
        p.values = insertLL(values[i], p.values);
      }
      return p;
    }
    else if (key.compareTo(t.key) < 0) {
      t.left = insertArrayH(key, values, t.left);
      return t;
    } else if (key.compareTo(t.key) > 0) {
      t.right = insertArrayH(key, values, t.right);
      return t;
    }
    else{
      for(int i = 0; i < values.length; ++i)
        t.values = insertLL(values[i], t.values);
      return t;
    }
  } 
  
  private Node insertLL(String s, Node p) {
    if(p == null)
      return new Node(s, null); 
    else if( p.value == s)
      return p;                    // do not insert duplicates
    else {
      p.next = insertLL(s,p.next);
      return p;
    }  
  }
  
  public String getValues(String title) {
    return getValuesHelper(title,root); 
  }
  
  public String getValuesHelper(String key, TreeNode t) {
    if (t == null)
      return null;
    else if (key.compareTo(t.key) < 0) {
      return getValuesHelper(key, t.left);
    } else if (key.compareTo(t.key) > 0) {
      return getValuesHelper(key, t.right);
    } else  {   // found it
      if(t.values == null)
        return "[]";
      else
        return t.values.toString();
    }
  }
  
  // Recursively reconstructs tree without the key n in it
  public void delete(String key) {
    root = delete(key,root);
  }
  
  private  TreeNode delete(String n, TreeNode t) {
    if (t == null)                             // Case 1: tree is null
      return t;
    else if (n.compareTo(t.key) < 0) {                      // Case 2: key n is in left subtree
      t.left = delete(n, t.left);
      return t;
    } else if (n.compareTo(t.key) > 0) {                    // Case 3: key n is in right subtree
      t.right = delete(n, t.right);
      return t;
    } else                                     // Case 4: found key n at root; 
      if (t.left == null)                // Case 4a: no left child, so reroute around this node
      return t.right;
    else if (t.right == null)                  // Case 4b: no right child, ditto
      return t.left;
    else {                                     // Case 4c: both children exist, so move minimal key in right subtree up 
      TreeNode min = findMin(t.right);             //    Preserve a pointer to this minimal node and then
      t.right = deleteMin(t.right);            //    reconstruct the right subtree without it
      min.left = t.left;                       //    Finally, replace root node with min node
      min.right = t.right;
      return min;
    }
  }
  
  // return a pointer to the minimal element in r
  
  private TreeNode findMin(TreeNode r) {
    if(r.left == null)          // this is the minimal node
      return r;
    else
      return findMin(r.left);
  }
  
  // reconstruct the tree r without its minimal element
  
  private TreeNode deleteMin(TreeNode r) {
    if(r.left == null)
      return r.right;
    else {
      r.left = deleteMin(r.left);
      return r; 
    } 
  }
  
  // methods to build inverted index
  
  public Index getInvertedIndex() {
    // first, must iterate through whole index tree, and for
    // each value, insert value and its key
    Index ID = new Index(); 
    traverseTree(root, ID);
    return ID;
  }
  
  private void traverseTree(TreeNode t, Index ID) {
    if(t != null) {
      traverseList(t.values,t.key,ID);
      traverseTree(t.left,ID);
      traverseTree(t.right,ID);
    } 
  }
  
  private void traverseList(Node p, String key, Index ID) {
    if(p != null) {
      ID.insert(p.value,key);
      traverseList(p.next, key, ID);     
    }  
  }
  
  
  
  // unit test
  
  public static void main (String[] args) { 
    Index D = new Index(); 
    String[][] V = {
      {"Coke", "Salad", "Pasta" },            
      {"Pepsi", "Salad", "Chicken", "Salad" },   // Node duplicate value 
      {"Chicken", "Pasta"} };
    
    D.insert("Ringo",  V[0]);
    D.insert("John",  V[1]);
    D.insert("George", V[2]);
    D.insert("George", "Pasta");       // duplicate, should not be inserted
    D.insert("George", "Milk");
    D.insert("Wayne"); 
    D.insert("Paul"); 
    D.insert("Paul", "Pasta");
    D.insert("Paul", "Beef");
    D.insert("Paul", "Coke");
    D.insert("Paul", "Pasta");         // duplicates, should not be inserted
    D.insert("Paul"); 
    D.insert("Wayne"); 
    
    
    System.out.println("\n[1] Printing keys of tree, should be:\n");
    System.out.println("\tWayne\n"
                         + "Ringo\n"
                         + "\t\tPaul\n"
                         + "\tJohn\n" 
                         + "\t\tGeorge\n");
    
    D.printTreeKeys(); 
    
    System.out.println("\n[2] Printing tree, should be:\n");
    System.out.println("\tWayne:[]\n"
                         + "Ringo:[Coke;Salad;Pasta]\n"
                         + "\t\tPaul:[Pasta;Beef;Coke]\n"
                         + "\tJohn:[Pepsi;Salad;Chicken]\n" 
                         + "\t\tGeorge:[Chicken;Pasta;Milk]\n");
    
    D.printTree(); 
    
    System.out.println("\n[3]: Testing size, should print out:\n5");
    System.out.println(D.size()); 
    
    System.out.println("\n[4]: Testing height, should print out:\n2");
    System.out.println(D.height());
    
    System.out.println("\n[5]: Testing getValues, should print out:\n[Chicken;Pasta;Milk]");
    System.out.println(D.getValues("George")); 
    
    System.out.println("\n[6]: Testing getValues, should print out:\n[]");
    System.out.println(D.getValues("Wayne")); 
    
    System.out.println("\n[7]: Testing getValues, should print out:\nnull");
    System.out.println(D.getValues("Ozzy")); 
    
    System.out.println("\n[8]: Testing delete, should print out:\n");
    System.out.println("Wayne\n"
                         + "\t\tPaul\n"
                         + "\tJohn\n"
                         + "\t\tGeorge\n");
    D.delete("Ringo"); 
    D.printTreeKeys();  
    
    System.out.println("\n[9]: Testing getValues, should print out:\nnull");
    System.out.println(D.getValues("Ringo"));  
    
    System.out.println("\nBuilding Inverted Index....\n"); 
    Index InvD = D.getInvertedIndex(); 
    
    System.out.println("[10] Printing tree, should be:\n");
    System.out.println("\tSalad:[John]\n"
                         + "Pepsi:[John]\n"
                         + "\t\tPasta:[George;Paul]\n"
                         + "\t\t\tMilk:[George]\n"
                         + "\t\t\t\tCoke:[Paul]\n"
                         + "\tChicken:[John;George]\n"
                         + "\t\tBeef:[Paul]\n");
    
    InvD.printTree(); 
    
    System.out.println("\n[12]: Testing size, should be:\n7");
    System.out.println(InvD.size()); 
    
    System.out.println("\n[13]: Testing height, should be:\n4");
    System.out.println(InvD.height()); 
    
    System.out.println("\n[14]: Testing getValues, should be:\n[George;Paul]");
    System.out.println(InvD.getValues("Pasta")); 
    
    System.out.println("\n[15]: Testing getValues, should be:\nnull");
    System.out.println(InvD.getValues("Pork"));
    
    
    
    
    
    
  }
}