CheckPoint 3
Hacks for checkpoint 3
public class LinkedList<T> {
private T data;
private LinkedList<T> prevNode, nextNode;
/**
* Constructs a new element
*
* @param data, data of object
* @param node, previous node
*/
public LinkedList(T data, LinkedList<T> node)
{
this.setData(data);
this.setPrevNode(node);
this.setNextNode(null);
}
/**
* Clone an object,
*
* @param node object to clone
*/
public LinkedList(LinkedList<T> node)
{
this.setData(node.data);
this.setPrevNode(node.prevNode);
this.setNextNode(node.nextNode);
}
/**
* Setter for T data in DoubleLinkedNode object
*
* @param data, update data of object
*/
public void setData(T data)
{
this.data = data;
}
/**
* Returns T data for this element
*
* @return data associated with object
*/
public T getData()
{
return this.data;
}
/**
* Setter for prevNode in DoubleLinkedNode object
*
* @param node, prevNode to current Object
*/
public void setPrevNode(LinkedList<T> node)
{
this.prevNode = node;
}
/**
* Setter for nextNode in DoubleLinkedNode object
*
* @param node, nextNode to current Object
*/
public void setNextNode(LinkedList<T> node)
{
this.nextNode = node;
}
/**
* Returns reference to previous object in list
*
* @return the previous object in the list
*/
public LinkedList<T> getPrevious()
{
return this.prevNode;
}
/**
* Returns reference to next object in list
*
* @return the next object in the list
*/
public LinkedList<T> getNext()
{
return this.nextNode;
}
}
public class Stack<T> {
private LinkedList<T> upper;
private int size;
// constructor initiates null LinkedList<T> object + set size to 0
public Stack() {
this.upper = null;
this.size = 0;
}
// push method for a new element to the upper value
public void push(T data) {
LinkedList<T> newNode = new LinkedList<T>(data, this.upper);
this.upper = newNode;
this.size++;
}
// peek method, return upper
public T peek() {
// try/catch to either return upper or print message if upper doesn't exist
try {
return this.upper.getData();
} catch (NullPointerException e) {
System.out.println("No upper element, empty stack!");
return null;
}
}
// pop method, return upper and remove
public T pop() {
// try/catch to either return + pop upper or print message if upper doesn't exist
try {
T data = this.upper.getData();
this.upper = this.upper.getPrevious();
this.size--;
return data;
} catch (NullPointerException e) {
System.out.println("No upper element, empty stack!");
return null;
}
}
// get size method
public int size() {
return this.size;
}
// isEmpty method, compare size to 0
public boolean isEmpty() {
return this.size == 0;
}
// toString method, from top to bottom
public String toString() {
String s = "[ ";
LinkedList<T> currentNode = upper;
// gets upper node, then keeps going down to previous until previous is null
while (currentNode != null) {
s += currentNode.getData();
currentNode = currentNode.getPrevious();
if (currentNode != null) {
s += ", ";
}
}
s += " ]";
return s;
}
public void bubbleSort() {
// if size is 0 or 1, don't sort
if (this.size <= 1) {
return;
}
// create a new stack to hold sorted values
Stack<T> sorted = new Stack<T>();
while (!this.isEmpty()) {
// empty stack by popping
T temp = this.pop();
// checks if temp is smaller than the top of sorted
while (!sorted.isEmpty() && ((Comparable<T>) sorted.peek()).compareTo(temp) > 0) {
// pop from sorted and push
this.push(sorted.pop());
}
// push temp into sorted
sorted.push(temp);
}
// if sorted still has elements, pop and push to this
while (!sorted.isEmpty()) {
this.push(sorted.pop());
}
}
public void selectionSort() {
// if size is 0 or 1, don't sort
if (this.size <= 1) {
return;
}
// create a new stack to hold sorted values
Stack<T> sorted = new Stack<T>();
while (!this.isEmpty()) {
// empty stack by popping
T temp = this.pop();
// checks if temp is smaller than the top of sorted
while (!sorted.isEmpty() && ((Comparable<T>) sorted.peek()).compareTo(temp) > 0) {
// pop from sorted and push
this.push(sorted.pop());
}
// push temp into sorted
sorted.push(temp);
}
// if sorted still has elements, pop and push to this
while (!sorted.isEmpty()) {
this.push(sorted.pop());
}
}
}
public class Tester {
public static void main(String[] args) {
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
// add objects to queue and print both
s1.push(1);
s1.push(5);
s1.push(3);
s1.push(4);
s1.push(2);
s2.push(1);
s2.push(5);
s2.push(3);
s2.push(4);
s2.push(2);
System.out.println("We are using Bubble Sort");
System.out.println(s1.toString());
s1.bubbleSort();
System.out.println(s1.toString());
System.out.println("We are using Selection Sort");
System.out.println(s2.toString());
s2.selectionSort();
System.out.println(s2.toString());
}
}
Tester.main(null);
public abstract class Collectable implements Comparable <Collectable> {
public final String masterType = "Collectable";
private String type; // extender should define their data type
// enumerated interface
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey(); // this method helps force usage of KeyTypes
// getter
public String getMasterType() {
return masterType;
}
// getter
public String getType() {
return type;
}
// setter
public void setType(String type) {
this.type = type;
}
// this method is used to establish key order
public abstract String toString();
// this method is used to compare toString of objects
public int compareTo(Collectable obj) {
return this.toString().compareTo(obj.toString());
}
// static print method used by extended classes
public static void print(Collectable[] objs) {
// print 'Object' properties
System.out.println(objs.getClass() + " " + objs.length);
// print 'Collectable' properties
if (objs.length > 0) {
Collectable obj = objs[0]; // Look at properties of 1st element
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
// print "Collectable: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
}
public class Sport extends Collectable {
// Class data
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) {Sport.key = key;}
public enum KeyType implements KeyTypes {title, name, date, color}
// Instance data
private final String name;
private final int date;
private final String color;
// Constructor
Sport(String name, int date, String color)
{
this.setType("Sport");
this.name = name;
this.date = date;
this.color = color;
}
/* 'Collectable' requires getKey to help enforce KeyTypes usage */
@Override
protected KeyTypes getKey() { return Sport.key; }
/* 'Collectable' requires toString override
* toString provides data based off of Static Key setting
*/
@Override
public String toString() {
String output="";
if (KeyType.name.equals(this.getKey())) {
output += this.name;
} else if (KeyType.date.equals(this.getKey())) {
output += this.date;
} else if (KeyType.color.equals(this.getKey())) {
output += this.color;
output = output.substring(output.length() - 2);
} else {
output = super.getType() + ": " + this.name + ", " + this.date + ", " + this.color;
}
return output;
}
// Test data initializer
public static Sport[] sports() {
return new Sport[]{
new Sport("Basketball", 1946, "Orange"),
new Sport("Baseball", 1876, "White"),
new Sport("Football", 1920, "Brown"),
new Sport("Soccer", 1863, "Black or White"),
new Sport("Hockey", 1917, "Black"),
};
}
public static void main(String[] args)
{
// Inheritance Hierarchy
Sport[] objs = sports(); // Array is reference type only, no methods
List<Sport> sports = new ArrayList<Sport>(Arrays.asList(objs)); // conversion required to make it a Collection
// print with title
Sport.setOrder(KeyType.title);
Sport.print(objs);
// convert to Coolection and sort in flavor order
Sport.setOrder(KeyType.name);
Collections.sort(sports); // This works because of Collectable compareTo method
Sport.setOrder(KeyType.title);
for (Sport sport : sports)
System.out.println(sport);
}
}
Sport.main(null);
public class SortingAnalyzing {
// create a random array of size 5000
public static int[] randomArray() {
int[] array = new int[5000];
for (int i = 0; i < array.length; i++) {
array[i] = (int) (Math.random() * 10000);
}
return array;
}
// bubble sort with input array
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
// selection sort with input array
public static void selectionSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int min = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
// merge sort with input array
public static void mergeSort(int[] array) {
if (array.length > 1) {
int[] left = leftHalf(array);
int[] right = rightHalf(array);
mergeSort(left);
mergeSort(right);
merge(array, left, right);
}
}
public static int[] leftHalf(int[] array) {
int size1 = array.length / 2;
int[] left = new int[size1];
for (int i = 0; i < size1; i++) {
left[i] = array[i];
}
return left;
}
public static int[] rightHalf(int[] array) {
int size1 = array.length / 2;
int size2 = array.length - size1;
int[] right = new int[size2];
for (int i = 0; i < size2; i++) {
right[i] = array[i + size1];
}
return right;
}
public static void merge(int[] result, int[] left, int[] right) {
int i1 = 0;
int i2 = 0;
for (int i = 0; i < result.length; i++) {
if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) {
result[i] = left[i1];
i1++;
} else {
result[i] = right[i2];
i2++;
}
}
}
// insertion sort with input array
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int current = array[i];
int j = i - 1;
while (j >= 0 && current < array[j]) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = current;
}
}
// create main method and call all the methods on the random array and then print the time taken and then do this for 12 times. When listing out make it in a table format. Also list out the average time for each
public static void main(String[] args) {
int[] average_times = new int[4];
for (int i = 0; i < 12; i++) {
int[] array = randomArray();
long startTime = System.currentTimeMillis();
bubbleSort(array);
long endTime = System.currentTimeMillis();
long time = endTime - startTime;
average_times[0] += time;
System.out.println("Time taken for bubble sort is " + time + " milliseconds");
array = randomArray();
startTime = System.currentTimeMillis();
selectionSort(array);
endTime = System.currentTimeMillis();
time = endTime - startTime;
average_times[1] += time;
System.out.println("Time taken for selection sort is " + time + " milliseconds");
array = randomArray();
startTime = System.currentTimeMillis();
mergeSort(array);
endTime = System.currentTimeMillis();
time = endTime - startTime;
average_times[2] += time;
System.out.println("Time taken for merge sort is " + time + " milliseconds");
array = randomArray();
startTime = System.currentTimeMillis();
insertionSort(array);
endTime = System.currentTimeMillis();
time = endTime - startTime;
average_times[3] += time;
System.out.println("Time taken for insertion sort is " + time + " milliseconds");
}
System.out.println("Average time taken for bubble sort is " + average_times[0] / 12 + " milliseconds");
System.out.println("Average time taken for selection sort is " + average_times[1] / 12 + " milliseconds");
System.out.println("Average time taken for merge sort is " + average_times[2] / 12 + " milliseconds");
System.out.println("Average time taken for insertion sort is " + average_times[3] / 12 + " milliseconds");
}
}
SortingAnalyzing.main(null);
import java.util.*;
public class MapTester {
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] array = new int[1000000];
for (int i = 0; i < array.length; i++) {
Integer value = (int) (Math.random() * 1000000);
array[i] = value;
map.put(value, value);
}
Scanner input = new Scanner(System.in);
System.out.println("Enter a number between 0 and 999999");
// do for loop 12 times and then print out the average time for map lookup and binary search and list it out in a table format
for (int i = 0; i < 12; i++) {
Integer val = input.nextInt();
long time = mapLookup(map, val);
System.out.println("Time taken for map lookup is " + time + " milliseconds");
time = binarySearch(array, val);
System.out.println("Time taken for binary search is " + time + " milliseconds");
}
}
// method that returns time it takes to tdo lookup in a map
public static long mapLookup(HashMap<Integer, Integer> map, Integer val) {
long startTime = System.currentTimeMillis();
map.containsKey(val);
long endTime = System.currentTimeMillis();
long time = endTime - startTime;
return time;
}
// binary search method that is handwritten that takes array and value and returns time it takes to do binary search
public static long binarySearch(int[] array, Integer val) {
long startTime = System.currentTimeMillis();
int low = 0;
int high = array.length - 1;
while (high >= low) {
int mid = (low + high) / 2;
if (array[mid] == val) {
long endTime = System.currentTimeMillis();
long time = endTime - startTime;
return time;
} else if (array[mid] < val) {
low = mid + 1;
} else {
high = mid - 1;
}
}
long endTime = System.currentTimeMillis();
long time = endTime - startTime;
return time;
}
}
MapTester.main(null);
Pros and Cons
| Collection | HashMap |
|---|---|
| Pros | Pros |
| + Simple and easy to use | + Fast access and retrieval |
| + Good for storing and | + Efficient for large data sets |
| iterating over small | + Provides key-value pairs |
| data sets | + No duplicates allowed |
| + Allows duplicates | |
| --------------------------- | ------------------------------ |
| Cons | Cons |
| - Slower access and retrieval | - More complex to use |
| - No efficient key-based | - More memory-intensive |
| access | - Not thread-safe |
| - No guarantee of order | - Requires more code for |
| iteration |