/**
 * Sorts a list of nodes with generic type.
 * @author John Doe
 * @param <T> user defined type
 */

public class OrderedList<T extends Comparable<T>> {
  private Node<T> head;
  private int size;

  /**
   * Initializes a new ordered list object.
   */
  public OrderedList() {
    head = null;
    size = 0;
  }

  /**
   * Creates a new node with a given item and inserts it into its correct
   * position in the list so that the list is in ascending order.
   * @param element newly inserted element
   */
  public void insert(T element) {
    Node<T> newNode = new Node<>(element, null);
    if (head == null) {
      head = newNode;
    } else {
      Node<T> current = head;
      Node<T> previous = null;
      while (current != null && current.data.compareTo(element) < 0) {
        previous = current;
        current = current.next;
      }
      newNode.next = current;
      if (previous == null) {
        head = newNode;
      } else {
        previous.next = newNode;
      }
    }
    size++;
  }

  /**
   * Returns a copy of the k-th item in the list for a given integer k.
   * @param index the position the user specifies
   * @return The element the user wants to get
   * @throws OutOfBoundException if the index is out of bounds
   */
  public T get(int index) throws OutOfBoundException
  {
    if (index < 0 || index >= size)
    {
      throw new OutOfBoundException("Index: " + index + " size: " + size);
    }
    Node<T> current = head;
    for (int i = 0; i < index; i++) {
      current = current.next;
    }
    return current.data;
  }

  /**
   * Removes the first instance of a user-specified item.
   * @param item user specified item
   */
  public void remove(T item)
  {
    Node<T> current = head;
    Node<T> previous = null;
    while (current != null) {
      if (item.equals(current.data)) {
        if (previous == null) {
          head = current.next;
        } else {
          previous.next = current.next;
        }
        size--;
      } else {
        previous = current;
      }
      current = current.next;
    }
  }

  /**
   * Returns the last k elements in this ordered list.
   * @param k number of elements to return
   * @return List of the k largest elements
   * @throws OutOfBoundException if the index is out of bounds
   */
  public OrderedList kLargest(int k) throws OutOfBoundException
  {
      if (k >= size || k < 0)
          k = Math.abs(size);
      OrderedList ol = new OrderedList();
      for (int i = size - k; i < size; i++)
      {
          ol.insert(get(i));
      }
      return ol;
  }

  /**
   * Temporary, crappy method doing what add(OrderedList list2) should do;
   * it should traverse through the nodes of this list and the other nodes
   * exactly one without having to repeatedly search the location where the
   * items should be added to on the new list.
   * @param list2 another ordered list
   * @return Elements from both ordered list
   * @throws OutOfBoundException if the index is out of bounds
   */
  public OrderedList addFrom(OrderedList list2) throws OutOfBoundException
  {
      OrderedList list3 = new OrderedList();
      for (int i = 0; i < size; i++)
      {
          list3.insert(get(i));
      }
      for (int j = 0; j < list2.size; j++)
      {
          T element = (T) list2.get(j);
          list3.insert(element);
      }
      return list3;
  }

  /**
   * Method of implementing proper version of "addFrom" should do with proper
   * efficiency.
   * @param list2 another ordered list
   * @return Elements from both ordered list
   * @throws OutOfBoundException if the index is out of bounds
   */
  public OrderedList add(OrderedList list2) throws OutOfBoundException
  {
    int i = 0;
    int j = 0;
    OrderedList list3 = new OrderedList();
    int k = i + j;
    while (k < this.size + list2.size)
    {
        if(list2.get(i).compareTo(this.get(j)) < 0)
        {
            System.out.println(list2.get(i));
            list3.insert(list2.get(i));
            i++;
        }
        else
        {
            System.out.println(this.get(j));
            list3.insert(this.get(j));
            j++;
        }
    }
      return list3;
  }

  /**
   * Returns a neatly formatted list with every node.
   * @return A representation of the nodes in the list
   */
  @Override
  public String toString()
  {
    String st = "[";
    for (Node<T> n = head; n != null; n = n.next)
        st += n.data + ((n.next == null ? "]" : ", "));
    return st;
  }
}

/**
 * Establishes that a node object has data and a next node object.
 * @author John Doe
 * @param <T> user defined type
 */
class Node<T> {
  T data;
  Node<T> next;

  /**
   * Initializes a new node object.
   * @param data specified user input
   * @param next what is the node next to
   */
  public Node(T data, Node<T> next) {
    this.data = data;
    this.next = next;
  }
}