Implement recursively two methods getFrequencyOf and isBagSorted in two classes: ResizableArrayBag and LinkedBag. Iterative implementations of getFrequencyOf methods are left commented out in the classes for your reference.

isBagSorted returns true if all elements in the bag are sorted in ascending order. Empty and one element bag should be considered sorted.

 public class LinkedBag currentNode = this.firstNode; // while (currentNode != null) // { // if (anEntry.equals(currentNode.data)) // { // frequency++; // } // // currentNode = currentNode.next; // } // // return frequency; // } // end getFrequencyOf public int getFrequencyOf(T anEntry) { return getFrequencyOf(anEntry, this.firstNode); } private int getFrequencyOf(T anEntry, Node currentNode) { // TODO Project #1a // implement recursively return 0; // THIS IS A STUB } /** * isBagSorted - a method that checks if the elements in this.bag are sorted */ public boolean isBagSorted() { return isBagSorted(this.firstNode); } /** * isBagSorted - a private helper recursive method that checks if the elements in this.bag are sorted * * @param currentNode node of the current element in this.bag */ private boolean isBagSorted(Node currentNode) { // TODO Project #1b // implement recursively return true; // THIS IS A STUB } /** * Tests whether this bag contains a given entry. * * @param anEntry the entry to locate * @return true if the bag contains anEntry, or false otherwise */ public boolean contains(T anEntry) { return getReferenceTo(anEntry) != null; } // end contains // Locates a given entry within this bag. // Returns a reference to the node containing the entry, if located, // or null otherwise. private Node getReferenceTo(T anEntry) { boolean found = false; Node currentNode = this.firstNode; while (!found && (currentNode != null)) { if (anEntry.equals(currentNode.data)) found = true; else currentNode = currentNode.next; } // end while return currentNode; } // end getReferenceTo /** * Removes all entries from this bag. */ public void clear() { while (!isEmpty()) remove(); } // end clear /** * Removes one unspecified entry from this bag, if possible. * * @return either the removed entry, if the removal * was successful, or null */ public T remove() { T result = null; if (this.firstNode != null) { result = this.firstNode.data; this.firstNode = this.firstNode.next; // remove first node from chain } // end if return result; } // end remove /** * Removes one occurrence of a given entry from this bag, if possible. * * @param anElement the entry to be removed * @return true if the removal was successful, or false otherwise */ public boolean removeElement(T anElement) { boolean result = false; Node nodeN = getReferenceTo(anElement); if (nodeN != null) { nodeN.data = this.firstNode.data; // replace located entry with entry in first node this.firstNode = this.firstNode.next; // remove first node from chain // this.numberOfEntries--; result = true; } // end if return result; } // end remove /** * Displays all the elements in the bag */ public void display() { int counter = 0; if (this.firstNode != null) { Node currentNode = this.firstNode; while (currentNode != null) { System.out.print(currentNode.data + " "); currentNode = currentNode.next; counter++; } System.out.println(); System.out.print("There are " + counter + " element(s) in the bag."); System.out.println(); } else System.out.println("The bag is empty."); } // end display private class Node { private S data; // entry in bag private Node next; // link to next node private Node(S dataPortion) { this(dataPortion, null); } // end constructor private Node(S dataPortion, Node nextNode) { this.data = dataPortion; this.next = nextNode; } } // end Node public static void main(String[] args) { LinkedBag bag = new LinkedBag<>(); bag.add("Y"); bag.add("A"); bag.add("B"); bag.add("A"); bag.add("C"); bag.add("B"); bag.add("A"); bag.add("B"); bag.add("A"); bag.add("X"); bag.add("Z"); System.out.println(" ***Testing getFrequencyOf method***"); System.out.println("Bag1 contains:"); bag.display(); System.out.println("There are " + bag.getFrequencyOf("A") + " of \"A\""); System.out.println("There are " + bag.getFrequencyOf("B") + " of \"B\""); System.out.println("There are " + bag.getFrequencyOf("C") + " of \"C\""); System.out.println("There are " + bag.getFrequencyOf("K") + " of \"K\""); System.out.println("There are " + bag.getFrequencyOf("X") + " of \"X\""); System.out.println("There are " + bag.getFrequencyOf("Y") + " of \"Y\""); System.out.println("There are " + bag.getFrequencyOf("Z") + " of \"Z\""); System.out.println(" ***Testing isBagSorted method***"); bag.display(); System.out.println("Bag is " + (bag.isBagSorted() ? "" : "NOT") + " sorted"); System.out.println(); System.out.println("Changing the content of the bag"); bag.clear(); bag.display(); System.out.println("Bag is" + (bag.isBagSorted() ? "" : " NOT") + " sorted"); System.out.println(); System.out.println("Changing the content of the bag"); bag.add("X"); bag.display(); System.out.println("Bag is" + (bag.isBagSorted() ? "" : " NOT") + " sorted"); System.out.println(); System.out.println("Changing the content of the bag"); bag.add("Y"); bag.display(); System.out.println("Bag is" + (bag.isBagSorted() ? "" : " NOT") + " sorted"); System.out.println(); System.out.println("Changing the content of the bag"); bag.clear(); bag.add("Y"); bag.add("X"); bag.display(); System.out.println("Bag is" + (bag.isBagSorted() ? "" : " NOT") + " sorted"); System.out.println(); System.out.println("Changing the content of the bag"); bag.clear(); final int ASCII_A = 65; int NUMBER_OF_ELEMENTS = 11; for (int i = NUMBER_OF_ELEMENTS - 1; i >= 0; i--) { bag.add((char) (ASCII_A + i) + ""); } bag.add("Z"); bag.display(); System.out.println("Bag is" + (bag.isBagSorted() ? "" : " NOT") + " sorted"); System.out.println(); System.out.println("Changing the content of the bag"); bag.removeElement("Z"); bag.display(); System.out.println("Bag is" + (bag.isBagSorted() ? "" : " NOT") + " sorted"); System.out.println(); System.out.println("Changing the content of the bag"); bag.removeElement("K"); bag.display(); System.out.println("Bag is" + (bag.isBagSorted() ? "" : " NOT") + " sorted"); System.out.println(); System.out.println("Changing the content of the bag"); bag.clear(); for (int i = 0; i < NUMBER_OF_ELEMENTS; i++) { bag.add((char) (ASCII_A + i) + ""); } bag.display(); System.out.println("Bag is" + (bag.isBagSorted() ? "" : " NOT") + " sorted"); System.out.println(); } // end main } // end LinkedBag