Collections Data Structure Java

//package proj6;
import java.text.DecimalFormat;
import java.text.NumberFormat;
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
/**
 * Implements QuickSort three different ways:
 * 1. Perform the basic, sequential QuickSort algorithm with two-pointer
 *    partition.
 * 2. Perform QuickSort using four threads, explicitely created and invoked.
 * 3. Perform QuickSort on numThreads using Executor support from Java's
 *    concurrency libraries.
 *
 * The program can be executed with the following command:
 * Usage: java Project6  [OPTIONS]
 *  - Valid parts are 1, 2, or 3
 *
 * Available options:
 * -s, --size    The size of the array to generate
 * -r, --random  True indicates a random array, false indicates a seeded array
 * -m, --max     Random numbers will generated between 0 (inclusive) and
 *               maxValue
 * -n, --num     Must be specified if you are desiring to run Part 3, otherwise
 *               it is ignored.
 *
 * @author Alex Laird
 * @author Ryan Morehart
 */
public class Project6
{
    /** The largest partition size that a task will execute for Part 3.*/
    private final int LARGEST_SIZE = 1000;
    /** Our processor ID if we are running in parallel. If the user is not running Part 2 or Part 3, this is left at -1.*/
    private int id = -1;
    /** In parallel algorithms, the number of threads that have completed their tasks.*/
    private int finishedThreads = 0;
    /** In parallel algorithms, the number of numbers that have been sorted.*/
    private int finishedCount = 0;
    /** The current number of tasks in use.*/
    private int taskCount = 0;
    /** Executor service for use in Part 3.*/
    ExecutorService pool;
    /** The number of threads to use if performing Part 2 or Part 3.*/
    private int numThreads = -1;
    /**
     * Constructs the class object with the number of threads used, if running Part 2 or Part 3.
     *
     * @param numThreads Number of threads to use.
     */
    public Project6(int numThreads)
    {
        this.numThreads = numThreads;
    }
    /**
     * Increments the variable stating the number of threads finished.
     */
    protected synchronized void threadFinished(int id)
    {
        ++finishedThreads;
    }
    /**
     * Check if the number of slave threads reporting they have finished working
     * is equal to the number of slave threads spawned.
     *
     * @return True if all spawned threads have finished, false otherwise.
     */
    private synchronized boolean waitingForThreads()
    {
        if (finishedThreads == numThreads)
        {
            return true;
        }
        return false;
    }
    /**
     * Check if the number of sorted items equals the total number of elements
     * in the array.
     *
     * @param size The number of elements total in the array.
     * @return True if all elements have been sorted, false otherwise.
     */
    private synchronized boolean waitingForCount(int size)
    {
        if (getFinishedCount () != size)
        {
            return true;
        }
        return false;
    }
    /**
     * Increment the finished counter by the given number n.
     *
     * @param n The amount to increment the finished counter by.
     */
    protected synchronized void addToFinishedCount (int n)
    {
        finishedCount += n;
    }
    
