Instructions
Requirements and Specifications
Source Code
A5 EXERCISE
public class A5Exercises {
// PART 1
/*
* Purpose: get a count of the number of elements in the array
* with a value that is a multiple of x
* Parameters: int[] arr
* Returns: int - the number multiples of x
* Pre-condition: x > 0
* Post-condition - the array contents are unchanged
*/
public static int countMultiples(int[] arr, int x) {
return countMultiplesStep(arr, x, arr.length);
}
private static int countMultiplesStep(int[] arr, int x, int len) {
if (len == 0) {
return 0;
}
return (arr[len-1] % x == 0 ? 1 : 0) + countMultiplesStep(arr, x, len-1);
}
/*
* Purpose: double all values in the given array
* Parameters: int[] array - the array to modify
* Returns: void - nothing
*/
public static void doubleAll(int[] array) {
doubleAllStep(array, array.length);
}
private static void doubleAllStep(int[] arr, int len) {
if (len == 0) {
return;
}
arr[len-1] *= 2;
doubleAllStep(arr, len-1);
}
/*
* Purpose: get the minimum value found in the array
* Parameters: int[] array - the array to search
* Returns: int - minimum value found in the array
* or -1 if the array is empty
* Post-condition - the array contents are unchanged
*/
public static int getMinimum(int[] array) {
return getMinimum(array, array.length);
}
private static int getMinimum(int[] arr, int len) {
if (len == 0) {
return -1;
}
if (len == 1) {
return arr[0];
}
return Math.min(arr[len-1], getMinimum(arr, len-1));
}
// PART II
/*
* Purpose: get the total number of books in s
* Parameters: Stack s - the stack of books
* Returns: int - the total number of books
* Post-condition: s is not modified
*/
public static int totalBooks(Stack s) {
return totalBooksStep(s);
}
private static int totalBooksStep(Stack s) {
if (s.isEmpty()) {
return 0;
}
Book top = s.pop();
int result = 1 + totalBooksStep(s);
s.push(top);
return result;
}
/*
* Purpose: get the total number of pages of all
* books in the stack
* Parameters: Stack s - the stack of books
* Returns: int - the total number of pages
* Post-condition: s is not modified
*/
public static int totalPages(Stack s) {
return totalPagesStep(s);
}
private static int totalPagesStep(Stack s) {
if (s.isEmpty()) {
return 0;
}
Book top = s.pop();
int result = top.getPages() + totalPagesStep(s);
s.push(top);
return result;
}
/*
* Purpose: get the average number of pages of books in s
* Parameters: Stack s - the stack of books
* Returns: double - the average number of pages
* 0.0 if there are no books in s
* Post-condition: s is not modified
*/
public static double averagePages(Stack s) {
// You don't need to change this, if you have
// completed the previous two exercises
// correctly, it should pass all the tests
if (s.isEmpty()) {
return 0.0;
} else {
double sum = totalPages(s);
int count = totalBooks(s);
return sum/count;
}
}
/*
* Purpose: determine whether toFind is contained in s
* Parameters: Stack s - the stack of books
* Book toFind - the book to search for
* Returns: boolean - true if s contains toFind, false otherwise
* Post-condition: s is not modified
*/
public static boolean containsBook(Stack s, Book toFind) {
return containsBookStep(s, toFind);
}
private static boolean containsBookStep(Stack s, Book toFind) {
if (s.isEmpty()) {
return false;
}
if (toFind.equals(s.top())) {
return true;
}
Book top = s.pop();
boolean result = containsBookStep(s, toFind);
s.push(top);
return result;
}
/*
* Purpose: determine the books in s are stacked correctly
* (ie. there is never a book stacked on top of
* another book with fewer pages)
* Parameters: Stack s - the stack of books
* Returns: boolean - true if books in s are stacked correctly
* Post-condition: s is not modified
*/
public static boolean stackedCorrectly(Stack s) {
return stackedCorrectlyStep(s);
}
public static boolean stackedCorrectlyStep(Stack s) {
if (s.isEmpty()) {
return true;
}
Book top = s.pop();
if (s.isEmpty()) {
s.push(top);
return true;
}
if (top.getPages() > s.top().getPages()) {
s.push(top);
return false;
}
boolean result = stackedCorrectlyStep(s);
s.push(top);
return result;
}
}
A5 NODE
apublic class A5Node{
private T data;
protected A5Node next;
public A5Node (T value) {
this.data = value;
this.next = null;
}
/*
* Purpose: get the data value of this Node
* Parameters: nothing
* Returns: T - the data value
*/
public T getData() {
return data;
}
/*
* Purpose: get the next node
* Parameters: nothing
* Returns: A5Node - the next node
*/
public A5Node getNext() {
return next;
}
/*
* Purpose: update the next reference for this node
* Parameters: A5Node next - the new next
* Returns: void - nothing
*/
public void setNext(A5Node next) {
this.next = next;
}
}
A5 STACK
public class A5Stack implements Stack {
private A5Node head;
public A5Stack() {
head = null;
}
public void push(T value) {
A5Node n = new A5Node(value);
n.next = head;
head = n;
}
public T pop() {
if (isEmpty()) {
return null;
} else {
T toReturn = head.getData();
head = head.next;
return toReturn;
}
}
public T top() {
if (isEmpty()) {
return null;
} else {
return head.getData();
}
}
public void popAll() {
head = null;
}
public boolean isEmpty() {
return head == null;
}
/************
FOR TESTING
************/
// Create a stack from an array of books
public A5Stack (T[] books) {
head = null;
for (int i = books.length-1; i >= 0; i--) {
push(books[i]);
}
}
public String toString() {
if (isEmpty()) {
return "{}";
}
String s = "{";
A5Node cur = head;
while (cur.next != null) {
s += cur.getData().toString() + ", ";
cur = cur.next;
}
s += cur.getData().toString() + "}";
return s;
}
}
BOOK
public class Book {
private String title;
private String author;
private int numPages;
public Book(String title, String author, int numPages) {
this.title = title;
this.author = author;
this.numPages = numPages;
}
public int getPages() {
return numPages;
}
public boolean isLonger(Book other) {
return this.numPages > other.numPages;
}
public boolean equals(Book other) {
return this.title.equals(other.title)
&& this.author.equals(other.author)
&& this.numPages == other.numPages;
}
public String toString() {
return "\"" + title + "\" (" + numPages + ")";
}
}