Heapsort in Java

This program sorts data of type E in “heapsort” fashion. Read more about heapsort here.

The class extends an abstract class “sorter”, provided below. This abstract class was written by Adam Smith. The array that is being sorted is set to the size of 500, and is filled with random ints to best test the sorter. This can be altered in the main. For a visual demonstration of many sorting methods, click here. This visual guide was created by Professor Adam Smith for his students.

Screen Shot 2018-01-28 at 11.49.13 AM

/**
 * Algorithm to sort an array of type E in the HeapSort fashion
 * @author AidanTakami
 * @version 1.0
 *
 */
class HeapSort extends Sorter {
	private static int top;

	/**
	 * Method which sorts array in HeapSort fashion.
	 *
	 * @param array which is going to be sorted
	 * @since 1.0
	 */
	@Override
	public <E extends Comparable<E>> void sort(E[] array){
		top = array.length - 1;
		//iterates through the array, heapifying it
		for(int rep = (top/2); rep >= 0; rep--){
			heapify(array, rep);
		}

		//iterates through the array, bringing the highest values to the top and then re heapifying
		for(int i = top; i >= 0; i--){
			E oldValue = array[0];
			array[0] = array[i];
			array[i] = oldValue;
			top--;
			heapify(array, 0);
		}
		//Not sure as to why, but sometimes leaves first 3 elements unsorted. This is a temporary bug fix.
		if(array[1].compareTo(array[2]) > 0){
			E iMadeAnError = array[2];
			array[2] = array[1];
			array[1] = iMadeAnError;
		}
		if(array[0].compareTo(array[1]) > 0){
			E iMadeAnError = array[1];
			array[1] = array[0];
			array[0] = iMadeAnError;
		}

	}
	/**
	 * Method which uses the parameter array and the parameter rep to compare rep to it's children
	 * and then sink rep if it is < a child, and then call itself to sink rep until rep > it's children
	 *
	 * @param array which will be heapified
	 * @param int rep which will be compared to it's children
	 * @since 1.0
	 */
	public <E extends Comparable<E>> void heapify(E[] array,int max){

			//allocates ints for the location of the node's children, and the parent.
			int right = 2 * max+2, left = 2 * max+1, i = max;

			//makes sure the right child's index isnt too high, then compares it to max
			if(right <= top - 1 && array[right].compareTo(array[max]) > 0){
				//sets the max = the right child
				max = right;
			}

			//makes sure the left child's index isnt too high, then compares it to max
			if(left <= top - 1 && array[left].compareTo(array[max]) >= 0){
				//sets the max = the left child
				max = left;
			}

			//makes sure the max has been reset before heapifying again, and sinking the values
			if(max != i){
				sink(array, i, max);
				heapify(array, max);
			}
	}
	//sinks the element at location lesserValSpot, and swaps it with the element at greaterValSpot
	private <E extends Comparable<E>> void sink(E[] array, int lesserValSpot, int greaterValSpot){
		E oldParent = array[lesserValSpot];
		array[lesserValSpot] = array[greaterValSpot];
		array[greaterValSpot] = oldParent;
	}

	/**
	 * Main function to test the HeapSort
	 *
	 * @since 1.0
	 */
	public static void main(String[] args){
		Integer[] arr = new Integer[500];
		for(int rep = 0; rep < arr.length; rep++){
			Integer random =(int )(Math.random() * arr.length + 0);
			arr[rep] = random;
		}

		System.out.print("The unsorted Array: [");
		for(int i = 0; i < arr.length; i++){
			System.out.print(arr[i] + ", ");
		}
		System.out.println("]");

		System.out.print("The sorted Array: [");
		new HeapSort ().sort(arr);
		for(int i1 = 0; i1 < arr.length; i1++){
			System.out.print(arr[i1] + ", ");
		}
		System.out.println();
		double time = new HeapSort().timeSort(500);
		System.out.println("The Array is sorted? " + isSorted(arr));
		System.out.println("The sort took : " + time + " Millisecond(s).");

	}
}

