import structure5.*; import java.util.Iterator; public class OrderedVector> extends AbstractStructure implements OrderedStructure { protected Vector v; public OrderedVector() { v = new Vector(); } public Iterator iterator() { return v.iterator(); } protected int locate(T value) { return searchHelper(value, 0, v.size() - 1); } private int searchHelper(T elem, int lo, int hi) { // base case #1: not found if (lo > hi) { return lo; } // calculate the midpoint int mid = (hi - lo) / 2 + lo; // is the midpoint the element we are looking for? int cmp = elem.compareTo(v.get(mid)); // base case #2: found if (cmp == 0) { return mid; // recursive case #1: elem is to the left of mid } else if (cmp < 0) { return searchHelper(elem, lo, mid - 1); // recursive case #2: elem is to the right of mid } else { return searchHelper(elem, mid + 1, hi); } } public void add(T value) { int pos = locate(value); v.add(pos, value); } /** * Check that structure contains value. * pre: value is not null. * post: returns true iff structure contains value. */ public boolean contains(T value) { int pos = locate(value); return (pos < size()) && v.get(pos).equals(value); } /** * Removes value. * pre: value is not null and Vector actually contains v. * post: removes instance of a value, leaving Vector v in order. */ public T remove(T value) { if (contains(value)) { int pos = locate(value); T found = v.get(pos); v.remove(pos); return found; } return null; } /** * Returns the size of the structure. */ public int size() { return v.size(); } /** * Clears the vector. */ public void clear() { v.clear(); } /** * Returns the element at the given index. */ public T get(int index) { return v.get(index); } public String toString() { return v.toString(); } }