    /**
     * Retrieve the number of finished threads.
     *
     * @return The number of finished threads.
     */
    private synchronized int getFinishedCount()
    {
        return finishedCount;
    }
    /**
     * Increment the current number of tasks in use by one.
     */
    protected synchronized void incrementTaskCount()
    {
        ++taskCount;
    }
    /**
     * Retrieve the current number of tasks running.
     *
     * @return The number of tasks running.
     */
    protected synchronized int getTaskCount()
    {
        return taskCount;
    }
    /**
     * Swaps the two indeces in the array given.
     *
     * @param array The array to perform the swap on.
     * @param first Swap this index with element at second.
     * @param second Swap this index with element at first.
     */
    public void swap(int[] array,
                     int first,
                     int second)
    {
        int temp = array[first];
        array[first] = array[second];
        array[second] = temp;
    }
    /**
     * Finds the most logical point to split the array in two parts and uses
     * that point as the partition. Uses a while loop to evaluate the partition.
     *
     * @param array The array to be sorted.
     * @param low The lowest index.
     * @param high The highest index.
     * @return The index of the partitioning point.
     */
    protected int partition(int[] array,
                            int low,
                            int high)
    {
        int pivot = array[high];
        int left = low;
        int right = high - 1;
        while (left <= right)
        {
            // Increment the low pointer until you meet the pivot
            while (left <= right &&
                   array[left] <= pivot)
            {
                ++left;
            }
            // Decrement the high pointer until you meet the pivot
            while (left <= right &&
                   array[right] >= pivot)
            {
                --right;
            }
            // If the pointers have crossed, swap the items
            if (left < right)
            {
                // Swap value at left with value at right
                swap(array, left, right);
            }
        }
        // Finally, swap value at left with value at high
        swap (array, left, high);
        return left;
    }
    /**
     * Performs a standard recursive QuickSort algorithm on an array from
     * indeces high to low.
     *
     * @param array The array to be sorted.
     * @param low The lowest index.
     * @param high The highest index.
     */
    protected void sort(int[] array,
                        int low,
                        int high)
    {
        if (low < high)
        {
            // Locate the most precise partition point
            int mid = partition (array, low, high);
            // Recursively sort the lower half
            sort (array, low, mid - 1);
            // Recursively sort the upper half
            sort (array, mid + 1, high);
        }
    }
    /**
     * Continue passing partitions out to threads until the partition size is small
     * enough for us to handle ourselves, backing out of recursion.
     *
     * @param low The lowest index.
     * @param high The highest index.
     * @param array The array to be sorted.
     */
    protected void part3(int low,
                         int high,
                         int[] array)
    {
        if (high - low + 1 < LARGEST_SIZE)
        {
            // The partition is small enough, so do the work ourselves
            sort (array, low, high);
            addToFinishedCount (high - low + 1);
        }
        else
        {
            // Identify partition point
            int mid = partition (array, low, high);
            addToFinishedCount (1);
            // Launch slave task
            pool.execute (new QuickSortTask (this, getTaskCount (), mid + 1, high, array));
            incrementTaskCount ();
            // Recurse to assign the lower half to its thread
            part3(low, mid - 1, array);
        }
    }
    /**
     * Generate the array, sort it using the correct method for the given part,
     * and benchmark.
     *
     * @param part The part of the problem to perform.  Value use be 1, 2, or 3
     * @param size The size of the array to sort.
     * @param random True if numbers should be generated randomly, false if they should follow a pattern
     * @param maxValue The maximum value a randomly generated number can be
     */
    private void go(int part,
                    int size,
                    boolean random,
                    int maxValue)
    {
        // Generate array, output if length is reasonable, and declare time variables before
        // starting the time count, so as to not effect performance
        int[] array = Utility.buildArray (size, random, maxValue);
        // Copy the array to an unsorted array location for verification after the fact
        int[] unsortedArray = Arrays.copyOf (array, array.length);
        System.out.println ("::Part " + part + "::");
        System.out.println ("Array size: " + Utility.NUM_FORMAT.format (size));
        if (array.length <= 25)
        {
            System.out.print ("Initial array: ");
            Utility.printArray (array);
        }
        
        long startTime = -1;
        long endTime = -1;
        // Mark beginning time for calculation later
        startTime = System.currentTimeMillis();
        // Perform the basic, sequential QuickSort algorithm with two-pointer partition
        if (part == 1)
        {
            sort (array, 0, array.length - 1);
        }
        // Perform QuickSort using four threads, explicitely created and invoked
        else if (part == 2)
        {
            // Set this processor's ID
            id = 0;
            // Set the number of slave threads
            numThreads = 3;
            
            int low = 0;
            int high = array.length - 1;
            // Identify partition points for master and slaves
            int mid = partition (array, low, high);
            int first = partition (array, low, mid - 1);
            int second = partition (array, mid + 1, high);
            // Instantiate slave threads and pass them their partition portions
            QuickSortThread thread2 = new QuickSortThread (this, 1, first + 1, mid - 1, array);
            QuickSortThread thread3 = new QuickSortThread (this, 2, mid + 1, second - 1, array);
            QuickSortThread thread4 = new QuickSortThread (this, 3, second + 1, high, array);
            // Launch slave threads
            thread2.start ();
            thread3.start ();
            thread4.start ();
            // Current thread is the first thread, so let it do the lowest part
            sort (array, low, first - 1);
            // Wait for all threads to finish
            while (!waitingForThreads ())
            {
                continue;
            }
        }
        // Perform QuickSort on numThreads using Executor support from Java's concurrency libraries
        else if (part == 3)
        {
            // Set this processor's ID and increment task count
            id = 0;
            incrementTaskCount ();
            // Launch slave task
            pool = Executors.newFixedThreadPool (numThreads);
            pool.execute (new QuickSortTask (this, getTaskCount (), 0, array.length - 1, array));
            incrementTaskCount ();
            while (waitingForCount (array.length))
            {
                continue;
            }
            pool.shutdown();
        }
        // Mark end time and calculate total runtime
        endTime = System.currentTimeMillis();
        long totalTime = endTime - startTime;
        // Output benchmark as well as results, if length is reasonable
        if (part == 2)
        {
            System.out.println ("Threads used: 4");
        }
        else if(part == 3)
        {
            System.out.println ("Tasks used: " + numThreads);
        }
        System.out.println ("Elapsed time: " + Utility.NUM_FORMAT.format (totalTime) + "ms");
        if (array.length <= 25)
        {
            System.out.print ("Sorted array: ");
            Utility.printArray (array);
        }
        if (Utility.verifyArray (array, unsortedArray))
        {
            System.out.println ("Verified: array sorted properly");
        }
        else
        {
            System.out.println ("Unverified: array did not sort properly");
        }
        System.out.println ();
    }
    /**
     * The main method executes first in the program, parsing command-line arguments
     * and then immediately leaving static-land for the actual algorithms and
     * computations.
     *
     * @param args The command-line arguments.  "Usage: java Project6  [OPTIONS]
     *  - Valid parts are 1, 2, or 3
     *
     * Available options:
     * -s, --size    The size of the array to generate
     * -r, --random  True indicates a random array, false indicates a seeded array
     * -m, --max     Random numbers will generated between 0 (inclusive) and maxValue
     * -n, --num     Must be specified if you are desiring to run Part 3, otherwise it is ignored.
     */
    public static void main(String[] args)
    {
        // Output string for common errors
        final String USAGE_TEXT = "Usage: java Project6  [OPTIONS]\n"
        + " - Valid parts are 1, 2, or 3\n\n"
        + "Available options:\n"
        + "-s, --size      The size of the array to generate\n"
        + "-r, --random    True indicates a random array, false indicates a seeded array\n"
        + "-m, --max       Random numbers will generated between 0 (inclusive) and maxValue\n"
        + "-n, --num       Must be specified if you are desiring to run Part 3, otherwise it is ignored.";
        // The part of the problem to perform.  Value use be 1, 2, or 3
        int part = -1;
        // The size of the array to sort.*/
        int size = 10;
        // True if numbers should be generated randomly, false if they should follow a pattern
        boolean random = false;
        // The maximum value a randomly generated number can be
        int maxValue = 10;
        // The number of threads to use if performing Part 3
        int numThreads = -1;
        
        // Parse through arguments and set their respective variables
        if (args.length > 0)
        {
            part = Integer.parseInt (args[0]);
            try
            {
                for (int i = 1; i < args.length; i += 2)
                {
                    if (args[i].equals ("-s"))
                    {
                        size = Integer.parseInt (args[i + 1]);
                    }
                    else if(args[i].equals ("-r"))
                    {
                        if (args[i + 1].equals ("true"))
                        {
                            random = true;
                        }
                        else if (!args[i + 1].equals ("false"))
                        {
                            int intRand = Integer.parseInt (args[i + 1]);
                            if (intRand == 1)
                            {
                                random = true;
                            }
                            else if (intRand != 0)
                            {
                                // Since the given random value was not valid at this point, just break the given part so the program termiantes
                                part = -1;
                            }
                        }
                    }
                    else if(args[i].equals("-m"))
                    {
                        maxValue = Integer.parseInt(args[i + 1]);
                    }
                    else if(args[i].equals("-n"))
                    {
                        numThreads = Integer.parseInt(args[i + 1]);
                    }
                }
            }
            catch (NumberFormatException ex)
            {
                System.out.println (USAGE_TEXT);
                System.exit (2);
            }
            // Make sure the given part number was valid
            if (part > 3 || part < 1)
            {
                System.out.println (USAGE_TEXT);
                System.exit (3);
            }
            // If we are doing Part 3 and the number of desired threads was not given, we cannot continue
            if (part == 3 && numThreads == -1)
            {
                System.out.println (USAGE_TEXT);
                System.exit (4);
            }
        }
        else
        {
            System.out.println (USAGE_TEXT);
            System.exit (1);
        }
        // Get us out of static-land!
        Project6 proj6 = new Project6 (numThreads);
        proj6.go (part, size, random, maxValue);
    }
}
class QuickSortTask implements Runnable
{
    /** The back-reference to the class containing the sorting routine.*/
    Project6 proj6;
    /** The ID of this task.*/
    int id;
    /** The lowest index this task goes in the array.*/
    int low;
    /** The highest index this task goes in the array.*/
    int high;
    /** The array to be sorted.*/
    int[] array;
    /**
     * Construct a new task, giving it a class reference containing the sorting
     * routine as well as the array to be sorted.
     *
     * @param proj6 Pass the reference to the class containing necessary sorting routine.
     * @param id The ID of this task.
     * @param low The lowest index this task goes in the array.
     * @param high The highest index this task goes in the array.
     * @param array The array to be sorted.
     */
    public QuickSortTask (Project6 proj6,
                          int id,
                          int low,
                          int high,
                          int[] array)
    {
        this.proj6 = proj6;
        this.id = id;
        this.low = low;
        this.high = high;
        this.array = array;
    }
    /**
     * Instantiates the task and performs the sort on the given array for the
     * specified portions.
     */
    @Override
    public void run()
    {
        proj6.part3 (low, high, array);
    }
}
/**
 * This class contains common, simple helper functions that are globally
 * available to any class that needs them.
 *
 * @author Alex Laird
 * @author Ryan Morehart
 */
 class Utility
{
    /** The number formatter for pretty output.*/
    public static final NumberFormat NUM_FORMAT = new DecimalFormat ("###,###");
    
