import java.util.*;

/**
 * A class representing an array which automatically
 * sorts itself as needed for efficient lookup of elements.
 * It is intended to be used in situations where there
 * are a series of additions (with no lookups) followed
 * by many lookups (with no additions).  
 * It implements Collection as it is neither a true
 * List nor a Set (it allows duplicates, and in that
 * sense is like a multiset).  The additional requirement
 * it adds to Collection is that its elements must be
 * comparable, and that the compare operation be
 * compatible with equals() to maintain substitutability
 * with Collection.  
 *
 * The comparison operation is by default implemented
 * by Comparable.compareTo, but can be implemented by
 * a user-provided Comparator object instead.  If
 * no Comparator object is provided, the objects passed
 * to add() must implement Comparable.  If one of these
 * two conditions is true, this documentation calls
 * the objects "comparable".
 *
 * Operations which depend on element ordering run in
 * O(n log n) worst case time, but O(log n) time if 
 * the collection is already sorted. 
 *
 * Methods without comments are identical to the Collection
 * interface specification, but with the above restrictions.
 */
public class LazyColl extends AbstractCollection {
    private boolean _isSorted = true;  // Tracks current sort status
    private ArrayList _array = new ArrayList(); // Stores objects
    // Class invariant: _isSorted implies _array is sorted
    private Comparator _cmp = null; // Optional comparator
    
    public LazyColl() {}

    public LazyColl(Collection other) {
        _isSorted = false;
        _array = new ArrayList(other);
        // Arguably, we should copy the other's comparator
        // object if available... this raises some thorny
        // issues.
    }
    
    public LazyColl(Comparator cmp) {
        _cmp = cmp;
    }
    
    public LazyColl(Collection other, Comparator cmp) {
        _cmp = cmp;
        _isSorted = false;
        _array = new ArrayList(other);
    }
    
    public int size() {
        return _array.size();
    }

    /**
     * Adds an element to the collection.
     * Runs in O(log n) time.
     * @param o Element to add (must be comparable)
     * @return true to indicate the collection was modified,
     *         false otherwise.
     */
    public boolean add(Object o) {
        _isSorted = false;
        return _array.add(o);
    }

    /**
     * Tells if collection contains an object equivalent
     * to the given one. 
     * @param o Element to search for (must be comparable)
     */
    public boolean contains(Object o) {
        return (find(o) != null);
    }

    /**
     * Returns an iterator to the contained elements.
     * Elements are always in sorted order.
     */
    public Iterator iterator() {
        ensureSorted();
        return _array.iterator();
    }

    /**
     * Removes an object equivalent to the given one. 
     * @param o Element to search for (must be comparable)
     */
    public boolean remove(Object o) {
        ensureSorted();
        int idx = binarySearch(o);
        if (idx>=0)
            _array.remove(idx);
        return (idx>=0);
    }

    /**
     * Finds match (in Comparable sense) for the
     * given object; returns matching object or
     * null if not found.
     * @param o Object (must be comparable)
     * @return The found object or null if no match found
     */
    public Object find(Object o) {
        ensureSorted();
        int idx = binarySearch(o);
        if (idx >= 0)
            return _array.get(idx);
        else
            return null;
    }

    /**
     * <p>Searches for given object, returning its index
     * or -(insert_index+1) if not found.</p>
     * <p>Requires that _array be sorted.</p>
     * @param o Object (must be comparable) 
     * @return index of found object, or -(ins_index+1) if not found
     */
    private int binarySearch(Object o) {
        return Collections.binarySearch(_array,o,_cmp);       
    }

    /**
     * Ensures that the array is sorted; if not sorted,
     * sorts it, but if already sorted this is a no-op.
     */
    private void ensureSorted() {
        if (!_isSorted) {
            Collections.sort(_array,_cmp);
            _isSorted = true;
        }
    }