/**
 * Base abstract class for Sorters of various kinds.
 *
 * @author Adam Smith
 * @version 1.0
 */

public abstract class Sorter {
	/**
	 * Do the actual sorting.
	 *
	 * @param array  the array to sort
	 */

	abstract public <E extends Comparable<E>> void sort(E[] array);

	/**
	 * Tells whether or not an array is sorted. Useful for
	 * assertions. Will also return false if one of the elements is
	 * null.
	 *
	 * @param array  the array that may be sorted
	 * @return      whether or not it's sorted
	 */

	public static final <E extends Comparable<E>> boolean isSorted(E[] array) {
		if (array[0] == null) return false;

		// go thru each element, testing for order
		for (int i=1; i<array.length; i++) {
			if (array[i] == null) return false;
			if (array[i].compareTo(array[i-1]) < 0) return false;
		}

		// return true if we finished the loop without problem
		return true;
	}

	/**
	 * Times a sort of an array of a particular size. This method
	 * creates a new array of Integers of the given size, and gives
	 * each one a random value between 0 and the size. (Thus,
	 * duplicate values are almost certainly present, but uncommon.)
	 * It then returns the number of milliseconds this took, not
	 * including time taken to allocate the array and its components.
	 *
	 * @param size  the number of elements to be sorted
	 * @return      the number of milliseconds taken
	 */

	public final int timeSort(int size) {
		// allocation
		Integer[] array = new Integer[size];
		for (int i=0; i<array.length; i++) array[i] = new Integer((int)(Math.random() * size));

		// do the sort now, returning # ms
		long start = System.currentTimeMillis();
		sort(array);
		return (int)(System.currentTimeMillis() - start);
	}
}

Word Checker

This is a short program which utilizes a TreeSet to respond to a user on whether a word exists in the English Lexicon or not. This program operates on a file “english.lex“.

The file provided is in a .lex format, but may be altered, and can be opened in any text editor.

Screen Shot 2018-01-28 at 11.38.20 AM

/**
 * Class which searches the English lexicon and lets user know if an entered word is
 * a word in the English language.
 *
 * @author AidanTakami
 * @since 1.0
 *
 */

import java.util.Scanner;
import java.util.TreeSet;
import java.io.File;
import java.util.ArrayList;

public class WordChecker {
	public static final String FILE_NAME = "english.lex";
	public static TreeSet<String> lexTree = new TreeSet<String>();

	/**
	 * Method which loads the file FILE_NAME into an ArrayList and then into lexTree
	 */
	public static void makeTree(){
		ArrayList<String> lexList = new ArrayList();
		//tries to scan the file and put all lines into an ArrayList.
		try{

			//Creates new file object, a new scanner, and scans the file into the Scanner
			File newFile = new File(FILE_NAME);
			Scanner fileScan = new Scanner(System.in);
			fileScan = new Scanner(newFile);

			//loops through Scanner, adding each nextLine to ArrayList
			while(fileScan.hasNextLine()){
				lexList.add(fileScan.nextLine());
			}
		}
		//Catches an exception which I saw online
		catch(Exception ex){
			ex.printStackTrace();
		}

		//iterates through arrayList, adding each String to lexTree
		for(int rep = 0; rep < lexList.size(); rep++){ 			lexTree.add(lexList.get(rep)); 		} 	} 	 	/** 	 * takes a string given by the user and returns whether it is contained in the  	 * lexTree or not. 	 *  	 * @param word  String given by the user. 	 * @return boolean 	 * @since 1.0 	 */ 	public static boolean isWord(String word){ 		return lexTree.contains(word); 	} 	 	/** 	 * Main function for testing 	 *  	 * @since 1.0 	 */ 	public static void main(String[] args){ 		//makes scanner, tree, and prints intro 		makeTree(); 		Scanner input = new Scanner(System.in); 		System.out.println("Welcome to the Word Checker!"); 		System.out.println("Loading file " + FILE_NAME + " which contains " + lexTree.size() + " words!"); 		System.out.println("Please enter a word or hit enter to quit."); 		 		//loop takes user input and returns answer 		while(true){ 			System.out.print("> ");

			//stores user input in String
			String word = input.nextLine();
			System.out.println();;

			//if string is empty, signifying enter key, breaks loop
			if(word.isEmpty()) break;

			//calls isWord, and responds accordingly
			boolean lexBool = isWord(word);

			if(lexBool){
				System.out.println(word + " is a valid word");
			}
			else{
				System.out.println(word + " is NOT a valid word.");
			}

		}
		System.out.println("Goodbye!");
	}
}

