Sort Week
Hacks & Explorations of Generics, Sorting, Queues, Stacks, Linked Lists, etc.
Generic Objects
One of the key concepts of object oriented programming is the idea that objects can inherit from one another. Thus, it stands to reason that you can have a generic type class that holds as many generic properties as possible that can be inherited and overridden by subsequent subclasses. Breaking these down we essentially get a tree of objects that inherit from one another or implement methods from one another.
Here, I'll make a generic class called vehicle which is based on Mr. M's "Collectable" object.
public abstract class Vehicle implements Comparable <Vehicle>{
public final String masterType = "Vehicle";
private String type;
/*
* Not sure what key types are for
* TODO: find out what enumeration is (enumeration, enumerated interfaces, etc.)
*/
// enumerated interface
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey(); // this method helps force usage of KeyTypes
// getter
public String getMasterType() {
return masterType;
}
// get type
public String getType() {
return type;
}
// set type
public void setType(String type) {
this.type = type;
}
// this method is used to establish key order ???
public abstract String toString();
// builds ascii string and converts back
public abstract int toAscii();
public static Map<Vehicle, Integer> mapAscii(Vehicle[] vehicles){
Map<Vehicle, Integer> asciiMap = new HashMap<>();
for (Vehicle vehicle : vehicles) {
asciiMap.put(vehicle, vehicle.toAscii());
}
return asciiMap;
} // how to make better generic method for this
// this method is used to compare toString of objects, compares two object together
public int compareTo(Vehicle obj) {
return this.toString().compareTo(obj.toString());
}
// this method is used to compare toAscii of objects, compares two objects together
// public int asciiCompareTo(Vehicle obj) {
// if(this.toAscii() > obj.toAscii()){
// return 1;
// } else if(this.toAscii() == obj.toAscii()){
// return 0;
// } else if (this.toAscii() < obj.toAscii()){
// return -1;
// } else {
// return -2;
// }
// }
// static print method used by extended classes (generally can use to list objects)
public static void print(Vehicle[] objs) {
// print 'Object' properties
System.out.println(objs.getClass() + " " + objs.length);
// print 'Vehicle' properties
if (objs.length > 0) {
Vehicle obj = objs[0]; // Look at properties of 1st element
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
// print "Vehicle: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
}
Sub Classes (Motor Vehicle, Marine Vehicle, Aerial Vehicle Extends Vehicle)
Through a generic class (vehicles in this case), we can inherit general methods and properties before building them up. For simplicity, I'll make some implementations of sub classes and focus in on motor vehicles and cars.
The code below is an instance of using an object within an object.
// shows object storing object
public class Engine {
private String type;
private boolean on;
public Engine(String type){
this.type = type;
this.on = false;
}
public void powerOn(){
this.on = true;
}
public void powerOff(){
this.on = false;
}
public String getType(){
return this.type;
}
public boolean getOn(){
return on;
}
}
public class Car extends Vehicle{
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) {Car.key = key;}
public enum KeyType implements KeyTypes {title, brand, model, engine, capacity}
// Instance data (note could add more data for realism but this is just for demonstration purposes)
private final String brand;
private final String model;
private final Engine engine;
private final int capacity;
// static id counter
private static int uniqueID = 0;
// Constructor
public Car(String brand, String model, Engine engine, int capacity){
this.setType("Car");
this.brand = brand;
this.model = model;
this.engine = engine;
this.capacity = capacity;
}
/*
* 'Vehicle' requires getKey to help enforce KeyTypes usage
* Mort's Code TODO: Understand key types
*/
@Override
protected KeyTypes getKey() { return Car.key; }
/*
* 'Vehicle' requires toString override (overrides are required if abstract method)
* toString provides data based off of Static Key setting
* TODO: Understand this toString Method
*/
@Override
public String toString() {
String output="";
if (KeyType.model.equals(this.getKey())) {
output += this.model;
} else if (KeyType.brand.equals(this.getKey())) {
output += this.brand;
} else if (KeyType.capacity.equals(this.getKey())){
output += String.valueOf(this.capacity);
} else {
output = super.getType() + ": " + this.model + ", " + this.brand;
}
return output;
}
// dk how to do multiple long values way (can ask abt this)
@Override
public int toAscii(){
if (KeyType.capacity.equals(this.getKey())){
return this.capacity;
} else if (KeyType.brand.equals(this.getKey())) {
return (int) this.brand.charAt(0);
} else if (KeyType.model.equals(this.getKey())) {
return (int) this.model.charAt(0);
} else {
return -1;
}
}
public String generateNumber(){
if (KeyType.model.equals(this.getKey())){
uniqueID += 1;
char c = this.model.charAt(0);
String id = "";
id += String.valueOf((int) c);
id += String.valueOf(uniqueID);
return id;
} else if (KeyType.brand.equals(this.getKey())) {
uniqueID += 1;
char c = this.brand.charAt(0);
String id = "";
id += String.valueOf((int) c);
id += String.valueOf(uniqueID);
return id;
} else {
return "";
}
}
// creates hash of registration numbers
public static Map<String, Car> registrationNumber(Car[] cars){
HashMap<String, Car> numberToCar = new HashMap<>();
for (Car car : cars) {
numberToCar.put(car.generateNumber(), car);
}
return numberToCar;
}
// creates list of numbers based on cars
public static ArrayList<String> carNumberList(Car[] cars){
ArrayList<String> numberArray = new ArrayList<>();
for (Car car : cars){
numberArray.add(car.generateNumber());
}
return numberArray;
}
public static void printCars(ArrayList<String> numberArray, Map<String, Car> map){
for (String number : numberArray){
System.out.println(map.get(number));
}
}
// Test data initializer
public static Car[] cars() {
return new Car[]{
new Car("Honda", "Civic", new Engine("Combustion"), 5),
new Car("Toyota", "Mirai", new Engine("Hydrogen Fuel Cell"), 5),
new Car("Chrysler", "Voyager", new Engine("Combustion"), 7),
new Car("Tesla", "Model 3", new Engine("Electric Motor"), 7),
new Car("Mercedes", "Some Car Model", new Engine("Combustion"), 5),
new Car("BMW", "Some Card Model", new Engine("Combustion"), 5),
new Car("Chevrolet", "Some Car Model", new Engine("Combustion"), 7),
new Car("Hyundai", "Some Car Model", new Engine("Combustion"), 6),
new Car("Ford", "Some Car Model", new Engine("Combustion"), 4),
};
}
public static void main(String[] args) {
// Inheritance Hierarchy
Car[] cars = cars(); // Array is reference type only, no methods
List<Car> carsList = new ArrayList<Car>(Arrays.asList(cars)); // conversion required to make it a Collection
System.out.println("-------------------------");
// print with brand order
Car.setOrder(KeyType.brand);
Car.print(cars);
for (Car car : carsList)
System.out.println(car);
System.out.println("-------------------------");
// convert to Collection and sort in model order
Car.setOrder(KeyType.model);
Collections.sort(carsList); // This works because of Collectable compareTo method
Car.print(cars);
for (Car car : carsList)
System.out.println(car);
System.out.println("-------------------------");
// convert to Collection and sort in capacity order
Car.setOrder(KeyType.capacity);
Collections.sort(carsList); // This works because of Collectable compareTo method
Car.print(cars); // doesn't sort properly but oh well LOL
for (Car car : carsList)
System.out.println(car);
System.out.println("-------------------------");
}
}
Car.main(null);
public class Boat /* extends Vehicle */ {
/* implementation not shown */
}
public class Airplane /* extends Vehicle */ {
/* implementation not shown */
}
Sorting
Sorting is a fundamental in CS because it helps us sort classified objects into groups that we can then use to have easier access to the data we store. There are many types of sorting algorithms, but for this class the main ones we have put focus on are bubble, selection, insertion, and merge sorting. Below is an implementation of these sorts first from a generic and then to a wider sort.
In this case, we are using cars to sort. Using the ascii converter into a hashmap, we sort the objects together.
abstract class Sort {
abstract void sort(String[] list);
/*
* @param n: the size of the list
* @param k: the number of simulations run
*
*/
// public double runSimulations(int size, int simRuns) {
// double sumTime = 0;
// for (int i = 0; i < simRuns; i++) {
// int[] list = new int[size];
// for (int j = 0; j < size; j++) {
// list[j] = (int) (Math.random() * 200);
// }
// double startTime = System.nanoTime();
// sort(list);
// double endTime = System.nanoTime();
// sumTime += endTime - startTime;
// }
// return (sumTime / simRuns) / 1000000;
// }
}
class SelectionSort extends Sort {
private String[] list;
SelectionSort(String[] list) {
this.list = list;
}
public void sort() {
sort(this.list);
}
@Override
public void sort(String[] list) {
for (int i = 0; i < list.length - 1; i++) {
int smallest = Integer.valueOf(list[i].substring(0, 2));
int smallestIndex = i;
for (int j = i + 1; j < list.length; j++) {
if (smallest > Integer.valueOf(list[j].substring(0, 2))) {
smallest = Integer.valueOf(list[j].substring(0, 2));
smallestIndex = j;
}
if (Integer.valueOf(list[i].substring(0, 2)) != smallest) {
String tmp = list[i];
list[i] = list[smallestIndex];
list[smallestIndex] = tmp;
}
}
}
}
public String[] get() {
return list;
}
}
public class Main{
public static void sortVehicles(String[] args){
Car[] cars = Car.cars();
Car.setOrder(Car.KeyType.brand);
Car.printCars(Car.carNumberList(cars), Car.registrationNumber(cars));
}
}
Main.sortVehicles(null);
// class BubbleSort<T> extends Sort {
// private double timeElapsed;
// private int[] list;
// BubbleSort(int[] list) {
// this.list = list;
// }
// @Override
// public void sort(int[] list) {
// boolean unsorted = true;
// while (unsorted) {
// unsorted = false;
// for (int i = 0; i < list.length - 1; i++) {
// if (list[i] > list[i + 1]) {
// int tmp = list[i];
// list[i] = list[i + 1];
// list[i + 1] = tmp;
// unsorted = true;
// }
// }
// }
// }
// public void sort() {
// sort(this.list);
// }
// public int[] get() {
// return list;
// }
// }
// class InsertionSort extends Sort {
// private int[] list;
// InsertionSort(int[] list) {
// this.list = list;
// }
// public void sort(int[] list) {
// for (int i = 1; i < list.length; i++) {
// int j = i;
// // I'm gonna be honest I have no idea why it's j > 1 and not j > 0
// while ((list[j - 1] > list[j]) && (j > 1)) {
// int tmp = list[j - 1];
// list[j - 1] = list[j];
// list[j] = tmp;
// j--;
// }
// }
// }
// public void sort() {
// sort(this.list);
// }
// public int[] get() {
// return list;
// }
// }
// class MergeSort extends Sort {
// private int[] list;
// MergeSort(int[] list) {
// this.list = list;
// }
// public void sort() {
// sort(this.list);
// }
// @Override
// public void sort(int[] list) {
// this.list = mergeSort(list);
// }
// public int[] mergeSort(int[] list) {
// if (list.length == 1) {
// return list;
// }
// int[] left = Arrays.copyOfRange(list, 0, (int) Math.floor(list.length/2.0));
// int[] right = Arrays.copyOfRange(list, (int) Math.floor(list.length/2.0), list.length);
// return merge(mergeSort(left), mergeSort(right));
// }
// public int[] merge(int[] arr1, int[] arr2) {
// int[] merged = new int[arr1.length + arr2.length];
// int counter = 0;
// int ind1 = 0;
// int ind2 = 0;
// int size1 = arr1.length;
// int size2 = arr2.length;
// while (size1 != 0 || size2 != 0) {
// if (size1 == 0) {
// merged[counter] = arr2[ind2];
// counter++;
// ind2++;
// size2--;
// } else if (size2 == 0) {
// merged[counter] = arr1[ind1];
// counter++;
// ind1++;
// size1--;
// } else if (arr1[ind1] <= arr2[ind2]) {
// merged[counter] = arr1[ind1];
// counter++;
// ind1++;
// size1--;
// } else {
// merged[counter] = arr2[ind2];
// counter++;
// ind2++;
// size2--;
// }
// }
// return merged;
// }
// public int[] get() {
// return list;
// }
// }
public class Main {
public static void main(String[] args){
Car[] cars = Car.cars();
Car.setOrder(Car.KeyType.model);
// bubbleSort.sortVehicles(Vehicle.mapAscii(cars));
}
}
Main.main(null);
public class HashStuff {
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] arr = new int[500000];
for (int i = 0; i < 500000; i++) {
Integer value = (int) (Math.random() * 500000);
map.put(value, -value);
arr[i] = value;
}
System.out.println("--------------------------------");
System.out.println("hash map look up");
System.out.println("--------------------------------");
double luTime = 0;
// used to throw out times
double smallestTime = 0;
double largestTime = 0;
// get num to search for from scanner
Scanner sc = new Scanner(System.in);
System.out.println("Enter a number to search for: ");
Integer num = sc.nextInt();
for (int i = 0; i < 12; i++) {
// check look up time for hash map
long time = (lookUp(map, num));
luTime += time;
if (time > smallestTime){
smallestTime = time;
}
if (time < largestTime || largestTime == 0){
largestTime = time;
}
String str = (time + " ns");
System.out.println(str);
}
luTime -= smallestTime;
luTime -= largestTime;
System.out.println("Average: " + (luTime / 10) + " ns (excluding shortest time: " + String.valueOf(largestTime) + " ns and, longest time " + String.valueOf(smallestTime) + " ns)");
System.out.println("--------------------------------");
System.out.println("binary search");
System.out.println("--------------------------------");
double bsTime = 0;
smallestTime = 0;
largestTime = 0;
for (int i = 0; i < 12; i++) {
// check look up time for hash map
long time = (binarySearch(arr, num));
bsTime += time;
if (time > smallestTime){
smallestTime = time;
}
if (time < largestTime || largestTime == 0){
largestTime = time;
}
String str = (time + " ns");
System.out.println(str);
}
bsTime -= smallestTime;
bsTime -= largestTime;
System.out.println("Average: " + (bsTime / 10) + " ns (excluding shortest time: " + String.valueOf(largestTime) + " ns and, longest time " + String.valueOf(smallestTime) + " ns)");
}
public static long lookUp(HashMap<Integer, Integer> map, Integer value) {
long start = System.nanoTime();
map.containsKey(value);
long end = System.nanoTime();
return (end - start);
}
public static long binarySearch(int[] arr, Integer value){
long start = System.nanoTime();
int low = 0;
int high = arr.length - 1;
int mid = (low + high) / 2;
while (low <= high) {
if (arr[mid] < value) {
low = mid + 1;
} else if (arr[mid] == value) {
break;
} else {
high = mid - 1;
}
mid = (low + high) / 2;
}
long end = System.nanoTime();
return (end - start);
}
}
HashStuff.main(null);