import java.util.ArrayList;
import java.util.List;

/**
 * Class containing functions for a code reading assignment.
 */
public class FourMystFunctions
{

    // --- Utility Function for Doing Something ---
    
    /**
     * Private helper method to do what ???
     */
    private static void mystHelper(ArrayList<Integer> data, int i, int j)
    {
        int temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

    // ---------------------------------------------------------------------
    // MYSTERY 1: 
    // ---------------------------------------------------------------------

    /**
     * What does this do?
     *
     * @param data a list of integers
     */
    public static void mystery1(ArrayList<Integer> data)
    {
        int n = data.size();
        
        // Start the outer loop from the second element (index 1), 
        // [... for some mysterious reason...]
        for (int i = 1; i < n; i++)
        {
            
            int current = data.get(i);
            
            // 'j' is [... not a great variable name. What is its purpose? ]
            int j;
            
            // Loop: [... what does this loop do? ...]
            for (j = i - 1; j >= 0 && data.get(j) > current; j-- )
            {
                
                data.set(j + 1, data.get(j));
            }
            
            // [... what is happening here? ...]
            data.set(j + 1, current);
        }
    }

    // ---------------------------------------------------------------------
    // MYSTERY 2:
    // ---------------------------------------------------------------------

    /**
     * What does this do?
     *
     * @param data a list of integers
     */
    public static void mystery2(ArrayList<Integer> data)
    {
        int n = data.size();

        // Outer loop: [... a comment would be nice ...]
        // [ Did we notice that it is NOT the canonical for loop? Why not?  ]
        for (int i = 0; i < n - 1; i++)
        {
            
            // [... a comment would be nice ...]
            int minIndex = i;
            
            // Inner loop: [... a comment would be nice ...]
            for (int j = i + 1; j < n; j++)
            {
                // [... a comment would be nice ...]
                if (data.get(j) < data.get(minIndex))
                {
                    minIndex = j;
                }
            }
            
            // Do something
            // What is the purpose or effect of doing that?
            if (minIndex != i)
            {
                mystHelper(data, i, minIndex);
            }
        }
    }
    
    // ---------------------------------------------------------------------
    // MYSTERY 3:
    // ---------------------------------------------------------------------

    /**
     * What does this do?
     *
     * @param data a list of integers
     */
    public static void mystery3(ArrayList<Integer> data)
    {
        if (data == null || data.size() < 2)
        {
            return;
        }
        recMyst3(data, 0, data.size() - 1);
    }
    
    /**
     * Recursive helper for mystery3 that [... does something ...]
     *
     * @param data a list of integers
     * @param low  the 'low' index for a range of integers in data
     * @param high  the 'high' index for a range of integers in data
     */
    private static void recMyst3(ArrayList<Integer> data, int low, int high)
    {
        if (low < high)
        {
            // [... what does this do? ...]
            int mid = low + (high - low) / 2;
            
            // Recursively [... do something ...]
            recMyst3(data, low, mid);
            
            // Recursively [... do something ...]
            recMyst3(data, mid + 1, high);
            
            // [... what does this do? ...]
            myst3Helper(data, low, mid, high);
        }
    }

    /**
     * Another helper function used by mystery3
     * What does this do?
     *
     * @param data a list of integers
     * @param low  the 'low' index for a range of integers in data
     * @param mid  a middle index between 'low' and 'high' (could be equal
     *                                                      to one of those)
     * @param high  the 'high' index for a range of integers in data
     */
    private static void myst3Helper(ArrayList<Integer> data,
            int low, int mid, int high)
    {
        // Create temporary lists for the left and right halves
        List<Integer> leftHalf = new ArrayList<>();
        List<Integer> rightHalf = new ArrayList<>();

        // [... what are we doing here? ...]
        for (int i = low; i <= mid; i++)
        {
            leftHalf.add(data.get(i));
        }
        for (int i = mid + 1; i <= high; i++)
        {
            rightHalf.add(data.get(i));
        }

        int leftIndex = 0;
        int rightIndex = 0;
        int dataIndex = low; // the index in the original 'data' list

        // [... what are we doing here? ...]
        while (leftIndex < leftHalf.size() && rightIndex < rightHalf.size())
        {
            if (leftHalf.get(leftIndex) <= rightHalf.get(rightIndex))
            {
                data.set(dataIndex, leftHalf.get(leftIndex));
                leftIndex++;
            }
            else
            {
                data.set(dataIndex, rightHalf.get(rightIndex));
                rightIndex++;
            }
            dataIndex++;
        }

        // [... what are we doing here? ...]
        while (leftIndex < leftHalf.size())
        {
            data.set(dataIndex, leftHalf.get(leftIndex));
            leftIndex++;
            dataIndex++;
        }

        // [... what are we doing here? ...]
        while (rightIndex < rightHalf.size())
        {
            data.set(dataIndex, rightHalf.get(rightIndex));
            rightIndex++;
            dataIndex++;
        }
    }
    
    // ---------------------------------------------------------------------
    // MYSTERY 4:
    // ---------------------------------------------------------------------

    /**
     * What does this do?
     *
     * @param data a list of integers
     */
    public static void mystery4(ArrayList<Integer> data)
    {
        if (data == null || data.size() < 2)
        {
            return;
        }
        recMyst4(data, 0, data.size() - 1);
    }
    
    /**
     * A helper function used by mystery4
     * What does this do?
     *
     * @param data a list of integers
     * @param low  the 'low' index for a range of integers in data
     * @param high  the 'high' index for a range of integers in data
     */
    private static void recMyst4(ArrayList<Integer> data, int low, int high)
    {
        if (low < high)
        {
            // pivotIndex is the index of the pivot element after doing
            // something
            int pivotIndex = doSomething(data, low, high);

            // Recursively sort elements before and after the pivot
            recMyst4(data, low, pivotIndex - 1);
            recMyst4(data, pivotIndex + 1, high);
        }
    }

    /**
     * Another helper function used by mystery4
     * What does this do?
     *
     * @param data a list of integers
     * @param low  the 'low' index for a range of integers in data
     * @param high  the 'high' index for a range of integers in data
     */
    private static int doSomething(ArrayList<Integer> data, int low, int high)
    {
        // Select the last element as the pivot
        int pivot = data.get(high);
        
        // i is the index of an element before the ones we're looking at
        int i = (low - 1); 

        for (int j = low; j < high; j++)
        {
            // [... what is this doing? ...]
            if (data.get(j) <= pivot)
            {
                i++;

                // [... what is this doing? ...]
                mystHelper(data, i, j);
            }
        }

        // [... what is this doing? ...]
        mystHelper(data, i + 1, high);
        
        // Return the final pivot index
        return i + 1;
    }

    public static void main(String[] args)
    {
        // CODE FOR TEST DRIVER IS MISSING.
    }

}