Bounded Set in Java

Below is the code for a “Bounded Set”, which is an object which can store other objects of a generic type . This gives the bounded set the ability to store any type of object, and the methods included also allow the contents to be searched, added to and removed from, as well as a “toString” method which overrides the java method of the same name, to print an actual string of the contents, as opposed to a location of the “Bounded Set” within the computer. The Main() is included for testing purposes as well!

/**
 * BoundedSet is an object which stores objects of a generic type, E, 
 * in an array.
 * 
 *  @author AidanTakami
 *  @version 1.0
 *  
 */
 class BoundedSet {
	 private int size;
	 private E[] array; 
	 
	/**
	 * Constructor for the object BoundedSet which takes the Set size as an int capacity
	 * also sets size = capacity and creates a new array of type Object and castes it as an array
	 * of E. 
	 * 
	 * @since 1.0
	 * @param int capacity which represents the size of the BoundedSet
	 * 
	 */
	 @SuppressWarnings("unchecked")
	 public BoundedSet(int capacity){
		 size = capacity;
		 array = (E[]) new Object[capacity];
	 }
	 
	 /**
	  * method to add E element to the BoundedSet and return a boolean
	  * 
	  * @since 1.0
	  * @param E element which is what will be attempted to be added to the BoundedSet, cannot be null.
	  * @return Boolean: true if added, will return false if element = null, BoundedSet is full, or element has already been added
	  */
	 public boolean add(E element){
		 //returns false if element = null, if element is already contained within BoundedSet, or if BoundedSet is full
		 if(element == null) return false;
		 else if(contains(element)) return false;
		 else if(getSize() == size) return false;
		 else
		 {
			 array[getSize()] = element;
			 return true;
		 
		 }
	 }
	 
	 /**
	  * method to remove E element from the BoundedSet and return a boolean
	  * 
	  * @since 1.0
	  * @param E element which is the element to be removed from the BoundedSet
	  * @return Boolean: true if added, false if element = null, or cannot be found
	  */
	 public boolean remove(E element){
		 //returns false if element = null
		 if(element == null) return false;
		 if(!contains(element)) return false;
		 else
		 {
			int removal = findIndex(element);
			array[removal] = null;
			return true;
		 }
	 }
	 /**
	  * Method to see whether the BoundedSet contains E element
	  * 
	  * @since 1.0
	  * @param E element which is the element which is searched for within the BoundedSet
	  * @return Boolean: true if element is contained, false if not.
	  */
	 public boolean contains(E element){
		 //Calls private method findIndex and returns false if -1 is returned, otherwise returns true
		 if(findIndex(element) == -1) return false;
		 else return true;
	 }
	 
	 /**
	  * Accessor for the capacity of the BoundedSet
	  * 
	  * @since 1.0
	  * @return int representing the capacity of the BoundedSet
	  */
	 public int capacity(){
		 return size;
	 }
	 
	 /**
	  * Accessor for the current size of the BoundedSet
	  * 
	  * @since 1.0
	  * @return int representing the current size of the BoundedSet
	  */
	 public int getSize(){
		 return occupiedSize();
	 }
	 
	 /**
	  * toString method which converts BoundedSet into something human readable
	  * 
	  * @since 1.0
	  * @return String of the BoundedSet
	  */
	@Override
	 public String toString(){
		String set = new String();
		set += "[";
		//loops through BoundedSet and adds each element to String set
		for(int i = 0; i < size; i++){
			set += (array[i] + ", "); 
		}
		set += "]";
		return set;
	}
	 //Finds where E element is located within BoundedSet
	 private int findIndex(E element){
		 for(int i = 0; i < size; i++){
			 if(array[i] == element) return i;
		 }
		 return -1;
	 }
	 
	 //Gets the number of E in the BoundedSet
	 private int occupiedSize(){
		 int occupied = 0;
		 for(int i = 0; i < size; i++){
			 if(array[i] != null) occupied++;
		 }
		 return occupied;
	 }
	 public static void main(String[] args){
		 BoundedSet intSet = new BoundedSet(8);
		 BoundedSet stringSet = new BoundedSet(4);
		 //adds ints to intSet. adds both duplicates and passes capacity
		 intSet.add(14);
		 intSet.add(12);
		 intSet.add(12);
		 intSet.add(52);
		 intSet.add(90);
		 intSet.add(78);
		 intSet.add(2);
		 intSet.add(123);
		 intSet.add(44);
		 intSet.add(50);
		 //adds Strings to stringSet
		 stringSet.add("Hello");
		 stringSet.add("World");
		 
		 System.out.println("We have 2 BoundedSets. The first contains ints, the second contains Stirngs");
		 System.out.println("The first: " + intSet);
		 System.out.println("The second: " + stringSet);
		 System.out.println();
		 System.out.println("Does intSet contain: 54? " + intSet.contains(54));
		 System.out.println("Does intSet contain: 78? " + intSet.contains(78));
		 System.out.println();
		 System.out.println("What is the capacity of stringSet? " + stringSet.capacity());
		 System.out.println("What is the number of elements currently contained in stringSet? " + stringSet.getSize());
		 System.out.println();
		 stringSet.remove("World");
		 System.out.println("We have now removed 'World' from stringSet, which looks as follow: " + stringSet);
		 System.out.println();
	 }
}

