JAVA The Bag ADT is an unordered collection that allows for multiple occurrences
ID: 3668593 • Letter: J
Question
JAVA
The Bag ADT is an unordered collection that allows for multiple occurrences of any item.
This interface is closely modeled on Frank Carrano's Bag interface in "Data Structures and Abstractions in Java" (3rd Edition)
Invariants:
if (isEmpty() == true)
then getCount() == 0
else getCount() > 0
if (contains(item) == true)
then getFrequencyOf(item) > 0
else getFrequencyOf(item) == 0
Creation constraints:
The constructor for any class the implements the Bag ADT must create an initially empty bag.
So, immediately after contruction,
isEmpty() == true
AND
getCount() == 0
/ interface BagWithCQS { /** * Adds the specified item to the bag *
* pre-condition: NOT isFull() *
* post-condition: * getFrequencyOf(item) == * getFrequencyOf(item)@pre + 1
* AND
* getCount() == getCount()@pre + 1
*
* @param item -- the item to be added to the bag * */ public void add(T item); /** * Returns the total number of items in the bag. * * @return number of items in the bag (counting duplicates) */ public int getCount(); /** Removes all items from the bag
pre-condition: none (true)
post-condition: getCount() == 0 */ public void clear(); /** * Removes one occurrence of the specified item from the * bag, if there is one *
* pre-condition: EXERCISE *
* post-condition:
EXERCISE * * @param item - the item to be removed */ public void remove(T item); /** * Removes an occurrence of an unspecified item from the * bag and returns it. Returns null if the bag is empty *
* pre-condition: EXERCISE *
* post-condition: EXERCISE * * @return removed item - note that this is a (minor) * violation of command query separation */ public T remove(); /** Checks whether the bag is empty
@return if getCount() == 0 true else false */ public boolean isEmpty(); /** Checks whether the bag is full (i.e., no item can be added), false otherwise
@return if bag is full then true else false */ public boolean isFull(); /** Checks whether the bag contains an occurrence of the specified item
@return if getFrequencyOf(item) > 0 then true else false */ public boolean contains (T item); /** Returns the number of occurrences of the specified item in the bag
@return the number of occurrences of item in the bag */ public int getFrequencyOf(T item); /** Returns an array of length getCount() containing the items in the bag. */ public T[] toArray(); } // interface Bag
Explanation / Answer
//Bag.java
import java.util.ArrayList;
public class Bag<T> {
ArrayList<T>bag;
int max;
public Bag()
{
bag=new ArrayList();
max=25;
}
/** Removes all items from the bag
/*
pre-condition: none (true)
post-condition: getCount() == 0 */
public void clear()
{
if(!isEmpty())
for(int i=0;i<bag.size();i++)
{
bag.remove(i);
}
}
/** * Removes one occurrence of the specified item from the * bag, if there is one *
* pre-condition: EXERCISE *
* post-condition:
EXERCISE * * @param item - the item to be removed */
public void remove(T item)
{ if(!isEmpty())
for(int i=0;i<bag.size();i++)
{
if(bag.get(i)==item)
{
bag.remove(i);
System.out.println(item+" is removed");
break;
}
}
}
/** * Removes an occurrence of an unspecified item from the * bag and returns it.
* Returns null if the bag is empty *
* pre-condition: EXERCISE *
* post-condition: EXERCISE * * @return removed item - n */
public T remove()
{
if(isEmpty())
return null;
else
{
return bag.remove(0);
}
}
/** Checks whether the bag is empty
@return if getCount() == 0 true else false */
public boolean isEmpty()
{
if(bag.size()==0) return true;
else
return false;
}
/** Checks whether the bag is full (i.e., no item can be added), false otherwise
@return if bag is full then true else false */
public boolean isFull()
{
if(bag.size()==max)
return true;
else
return false;
}
/** Checks whether the bag contains an occurrence of the specified item
@return if getFrequencyOf(item) > 0 then true else false */
public boolean contains (T item)
{
if(!isEmpty())
for(int i=0;i<bag.size();i++)
{
if(bag.get(i)==item)
{
return true;
}
}
return false;
}
/** Returns the number of occurrences of the specified item in the bag
@return the number of occurrences of item in the bag */
public int getFrequencyOf(T item)
{
int f=0;
if(!isEmpty())
for(int i=0;i<bag.size();i++)
{
if(bag.get(i)==item)
{
f++;
}
}
return f;
}
/** Returns an array of length getCount() containing the items in the bag. */
/** * Returns the total number of items in the bag.
* * @return number of items in the bag (counting duplicates) */
public int getCount()
{
return bag.size();
}
/** * Adds the specified item to the bag *
* pre-condition: NOT isFull() *
* post-condition: * getFrequencyOf(item) == * getFrequencyOf(item)@pre + 1
* AND
* getCount() == getCount()@pre + 1
*
* @param item -- the item to be added to the bag * */
public void add(T item)
{
if(!isFull())
{
bag.add(item);
}
}
public T[] toArray()
{
return (T[]) bag.toArray();
}
}
//////////////////////////////////////////////////////////////////
//BagCQS.java
public class BagCQS {
public static void main(String[] args) {
Bag <Integer> newBag=new Bag();
newBag.add(10);
newBag.add(2);
newBag.add(3);
newBag.add(2);
newBag.add(2);
newBag.add(2);
newBag.add(7);
newBag.add(3);
Integer[] arr = newBag.toArray();
System.out.println("Items in the bag are ");
for(int i=0;i<arr.length;i++)
{
System.out.print(" "+arr[i]);
}
System.out.print(" ");
System.out.println("Number of items in Bag: "+newBag.getCount());
System.out.println("Frequency of 2: "+newBag.getFrequencyOf(2));
if(newBag.contains(7))
System.out.println("Bag contains 7");
else
System.out.println("Bag doesn't contain 7");
newBag.remove(3);
int r=newBag.remove();
System.out.println("removed element "+r);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.