Description
1.1. Homework 6.1 (10 Points) Objective: Modifying an existing algorithm and learning how to use generics Grading: Correctness: You can lose up to 40% if your solution is not correct Quality: You can lose up to 80% if your solution is poorly designed Testing: You can lose up to 50% if your solution is not well tested Explanation: You can lose up to 100% if your solution if you can not explain your solution during the grading session Homework Description: You hav e to implement a storage system that is behaves likeaset. Explanation: A set is collection of objects in which order has no significance. Members of a set are called elements. The following operations are Union ∪ and intersection ∩. defined on sets. It is also possible to ask if x is a member of a set A. x ∈ A is true, if x is a member of A otherwise false. You hav e to implement the following methods: boolean add(E e) /* add e to the set */ boolean addAll( /* add all elements of the set */ /* you have to come of with the correct signature */ /* for all elements of type E or subclass shape */ /* if possible * /* true if one element could have been added */ boolean removeAll( /* remove all elements of the set */ /* you have to come of with the correct signature */ /* for all elements of type E or subclass shape */ /* if possible * /* true if all elements could have been removed */ Object[] toArray() /* return all elements of the set in an array */ boolean contains(Object o) /* true if o is in the set, false else */ boolean remove(Object o) /* remove o, true if o could be removed */ void clear() /* empty the set */ int size() /* # of elements in the set */ Your Work: A constructor is not defined. It is up to you to define at least one constructor. It might be useful to think about the signatures of addAll, and removeAll before you implement the class. It might be useful to think about in which order you should develop the methods and how you will test the methods. -2- You can not use any existing Java class for this home work. Requirements: You hav e to provide a test environment for your work. You have to name tour storage class Storage.java. Example: An example of a solution execution: This is a compilation and execution of the following code: % ls Storage.java TestStorage.java Storage.java TestStorage.java % java TestStorage aStorage: # of elements: 1 ->a->null You can not add yourself to yourself. aStorage: # of elements: 1 ->a->null % cat TestStorage.java | extractPublic public static void exampleOfHowToUseIt( Storage aStorage) { aStorage = new Storage(); Storage bStorage = new Storage(); aStorage.add(“a”); System.out.println(“aStorage: ” + aStorage ); bStorage.add(“b”); if ( ! aStorage.addAll(aStorage) ) System.out.println(“You can not add yourself to yourself.”); aStorage.addAll(bStorage); aStorage.removeAll(bStorage); System.out.println(“aStorage: ” + aStorage ); } public static void test(Storage aStorage) { if ( ! testRemove() ) System.err.println(“testRemove failed”); if ( ! testRemoveAll() ) System.err.println(“testRemove failed”); if ( ! testContains() ) System.err.println(“testContains failed”); if ( ! testAdd() ) System.err.println(“testAdd failed”); if ( ! testAddAll() ) System.err.println(“testAddAll failed”); if ( ! testClear() ) System.err.println(“testClear failed”); } public static void main(String args[] ) { test(new Storage()); exampleOfHowToUseIt(new Storage()); } } Submission: -3- % ssh glados.cs.rit.edu # or use queeg.cs.rit.edu if glados is down # password # go to the directory where your solution is … % try hpb-grd lab6-1 ’All files required’ # you can see if your submission was successful: # try -q hpb-grd lab6-1 Solution: (This solution serves as the basis for the discussion in class. Sometimes there will be errors introduced to show common mistakes) 1 /* 2 * you can not add or test for null elements in this implementation 3 */ 4 public class Storage implements StorageI { 5 6 private Storage root; 7 private Storage next; 8 private int nElements = 0; 9 10 E payLoad; 11 12 public Storage(){ 13 } 14 public String getClassName() { 15 return “Storage”; 16 } 17 public Object[] toArray() { 18 Object[] anArray = new Object[size()]; 19 Storage runner = root; 20 int index = 0; 21 while ( runner.payLoad != null ) { 22 anArray[index++] = runner.payLoad; 23 runner = runner.next; 24 } 25 return anArray; 26 } 27 public boolean addAll(Storage<? extends E> theSetToAdd) { 28 29 boolean rValue = true; 30 if ( this == theSetToAdd ) { 31 return false; 32 } 33 Storage<? extends E> runner = theSetToAdd.root; 34 while ( runner.payLoad != null ) { 35 rValue &= add(runner.payLoad ); 36 runner = runner.next; 37 } 38 return rValue; 39 } 40 public boolean removeAll(Storage<? extends E> theSetToRemove) { 41 boolean rValue = true; 42 if ( this == theSetToRemove ) { -4- 43 return false; 44 } 45 Storage<? extends E> runner = theSetToRemove.root; 46 while ( runner.payLoad != null ) { 47 if ( contains(runner.payLoad) ) { 48 rValue |= null != remove(runner.payLoad); 49 runner = runner.next; 50 } 51 } 52 return rValue; 53 } 54 public boolean contains(E e) { 55 Storage runner = root; 56 boolean result = false; 57 if ( e == null ) 58 return false; 59 if ( root == null ) 60 result = false; 61 else { 62 while ((runner.payLoad != null ) && 63 ( !(result = runner.payLoad.equals(e) ) ) 64 ) { 65 runner = runner.next; 66 } 67 } 68 return result; 69 } 70 public int size() { 71 return nElements; 72 } 73 74 public boolean add(E e) { 75 boolean rValue = true; 76 if ( e == null ) 77 return false; 78 if ( root == null ) { 79 root = new Storage(); 80 root.payLoad = e; 81 root.next = new Storage(); 82 next = root; 83 } else { 84 if ( contains(e) ) 85 rValue = false; 86 else { 87 Storage toAddAtFront = new Storage(); 88 toAddAtFront.payLoad = e; 89 toAddAtFront.next = root; 90 root = toAddAtFront; 91 rValue = true; 92 } 93 } 94 95 if ( rValue ) 96 nElements ++; -5- 97 return rValue; 98 } 99 public void clear() { 00 root = null; 01 nElements = 0; 02 } 03 E element() { 04 return root.payLoad; 05 } 06 public E remove(E o) { 07 if ( o == null ) 08 return null; 09 Storage index = root; 10 E element = null; 11 int position = -1; 12 if ((root == null ) || ( size() == 0 ) ) 13 element = null; 14 else if ( root.payLoad.equals(o) ) { 15 element = root.payLoad; 16 nElements –; 17 root = root.next; 18 } else { 19 index = root; 20 while ( ( index.next != null ) 21 && ( index.next.payLoad != null ) 22 && !(index.next.payLoad.equals(o) ) ) { 23 index = index.next; 24 } 25 element = index.next.payLoad; 26 index.next = index.next.next; 27 nElements –; 28 } 29 return element; 30 } 31 32 public String toString() { 33 Storage index = root; 34 String result = “# of elements: ” + size() + ” “; 35 int counter = 0; 36 if ( root == null ) 37 return “”; 38 do { 39 if ( index == null ) 40 result = result + “->null”; 41 else 42 result = result + “->” + index.payLoad; 43 index = index.next; 44 } while ( index != null ); 45 return result; 46 } 47 } 48 Source Code: Src/26_sol/Storage_1.java -6- 1 class TestStorage { 2 public static boolean testAdd() { 3 Storage aStorage = new Storage(); 4 String theStrings[] = { “a”, “b”, “c” }; 5 boolean rValue = true; 6 for ( int index = 0; index < theStrings.length; index ++ ) 7 aStorage.add(theStrings[index]); 8 9 for ( int index = 0; index < theStrings.length; index ++ ) { // test if10 rValue &= aStorage.remove(theStrings[index]).equals(theStrings[ind11 } 12 13 aStorage.clear(); 14 rValue &= aStorage.add(theStrings[0]); 15 rValue &= aStorage.size() == 1; 16 17 return rValue; 18 } 19 public static boolean testClear() { 20 Storage aStorage = new Storage(); 21 String theStrings[] = { “a”, “b”, “c” }; 22 boolean rValue = true; 23 24 aStorage.add(“a”); 25 aStorage.clear(); 26 rValue &= aStorage.size() == 0; 27 aStorage.add(“a”); 28 rValue &= aStorage.size() == 1; 29 30 return rValue; 31 } 32 public static boolean testContains() { 33 Storage aStorage = new Storage(); 34 String theStrings[] = { “a”, “b”, “c”, “d” }; 35 boolean rValue = true; 36 37 rValue &= ! aStorage.contains(theStrings[0]); 38 aStorage.add(theStrings[0]); 39 rValue &= aStorage.contains(theStrings[0]); 40 rValue &= ! aStorage.contains(theStrings[1]); 41 42 aStorage.add(theStrings[1]); 43 rValue &= aStorage.contains(theStrings[1]); 44 45 aStorage.add(theStrings[2]); 46 aStorage.add(theStrings[3]); 47 rValue &= aStorage.contains(theStrings[2]); 48 rValue &= aStorage.contains(theStrings[3]); 49 50 return rValue; 51 } 52 public static void addArray(Storage aStorage, String[] theStrings) { 53 for ( int index = 0; index < theStrings.length; index ++ ) -7- 54 aStorage.add(theStrings[index]); 55 } 56 public static boolean testAddAll() { 57 Storage aStorage = new Storage(); 58 Storage bStorage = new Storage(); 59 Storage cStorage = new Storage(); 60 String theAstrings[] = { “a”, “b”, “c” }; 61 String theBstrings[] = { “A”, “B”, “C” }; 62 String theCstrings[] = { “AA”, “BB”, “CC” }; 63 addArray(bStorage, theBstrings); 64 addArray(cStorage, theCstrings); 65 boolean rValue = true; 66 rValue &= aStorage.addAll(bStorage); 67 rValue &= aStorage.size() == theBstrings.length; 68 69 rValue &= aStorage.addAll(cStorage); 70 rValue &= aStorage.size() == theBstrings.length + theCstrings.length; 71 72 rValue &= ! aStorage.addAll(aStorage); 73 return rValue; 74 } 75 public static boolean testRemove() { 76 String theStrings[] = { “a”, “b”, “c” }; 77 Storage aStorage = new Storage(); 78 boolean rValue = true; 79 80 rValue &= null == aStorage.remove(theStrings[0] ); 81 aStorage.add(theStrings[0] ); 82 rValue &= aStorage.remove(theStrings[0] ).equals(theStrings[0]); 83 aStorage.add(theStrings[0]); 84 aStorage.add(theStrings[1]); 85 aStorage.remove(theStrings[0]); 86 rValue &= aStorage.remove(theStrings[1] ).equals(theStrings[1]); 87 88 addArray(aStorage, theStrings); 89 rValue &= aStorage.remove(theStrings[1] ).equals(theStrings[1]); 90 91 addArray(aStorage, theStrings); 92 rValue &= aStorage.remove(theStrings[2] ).equals(theStrings[2]); 93 94 return rValue; 95 } 96 public static boolean testRemoveAll() { 97 boolean rValue = true; 98 String theAstrings[] = { “a”, “b”, “c” }; 99 String theBstrings[] = { “a”, “b”, “c” }; 00 Storage aStorage = new Storage(); 01 Storage bStorage = new Storage(); 02 03 aStorage.add(theAstrings[0] ); 04 aStorage.add(theAstrings[1] ); 05 bStorage.add(theAstrings[0] ); 06 rValue &= aStorage.removeAll(bStorage); 07 -8- 08 return rValue; 09 } 10 public static void exampleOfHowToUseIt( Storage aStorage) { 11 aStorage = new Storage(); 12 Storage bStorage = new Storage(); 13 aStorage.add(“a”); 14 System.out.println(“aStorage: “+aStorage ); 15 bStorage.add(“b”); 16 if (!aStorage.addAll(aStorage) ) 17 System.out.println(“You can not add yourself to yourself.”); 18 aStorage.addAll(bStorage); 19 aStorage.removeAll(bStorage); 20 System.out.println(“aStorage: “+aStorage ); 21 22 } 23 public static void test(Storage aStorage) { 24 if (!testRemove() ) 25 System.err.println(“testRemove failed”); 26 if (!testRemoveAll() ) 27 System.err.println(“testRemove failed”); 28 if (!testContains() ) 29 System.err.println(“testContains failed”); 30 if (!testAdd() ) 31 System.err.println(“testAdd failed”); 32 if (!testAddAll() ) 33 System.err.println(“testAddAll failed”); 34 if (!testClear() ) 35 System.err.println(“testClear failed”); 36 } 37 public static void main(String args[] ) { 38 test(new Storage()); 39 // exampleOfHowToUseIt(new Storage()); 40 41 } 42 } 43 Source Code: Src/26_sol/TestStorage_1.java -9- 1.2. Homework 6.2 (10 Points) Objective: Implementing based on interface and specs Grading: Correctness: You can lose up to 40% if your solution is not correct Quality: You can lose up to 80% if your solution is poorly designed Testing: You can lose up to 50% if your solution is not well tested Explanation: You can lose up to 100% if your solution if you can not explain your solution during the grading session Homework Description: You hav e to implement a storage solution based on a interface and a functionality requirement. Explanation: Given is the following interface: 1 2 public interface StorageI { 3 4 public boolean add(E e); // 2 5 public E get(); 6 public void clear(); // 2 3 7 public boolean contains(E e); 8 public boolean isEmpty(); 9 public void sort(); // 3 10 public int size(); // 2 3 11 public String getClassName(); 12 13 } 14 15 Source Code: Src/26/StorageI.java After sort() is called, get() must return the elements in order, unless a other element is inserted. Your Work: Implement the storage class and test your implementation. The lines in the interface marked with 2, must perform O(1). It might be useful to think about in which order you should develop the methods and how you will test the methods. You can not use any existing Java class for this home work. Requirements: You hav e to provide a test environment for your work. You have to name your class FastAdd.java. Example: An example of a solution execution: Submission: % ssh glados.cs.rit.edu # or use queeg.cs.rit.edu if glados is down # password # go to the directory where your solution is … % try hpb-grd lab6-2 ’All files required’ # you can see if your submission was successful: -10- # try -q hpb-grd lab6-2 Solution: (This solution serves as the basis for the discussion in class. Sometimes there will be errors introduced to show common mistakes) 1 class Storage implements StorageI { 2 3 private Storage root = null; 4 private Storage next = null; 5 private Object[] getArray = null; 6 private int getIndex = -1; 7 private int nElements = 0; 8 private Object[] sorted; 9 E payLoad; 10 11 public Storage(){ 12 } 13 public int size() { 14 return nElements; 15 } 16 17 public boolean add(E e) { 18 if ( root == null ) { 19 root = new Storage(); 20 root.payLoad = e; 21 root.next = new Storage(); 22 next = root; 23 } else { 24 next.payLoad = e; 25 next.next = new Storage(); 26 } 27 next = next.next; 28 nElements++; 29 30 return true; 31 } 32 public void add(int index, E element) { 33 if ( index > nElements ) 34 return; 35 if ( index == nElements ) 36 add(element); 37 else if ( index == 0 ) 38 addFirst(element); 39 else { 40 nElements++; 41 Storage helper = root; 42 for ( int counter = 1; counter < index ; counter ++ ) { 43 helper = helper.next; 44 } 45 Storage tmp = new Storage(); 46 47 tmp.next = helper.next; -11- 48 tmp.payLoad = element; 49 helper.next = tmp; 50 51 } 52 53 } 54 public void addFirst(E e) { 55 Storage newRoot = new Storage(); 56 newRoot.payLoad = e; 57 newRoot.next = root; 58 nElements++; 59 root = newRoot; 60 } 61 public void addLast(E e) { 62 add(e); 63 } 64 public void clear() { 65 root = null; 66 nElements = 0; 67 } 68 public E element() { 69 return root.payLoad; 70 } 71 public E remove() { 72 if ( root == null ) 73 return null; 74 nElements–; 75 E element = root.payLoad; 76 root = root.next; 77 return element; 78 } 79 public E remove(int index) { 80 E element = null; 81 if ( root == null ) { 82 return null; 83 } else if ( index < nElements ) { 84 if ( index == 0 ) { 85 element = remove(); 86 } else { 87 nElements–; 88 Storage helper = root; 89 for ( int counter = 0; counter < index – 1 ; counter ++ ) 90 helper = helper.next; 91 } 92 element = helper.next.payLoad; 93 helper.next = helper.next.next; 94 // System.out.println(“helper.payLoad: ” + helper.payLoad); 95 // System.out.println(“element: ” + element); 96 } 97 } 98 return element; 99 } 00 01 public String toString() { -12- 02 Storage index = root; 03 String result = “# of elements: ” + size() + ” “; 04 int counter = 0; 05 if ( root == null ) 06 return “”; 07 do { 08 if ( index == null ) 09 result = result + “->null”; 10 else 11 result = result + “->” + index.payLoad; 12 index = index.next; 13 } while ( index != null ); 14 return result; 15 } 16 17 public String getClassName() { 18 return getClass().getCanonicalName(); 19 } 20 Object[] toArray() { 21 if ( root == null ) 22 return null; 23 24 Object[] theArray = new Object[size()]; 25 Storage index = root; 26 int runner = 0; 27 28 while ( index != null ) { 29 if ( index.payLoad != null ) 30 theArray[runner++] = index.payLoad; 31 index = index.next; 32 } 33 return theArray; 34 } 35 private static void printArray(Object[] theArray) { 36 for ( int index = 0; index < theArray.length; index ++ ) { 37 System.out.println(index + “: ” + theArray[index]); 38 } 39 } 40 private Object[] bubbleSort(Object[] theArray) { 41 for (int index = 0; index < theArray.length – 1; index++) { 42 for (int walker=0; walker < theArray.length – 1; walker++) { 43 String leftString = theArray[walker].toString(); 44 String rightString = theArray[walker + 1 ].toString(); 45 if ( leftString.compareTo(rightString) > 0 ) { 46 E tmp = (E)theArray[walker]; 47 theArray[walker] = theArray[walker + 1]; 48 theArray[walker+1] = tmp; 49 } 50 } 51 } 52 return theArray; 53 } 54 private void fillTheArray(Object[] theArray) { 55 for ( int index = 0; index < theArray.length; index ++ ) { -13- 56 if ( theArray[index] != null ) 57 add((E)theArray[index]); 58 } 59 } 60 public void sort() { 61 if ( root == null ) 62 return; 63 Object[] theArray = toArray(); 64 clear(); 65 theArray = bubbleSort(theArray ); 66 bubbleSort(theArray ); 67 fillTheArray(theArray ); 68 69 } 70 public boolean isEmpty() { 71 return size() == 0; 72 } 73 public boolean contains(E e) { 74 Storage index = root; 75 boolean rValue = true; 76 boolean found = true;; 77 78 if ( root == null ) 79 rValue = false; 80 else { 81 do { 82 found = e.equals(index.payLoad); 83 index = index.next; 84 } while ( ! found && ( index != null ) ); 85 } 86 87 return rValue && found; 88 } 89 public E get() { 90 if ( root == null ) 91 return null; 92 if ( getIndex == -1 ) { 93 getArray = toArray(); 94 getIndex = 0; 95 } 96 if ( getIndex < getArray.length ) { 97 return (E)getArray[getIndex++]; 98 } else { 99 getIndex = -1; 00 return null; 01 } 02 } 03 public static boolean testAddIndex() { 04 Storage aStorage = new Storage(); 05 String theStrings[] = { “a”, “b”, “c” }; 06 boolean rValue = true; 07 for ( int index = 0; index < theStrings.length; index ++ ) 08 aStorage.add(theStrings[index]); 09 int size; -14- 10 11 String theItem = “0”; 12 aStorage.add(0, theItem); 13 rValue &= aStorage.remove() == theItem; 14 theItem = “1”; 15 size = aStorage.size(); 16 aStorage.add(size, theItem); 17 rValue &= aStorage.remove(size) == theItem; 18 size = aStorage.size(); 19 aStorage.add(size + 1, theItem); 20 rValue &= aStorage.size() == size; 21 theItem = “2”; 22 aStorage.add(1, theItem); 23 rValue &= aStorage.remove(1) == theItem; 24 25 return rValue; 26 } 27 public static boolean testRemoveIndex() { 28 Storage aStorage = new Storage(); 29 String theStrings[] = { “a”, “b”, “c” }; 30 boolean rValue = true; 31 for ( int index = 0; index < theStrings.length; index ++ ) 32 aStorage.add(theStrings[index]); 33 rValue &= aStorage.remove(aStorage.size()) == null; 34 rValue &= aStorage.remove(2).equals(theStrings[2]); 35 rValue &= aStorage.remove(1).equals(theStrings[1]); 36 rValue &= aStorage.remove(0).equals(theStrings[0]); 37 rValue &= aStorage.remove(0) == null; 38 39 aStorage.add(“c”); 40 41 return rValue; 42 } 43 public static boolean testAdd() { 44 Storage aStorage = new Storage(); 45 String theStrings[] = { “a”, “b”, “c” }; 46 boolean rValue = true; 47 for ( int index = 0; index < theStrings.length; index ++ ) 48 aStorage.add(theStrings[index]); 49 for ( int index = 0; index < theStrings.length; index ++ ) 50 rValue &= aStorage.remove().equals(theStrings[index]); 51 rValue &= aStorage.remove() == null; 52 aStorage.add(“c”); 53 54 return rValue; 55 } 56 public static boolean testClassName() { 57 Storage aStorage = new Storage(); 58 59 return “Storage”.equals(aStorage.getClassName()); 60 } 61 public static boolean testClear() { 62 Storage aStorage = new Storage(); 63 boolean rValue = true; -15- 64 65 rValue &= aStorage.remove() == null; 66 aStorage.add(“a”); 67 aStorage.clear(); 68 rValue &= aStorage.size() == 0; 69 70 return rValue; 71 } 72 public static boolean testContains() { 73 Storage aStorage = new Storage(); 74 String theStrings[] = { “a”, “b”, “c” }; 75 76 boolean rValue = true; 77 rValue &= ! aStorage.contains(theStrings[0]); 78 for ( int index = 0; index < theStrings.length; index ++ ) 79 aStorage.add(theStrings[index]); 80 rValue &= aStorage.contains(theStrings[0]); 81 rValue &= ! aStorage.contains(“d”); 82 83 return rValue; 84 } 85 public static boolean testToArray() { 86 Storage aStorage = new Storage(); 87 String theStrings[] = { “a”, “b”, “c” }; 88 boolean rValue = true;; 89 90 for ( int index = 0; index < theStrings.length; index ++ ) 91 aStorage.add(theStrings[index]); 92 Object[] anArrry = aStorage.toArray(); 93 94 rValue &= anArrry.length == aStorage.size(); 95 rValue &= anArrry.length == theStrings.length; 96 return rValue; 97 } 98 public static boolean testGet() { 99 Storage aStorage = new Storage(); 00 String theStrings[] = { “a”, “b”, “c” }; 01 boolean rValue = true;; 02 03 rValue &= aStorage.get() == null; 04 05 for ( int index = 0; index < theStrings.length; index ++ ) 06 aStorage.add(theStrings[index]); 07 for ( int index = 0; index < theStrings.length; index ++ ) 08 rValue &= aStorage.get().equals(theStrings[index]); 09 rValue &= aStorage.get() == null; 10 11 return rValue; 12 } 13 public static boolean testSort() { 14 Storage aStorage = new Storage(); 15 String theStrings[] = { “x”, “t”, “c” }; 16 boolean rValue = true;; 17 -16- 18 for ( int index = 0; index < theStrings.length; index ++ ) 19 aStorage.add(theStrings[index]); 20 21 aStorage.sort(); 22 23 for ( int index = 0; index < aStorage.size() – 1; index ++ ) { 24 String leftString = aStorage.get(); aStorage.remove(); 25 String rightString = aStorage.get(); aStorage.remove(); 26 rValue &= ( leftString.compareTo(rightString) <= 0 ); 27 } 28 return rValue; 29 } 30 public static void exampleOfHowToUseIt( Storage aStorage) { 31 aStorage.add(“a”); 32 aStorage.add(0, “0”); 33 aStorage.add(aStorage.size(), “1”); 34 aStorage.add(aStorage.size() + 1, “2”); 35 System.out.println(“aStorage: “+aStorage ); 36 37 } 38 public static void test(Storage aStorage) { 39 if (!testAdd() ) 40 System.err.println(“testAdd failed”); 41 if (!testRemoveIndex() ) 42 System.err.println(“testRemoveIndex failed”); 43 if (!testAddIndex() ) 44 System.err.println(“testAddIndex failed”); 45 if (!testClear() ) 46 System.err.println(“testClear failed”); 47 if (!testToArray() ) 48 System.err.println(“testToArray failed”); 49 if (!testSort() ) 50 System.err.println(“testSort failed”); 51 if (!testGet() ) 52 System.err.println(“testGet failed”); 53 if (!testContains() ) 54 System.err.println(“testContains failed”); 55 if (!testClassName() ) 56 System.err.println(“testClassName failed”); 57 } 58 public static void main(String args[] ) { 59 test(new Storage()); 60 // exampleOfHowToUseIt(new Storage()); 61 62 } 63 } 64 65 66 67 68 Source Code: Src/26_sol/Storage_2.java -17- 1.3. Homework 6.3 (10 Points) Objective: Implementing based on interface and specs Grading: Correctness: You can lose up to 40% if your solution is not correct Quality: You can lose up to 80% if your solution is poorly designed Testing: You can lose up to 50% if your solution is not well tested Explanation: You can lose up to 100% if your solution if you can not explain your solution during the grading session Homework Description: You hav e to implement a storage solution based on a interface and a functionality requirement. Explanation: Given is the following interface: 1 2 public interface StorageI { 3 4 public boolean add(E e); // 2 5 public E get(); 6 public void clear(); // 2 3 7 public boolean contains(E e); 8 public boolean isEmpty(); 9 public void sort(); // 3 10 public int size(); // 2 3 11 public String getClassName(); 12 13 } 14 15 Source Code: Src/26/StorageI.java After sort() is called, get() must return the elements in order, unless a other element is inserted. Your Work: Implement the storage class and test your implementation. The lines in the interface marked with 3, must perform O(1). 3 is the only differnce between hw 6.2 and hw 6.3. You will need to develop a different underlying data structure. It might be useful to think about in which order you should develop the methods and how you will test the methods. You can not use any existing Java class for this home work. Requirements: You hav e to provide a test environment for your work. You have to name your class FastSort.java. Example: An example of a solution execution: Submission: -18- % ssh glados.cs.rit.edu # or use queeg.cs.rit.edu if glados is down # password # go to the directory where your solution is … % try hpb-grd lab6-3 ’All files required’ # you can see if your submission was successful: # try -q hpb-grd lab6-3 Solution: (This solution serves as the basis for the discussion in class. Sometimes there will be errors introduced to show common mistakes) 1 class Storage implements StorageI { 2 3 private Storage root = null; 4 private Storage next = null; 5 private Object[] getArray = null; 6 private int getIndex = -1; 7 private int nElements = 0; 8 private Object[] sorted; 9 E payLoad; 10 11 public Storage(){ 12 } 13 public int size() { 14 return nElements; 15 } 16 17 public boolean add(E e) { 18 if ( root == null ) { 19 root = new Storage(); 20 root.payLoad = e; 21 root.next = new Storage(); 22 } else { 23 Storage insertAfter = findPosition(e); 24 Storage next = new Storage(); 25 next.payLoad = e; 26 if ( insertAfter == null ) { // new root 27 next.next = root; 28 root = next; 29 } else { 30 next.next = insertAfter.next; 31 insertAfter.next= next; 32 } 33 } 34 nElements++; 35 36 return true; 37 } 38 private Storage findPosition(E element) { 39 Storage runner = root; 40 Storage followUp = null; 41 boolean keepGoing = true; 42 String insertString = element.toString(); -19- 43 44 do { 45 String payLoadString = runner.payLoad.toString(); 46 if ( payLoadString.compareTo(insertString) < 0 ) { 47 followUp = runner; 48 runner = runner.next; 49 keepGoing =(runner.payLoad != null ); 50 } else { 51 keepGoing = false; 52 } 53 } while ( keepGoing ); 54 return followUp; 55 } 56 public void add(int index, E element) { 57 if ( index > nElements ) 58 return; 59 if ( index == nElements ) 60 add(element); 61 else if ( index == 0 ) 62 addFirst(element); 63 else { 64 nElements++; 65 Storage helper = root; 66 for ( int counter = 1; counter < index ; counter ++ ) { 67 helper = helper.next; 68 } 69 Storage tmp = new Storage(); 70 71 tmp.next = helper.next; 72 tmp.payLoad = element; 73 helper.next = tmp; 74 75 } 76 77 } 78 public void addFirst(E e) { 79 Storage newRoot = new Storage(); 80 newRoot.payLoad = e; 81 newRoot.next = root; 82 nElements++; 83 root = newRoot; 84 } 85 public void addLast(E e) { 86 add(e); 87 } 88 public void clear() { 89 root = null; 90 nElements = 0; 91 } 92 public E element() { 93 return root.payLoad; 94 } 95 public E remove() { 96 if ( root == null ) -20- 97 return null; 98 nElements–; 99 E element = root.payLoad; 00 root = root.next; 01 return element; 02 } 03 public E remove(int index) { 04 E element = null; 05 if ( root == null ) { 06 return null; 07 } else if ( index < nElements ) { 08 if ( index == 0 ) { 09 element = remove(); 10 } else { 11 nElements–; 12 Storage helper = root; 13 for ( int counter = 0; counter < index – 1 ; counter ++ ) 14 helper = helper.next; 15 } 16 element = helper.next.payLoad; 17 helper.next = helper.next.next; 18 // System.out.println(“helper.payLoad: ” + helper.payLoad); 19 // System.out.println(“element: ” + element); 20 } 21 } 22 return element; 23 } 24 25 public String toString() { 26 Storage index = root; 27 String result = “# of elements: ” + size() + ” “; 28 int counter = 0; 29 if ( root == null ) 30 return “”; 31 do { 32 if ( index == null ) 33 result = result + “->null”; 34 else 35 result = result + “->” + index.payLoad; 36 index = index.next; 37 } while ( index != null ); 38 return result; 39 } 40 41 public String getClassName() { 42 return getClass().getCanonicalName(); 43 } 44 Object[] toArray() { 45 if ( root == null ) 46 return null; 47 48 Object[] theArray = new Object[size()]; 49 Storage index = root; 50 int runner = 0; -21- 51 52 while ( index != null ) { 53 if ( index.payLoad != null ) 54 theArray[runner++] = index.payLoad; 55 index = index.next; 56 } 57 return theArray; 58 } 59 private static void printArray(Object[] theArray) { 60 for ( int index = 0; index < theArray.length; index ++ ) { 61 System.out.println(index + “: ” + theArray[index]); 62 } 63 } 64 private Object[] bubbleSort(Object[] theArray) { 65 for (int index = 0; index < theArray.length – 1; index++) { 66 for (int walker=0; walker < theArray.length – 1; walker++) { 67 String leftString = theArray[walker].toString(); 68 String rightString = theArray[walker + 1 ].toString(); 69 if ( leftString.compareTo(rightString) > 0 ) { 70 E tmp = (E)theArray[walker]; 71 theArray[walker] = theArray[walker + 1]; 72 theArray[walker+1] = tmp; 73 } 74 } 75 } 76 return theArray; 77 } 78 private void fillTheArray(Object[] theArray) { 79 for ( int index = 0; index < theArray.length; index ++ ) { 80 if ( theArray[index] != null ) 81 add((E)theArray[index]); 82 } 83 } 84 public void sort() { 85 if ( root == null ) 86 return; 87 Object[] theArray = toArray(); 88 clear(); 89 theArray = bubbleSort(theArray ); 90 bubbleSort(theArray ); 91 fillTheArray(theArray ); 92 93 } 94 public boolean isEmpty() { 95 return size() == 0; 96 } 97 public boolean contains(E e) { 98 Storage index = root; 99 boolean rValue = true; 00 boolean found = true;; 01 02 if ( root == null ) 03 rValue = false; 04 else { -22- 05 do { 06 found = e.equals(index.payLoad); 07 index = index.next; 08 } while ( ! found && ( index != null ) ); 09 } 10 11 return rValue && found; 12 } 13 public E get() { 14 if ( root == null ) 15 return null; 16 if ( getIndex == -1 ) { 17 getArray = toArray(); 18 getIndex = 0; 19 } 20 if ( getIndex < getArray.length ) { 21 return (E)getArray[getIndex++]; 22 } else { 23 getIndex = -1; 24 return null; 25 } 26 } 27 public static boolean testAddIndex() { 28 Storage aStorage = new Storage(); 29 String theStrings[] = { “a”, “b”, “c” }; 30 boolean rValue = true; 31 for ( int index = 0; index < theStrings.length; index ++ ) 32 aStorage.add(theStrings[index]); 33 int size; 34 String theItem = “0”; 35 aStorage.add(0, theItem); 36 rValue &= aStorage.remove() == theItem; 37 theItem = “1”; 38 size = aStorage.size(); 39 aStorage.add(size, theItem); 40 rValue &= aStorage.remove(size) == theItem; 41 size = aStorage.size(); 42 aStorage.add(size + 1, theItem); 43 rValue &= aStorage.size() == size; 44 theItem = “2”; 45 aStorage.add(1, theItem); 46 rValue &= aStorage.remove(1) == theItem; 47 48 return rValue; 49 } 50 public static boolean testRemoveIndex() { 51 Storage aStorage = new Storage(); 52 String theStrings[] = { “a”, “b”, “c” }; 53 boolean rValue = true; 54 for ( int index = 0; index < theStrings.length; index ++ ) 55 aStorage.add(theStrings[index]); 56 rValue &= aStorage.remove(aStorage.size()) == null; 57 rValue &= aStorage.remove(2).equals(theStrings[2]); 58 rValue &= aStorage.remove(1).equals(theStrings[1]); -23- 59 rValue &= aStorage.remove(0).equals(theStrings[0]); 60 rValue &= aStorage.remove(0) == null; 61 62 aStorage.add(“c”); 63 64 return rValue; 65 } 66 public static boolean testAdd() { // weak test 67 Storage aStorage = new Storage(); 68 String theStrings[] = { “t”, “x”, “c” }; 69 boolean rValue = true; 70 for ( int index = 0; index < theStrings.length; index ++ ) { 71 aStorage.add(theStrings[index]); 72 } 73 rValue &= aStorage.remove().equals(theStrings[2]); 74 rValue &= aStorage.remove().equals(theStrings[0]); 75 rValue &= aStorage.remove().equals(theStrings[1]); 76 77 rValue &= aStorage.remove() == null; 78 79 return rValue; 80 } 81 public static boolean testClassName() { 82 Storage aStorage = new Storage(); 83 84 return “Storage”.equals(aStorage.getClassName()); 85 } 86 public static boolean testClear() { 87 Storage aStorage = new Storage(); 88 boolean rValue = true; 89 90 rValue &= aStorage.remove() == null; 91 aStorage.add(“a”); 92 aStorage.clear(); 93 rValue &= aStorage.size() == 0; 94 95 return rValue; 96 } 97 public static boolean testContains() { 98 Storage aStorage = new Storage(); 99 String theStrings[] = { “a”, “b”, “c” }; 00 01 boolean rValue = true; 02 rValue &= ! aStorage.contains(theStrings[0]); 03 for ( int index = 0; index < theStrings.length; index ++ ) 04 aStorage.add(theStrings[index]); 05 rValue &= aStorage.contains(theStrings[0]); 06 rValue &= ! aStorage.contains(“d”); 07 08 return rValue; 09 } 10 public static boolean testToArray() { 11 Storage aStorage = new Storage(); 12 String theStrings[] = { “a”, “b”, “c” }; -24- 13 boolean rValue = true;; 14 15 for ( int index = 0; index < theStrings.length; index ++ ) 16 aStorage.add(theStrings[index]); 17 Object[] anArrry = aStorage.toArray(); 18 19 rValue &= anArrry.length == aStorage.size(); 20 rValue &= anArrry.length == theStrings.length; 21 return rValue; 22 } 23 public static boolean testGet() { 24 Storage aStorage = new Storage(); 25 String theStrings[] = { “a”, “b”, “c” }; 26 boolean rValue = true;; 27 28 rValue &= aStorage.get() == null; 29 30 for ( int index = 0; index < theStrings.length; index ++ ) 31 aStorage.add(theStrings[index]); 32 for ( int index = 0; index < theStrings.length; index ++ ) 33 rValue &= aStorage.get().equals(theStrings[index]); 34 rValue &= aStorage.get() == null; 35 36 return rValue; 37 } 38 public static boolean testSort() { 39 Storage aStorage = new Storage(); 40 String theStrings[] = { “x”, “t”, “c” }; 41 boolean rValue = true;; 42 43 for ( int index = 0; index < theStrings.length; index ++ ) 44 aStorage.add(theStrings[index]); 45 46 aStorage.sort(); 47 48 for ( int index = 0; index < aStorage.size() – 1; index ++ ) { 49 String leftString = aStorage.get(); aStorage.remove(); 50 String rightString = aStorage.get(); aStorage.remove(); 51 rValue &= ( leftString.compareTo(rightString) <= 0 ); 52 } 53 return rValue; 54 } 55 public static void exampleOfHowToUseIt( Storage aStorage) { 56 aStorage.add(“a”); 57 aStorage.add(0, “0”); 58 aStorage.add(aStorage.size(), “1”); 59 aStorage.add(aStorage.size() + 1, “2”); 60 System.out.println(“aStorage: “+aStorage ); 61 62 } 63 public static void test(Storage aStorage) { 64 if (!testAdd() ) 65 System.err.println(“testAdd failed”); 66 /* -25- 67 if (!testRemoveIndex() ) 68 System.err.println(“testRemoveIndex failed”); 69 if (!testAddIndex() ) 70 System.err.println(“testAddIndex failed”); 71 if (!testClear() ) 72 System.err.println(“testClear failed”); 73 if (!testToArray() ) 74 System.err.println(“testToArray failed”); 75 if (!testSort() ) 76 System.err.println(“testSort failed”); 77 if (!testGet() ) 78 System.err.println(“testGet failed”); 79 if (!testContains() ) 80 System.err.println(“testContains failed”); 81 if (!testClassName() ) 82 System.err.println(“testClassName failed”); 83 */ 84 } 85 public static void main(String args[] ) { 86 test(new Storage()); 87 // exampleOfHowToUseIt(new Storage()); 88 89 } 90 } 91 92 93 94 95 Source Code: Src/26_sol/Storage_3.java 1 class TestStorage { 2 public static boolean testAdd() { 3 Storage aStorage = new Storage(); 4 String theStrings[] = { “a”, “b”, “c” }; 5 boolean rValue = true; 6 for ( int index = 0; index < theStrings.length; index ++ ) 7 aStorage.add(theStrings[index]); 8 9 for ( int index = 0; index < theStrings.length; index ++ ) { // test if10 rValue &= aStorage.remove(theStrings[index]).equals(theStrings[ind11 } 12 13 aStorage.clear(); 14 rValue &= aStorage.add(theStrings[0]); 15 rValue &= aStorage.size() == 1; 16 17 return rValue; 18 } 19 public static boolean testClear() { 20 Storage aStorage = new Storage(); 21 String theStrings[] = { “a”, “b”, “c” }; 22 boolean rValue = true; -26- 23 24 aStorage.add(“a”); 25 aStorage.clear(); 26 rValue &= aStorage.size() == 0; 27 aStorage.add(“a”); 28 rValue &= aStorage.size() == 1; 29 30 return rValue; 31 } 32 public static boolean testContains() { 33 Storage aStorage = new Storage(); 34 String theStrings[] = { “a”, “b”, “c”, “d” }; 35 boolean rValue = true; 36 37 rValue &= ! aStorage.contains(theStrings[0]); 38 aStorage.add(theStrings[0]); 39 rValue &= aStorage.contains(theStrings[0]); 40 rValue &= ! aStorage.contains(theStrings[1]); 41 42 aStorage.add(theStrings[1]); 43 rValue &= aStorage.contains(theStrings[1]); 44 45 aStorage.add(theStrings[2]); 46 aStorage.add(theStrings[3]); 47 rValue &= aStorage.contains(theStrings[2]); 48 rValue &= aStorage.contains(theStrings[3]); 49 50 return rValue; 51 } 52 public static void addArray(Storage aStorage, String[] theStrings) { 53 for ( int index = 0; index < theStrings.length; index ++ ) 54 aStorage.add(theStrings[index]); 55 } 56 public static boolean testAddAll() { 57 Storage aStorage = new Storage(); 58 Storage bStorage = new Storage(); 59 Storage cStorage = new Storage(); 60 String theAstrings[] = { “a”, “b”, “c” }; 61 String theBstrings[] = { “A”, “B”, “C” }; 62 String theCstrings[] = { “AA”, “BB”, “CC” }; 63 addArray(bStorage, theBstrings); 64 addArray(cStorage, theCstrings); 65 boolean rValue = true; 66 rValue &= aStorage.addAll(bStorage); 67 rValue &= aStorage.size() == theBstrings.length; 68 69 rValue &= aStorage.addAll(cStorage); 70 rValue &= aStorage.size() == theBstrings.length + theCstrings.length; 71 72 rValue &= ! aStorage.addAll(aStorage); 73 return rValue; 74 } 75 public static boolean testRemove() { 76 String theStrings[] = { “a”, “b”, “c” }; -27- 77 Storage aStorage = new Storage(); 78 boolean rValue = true; 79 80 rValue &= null == aStorage.remove(theStrings[0] ); 81 aStorage.add(theStrings[0] ); 82 rValue &= aStorage.remove(theStrings[0] ).equals(theStrings[0]); 83 aStorage.add(theStrings[0]); 84 aStorage.add(theStrings[1]); 85 aStorage.remove(theStrings[0]); 86 rValue &= aStorage.remove(theStrings[1] ).equals(theStrings[1]); 87 88 addArray(aStorage, theStrings); 89 rValue &= aStorage.remove(theStrings[1] ).equals(theStrings[1]); 90 91 addArray(aStorage, theStrings); 92 rValue &= aStorage.remove(theStrings[2] ).equals(theStrings[2]); 93 94 return rValue; 95 } 96 public static boolean testRemoveAll() { 97 boolean rValue = true; 98 String theAstrings[] = { “a”, “b”, “c” }; 99 String theBstrings[] = { “a”, “b”, “c” }; 00 Storage aStorage = new Storage(); 01 Storage bStorage = new Storage(); 02 03 aStorage.add(theAstrings[0] ); 04 aStorage.add(theAstrings[1] ); 05 bStorage.add(theAstrings[0] ); 06 rValue &= aStorage.removeAll(bStorage); 07 08 return rValue; 09 } 10 public static void exampleOfHowToUseIt( Storage aStorage) { 11 aStorage = new Storage(); 12 Storage bStorage = new Storage(); 13 aStorage.add(“a”); 14 System.out.println(“aStorage: “+aStorage ); 15 bStorage.add(“b”); 16 if (!aStorage.addAll(aStorage) ) 17 System.out.println(“You can not add yourself to yourself.”); 18 aStorage.addAll(bStorage); 19 aStorage.removeAll(bStorage); 20 System.out.println(“aStorage: “+aStorage ); 21 22 } 23 public static void test(Storage aStorage) { 24 if (!testRemove() ) 25 System.err.println(“testRemove failed”); 26 if (!testRemoveAll() ) 27 System.err.println(“testRemove failed”); 28 if (!testContains() ) 29 System.err.println(“testContains failed”); 30 if (!testAdd() ) -28- 31 System.err.println(“testAdd failed”); 32 if (!testAddAll() ) 33 System.err.println(“testAddAll failed”); 34 if (!testClear() ) 35 System.err.println(“testClear failed”); 36 } 37 public static void main(String args[] ) { 38 test(new Storage()); 39 // exampleOfHowToUseIt(new Storage()); 40 41 } 42 } 43 Source Code: Src/26_sol/TestStorage_1.java -29-