ArraySet

ArraySet.java

package arrayset;

import java.util.ArrayList;
import java.util.*;

import static java.util.Arrays.*;

/**
 * java ArraySet
 * <p/>
 * sorted-array optimized Set.
 * <p/>
 * creates a set assumed to be sorted, backed by an array.
 * <p/>
 * uses {@link mmapgeo.ArraySet#getOperationList } to provide a scratch ArrayList to perform mutations on.
 * <p/>
 * when {@link mmapgeo.ArraySet#sync}   is called the operationList is sorted,
 * and the backing array is replaced from it.
 * <p/>
 * solves the case where CopyOnWriteArraySet mutations are too expensive but an array-backed set is desired.
 */
public class ArraySet<T> implements SortedSet<T> {
    T[] arr;
    private ArrayList<T> operationList;
    private Comparator<? super T> comparator;

    public ArraySet(T... sortedArr) {
        this.arr = sortedArr;
    }

    @Override
    public int size() {
        return arr.length;
    }

    @Override
    public boolean isEmpty() {
        return 0 == arr.length;  //To change body of implemented methods use File | Settings | File Templates.
    }

    @Override
    public boolean contains(Object key) {
        return 0 <= binarySearch(arr, key);
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            public int i = 0;

            @Override
            public boolean hasNext() {
                return i <  arr.length;  //To change body of implemented methods use File | Settings | File Templates.
            }

            @Override
            public T next() {
                return arr[i++];  //To change body of implemented methods use File | Settings | File Templates.
            }

            @Override
            public void remove() {
                //To change body of implemented methods use File | Settings | File Templates.
            }
        };
    }

    @Override
    public T[] toArray() {
        return arr;  //To change body of implemented methods use File | Settings | File Templates.
    }

    @Override
    public <T1> T1[] toArray(T1[] a) {
        return Arrays.copyOf(arr, arr.length, (Class<? extends T1[]>) a.getClass());  //To change body of implemented methods use File | Settings | File Templates.
    }

    @Override
    public boolean add(T t) {

        return getOperationList().add(t);
    }

    @Override
    public boolean remove(Object o) {
        return getOperationList().remove(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Iterator<?> iterator = c.iterator(); iterator.hasNext(); ) {
            Object o = iterator.next();
            if (!contains(o))
                return false;
        }
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        return operationList.addAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        clear();
        for (Iterator<?> iterator = c.iterator(); iterator.hasNext(); ) {
            Object o = iterator.next();
            if (contains(o)) operationList.add((T) o);
        }
        return operationList.size() != arr.length;
    }

    @Override
    public boolean removeAll(Collection<?> c) {

        return getOperationList().removeAll(c);
    }

    @Override
    public void clear() {
        setOperationList(new ArrayList<T>());

    }

    public ArrayList<T> getOperationList() {
        return operationList == null ? operationList = new ArrayList<T>(Arrays.asList(arr)) : operationList;
    }

    public void setOperationList(ArrayList<T> operationList) {
        this.operationList = operationList;
    }

    /**
     * sorts operationalList then pushes the operatoinalList current contents to arr
     */
    public ArraySet<T> sync() {
        Collections.sort(getOperationList(),getComparator());
        final T[] ts = getOperationList().toArray(copyOf(arr, getOperationList().size()));
        arr = ts;
        return this;
    }

    @Override
    public Comparator<? super T> comparator() {
        return getComparator();  //To change body of implemented methods use File | Settings | File Templates.
    }

    @Override
    public SortedSet<T> subSet(T fromElement, T toElement) {
        return new ArraySet<T>(copyOfRange(arr, binarySearch(arr, fromElement, getComparator()), binarySearch(arr, toElement, getComparator())));
    }

    @Override
    public SortedSet<T> headSet(T toElement) {
        return new ArraySet<T>(copyOf(arr, binarySearch(arr, toElement, getComparator())));
    }

    @Override
    public SortedSet<T> tailSet(T fromElement) {
        return new ArraySet<T>(copyOfRange(arr, binarySearch(arr, fromElement, getComparator()), arr.length));
    }

    @Override
    public T first() {
        return arr[0];
    }

    @Override
    public T last() {
        return arr[arr.length - 1];
    }

    public Comparator<? super T> getComparator() {
        return comparator;
    }

    public ArraySet<T> setComparator(Comparator<? super T> comparator) {
        this.comparator = comparator;
        return this;
    }
}