import java.util.*;
/**
* SortedArraySet - an implementation of Set
*
* The implementation uses an array to store the items.
* It keeps the items in order, determined by a comparator
* provided to the constructor
*
* It does not allow null as an element of a set.
* It is efficient for accessing items; it is slower to insert.
* When full it will create a new array of double the current size, and
* copy all the items over to the new array
*/
public class SortedArraySet < E > extends AbstractSet < E > {
// data fields
private static int INITIALCAPACITY = 10;
private int count = 0;
private E[] data;
private Comparator < E > comp; // the comparator
/** Constructs an empty SortedArraySet that will use the given comparator */
public SortedArraySet(Comparator < E > comp) {
data = (E[])new Object[INITIALCAPACITY];
this.comp = comp;
}
/** Constructs an SortedArraySet that will use the given comparator
* and initially contains all the items in the given collection (with
* duplicates removed)
*/
public SortedArraySet(Collection < E > col, Comparator < E > comp) {
// YOUR CODE HERE
removeDuplicates(); // the collection may have had duplicate values.
}
/** Returns true iff the collection is empty */
public boolean isEmpty() {
return count == 0;
}
/** Returns the number of elements in collection */
public int size() {
return count;
}
/** Returns true iff the set contains an item */
public boolean contains(Object item) {
int index = findIndex(item);
if (index >= 0 && data[index] != null)
return true;
return false;
// YOUR CODE HERE
}
/** Adds the specified element to this set if it is not already present
* Returns true if the collection changes, and false if it did not change.
*/
public boolean add(E item) {
int index = findIndex(item); // where item should be.
System.out.println("We got index: " + index);
if (index < 0 || index > count)
throw new IndexOutOfBoundsException();
if (item == null){
System.out.println("NULL!! not adding this piece of crud");
throw new NullPointerException();
}
// YOUR CODE HERE
//add - ensureCapacity. Then move all items along whilst adding the new item
// in first.
ensureCapacity();
if (data[index] == null) {//at the end of the array so just append to end and increment count
data[count] = item;
count++;
return true;
} else if (data[index].equals(item)){
return false;
} else {
for (int i=count; i> index; i--){
data[i]=data[i-1];
}
System.out.println("adding: " + item + " over " + data[index] + " count at: " + count);
data[index]=item;//insert value
count++;
return true;
}
/*
if (data[index] != null && data[index].equals(item)) {
System.out.println("Already exists");
return false;
}
else {
ensureCapacity();
for (int i = count-1; i == index; i--) { //move items along
System.out.println("Moving: " + data[i] + " over " + data[i+1]);
if (data[i+1] != null)
data[i + 1] = data[i];
}
System.out.println("adding: " + item + " over " + data[index] + " count at: " + count);
data[index] = item;
count++;
//increment count by 1
return true;
}
*/
}
/** Remove the element matching a given item
* Returns true if the collection changes, and false if it did not change.
*/
public boolean remove(Object item) {
if (item == null)
return false;
int index = findIndex(item);
// YOUR CODE HERE
System.out.println("Deleting " + data[index]);
for (int i = index; i < count-1; i++) {
data[i] = data[i+1];
}
count--; //decrement count by 1
return true;
}
/** Returns an iterator over the elements in this set. **/
public Iterator < E > iterator() {
return new SortedArraySetIterator < E > (this);
}
// SortedArraySet utility methods
/** Find the index of where an element is in the dataarray,
* (or where it ought to be, if it's not there).
* Assumes that the item is not null.
* Uses binary search and requires that the items are kept in order.
*/
private int findIndex(Object itm) {
//Comparable < E > temp = (Comparable < E > )itm;
E item = (E)itm;
Comparable < E > temp = (Comparable < E > )item;
int low = 0;
int high = count;
int mid = 0;
if (isEmpty()) return 0; //if the array is empty just return 0
if (low >=high) return low;
while (low < high){
mid=((low+high)/2);
if (temp.compareTo(data[mid]) == 0)
return mid;//this is it
else if (temp.compareTo(data[mid]) > 0)
low = mid+1;
else
high = mid;
}
//if we reach here we have not found the element we are looking for but this
// is where we want it so..
return low;
}
/** Ensure data array has sufficient number of elements
* to add a new element
*/
private void ensureCapacity() {
if (count < data.length)
return;
E[] newArray = (E[])new Object[data.length * 2];
for (int i = 0; i < count; i++)
newArray[i] = data[i];
data = newArray;
}
/** Removes any duplicate items in a single pass,
* Assumes that the data is sorted so that duplicates are adjacent
*/
private void removeDuplicates() {
int i = 0;
int j = 1; // j is always > i
while (j < count) {
if (data[i].equals(data[j])) // duplicate at j
j++; // so don't copy item at j, advance j, but leave i
else // not a duplicate,
data[++i] = data[j++];
// so shift item at j down and advance both i andj
}
count = i + 1;
}
private class SortedArraySetIterator < E > implements Iterator < E > {
private SortedArraySet < E > set;
private int nextIndex = 0;
private boolean canRemove = false;
private SortedArraySetIterator(SortedArraySet < E > s) {
set = s;
}
/** Return true if iterator has at least one more element */
public boolean hasNext() {
return (nextIndex < set.count);
}
/** return next element in the set */
public E next() {
if (nextIndex >= set.count)
throw new NoSuchElementException();
canRemove = true;
return set.data[nextIndex++];
}
/** Remove from the set the last element returned by the iterator.
* Can only be called once per call to next.
*/
public void remove() {
if (!canRemove)
throw new IllegalStateException();
canRemove = false;
nextIndex--;
set.count--;
for (int i = nextIndex + 1; i < set.count; i++)
data[i - 1] = data[i];
data[count] = null;
canRemove = false;
}
}
public static void main(String[] args) {
test();
}
// two comparators for the test method.
private static class StringComparator implements Comparator < String > {
public int compare(String str1, String str2) {
return (str1).compareTo(str2);
}
}
private static class ReverseStringComparator implements Comparator < String >
{
public int compare(String str1, String str2) {
return ( - str1.compareTo(str2));
}
}
public static void test() {
SortedArraySet < String > set = new SortedArraySet < String >
(new StringComparator());
System.out.format("\nCreating new, empty set:\n");
System.out.format(" Size: %d, isEmpty: %b, Set: %s\n", set.size(),
set.isEmpty(), set);
System.out.format("\nChecking add:\n");
String[] array1 = {
"A", "P", "F", "R", "E", "W", "Q", "T", "Z", "X", "C", "V", "B", "G",
"I", "H", "M", "S", "K", "U", "N"
}
;
for (String s: array1){
System.out.println("Set size: " +set.size());
set.add(s);
}
System.out.format(" Size: %d, isEmpty: %b, Set: %s\n", set.size(),
set.isEmpty(), set);
System.out.format("\nChecking contains:\n");
for (String st: array1)
System.out.print(set.contains(st)? " OK": " FAIL");
System.out.format("\n Contains(D)=%s\n", set.contains("D"));
System.out.format("\nAdding A, Z, and P again\n");
set.add("A");
set.add("Z");
set.add("P");
System.out.format(" Size: %d, isEmpty: %b, Set: %s\n", set.size(),
set.isEmpty(), set);
System.out.format("\nRemoving A, Z, and P\n");
set.remove("A");
System.out.println(" now contains(A)=" + set.contains("A"));
set.remove("Z");
System.out.println(" now contains(Z)=" + set.contains("Z"));
set.remove("P");
System.out.println(" now contains(P)=" + set.contains("P"));
System.out.format(" Size: %d, isEmpty: %b, Set: %s\n", set.size(),
set.isEmpty(), set);
System.out.format("\nChecking alternative constructors\n");
List < String > list = new ArrayList < String > ();
String[] array2 = {
"a", "p", "f", "r", "e", "w", "q", "q", "t", "z", "x", "c", "v", "b",
"a", "z"
}
;
for (String s: array2)
list.add(s);
SortedArraySet < String > set2 = new SortedArraySet < String >
(list, new StringComparator());
System.out.format(" Set(list): %s\n", set2);
for (String s: list)
if (!set2.contains(s))
System.out.format(" Fail contains: %s\n", s);
//check with a reversed String comparator.
SortedArraySet < String > set3 = new SortedArraySet < String >
(new ReverseStringComparator());
for (String s: list)
set3.add(s);
System.out.format(" Set(reverse): %s\n", set3);
for (String s: list)
if (!set3.contains(s))
System.out.format(" Fail contains: %s\n", s);
SortedArraySet < String > set4 = new SortedArraySet < String >
(list, new ReverseStringComparator());
System.out.format(" Set(list,reverse): %s\n", set4);
for (String s: list)
if (!set4.contains(s))
System.out.format(" Fail contains: %s\n", s);
}
}