/**
 * Classwork 6 - Report
 * Collect all answers to runtime analysis problems here.
 * 
 * GROUP MEMBERS:
 *   1. I. R. Solution
 */

 
// -------------------------------------------------------
// Problem 1
// -------------------------------------------------------
 
/**
 * Assumptions:
 *  - Let n = the number of words in the input sentence, which we assume
 *    are at most some length of a constant k
 *  - Worst Case Assumption: The inner loop will maximally iterate in cases
 *    where the input sentence has no duplicates (meaning the if-condition that
 *    breaks from the loop will never be true, and so its contents will never execute).
 */

/**
 * Returns the number of unique, unrepeated words that are found
 * in the given sentence sent
 * NOTE: This solution is not very good!!! It can be simplified
 * by using ArrayLists, but even those aren't the best choice here!
 * @param sent The sentence in which to count unique words
 * @return The number of unique, unrepeated words in sent
 */
public static int uniqueWords (String sent) {
    String[] words = sent.split(" ");                           // c1 * k * n
    String currWord, compWord;                                  // c2
    int count = 0;                                              // c3

    // Compare each pair of words (again, warning: not great)
    for (int i = 0; i < words.length; i++) {                    // c4 * n
        boolean repeatFound = false;                            // c5 * n
        currWord = words[i];                                    // c6 * n
        if (currWord.equals("")) { continue; }                  // c7 * n
        
        for (int j = 0; j < words.length; j++) {                // c8 * n^2
            compWord = words[j];                                // c9 * n^2
            if (currWord.equals(compWord) && i != j) {          // c10 * k * n^2
                repeatFound = true;
                break;
            }
        }
        
        // Only increment the count for the first occurrence of each match
        count += (repeatFound) ? 0 : 1;                         // c11 * n
    }

    return count;                                               // c12
}

/**
 * Total Cost Analysis:
 *   T(n) = (c2 + c3 + c12) + n * (c1 * k + c4 + c5 + c6 + c7 + c11) + n^2 (c8 + c9 + c10 * k)
 *        = O(n^2)
 */
 
 
// -------------------------------------------------------
// Problem 2
// -------------------------------------------------------

/**
 * Assumptions:
 *   - Let n = arr.size(), the number of Strings in the input ArrayList
 *   - Worst case performance = looping through all elements of the ArrayList
 *     no matter what, so again, no worst-case here
 */
public static ArrayList<String> reverse_A (ArrayList<String> arr) {
    ArrayList<String> result = new ArrayList<String>();               // c_1
    for (int i = 0; i < arr.size(); i++) {                            // c_2 * n
        result.add(0, arr.get(i));                                    // c_3 * n * O(n) (prepend on AL)
    }
    return result;                                                    // c_4
}
  
/**
 * T(n) = O(1) + O(n) + O(n^2)
 *      = O(n^2)
 */
  
/**
 * Assumptions:
 *   - Let n = arr.size(), the number of Strings in the input ArrayList
 *   - Worst case performance = looping through all elements of the ArrayList
 *     no matter what, so again, no worst-case here
 */
public static ArrayList<String> reverse_B (ArrayList<String> arr) {
    ArrayList<String> result = new ArrayList<String>();               // c_1
    for (int i = arr.size() - 1; i >= 0; i--) {                       // c_2 * n
        result.add(arr.get(i));                                       // c_3 * n * O(1) (append on AL)
    }
    return result;                                                    // c_4
}
  
/**
 * T(n) = O(1) + O(n)
 *      = O(n)
 */
 
 
// -------------------------------------------------------
// Problem 3
// -------------------------------------------------------

/**
 * Assumptions:
 *   - Let n = a1.length, m = a2.length, the number of ints in each input array
 *   - Worst case performance = maximally looping through each of the for-loops,
 *     which will break out in cases that:
 *     - The outer for-loop will terminate at the first element found in a1 that
 *       isn't found in a2, so the worst case must avoid this
 *     - As such, the worst case must be when a1 is a subset of a2
 *     - Moreover, to avoid breaking on the first comparison each time, we'll
 *       assume a1 and a2's common elements appear in reverse order
 */
/**
 * Returns true iff all of a1's elements are found
 * within a2
 * @param a1 An array of ints
 * @param a2 An array of ints
 * @return Whether all elements of a1 are somewhere in a2
 */
public static boolean isSubset (int[] a1, int[] a2) {
    for (int i = 0; i < a1.length; i++) {          // c_1 * n
        boolean contained = false;                 // c_2 * n
        for (int j = 0; j < a2.length; j++) {      // c_3 * n * m
            if (a1[i] == a2[j]) {                  // c_4 * n * m
                contained = true;                  // c_5 * n
                break;                             // c_6 * n
            }
        }
        if (!contained) {return false;}            // c_7 * n
    }
    return true;                                   // c_8
}
  
/**
 * T(n) = O(1) + O(n) + O(n * m)
 *      = O(n * m)
 */
 
 
// -------------------------------------------------------
// FINAL ANSWERS
// Please collect your final answers to the above, below
// -------------------------------------------------------

1. O(n^2)
2a. O(n^2)
2b. O(n)
3. O(n * m)