public class ArraySet<T extends Comparable<T>>{ // A simple implementation of a
ID: 3832198 • Letter: P
Question
public class ArraySet<T extends Comparable<T>>{ // A simple implementation of a Set backed by an array. As a Set, // instances track *unique* items so that no duplicates occur. This // implementation should keep the underlying array sorted and use // binary search to quickly identify if items are present or absent to // maintain uniqueness. To maintain this, items that go into the set // must implement the Comparable interface so that they have a // compareTo(..) method and are compatible with library search and // sort methods. // // Good choices for private fields are an ArrayList which will manage // the underlying array size automatically. public ArraySet(); // Create an empty ArraySet public int size(); // Return the size of the set which is the number of unique items in // it. public List<T> asList(); // Return the contents of the set as a list. The return list does // not have to be distinct from the lists pointed to by internal // fields of the set (no deep copies need to be made). public boolean contains(T query); // Return true if the query item is present in the set and false // otherwise. This method should use binary search to efficiently // determine presence or absence. public boolean add(T item); // Ensure the specified item is present in the set. Maintain the // uniqueness of items in the set: do not add duplicates which // would be equal to one another. If the given item is added to // the set, return true. If the item is already present so that the // set does not change size, return false. Throw a RuntimeException // in the event a item is null: ArraySet does not support null // items. public T get(T query); // Retrieve an item in the set that is equal to the query item. If // no item in the set is equal to the query, return null. public String toString(); // Return a string representation of the set and its contents. The // string should be identical in format to Lists making use the // toString() method of a List field the easiest way to implement // this method. Examples: // // [1, 3, 5, 9, 20, 27] // ["A", "B", "F", "R", "V"] }
Explanation / Answer
import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
import java.util.Objects;
/**
*
* @author Sam
*/
public class ArraySet<T extends Comparable<T>>{
// A simple implementation of a Set backed by an array. As a Set,
// instances track *unique* items so that no duplicates occur. This
// implementation should keep the underlying array sorted and use
// binary search to quickly identify if items are present or absent to
// maintain uniqueness. To maintain this, items that go into the set
// must implement the Comparable interface so that they have a
// compareTo(..) method and are compatible with library search and
// sort methods.
//
// Good choices for private fields are an ArrayList which will manage
// the underlying array size automatically.
private T[] array;
private int size;
public ArraySet() {
// Create an empty ArraySet
array = (T[])(new Object[10]); //This is how we create generic array!!
size = 0;
}
public int size() {
// Return the size of the set which is the number of unique items in
// it.
return size; //just return the size or number of element in arraySet
}
public List<T> asList() {
// Return the contents of the set as a list. The return list does
// not have to be distinct from the lists pointed to by internal
// fields of the set (no deep copies need to be made).
ArrayList newList = new ArrayList<>(size()); //convert to ArrayList
for (int i = 0; i < size; i++)
newList.add(array[i]); //then add item to the new array list
return newList; //return the list
}
public boolean contains(T query) {
// Return true if the query item is present in the set and false
// otherwise. This method should use binary search to efficiently
// determine presence or absence.
for (T t: array)
if(t.compareTo(query) == 0) //if equal, item is found
return true; //so return true
return false; //if not found
}
public boolean add(T item) {
// Ensure the specified item is present in the set. Maintain the
// uniqueness of items in the set: do not add duplicates which
// would be equal to one another. If the given item is added to
// the set, return true. If the item is already present so that the
// set does not change size, return false. Throw a RuntimeException
// in the event a item is null: ArraySet does not support null
// items.
if (item == null)
throw new IllegalArgumentException("Item cannot be null"); //item is null
for (int i = 0; i < size; i++)
if (Objects.deepEquals(item, array[i])) //if same item is found
return false; //return false and dont add it to the arraySet
if (size == array.length) { // It the arraySet is full
T[] newArray = (T[])(new Object[size*2]); //double the size of array
System.arraycopy(array, 0, newArray, 0, size); //and copy the elemets
array = newArray;
}
array[size++] = item; //finally add elemt
return true;
}
public T get(T query) {
// Retrieve an item in the set that is equal to the query item. If
// no item in the set is equal to the query, return null.
for (int i = 0; i < size; i++)
if(array[i].compareTo(query) == 0)
return array[i];
return null;
}
public String toString() {
// Return a string representation of the set and its contents. The
// string should be identical in format to Lists making use the
// toString() method of a List field the easiest way to implement
// this method. Examples:
//
// [1, 3, 5, 9, 20, 27]
// ["A", "B", "F", "R", "V"]
return Arrays.toString(array);
}
}
Here you go champ. The code is ready for you. I have kept the code very simple and also commented the code wherever I felt necessary. If incase you face any trouble with the code, please feel free to comment below. I shall be gald to help you.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.