    /**
     * Checks invariants for the class; throws exception
     * if they are violated.
     */
    public void checkOK() {
        if (_isSorted) {
            Iterator i = _array.iterator();
            Object last = null;
            while (i.hasNext()) {
                Object obj = i.next();
                if (last != null) {
                    int result = 0;
                    if (_cmp!=null)
                       result = _cmp.compare(last,obj);
                    else {
                       result = ((Comparable)last).compareTo(obj);
                    }
                    if (result > 0)
                        throw new RuntimeException("Not sorted: "+last+" > "+obj);
                }
                last = obj;
            }
        }
    }
    
    /**
     * Does tests for a LazyColl collection of String objects.
     * @param c LazyColl to test
     * @throws RuntimeException If a test fails.
     */
    private static void stringTests(LazyColl c) {      
        c.checkOK();
        assertTrue(c.isEmpty());
        assertTrue(c.add("Sneezy"));
        c.checkOK();
        assertTrue(c.add("Dopey"));
        assertTrue(c.add("Grumpy"));
        assertTrue(!c.isEmpty());
        Iterator i = c.iterator();
        c.checkOK();
        assertTrue(i.hasNext());
        assertTrue(c.size()==3);
        assertTrue(c.remove("Dopey"));
        c.checkOK();
        assertTrue(c.size()==2);
        assertTrue(c.contains("Grumpy"));
    }

    /**
     * Does tests for a LazyColl collection of Integer objects.
     * @param c LazyColl to test
     * @throws RuntimeException If a test fails.
     */
    private static void basicTests(LazyColl c) {
        ArrayList testData = new ArrayList();
        testData.add(new Integer(50));
        testData.add(new Integer(48));
        testData.add(new Integer(55));
        testData.add(new Integer(54));
       
        c.checkOK();
        assertTrue(c.isEmpty());
        assertTrue(c.add(new Integer(5)));
        c.checkOK();
        assertTrue(c.add(new Integer(3)));
        assertTrue(c.add(new Integer(4)));
        assertTrue(!c.isEmpty());
        Iterator i = c.iterator();
        c.checkOK();
        assertTrue(i.hasNext());
        assertTrue(c.size()==3);
        assertTrue(c.remove(new Integer(4)));
        c.checkOK();
        assertTrue(c.size()==2);
        assertTrue(c.contains(new Integer(5))); // was typo

        LazyColl c2 = new LazyColl(testData);
        c2.checkOK();
        c2.addAll(testData);
        assertTrue(c2.size() == 2*testData.size());
        assertTrue(c2.remove(new Integer(54)));
        assertTrue(c2.contains(new Integer(55)));
        c2.checkOK();
        c2.removeAll(testData);
        assertTrue(c2.isEmpty());
    }
    
    static void nonComparableTests() {
        LazyColl c = new LazyColl(new Comparator() {
             public int compare(Object a, Object b) {
                return 0;
            }           
        });
        c.add(new Object());
        c.add(new Object());
        c.contains(new Object());
        c.checkOK();
    }

    /**
     * Checks condition and throws RuntimeException
     * if the assertion fails.
     * @throws RuntimeException On assertion failure.
     */
    private static void assertTrue(boolean cond) {
        if (!cond) {
            throw new RuntimeException("Assertion failed!");
        }
    }    
    
    /**
     * Unit tests for LazyColl.
     */
    public static void main(String[] args) {
        // Do basic tests with default compareTo():
        basicTests(new LazyColl());

        Comparator revCmp = new Comparator() {
            public int compare(Object a, Object b) {
                return - ((Comparable)a).compareTo(b);
            }
        };
        
        // Test with reverse of natural ordering via comparator:
        basicTests(new LazyColl(revCmp));
        
        // Test with String objects:
        stringTests(new LazyColl());
        
        // Reverse order for Strings:
        stringTests(new LazyColl(revCmp));
        
        // Test with non-Comparable objects:
        nonComparableTests();
        
        System.out.println("LazyColl unit tests: OK");
    }
}