Question
I am getting an error when writing my generic array list methods and I do not know how to fix them. Below is the driver
I am getting an error when writing my generic array list methods and I do not know how to fix them. Below is the driver containing the tests it needs to pass and below that is my code that is almost working.
DRIVER CODE~~~~~~~~~~~~~~~~~
import java.util.Random;
import java.util.ArrayList;
import mypackages.util.DataToolsAL;
/**
* Driver to test methods in your DataTools class.
* @author Mr. Cavanaugh
*
*/
public class Lab10ArrayListGenerics
{
/**
* Number of cases run for each test.
*/
private static final int NUM_TESTS = 5;
/**
* Exclusive limit for finding random numbers.
*/
private static final int RAND_LIMIT = 40;
/**
* Size of the arrays created for standard tests.
*/
private static final int ARRAY_TEST_SIZE = 20;
/**
* Random number generator for creating random data sets and search keys.
*/
private static Random rand = new Random();
/**
* Main method for DataTools testing.
* @param args Not used.
*/
public static void main(String[] args)
{
//Test your linear search implementation
System.out.println("TESTING LINEAR SEARCH");
for (int i = 0; i < NUM_TESTS; i++)
{
System.out.printf("***Linear Search Test %d*** ", i + 1);
System.out.println("--TESTING WITH INTEGERS--");
testLinearInteger();
System.out.println("--TESTING WITH DOUBLES--");
testLinearDouble();
}
//Test your tim sort implementation
System.out.println(" TESTING TIM SORT");
for (int i = 0; i < NUM_TESTS; i++)
{
System.out.printf("***Tim Sort Test %d*** ", i + 1);
System.out.println("--TESTING WITH INTEGERS--");
testTimSortInteger();
System.out.println("--TESTING WITH DOUBLES--");
testTimSortDouble();
}
//Test your binary search implementation
//Note that this will not work if your tim sort does not work!
System.out.println(" TESTING BINARY SEARCH");
for (int i = 0; i < NUM_TESTS; i++)
{
System.out.printf("***Binary Search Test %d*** ", i + 1);
System.out.println("--TESTING WITH INTEGERS--");
testBinaryInteger();
System.out.println("--TESTING WITH DOUBLES--");
testBinaryDouble();
}
//Test your median implementation
//Note that this will not work if your tim sort does not work!
System.out.println(" TESTING MEDIAN");
for (int i = 0; i < NUM_TESTS; i++)
{
System.out.printf("***Median Test %d*** ", i + 1);
System.out.println("--TESTING WITH INTEGERS--");
testMedianInteger();
System.out.println("--TESTING WITH DOUBLES--");
testMedianDouble();
}
}
/**
* A single test of your linear search using Doubles.
*/
private static void testLinearDouble()
{
//Create ArrayList for data
ArrayList data = new ArrayList();
//Randomly generate a value to find
double key = rand.nextInt(RAND_LIMIT);
//Populate the array
populateDataDouble(data, 1);
//Call upon your linear search
int found = DataToolsAL.linearSearch(data, key);
//Output the results
outputData(data);
if (found != -1)
{
System.out.printf("Value of %.1f found at position %d ", key, found);
}
else
{
System.out.printf("Value of %.1f not found ", key);
}
boolean arraysSearch = data.contains(key);
found = found == -1 ? -1 : 1;
if ((found == -1 ? false : true) == arraysSearch)
{
System.out.println("TEST PASSED");
}
else
{
System.out.println("TEST FAILED");
}
}
/**
* A single test of your linear search using Integers.
*/
private static void testLinearInteger()
{
//Create ArrayList for data
ArrayList data = new ArrayList();
//Randomly generate a value to find
int key = rand.nextInt(RAND_LIMIT);
//Populate the array
populateDataInteger(data, 1);
//Call upon your linear search
int found = DataToolsAL.linearSearch(data, key);
//Output the results
outputData(data);
if (found != -1)
{
System.out.printf("Value of %d found at position %d ", key, found);
}
else
{
System.out.printf("Value of %d not found ", key);
}
boolean arraysSearch = data.contains(key);
found = found == -1 ? -1 : 1;
if ((found == -1 ? false : true) == arraysSearch)
{
System.out.println("TEST PASSED");
}
else
{
System.out.println("TEST FAILED");
}
}
/**
* A single test of your tim sort with Integers.
*/
private static void testTimSortInteger()
{
//Create and populate data set
ArrayList data = new ArrayList();
populateDataInteger(data, 1);
//Output original state of the data
System.out.println("ORIGINALLY ORDERED ");
outputData(data);
//Sort and output the ordered data set
DataToolsAL.timSort(data);
System.out.println("SORTED ORDER ");
outputData(data);
//Determine if data is in fact sorted
System.out.printf("TEST %s ", checkOrder(data) ? "PASSED" : "FAILED");
}
/**
* A single test of your tim sort with Doubles.
*/
private static void testTimSortDouble()
{
//Create and populate data set
ArrayList data = new ArrayList();
populateDataDouble(data, 1);
//Output original state of the data
System.out.println("ORIGINALLY ORDERED ");
outputData(data);
//Sort and output the ordered data set
DataToolsAL.timSort(data);
System.out.println("SORTED ORDER ");
outputData(data);
//Determine if data is in fact sorted
System.out.printf("TEST %s ", checkOrder(data) ? "PASSED" : "FAILED");
}
/**
* A single test of your binary search with Integers.
*/
private static void testBinaryInteger()
{
//Create array for data
ArrayList data = new ArrayList();
//Randomly generate a value to find
int key = rand.nextInt(RAND_LIMIT);
//Populate the data
populateDataInteger(data, 1);
//Binary search only works on sorted data!
//Sort the data, your tim sort needs to work!
DataToolsAL.timSort(data);
//Call upon your binary search
int found = DataToolsAL.binarySearch(data, key);
//Output the results
outputData(data);
if (found != -1)
{
System.out.printf("Value of %d found at position %d ", key, found);
}
else
{
System.out.printf("Value of %d not found ", key);
}
boolean arraysSearch = data.contains(key);
found = found == -1 ? -1 : 1;
if ((found == -1 ? false : true) == arraysSearch)
{
System.out.println("TEST PASSED");
}
else
{
System.out.println("TEST FAILED");
}
}
/**
* A single test of your binary search with Doubles.
*/
private static void testBinaryDouble()
{
//Create array for data
ArrayList data = new ArrayList();
//Randomly generate a value to find
double key = rand.nextInt(RAND_LIMIT);
//Populate the data
populateDataDouble(data, 1);
//Binary search only works on sorted data!
//Sort the data, your tim sort needs to work!
DataToolsAL.timSort(data);
//Call upon your binary search
int found = DataToolsAL.binarySearch(data, key);
//Output the results
outputData(data);
if (found != -1)
{
System.out.printf("Value of %.1f found at position %d ", key, found);
}
else
{
System.out.printf("Value of %.1f not found ", key);
}
boolean arraysSearch = data.contains(key);
found = found == -1 ? -1 : 1;
if ((found == -1 ? false : true) == arraysSearch)
{
System.out.println("TEST PASSED");
}
else
{
System.out.println("TEST FAILED");
}
}
/**
* A single test of your median method with Integers.
*/
private static void testMedianInteger()
{
//Create array for data
ArrayList data = new ArrayList();
//Populate the data
populateDataInteger(data, 1);
Integer median = DataToolsAL.median(data);
outputData(data);
System.out.printf("Found Median value of %s ", median);
if (checkOrder(data) && median.equals(data.get(data.size() / 2)))
{
System.out.println("TEST PASSED");
}
else
{
System.out.println("TEST FAILED");
}
}
/**
* A single test of your median method with Doubles.
*/
private static void testMedianDouble()
{
//Create array for data
ArrayList data = new ArrayList();
//Populate the data
populateDataDouble(data, 1);
Double median = DataToolsAL.median(data);
outputData(data);
System.out.printf("Found Median value of %s ", median);
if (checkOrder(data) && median.equals(data.get(data.size() / 2)))
{
System.out.println("TEST PASSED");
}
else
{
System.out.println("TEST FAILED");
}
}
/**
* Given a set of data, determines if the elements are in order.
* @param data Data set to check the order of.
* @param Generic type found in the passed ArrayList. Must be Comparable in order
* to check if order is correct.
* @return Whether or not the data set is in order.
*/
private static > boolean checkOrder(ArrayList data)
{
//Go through the data
for (int i = 0; i < data.size() - 1; i++)
{
//If an unordered pair is found return false...
if (data.get(i).compareTo(data.get(i + 1)) > 0)
{
return false;
}
}
//Otherwise it's all good!
return true;
}
/**
* Randomly populates a given array.
* @param data Array to be randomly populated.
* @param randMultiplier Multiplier to be used with RAND_LIMIT.
*/
private static void populateDataDouble(ArrayList data, int randMultiplier)
{
//Go through each element in array
for (int i = 0; i < ARRAY_TEST_SIZE; i++)
{
//Randomly generate value for current element
data.add((double) rand.nextInt(RAND_LIMIT) * randMultiplier);
}
}
/**
* Randomly populates a given array.
* @param data Array to be randomly populated.
* @param randMultiplier Multiplier to be used with RAND_LIMIT.
*/
private static void populateDataInteger(ArrayList data, int randMultiplier)
{
//Go through each element in array
for (int i = 0; i < ARRAY_TEST_SIZE; i++)
{
//Randomly generate value for current element
data.add(rand.nextInt(RAND_LIMIT) * randMultiplier);
}
}
/**
* Outputs all elements in an ArrayList, showing indices below.
* @param data Array to be output.
* @param Generic type found in the passed ArrayList.
*/
private static void outputData(ArrayList data)
{
//Output the data
System.out.printf("%-7s", "DATA:");
for (int i = 0; i < data.size(); i++)
{
System.out.printf("%4s ", data.get(i));
}
//Output the indices
System.out.printf(" %-7s", "INDEX:");
for (int i = 0; i < data.size(); i++)
{
System.out.printf("%4d ", i);
}
//End with a new line
System.out.println();
}
}
MY CODE~~~~~~~~~~~
package mypackages.util;
import java.util.ArrayList;
import java.util.Collections;
/**
*
* @author Mark
*
*/
public class DataToolsAL
{
/**
* The limit at which insertion sort will be used instead of merge sort.
*/
private static final int TIM_SORT_LIMIT = 10;
/**
* Finds the median of a set of data.
* @param data Data set to find the median of.
* @return Median value of the passed data set.
* @param
*/
public static
{
timSort(data);
return data.get(data.size() / 2);
}
/**
* Performs a linear search on a data set of integers given a key value to search for.
* @param data Set of data to search.
* @param key Value to search for.
* @return If the key is found in data, returns the index of the key, if not found returns -1.
*/
public static
{
for (int i = 0; i < data.size(); i++)
{
if (data.get(i).compareTo(key) == 0)
{
return i;
}
}
return -1;
}
/**
* Performs a binary search on a data set of sorted integers given a key value to search for.
* @param data Sorted set of data to search.
* @param key Value to search for.
* @return If the key is found in data, returns the index of the key, if not found returns -1.
*/
public static
int start = 0;
int end = data.size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (data.get(mid).compareTo(key) == 0) {
return mid;
}
if (data.get(mid).compareTo(key) < 0) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
/**
* This method is the public entry point to the actual timSort method.
* @param data The data set to be ordered.
*/
public static
{
timSort(data, 0, data.size() -1);
}
/**
* A hybrid of Merge Sort and Insertion Sort.
* @param data The data in which the sub-array is located
* @param low Lower index of the sub-array.
* @param high Upper index of the sub-array.
*/
private static
{
if ((high - low) >= 1)
{
int middle1 = (low + high) / 2;
int middle2 = middle1 + 1;
if (data.size() < TIM_SORT_LIMIT)
{
insertionSort(data);
}
else
{
timSort(data, low, middle1);
timSort(data, middle2, high);
}
merge(data, low, middle1, middle2, high);
}
}
/**
* Helper method for merge sort. Merges two sub-arrays into sorted order.
* @param data The data in which the sub-arrays are located
* @param left Lower index of first sub-array.
* @param middle1 Upper index of first sub-array.
* @param middle2 Lower index of second sub-array.
* @param right Upper index of second sub-array.
*/
private static
{
Integer leftIndex = left;
Integer rightIndex = middle2;
Integer combinedIndex = left;
int[] combined = new int[data.size()];
/*System.out.printf("merge: %s ", subarrayString(data, left, middle1));
System.out.printf(" %s ", subarrayString(data, middle2, right));*/
while (leftIndex <= middle1 && rightIndex <= right)
{
if (data.get(leftIndex).compareTo(data.get(rightIndex)) <= 0)
{
combined[combinedIndex++] = (Integer) data.get(leftIndex++);
}
else
{
combined[combinedIndex++] = (Integer) data.get(rightIndex++);
}
}
if (leftIndex == middle2)
{
while (rightIndex <= right)
{
combined[combinedIndex++] = (Integer) data.get(rightIndex++);
}
}
else
{
while (leftIndex <= middle1)
{
combined[combinedIndex++] = (Integer) data.get(leftIndex++);
}
}
for (int i = left; i <= right; i++)
{
Object mo=combined[i];
data.set(2, (T) mo);
//data[i] = combined[i];
}
//System.out.printf(" %s ", subarrayString(data, left, right));
}
/**
* Modified version of the Insertion Sort found in the slides and text.
* Only applies the Insertion Sort upon a sub-array specified by low and high.
* @param data The data in which the sub-array is located
* @param low Lower index of the sub-array.
* @param high Upper index of the sub-array.
*/
private static
{
for (int next = 1; next < data.size(); next++)
{
T insert = data.get(next);
int moveItem = next;
while (moveItem > 0 && data.get(moveItem - 1).compareTo(insert) > 0)
{
data.set(moveItem,data.get(moveItem-1));
//data[moveItem] = data[moveItem - 1];
moveItem--;
}
data.set(moveItem,insert);
}
}
/**
* Method used to create a formatted String containing a specified sub-array.
* @param data Data set containing the sub-array to be formatted.
* @param low Lower index of the sub-array.
* @param high Upper index of the sub-array.
* @return String containing the values in the specified sub-array, spaced to
* match location in the array.
*/
private static
{
StringBuilder temp = new StringBuilder();
for (int i = 0; i < low; i++)
{
temp.append(" ");
}
for (int i = low; i <= high; i++)
{
temp.append(" " + data.get(i));
}
return temp.toString();
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Intelligent Information And Database Systems Asian Conference Aciids 2012 Kaohsiung Taiwan March 19 21 2012 Proceedings Part 3 Lnai 7198
Authors: Jeng-Shyang Pan ,Shyi-Ming Chen ,Ngoc-Thanh Nguyen
2012th Edition
3642284922, 978-3642284922
