Lab #12 CMPS 144L Fall 2021 CMPS 144L Spring 2021 Lab #12 (November 18): Recursive List Utilities These three files provide a Java implementation of the recursive list abstract data type: RecursiveList: interface that specifies the recursive list abstract data type. RecursiveListEmpty: concrete Java class whose instances represent empty lists. RecursiveListNonEmpty: concrete Java class whose instances represent non-empty lists. The Java class RecListLabUtils has seven stubbed methods, each of which involves a recursive list containing integer values. Complete as many of the methods as you can. Each one's most natural solution is recursive, meaning that it calls itself, except in simple cases. Here are brief descriptions: numOccur(): Given a list and an integer k, returns how many times k occurs in the list. Example: numOccur([4,7,2,7,3], 7) yields 2 removeFirst(): Given a list and an integer k, returns a list identical to the given one, except that the first occurrence of k (if one exists) is absent. Example: removeFirst([4,7,2,7,3],7) yields [4,2,7,3] removeAll(): Given a list and an integer k, returns a list identical to the given one, except that every occurrence of k is absent. Example: removeAll([4,7,2,7,3],7) yields [4,2,3] prefixOf(): Given a list and a nonnegative integer k, returns the prefix of length k of the list. Example: prefixOf([4,7,2,7,3,5],3) yields [4,7,2] suffixOf(): Given a list and a nonnegative integer k, returns the suffix of the list obtained by "chopping off" its prefix of length k. Example: suffixOf([4,7,2,7,3,5],4) yields [3,5] isAscending(): Given a list, reports whether or not its elements are in ascending order. Example 1: isAscending([4,7,2,7,3,5]) yields false Example 2: isAscending([4,7,9,9,15]) yields true orderedInsert(): Given a list whose elements are in ascending order and an integer k, returns the list obtained by "inserting" k into its rightful place within the list (i.e., to preserve its being in ascending order). Example: orderedInsert([2,5,8,8,13], 6) yields [2,5,6,8,8,13] The methods lengthOf(), get(), and put() are included, in full, simply to give you examples to emulate. Note that your four main tools are the methods isEmpty(), headOf(), tailOf(), and cons(). For tesing your work, provided to you is the Java application RecListLabUtilsTester. For each method X() among those that are stubbed, this application has a method named testX() that calls X() several times, each time reporting the result. Assuming that all seven stubbed methods are completed correctly, running this application will produce the output shown below. Of course, you are free to modify the application to make it suit your needs. In particular, you will probably want to comment out calls (in the main() method) to testX() methods that are not relevant to you at the moment. Testing the numOccur() method...
With respect to the list [3 5 4 6 3 5 7 1 3 6 5 ]:
numOccur(list,0) yields 0
numOccur(list,1) yields 1
numOccur(list,2) yields 0
numOccur(list,3) yields 3
numOccur(list,4) yields 1
numOccur(list,5) yields 3
numOccur(list,6) yields 2
numOccur(list,7) yields 1
numOccur(list,8) yields 0
Testing the removeFirst() method...
With respect to the list [3 5 4 6 3 5 7 1 3 6 5 ]:
removeFirst(list,1) yields [3 5 4 6 3 5 7 3 6 5 ]
removeFirst(list,2) yields [3 5 4 6 3 5 7 1 3 6 5 ]
removeFirst(list,3) yields [5 4 6 3 5 7 1 3 6 5 ]
removeFirst(list,4) yields [3 5 6 3 5 7 1 3 6 5 ]
removeFirst(list,5) yields [3 4 6 3 5 7 1 3 6 5 ]
removeFirst(list,6) yields [3 5 4 3 5 7 1 3 6 5 ]
removeFirst(list,7) yields [3 5 4 6 3 5 1 3 6 5 ]
removeFirst(list,8) yields [3 5 4 6 3 5 7 1 3 6 5 ]
Testing the removeAll() method...
With respect to the list [3 5 4 6 3 5 7 1 3 6 5 ]:
removeAll(list,1) yields [3 5 4 6 3 5 7 3 6 5 ]
removeAll(list,2) yields [3 5 4 6 3 5 7 1 3 6 5 ]
removeAll(list,3) yields [5 4 6 5 7 1 6 5 ]
removeAll(list,4) yields [3 5 6 3 5 7 1 3 6 5 ]
removeAll(list,5) yields [3 4 6 3 7 1 3 6 ]
removeAll(list,6) yields [3 5 4 3 5 7 1 3 5 ]
removeAll(list,7) yields [3 5 4 6 3 5 1 3 6 5 ]
removeAll(list,8) yields [3 5 4 6 3 5 7 1 3 6 5 ]
Testing the prefixOf() method...
With respect to the list [3 7 4 9 6 ]:
prefixOf(list,0) is [].
prefixOf(list,1) is [3 ].
prefixOf(list,2) is [3 7 ].
prefixOf(list,3) is [3 7 4 ].
prefixOf(list,4) is [3 7 4 9 ].
prefixOf(list,5) is [3 7 4 9 6 ].
prefixOf(list,6) is [3 7 4 9 6 ].
Testing the suffixOf() method...
With respect to the list [3 7 4 9 6 ]:
suffixOf(list,0) is [3 7 4 9 6 ].
suffixOf(list,1) is [7 4 9 6 ].
suffixOf(list,2) is [4 9 6 ].
suffixOf(list,3) is [9 6 ].
suffixOf(list,4) is [6 ].
suffixOf(list,5) is [].
suffixOf(list,6) is [].
Testing the isAscending() method...
isAscending([3 5 4 6 3 5 7 1 3 6 5 ]) is false
isAscending([1 3 4 6 7 ]) is true
isAscending([1 3 3 3 6 7 ]) is true
Testing the orderedInsert() method...
With respect to the list [1 2 5 7 8 ]:
orderedInsert(list,0) is [0 1 2 5 7 8 ].
orderedInsert(list,2) is [1 2 2 5 7 8 ].
orderedInsert(list,4) is [1 2 4 5 7 8 ].
orderedInsert(list,6) is [1 2 5 6 7 8 ].
orderedInsert(list,8) is [1 2 5 7 8 8 ].
orderedInsert(list,10) is [1 2 5 7 8 10 ].