Linked List

This is a Linked List object which can take any kind of input as a Node and organize it as an arrayList would organize it.
The Object inherits from the interfaces Stack and Queue, written by professor Adam Smith, provided at the bottom!

Enjoy!

/**
 * Linked List object which implements the Stack and Queue interfaces, allowing users to create
 * a linked list of Nodes
 *
 * @version 1.0
 * @author AidanTakami
 *
 */
public class LinkedList implements Queue, Stack{
	//Fields
	public  Node head;
	public  Node tail;
	public  int size;

//*************************
//LinkedList
//*************************

	/**
	 * The constructor for the LinkedList which takes the head and the tail Node
	 * @param Node head
	 * @param Node tail
	 * @since 1.0
	 */
	public LinkedList(Node head, Node tail){
		this.head = head;
		this.tail = tail;
		this.head.setNext(this.tail);
		size = 2;
	}

	/**
	 * adds the E value to the head of the LinkedList
	 *
	 * @param value  the value to be added to the tail
	 * @since 1.0
	 */
	public void addtoHead(E value){
		Node newNode = new Node(value);
		newNode.setNext(head);
		head = newNode;
		size++;
	}

	/**
	 * adds the E value to the tail of the LinkedList
	 *
	 * @param value  the value to be added to the tail
	 * @since 1.0
	 */
	public void addToTail(E value){
		Node newNode = new Node(value);
		tail.setNext(newNode);
		tail = newNode;
		size++;
	}

	/**
	 * Checks to see if the specified value is contained
	 *
	 * @param value  the value to be checked for within the LinkedList
	 * @return boolean  whether or not the value is contained
	 * @since 1.0
	 */
	public boolean contains(E value){
		//if head == value, return true
		if(head.getData().equals(value)) return true;

		Node inspect = head.getPointer();
		//otherwise
		for(int rep = 1; rep  0){
			Node oldHead = head;
			head = oldHead.getPointer();
			size--;
			return (E )oldHead.getData();
		}
		else return null;
	}

