Question

Create MySortedArrayCollection.java

• This file is inherited from SortedArrayCollection.java
• This file implements MySortedArrayCollectionInterface.java

****** Make new and just complete MySortedArrayCollection.java, dont modify others

////////////////////////////////////////////////////////

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;
   }
}
///////////////////////////////////////////////////////

MySortedArrayCollectionInterface.java

public interface MySortedArrayCollectionInterface<T> extends CollectionInterface<T> {
   public String toString();
   // Creates and returns a string that correctly represents the current
   // collection.
   // 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.

   public T smallest();
   // Returns null if the collection is empty, otherwise returns the smallest
   // element of the collection.

   public int greater(T element);
   // Returns a count of the number of elements e in the collection that are
   // greater then element, that is such that e.compareTo(element) is > 0

   public MySortedArrayCollection<T> combine(MySortedArrayCollection<T> other);
   // Creates and returns a new SortedArrayCollection object that is a combination
   // of this object and the argument object.

   public T[] toArray();
   // Returns an array containing all of the elements of the collection.

   public void clear();
   // Removes all elements.

   public boolean equals(Object o);
   // Takes an Object argument, returning true if it is equal to the current
   // collection and false otherwise

   public boolean addAll(MySortedArrayCollection<T> c);
   // Takes a MySortedArrayCollection argument and adds its contents to the current
   // collection;
   // returns a boolean indicating success or failure.

   public boolean retainAll(MySortedArrayCollection<T> c);
   // Takes a MySortedArrayCollection argument and removes any elements from the
   // current collection that are not in the argument collection; returns a boolean
   // indicating success or failure.

   public void removeAll(MySortedArrayCollection<T> c);
   // Takes a MySortedArrayCollection argument and removes any elements from the
   // current collection that are also in the argument collection.
}

//////////////////////////////////////////////

CollectionInterface.java

public interface CollectionInterface<T> {
   boolean add(T element);
   // Attempts to add element to this collection.
   // Returns true if successful, false otherwise.

   T get(T target);
   // Returns an element e from this collection such that e.equals(target).
   // If no such e exists, returns null.

   boolean contains(T target);
   // Returns true if this collection contains an element e such that
   // e.equals(target); otherwise returns false.

   boolean remove(T target);
   // Removes an element e from this collection such that e.equals(target)
   // and returns true. If no such e exists, returns false.

   boolean isFull();
   // Returns true if this collection is full; otherwise, returns false.

   boolean isEmpty();
   // Returns true if this collection is empty; otherwise, returns false.

   int size();
   // Returns the number of elements in this collection.
}

Answer 1

MySortedArrayCollection.java

public class MySortedArrayCollection<T extends Comparable<T>> extends SortedArrayCollection<T> implements MySortedArrayCollectionInterface<T> {

        // Creates and returns a string that correctly represents the current
        // collection.
        public String toString() {
                T elements[] = this.toArray();
                String k = "[ ";
                k = k + elements[0];
                for (int i=1; i<elements.length; i++) {
                        k = k + ", " + elements[i];
                }
                k=k+"]";
                return k;
        }
        
        // Returns null if the collection is empty, otherwise returns the smallest
        // element of the collection.
        public T smallest() {
                if(this.isEmpty())
                        return null;
                T elements[] = this.toArray();
                T small=elements[0];
                for(int i=1;i<this.size();i++)
                {
                        if(elements[i].compareTo(small)<0)
                        {
                                small=elements[i];
                        }
                }
                return small;
        }

        // Returns a count of the number of elements e in the collection that are
        // greater then element, that is such that e.compareTo(element) is > 0
        public int greater(T element) {
                int count=0;
                if(this.isEmpty())
                        return 0;
                T elements[] = this.toArray();
                for (int i=0; i<this.size(); i++) {
                        if (elements[i].compareTo(element)>0) {
                                count++;
                        }
                }
                return count;
                
        }

        // Creates and returns a new SortedArrayCollection object that is a combination
        // of this object and the argument object.
        public MySortedArrayCollection<T> combine(MySortedArrayCollection<T> other) {
                T[] a=this.toArray();
                T[] b=other.toArray();
                MySortedArrayCollection<T> k = new MySortedArrayCollection<T>();
                for (int i=0; i<a.length; i++) {
                        k.add(a[i]);
                }
                for (int i=0; i<b.length; i++) {
                        k.add(b[i]);
                }
                return k;
        }

        // Returns an array containing all of the elements of the collection.
        public T[] toArray() {
                return elements;
        }

        // Removes all elements.
        public void clear()
        {
                T elements[] = this.toArray();
                for(int i=this.size()-1; i>=0;i--)
                {
                        this.remove(elements[i]);
                }
        }

        // Takes an Object argument, returning true if it is equal to the current
        // collection and false otherwise
        public boolean equals(Object o) {
                return (this.equals(o));
        }

        // Takes a MySortedArrayCollection argument and adds its contents to the current
        // collection;
        // returns a boolean indicating success or failure.
        public boolean addAll(MySortedArrayCollection<T> c) {
                T arr[] = c.toArray();
                for (int i=0; i<arr.length; i++) {
                        if(!this.add(arr[i]))
                                return false;
                }
                return true;
        }

        // Takes a MySortedArrayCollection argument and removes any elements from the
        // current collection that are not in the argument collection; returns a boolean
        // indicating success or failure.
        public boolean retainAll(MySortedArrayCollection<T> c) {
                T arr[] = c.toArray();
                for (int i=0; i<arr.length; i++) {
                        if (!this.contains(arr[i])) {
                                if (!this.remove(arr[i])) {
                                        return false;
                                }
                        }
                }
                return true;
        }

        // Takes a MySortedArrayCollection argument and removes any elements from the
        // current collection that are also in the argument collection.
        public void removeAll(MySortedArrayCollection<T> c) {
                for(int i=0;i<c.size();i++)
                {
                        this.remove(elements[i]);
                }
        }
}

MySortedArrayCollectionInterface.java

public interface MySortedArrayCollectionInterface<T extends Comparable<T>> extends CollectionInterface<T> {
   public String toString();
   // Creates and returns a string that correctly represents the current
   // collection.
   // 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.

   public T smallest();
   // Returns null if the collection is empty, otherwise returns the smallest
   // element of the collection.

   public int greater(T element);
   // Returns a count of the number of elements e in the collection that are
   // greater then element, that is such that e.compareTo(element) is > 0

   public MySortedArrayCollection<T> combine(MySortedArrayCollection<T> other);
   // Creates and returns a new SortedArrayCollection object that is a combination
   // of this object and the argument object.

   public T[] toArray();
   // Returns an array containing all of the elements of the collection.

   public void clear();
   // Removes all elements.

   public boolean equals(Object o);
   // Takes an Object argument, returning true if it is equal to the current
   // collection and false otherwise

   public boolean addAll(MySortedArrayCollection<T> c);
   // Takes a MySortedArrayCollection argument and adds its contents to the current
   // collection;
   // returns a boolean indicating success or failure.

   public boolean retainAll(MySortedArrayCollection<T> c);
   // Takes a MySortedArrayCollection argument and removes any elements from the
   // current collection that are not in the argument collection; returns a boolean
   // indicating success or failure.

   public void removeAll(MySortedArrayCollection<T> c);
   // Takes a MySortedArrayCollection argument and removes any elements from the
   // current collection that are also in the argument collection.
}