Question from Object-Oriented Data Structures Using Java 4th Edition Chapter 5 Question 30 Add the following...
Question from Object-Oriented Data Structures Using Java 4th Edition
Chapter 5 Question 30
Add the following methods to the LinkedCollection class, and create a test driver for each to show that they work correctly. Code each of these methods by accessing the internal variables of the LinkedCollection, not by calling the previously defined methods of the class.String toString() creates and returns a string that correctly represents the current collection.
1. Such a method could prove useful for testing and debugging the class and for testing and debugging applications that use the class. Assume each stored element already provides its own reasonable toString method.
2. int count(T target) returns a count of the number of elements e in the collection such that e.equals(target) is true.
3. void removeAll(T target) removes all elements e from the collection such that e.equals(target) is true.
4. LinkedCollection combine(LinkedCollection other) creates and returns a new SortedArrayCollection object that is a combination of this object and the argument object.
//---------------------------------------------------------------------------
// LinkedCollection.java by Dale/Joyce/Weems Chapter 5
//
// Implements the CollectionInterface using a linked collection.
// Null elements are not allowed. Duplicate elements are allowed.
// One constructor is provided, one that creates an empty collection.
//---------------------------------------------------------------------------
public class LinkedCollection implements CollectionInterface
{
protected LLNode head; // head of the linked list
protected int numElements = 0; // number of elements in this collection
// set by find method
protected boolean found; // true if target found, else false
protected LLNode location; // node containing target, if found
protected LLNode previous; // node preceding location
public LinkedCollection()
{
numElements = 0;
head = null;
}
public boolean add(T element)
// Adds element to this collection.
{
LLNode newNode = new LLNode(element);
newNode.setLink(head);
head = newNode;
numElements++;
return true;
}
protected void find(T target)
// Searches the collection for an occurence of an element e such that
// e.equals(target). If successful, sets instance variables
// found to true, location to node containing e, and previous
// to the node that links to location. If not successful, sets
// found to false.
{
location = head;
found = false;
while (location != null)
{
if (location.getInfo().equals(target)) // if they match
{
found = true;
return;
}
else
{
previous = location;
location = location.getLink();
}
}
}
public int size()
// Returns the number of elements on this collection.
{
return numElements;
}
public boolean contains (T target)
// Returns true if this collection contains an element e such that
// e.equals(target); otherwise, returns false.
{
find(target);
return found;
}
public boolean remove (T target)
// Removes an element e from this collection such that e.equals(target)
// and returns true; if no such element exists, returns false.
{
find(target);
if (found)
{
if (head == location)
head = head.getLink(); // remove first node
else
previous.setLink(location.getLink()); // remove node at location
numElements--;
}
return found;
}
public T get(T target)
// Returns an element e from this collection such that e.equals(target);
// if no such element exists, returns null.
{
find(target);
if (found)
return location.getInfo();
else
return null;
}
public boolean isEmpty()
// Returns true if this collection is empty; otherwise, returns false.
{
return (numElements == 0);
}
public boolean isFull()
// Returns true if this collection is full; otherwise, returns false.
{
return false; // Linked implementation is never full
}
}
//----------------------------------------------------------------------------
// SortedArrayCollection.java by Dale/Joyce/Weems Chapter 5
//
// Implements the CollectionInterface using a sorted array. The collection is
// stored in increasing order as defined by the compareTo method of the added
// elements. Only Comparable elements should be added to a collection. It is
// assumed that the compareTo method and equals method as defined for added
// elements are consistent.
//
// Null elements are not permitted in this collection.
//
// Two constructors are provided: one that creates a collection of a default
// original capacity, and one that allows the calling program to specify the
// original capacity. The collection is unbounded.
//----------------------------------------------------------------------------
public class SortedArrayCollection<T> implements CollectionInterface<T>
{
protected final int DEFCAP = 100; // default capacity
protected int origCap; // original capacity
protected T[] elements; // array to hold collection elements
protected int numElements = 0; // number of elements in this collection
// set by find method
protected boolean found; // true if target found, otherwise false
protected int location; // indicates location of target if found,
// indicates add index if not found
public SortedArrayCollection()
{
elements = (T[]) new Object[DEFCAP];
origCap = DEFCAP;
}
public SortedArrayCollection(int capacity)
{
elements = (T[]) new Object[capacity];
this.origCap = capacity;
}
protected void enlarge()
// Increments the capacity of the collection by an amount
// equal to the original capacity.
{
// Create the larger array.
T[] larger = (T[]) new Object[elements.length + origCap];
// Copy the contents from the smaller array into the larger array.
for (int i = 0; i < numElements; i++)
{
larger[i] = elements[i];
}
// Reassign elements reference.
elements = larger;
}
protected void find(T target)
// Searches elements for an occurrence of an element e such that
// e.equals(target). If successful, sets instance variables
// found to true and location to the array index of e. If
// not successful, sets found to false and location to the
// array index where target should be inserted.
{
location = 0;
found = false;
if (!isEmpty())
recFind(target, 0, numElements - 1);
}
protected void recFind(T target, int first, int last)
// Used by find.
{
int result; // result of the comparison
if (first > last)
{
found = false;
result = ((Comparable)target).compareTo(elements[location]);
if (result > 0)
location++; // adjust location to indicate insert index
}
else
{
location = (first + last) / 2;
result = ((Comparable)target).compareTo(elements[location]);
if (result == 0) // found target
found = true;
else
if (result > 0) // target too high
recFind(target, location + 1, last);
else // target too low
recFind(target, first, location - 1);
}
}
public boolean add(T element)
// Precondition: element is Comparable to previously added objects
//
// Adds element to this collection.
{
if (numElements == elements.length)
enlarge();
find(element); // sets location to index where element belongs
for (int index = numElements; index > location; index--)
elements[index] = elements[index - 1];
elements[location] = element;
numElements++;
return true;
}
public boolean remove (T target)
// Removes an element e from this collection such that e.equals(target)
// and returns true; if no such element exists, returns false.
{
find(target);
if (found)
{
for (int i = location; i <= numElements - 2; i++)
elements[i] = elements[i+1];
elements[numElements - 1] = null;
numElements--;
}
return found;
}
public int size()
// Returns the number of elements on this collection.
{
return numElements;
}
public boolean contains (T target)
// Returns true if this collection contains an element e such that
// e.equals(target); otherwise, returns false.
{
find(target);
return found;
}
public T get(T target)
// Returns an element e from this collection such that e.equals(target);
// if no such element exists, returns null.
{
find(target);
if (found)
return elements[location];
else
return null;
}
public boolean isEmpty()
// Returns true if this collection is empty; otherwise, returns false.
{
return (numElements == 0);
}
public boolean isFull()
// This collection is unbounded so always returns false.
{
return false;
}
}
Homework Answers
SortedArrayCollection.java
public class SortedArrayCollection<T> implements
CollectionInterface<T>
{
protected final int DEFCAP = 100; // default capacity
protected int origCap; // original capacity
protected T[] elements; // array to hold collection elements
protected int numElements = 0; // number of elements in this
collection
// set by find method
protected boolean found; // true if target found, otherwise
false
protected int location; // indicates location of target if
found,
// indicates add index if not found
public SortedArrayCollection()
{
elements = (T[]) new Object[DEFCAP];
origCap = DEFCAP;
}
public SortedArrayCollection(int capacity)
{
elements = (T[]) new Object[capacity];
this.origCap = capacity;
}
protected void enlarge()
// Increments the capacity of the collection by an amount
// equal to the original capacity.
{
// Create the larger array.
T[] larger = (T[]) new Object[elements.length + origCap];
// Copy the contents from the smaller array into the larger
array.
for (int i = 0; i < numElements; i++)
{
larger[i] = elements[i];
}
// Reassign elements reference.
elements = larger;
}
protected void find(T target)
// Searches elements for an occurrence of an element e such
that
// e.equals(target). If successful, sets instance variables
// found to true and location to the array index of e. If
// not successful, sets found to false and location to the
// array index where target should be inserted.
{
location = 0;
found = false;
if (!isEmpty())
recFind(target, 0, numElements - 1);
}
protected void recFind(T target, int first, int last)
// Used by find.
{
int result; // result of the comparison
if (first > last)
{
found = false;
result = ((Comparable)target).compareTo(elements[location]);
if (result > 0)
location++; // adjust location to indicate insert index
}
else
{
location = (first + last) / 2;
result = ((Comparable)target).compareTo(elements[location]);
if (result == 0) // found target
found = true;
else
if (result > 0) // target too high
recFind(target, location + 1, last);
else // target too low
recFind(target, first, location - 1);
}
}
public boolean add(T element)
// Precondition: element is Comparable to previously added
objects
//
// Adds element to this collection.
{
if (numElements == elements.length)
enlarge();
find(element); // sets location to index where element
belongs
for (int index = numElements; index > location; index--)
elements[index] = elements[index - 1];
elements[location] = element;
numElements++;
return true;
}
public boolean remove (T target)
// Removes an element e from this collection such that
e.equals(target)
// and returns true; if no such element exists, returns
false.
{
find(target);
if (found)
{
for (int i = location; i <= numElements - 2; i++)
elements[i] = elements[i+1];
elements[numElements - 1] = null;
numElements--;
}
return found;
}
public int size()
// Returns the number of elements on this collection.
{
return numElements;
}
public boolean contains (T target)
// Returns true if this collection contains an element e such
that
// e.equals(target); otherwise, returns false.
{
find(target);
return found;
}
public T get(T target)
// Returns an element e from this collection such that
e.equals(target);
// if no such element exists, returns null.
{
find(target);
if (found)
return elements[location];
else
return null;
}
public boolean isEmpty()
// Returns true if this collection is empty; otherwise, returns
false.
{
return (numElements == 0);
}
public boolean isFull()
// This collection is unbounded so always returns false.
{
return false;
}
public String toString()
{
if(isEmpty())
return "";
String str = elements[0].toString();
for(int i = 1; i < numElements; i++)
str += ", " + elements[i];
return str;
}
public T smallest()
{
if(isEmpty())
return null;
else
return elements[0];
}
public int greater(T elem)
{
if(isEmpty())
return 0;
find(elem);
int idx = location;
if(found)
{
while(elements[idx].equals(elem))
idx++;
}
return numElements - idx;
}
SortedArrayCollection<T>
combine(SortedArrayCollection<T> other)
{
int idx1 = 0, idx2 = 0, idx3 = 0;
int sz1 = size(), sz2 = other.size();
SortedArrayCollection<T> col = new
SortedArrayCollection<>(sz1 + sz2);
while(idx1 < sz1 && idx2 < sz2)
{
if(((Comparable)(elements[idx1])).compareTo(other.elements[idx2])
< 0)
col.add(elements[idx1++]);
else
col.add(other.elements[idx2++]);
}
while(idx1 < sz1)
col.add(elements[idx1++]);
while(idx2 < sz2)
col.add(other.elements[idx2++]);
return col;
}
}
TestSortedCollection.java
public class TestSortedCollection {
public static void main(String[] args) {
SortedArrayCollection<String> fruits = new
SortedArrayCollection<String>();
fruits.add("orange");
fruits.add("grapes");
fruits.add("pineapple");
fruits.add("apple");
System.out.println("The fruits collection is " +
fruits.toString());
System.out.println("The smallest is " + fruits.smallest());
System.out.println("greater than banana = " +
fruits.greater("banana"));
System.out.println("greater than watermelon = " +
fruits.greater("watermelon"));
System.out.println("greater than grapes = " +
fruits.greater("grapes"));
SortedArrayCollection<String> veggies = new
SortedArrayCollection<String>();
veggies.add("tomato");
veggies.add("chilly");
veggies.add("brinjal");
veggies.add("potato");
SortedArrayCollection<String> all =
fruits.combine(veggies);
System.out.println("The fruits collection is " +
fruits.toString());
System.out.println("The veggies collection is " +
veggies.toString());
System.out.println("All combined is " + all.toString());
}
}
output :
The fruits collection is apple, grapes, orange, pineapple
The smallest is apple
greater than banana = 3
greater than watermelon = 0
greater than grapes = 2
The fruits collection is apple, grapes, orange, pineapple
The veggies collection is brinjal, chilly, potato, tomato
All combined is apple, brinjal, chilly, grapes, orange, pineapple,
potato, tomato
Add Answer to:
Question from Object-Oriented Data Structures Using Java 4th
Edition
Chapter 5 Question 30
Add the following...
Modify the LinkedCollection class to be a SortedLinkedCollecton class and see how that effects our implementation...
Modify the LinkedCollection class to be a SortedLinkedCollecton class and see how that effects our implementation for adding and removing items. You should reference the SortedArrayCollection class provided for how these algorithms should be implemented. What needs to change here? Is it a lot of code or not much? Include a toString method that creates and returns a string that correctly represents the current collection. Include a test driver application that demonstrates your class correctly. //--------------------------------------------------------------------------- // LinkedCollection.java // //...
Suppose we decide to add a new operation to our Stack ADT called sizeIs, which returns...
Suppose we decide to add a new operation to our Stack ADT called sizeIs, which returns a value of primitive type int equal to the number of items on the stack. The method signature for sizeIS is public int sizeIs() a.) Write the code for sizeIs for the ArrayStack class b.) Write the code for sizeIs for the LinkedStack class (do not add any instance variables to the class; each time sizeIs is called you must "walk" through the stack...
Plz help me with the code. And here are the requirement. Thanks!! You are required to...
Plz help me with the code. And here are the requirement. Thanks!! You are required to design and implement a circular list using provided class and interface. Please filling the blank in CircularList.java. This circular list has a tail node which points to the end of the list and a number indicating how many elements in the list. And fill out the blank of the code below. public class CircularList<T> implements ListInterface<T> { protected CLNode<T> tail; // tail node that...
In Java You may add any classes or methods to the following as you see fit in order to complete t...
In Java You may add any classes or methods to the following as you see fit in order to complete the given tasks. Modify the LinkedList (or DoubleLinkedList) class and add a method append. append should take another LinkedList (DoubleLinkedList) as input and append that list to the end of this list. The append method should work by doing a few "arrow" adjustments on the boxes and it should not loop through the input list to add elements one at...
When compiling the LinkedList and Iterator class, the following error is being produced: Note: LinkedList.java uses...
When compiling the LinkedList and Iterator class, the following error is being produced: Note: LinkedList.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details. Any suggestions? public class LinkedList<T> { Node<T> itsFirstNode; Node<T> itsLastNode; private int size; public LinkedList() { itsFirstNode = null; itsLastNode = null; size = 0; } public Iterator<T> getIterator() { return new Iterator(this); } // THIS WILL NEED...
JAVA: Already completed: MyList.java, MyAbstractList.java, MyArrayList.java, MyLinkedLink.java, MyStack.java, MyQueue.java. Need to complete: ReversePoem.java. This program has...
JAVA: Already completed: MyList.java, MyAbstractList.java, MyArrayList.java, MyLinkedLink.java, MyStack.java, MyQueue.java. Need to complete: ReversePoem.java. This program has you display a pessimistic poem from a list of phrases. Next, this program has you reverse the phrases to find another more optimistic poem. Use the following algorithm. 1. You are given a list of phrases each ending with a pound sign: ‘#’. 2. Create a single String object from this list. 3. Then, split the String of phrases into an array of phrases...
Please use Java programming: Modify both ArrayList and LinkedList classes and add the following method to...
Please use Java programming: Modify both ArrayList and LinkedList classes and add the following method to both classes: public void reverseThisList(), This method will reverse the lists. When testing the method: print out the original list, call the new method, then print out the list again ------------------------------------------------------------------------- //ARRAY LIST class: public class ArrayList<E> implements List<E> { /** Array of elements in this List. */ private E[] data; /** Number of elements currently in this List. */ private int size; /**...
Using a doubly linked list as the underlying data structure, implement a list ADT that implements...
Using a doubly linked list as the underlying data structure, implement a list ADT that implements the ListInterface.java found in the ProgProjTwo Eclipse project starting point for this assignment. In addition to the forward iterator defined by resetIterator( ) and getNextItem( ) in ListInterface.java, implement a backwards iterator by providing resetBackIterator( ) and getPreviousItem( ) methods. As noted in the syllabus addendum, you are encouraged to develop a find( ) helper method that can support various list ADT operations. A...
1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the...
1) Extend the Binary Search Tree ADT to include
a public method leafCount that returns the number of leaf nodes in
the tree.
2) Extend the Binary Search Tree ADT to include a
public method singleParent-Count that returns the number of nodes
in the tree that have only one child.
3) The Binary search tree ADT is extended to
include a boolean method similarTrees that receives references to
two binary trees and determines whether the shapes of the trees are...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements...
Java help: Please help complete the locate method that is in bold.. public class LinkedDoubleEndedList implements DoubleEndedList { private Node front; // first node in list private Node rear; // last node in list private int size; // number of elements in list ////////////////////////////////////////////////// // YOU MUST IMPLEMENT THE LOCATE METHOD BELOW // ////////////////////////////////////////////////// /** * Returns the position of the node containing the given value, where * the front node is at position zero and the rear node is...
1) Extend the Binary Search Tree ADT to include
a public method leafCount that returns the number of leaf nodes in
the tree.
2) Extend the Binary Search Tree ADT to include a
public method singleParent-Count that returns the number of nodes
in the tree that have only one child.
3) The Binary search tree ADT is extended to
include a boolean method similarTrees that receives references to
two binary trees and determines whether the shapes of the trees are...
Most questions answered within 3 hours.
-
How many liters of 0.669 M KOH will be needed to raise the pH of
0.339...
asked 2 hours ago -
A liquid of density 1270 kg/m 3 flows steadily through a pipe of
varying diameter and...
asked 2 hours ago -
Questions: What should the American executive do?
'A visiting American executive finds that a foreign subsidiary...
asked 2 hours ago -
Activity based costing was introduced as an alternative to
absorption costing.
1. Discuss using illustration the...
asked 2 hours ago -
1. You own shares of Crane DVD Company and are interested in
selling them. With so...
asked 2 hours ago -
How many grams of He are necessary to fill a balloon having a
volume of 4.5E3...
asked 2 hours ago -
The 2 patients, still in the hospital, were interviewed by a
MoH epidemiologist. The interviews revealed...
asked 2 hours ago -
An uncharged capacitor and a resistor are connected in series to
a source of emf. If...
asked 2 hours ago -
If assets are $540,000 and liabilities are $236,000 what is the
amount of owner’s equity?
asked 2 hours ago -
MATH 3421 Maple Assignment 1 Due February 13, 2019 Maple is a
Computer Algebra System that...
asked 2 hours ago -
CODING IN JAVA
Dates are printed in several common formats. Two of the more
common formats...
asked 2 hours ago -
A hydrometer is a device used to measure the density of a
liquid. It is a...
asked 3 hours ago