In: Computer Science
complete the public T removeRandom(), public SetADT<T> union(SetADT<T> set), and the incomplete part in the arraysettester
arrayset.java
package arraysetpackage;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;
public class ArraySet<T> implements SetADT<T>
{
private static final int DEFAULT_SIZE = 20;
private int count;
private T[] setValues;
private Random rand;
public ArraySet (){
this(DEFAULT_SIZE);
} // end of constructor
public ArraySet (int size){
count = 0;
setValues = (T[]) new
Object[size];
rand = new Random();
} // end of constructor
public void add(T element) {
if (contains(element))
return;
if (count == setValues.length)
{
T[] temp = (T[])
new Object[setValues.length*2];
for (int i = 0;
i < setValues.length; i++) {
temp[i] = setValues[i];
}
setValues =
temp;
}
setValues[count] = element;
count++;
}
public void addAll(SetADT<T> set) {
Iterator<T> iter =
set.iterator();
while (iter.hasNext()){
System.out.println(iter.next());
}
// finish: this method adds all of
the input sets elements to this array
}
public boolean contains(T target) {
for (int i = 0; i < count; i++
)
if
(setValues[i].equals(target))
return true;
return false;
}
public String toString () {
String toReturn = "[";
for (int i = 0; i < count; i++)
{
toReturn +=
setValues[i] + " ";
}
toReturn +="]";
return toReturn;
}
public boolean equals(SetADT<T> set) {
// finish: tests to see if this set
and the input set have exactly the same
// elements
return false; // this is just
generic, you need to change the return
}
public boolean isEmpty() {
return count==0;
}
public Iterator<T> iterator() {
return new
ArraySetIterator<T>(setValues,count);
}
public T remove(T element) {
for (int i = 0; i < count; i++ )
{
if
(setValues[i].equals(element)) {
T toReturn = setValues[i];
setValues[i] = setValues[count-1];
count--;
return toReturn;
}
}
throw new
NoSuchElementException("not present");
}
public T removeRandom() {
// finish: remove and return a
random element. you will use the
// local rand object
return null; // this is just
generic, you need to change the return
}
public int size() {
return count;
}
public SetADT<T> union(SetADT<T> set)
{
// finish: a new set is created and
returned. This new set will
// contain all of elements from
this set and the input parameter set
return null; // this is just
generic, you need to change the return
}
}
arraysetester.java:
package arraysetpackage;
import java.util.Iterator;
public class ArraySetTester {
public static void main(String[] args) {
SetADT <String> mySet = new
ArraySet<String>();
for (int i = 0; i < 12;
i++)
mySet.add(new
String("apple"+i));
System.out.println(mySet);
System.out.println("mysize =
"+mySet.size()+ " [expect 12]");
mySet.add(new String
("apple0"));
System.out.println("mysize =
"+mySet.size()+ " [expect 12]");
System.out.println("contains 11? =
"+mySet.contains(new String("11")));
System.out.println("contains
apple11? = "+mySet.contains(new String("apple11")));
try {
String
removedItem = mySet.remove("apple7");
System.out.println(mySet);
System.out.println(removedItem+ " was removed");
} catch (Exception e) {
System.out.println("item not found, can't remove");
}
try {
String
removedItem = mySet.remove("apple17");
System.out.println(mySet);
System.out.println(removedItem+ " was removed");
} catch (Exception e) {
System.out.println("item not found, can't remove");
}
Iterator<String> iter =
mySet.iterator();
while (iter.hasNext()){
System.out.println(iter.next());
}
SetADT <String> mySet2 = new ArraySet<String>();
for (int i = 0; i < 12;
i++)
mySet2.add(new
String("orange"+i));
System.out.println(mySet2);
// add code here to test methods
you finish in ArraySet
// after you complete the existing
methods, do the Case Study
// Approach 1 will be here in the
main
// Approach 2 will be here in
ArraySetTester, but you will
// create a local static method
that you will call from the main
// Approach 3 will start with
uncommenting the prototype in SetADT
// and then creating the method in
ArraySet. Finally you will write
// code here to test the new
method
}
}
arraysetiterator.java
package arraysetpackage;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class ArraySetIterator <T> implements Iterator
<T> {
private int position; //Always points to the next
value
private T [] values;
private int count;
public ArraySetIterator (T [] theValues, int aCount)
{
position = 0;
values = theValues;
count = aCount;
}
public boolean hasNext() {
return position < count;
}
public T next() {
if (position >= count)
throw new
NoSuchElementException("Past " + count + " elements");
position++;
return values[position - 1];
}
public void remove() {
throw new
UnsupportedOperationException("No
remove for ArraySet");
}
}
setadt.java
package arraysetpackage;
import java.util.Iterator;
public interface SetADT<T> {
public void add (T element); //Adds one element to
this set, ignoring duplicates
public void addAll (SetADT<T> set); //Adds all
elements in the parameter to this set,
// ignoring duplicates
public T removeRandom (); //Removes and returns a
random element from this set
public T remove (T element); //Removes and returns the
specified element from this set
public SetADT<T> union (SetADT<T> set);
//Returns the union of this set and the
// parameter
public boolean contains (T target); //Returns true if
this set contains the parameter
//public boolean contains(SetADT<T> Set); //
Returns true if this set contains the parameter
public boolean equals (SetADT<T> set); //Returns
true if this set and the parameter
//contain exactly same elements
public boolean isEmpty(); //Returns true if this set
contains no elements
public int size(); //Returns the number of elements in
this set
public Iterator<T> iterator(); //Returns an
iterator for the elements in this set
public String toString(); //Returns a string
representation of this set
}
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks
// ArraySet.java
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;
public class ArraySet<T> implements SetADT<T> {
private static final int DEFAULT_SIZE = 20;
private int count;
private T[] setValues;
private Random rand;
public ArraySet() {
this(DEFAULT_SIZE);
} // end of constructor
public ArraySet(int size) {
count = 0;
setValues = (T[]) new Object[size];
rand = new Random();
} // end of constructor
public void add(T element) {
if (contains(element))
return;
if (count == setValues.length) {
T[] temp = (T[]) new Object[setValues.length * 2];
for (int i = 0; i < setValues.length; i++) {
temp[i] = setValues[i];
}
setValues = temp;
}
setValues[count] = element;
count++;
}
public void addAll(SetADT<T> set) {
Iterator<T> iter = set.iterator();
while (iter.hasNext()) {
T item = iter.next();
// adding item to set, add method will check for duplicates before
// adding, so we dont need to worry about that
add(item);
}
// finished
}
public boolean contains(T target) {
for (int i = 0; i < count; i++)
if (setValues[i].equals(target))
return true;
return false;
}
public String toString() {
String toReturn = "[";
for (int i = 0; i < count; i++) {
toReturn += setValues[i] + " ";
}
toReturn += "]";
return toReturn;
}
public boolean equals(SetADT<T> set) {// finished
if (this.size() == set.size()) {
// same size
Iterator<T> iter = set.iterator();
// checking if all elements of set present on this set
while (iter.hasNext()) {
T item = iter.next();
if (!contains(item)) {
// item is not present on this set, so not equal
return false;
}
}
// all elements are same (can be in different order)
return true;
}
// not equal
return false;
}
public boolean isEmpty() {
return count == 0;
}
public Iterator<T> iterator() {
return new ArraySetIterator<T>(setValues, count);
}
public T remove(T element) {
for (int i = 0; i < count; i++) {
if (setValues[i].equals(element)) {
T toReturn = setValues[i];
setValues[i] = setValues[count - 1];
count--;
return toReturn;
}
}
throw new NoSuchElementException("not present");
}
public T removeRandom() {// finished
// making sure that the set is not empty
if (count > 0) {
// generating a random index
int randIndex = rand.nextInt(count);
// getting element at selected index
T itemToRemove = setValues[randIndex];
// removing the random item using remove() method
remove(itemToRemove);
// returning removed item
return itemToRemove;
}
return null; //empty set
}
public int size() {
return count;
}
public SetADT<T> union(SetADT<T> set) {// finished
// creating a new SetADT object
SetADT<T> newSet = new ArraySet<T>(count + set.size());
// adding all elements of this set
newSet.addAll(this);
// adding all elements of other set (not allowing duplicates)
newSet.addAll(set);
return newSet;
}
}
// ArraySetTester.java
import java.util.Iterator;
public class ArraySetTester {
public static void main(String[] args) {
SetADT<String> mySet = new ArraySet<String>();
for (int i = 0; i < 12; i++)
mySet.add(new String("apple" + i));
System.out.println(mySet);
System.out.println("mysize = " + mySet.size() + " [expect 12]");
mySet.add(new String("apple0"));
System.out.println("mysize = " + mySet.size() + " [expect 12]");
System.out
.println("contains 11? = " + mySet.contains(new String("11")));
System.out.println("contains apple11? = "
+ mySet.contains(new String("apple11")));
try {
String removedItem = mySet.remove("apple7");
System.out.println(mySet);
System.out.println(removedItem + " was removed");
} catch (Exception e) {
System.out.println("item not found, can't remove");
}
try {
String removedItem = mySet.remove("apple17");
System.out.println(mySet);
System.out.println(removedItem + " was removed");
} catch (Exception e) {
System.out.println("item not found, can't remove");
}
Iterator<String> iter = mySet.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
SetADT<String> mySet2 = new ArraySet<String>();
for (int i = 0; i < 12; i++)
mySet2.add(new String("orange" + i));
System.out.println(mySet2);
// code to test new methods finished in ArraySet
//finding and displaying union
SetADT<String> union = mySet.union(mySet2);
System.out.println("Union of mySet and mySet2:");
iter = union.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}
//storing size
int size = mySet2.size();
//removing a random element, displaying removed value
String str = mySet2.removeRandom();
System.out.println("Random element " + str + " is removed from mySet2");
//displaying the size and expected size of set (should be size-1)
System.out.println("Current size of mySet2: " + mySet2.size()
+ ", [expect: " + (size - 1)+"]");
//ensuring that deleted element is no longer present
System.out.println("MySet2 contains " + str + "? "
+ mySet2.contains(str));
//testing equals method
System.out.println("mySet equals mySet2: " + mySet.equals(mySet2));
System.out.println("mySet equals mySet: " + mySet.equals(mySet));
}
}
/*OUTPUT*/
[apple0 apple1 apple2 apple3 apple4 apple5 apple6 apple7 apple8 apple9 apple10 apple11 ]
mysize = 12 [expect 12]
mysize = 12 [expect 12]
contains 11? = false
contains apple11? = true
[apple0 apple1 apple2 apple3 apple4 apple5 apple6 apple11 apple8 apple9 apple10 ]
apple7 was removed
item not found, can't remove
apple0
apple1
apple2
apple3
apple4
apple5
apple6
apple11
apple8
apple9
apple10
[orange0 orange1 orange2 orange3 orange4 orange5 orange6 orange7 orange8 orange9 orange10 orange11 ]
Union of mySet and mySet2:
apple0
apple1
apple2
apple3
apple4
apple5
apple6
apple11
apple8
apple9
apple10
orange0
orange1
orange2
orange3
orange4
orange5
orange6
orange7
orange8
orange9
orange10
orange11
Random element orange6 is removed from mySet2
Current size of mySet2: 11, [expect: 11]
MySet2 contains orange6? false
mySet equals mySet2: false
mySet equals mySet: true