Generics and Collections
Generics and Collections
/* This is wrapper class...
Objective would be to push more functionality into this Class to enforce consistent definition
*/
public abstract class Generics {
public final String masterType = "Generic";
private String type; // extender should define their data type
// generic 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();
// static print method used by extended classes
public static void print(Generics[] objs) {
// print 'Object' properties
System.out.println(objs.getClass() + " " + objs.length);
// print 'Generics' properties
if (objs.length > 0) {
Generics obj = objs[0]; // Look at properties of 1st element
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
// print "Generics: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
}
public class Car extends Generics {
public static KeyTypes key = KeyType.title;
public static void setOrder(KeyTypes key) { Car.key = key; }
public enum KeyType implements KeyTypes {title, name, year, mpg, used}
private final String name;
private final int year;
private final double mpg;
// True if used, false if new
private final boolean used;
public Car(String name, int year, double mpg, boolean used)
{
super.setType("Car");
this.name = name;
this.year = year;
this.mpg = mpg;
this.used = used;
}
@Override
protected KeyTypes getKey() { return Car.key; }
@Override
public String toString()
{
String output="";
if (KeyType.name.equals(this.getKey())) {
output += this.name;
} else if (KeyType.year.equals(this.getKey())) {
output += "00" + this.year;
output = output.substring(output.length() - 2);
} else if (KeyType.mpg.equals(this.getKey())) {
output += this.mpg;
} else if (KeyType.used.equals(this.getKey())) {
output += this.used;
} else {
output += super.getType() + ": " + this.name + ", " + this.used + ", " + this.year + ", " + this.mpg;
}
return output;
}
// Test data initializer
public static Car[] cars() {
return new Car[]{
new Car("Tesla Model 3", 2023, 0, false),
new Car("Toyota Corolla", 2004, 33, true),
new Car("Honda Odyssey", 2010, 22, true)
};
}
public static void main(String[] args)
{
// Inheritance Hierarchy
Car[] objs = cars();
// print with title
Car.setOrder(KeyType.title);
Car.print(objs);
// print name only
Car.setOrder(KeyType.name);
Car.print(objs);
}
}
Car.main(null);
/**
* Implementation of a Double Linked List; forward and backward links point to adjacent Nodes.
*
*/
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;
}
}
import java.util.Iterator;
/**
* Queue Iterator
*
* 1. "has a" current reference in Queue
* 2. supports iterable required methods for next that returns a generic T Object
*/
class QueueIterator<T> implements Iterator<T> {
LinkedList<T> current; // current element in iteration
// QueueIterator is pointed to the head of the list for iteration
public QueueIterator(LinkedList<T> head) {
current = head;
}
// hasNext informs if next element exists
public boolean hasNext() {
return current != null;
}
// next returns data object and advances to next position in queue
public T next() {
T data = current.getData();
current = current.getNext();
return data;
}
}
/**
* Queue: custom implementation
* @author John Mortensen
*
* 1. Uses custom LinkedList of Generic type T
* 2. Implements Iterable
* 3. "has a" LinkedList for head and tail
*/
public class Queue<T> implements Iterable<T> {
LinkedList<T> head = null, tail = null;
/**
* Add a new object at the end of the Queue,
*
* @param data, is the data to be inserted in the Queue.
*/
public void add(T data) {
// add new object to end of Queue
LinkedList<T> tail = new LinkedList<>(data, null);
if (this.head == null) // initial condition
this.head = this.tail = tail;
else { // nodes in queue
this.tail.setNextNode(tail); // current tail points to new tail
this.tail = tail; // update tail
}
}
/**
* Returns the data of head.
*
* @return data, the dequeued data
*/
public T delete() {
T data = this.peek();
if (this.tail != null) { // initial condition
this.head = this.head.getNext(); // current tail points to new tail
if (this.head != null) {
this.head.setPrevNode(tail);
}
}
return data;
}
/**
* Returns the data of head.
*
* @return this.head.getData(), the head data in Queue.
*/
public T peek() {
return this.head.getData();
}
/**
* Returns the head object.
*
* @return this.head, the head object in Queue.
*/
public LinkedList<T> getHead() {
return this.head;
}
/**
* Returns the tail object.
*
* @return this.tail, the last object in Queue
*/
public LinkedList<T> getTail() {
return this.tail;
}
public boolean isEmpty() {
if ((this.getHead() == null) && (this.getTail() == null)) {
return true;
}
else {
return false;
}
}
public int getSize() {
int size = 0;
for (T data : this)
size += 1;
return size;
}
/**
* Returns the iterator object.
*
* @return this, instance of object
*/
public LinkedList<T> next() {
LinkedList<T> next = this.head.getNext();
this.head = next;
return next;
}
public static <T extends Comparable<T>> int compare(T x, T y) {
return x.compareTo(y);
}
public Iterator<T> iterator() {
return new QueueIterator<>(this.head);
}
}
/**
* Queue Manager
* 1. "has a" Queue
* 2. support management of Queue tasks (aka: titling, adding a list, printing)
*/
class QueueManager<T> {
// queue data
private final String name; // name of queue
private int count = 0; // number of objects in queue
public final Queue<T> queue = new Queue<>(); // queue object
/**
* Queue constructor
* Title with empty queue
*/
public QueueManager(String name) {
this.name = name;
}
/**
* Queue constructor
* Title with series of Arrays of Objects
*/
public QueueManager(String name, T[]... seriesOfObjects) {
this.name = name;
this.addList(seriesOfObjects);
}
/**
* Add a list of objects to queue
*/
public void addList(T[]... seriesOfObjects) { //accepts multiple generic T lists
for (T[] objects: seriesOfObjects)
for (T data : objects) {
this.queue.add(data);
this.count++;
}
}
/**
* Print any array objects from queue
*/
public void printQueue() {
System.out.println(this.name + " count: " + count);
System.out.print(this.name + " data: ");
for (T data : queue)
System.out.print(data + " ");
System.out.println();
}
}
/**
* Driver Class
* Tests queue with string, integers, and mixes of Classes and types
*/
class QueueCarTester {
public static void main(String[] args)
{
// Create iterable Queue of NCS Generics
Car.setOrder(Car.KeyType.name);
// Illustrates use of a series of repeating arguments
QueueManager qGenerics = new QueueManager("My Generics", Car.cars());
qGenerics.printQueue();
qGenerics.queue.add(new Car("Tesla Model X", 2022, 0, false));
qGenerics.printQueue();
qGenerics.queue.delete();
qGenerics.printQueue();
qGenerics.queue.delete();
qGenerics.printQueue();
qGenerics.queue.delete();
qGenerics.printQueue();
qGenerics.queue.delete();
qGenerics.printQueue();
}
}
QueueCarTester.main(null);
Merge Sort Implementation using Queues
In the below algorithm, the first element in a queue is used as the pivot. From there, the elements greater than the pivot form a "right" queue, and the elements less than the pivot form a "left" queue. The "left" and "right" queues are both recursively split into subsequent left and right queues, until there is only one element. From there, each left and right queue is combined with the pivot added back in the middle, which creates mini sorted queues. Once everything is combined, the final queue is sorted.
class QueueSort {
public static Queue sort(Queue q) {
// Base case for recursion
if (q.getSize() < 2) {
return q;
}
// Setting the pivot
Integer mid = (Integer) q.peek();
// Creating two sides of the pivot
Queue left = new Queue<>();
Queue right = new Queue<>();
q.delete();
// Populating each side of the pivot
while (q.getSize() > 0) {
Integer element = (Integer) q.delete();
if (element < mid) {
left.add(element);
}
else {
right.add(element);
}
}
// Recursively sorting each side of the pivot
Queue sortedLeft = sort(left);
Queue sortedRight = sort(right);
// Putting each side of the pivot together with the pivot itself to form a sorted queue
Queue sortedComplete = new Queue<>();
while (sortedLeft.getSize() > 0) {
sortedComplete.add(sortedLeft.delete());
}
sortedComplete.add(mid);
while (sortedRight.getSize() > 0) {
sortedComplete.add(sortedRight.delete());
}
return sortedComplete;
}
public static void main(String[] args)
{
// Initializing the queue to be sorted
int[] primitiveArr = new int[] {5, 1, 4, 3, 7, 2};
Integer[] objectArr = new Integer[primitiveArr.length];
for(int i = 0; i < primitiveArr.length; i++) {
objectArr[i] = Integer.valueOf(primitiveArr[i]);
}
QueueManager original = new QueueManager("Original", objectArr);
original.printQueue();
Queue sortedQ = QueueSort.sort(original.queue);
// Parsing the sorted queue to be input into the QueueManager
int length = sortedQ.getSize();
Integer[] sortedArr = new Integer[sortedQ.getSize()];
for (int i = 0; i < length; i++) {
if (i == 0) {
sortedArr[i] = (Integer) sortedQ.getHead().getData();
}
else {
sortedArr[i] = (Integer) sortedQ.next().getData();
}
}
QueueManager sorted = new QueueManager("Sorted", sortedArr);
sorted.printQueue();
}
}
QueueSort.main(null);
Shuffling a Queue
Incomplete, as when I tried to find a solution, I found that it defeated the purpose of using a Queue data structure instead of an array....
import java.lang.Math;
class QueueShuffle {
public static void main(String[] args) {
// Initializing the queue
int[] primitiveArr = new int[] {5, 1, 4, 3, 7, 2};
Integer[] objectArr = new Integer[primitiveArr.length];
for(int i = 0; i < primitiveArr.length; i++) {
objectArr[i] = Integer.valueOf(primitiveArr[i]);
}
QueueManager original = new QueueManager("Original", objectArr);
original.printQueue();
}
}
QueueShuffle.main(null);
public class ConsoleMethods {
//Method to make sure no database is available in the
//input stream
private static void inputFlush() {
try {
while (System.in.available() != 0) {
}
} catch (java.io.IOException e) {
System.out.println("Input error");
}
}
public static void printChar(char txt)
{
System.out.print(txt);
}
public static void clearScreen()
{
printChar('\u000C');
}
public static void print(String txt)
{
System.out.print(txt);
}
public static void println()
{
System.out.println("\n");
}
public static void println(String txt)
{
System.out.println(txt);
}
public static void println(Object obj)
{
System.out.println(obj);
}
public static void printPrompt(String prompt) {
print(prompt + " ");
System.out.flush();
}
public static String inputString(String prompt) {
//inputFlush();
printPrompt(prompt);
return inString();
}
private static String inString() {
int aChar;
StringBuilder s = new StringBuilder();
boolean finished = false;
while (!finished) {
try {
aChar = System.in.read();
if (aChar < 0 || (char) aChar == '\n')
finished = true;
else if ((char) aChar != '\r')
s.append((char) aChar); // Enter into string
}
catch (java.io.IOException e) {
System.out.println("Input error");
finished = true;
}
}
return s.toString();
}
public static int inputInt(String prompt) {
while (true) {
inputFlush();
printPrompt(prompt);
try {
return Integer.parseInt(inString().trim());
}
catch (NumberFormatException e) {
System.out.println("Invalid input. Not an integer");
}
}
}
public static char inputChar(String prompt) {
int aChar = 0;
inputFlush();
printPrompt(prompt);
try {
aChar = System.in.read();
}
catch (java.io.IOException e) {
println("Input error");
}
inputFlush();
return (char) aChar;
}
}
public class Stack<T>
{
private LinkedList<T> lifo = null; // last in first out Object of stack
/**
* Returns the current (LIFO) objects data.
*
* @return the current data in Stack.
*/
public T peek()
{
if (lifo == null)
return null;
else
return lifo.getData();
}
/**
* Inserts a new data object at the top of this Stack,
*
* @param data to be inserted at the top of the Stack.
*/
public void push(T data)
{
// note the order that things happen:
// the new object becomes current and gets a value
// current lifo is parameter, it is assigned as previous node in lifo
lifo = new LinkedList<>(data, lifo);
}
/**
* Removes the top element in the Stack.
*
* @return the popped data from the Stack.
*/
public T pop()
{
T data = null; // empty condition
if (lifo != null) {
data = lifo.getData();
lifo = lifo.getPrevious(); // stack is overwritten with next item
}
return data; // pop always returns data of element popped
}
public boolean isEmpty() {
if (lifo == null) {
return true;
}
else {
return false;
}
}
/**
* Returns a string representation of this Stack,
* polymorphic nature of toString overrides of standard System.out.print behavior
*
* @return string representation of data within Stack
*/
public String toString()
{
StringBuilder stackToString = new StringBuilder("[");
LinkedList<T> node = lifo; // start from the back
while (node != null)
{
stackToString.append(node.getData()); // append the database to output string
node = node.getPrevious(); // go to previous node
if (node != null)
stackToString.append(", ");
} // loop 'till you reach the beginning
stackToString.append("]");
return stackToString.toString();
}
}
class StackDriver<T> {
static public boolean DEBUG = false;
private String title;
public final Stack<T> stack = new Stack<>(); // stack object
public int count;
/**
* Stack constructor
*
* @param title name associated with stack
* @param seriesOfObjects data to be inserted into stack
*/
@SafeVarargs
public StackDriver(String title, T[]... seriesOfObjects) {
this.title = title;
this.addList(seriesOfObjects);
}
/**
* Add a series of data object to the Stack
*
* @param seriesOfObjects data to be inserted into stack
*/
@SafeVarargs
public final void addList(T[]... seriesOfObjects)
{
if (DEBUG) ConsoleMethods.println("Add " + title);
for (T[] objects: seriesOfObjects)
for (T data : objects) {
this.stack.push(data);
this.count++;
if (DEBUG) ConsoleMethods.println("Push: " + this.stack.peek() + " " + this.stack);
}
if (DEBUG) ConsoleMethods.println();
}
/**
* Empty or remove all data objects from the Stack
*
*/
public void emptyStack()
{
if (DEBUG) ConsoleMethods.println("Delete " + title);
while (this.stack.peek() != null) {
T data = this.stack.pop();
if (DEBUG) ConsoleMethods.println("Pop: " + data + " " + stack);
}
if (DEBUG) ConsoleMethods.println();
}
/**
* Print analytics from the Stack
*
*/
public void printStack()
{
ConsoleMethods.println("Size: " + count);
ConsoleMethods.println("Top Element: " + stack.peek());
ConsoleMethods.println("Full Stack: " + stack);
ConsoleMethods.println();
}
}
class Main {
/**
* Test Stack functionality using different types of Objects
*
*/
public static void main(String[] args) {
// Create Stack of Integers
StackDriver.DEBUG = false;
Object[] numbers = new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
StackDriver<Object> sNums = new StackDriver<>("Integers", numbers );
sNums.printStack();
sNums.emptyStack();
// Create iterable Queue of NCS Generics
StackDriver.DEBUG = false;
Car.setOrder(Car.KeyType.name);
// Illustrates use of a series of arrays
StackDriver<Generics> sGenerics = new StackDriver<>("My Generics", Car.cars());
sGenerics.printStack();
sGenerics.emptyStack();
}
}
Main.main(null);
class QueueReverse {
public static void main(String[] args) {
// Initializing the queue
int[] primitiveArr = new int[] {5, 1, 4, 3, 7, 2};
Integer[] objectArr = new Integer[primitiveArr.length];
for(int i = 0; i < primitiveArr.length; i++) {
objectArr[i] = Integer.valueOf(primitiveArr[i]);
}
QueueManager original = new QueueManager("Original", objectArr);
original.printQueue();
Object[] numbers = new Integer[] {};
StackDriver<Object> sNums = new StackDriver<>("Integers", numbers );
int length = original.queue.getSize();
for (int i = 0; i < length; i++) {
sNums.stack.push((Integer) original.queue.delete());
}
sNums.printStack();
}
}
QueueReverse.main(null);