    /**
     * Builds an array of given size with random values (if random is true) between
     * 0 (inclusive) and MAX_VALUE.  If random is set to false, values are seeded to
     * the indeces of the array.
     * 
     * @param size The size to build the array.
     * @param random True if values should be random, false if values should be seeded.
     * @param MAX_VALUE The maximum value of a randomly generated number.
     * @return The newly built array.
     */
    public static int[] buildArray (int size,
                                    boolean random,
                                    final int MAX_VALUE)
    {
        int[] array = new int[size];
        Random randomizer = new Random ();
        // Loop through and set all array values
        for (int i = 0; i < size; ++i)
        {
            // If random, set value between 0 (inclusive) and MAX_VALUE
            if (random)
            {
                array[i] = randomizer.nextInt(MAX_VALUE);
            }
            // Not random, so set value to the index of the array
            else
            {
                array[i] = i;
            }
        }
        return array;
    }
    /**
     * Verify that the two arrays are equal by sorting the unsorted array, using
     * verified Java sorting libraries, and comparing the two arrays.
     *
     * @param sortedArray The sorted array.
     * @param unsortedArray The unsorted array to be sorted and compared to the sorted array.
     * @return True if the arrays are equal after sorting using Java sorting libraries, false if there was an inconsistency.
     */
    public static boolean verifyArray(int[] sortedArray,
                                      int[] unsortedArray)
    {
        Arrays.sort (unsortedArray);
        for (int i = 0; i < sortedArray.length ;++i)
        {
            if (sortedArray[i] != unsortedArray[i])
            {
                return false;
            }
        }
        return true;
    }
    /**
     * Print the given array.
     *
     * @param array The array to be printed.
     */
    public static void printArray(int[] array)
    {
        for (int i = 0; i < array.length; ++i)
        {
            System.out.print (array[i]);
            if (i < array.length - 1)
            {
                System.out.print (", ");
            }
        }
        System.out.println ();
    }
}
 /**
  * A thread that will sort a set array upon execution.
  *
  * @author Alex Laird
  * @author Ryan Morehart
  */
  class QuickSortThread extends Thread
 {
     /** The back-reference to the class containing the sorting routine.*/
     Project6 proj6;
     /** The ID of this thread.*/
     int id;
     /** The lowest index this thread goes in the array.*/
     int low;
     /** The highest index this thread goes in the array.*/
     int high;
     /** The array to be sorted.*/
     int[] array;
     /**
      * Construct a new thread, giving it a class reference containing the sorting
      * routine as well as the array to be sorted.
      * 
      * @param proj6 Pass the reference to the class containing necessary sorting routine.
      * @param id The ID of this thread.
      * @param low The lowest index this thread goes in the array.
      * @param high The highest index this thread goes in the array.
      * @param array The array to be sorted.
      */
     public QuickSortThread (Project6 proj6,
                             int id,
                             int low,
                             int high,
                             int[] array)
     {
         this.proj6 = proj6;
         this.id = id;
         this.low = low;
         this.high = high;
         this.array = array;
     }
     /**
      * Instantiates the thread and performs the sort on the given array for the
      * specified portions.
      */
     @Override
     public void run()
     {
         proj6.sort (array, low, high);
         proj6.threadFinished (id);
     }
 }