Linked List Sorting
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 class Tester {
public static void main(String[] args) {
Stack<Integer> s1 = 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);
System.out.println(s1.toString());
s1.bubbleSort();
System.out.println(s1.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());
}
System.out.println("-------------------------");
// print "Collectable: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
}
public class UserProgress extends Collectable {
// Class data
public static KeyTypes key = KeyType.title; // static initializer
public static void setOrder(KeyTypes key) {UserProgress.key = key;}
public enum KeyType implements KeyTypes {title, name, currentfrq, percentCompletion, grade}
// Instance data
private final String name;
private final int percentCompletion;
private final int grade;
private final String currentfrq;
// Constructor
UserProgress(String name, String currentfrq, int percentCompletion, int grade)
{
this.setType("UserProgress");
this.name = name;
this.percentCompletion = percentCompletion;
this.grade = grade;
this.currentfrq = currentfrq;
}
/* 'Collectable' requires getKey to help enforce KeyTypes usage */
@Override
protected KeyTypes getKey() { return UserProgress.key; }
/* 'Collectable' requires toString override
* toString provides data based off of Static Key setting
*/
@Override
public String toString() {
String output="";
if (KeyType.currentfrq.equals(this.getKey())) {
output += this.currentfrq;
} else if (KeyType.name.equals(this.getKey())) {
output += this.name;
}
else if (KeyType.percentCompletion.equals(this.getKey())) {
output += this.percentCompletion;
} else if (KeyType.grade.equals(this.getKey())) {
output += "" + this.grade;
output = output.substring(output.length() - 2);
} else {
output = super.getType() + ": " + this.name + " (Grade " + this.grade + ") is currently on FRQ "+ this.currentfrq + ", and is " + this.percentCompletion + "% done overall.";
}
return output;
}
// Test data initializer
public static UserProgress[] UserProgressArray() {
return new UserProgress[]{
new UserProgress("Daniel", "2004#2", 20, 12),
new UserProgress("Krish", "2004#1", 17, 11),
new UserProgress("Aadit", "2004#1", 25, 11),
new UserProgress("Rohan", "2019#4", 97, 12),
new UserProgress("Kurtis", "2021#2", 57, 12),
new UserProgress("Yash", "2013#3", 13, 12),
new UserProgress("Nathan", "2022#5", 99, 11)
};
}
public static void main(String[] args)
{
UserProgress[] objs = UserProgressArray();
List<UserProgress> UserProgressArray = new ArrayList<UserProgress>(Arrays.asList(objs));
// print with title
UserProgress.setOrder(KeyType.title);
UserProgress.print(objs);
// convert to coection, sort in name order
UserProgress.setOrder(KeyType.name);
Collections.sort(UserProgressArray);
UserProgress.setOrder(KeyType.title);
System.out.println("-------------------------");
for (UserProgress UserProgress : UserProgressArray)
System.out.println(UserProgress);
}
}
UserProgress.main(null);