dsa

Data Structures & Algorithms - Spring 2018
Log | Files | Refs | README

commit f8c9737aa55f435f28fe4f4b423d9a0e89dc76b7
parent db11dd444aca0a8b013c81a13ae84effd7e49861
Author: John Kubach <johnkubach@gmail.com>
Date:   Mon, 15 Oct 2018 18:23:09 -0400

lab2

Diffstat:
ALab02/src/lab2/Driver.java | 138+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ALab02/src/lab2/ListArrayBased.java | 106+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ALab02/src/lab2/ListArrayBasedPlus.java | 51+++++++++++++++++++++++++++++++++++++++++++++++++++
ALab02/src/lab2/ListArrayListBased.java | 65+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ALab02/src/lab2/ListArrayListBasedPlus.java | 22++++++++++++++++++++++
ALab02/src/lab2/ListException.java | 10++++++++++
ALab02/src/lab2/ListIndexOutOfBoundsException.java | 11+++++++++++
ALab02/src/lab2/ListInterface.java | 17+++++++++++++++++
8 files changed, 420 insertions(+), 0 deletions(-)

diff --git a/Lab02/src/lab2/Driver.java b/Lab02/src/lab2/Driver.java @@ -0,0 +1,138 @@ +package lab2; + +/* + * Purpose: Data Structure and Algorithms Lab 2 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 'Johnny' 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 userSelection; + Driver ui = new Driver(); + + /* Comment out one of the two following lines to toggle between + * Array or ArrayList Implementation + */ + ListArrayBasedPlus listArrayPlus = new ListArrayBasedPlus(); + // ListArrayListBasedPlus listArrayPlus = new ListArrayListBasedPlus(); + + ui.listOptions(); + + do { + userSelection = ui.menuSelection(); + System.out.println(userSelection); + switch (userSelection) { + case 1: + ui.addItem(listArrayPlus); + break; + case 2: + ui.removeItem(listArrayPlus); + break; + case 3: + ui.getItem(listArrayPlus); + break; + case 4: + listArrayPlus.removeAll(); + break; + case 5: + ui.printList(listArrayPlus); + break; + case 6: + listArrayPlus.reverse(); + break; + case 7: + ui.exitProgram(); + } + } while (userSelection != 7); + } + + public void addItem(ListArrayBasedPlus listArrayPlus) { + int index; + Object item; + System.out.println("Your are now entering an item"); + System.out.print(" Enter item: "); + item = in.nextLine(); + System.out.println(item); + System.out.print(" Enter position to insert item in: "); + index = Integer.parseInt(in.nextLine().trim()); + System.out.println(index); + if (index > listArrayPlus.size()) { + System.out.println("Position is out of bounds!"); + } + else { + listArrayPlus.add(index, item); + System.out.println("Item " + item + " inserted in position " + index + " in the list."); + } + } + + 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. Clear list"); + System.out.println(" 5. Print size and contents of list"); + System.out.println(" 6. Reverse list"); + System.out.println(" 7. Exit program"); + } + + void exitProgram(){ + System.out.println("Exiting program...Good Bye"); + System.exit(0); + } + +} diff --git a/Lab02/src/lab2/ListArrayBased.java b/Lab02/src/lab2/ListArrayBased.java @@ -0,0 +1,106 @@ +package lab2; + +// ******************************************************** +// Array-based implementation of the ADT list. +// ********************************************************* +public class ListArrayBased implements ListInterface +{ + + private static final int MAX_LIST = 3; + protected Object []items; // an array of list items + protected int numItems; // number of items in list + + public ListArrayBased() + { + items = 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 = new Object[MAX_LIST]; + numItems = 0; + } // end removeAll + + public void add(int index, Object 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 Object 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/Lab02/src/lab2/ListArrayBasedPlus.java b/Lab02/src/lab2/ListArrayBasedPlus.java @@ -0,0 +1,51 @@ +package lab2; + +public class ListArrayBasedPlus extends ListArrayBased { + + public ListArrayBasedPlus() { + super(); + } + + public void add(int index, Object 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++) { + Object tempObject = items[i]; + items[i] = items[numItems - i - 1]; + items[numItems - i - 1] = tempObject; + } + System.out.println("List reversed"); + } + + public void resize() { + Object []tmp; + tmp = 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/Lab02/src/lab2/ListArrayListBased.java b/Lab02/src/lab2/ListArrayListBased.java @@ -0,0 +1,65 @@ +package lab2; + +import java.util.ArrayList; + +public class ListArrayListBased implements ListInterface{ + + protected ArrayList<Object> items; // an array list of objects + + public ListArrayListBased() + { + items = new ArrayList<Object>(); + } // end default constructor + + public boolean isEmpty() + { + return (items.isEmpty()); + } // end isEmpty + + public int size() + { + return items.size(); + } // end size + + public void removeAll() + { + items.clear(); + } // end removeAll + + public void add(int index, Object item) + throws ListIndexOutOfBoundsException + { + items.add(index, item); + } //end add + + public Object get(int index) + throws ListIndexOutOfBoundsException + { + if (index >= 0 && index < size()) + { + return items.get(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 < size()) + { + items.remove(index); + } + else + { + // index out of range + throw new ListIndexOutOfBoundsException( + "ListIndexOutOfBoundsException on remove"); + } // end if + } //end remove +} + diff --git a/Lab02/src/lab2/ListArrayListBasedPlus.java b/Lab02/src/lab2/ListArrayListBasedPlus.java @@ -0,0 +1,22 @@ +package lab2; + +import java.util.Collections; + +public class ListArrayListBasedPlus extends ListArrayListBased { + + public void reverse() { + Collections.reverse(items); + } + + @Override + public String toString() { + String result = "List of size " + size() + " has the following items : "; + + for (int i = 0; i < size(); i++) { + if (get(i)!= null) + result += get(i) + " "; + } + + return result; + } +} diff --git a/Lab02/src/lab2/ListException.java b/Lab02/src/lab2/ListException.java @@ -0,0 +1,9 @@ +package lab2; + +public class ListException extends RuntimeException +{ + public ListException(String s) + { + super(s); + } // end constructor +} // end ListException +\ No newline at end of file diff --git a/Lab02/src/lab2/ListIndexOutOfBoundsException.java b/Lab02/src/lab2/ListIndexOutOfBoundsException.java @@ -0,0 +1,11 @@ +package lab2; + +public class ListIndexOutOfBoundsException + extends IndexOutOfBoundsException +{ + public ListIndexOutOfBoundsException(String s) + { + super(s); + } // end constructor +} // end ListIndexOutOfBoundsException + diff --git a/Lab02/src/lab2/ListInterface.java b/Lab02/src/lab2/ListInterface.java @@ -0,0 +1,17 @@ +package lab2; + +// ******************************************************** +// 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