import java.util.Deque;
import java.util.Queue;
import java.util.ArrayDeque;
import java.util.Arrays;

/** Solutions to the recursion worksheet.

    @author Jed Yang
*/
public class RecursionWorksheet
{
   private static final int MIN_SIZE = 4;

   /** Iterative quick sort. */
   public static void quickSort(int[] array)
   {
      Queue<Integer> initialArgs = new ArrayDeque<>(); // to store parameters
      initialArgs.add(0); // first
      initialArgs.add(array.length - 1); // last

      Deque<Queue<Integer>> callStack = new ArrayDeque<>(); // used as a stack
      callStack.push(initialArgs);

      while (!callStack.isEmpty())
      {
         // restore parameters
         Queue<Integer> currentArgs = callStack.pop();
         int first = currentArgs.remove();
         int last = currentArgs.remove();
         if (first < last)
         {
            if (last - first + 1 < MIN_SIZE)
            {
               Helper.insertionSort(array, first, last);
            }
            else
            {
               int pivotIndex = Helper.partition(array, first, last);

               // As written below, the left and right recursive calls are
               // processed in the opposite order as our original code (though
               // it still works perfectly).  What changes can you make to have
               // the recursive calls be processed in the customary order?
               Queue<Integer> leftHalfArgs = new ArrayDeque<>();
               leftHalfArgs.add(first);
               leftHalfArgs.add(pivotIndex - 1);
               callStack.push(leftHalfArgs);

               Queue<Integer> rightHalfArgs = new ArrayDeque<>();
               rightHalfArgs.add(pivotIndex + 1);
               rightHalfArgs.add(last);
               callStack.push(rightHalfArgs);
            }
         }
      }
   }

////////////////////////////////////////////////////////////////////////////////

   /** Returns max value possible in a knapsack with limited capacity. */
   public static int knapsack(int[] weights, int[] values, int maxWeight)
   {
      return knapsack(weights, values, maxWeight, 0);
   }

   private static int knapsack(int[] weights, int[] values,
                               int weightRemaining, int index)
   {
      if (index >= weights.length)
         return 0;

      // we assume all values are nonnegative, so 0 will be masked by
      // valueWithoutItem when valueWithItem is not set by the if block.
      int valueWithItem = 0;
      // try adding current item if weight allows
      if (weights[index] <= weightRemaining)
      {
         valueWithItem = values[index]
               + knapsack(weights, values, weightRemaining - weights[index],
                          index + 1); 
      }

      // without adding item
      int valueWithoutItem = knapsack(weights, values,
                                      weightRemaining, index + 1);

      // pick the larger one
      if (valueWithItem > valueWithoutItem)
         return valueWithItem;
      else
         return valueWithoutItem;
   }

////////////////////////////////////////////////////////////////////////////////

   /** Returns n-th Fibonacci number.  By using tail recursion, this is O(n). */
   public static int fibonacci(int n)
   {
      // fibonacci(0) = 0, fibonacci(1) = 1
      if (n <= 1)
         return n;

      return fibonacci(n, 1, fibonacci(1), fibonacci(0));
   }

   /** Call with
       @param n if interested in fibonacci(n)
       @param k for some k less than or equal to n
       @param cur = fibonacci(k)
       @param prev = fibonacci(k-1)
       @return fibonacci(n)
   */
   private static int fibonacci(int n, int k, int cur, int prev)
   {
      if (k == n)
         return cur;

      return fibonacci(n, k + 1, cur + prev, cur);
   }

////////////////////////////////////////////////////////////////////////////////

   /** Prints a spaceship with side and middle as lengths. */
   public static void spaceship(int side, int middle)
   {
      printRow(side);
      if (side == middle)
         return;

      spaceship(side + 1, middle);
      printRow(side);
   }

   private static void printRow(int length)
   {
      printRow(length, 0);
      System.out.println();
   }

   private static void printRow(int length, int printedSoFar)
   {
      if (printedSoFar == length)
         return;
      System.out.print("+ ");
      printRow(length, printedSoFar + 1);
   }

////////////////////////////////////////////////////////////////////////////////

   /** Returns a raised to the power of b. */
   public static int power(int a, int b)
   {
      if (b == 0)
         return 1;

      int factor = power(a, b / 2);
      int product = factor * factor;
      if (b % 2 == 1)
         product *= a;
      return product;
   }

////////////////////////////////////////////////////////////////////////////////

   public static void main(String[] args)
   {
      spaceship(4, 6);

      for (int i = 0; i < 8; i++)
      {
         System.out.println("fibonacci(" + i + ") = " + fibonacci(i));
      }

      System.out.println(power(2,10)); // should print 1024
      int[] array = new int[10];
      Helper.fillAndShuffle(array);
      System.out.println(Arrays.toString(array));
      quickSort(array);
      System.out.println(Arrays.toString(array));

      int[] weights = {2, 4, 5, 3};
      int[] values = {3, 2, 6, 4};
      System.out.println(knapsack(weights, values, 6)); // should print 7
   }
}