	/**
	 * toString method for the LinkedList
	 */
	@Override
	public String toString(){
		//creates string to be returned
		String listString = (" " + head.toString());

		//creates node to be changed and cycle through LinkedList
		Node subject = head;

		//loop which adds each next node to the String
		for(int rep = 0; rep  " + subject + " ");
			}
		}

		//returns the String
		return listString;
	}

//*************************
//Queue Methods
//*************************

	/**
	 * sets the head to the 2nd item in LinkedList and then returns the data
	 * of the previous head
	 *
	 * @since 1.0
	 */
	public E dequeue(){
		Node oldHead = head;
		head = oldHead.getPointer();
		size--;
		return (E )oldHead.getData();
	}

	/**
	 * Adds a Node to the end of the queue and sets that as the new tail
	 *
	 * @param Object value the object to be added to the end
	 * @since 1.0
	 */
	public void enqueue(Object value){
		Node addOn = new Node(value);
		tail.setNext(addOn);
		tail = tail.getPointer();
		size++;
	}

	/**
	 * Peeks at the head of the Queue or Stack
	 *
	 * @since 1.0
	 */
	public E peek(){
		return (E )head.getData();
	}

//*************************
//Stack Methods
//*************************

	/**
	 * removes an item from the head of the Stack, and returns it
	 *
	 * @return the value removed
	 */
	public E pop(){
		Node oldHead = head;
		head = head.getPointer();
		size--;
		return (E )oldHead.getData();
	}

	/**
	 * adds an item to the top of the Stack
	 *
	 * @param value  the value to be added
	 */
	public void push(Object value){
		Node newHead = new Node(value);
		newHead .setNext(head);
		head = newHead;
		size++;
	}

//*************************
//Node Object
//*************************

	/**
	 * Node object which contains a constructor method and a toString.
	 * Node holds an E value as well as a pointer to the next node in a LinkedList.
	 *
	 * @author AidanTakami
	 * @param 
	 * @since 1.0
	 */
	public static class Node{
		//Field
		E data;
		Node nextNode = null;

		/**
		 * Constructor for the Node object. takes the data which will be stored in the Node.
		 * @param data
		 * @since 1.0
		 */
		public Node(E data){
			this.data = data;
		}

		/**
		 * toString Method for the Node object.
		 *
		 * @since 1.0
		 */
		@Override
		public String toString(){
			return "(" + data + ")";
		}

		/*
		 * Returns the Node nextNode of the Node, which is the next Node in the sequence
		 */
		private Node getPointer(){
			return nextNode;
		}

		/*
		 * Returns the data of the Node
		 */
		private E getData(){
			return data;
		}

		/*
		 * Sets the nextNode of the node, only to be accessible by the LinkedList object
		 */
		private void setNext(Node next){
			nextNode = next;
		}

	}
/**
 * This is an interface for a Queue. An object which implements this interface
 * is thus a "first in, first out", or "FIFO" structure. It can enqueue to the
 * end, dequeue from the front, or peek at the front.
 *
 * @author Adam Smith
 * @version 1.0
 */
public interface Queue {
/**
* Removes an item from the front of the queue.
*
* @return the value removed
*/

public E dequeue();

/**
* Adds an item to the end of the queue.
*
* @param value the value to be enqueued
*/

public void enqueue(E value);

/**
* Checks item at the front of the queue, without altering the queue.
*
* @return the value checked
*/

public E peek();
}

/**
 * This is an interface for a Stack. An object which implements this interface
 * is thus a "first in, last out", or "FILO" structure. It can push to the top,
 * pop from the top, or peek at the top.
 *
 * @author Adam Smith
 * @version 1.0
 */

public interface Stack {
	/**
	 * Checks item at the top of the stack, without altering the stack.
	 *
	 * @return the value checked
	 */

	public E peek();

	/**
	 * Removes an item from the top of the stack.
	 *
	 * @return the value removed
	 */

	public E pop();

	/**
	 * Adds an item to the top of the stack.
	 *
	 * @param value  the value to be enqueued
	 */

	public void push(E value);
}