package cse1030;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class Lab9 {

  /**
   * Solve the subset sum problem for a set of integer values.
   * 
   * @param t
   *          a set of integer values
   * @return <code>true</code> if there exists a non-empty subset of
   *         <code>t</code> whose elements sum to zero.
   */
  public static boolean subsetSum(Set<Integer> t) {
    return subsetSum(new ArrayList<Integer>(t), null);
  }

  /**
   * Computes the sum of two Integers where one or both references are null. If
   * both references are null then the result is null; otherwise the result is
   * an integer equal to <code>a + b</code> where null references are treated as
   * being equal to zero.
   * 
   * @param a
   * @param b
   * @return the sum of <code>a</code> and <code>b</code>
   */
  private static Integer add(Integer a, Integer b) {
    if (a == null && b == null) {
      return null;
    } else if (a == null) {
      return b;
    } else if (b == null) {
      return a;
    }
    return a + b;
  }

  /**
   * Recursive solution for the subset sum problem.
   * 
   * <p>
   * <code>currentSum</code> holds the value of the subset under consideration;
   * it should be <code>null</code> if the current subset is empty.
   * 
   * @param t
   *          a list containing unique integer values (a set of integers)
   * @param currentSum
   *          the current subset sum so far
   * @return <code>true</code> if there exists a subset of <code>t</code> such
   *         that the sum of the elements in the subset and
   *         <code>currentSum</code> equals zero.
   */
  private static boolean subsetSum(List<Integer> t, Integer currentSum) {
    if (currentSum != null && currentSum == 0) {
      return true;
    }
    if (t.size() == 1) {
      int i = t.get(0);
      return add(i, currentSum) == 0;
    }
    if (t.isEmpty()) {
      return false;
    }
    Integer first = t.get(0);
    boolean withFirst = subsetSum(t.subList(1, t.size()),
        add(first, currentSum));
    boolean withoutFirst = subsetSum(t.subList(1, t.size()), currentSum);
    return withFirst || withoutFirst;
  }

  /**
   * Recursively merge two sorted lists into a single sorted list.
   * 
   * @param left
   * @param right
   * @return a single list sorted in increasing order containing the elements of
   *         <code>left</code> and <code>right</code>
   */
  public static LinkedList<Integer> merge(LinkedList<Integer> left,
      LinkedList<Integer> right) {
    if (left.isEmpty()) {
      return right;
    }
    if (right.isEmpty()) {
      return left;
    }
    int fL = left.getFirst();
    int fR = right.getFirst();
    LinkedList<Integer> t = new LinkedList<Integer>();
    if (fL < fR) {
      t.add(fL);
      left.removeFirst();
      t.addAll(merge(left, right));
      return t;
    } else {
      t.add(fR);
      right.removeFirst();
      t.addAll(merge(left, right));
      return t;
    }
  }

  /**
   * Determines if an integer is prime.
   * 
   * @param x
   *          an integer value greater than 2
   * @return <code>true</code> if <code>n</code> is prime, <code>false</code>
   *         otherwise
   */
  public static boolean isPrime(int x) {
    return isPrime(x, 2);
  }

  /**
   * Recursively determine if an integer is prime.
   * 
   * @param n
   *          an integer value greater than 2
   * @param divisor
   * @return <code>true</code> if <code>n</code> is prime, <code>false</code>
   *         otherwise
   */
  private static boolean isPrime(int x, int divisor) {
    if (divisor > Math.sqrt(x)) {
      return true;
    }
    if (x % divisor == 0) {
      return false;
    }
    return isPrime(x, divisor + 1);
  }

  /**
   * Find the minimum element in a list.
   * 
   * @param t a list of integers
   * @return the minimum element in the list
   */
  public static int min(List<Integer> t) {
    if (t.size() == 1) {
      return t.get(0);
    }
    return Math.min(t.get(0), min(t.subList(1, t.size())));
  }
  
  /**
   * Find the maximum element in a list.
   * 
   * @param t a list of integers
   * @return the maximum element in the list
   */
  public static int max(List<Integer> t) {
    if (t.size() == 1) {
      return t.get(0);
    }
    return Math.max(t.get(0), max(t.subList(1, t.size())));
  }

  /**
   * Computes the remainder after division.
   * 
   * @param a an integer greater than zero
   * @param b an integer greater than zero
   * @return the value <code>a % b</code>
   */
  public static int remainder(int a, int b) {
    if (a < b) {
      return a;
    }
    return remainder(a - b, b);
  }

  /**
   * Integer division.
   * 
   * @param a an integer greater than zero
   * @param b an integer greater than zero
   * @return the value <code>a / b</code>
   */
  public static int divide(int a, int b) {
    if (a < b) {
      return 0;
    }
    return 1 + divide(a - b, b);
  }

}