commit 21bb93304ec3c16c09c99804022e710c06238d09 parent f8c9737aa55f435f28fe4f4b423d9a0e89dc76b7 Author: John Kubach <johnkubach@gmail.com> Date: Mon, 15 Oct 2018 18:25:54 -0400 update labs Diffstat:
| A | Lab03/src/lab3/.MyListReferenceBased.java.swp | | | 0 | |
| A | Lab03/src/lab3/Driver.java | | | 218 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab03/src/lab3/ListIndexOutOfBoundsException.java | | | 11 | +++++++++++ |
| A | Lab03/src/lab3/ListInterface.java | | | 17 | +++++++++++++++++ |
| A | Lab03/src/lab3/ListReferenceBased.java | | | 131 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab03/src/lab3/MyListReferenceBased.java | | | 102 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab03/src/lab3/Node.java | | | 41 | +++++++++++++++++++++++++++++++++++++++++ |
| A | Lab04/src/lab4/DNode.java | | | 52 | ++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab04/src/lab4/Driver.java | | | 147 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab04/src/lab4/ListCDLSBased.java | | | 149 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab04/src/lab4/ListIndexOutOfBoundsException.java | | | 11 | +++++++++++ |
| A | Lab04/src/lab4/ListInterface.java | | | 17 | +++++++++++++++++ |
| A | Lab04/src/lab4/ListReferenceBased.java | | | 1 | + |
| A | Lab04/src/lab4/Main.java | | | 25 | +++++++++++++++++++++++++ |
| A | Lab05/src/collections/Driver.java | | | 195 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab05/src/collections/Node.java | | | 41 | +++++++++++++++++++++++++++++++++++++++++ |
| A | Lab05/src/collections/Package.java | | | 47 | +++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab05/src/collections/Sample.java | | | 30 | ++++++++++++++++++++++++++++++ |
| A | Lab05/src/collections/StackException.java | | | 9 | +++++++++ |
| A | Lab05/src/collections/StackInterface.java | | | 43 | +++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab05/src/collections/StackRA.java | | | 79 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab05/src/collections/StackSLS.java | | | 70 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab06/src/lab6/Deq.java | | | 27 | +++++++++++++++++++++++++++ |
| A | Lab06/src/lab6/Driver.java | | | 150 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab06/src/lab6/Driver.sync-conflict-20180301-225031-QVHBCPO.java | | | 148 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab06/src/lab6/DriverDeq.java | | | 114 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab06/src/lab6/DriverDeq.sync-conflict-20180301-225030-FTT5XUP.java | | | 114 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab06/src/lab6/DriverQueue.java | | | 87 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab06/src/lab6/ExtendedQueueException.java | | | 7 | +++++++ |
| A | Lab06/src/lab6/ExtendedQueueInterface.java | | | 8 | ++++++++ |
| A | Lab06/src/lab6/Queue.java | | | 83 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab06/src/lab6/QueueException.java | | | 8 | ++++++++ |
| A | Lab06/src/lab6/QueueInterface.java | | | 41 | +++++++++++++++++++++++++++++++++++++++++ |
| A | Lab07/src/lab7/Driver.java | | | 116 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab07/src/lab7/Factorial.java | | | 37 | +++++++++++++++++++++++++++++++++++++ |
| A | Lab07/src/lab7/Factorial2.java | | | 38 | ++++++++++++++++++++++++++++++++++++++ |
| A | Lab07/src/lab7/Factorial3.java | | | 36 | ++++++++++++++++++++++++++++++++++++ |
| A | Lab07/src/lab7/Towers.java | | | 43 | +++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab08/src/lab8/AscendinglyOrderedStringList.java | | | 135 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab08/src/lab8/AscendinglyOrderedStringListInterface.java | | | 18 | ++++++++++++++++++ |
| A | Lab08/src/lab8/Driver.java | | | 170 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab08/src/lab8/Driver2.java | | | 134 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab08/src/lab8/ListArrayBased.java | | | 106 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab08/src/lab8/ListArrayBasedPlus.java | | | 51 | +++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab08/src/lab8/ListException.java | | | 10 | ++++++++++ |
| A | Lab08/src/lab8/ListIndexOutOfBoundsException.java | | | 11 | +++++++++++ |
| A | Lab08/src/lab8/ListInterface.java | | | 17 | +++++++++++++++++ |
| A | Lab09/src/lab9/Driver.java | | | 177 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab10/src/lab10/Driver.java | | | 173 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab11/src/lab11/BSTPInterface.java | | | 28 | ++++++++++++++++++++++++++++ |
| A | Lab11/src/lab11/BinarySearchTree.java | | | 168 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab11/src/lab11/BinaryTreeBasis.java | | | 39 | +++++++++++++++++++++++++++++++++++++++ |
| A | Lab11/src/lab11/Driver.java | | | 161 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab11/src/lab11/Item.java | | | 10 | ++++++++++ |
| A | Lab11/src/lab11/KeyedItem.java | | | 14 | ++++++++++++++ |
| A | Lab11/src/lab11/MyBinarySearchTree.java | | | 160 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab11/src/lab11/MyBinarySearchTreePlus.java | | | 115 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab11/src/lab11/TreeException.java | | | 7 | +++++++ |
| A | Lab11/src/lab11/TreeNode.java | | | 46 | ++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab12/src/lab12/ChainNode.java | | | 33 | +++++++++++++++++++++++++++++++++ |
| A | Lab12/src/lab12/Driver.java | | | 107 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab12/src/lab12/HashException.java | | | 7 | +++++++ |
| A | Lab12/src/lab12/HashTable.java | | | 121 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | Lab12/src/lab12/HashTableInterface.java | | | 16 | ++++++++++++++++ |
64 files changed, 4527 insertions(+), 0 deletions(-)
diff --git a/Lab03/src/lab3/.MyListReferenceBased.java.swp b/Lab03/src/lab3/.MyListReferenceBased.java.swp Binary files differ. diff --git a/Lab03/src/lab3/Driver.java b/Lab03/src/lab3/Driver.java @@ -0,0 +1,217 @@ +package lab3; + +import java.util.Scanner; + +public class Driver { + Scanner in = new Scanner(System.in); + public static void main(String[] args) { + int menuSelection; + + Driver ui = new Driver(); + MyListReferenceBased myList = new MyListReferenceBased(); + + ui.welcomeMessage(); + + do { + menuSelection = ui.menuSelect(); + System.out.println(menuSelection); + + switch (menuSelection) { + case 1: + ui.addObject(myList); + break; + case 2: + ui.removeObject(myList); + break; + case 3: + ui.getObject(myList); + break; + case 4: + ui.removeAll(myList); + break; + case 5: + ui.printList(myList); + break; + case 6: + ui.deleteLargestObject(myList); + break; + case 7: + myList = ui.reverseList(myList); + break; + case 8: + ui.exit(); + break; + case 9: + ui.deleteSmallestObject(myList); + break; + case 10: + ui.compareStrings(myList); + break; + default: + System.out.println("Enter a valid selection."); + } + }while(menuSelection != 8); + } + + private int menuSelect() { + System.out.print("Make your menu selection now: "); + return Integer.parseInt(in.nextLine()); + } + + private void addObject(MyListReferenceBased myList) { + Object userInput; + int userIndex; + System.out.println("You are now inserting an item into the list"); + System.out.print("Enter item: "); + userInput = in.nextLine(); + System.out.println(userInput); + System.out.print("Enter position to insert item in: "); + userIndex = Integer.parseInt(in.nextLine()); + System.out.println(userIndex); + if (userIndex <= myList.size()) { + myList.add(userIndex, userInput); + System.out.println("Item " + userInput + " inserted in position " + userIndex + " in the list"); + } + else { + System.out.println("Position specified is out of range!"); + } + } + + private void removeObject(MyListReferenceBased myList) { + int userIndex; + System.out.print("Enter position to remove item from "); + userIndex = Integer.parseInt(in.nextLine()); + System.out.println(userIndex); + if (userIndex <= myList.size()) { + System.out.println("Item " + myList.get(userIndex) + " removed from position " + userIndex + " in the list"); + myList.remove(userIndex); + } + else { + System.out.println("Position specified is out of range!"); + } + } + + private void getObject(MyListReferenceBased myList) { + int userIndex; + System.out.print("Enter position to retrieve item from: "); + userIndex = Integer.parseInt(in.nextLine()); + System.out.println(userIndex); + if (userIndex <= myList.size()) { + System.out.println("Item " + myList.get(userIndex) + " retrieved from position " + userIndex + " in the list"); + } + else { + System.out.println("Position specified is out of range!"); + } + } + + private void removeAll(MyListReferenceBased myList) { + myList.removeAll(); + } + + private void printList(MyListReferenceBased myList) { + if (myList.size() > 0) { + System.out.println(myList.toString()); + } + else { + System.out.println("List is empty."); + } + } + + private void deleteLargestObject(MyListReferenceBased myList) { + int largestIndex = 0; + String largestString = ""; + String currentString; + if (myList.size() > 0) { + for (int i = 0; i < myList.size(); i++) { + currentString = myList.get(i).toString(); + if (currentString.compareTo(largestString) > 0 && largestString.compareTo(currentString) < 0 || largestString.equals("")) { + largestIndex = i; + largestString = myList.get(largestIndex).toString(); + } + } + System.out.println("Largest item " + largestString + " deleted."); + myList.remove(largestIndex); + } + else { + System.out.println("List empty, nothing to delete!"); + } + } + + private void deleteSmallestObject(MyListReferenceBased myList) { + int smallestIndex = 0; + String smallestString = ""; + String currentString; + if (myList.size() >0) { + for (int i = 0; i < myList.size(); i++) { + currentString = myList.get(i).toString(); + if (currentString.compareTo(smallestString) < 0 && smallestString.compareTo(currentString) > 0 || smallestString.equals("")) { + smallestIndex = i; + smallestString = myList.get(smallestIndex).toString(); + } + } + System.out.println("Smallest item " + smallestString + " deleted."); + myList.remove(smallestIndex); + } + else { + System.out.println("List empty, nothing to delete!"); + } + } + + private void compareStrings(MyListReferenceBased myList) { + int userIndex, difference; + String str1, str2; + System.out.print("Enter index of first string: "); + userIndex = Integer.parseInt(in.nextLine()); + System.out.println(userIndex); + str1 = myList.get(userIndex).toString(); + System.out.print("Enter index of second string: "); + userIndex = Integer.parseInt(in.nextLine()); + System.out.println(userIndex); + str2 = myList.get(userIndex).toString(); + difference = str1.compareTo(str2); + System.out.println("The difference between these two strings is " + difference); + } + + private MyListReferenceBased reverseList(MyListReferenceBased myList) { + MyListReferenceBased tempList = new MyListReferenceBased(); + int listSize = myList.size(); + if (listSize > 0) { + for (int i = 0; i < listSize; i++) { + tempList.add(i, myList.get(listSize - 1 - i)); + } + + // myList = tempList; + + System.out.println("List has been reversed"); + System.out.print("Here is the content: "); + for (int i = 0; i < listSize; i++) { + System.out.print(tempList.get(i) + " "); + } + System.out.println(); + } + else { + System.out.println("List is empty.. nothing to reverse!"); + } + return tempList; + + } + + private void welcomeMessage() { + System.out.println("Select from the following menu: "); + System.out.println(" 1. Insert item to list"); + System.out.println(" 2. Remove item from list"); + System.out.println(" 3. Get item from list"); + System.out.println(" 4. Clear list"); + System.out.println(" 5. Print size and content of list"); + System.out.println(" 6. Delete largest item in list"); + System.out.println(" 7. Reverse list"); + System.out.println(" 8. Exit program"); + System.out.println(" 9. Delete smallest item in list (EXTRA)"); + System.out.println(" 10. Compare two strings (EXTRA)"); + } + + private void exit() { + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } +} +\ No newline at end of file diff --git a/Lab03/src/lab3/ListIndexOutOfBoundsException.java b/Lab03/src/lab3/ListIndexOutOfBoundsException.java @@ -0,0 +1,11 @@ +package lab3; + +public class ListIndexOutOfBoundsException + extends IndexOutOfBoundsException +{ + public ListIndexOutOfBoundsException(String s) + { + super(s); + } // end constructor +} // end ListIndexOutOfBoundsException + diff --git a/Lab03/src/lab3/ListInterface.java b/Lab03/src/lab3/ListInterface.java @@ -0,0 +1,17 @@ +package lab3; + +// ******************************************************** +// Interface ListInterface for the ADT list. +// ********************************************************* +public interface ListInterface +{ + boolean isEmpty(); + int size(); + void add(int index, Object item) + throws ListIndexOutOfBoundsException; + Object get(int index) + throws ListIndexOutOfBoundsException; + void remove(int index) + throws ListIndexOutOfBoundsException; + void removeAll(); +} // end ListInterface diff --git a/Lab03/src/lab3/ListReferenceBased.java b/Lab03/src/lab3/ListReferenceBased.java @@ -0,0 +1,131 @@ +package lab3; + +// Please note that this code is slightly different from the textbook code +//to reflect the fact that the Node class is implemented using data encapsulation + + +// **************************************************** +// Reference-based implementation of ADT list. +// **************************************************** +public class ListReferenceBased implements ListInterface +{ + // reference to linked list of items + private Node head; + private int numItems; // number of items in list + + public ListReferenceBased() + { + numItems = 0; + head = null; + } // end default constructor + + public boolean isEmpty() + { + return numItems == 0; + } // end isEmpty + + public int size() + { + return numItems; + } // end size + + private Node find(int index) + { + // -------------------------------------------------- + // Locates a specified node in a linked list. + // Precondition: index is the number of the desired + // node. Assumes that 0 <= index <= numItems + // Postcondition: Returns a reference to the desired + // node. + // -------------------------------------------------- + Node curr = head; + for (int skip = 0; skip < index; skip++) + { + curr = curr.getNext(); + } // end for + return curr; + } // end find + + public Object get(int index) + throws ListIndexOutOfBoundsException + { + if (index >= 0 && index < numItems) + { + // get reference to node, then data in node + Node curr = find(index); + Object dataItem = curr.getItem(); + return dataItem; + } + else + { + throw new ListIndexOutOfBoundsException( + "List index out of bounds exception on get"); + } // end if + } // end get + + public void add(int index, Object item) + throws ListIndexOutOfBoundsException + { + if (index >= 0 && index < numItems+1) + { + if (index == 0) + { + // insert the new node containing item at + // beginning of list + Node newNode = new Node(item, head); + head = newNode; + } + else + { + Node prev = find(index-1); + // insert the new node containing item after + // the node that prev references + Node newNode = new Node(item, prev.getNext()); + prev.setNext(newNode); + } // end if + numItems++; + } + else + { + throw new ListIndexOutOfBoundsException( + "List index out of bounds exception on add"); + } // end if + } // end add + + public void remove(int index) + throws ListIndexOutOfBoundsException + { + if (index >= 0 && index < numItems) + { + if (index == 0) + { + // delete the first node from the list + head = head.getNext(); + } + else + { + Node prev = find(index-1); + // delete the node after the node that prev + // references, save reference to node + Node curr = prev.getNext(); + prev.setNext(curr.getNext()); + } // end if + numItems--; + } // end if + else + { + throw new ListIndexOutOfBoundsException( + "List index out of bounds exception on remove"); + } // end if + } // end remove + + public void removeAll() + { + // setting head to null causes list to be + // unreachable and thus marked for garbage + // collection + head = null; + numItems = 0; + } // end removeAll + +} // end ListReferenceBased diff --git a/Lab03/src/lab3/MyListReferenceBased.java b/Lab03/src/lab3/MyListReferenceBased.java @@ -0,0 +1,102 @@ +package lab3; + +public class MyListReferenceBased implements ListInterface{ + private Node head; + + public MyListReferenceBased() { + head = null; + } + + public boolean isEmpty() { + if (head == null) { + return true; + } + return false; + } + + public int size() { + int size = 0; + for (Node temp = head; temp != null; temp = temp.getNext()) { + size++; + } + return size; + } + + private Node find(int index) { + Node curr = head; + for (int skip = 0; skip < index; skip++) { + curr = curr.getNext(); + } + return curr; + } + + public Object get(int index) + throws ListIndexOutOfBoundsException { + if (index >= 0 && index < size()) { + Node curr = find(index); + Object dataItem = curr.getItem(); + return dataItem; + } + else { + throw new ListIndexOutOfBoundsException( + "List index out of bounds exception on get"); + } + } + + public void add(int index, Object item) + throws ListIndexOutOfBoundsException { + if (index >= 0 ) { + if (index == 0) { + Node newNode = new Node(item, head); + head = newNode; + } + else { + Node prev = find(index-1); + Node newNode = new Node(item, prev.getNext()); + prev.setNext(newNode); + } + } + else { + throw new ListIndexOutOfBoundsException( + "List index out of bounds exception on add"); + } + } + + public void remove(int index) + throws ListIndexOutOfBoundsException { + if (index >= 0 && index < size()) { + if (index == 0) { + head = head.getNext(); + } + else { + Node prev = find(index-1); + Node curr = prev.getNext(); + prev.setNext(curr.getNext()); + } + size(); + } + else { + throw new ListIndexOutOfBoundsException( + "List index out of bounds exception on remove"); + } + } + + public void removeAll() { + head = null; + } + + @Override + public String toString() { + Object dataItem; + Node curr = head; + String result = "List of size " + size() + " has the following items : "; + for (int i = 0; i < size(); i++) { + if (curr != null) { + dataItem = curr.getItem(); + curr = curr.getNext(); + result += dataItem + " "; + } + } + return result; + } +} diff --git a/Lab03/src/lab3/Node.java b/Lab03/src/lab3/Node.java @@ -0,0 +1,41 @@ +package lab3; + +//please note that this code is different from the textbook code, because the data is encapsulated! + +public class Node +{ + private Object item; + private Node next; + + public Node(Object newItem) + { + item = newItem; + next = null; + } // end constructor + + public Node(Object newItem, Node nextNode) + { + item = newItem; + next = nextNode; + } // end constructor + + public void setItem(Object newItem) + { + item = newItem; + } // end setItem + + public Object getItem() + { + return item; + } // end getItem + + public void setNext(Node nextNode) + { + next = nextNode; + } // end setNext + + public Node getNext() + { + return next; + } // end getNext +} // end class Node diff --git a/Lab04/src/lab4/DNode.java b/Lab04/src/lab4/DNode.java @@ -0,0 +1,52 @@ +package lab4; + +//please note that this code is different from the textbook code, because the data is encapsulated! + +public class DNode +{ + private Object item; + private DNode next; + private DNode back; + + public DNode(Object newItem) + { + item = newItem; + next = this; + back = this; + } // end constructor + + public DNode(Object newItem, DNode nextNode, DNode previousNode) + { + item = newItem; + next = nextNode; + back = previousNode; + } // end constructor + + public void setItem(Object newItem) + { + item = newItem; + } // end setItem + + public Object getItem() + { + return item; + } // end getItem + + public void setNext(DNode nextNode) + { + next = nextNode; + } // end setNext + + public DNode getNext() + { + return next; + } // end getNext + + public void setBack(DNode previousNode) { + back = previousNode; + } + + public DNode getBack() { + return back; + } +} // end class Node diff --git a/Lab04/src/lab4/Driver.java b/Lab04/src/lab4/Driver.java @@ -0,0 +1,146 @@ +package lab4; + +import java.util.Scanner; + +public class Driver { + Scanner in = new Scanner(System.in); + public static void main(String[] args) { + int menuSelection; + + Driver ui = new Driver(); + ListCDLSBased myList = new ListCDLSBased(); + + ui.welcomeMessage(); + + do { + menuSelection = ui.menuSelect(); + System.out.println(menuSelection); + + switch (menuSelection) { + case 1: + ui.addObject(myList); + break; + case 2: + ui.removeObject(myList); + break; + case 3: + ui.getObject(myList); + break; + case 4: + myList.removeAll(); + break; + case 5: + ui.printList(myList); + break; + case 6: + myList = ui.reverseList(myList); + break; + case 7: + ui.exit(); + break; + default: + System.out.println("Enter a valid selection."); + } + }while(menuSelection != 8); + } + + private int menuSelect() { + System.out.print("Make your menu selection now: "); + return Integer.parseInt(in.nextLine()); + } + + private void addObject(ListCDLSBased myList) { + Object userInput; + int userIndex; + System.out.println("You are now inserting an item into the list"); + System.out.print("Enter item: "); + userInput = in.nextLine(); + System.out.println(userInput); + System.out.print("Enter position to insert item in: "); + userIndex = Integer.parseInt(in.nextLine()); + System.out.println(userIndex); + if (userIndex <= myList.size()) { + myList.add(userIndex, userInput); + System.out.println("Item " + userInput + " inserted in position " + userIndex + " in the list"); + } + else { + System.out.println("Position specified is out of range!"); + } + } + + private void removeObject(ListCDLSBased myList) { + int userIndex; + System.out.print("Enter position to remove item from "); + userIndex = Integer.parseInt(in.nextLine()); + System.out.println(userIndex); + if (userIndex <= myList.size()) { + System.out.println("Item " + myList.get(userIndex) + " removed from position " + userIndex + " in the list"); + myList.remove(userIndex); + } + else { + System.out.println("Position specified is out of range!"); + } + } + + private void getObject(ListCDLSBased myList) { + int userIndex; + System.out.print("Enter position to retrieve item from: "); + userIndex = Integer.parseInt(in.nextLine()); + System.out.println(userIndex); + if (userIndex < myList.size()) { + System.out.println("Item " + myList.get(userIndex) + " retrieved from position " + userIndex + " in the list"); + } + else { + System.out.println("Position specified is out of range!"); + } + } + + private void printList(ListCDLSBased myList) { + if (myList.size() > 0) { + System.out.println(myList.toString()); + } + else { + System.out.println("List is empty."); + } + } + + private ListCDLSBased reverseList(ListCDLSBased myList) { + ListCDLSBased tempList = new ListCDLSBased(); + int listSize = myList.size(); + if (listSize > 0) { + for (int i = 0; i < listSize; i++) { + tempList.add(i, myList.get(listSize - 1 - i)); + System.out.println(tempList.get(i)); + } + + // myList = tempList; + + System.out.println("List has been reversed"); + System.out.print("Here is the content: "); + for (int i = 0; i < listSize; i++) { + System.out.print(tempList.get(i) + " "); + } + System.out.println(); + } + else { + System.out.println("List is empty.. nothing to reverse!"); + } + return tempList; + } + + private void welcomeMessage() { + System.out.println("Select from the following menu: "); + System.out.println(" 1. Insert item to list"); + System.out.println(" 2. Remove item from list"); + System.out.println(" 3. Get item from list"); + System.out.println(" 4. Clear list"); + System.out.println(" 5. Print size and content of list"); + System.out.println(" 6. Reverse List"); + System.out.println(" 7. Exit Program"); + } + + private void exit() { + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } +} +\ No newline at end of file diff --git a/Lab04/src/lab4/ListCDLSBased.java b/Lab04/src/lab4/ListCDLSBased.java @@ -0,0 +1,149 @@ +package lab4; + +// Please note that this code is slightly different from the textbook code +//to reflect the fact that the Node class is implemented using data encapsulation + +// **************************************************** +// Reference-based implementation of ADT list. +// **************************************************** +public class ListCDLSBased implements ListInterface +{ + // reference to linked list of items + private DNode head; + private int numItems; // number of items in list + + public ListCDLSBased() + { + numItems = 0; + head = null; + } // end default constructor + + public boolean isEmpty() + { + return numItems == 0; + } // end isEmpty + + public int size() + { + return numItems; + } // end size + + + private DNode find(int index) + { + DNode curr = head; + if (index > numItems / 2) { + int findIndex = numItems - index; + for (int i = findIndex; i > 0; i--) { + curr = curr.getBack(); + } + return curr; + } + else { + for (int i = index; i > 0; i--) { + curr = curr.getNext(); + } + return curr; + } + } + + public Object get(int index) + throws ListIndexOutOfBoundsException + { + if (index >= 0 && index < numItems) + { + // get reference to node, then data in node + DNode curr = find(index); + Object dataItem = curr.getItem(); + return dataItem; + } + else + { + throw new ListIndexOutOfBoundsException( + "List index out of bounds exception on get"); + } // end if + } // end get + + public void add(int index, Object item) + throws ListIndexOutOfBoundsException { + if (index >= 0 && index < numItems + 1) { + if (head == null) { + DNode newNode = new DNode(item); + head = newNode; + } + else { + DNode curr; + if (index == numItems || index == 0) { + curr = head; + } + else { + curr = find(index); + } + DNode newNode = new DNode(item, curr, curr.getBack()); + curr.getBack().setNext(newNode); + curr.setBack(newNode); + if (index == 0) { + head = newNode; + } + } + numItems++; + } + else { + throw new ListIndexOutOfBoundsException( + "List index out of bounds exception on add"); + } // end if + } // end add + + public void remove(int index) + throws ListIndexOutOfBoundsException + { + if (index >= 0 && index <= numItems) + { + DNode prev; + if (index == 0) { + prev = head.getBack(); + } + else { + prev = find(index - 1); + } + prev.getNext().getNext().setBack(prev); + prev.setNext(prev.getNext().getNext()); + if(index == 0) { + head = prev.getNext(); + } + numItems--; + } + else + { + throw new ListIndexOutOfBoundsException( + "List index out of bounds exception on remove"); + } + } + + public void removeAll() + { + // setting head to null causes list to be + // unreachable and thus marked for garbage + // collection + head = null; + numItems = 0; + } // end removeAll + + @Override + public String toString() { + Object dataItem; + DNode curr = head; + String result = "List of size " + size() + " has the following items : "; + for (int i = 0; i < size(); i++) { + if (curr != null) { + dataItem = curr.getItem().toString(); + curr = curr.getNext(); + result += dataItem + " "; + } + } + return result; + } + + +} // end ListReferenceBased + diff --git a/Lab04/src/lab4/ListIndexOutOfBoundsException.java b/Lab04/src/lab4/ListIndexOutOfBoundsException.java @@ -0,0 +1,11 @@ +package lab4; + +public class ListIndexOutOfBoundsException + extends IndexOutOfBoundsException +{ + public ListIndexOutOfBoundsException(String s) + { + super(s); + } // end constructor +} // end ListIndexOutOfBoundsException + diff --git a/Lab04/src/lab4/ListInterface.java b/Lab04/src/lab4/ListInterface.java @@ -0,0 +1,17 @@ +package lab4; + +// ******************************************************** +// Interface ListInterface for the ADT list. +// ********************************************************* +public interface ListInterface +{ + boolean isEmpty(); + int size(); + void add(int index, Object item) + throws ListIndexOutOfBoundsException; + Object get(int index) + throws ListIndexOutOfBoundsException; + void remove(int index) + throws ListIndexOutOfBoundsException; + void removeAll(); +} // end ListInterface diff --git a/Lab04/src/lab4/ListReferenceBased.java b/Lab04/src/lab4/ListReferenceBased.java @@ -0,0 +1 @@ + diff --git a/Lab04/src/lab4/Main.java b/Lab04/src/lab4/Main.java @@ -0,0 +1,25 @@ +package lab4; + +public class Main { + + public static void main(String[] args) { + ListCDLSBased list = new ListCDLSBased(); + + list.add(0, 1); + System.out.println(list.get(0)); + list.add(1,5); + System.out.println(list.get(1)); + list.add(2,7); + System.out.println(list.get(2)); + list.add(3,10); + System.out.println(list.get(3)); + list.add(4,20); + System.out.println(list.get(4)); + list.add(5, 30); + System.out.println(list.get(5)); + + + System.out.println(); + list.remove(3); + } +} diff --git a/Lab05/src/collections/Driver.java b/Lab05/src/collections/Driver.java @@ -0,0 +1,195 @@ +package collections; + +import java.util.Scanner; + +public class Driver { + Scanner in = new Scanner(System.in); + + public static void main(String[] args) { + int userSelection; + double totalBagWeight = 0; + double totalSampleWeight = 0; + Driver ui = new Driver(); + + /* + try { + StackInterface<String> packageBag = (StackInterface) Class.forName(args[0]).newInstance(); + } + catch (ClassNotFoundException e1) { + e1.printStackTrace(); + } + catch (InstantiationException e1) { + e1.printStackTrace(); + } + catch (IllegalAccessException e1) { + e1.printStackTrace(); + } + */ + + StackRA<Package> packageBag = new StackRA<>(); + StackRA<Sample> sampleBag = new StackRA<>(); + + ui.listOptions(); + + do { + userSelection = ui.menuSelection(); + System.out.println(userSelection); + switch (userSelection) { + case 0: + ui.exitProgram(); + break; + case 1: + totalBagWeight += ui.pickUp(packageBag); + break; + case 2: + if (ui.askForSample(packageBag)) { + ui.addSample(packageBag, sampleBag); // Take a sample if yes. + } + totalBagWeight -= ui.updateBagWeight(packageBag); + totalSampleWeight += ui.dropOff(packageBag); + break; + case 3: + ui.getBagContents(packageBag, totalBagWeight); + break; + case 4: + ui.getSampleContents(sampleBag, totalSampleWeight); + break; + case 5: + totalSampleWeight -= ui.updateSampleWeight(sampleBag); + ui.enjoySample(sampleBag); + break; + case 6: + totalSampleWeight = 0; + sampleBag.popAll(); + System.out.println("Sample bag has been emptied"); + } + } while (userSelection != 0); + } + + public double pickUp(StackRA<Package> myStack) { + String name; + double weight; + int number; + String sender; + String recipient; + + System.out.println("Please specify package info:"); + System.out.print("Item name: "); + name = in.nextLine().trim(); + System.out.print(name); + + System.out.print("Item weight: "); + weight = Double.parseDouble(in.nextLine().trim()); + System.out.print(weight); + + System.out.print("Number of items: "); + number = Integer.parseInt(in.nextLine().trim()); + System.out.print(number); + + System.out.print("Sender: "); + sender = in.nextLine().trim(); + System.out.print(sender); + + System.out.print("Recipient"); + recipient = in.nextLine().trim(); + System.out.print(recipient); + + Package bagPackage = new Package(name, weight, number, sender, recipient); + + + myStack.push(bagPackage); + System.out.println("A package of " + name + " each weighing " + weight + " are now in the bag"); + + return weight * number; + } + + public boolean askForSample(StackRA<Package> bag) { + if (bag.isEmpty()) { + System.out.println("No deliveries to process!"); + return false; + } + else { + char answer; + System.out.println("Here is your package " + bag.peek().getRecipient() + ", may I please, please keep a sample (Y/N)?"); + answer = in.nextLine().charAt(0); + System.out.println(answer); + + if (answer == 'Y') { + return true; + } + return false; + } + } + + public double dropOff(StackRA<Package> myStack) { + if(myStack.isEmpty()) { + return 0; + } + + Package pack = myStack.peek(); + myStack.pop(); + return pack.getWeight(); + } + + public void addSample(StackRA<Package> packageBag, StackRA<Sample> sampleBag) { + Package pack = packageBag.peek(); + Sample newSample = new Sample(pack.getName(), pack.getWeight()); + sampleBag.push(newSample); + } + + public double updateBagWeight(StackRA<Package> bag) { + if (!bag.isEmpty()) { + double weight = bag.peek().getWeight() * bag.peek().getNumber(); + return weight; + } + return 0; + } + + public double updateSampleWeight(StackRA<Sample> bag) { + if (!bag.isEmpty()) { + return bag.peek().getWeight(); + } + return 0; + } + + public void getBagContents(StackRA<Package> bag, double totalWeight) { + System.out.println("Bag has " + bag.size() + " items and weighs " + totalWeight + " lbs"); + } + + public void getSampleContents(StackRA<Sample> samples, double totalWeight) { + + System.out.println("Bag has " + samples.size() + " items and weighs " + totalWeight + " lbs"); + } + + public void enjoySample(StackRA<Sample> sampleBag) { + if (sampleBag.isEmpty()) { + System.out.println("No samples to enjoy!"); + } + else { + System.out.println("This " + sampleBag.peek() + " is amazing! I love free stuff"); + sampleBag.pop(); + } + } + + public int menuSelection() { + System.out.print("Make your menu selection now: "); + return Integer.parseInt(in.nextLine().trim()); + } + + public void listOptions(){ + System.out.println("Select from the following menu:"); + System.out.println(" 0. Exit"); + System.out.println(" 1. Pick up an order"); + System.out.println(" 2. Drop off an order"); + System.out.println(" 3. Display number of packages and weight of bag."); + System.out.println(" 4. Display number of items and weight of bag of samples"); + System.out.println(" 5. Enjoy an item from bag of samples"); + System.out.println(" 6. Empty bag of samples"); + } + + void exitProgram(){ + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } +} + diff --git a/Lab05/src/collections/Node.java b/Lab05/src/collections/Node.java @@ -0,0 +1,41 @@ +package collections; + +//please note that this code is different from the textbook code, because the data is encapsulated! + +public class Node<T> +{ + private T item; + private Node next; + + public Node(T newItem) + { + item = newItem; + next = null; + } // end constructor + + public Node(T newItem, Node nextNode) + { + item = newItem; + next = nextNode; + } // end constructor + + public void setItem(T newItem) + { + item = newItem; + } // end setItem + + public T getItem() + { + return item; + } // end getItem + + public void setNext(Node nextNode) + { + next = nextNode; + } // end setNext + + public Node getNext() + { + return next; + } // end getNext +} // end class Node diff --git a/Lab05/src/collections/Package.java b/Lab05/src/collections/Package.java @@ -0,0 +1,47 @@ +package collections; + +/* +// This class is used to hold the parameters of each package +// Each package is then contained inside a stack or "bag". +*/ + +public class Package { + private String name; + private double weight; + private int number; + private String sender; + private String recipient; + + public Package(String name, double weight, int number, String sender, String recipient) { + this.name = name; + this.weight = weight; + this.number = number; + this.sender = sender; + this.recipient = recipient; + } + + public String getName() { + return name; + } + + public double getWeight() { + return this.weight; + } + + public int getNumber() { + return number; + } + + public String getSender() { + return sender; + } + + public String getRecipient() { + return recipient; + } + + @Override + public String toString() { + return name; + } +} diff --git a/Lab05/src/collections/Sample.java b/Lab05/src/collections/Sample.java @@ -0,0 +1,30 @@ +package collections; + +/* +// Instead of putting Packages into the samples bag, +// we'll create a new object Sample. This way we are +// not storing information that we no longer need. +*/ + +public class Sample { + private String name; + private double weight; + + public Sample(String name, double weight) { + this.name = name; + this.weight = weight; + } + + public String getName() { + return name; + } + + public double getWeight() { + return weight; + } + + @Override + public String toString() { + return name; + } +} diff --git a/Lab05/src/collections/StackException.java b/Lab05/src/collections/StackException.java @@ -0,0 +1,8 @@ +package collections; + +public class StackException + extends java.lang.RuntimeException { + public StackException(String s) { + super(s); + } // end constructor +} // end StackException +\ No newline at end of file diff --git a/Lab05/src/collections/StackInterface.java b/Lab05/src/collections/StackInterface.java @@ -0,0 +1,43 @@ +package collections; + +public interface StackInterface<T> { + public boolean isEmpty(); + // Determines whether the stack is empty. + // Precondition: None. + // Postcondition: Returns true if the stack is empty; + // otherwise returns false. + + public void popAll(); + // Removes all the items from the stack. + // Precondition: None. + // PostCondition: Stack is empty. + + public void push(T newItem) throws StackException; + // Adds an item to the top of a stack. + // Precondition: newItem is the item to be added. + // Postcondition: If insertion is successful, newItem + // is on the top of the stack. + // Exception: Some implementations may throw + // StackException when newItem cannot be placed on + // the stack. + + public T pop() throws StackException; + // Removes the top of a stack. + // Precondition: None. + // Postcondition: If the stack is not empty, the item + // that was added most recently is removed from the + // stack. + // Exception: Throws StackException if the stack is + // empty. + + public T peek() throws StackException; + // Retrieves the top of a stack. + // Precondition: None. + // Postcondition: If the stack is not empty, the item + // that was added most recently is returned. The + // stack is unchanged. + // Exception: Throws StackException if the stack is + // empty. + public String toString(); +} // end StackInterface + diff --git a/Lab05/src/collections/StackRA.java b/Lab05/src/collections/StackRA.java @@ -0,0 +1,79 @@ +package collections; + +public class StackRA<T> implements StackInterface<T>{ + + protected T []items; + protected int numItems; + + public StackRA() { + items = (T[]) new Object[3]; + numItems = 0; + } + + public boolean isEmpty() { + return (numItems == 0); + } + + public int size() { + return numItems; + } + + public void popAll() { + items = (T[]) new Object[3]; + numItems = 0; + } + + public void push (T item) + throws StackException { + + if (numItems == items.length) { + resize(); + } + items[numItems++] = item; + } + + public T pop() + throws StackException { + if (numItems != 0) { + T item = items[numItems -1]; + items[numItems-1] = null; + numItems --; + return item; + } + else { + throw new StackException("StackException: Stack is empty on pop()"); + } + } + + public T peek() + throws StackException { + if (numItems != 0) { + return items[numItems - 1]; + } + else { + throw new StackException("StackException: Stack is empty on peek()"); + } + } + + public void resize() { + T []tmp; + tmp = (T[]) new Object[numItems*2 + 1]; + for (int i = 0; i < items.length; i++) { + tmp[i] = items[i]; + } + items = tmp; + } + + @Override + public String toString() { + String result = "Stack of size " + numItems + " has the following items : "; + + for (int i = 0; i < numItems; i++) { + if (items[i] != null) + result += items[i] + " "; + } + + return result; + } + +} diff --git a/Lab05/src/collections/StackSLS.java b/Lab05/src/collections/StackSLS.java @@ -0,0 +1,70 @@ +package collections; + +public class StackSLS<T> implements StackInterface<T> { + + private Node<T> top; + // private int numItems; + + public StackSLS() { + top = null; + } + + public int size() { + int size = 0; + for (Node temp = top; temp != null; temp = temp.getNext()) { + size++; + } + return size; + } + + public boolean isEmpty() { + return top == null; + } + + public void popAll() { + top = null; + } + + public void push (T item) { + top = new Node<T>(item, top); + } + + public T pop() + throws StackException{ + T result; + if (top == null) { + throw new StackException("StackException: Stack is empty on pop"); + } + else { + result = top.getItem(); + top = top.getNext(); + return result; + } + } + + public T peek() { + if (top == null) { + throw new StackException("StackException: Stack is empty on peek()"); + } + else { + return top.getItem(); + } + } + + @Override + public String toString() { + Object dataItem; + Node curr = top; + String result = "Stack of size " + size() + " has the following items : "; + for (int i = 0; i < size(); i++) { + if (curr != null) { + dataItem = curr.getItem(); + curr = curr.getNext(); + result += dataItem + " "; + } + } + return result; + } + + +} diff --git a/Lab06/src/lab6/Deq.java b/Lab06/src/lab6/Deq.java @@ -0,0 +1,27 @@ +package lab6; + +public class Deq<T> extends Queue<T> implements ExtendedQueueInterface<T>{ + + public void enqueueFirst(T newItem) + throws ExtendedQueueException { + if (numItems == items.length) { + resize(); + } + front = ((((front - 1) % items.length) + items.length) % items.length); + items[front] = newItem; + numItems++; + } + + public T dequeueLast() + throws ExtendedQueueException { + back = ((((back - 1) % items.length) + items.length) % items.length); + T item = items[back]; + items[back] = null; + numItems--; + return item; + } + + public T peekLast() { + return items[((((back - 1) % items.length) + items.length) % items.length)]; + } +} diff --git a/Lab06/src/lab6/Driver.java b/Lab06/src/lab6/Driver.java @@ -0,0 +1,150 @@ +package lab6; + +import java.util.Scanner; + +public class Driver { + + Scanner in = new Scanner(System.in); + + public static void main(String[] args) { + int leftSideSize, rightSideSize, sizeDifference; /* For comparing sizes of words. */ + boolean isPalindrome = false, isSame = true; /* isSame initialized to true for the case where + no characters are entered. */ + Driver ui = new Driver(); + Deq<Character> leftSide = new Deq<>(); + Deq<Character> rightSide = new Deq<>(); + + leftSideSize = ui.insertLeftSide(leftSide); + + if (leftSideSize != -1) { + rightSideSize = ui.insertRightSide(rightSide); + sizeDifference = ui.compareSides(leftSideSize, rightSideSize); + while (!leftSide.isEmpty() && !rightSide.isEmpty()) { + isPalindrome = ui.checkPalindrome(leftSide, rightSide); + if (isSame) { + isSame = ui.checkSame(leftSide, rightSide); + } + leftSide.dequeue(); + if (!leftSide.isEmpty()) { + leftSide.dequeueLast(); + } + rightSide.dequeue(); + if (!rightSide.isEmpty()) { + rightSide.dequeueLast(); + } + } + + if (sizeDifference > 0) { + System.out.println("Left side longer"); + } else if (sizeDifference < 0) { + System.out.println("Right side longer"); + } else { + if (isPalindrome && isSame) { + System.out.println("Same length, same content, palindrome"); + } else if (isSame && !isPalindrome) { + System.out.println("Same length, same content, not palindrome"); + } else { + System.out.println("Same length, different content"); + } + } + } + } + + public int insertLeftSide(Deq<Character> charDeq) { + char userInput; + int leftSideSize = 0; + do { + System.out.print("Enter Character: "); + userInput = in.nextLine().charAt(0); + if (userInput != '*') { + charDeq.enqueue(userInput); + leftSideSize++; + } + if (userInput == '!') { + System.out.println("No Star"); + return -1; + } + }while (userInput != '*'); + return leftSideSize; + } + + public int insertRightSide(Deq<Character> charDeq) { + char userInput; + int rightSideSize = 0; + do { + System.out.print("Enter Character: "); + userInput = in.nextLine().charAt(0); + if (userInput != '!') { + charDeq.enqueue(userInput); + rightSideSize++; + } + }while (userInput != '!'); + return rightSideSize; + } + + public int compareSides(int leftSide, int rightSide) { + if (leftSide - rightSide == 0) { + return 0; + } + else if (leftSide - rightSide < 0) { + return -1; + } + else { + return 1; + } + } + + public boolean checkPalindrome(Deq<Character> leftSide, Deq<Character> rightSide) { + if (leftSide.peek() != rightSide.peekLast()) { + return false; + } + else { + return true; + } + } + + public boolean checkSame(Deq<Character> leftSide, Deq<Character> rightSide) { + if (leftSide.peek() != rightSide.peek() || leftSide.peekLast() != rightSide.peekLast()) { + return false; + } + else { + return true; + } + } + + public void insertItem(Deq myQueue, Object item) { + System.out.println("Item " + item + " has been added"); + myQueue.enqueue(item); + + } + + public void insertFirst(Deq myQueue, Object item) { + System.out.println("Item " + item + " has been added"); + myQueue.enqueueFirst(item); + } + + public void removeItem(Deq myQueue) { + System.out.println("Item " + myQueue.dequeue() + " has been removed"); + } + + public void removeLast(Deq myQueue) { + System.out.println("Item " + myQueue.dequeueLast() + " has been removed"); + } + + public void peek(Deq myQueue) { + System.out.println(myQueue.peek()); + } + + public void peekLast(Deq myQueue) { + System.out.println(myQueue.peekLast()); + } + + public void clear(Deq myQueue) { + myQueue.dequeueAll(); + } + + public void display(Deq myQueue) { + System.out.println(myQueue.toString()); + } + +} diff --git a/Lab06/src/lab6/Driver.sync-conflict-20180301-225031-QVHBCPO.java b/Lab06/src/lab6/Driver.sync-conflict-20180301-225031-QVHBCPO.java @@ -0,0 +1,148 @@ +package lab6; + +import java.util.Scanner; + +public class Driver { + + Scanner in = new Scanner(System.in); + + public static void main(String[] args) { + int leftSideSize, rightSideSize, sizeDifference; /* For comparing sizes of words. */ + boolean isPalindrome = false, isSame = true; /* isSame initialized to true for the case where + no characters are entered. */ + Driver ui = new Driver(); + Deq<Character> leftSide = new Deq<>(); + Deq<Character> rightSide = new Deq<>(); + + leftSideSize = ui.insertLeftSide(leftSide); + + if (leftSideSize != -1) { + rightSideSize = ui.insertRightSide(rightSide); + sizeDifference = ui.compareSides(leftSideSize, rightSideSize); + while (!leftSide.isEmpty() && !rightSide.isEmpty()) { + isPalindrome = ui.checkPalindrome(leftSide, rightSide); + isSame = ui.checkSame(leftSide, rightSide); + leftSide.dequeue(); + if (!leftSide.isEmpty()) { + leftSide.dequeueLast(); + } + rightSide.dequeue(); + if (!rightSide.isEmpty()) { + rightSide.dequeueLast(); + } + } + + if (sizeDifference > 0) { + System.out.println("Left side longer"); + } else if (sizeDifference < 0) { + System.out.println("Right side longer"); + } else { + if (isPalindrome && isSame) { + System.out.println("Same length, same content, palindrome"); + } else if (isSame && !isPalindrome) { + System.out.println("Same length, same content, not palindrome"); + } else { + System.out.println("Same length, different content"); + } + } + } + } + + public int insertLeftSide(Deq<Character> charDeq) { + char userInput; + int leftSideSize = 0; + do { + System.out.print("Enter Character: "); + userInput = in.nextLine().charAt(0); + if (userInput != '*') { + charDeq.enqueue(userInput); + leftSideSize++; + } + if (userInput == '!') { + System.out.println("No Star"); + return -1; + } + }while (userInput != '*'); + return leftSideSize; + } + + public int insertRightSide(Deq<Character> charDeq) { + char userInput; + int rightSideSize = 0; + do { + System.out.print("Enter Character: "); + userInput = in.nextLine().charAt(0); + if (userInput != '!') { + charDeq.enqueue(userInput); + rightSideSize++; + } + }while (userInput != '!'); + return rightSideSize; + } + + public int compareSides(int leftSide, int rightSide) { + if (leftSide - rightSide == 0) { + return 0; + } + else if (leftSide - rightSide < 0) { + return -1; + } + else { + return 1; + } + } + + public boolean checkPalindrome(Deq<Character> leftSide, Deq<Character> rightSide) { + if (leftSide.peek() != rightSide.peekLast()) { + return false; + } + else { + return true; + } + } + + public boolean checkSame(Deq<Character> leftSide, Deq<Character> rightSide) { + if (leftSide.peek() != rightSide.peek()) { + return false; + } + else { + return true; + } + } + + public void insertItem(Deq myQueue, Object item) { + System.out.println("Item " + item + " has been added"); + myQueue.enqueue(item); + + } + + public void insertFirst(Deq myQueue, Object item) { + System.out.println("Item " + item + " has been added"); + myQueue.enqueueFirst(item); + } + + public void removeItem(Deq myQueue) { + System.out.println("Item " + myQueue.dequeue() + " has been removed"); + } + + public void removeLast(Deq myQueue) { + System.out.println("Item " + myQueue.dequeueLast() + " has been removed"); + } + + public void peek(Deq myQueue) { + System.out.println(myQueue.peek()); + } + + public void peekLast(Deq myQueue) { + System.out.println(myQueue.peekLast()); + } + + public void clear(Deq myQueue) { + myQueue.dequeueAll(); + } + + public void display(Deq myQueue) { + System.out.println(myQueue.toString()); + } + +} diff --git a/Lab06/src/lab6/DriverDeq.java b/Lab06/src/lab6/DriverDeq.java @@ -0,0 +1,114 @@ +package lab6; + +import java.util.Scanner; + +public class DriverDeq { + Scanner in = new Scanner(System.in); + public static void main(String[]args) { + int userSelection; + DriverDeq ui = new DriverDeq(); + Deq<Object> myDeq = new Deq<>(); + + ui.listOptions(); + + do { + userSelection = ui.menuSelection(); + System.out.println(userSelection); + switch (userSelection) { + case 1: + ui.insertItem(myDeq); + break; + case 2: + ui.insertFirst(myDeq); + break; + case 3: + ui.removeItem(myDeq); + break; + case 4: + ui.removeLast(myDeq); + break; + case 5: + ui.peek(myDeq); + break; + case 6: + ui.peekLast(myDeq); + break; + case 7: + ui.clear(myDeq); + break; + case 8: + ui.display(myDeq); + break; + case 9: + ui.exitProgram(); + break; + } + } while (userSelection != 0); + + } + + public void insertItem(Deq myQueue) { + Object newItem; + System.out.print("Enter item: "); + newItem = in.nextLine(); + myQueue.enqueue(newItem); + System.out.println("Item " + newItem + " has been added to the back"); + + } + + public void insertFirst(Deq myQueue) { + Object newItem; + System.out.print("Enter item: "); + newItem = in.nextLine(); + myQueue.enqueueFirst(newItem); + System.out.println("Item " + newItem + " has been added to the back"); + } + + public void removeItem(Deq myQueue) { + System.out.println("Item " + myQueue.dequeue() + " has been removed from the front"); + } + + public void removeLast(Deq myQueue) { + System.out.println("Item " + myQueue.dequeueLast() + " has been removed from the back"); + } + + public void peek(Deq myQueue) { + System.out.println(myQueue.peek()); + } + + public void peekLast(Deq myQueue) { + System.out.println(myQueue.peekLast()); + } + + public void clear(Deq myQueue) { + myQueue.dequeueAll(); + } + + public void display(Deq myQueue) { + System.out.println(myQueue.toString()); + } + + public int menuSelection() { + System.out.print("Make your menu selection now: "); + return Integer.parseInt(in.nextLine().trim()); + } + + public void listOptions() { + System.out.println("Select from the following menu:"); + System.out.println(" 1. Insert item in back of Deq"); + System.out.println(" 2. Insert item at front of Deq"); + System.out.println(" 3. Remove item from front of Deq"); + System.out.println(" 4. Remove item from back of Deq"); + System.out.println(" 5. Display front of Deq"); + System.out.println(" 6. Display back of Deq"); + System.out.println(" 7. Clear Deq"); + System.out.println(" 8. Display contents of Deq"); + System.out.println(" 9. Exit"); + } + + void exitProgram(){ + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } +} + diff --git a/Lab06/src/lab6/DriverDeq.sync-conflict-20180301-225030-FTT5XUP.java b/Lab06/src/lab6/DriverDeq.sync-conflict-20180301-225030-FTT5XUP.java @@ -0,0 +1,114 @@ +package lab6; + +import java.util.Scanner; + +public class DriverDeq { + Scanner in = new Scanner(System.in); + public static void main(String[]args) { + int userSelection; + DriverDeq ui = new DriverDeq(); + Deq<Object> myDeq = new Deq<>(); + + ui.listOptions(); + + do { + userSelection = ui.menuSelection(); + System.out.println(userSelection); + switch (userSelection) { + case 1: + ui.insertItem(myDeq); + break; + case 2: + ui.insertFirst(myDeq); + break; + case 3: + ui.removeItem(myDeq); + break; + case 4: + ui.removeLast(myDeq); + break; + case 5: + ui.peek(myDeq); + break; + case 6: + ui.peekLast(myDeq); + break; + case 7: + ui.clear(myDeq); + break; + case 8: + ui.display(myDeq); + break; + case 9: + ui.exitProgram(); + break; + } + } while (userSelection != 0); + + } + + public void insertItem(Deq myQueue) { + Object newItem; + System.out.print("Enter item: "); + newItem = in.nextLine(); + myQueue.enqueue(newItem); + System.out.println("Item " + newItem + " has been added to the back"); + + } + + public void insertFirst(Deq myQueue) { + Object newItem; + System.out.print("Enter item: "); + newItem = in.nextLine(); + myQueue.enqueueFirst(newItem); + System.out.println("Item " + newItem + " has been added to the back"); System.out.println("Item " + item + " has been added to the front"); + } + + public void removeItem(Deq myQueue) { + System.out.println("Item " + myQueue.dequeue() + " has been removed from the front"); + } + + public void removeLast(Deq myQueue) { + System.out.println("Item " + myQueue.dequeueLast() + " has been removed from the back"); + } + + public void peek(Deq myQueue) { + System.out.println(myQueue.peek()); + } + + public void peekLast(Deq myQueue) { + System.out.println(myQueue.peekLast()); + } + + public void clear(Deq myQueue) { + myQueue.dequeueAll(); + } + + public void display(Deq myQueue) { + System.out.println(myQueue.toString()); + } + + public int menuSelection() { + System.out.print("Make your menu selection now: "); + return Integer.parseInt(in.nextLine().trim()); + } + + public void listOptions() { + System.out.println("Select from the following menu:"); + System.out.println(" 1. Insert item in back of Deq"); + System.out.println(" 2. Insert item at front of Deq"); + System.out.println(" 3. Remove item from front of Deq"); + System.out.println(" 4. Remove item from back of Deq"); + System.out.println(" 5. Display front of Deq"); + System.out.println(" 6. Display back of Deq"); + System.out.println(" 7. Clear Deq"); + System.out.println(" 8. Display contents of Deq"); + System.out.println(" 9. Exit"); + } + + void exitProgram(){ + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } +} + diff --git a/Lab06/src/lab6/DriverQueue.java b/Lab06/src/lab6/DriverQueue.java @@ -0,0 +1,87 @@ +package lab6; + +import java.util.Scanner; + +public class DriverQueue { + + Scanner in = new Scanner(System.in); + public static void main(String[]args) { + int userSelection; + DriverQueue ui = new DriverQueue(); + Queue<Object> myQueue = new Queue<>(); + + ui.listOptions(); + + do { + userSelection = ui.menuSelection(); + System.out.println(userSelection); + switch (userSelection) { + case 1: + ui.insertItem(myQueue); + break; + case 2: + ui.removeItem(myQueue); + break; + case 3: + ui.peek(myQueue); + break; + case 4: + ui.clear(myQueue); + break; + case 5: + ui.display(myQueue); + break; + case 6: + ui.exitProgram(); + break; + } + } while (userSelection != 0); + + } + + public void insertItem(Queue myQueue) { + Object newItem; + System.out.print("Enter item: "); + newItem = in.nextLine(); + myQueue.enqueue(newItem); + System.out.println("Item " + newItem + " has been added to the back"); + + } + + public void removeItem(Queue myQueue) { + System.out.println("Item " + myQueue.dequeue() + " has been removed from the front"); + } + + public void peek(Queue myQueue) { + System.out.println(myQueue.peek()); + } + + public void clear(Queue myQueue) { + myQueue.dequeueAll(); + } + + public void display(Queue myQueue) { + System.out.println(myQueue.toString()); + } + + public int menuSelection() { + System.out.print("Make your menu selection now: "); + return Integer.parseInt(in.nextLine().trim()); + } + + public void listOptions() { + System.out.println("Select from the following menu:"); + System.out.println(" 1. Insert item in back of Queue"); + System.out.println(" 2. Remove item from front of Queue"); + System.out.println(" 3. Display front of Queue"); + System.out.println(" 4. Clear Queue"); + System.out.println(" 5. Display contents of Queue"); + System.out.println(" 6. Exit"); + } + + void exitProgram(){ + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } +} + diff --git a/Lab06/src/lab6/ExtendedQueueException.java b/Lab06/src/lab6/ExtendedQueueException.java @@ -0,0 +1,7 @@ +package lab6; + +public class ExtendedQueueException extends RuntimeException { + public ExtendedQueueException(String s) { + super(s); + } // end constructor +} // end ExtendedQueueException diff --git a/Lab06/src/lab6/ExtendedQueueInterface.java b/Lab06/src/lab6/ExtendedQueueInterface.java @@ -0,0 +1,8 @@ +package lab6; + +public interface ExtendedQueueInterface<T> { + + public void enqueueFirst(T newItem) throws ExtendedQueueException; + public T dequeueLast() throws ExtendedQueueException; + public T peekLast() throws ExtendedQueueException; +} // end ExtendedQueueInterface diff --git a/Lab06/src/lab6/Queue.java b/Lab06/src/lab6/Queue.java @@ -0,0 +1,83 @@ +package lab6; + +public class Queue<T> implements QueueInterface<T> { + + T [] items; + int front; + int back; + int numItems; + + public Queue() { + front = back = numItems = 0; + items = (T[]) new Object[3]; + } + + public boolean isEmpty() { + if (numItems == 0) { + return true; + } + return false; + } + + public void enqueue(T newItem) + throws QueueException { + if (numItems == items.length) { + resize(); + } + items[back] = newItem; + back = (back + 1) % items.length; + numItems ++; + } + + public T dequeue() + throws QueueException { + if (numItems != 0) { + T item = items[front]; + items[front] = null; + front = (front + 1) % items.length; + numItems--; + return item; + } + else { + throw new QueueException("QueueException: Queue is empty on dequeue"); + } + } + + public void dequeueAll() { + items = (T[]) new Object[3]; + front = back = numItems = 0; + } + + public T peek() + throws QueueException { + if (numItems != 0) { + return items[front]; + } + else { + throw new QueueException("QueueException: Queue is empty on peek"); + } + } + + protected void resize() { + T []tmp; + tmp = (T[]) new Object[numItems*2 + 1]; + for (int i = 0; i < items.length; i++) { + tmp[i] = items[(front + i) % items.length]; + } + front = 0; + back = numItems; + items = tmp; + } + + @Override + public String toString() { + String result = "Queue of size " + numItems + " has the following items: "; + if(numItems == 0) + result = "No items"; + for(int i = 0; i < numItems; i++) { + result += items[(i + front) % items.length] + " "; + } + return result; + } +} + diff --git a/Lab06/src/lab6/QueueException.java b/Lab06/src/lab6/QueueException.java @@ -0,0 +1,8 @@ +package lab6; + +public class QueueException extends RuntimeException { + + public QueueException(String s) { + super(s); + } // end constructor +} // end QueueException diff --git a/Lab06/src/lab6/QueueInterface.java b/Lab06/src/lab6/QueueInterface.java @@ -0,0 +1,41 @@ +package lab6; + +public interface QueueInterface<T> { + + public boolean isEmpty(); + // Determines whether a queue is empty. + // Precondition: None. + // Postcondition: Returns true if the queue is empty; + // otherwise returns false. + + public void enqueue(T newItem) throws QueueException; + // Adds an item at the back of a queue. + // Precondition: newItem is the item to be inserted. + // Postcondition: If the operation was successful, newItem + // is at the back of the queue. Some implementations + // may throw QueueException if newItem cannot be added + // to the queue. + + public T dequeue() throws QueueException; + // Retrieves and removes the front of a queue. + // Precondition: None. + // Postcondition: If the queue is not empty, the item that + // was added to the queue earliest is removed. If the queue is + // empty, the operation is impossible and QueueException is thrown. + + public void dequeueAll(); + // Removes all items of a queue. + // Precondition: None. + // Postcondition: The queue is empty. + + public T peek() throws QueueException; + // Retrieves the item at the front of a queue. + // Precondition: None. + // Postcondition: If the queue is not empty, the item + // that was added to the queue earliest is returned. + // If the queue is empty, the operation is impossible + // and QueueException is thrown. + + public String toString(); +} // end QueueInterface + diff --git a/Lab07/src/lab7/Driver.java b/Lab07/src/lab7/Driver.java @@ -0,0 +1,116 @@ +package lab7; + +import java.util.Scanner; + +public class Driver { + + Scanner in = new Scanner(System.in); + + public static void main (String args[]) { + Driver binomial= new Driver(); + int n = 6; + int k = 4; + + System.out.print("Enter n "); + n = binomial.getInput(); + System.out.print(n); + System.out.println(); + + System.out.print("Enter k "); + k = binomial.getInput(); + System.out.print(k); + System.out.println(); + System.out.println(); + + System.out.println(binomial.recursiveBinomial(n, k)); + binomial.displayTriangle(n+1); + System.out.println(binomial.iterativeBinomial(n+1, k+1)); + System.out.println(binomial.formulaBinomial(n, k)); + } + + public int recursiveBinomial(int n, int k) { + int result; + + if (k == n || k == 0) { + result = 1; + } + else { + result = recursiveBinomial(n - 1, k - 1) + recursiveBinomial(n - 1, k); + } + return result; + } + + public int iterativeBinomial(int n, int k) { + int[][] pascal = new int[n +1][]; + pascal[1] = new int[1 + 3]; + pascal[1][1] = 1; + for (int i = 2; i <= n; i++) { + pascal[i] = new int[i + 2]; + for (int j = 1; j < pascal[i].length - 1; j++) { + pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]; + } + } + // System.out.println(pascal[n][k]); + return pascal[n][k]; + } + + public int formulaBinomial(int n, int k) { + int result; + int top = 1; + int bot = 1; + if (n - k > k) { + for (int i = (n-k+1); i <= n; i++) { + top *= i; + } + //System.out.println(top); + for (int i = 1; i <= k; i++ ) { + bot *= i; + } + //System.out.println(bot); + result = top/bot; + return result; + } + else { + for (int i = (k+1); i <= n; i++) { + top *= i; + + } + for (int i = 1; i <= (n-k); i++) { + bot *= i; + } + result = top/bot; + return result; + } + } + + public void displayTriangle(int n) { + int[][] pascal = new int[n +1][]; + pascal[1] = new int[1 + 2]; + pascal[1][1] = 1; + for (int i = 2; i <= n; i++) { + pascal[i] = new int[i + 2]; + for (int j = 1; j < pascal[i].length - 1; j++) { + pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]; + } + } + for (int i = 1; i <= n; i++) { + for (int j = 1; j < pascal[i].length - 1; j++) { + System.out.print(pascal[i][j] + " "); + } + System.out.println(); + } + } + + public int factorial(int n) { + int result = 1; + for (int i = 1; i <=n; i++) { + result *= i; + } + return result; + } + + public int getInput() { + int userIn = Integer.parseInt(in.nextLine()); + return userIn; + } +} diff --git a/Lab07/src/lab7/Factorial.java b/Lab07/src/lab7/Factorial.java @@ -0,0 +1,37 @@ +package lab7; + +import java.math.BigInteger; +import java.util.Scanner; + +public class Factorial { + Scanner in = new Scanner(System.in); + public static void main(String[] args) { + int n; + + Factorial factorial = new Factorial(); + + n = factorial.getInput(); + System.out.println(factorial.recursiveFactorial(n)); + + } + + public int recursiveFactorial(int n) { + int result; + // double[] array = new double[1000000000]; + if (n == 1 || n == 0) { + result = 1; + } + else { + result = n * recursiveFactorial(n - 1); + } + return result; + } + + public int getInput() { + int userIn; + System.out.print("Enter number to calculate factorial: "); + userIn = Integer.parseInt(in.nextLine()); + return userIn; + } + +} diff --git a/Lab07/src/lab7/Factorial2.java b/Lab07/src/lab7/Factorial2.java @@ -0,0 +1,38 @@ +package lab7; + +import java.util.Scanner; + +public class Factorial2 { + + Scanner in = new Scanner(System.in); + public static void main(String[] args) { + long n; + + Factorial2 factorial = new Factorial2(); + + n = factorial.getInput(); + System.out.println(factorial.recursiveFactorial(n)); + + } + + public long recursiveFactorial(long n) { + long result; + // double[] array = new double[1000000000]; + if (n == 1 || n == 0) { + result = 1; + } + else { + result = n * recursiveFactorial(n - 1); + } + return result; + } + + public long getInput() { + long userIn; + System.out.print("Enter number to calculate factorial: "); + userIn = Long.parseLong(in.nextLine()); + return userIn; + } + + +} diff --git a/Lab07/src/lab7/Factorial3.java b/Lab07/src/lab7/Factorial3.java @@ -0,0 +1,36 @@ +package lab7; + +import java.math.BigInteger; +import java.util.Scanner; + +public class Factorial3 { + Scanner in = new Scanner(System.in); + public static void main(String[] args) { + BigInteger n; + + Factorial3 factorial = new Factorial3(); + + n = factorial.getInput(); + System.out.println(factorial.recursiveFactorial(n)); + + } + + public BigInteger recursiveFactorial(BigInteger n) { + BigInteger result; + // double[] array = new double[1000000000]; + if (n.intValue() == 1 || n.intValue() == 0) { + result = BigInteger.valueOf(1); + } + else { + result = n.multiply( recursiveFactorial(n.subtract(BigInteger.valueOf(1)))); + } + return result; + } + + public BigInteger getInput() { + BigInteger userIn; + System.out.print("Enter number to calculate factorial: "); + userIn = in.nextBigInteger(); + return userIn; + } +} diff --git a/Lab07/src/lab7/Towers.java b/Lab07/src/lab7/Towers.java @@ -0,0 +1,43 @@ +package lab7; + +import java.util.Scanner; + +public class Towers { + Scanner in = new Scanner(System.in); + public static int count = 0; + public static int moves = 0; + + public static void main(String args[]) { + int n; + + Towers towers = new Towers(); + + n = towers.getInput(); + towers.solve(n, "Initial", "Destination", "Temporary"); + count++; + System.out.println("Number of method calls: " + count); + System.out.println("Number of disk moves " + moves); + + } + + public void solve(int n, String Initial, String Destination, String Temp) { + count++; + if (n == 1) { + System.out.println("Move disk 1 from: " + Initial + " to " + Destination); + moves++; + } + else { + solve(n - 1, Initial, Temp, Destination); + System.out.println("Move disk " + n + " from " + Initial + " to " + Destination); + moves++; + solve(n - 1, Temp, Destination, Initial); + } + } + + public int getInput() { + int userIn; + System.out.print("Enter number of towers: "); + userIn = Integer.parseInt(in.nextLine()); + return userIn; + } +} diff --git a/Lab08/src/lab8/AscendinglyOrderedStringList.java b/Lab08/src/lab8/AscendinglyOrderedStringList.java @@ -0,0 +1,135 @@ +package lab8; + +public class AscendinglyOrderedStringList implements AscendinglyOrderedStringListInterface { + private static final int MAX_LIST = 3; + protected String []items; + protected int numItems; + + public AscendinglyOrderedStringList() + { + items = new String[MAX_LIST]; + numItems = 0; + } + + public boolean isEmpty() + { + return (numItems == 0); + } + + public int size() + { + return numItems; + } + + public String get(int index) + throws ListIndexOutOfBoundsException + { + if (index >= 0 && index < numItems) + { + return items[index]; + } + else + { + throw new ListIndexOutOfBoundsException( + "ListIndexOutOfBoundsException on get"); + } + } + + public void add(String item) { + int index; + + if (numItems == items.length) { + resize(); + } + + index = search(item); + if (index <= 0) { + index = -index; + for (int pos = numItems - 1; pos >= index; pos--) + { + items[pos + 1] = items[pos]; + } + items[index] = item; + System.out.println("Item " + item + "inserted in position " + (index)); + numItems++; + } else { + System.out.println("Item already exists"); + } + } + + public void remove(int index) + throws ListIndexOutOfBoundsException + { + if (index >= 0 && index < numItems) + { + for (int pos = index+1; pos < numItems; pos++) + + { + items[pos-1] = items[pos]; + } + items[numItems - 1] = null; + numItems--; + } + else + { + throw new ListIndexOutOfBoundsException( + "ListIndexOutOfBoundsException on remove"); + } + } + + /* + * Using binary method II + */ + + public int search(String item) { + int low = 0; + int high = items.length-1; + while (low < high) { + int mid = (low+high)/2; + String midKey = items[mid]; + + if (items[mid] == null || midKey.compareTo(item) >= 0) { + high = mid; + } + else { + low = mid + 1; + } + } + + if (item.equals(items[low])) { + low = low + 1; + return low; + } + else { + low = -low; + return low; + } + } + + public void clear() + { + items = new String[MAX_LIST]; + numItems = 0; + } + + public void resize() { + String []tmp; + tmp = new String[numItems*2 + 1]; + for (int i = 0; i < numItems; i++) { + tmp[i] = items[i]; + } + items = tmp; + } + + @Override + public String toString() { + String result = "List of size " + size() + " has the following items : "; + + for (int i = 0; i < size(); i++) { + if (items[i] != null) + result += items[i] + " "; + } + + return result; + } +} diff --git a/Lab08/src/lab8/AscendinglyOrderedStringListInterface.java b/Lab08/src/lab8/AscendinglyOrderedStringListInterface.java @@ -0,0 +1,18 @@ +package lab8; + +public interface AscendinglyOrderedStringListInterface { + boolean isEmpty(); + + int size(); + + void add(String item) throws ListIndexOutOfBoundsException; + + String get(int index) throws ListIndexOutOfBoundsException; + + void remove(int index) throws ListIndexOutOfBoundsException; + + int search(String item); + + void clear(); + +} diff --git a/Lab08/src/lab8/Driver.java b/Lab08/src/lab8/Driver.java @@ -0,0 +1,170 @@ +package lab8; + +/* + * Purpose: Data Structure and Algorithms Lab 8 Problem 1 + * Status: Complete and thoroughly tested + * Last update: 04/09/18 + * Submitted: 04/09/18 + * Comment: test suite and sample run attached + * @author: John Kubach + * @version: 2018.04.09 + */ + +import java.util.Scanner; + +public class Driver { + Scanner in = new Scanner(System.in); + public static void main(String[] args) { + int userSelection; + Driver ui = new Driver(); + + ListArrayBasedPlus<Integer> listArrayPlus = new ListArrayBasedPlus<>(); + + ui.listOptions(); + + do { + userSelection = ui.menuSelection(); + System.out.println(userSelection); + switch (userSelection) { + case 1: + ui.insertItem(listArrayPlus); + break; + case 2: + ui.removeItem(listArrayPlus); + break; + case 3: + ui.getItem(listArrayPlus); + break; + case 4: + ui.getSearchInput(listArrayPlus); + break; + case 5: + listArrayPlus.removeAll(); + break; + case 6: + ui.printList(listArrayPlus); + break; + case 7: + ui.exitProgram(); + } + } while (userSelection != 7); + } + + + public void insertItem(ListArrayBasedPlus<Integer> listArrayPlus) { + int searchKey; + int index; + System.out.println("Your are now entering an item"); + System.out.print(" Enter item: "); + searchKey = Integer.parseInt(in.nextLine()); + System.out.println(searchKey); + + + index = searchList(listArrayPlus, searchKey); + if (index >= 0) { + listArrayPlus.add(index, searchKey); + System.out.println(searchKey + " added at index " + index); + } + else if (index < 0) { + System.out.println("Item already exists at index " + (-index - 1)); + } + } + + /* + * Using method III from class. + */ + + public void getSearchInput(ListArrayBasedPlus listArrayPlus) { + int searchKey; + int result; + System.out.print("Enter key: "); + searchKey = Integer.parseInt(in.nextLine()); + System.out.println(searchKey); + + result = searchList(listArrayPlus, searchKey); + if (result >= 0) { + System.out.println(searchKey + " not found, stopped at index " + result); + } + else if (result < 0) { + System.out.println("Key found at index " + (-result - 1)); + } + + } + + public int searchList(ListArrayBasedPlus<Integer> listArrayPlus, int searchKey) { + int index; + for (index = 0; index < listArrayPlus.size(); index++) { + + System.out.println(listArrayPlus.get(index)); + if (searchKey == listArrayPlus.get(index)) { + return (-index - 1); + } + } + return index; + } + + + public void removeItem(ListArrayBasedPlus listArrayPlus) { + int index; + System.out.print("Enter position to remove item from: "); + index = Integer.parseInt(in.nextLine().trim()); + System.out.println(index); + + if (index >= listArrayPlus.size()) + { + System.out.println("Index is out of range!"); + } + else { + System.out.println("Item " + listArrayPlus.get(index) + " removed from position " + index + " in the list"); + listArrayPlus.remove(index); + } + } + + + public void getItem(ListArrayBasedPlus listArrayPlus) { + int index; + System.out.print("Enter position to retrieve from list "); + index = Integer.parseInt(in.nextLine().trim()); + System.out.println(index); + + if (index >= listArrayPlus.size()) { + System.out.println("Index is out of range!"); + } + else { + System.out.println("Item " + listArrayPlus.get(index) + " retrieved from position " + index + " in the list"); + } + } + + + + public void printList(ListArrayBasedPlus listArrayPlus) { + if (listArrayPlus.size() == 0) + { + System.out.println("List is empty"); + } + else { + System.out.println(listArrayPlus.toString()); + } + } + + public int menuSelection() { + System.out.print("Make your menu selection now: "); + return Integer.parseInt(in.nextLine()); + } + + public void listOptions(){ + System.out.println("Select from the following menu:"); + System.out.println(" 1. Insert item to list"); + System.out.println(" 2. Remove item from list"); + System.out.println(" 3. Get item from list"); + System.out.println(" 4. Search for a specified item in the list"); + System.out.println(" 5. Clear list"); + System.out.println(" 6. Print size and contents of list"); + System.out.println(" 7. Exit program"); + } + + void exitProgram(){ + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } +} diff --git a/Lab08/src/lab8/Driver2.java b/Lab08/src/lab8/Driver2.java @@ -0,0 +1,134 @@ +package lab8; + +import java.util.Scanner; +public class Driver2 { + + Scanner in = new Scanner(System.in); + public static void main(String[] args) { + int userSelection; + Driver2 ui = new Driver2(); + + AscendinglyOrderedStringList orderedList = new AscendinglyOrderedStringList(); + ui.listOptions(); + + do { + userSelection = ui.menuSelection(); + System.out.println(userSelection); + switch (userSelection) { + case 1: + ui.insertItem(orderedList); + break; + case 2: + ui.removeItem(orderedList); + break; + case 3: + ui.getItem(orderedList); + break; + case 4: + ui.searchList(orderedList); + break; + case 5: + orderedList.clear(); + break; + case 6: + ui.printList(orderedList); + break; + case 7: + ui.exitProgram(); + } + } while (userSelection != 7); + } + + + + public void insertItem(AscendinglyOrderedStringList orderedList) { + String searchKey; + System.out.println("Your are now entering an item"); + System.out.print(" Enter item: "); + searchKey = in.nextLine(); + System.out.println(searchKey); + orderedList.add(searchKey); + } + + + + public void removeItem(AscendinglyOrderedStringList orderedList) { + int index; + System.out.print("Enter position to remove item from: "); + index = Integer.parseInt(in.nextLine().trim()); + System.out.println(index); + + if (index >= orderedList.size()) + { + System.out.println("Index is out of range!"); + } + else { + System.out.println("Item " + orderedList.get(index) + " removed from position " + index + " in the list"); + orderedList.remove(index); + } + } + + + public void getItem(AscendinglyOrderedStringList orderedList) { + int index; + System.out.print("Enter position to retrieve from list "); + index = Integer.parseInt(in.nextLine().trim()); + System.out.println(index); + + if (index >= orderedList.size()) { + System.out.println("Index is out of range!"); + } + else { + System.out.println("Item " + orderedList.get(index) + " retrieved from position " + index + " in the list"); + } + } + + public void searchList(AscendinglyOrderedStringList orderedList) { + String key; + int index; + System.out.print("Enter key to search: "); + key = in.nextLine().trim(); + + index = orderedList.search(key); + if (index > 0) { + System.out.println("Key " + key + " found at index " + (index-1)); + } + else{ + + System.out.println("Key could not be found, stopped at index " + (-index)); + } + } + + + public void printList(AscendinglyOrderedStringList orderedList) { + if (orderedList.size() == 0) + { + System.out.println("List is empty"); + } + else { + System.out.println(orderedList.toString()); + } + } + + public int menuSelection() { + System.out.print("Make your menu selection now: "); + return Integer.parseInt(in.nextLine()); + } + + public void listOptions(){ + System.out.println("Select from the following menu:"); + System.out.println(" 1. Insert item to list"); + System.out.println(" 2. Remove item from list"); + System.out.println(" 3. Get item from list"); + System.out.println(" 4. Search for a specified item in the list"); + System.out.println(" 5. Clear list"); + System.out.println(" 6. Print size and contents of list"); + System.out.println(" 7. Exit program"); + } + + void exitProgram(){ + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } + +} diff --git a/Lab08/src/lab8/ListArrayBased.java b/Lab08/src/lab8/ListArrayBased.java @@ -0,0 +1,106 @@ +package lab8; + +// ******************************************************** +// Array-based implementation of the ADT list. +// ********************************************************* +public class ListArrayBased<T> implements ListInterface<T> +{ + + private static final int MAX_LIST = 3; + protected T []items; // an array of list items + protected int numItems; // number of items in list + + public ListArrayBased() + { + items = (T[]) new Object[MAX_LIST]; + numItems = 0; + } // end default constructor + + public boolean isEmpty() + { + return (numItems == 0); + } // end isEmpty + + public int size() + { + return numItems; + } // end size + + public void removeAll() + { + // Creates a new array; marks old array for + // garbage collection. + items = (T[]) new Object[MAX_LIST]; + numItems = 0; + } // end removeAll + + public void add(int index, T item) + throws ListIndexOutOfBoundsException + { + if (numItems == items.length ) //fixes implementation errors and programming errors. + { + throw new ListException("ListException on add"); + } // end if + if (index >= 0 && index <= numItems) + { + // make room for new element by shifting all items at + // positions >= index toward the end of the + // list (no shift if index == numItems+1) + for (int pos = numItems-1; pos >= index; pos--) //textbook code modified to eliminate logic error causing ArrayIndexOutOfBoundsException + { + items[pos+1] = items[pos]; + } // end for + // insert new item + items[index] = item; + numItems++; + } + else + { + // index out of range + throw new ListIndexOutOfBoundsException( + "ListIndexOutOfBoundsException on add"); + } // end if + } //end add + + public T get(int index) + throws ListIndexOutOfBoundsException + { + if (index >= 0 && index < numItems) + { + return items[index]; + } + else + { + // index out of range + throw new ListIndexOutOfBoundsException( + "ListIndexOutOfBoundsException on get"); + } // end if + } // end get + + public void remove(int index) + throws ListIndexOutOfBoundsException + { + if (index >= 0 && index < numItems) + { + // delete item by shifting all items at + // positions > index toward the beginning of the list + // (no shift if index == size) + for (int pos = index+1; pos < numItems; pos++) //textbook code modified to eliminate logic error causing ArrayIndexOutOfBoundsException + + { + items[pos-1] = items[pos]; + } // end for + items[numItems - 1] = null; // Fixes memory leak. + numItems--; + } + else + { + // index out of range + throw new ListIndexOutOfBoundsException( + "ListIndexOutOfBoundsException on remove"); + } // end if + } //end remove + + + +} diff --git a/Lab08/src/lab8/ListArrayBasedPlus.java b/Lab08/src/lab8/ListArrayBasedPlus.java @@ -0,0 +1,51 @@ +package lab8; + +public class ListArrayBasedPlus<T> extends ListArrayBased<T> { + + public ListArrayBasedPlus() { + super(); + } + + public void add(int index, T item) + throws ListIndexOutOfBoundsException + { + if (numItems == items.length ) //fixes implementation errors and programming errors. + { + resize(); + } // end if + if (index >= 0 && index <= numItems) + { + super.add(index, item); + } + } //end add + + public void reverse() { + for(int i = 0; i < numItems/2; i++) { + T tempObject = items[i]; + items[i] = items[numItems - i - 1]; + items[numItems - i - 1] = tempObject; + } + System.out.println("List reversed"); + } + + public void resize() { + T []tmp; + tmp = (T[]) new Object[numItems*2 + 1]; + for (int i = 0; i < numItems; i++) { + tmp[i] = items[i]; + } + items = tmp; + } + + @Override + public String toString() { + String result = "List of size " + size() + " has the following items : "; + + for (int i = 0; i < size(); i++) { + if (items[i] != null) + result += items[i] + " "; + } + + return result; + } +} diff --git a/Lab08/src/lab8/ListException.java b/Lab08/src/lab8/ListException.java @@ -0,0 +1,9 @@ +package lab8; + +public class ListException extends RuntimeException +{ + public ListException(String s) + { + super(s); + } // end constructor +} // end ListException +\ No newline at end of file diff --git a/Lab08/src/lab8/ListIndexOutOfBoundsException.java b/Lab08/src/lab8/ListIndexOutOfBoundsException.java @@ -0,0 +1,11 @@ +package lab8; + +public class ListIndexOutOfBoundsException + extends IndexOutOfBoundsException +{ + public ListIndexOutOfBoundsException(String s) + { + super(s); + } // end constructor +} // end ListIndexOutOfBoundsException + diff --git a/Lab08/src/lab8/ListInterface.java b/Lab08/src/lab8/ListInterface.java @@ -0,0 +1,17 @@ +package lab8; + +// ******************************************************** +// Interface ListInterface for the ADT list. +// ********************************************************* +public interface ListInterface<T> +{ + boolean isEmpty(); + int size(); + void add(int index, T item) + throws ListIndexOutOfBoundsException; + T get(int index) + throws ListIndexOutOfBoundsException; + void remove(int index) + throws ListIndexOutOfBoundsException; + void removeAll(); +} // end ListInterface diff --git a/Lab09/src/lab9/Driver.java b/Lab09/src/lab9/Driver.java @@ -0,0 +1,177 @@ +package lab9; + +/* + * Purpose: Data Structure and Algorithms Lab 9 Problem 1 + * Status: Complete and thoroughly tested + * Last update: 01/31/18 + * Submitted: 02/01/18 + * Comment: test suite and sample run attached + * @author: John Kubach + * @version: 2018.01.31 + */ + +import java.util.Scanner; + +public class Driver { + Scanner in = new Scanner(System.in); + public static void main(String[] args) { + int[] items; + Driver ui = new Driver(); + + items = ui.getArray(); + + /* Uncomment to select sorting algorithm */ + + //ui.bubbleSort(items); + //ui.improvedBubbleSort(items); + //ui.selectionSort(items); + ui.improvedSelectionSort(items); + //ui.insertionSort(items); + } + + public void bubbleSort(int items[]) { + System.out.println("BUBBLE SORT"); + int temp; + int compare = 0; + int swap = 0; + for (int i = 0; i < items.length - 1; i++) { + for (int j = 0; j < items.length - 1 - i; j++) { + compare++; + if (items[j] > items[j+1]) { + temp = items[j]; + items[j] = items[j+1]; + items[j+1] = temp; + swap++; + } + } + } + printOperations(compare, swap); + printArray(items); + } + + public void improvedBubbleSort(int items[]) { + System.out.println("\n IMPROVED BUBBLE SORT \n"); + boolean sorted = true; + int temp; + int compare = 0; + int swap = 0; + for (int i = 0; i < items.length - 1 && sorted; i++) { + + sorted = false; + for (int j = 0; j < items.length - 1 - i; j++) { + compare++; + if (items[j] > items[j+1]) { + temp = items[j]; + items[j] = items[j+1]; + items[j+1] = temp; + swap++; + sorted = true; + } + } + } + printOperations(compare, swap); + printArray(items); + } + + public void selectionSort(int[] items){ + System.out.println("\n SELECTION SORT \n"); + int temp; + int min; + int swap = 0; + int compare = 0; + + for (int i = 0; i < items.length - 1; i++) { + min = i; + printArray(items); + for ( int j = (i+1); j < items.length; j++) { + compare++; + if (items[j] < items[min]) { + min = j; + } + printArray(items); + } + if (i != min){ + temp = items[i]; + items[i]=items[min]; + items[min] = temp; + swap++; + } + } + printOperations(compare, swap); + printArray(items); + } + + public void improvedSelectionSort(int[] items) { + System.out.println("\n IMPROVED SELECTION SORT \n"); + int temp; + int min; + int swap = 0; + int compare = 0; + boolean setMin = true; + for (int i = 0; i < items.length - 1 && setMin; i++) { + min = i; + setMin = false; + for ( int j = (i+1); j < items.length; j++) { + compare++; + if (items[j] < items[min]) { + min = j; + } + } + if (i != min) { + temp = items[i]; + items[i]=items[min]; + items[min] = temp; + swap++; + setMin = true; + } + } + printOperations(compare, swap); + printArray(items); + } + + + public void insertionSort(int items[]) { + System.out.println("\n INSERTION SORT \n"); + int swap = 0; + int compare = 0; + for (int i = 1; i < items.length; i++) { + int j; + int current = items[i]; + compare++; + + for (j = i - 1; j >= 0 && items[j] > current; j--) { + items[j+1] = items[j]; + swap++; + } + items[j+1] = current; + } + printOperations(compare, swap); + printArray(items); + } + + public int[] getArray() { + int size; + int element; + System.out.print("Enter number of integers: "); + size = Integer.parseInt(in.nextLine()); + int newArray[] = new int[size]; + for (int i = 0; i < newArray.length; i++) { + System.out.print("Enter integer " + (i+1) + ": "); + element = Integer.parseInt(in.nextLine()); + newArray[i] = element; + } + return newArray; + } + + public void printOperations(int compare, int swap) { + System.out.println("Number of comparisons: " + compare); + System.out.println("Number of swaps: " + swap); + } + + public void printArray(int items[]) { + for (int i = 0; i < items.length; i++) { + System.out.print(items[i] + " "); + } + System.out.println(); + } +} diff --git a/Lab10/src/lab10/Driver.java b/Lab10/src/lab10/Driver.java @@ -0,0 +1,173 @@ +package lab10; + +/* + * Purpose: Data Structure and Algorithms Lab 10 Problem 1 + * Status: Complete and thoroughly tested + * Last update: 01/31/18 + * Submitted: 02/01/18 + * Comment: test suite and sample run attached + * @author: John Kubach + * @version: 2018.01.31 + */ + +import java.util.Scanner; +import java.util.Random; + +public class Driver { + Scanner in = new Scanner(System.in); + public static void main(String[] args) { + int[] items; + int compare = 0; + Driver ui = new Driver(); + + items = ui.getArray(); + ui.printArray(items); + + /* Uncomment to select sorting algorithm */ + //ui.iterativeMergeSort(items); + compare += ui.QuickSort( 0, items.length - 1,compare, items); + ui.printArray(items); + System.out.println(compare); + + + } + + public void iterativeMergeSort(int items[]) { + System.out.println("ITERATIVE MERGE SORT"); + int mid; + int end; + int[] tempArray = new int[items.length]; + int compare = 0; + + for (int size = 1; size < items.length; size = (size*2)) { + for (int begin = 0; begin < items.length; begin+= (2*size)) { + mid = (begin + size); + end = (begin + 2 * size); + if (end > items.length) { + end = items.length; + } + compare += mergeSubArrays(begin, end, mid, items, tempArray ); + } + } + + printOperations(compare); + printArray(items); + } + + public int mergeSubArrays (int begin, int end, int mid, int items[], int tempArray[]) { + int tempBegin = begin; + int tempMid = mid; + int compare = 0; + if (mid >= items.length) { + return 0; + } + /* + System.out.println(begin); + System.out.println(mid); + System.out.println(end); + */ + for (int i = begin; i < end; i++) { + if (tempBegin == mid) { + tempArray[i] = items[tempMid++]; + } + else if (tempMid == end) { + tempArray[i] = items[tempBegin++]; + } + else if (items[tempMid] < items[tempBegin]) { + tempArray[i] = items[tempMid++]; + } + else { + tempArray[i] = items[tempBegin++]; + } + compare++; + } + for (int i = begin; i < end; i++) { + items[i] = tempArray[i]; + } + return compare; + } + + + + public int QuickSort(int leftBound, int rightBound, int compare, int items[]){ + int pivot; + if (leftBound < rightBound) { + compare++; + System.out.println("SORTING ARRAY" ); + printArray(items); + System.out.println(); + pivot = quickSortPartition(leftBound, rightBound, items); + QuickSort(leftBound, pivot - 1, compare, items); + QuickSort(pivot + 1, rightBound, compare, items); + } + return compare; + } + + public int quickSortPartition(int leftbound, int rightbound, int items[]) { + int temp; + int lessThan = leftbound; + int pivot; + System.out.println("PARTITIONING ARRAY "); + printArray(items); + System.out.println(); + getPivot(leftbound, rightbound, items); + pivot = items[leftbound]; + System.out.println("COMPARING ITEMS"); + for (int greaterThan = leftbound + 1; greaterThan <= rightbound; greaterThan++) { + if (items[greaterThan] < pivot) { + System.out.println(items[greaterThan] + " IS LESS THAN " + pivot); + ++lessThan; + System.out.println("SWAP " + items[greaterThan] + " WITH " + items[lessThan]); + temp = items[greaterThan]; + items[greaterThan] = items[lessThan]; + items[lessThan] = temp; + } + } + System.out.println("SWAP PIVOT " + items[leftbound] + " WITH LAST ITEM IN <P " + items[lessThan]); + temp = items[leftbound]; + items[leftbound] = items[lessThan]; + items[lessThan] = temp; + System.out.println(); + return lessThan; + } + public void getPivot(int leftBound, int rightBound, int items[]) { + int pivot; + int temp; + System.out.println("FINDING PIVOT OF ARRAY "); + printArray(items); + Random generatePivot = new Random(); + pivot = generatePivot.nextInt((rightBound-leftBound) + leftBound); + System.out.println("GET PIVOT IS " + items[pivot]); + if (leftBound <= pivot) { + temp = items[leftBound]; + items[leftBound] = items[pivot]; + items[pivot] = temp; + } + printArray(items); + System.out.println(); + } + + public int[] getArray() { + int size; + Random num = new Random(); + System.out.print("Enter number of integers: "); + size = Integer.parseInt(in.nextLine()); + System.out.println("GENERATING RANDOM ARRAY..."); + int newArray[] = new int[size]; + for (int i = 0; i < newArray.length; i++) { + newArray[i] = num.nextInt(100); + } + return newArray; + } + + public void printOperations(int compare) { + System.out.println("Number of key comparisons: " + compare); + } + + public void printArray(int items[]) { + for (int i = 0; i < items.length; i++) { + System.out.print(items[i] + " "); + } + System.out.println(); + } +} diff --git a/Lab11/src/lab11/BSTPInterface.java b/Lab11/src/lab11/BSTPInterface.java @@ -0,0 +1,28 @@ +package lab11; + +public interface BSTPInterface <T extends KeyedItem<KT>,KT extends Comparable<? super KT>> { + + public int getHeight(); +// returns the height of the tree (recursive implementation) + + public int getSize(); +// returns the number of nodes in the tree(recursive implementation) + + public String toStringInorder(); +// returns String representation of Tree with items in Inorder +//(recursive implementation) + + public String toStringPreorder(); +// returns String representation of Tree with items in Preorder +//(recursive implementation) + + public String toStringPostorder(); +// returns String representation of Tree with items in Postorder +// (recursive implementation) + + public MyBinarySearchTreePlus<T,KT> getCopyOfTree(); +// returns a new tree containing a copy of the original tree +// with the same structure. Note: the new tree should not have +// any shared nodes with the original.(recursive implementation) + +}// end BSTPInterface diff --git a/Lab11/src/lab11/BinarySearchTree.java b/Lab11/src/lab11/BinarySearchTree.java @@ -0,0 +1,168 @@ +package lab11; + +public class BinarySearchTree<T extends KeyedItem<KT>, + KT extends Comparable<? super KT>> + extends BinaryTreeBasis<T> { + // inherits isEmpty(), makeEmpty(), getRootItem(), and + // the use of the constructors from BinaryTreeBasis + + public BinarySearchTree() { + } // end default constructor + + public BinarySearchTree(T rootItem) { + super(rootItem); + } // end constructor + + public void setRootItem(T newItem) + throws UnsupportedOperationException { + throw new UnsupportedOperationException(); + } // end setRootItem + + public void insert(T newItem) { + root = insertItem(root, newItem); + } // end insert + + public T retrieve(KT searchKey) { + return retrieveItem(root, searchKey); + } // end retrieve + + public void delete(KT searchKey) throws TreeException { + root = deleteItem(root, searchKey); + } // end delete + + public void delete(T item) throws TreeException { + root = deleteItem(root, item.getKey()); + } // end delete + + protected TreeNode<T> insertItem(TreeNode<T> tNode, + T newItem) { + TreeNode<T> newSubtree; + if (tNode == null) { + // position of insertion found; insert after leaf + // create a new node + tNode = new TreeNode<T>(newItem, null, null); + return tNode; + } // end if + T nodeItem = tNode.getItem(); + + // search for the insertion position + + if (newItem.getKey().compareTo(nodeItem.getKey()) < 0) { + // search the left subtree + newSubtree = insertItem(tNode.getLeftChild(), newItem); + tNode.setLeftChild(newSubtree); + return tNode; + } + else { // search the right subtree + newSubtree = insertItem(tNode.getRightChild(), newItem); + tNode.setRightChild(newSubtree); + return tNode; + } // end if + } // end insertItem + + protected T retrieveItem(TreeNode<T> tNode, + KT searchKey) { + T treeItem; + if (tNode == null) { + treeItem = null; + } + else { + T nodeItem = tNode.getItem(); + if (searchKey.compareTo(nodeItem.getKey()) == 0) { + // item is in the root of some subtree + treeItem = tNode.getItem(); + } + else if (searchKey.compareTo(nodeItem.getKey()) < 0) { + // search the left subtree + treeItem = retrieveItem(tNode.getLeftChild(), searchKey); + } + else { // search the right subtree + treeItem = retrieveItem(tNode.getRightChild(), searchKey); + } // end if + } // end if + return treeItem; + } // end retrieveItem + + protected TreeNode<T> deleteItem(TreeNode<T> tNode, + KT searchKey) { + // Calls: deleteNode. + TreeNode<T> newSubtree; + if (tNode == null) { + throw new TreeException("TreeException: Item not found"); + } + else { + T nodeItem = tNode.getItem(); + if (searchKey.compareTo(nodeItem.getKey()) == 0) { + // item is in the root of some subtree + tNode = deleteNode(tNode); // delete the item + } + // else search for the item + else if (searchKey.compareTo(nodeItem.getKey()) < 0) { + // search the left subtree + newSubtree = deleteItem(tNode.getLeftChild(), searchKey); + tNode.setLeftChild(newSubtree); + } + else { // search the right subtree + newSubtree = deleteItem(tNode.getRightChild(), searchKey); + tNode.setRightChild(newSubtree); + } // end if + } // end if + return tNode; + } // end deleteItem + + protected TreeNode<T> deleteNode(TreeNode<T> tNode) { + // Algorithm note: There are four cases to consider: + // 1. The tNode is a leaf. + // 2. The tNode has no left child. + // 3. The tNode has no right child. + // 4. The tNode has two children. + // Calls: findLeftmost and deleteLeftmost + T replacementItem; + + // test for a leaf + if ( (tNode.getLeftChild() == null) && + (tNode.getRightChild() == null) ) { + return null; + } // end if leaf + + // test for no left child + else if (tNode.getLeftChild() == null) { + return tNode.getRightChild(); + } // end if no left child + + // test for no right child + else if (tNode.getRightChild() == null) { + return tNode.getLeftChild(); + } // end if no right child + + // there are two children: + // retrieve and delete the inorder successor + else { + replacementItem = findLeftmost(tNode.getRightChild()); + tNode.setItem(replacementItem); + tNode.setRightChild(deleteLeftmost(tNode.getRightChild())); + return tNode; + } // end if + } // end deleteNode + + protected T findLeftmost(TreeNode<T> tNode) { + if (tNode.getLeftChild() == null) { + return tNode.getItem(); + } + else { + return findLeftmost(tNode.getLeftChild()); + } // end if + } // end findLeftmost + + protected TreeNode<T> deleteLeftmost(TreeNode<T> tNode) { + if (tNode.getLeftChild() == null) { + return tNode.getRightChild(); + } + else { + tNode.setLeftChild(deleteLeftmost(tNode.getLeftChild())); + return tNode; + } // end if + } // end deleteLeftmost + +} // end BinarySearchTree + diff --git a/Lab11/src/lab11/BinaryTreeBasis.java b/Lab11/src/lab11/BinaryTreeBasis.java @@ -0,0 +1,39 @@ +package lab11; + +public abstract class BinaryTreeBasis<T> { + protected TreeNode<T> root; + + public BinaryTreeBasis() { + root = null; + } // end default constructor + + public BinaryTreeBasis(T rootItem) { + root = new TreeNode<T>(rootItem, null, null); + } // end constructor + + public boolean isEmpty() { + // Returns true if the tree is empty, else returns false. + return root == null; + } // end isEmpty + + public void makeEmpty() { + // Removes all nodes from the tree. + root = null; + } // end makeEmpty + + public T getRootItem() throws TreeException { + // Returns the item in the tree's root. + if (root == null) { + throw new TreeException("TreeException: Empty tree"); + } + else { + return root.getItem(); + } // end if + } // end getRootItem + + public abstract void setRootItem(T newItem); + // Throws UnsupportedOperationException if operation + // is not supported. + +} // end BinaryTreeBasis + diff --git a/Lab11/src/lab11/Driver.java b/Lab11/src/lab11/Driver.java @@ -0,0 +1,161 @@ +package lab11; +import java.util.Scanner; + +public class Driver { + Scanner in = new Scanner(System.in); + + public static void main(String[] args) { + int userSelection; + Driver ui = new Driver(); + + MyBinarySearchTreePlus<Item, String> BST = new MyBinarySearchTreePlus<>(); + MyBinarySearchTreePlus<Item, String> copyBST; + + ui.listOptions(); + + do { + userSelection = ui.menuSelection(); + System.out.println(userSelection); + switch (userSelection) { + case 1: + ui.insertKey(BST); + break; + case 2: + ui.removeKey(BST); + break; + case 3: + ui.search(BST); + break; + case 4: + ui.getHeight(BST); + break; + case 5: + ui.getSize(BST); + break; + case 6: + ui.displayInorder(BST); + break; + case 7: + ui.displayPreorder(BST); + break; + case 8: + ui.displayPostorder(BST); + break; + case 9: + copyBST = ui.copyTree(BST); + ui.testCopy(BST, copyBST); + break; + case 10: + ui.exitProgram(); + break; + } + } while(userSelection != 10); + } + + + public void insertKey(MyBinarySearchTreePlus<Item, String> BST) { + String key; + System.out.print("Enter key to insert: "); + key = in.next().trim(); + System.out.print(key); + BST.insert(new Item(key)); + System.out.println("Key " + key + " inserted"); + } + + public void removeKey(MyBinarySearchTreePlus<Item, String > BST) { + String key; + System.out.print("Enter key to remove: "); + key = in.next().trim(); + System.out.print(key); + BST.delete(key); + System.out.println("Key " + key + " deleted"); + } + + public void search(MyBinarySearchTreePlus<Item, String> BST) { + String key; + Item result; + System.out.print("Enter key to search: "); + key = in.next().trim(); + System.out.print(key); + result = BST.retrieve(key); + if (result == null) { + System.out.println("Key not found"); + } + else { + System.out.println("Key " + result.getKey() + " found"); + } + } + + public void getHeight(MyBinarySearchTreePlus<Item, String> BST) { + System.out.println("The height of the tree is " + BST.getHeight()); + } + + public void getSize(MyBinarySearchTreePlus<Item, String> BST) { + System.out.println("The size of the tree is " + BST.getSize()); + } + + public void displayInorder(MyBinarySearchTreePlus<Item, String> BST) { + System.out.println(BST.toStringInorder()); + } + + public void displayPreorder(MyBinarySearchTreePlus<Item, String> BST) { + System.out.println(BST.toStringPreorder()); + } + + public void displayPostorder(MyBinarySearchTreePlus<Item, String> BST) { + System.out.println(BST.toStringPostorder()); + } + + public MyBinarySearchTreePlus<Item, String> copyTree(MyBinarySearchTreePlus<Item, String> BST) { + return BST.getCopyOfTree(); + } + + public void testCopy(MyBinarySearchTreePlus<Item, String> BST, MyBinarySearchTreePlus<Item, String> copyBST) { + System.out.println("ORIGINAL TREE INORDER"); + displayInorder(BST); + + System.out.println("COPY TREE INORDER"); + displayInorder(copyBST); + + System.out.println("ADDING A KEY TO ORIGINAL TREE"); + insertKey(BST); + + System.out.println("REMOVING ITEM FROM COPY TREE"); + removeKey(copyBST); + + System.out.println("COMPARISON OF ORIGINAL AND COPY"); + displayInorder(BST); + displayInorder(copyBST); + } + + + + + + + + + public int menuSelection() { + System.out.print("Make your menu selection now: "); + return Integer.parseInt(in.next().trim()); + } + + public void listOptions(){ + System.out.println("Select from the following menu:"); + System.out.println(" 1. Insert key into BST"); + System.out.println(" 2. Remove key from BST"); + System.out.println(" 3. Search for key in BST"); + System.out.println(" 4. Display height of BST"); + System.out.println(" 5. Display size of BST"); + System.out.println(" 6. Display content of BST inorder"); + System.out.println(" 7. Display content of BST in preorder"); + System.out.println(" 8. Display content of BST in postorder"); + System.out.println(" 9. Build copy of tree and test it"); + System.out.println(" 10. Exit program"); + } + + void exitProgram(){ + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } +} diff --git a/Lab11/src/lab11/Item.java b/Lab11/src/lab11/Item.java @@ -0,0 +1,10 @@ +package lab11; + +public class Item extends KeyedItem<String> { + private String item; + + public Item(String item) { + super(item); + this.item = item; + } +} diff --git a/Lab11/src/lab11/KeyedItem.java b/Lab11/src/lab11/KeyedItem.java @@ -0,0 +1,14 @@ +package lab11; + +public abstract class KeyedItem<KT extends + Comparable<? super KT>> { + private KT searchKey; + + public KeyedItem(KT key) { + searchKey = key; + } // end constructor + + public KT getKey() { + return searchKey; + } // end getKey +} // end KeyedItem diff --git a/Lab11/src/lab11/MyBinarySearchTree.java b/Lab11/src/lab11/MyBinarySearchTree.java @@ -0,0 +1,160 @@ +package lab11; + +public class MyBinarySearchTree<T extends KeyedItem<KT>, + KT extends Comparable<? super KT>> + extends BinaryTreeBasis<T> { + // inherits isEmpty(), makeEmpty(), getRootItem(), and + // the use of the constructors from BinaryTreeBasis + + public MyBinarySearchTree() { + } // end default constructor + + public MyBinarySearchTree(T rootItem) { + super(rootItem); + } // end constructor + + public void setRootItem(T newItem) + throws UnsupportedOperationException { + throw new UnsupportedOperationException(); + } // end setRootItem + + public void insert(T newItem) { + root = insertItem(root, newItem); + } // end insert + + public T retrieve(KT searchKey) { + TreeNode<T> tempTree = root; + int compare; + while (tempTree != null) { + compare = searchKey.compareTo(tempTree.getItem().getKey()); + if (compare < 0) { + tempTree = tempTree.getLeftChild(); + } + else if (compare > 0) { + tempTree = tempTree.getRightChild(); + } + else { + return tempTree.getItem(); + } + } + return null; + } // end retrieve + + public void delete(KT searchKey) throws TreeException { + root = deleteItem(root, searchKey); + } // end delete + + public void delete(T item) throws TreeException { + root = deleteItem(root, item.getKey()); + } // end delete + + protected TreeNode<T> insertItem(TreeNode<T> tNode, + T newItem) { + TreeNode<T> newSubtree; + if (tNode == null) { + // position of insertion found; insert after leaf + // create a new node + tNode = new TreeNode<T>(newItem, null, null); + return tNode; + } // end if + T nodeItem = tNode.getItem(); + + // search for the insertion position + + if (newItem.getKey().compareTo(nodeItem.getKey()) < 0) { + // search the left subtree + newSubtree = insertItem(tNode.getLeftChild(), newItem); + tNode.setLeftChild(newSubtree); + return tNode; + } + else { // search the right subtree + newSubtree = insertItem(tNode.getRightChild(), newItem); + tNode.setRightChild(newSubtree); + return tNode; + } // end if + } // end insertItem + + + protected TreeNode<T> deleteItem(TreeNode<T> tNode, + KT searchKey) { + // Calls: deleteNode. + TreeNode<T> newSubtree; + if (tNode == null) { + throw new TreeException("TreeException: Item not found"); + } + else { + T nodeItem = tNode.getItem(); + if (searchKey.compareTo(nodeItem.getKey()) == 0) { + // item is in the root of some subtree + tNode = deleteNode(tNode); // delete the item + } + // else search for the item + else if (searchKey.compareTo(nodeItem.getKey()) < 0) { + // search the left subtree + newSubtree = deleteItem(tNode.getLeftChild(), searchKey); + tNode.setLeftChild(newSubtree); + } + else { // search the right subtree + newSubtree = deleteItem(tNode.getRightChild(), searchKey); + tNode.setRightChild(newSubtree); + } // end if + } // end if + return tNode; + } // end deleteItem + + protected TreeNode<T> deleteNode(TreeNode<T> tNode) { + // Algorithm note: There are four cases to consider: + // 1. The tNode is a leaf. + // 2. The tNode has no left child. + // 3. The tNode has no right child. + // 4. The tNode has two children. + // Calls: findLeftmost and deleteLeftmost + T replacementItem; + + // test for a leaf + if ( (tNode.getLeftChild() == null) && + (tNode.getRightChild() == null) ) { + return null; + } // end if leaf + + // test for no left child + else if (tNode.getLeftChild() == null) { + return tNode.getRightChild(); + } // end if no left child + + // test for no right child + else if (tNode.getRightChild() == null) { + return tNode.getLeftChild(); + } // end if no right child + + // there are two children: + // retrieve and delete the inorder successor + else { + replacementItem = findLeftmost(tNode.getRightChild()); + tNode.setItem(replacementItem); + tNode.setRightChild(deleteLeftmost(tNode.getRightChild())); + return tNode; + } // end if + } // end deleteNode + + protected T findLeftmost(TreeNode<T> tNode) { + TreeNode<T> tempNode = tNode; + if (tempNode != null) { + while (tempNode.getLeftChild() != null) { + tempNode = tNode.getLeftChild(); + } + } + return tempNode.getItem(); + } // end findLeftmost + + protected TreeNode<T> deleteLeftmost(TreeNode<T> tNode) { + if (tNode.getLeftChild() == null) { + return tNode.getRightChild(); + } + else { + tNode.setLeftChild(deleteLeftmost(tNode.getLeftChild())); + return tNode; + } // end if + } // end deleteLeftmost + +} // end MyBinarySearchTree diff --git a/Lab11/src/lab11/MyBinarySearchTreePlus.java b/Lab11/src/lab11/MyBinarySearchTreePlus.java @@ -0,0 +1,115 @@ +package lab11; + +public class MyBinarySearchTreePlus <T extends KeyedItem<KT>,KT extends Comparable<? super KT>> extends MyBinarySearchTree<T,KT> implements BSTPInterface<T,KT> { + + public int getHeight() { + int height = 0; + if (root != null) { + height += getHeight(root); + } + return height; + } + private int getHeight(TreeNode<T> treeNode){ + if (treeNode == null) { + return 0; + } + int ls = getHeight(treeNode.getLeftChild()); + int rs = getHeight(treeNode.getRightChild()); + if (ls > rs) { + return 1 + ls; + } + else { + return 1 + rs; + } + } + + public int getSize() { + int size = 0; + if (root != null) { + size += getSize(root); + } + return size; + } + + private int getSize(TreeNode<T> treeNode) { + if (treeNode == null) { + return 0; + } + int ls = getSize(treeNode.getLeftChild()); + int rs = getSize(treeNode.getRightChild()); + return ls + rs + 1; + + } + + public String toStringInorder() { + String result =""; + if (root != null) { + result += toStringInorder(root); + } + return result; + } + private String toStringInorder(TreeNode<T> treeNode) { + if (treeNode == null) { + return ""; + } + String result = ""; + result += toStringInorder(treeNode.getLeftChild()); + result += treeNode.getItem().getKey() + " "; + result += toStringInorder(treeNode.getRightChild()); + return result; + } + + public String toStringPreorder() { + String result = ""; + if (root != null) { + result += toStringPreorder(root); + } + return result; + } + private String toStringPreorder(TreeNode<T> treeNode) { + if (treeNode == null) { + return ""; + } + String result = ""; + result += treeNode.getItem().getKey() + " "; + result += toStringInorder(treeNode.getLeftChild()); + result += toStringInorder(treeNode.getRightChild()); + return result; + } + + public String toStringPostorder() { + String result = ""; + if (root != null) { + result += toStringPostorder(root); + } + return result; + } + private String toStringPostorder(TreeNode<T> treeNode) { + if (treeNode == null) { + return ""; + } + String result = ""; + result += toStringInorder(treeNode.getLeftChild()); + result += toStringInorder(treeNode.getRightChild()); + result += treeNode.getItem().getKey() + " "; + return result; + } + + public MyBinarySearchTreePlus<T , KT> getCopyOfTree() + { + MyBinarySearchTreePlus<T , KT> tree = new MyBinarySearchTreePlus<>(); + return getCopyOfTree(root, tree); + + } + private MyBinarySearchTreePlus<T,KT> getCopyOfTree(TreeNode<T> treeNode, MyBinarySearchTreePlus<T, KT> copyTree) { + if (treeNode != null) { + copyTree.insert(treeNode.getItem()); + getCopyOfTree(treeNode.getLeftChild(), copyTree); + getCopyOfTree(treeNode.getRightChild(), copyTree); + } + return copyTree; + } +// returns a new tree containing a copy of the original tree +// with the same structure. Note: the new tree should not have +// any shared nodes with the original.(recursive implementation) +} diff --git a/Lab11/src/lab11/TreeException.java b/Lab11/src/lab11/TreeException.java @@ -0,0 +1,7 @@ +package lab11; + +public class TreeException extends RuntimeException { + public TreeException(String s) { + super(s); + } // end constructor +} // end TreeException diff --git a/Lab11/src/lab11/TreeNode.java b/Lab11/src/lab11/TreeNode.java @@ -0,0 +1,46 @@ +package lab11; + +class TreeNode<T> { + private T item; + private TreeNode<T> leftChild; + private TreeNode<T> rightChild; + + public TreeNode(T newItem) { + // Initializes tree node with item and no children. + item = newItem; + leftChild = null; + rightChild = null; + } // end constructor + + public TreeNode(T newItem, + TreeNode<T> left, TreeNode<T> right) { + // Initializes tree node with item and + // the left and right children references. + item = newItem; + leftChild = left; + rightChild = right; + } // end constructor + + public T getItem() + {return item;} + + public void setItem(T item) + {this.item = item;} + + public TreeNode<T> getLeftChild() + {return leftChild;} + + public void setLeftChild(TreeNode<T> leftChild) + {this.leftChild = leftChild;} + + + public TreeNode<T> getRightChild() + {return rightChild;} + + public void setRightChild(TreeNode<T> rightChild) + {this.rightChild = rightChild;} + + +} // end TreeNode + + diff --git a/Lab12/src/lab12/ChainNode.java b/Lab12/src/lab12/ChainNode.java @@ -0,0 +1,33 @@ +package lab12; +class ChainNode<K, V> { + private K key; + private V value; + private ChainNode<K, V> next; + + public ChainNode(K newKey, V newValue, + ChainNode<K, V> nextNode) { + key = newKey; + value = newValue; + next = nextNode; + } // end constructor + + public V getValue() { + return value; + } // end getValue + + public K getKey() { + return key; + } // end getKey + + public ChainNode<K, V> getNext() + { + return next; + } // end getNext + + public void setNext(ChainNode<K, V> next) + { + this.next=next; + } // end setNext + + +} // end ChainNode diff --git a/Lab12/src/lab12/Driver.java b/Lab12/src/lab12/Driver.java @@ -0,0 +1,107 @@ +package lab12; +import java.util.Scanner; + +public class Driver { + Scanner in = new Scanner(System.in); + public static void main(String[] args) { + int userSelection; + Driver ui = new Driver(); + HashTable<String, String> table = new HashTable<>(); + + ui.listOptions(); + + do { + userSelection = ui.menuSelection(); + System.out.println(userSelection); + + switch (userSelection) { + case 1: + ui.insert(table); + break; + case 2: + ui.delete(table); + break; + case 3: + ui.retrieve(table); + break; + case 4: + ui.displayHashIndex(table); + break; + case 5: + ui.exitProgram(); + break; + } + } while (userSelection !=5); + } + + public void insert(HashTable<String, String> table) { + String key, value; + System.out.print("Enter Key "); + key = in.next().trim(); + System.out.println(key); + System.out.print("Enter Value "); + value = in.next().trim(); + System.out.println(value); + table.tableInsert(key, value); + } + + public void retrieve(HashTable<String, String> table) { + String key; + String result; + System.out.print("Enter key "); + key = in.next().trim(); + System.out.println(key); + + result = table.tableRetrieve(key); + if (result != null) { + System.out.println("Key " + key + " has value of " + result); + } + else { + System.out.println("Key not found!"); + } + + } + + public void delete(HashTable<String, String> table) { + String key; + System.out.print("Enter Key"); + key = in.next().trim(); + System.out.println(key); + + if (table.tableDelete(key)) { + System.out.println("Key " + key + " has been deleted"); + } + else { + System.out.println("Key not found in table"); + } + } + + public void displayHashIndex(HashTable<String, String> table) { + String key; + + System.out.print("Enter key "); + key = in.next().trim(); + System.out.println(key); + + System.out.println("Hash index of key " + key + " is " + table.hashIndex(key)); + } + + public int menuSelection() { + System.out.print("Make your menu selection now: "); + return Integer.parseInt(in.next().trim()); + } + + public void listOptions(){ + System.out.println("Select from the following menu:"); + System.out.println(" 1. Insert a symbol key with an associated value in the table"); + System.out.println(" 2. Delete symbol from the table"); + System.out.println(" 3. Retrieve and display the value associated with a symbol key in the table"); + System.out.println(" 4. Display the hash index of a symbol key"); + System.out.println(" 5. Exit Program"); + } + + public void exitProgram(){ + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } +} diff --git a/Lab12/src/lab12/HashException.java b/Lab12/src/lab12/HashException.java @@ -0,0 +1,7 @@ +package lab12; +public class HashException extends RuntimeException { + public HashException(String s) { + super(s); + } // end constructor +} // end HashException + diff --git a/Lab12/src/lab12/HashTable.java b/Lab12/src/lab12/HashTable.java @@ -0,0 +1,121 @@ +package lab12; +// ******************************************************** +// Hash table implementation. +// Assumption: A table contains unique items(at most one +// item with a given search key at any time) +// ********************************************************* + +public class HashTable<K, V> implements HashTableInterface<K,V> { + private ChainNode[] table; // hash table + private int size = 0; // size of table, i.e. number of entries ((key,value) associations) + + public HashTable() { + table = new ChainNode[3]; + } // end default constructor + + // table operations + public boolean tableIsEmpty() { + return size==0; + } // end tableIsEmpty + + public int tableLength() { + return size; + } // end tableLength + + +//implement the following 4 methods + + public boolean tableInsert(K key, V value) //inserts association (key,value) only if key is not already in HashTable and returns true; returns false if the key already has an associated value in HashTable and does not insert + { + int index; + boolean duplicate = false; + boolean nullValue = false; + index = hashIndex(key); + + ChainNode<K, V> curr = table[index]; + ChainNode<K, V> newNode = new ChainNode<>(key, value, null); + if (curr != null) { + while (!nullValue && !duplicate) { + if (curr.getKey().equals(key)) { + duplicate = true; + } + else if (curr.getNext() == null) { + nullValue = true; + } + else { + curr = curr.getNext(); + } + } + } + else { + table[index] = newNode; + size++; + return true; + } + if (!duplicate) { + System.out.println("COLLISION"); + curr.setNext(newNode); + System.out.println("COLLISION RESOLVED"); + size++; + return true; + } + return false; + } + + public boolean tableDelete(K searchKey) //deletes the key and its association from the HashTable if it is in the table and returns true; returns false if key is not in the HashTable + { + int index; + index = hashIndex(searchKey); + ChainNode<K, V> node = table[index]; + + if (node.getKey().equals(searchKey)) { + table[index] = node.getNext(); + size--; + return true; + } + while (node.getNext() != null) { + if (node.getNext().getKey().equals(searchKey)) { + node.setNext(node.getNext().getNext()); + size --; + return true; + } + node = node.getNext(); + } + return false; + } + + public V tableRetrieve(K searchKey) //returns the value associated with searchkey in HashTable or null if there is no association + { + int index; + index = hashIndex(searchKey); + ChainNode<K, V> node = table[index]; + + while (node != null) { + if (searchKey.toString().equals(node.getKey())) { + return node.getValue(); + } + else { + node = node.getNext(); + } + } + return null; + } + + public int hashIndex(K key) { + int horner = 0; + int mapKey; + int resultKey; + int length = key.toString().length(); + int [] characters = new int[length]; + + for(int i = 0; i < length; i++) { + mapKey = key.toString().charAt(i) - ('A') + 1; + characters[i] = mapKey; + horner += characters[i] << ((length - 1 - i) * 5); + } + resultKey = horner % table.length; + return resultKey; + } +} // end HashTable + + diff --git a/Lab12/src/lab12/HashTableInterface.java b/Lab12/src/lab12/HashTableInterface.java @@ -0,0 +1,16 @@ +package lab12; +public interface HashTableInterface<K,V> { + + public boolean tableIsEmpty(); + public int tableLength(); + + public boolean tableInsert(K key, V value); //inserts association (key,value) only if key is not already in HashTable and returns true; returns false if the key already has an associated value in HashMap and does not insert + + public boolean tableDelete(K searchKey); //deletes the key and its association from the HashTable if it is in the table and returns true; returns false if key is not in the HashTable + + public V tableRetrieve(K searchKey); //returns the value associated with searchkey in HashMap or null if there is no association + + public int hashIndex(K key); + +} // end HashTableInterface +