// Sorted Bag
// inherits most of Collection functionality from AbstractCollection
// Implementation: most of elements in sorted order, recently added
// elements unsorted.
// Sort whole array when necessary
// remove just mark elements null


import java.lang.Math;
import java.util.Arrays;
import java.util.Collection;
import java.util.AbstractCollection;
import java.util.Iterator;
import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;
import java.lang.UnsupportedOperationException;

public class SortedBag<E extends Comparable<? super E>>
    extends AbstractCollection<E>
    implements Iterable<E>, Collection<E>
{
    private Object[] sortedElements; // storage of sorted elements
    private int sortedCount; // number of sorted elements

    private Object[] addedElements; // recently added elements (unsorted)
    private int addedCount; // number of unsorted elements

    private int addMax; // maximum allowed number of unsorted elements

    private int removedCount; // number of removed (null) elements in sorted array

    private int modCount; 

    public SortedBag(int initialCapacity) {
        if (initialCapacity < 10)
            initialCapacity = 10;

        sortedElements = new Object[initialCapacity];
        sortedCount = 0;

        addMax = (int)Math.floor( Math.log(initialCapacity) / Math.log(2) ) + 1;

        // large enough add storage
        addedElements = (new Object[33]);    // log2(maxint)+1
        addedCount = 0;
        removedCount = 0;

        modCount = 0;
    }


    public SortedBag() {
        this(10);
    }


    // Constructor that copies given collection here
    public SortedBag(Collection<? extends E> c) {
        sortedCount = c.size();
        sortedElements = new Object[(int)(sortedCount * 1.2)];
        c.toArray(sortedElements);
    }

    // number of elements
    public int size() {
        return sortedCount + addedCount - removedCount;
    }

    // empty or not
    public boolean isEmpty() {
        return ((sortedCount + addedCount - removedCount) == 0);
    }

    // do contain or not
    public boolean contains(E x) {
        return find(x) != -1;
    }

    // add elements
    // returns true always
    public boolean add(E x) {
        addedElements[addedCount++] = x;
        modCount++;
        if (addedCount > addMax)
            sort();
        return true;
    }

    // removes single instance of element x
    public boolean remove(E x) {
        int ind = find(x);
        if (ind == -1)
            return false;

        if (ind < sortedCount) {      // remove from sorted
            sortedElements[ind] = null;
            removedCount++;
        } else {                // remove from added
            // move last instead of removed
            addedElements[ind] = addedElements[addedCount-1];
            addedCount--;
        }
        modCount++;
        return true;
    }

    // remove all instances of x
    @SuppressWarnings("unchecked")
    public boolean removeAll(E x) {

        int ind = -1;
            ind = find(x);

        if (ind == -1)
            return false;

        if (ind < sortedCount) {      // remove from sorted
            sortedElements[ind] = null;
            removedCount++;

            // remove to left
            int i = ind-1;
            while (i >= 0 && sortedElements[i] != null &&
                   ((Comparable)(sortedElements[i])).compareTo(x) == 0) {
                sortedElements[i--] = null;
                removedCount++;
            }

            // remove to right
            i = ind+1;
            while (i < sortedCount && sortedElements[i] != null &&
                   ((Comparable)(sortedElements[i])).compareTo(x) == 0) {
                sortedElements[i++] = null;
                removedCount++;
            }
        }

        // remove from added

        int i = 0;
        while (i < addedCount) {
            if (((Comparable)(addedElements[i])).compareTo(x) == 0) {
                addedElements[i++] = addedElements[addedCount-1];
                addedCount--;
            }
        }
        modCount++;
        return true;
    } // removeAll(E)


    // removes all elements of c
    @SuppressWarnings("unchecked")
    public boolean removeAll(Collection<?> c) {
        boolean ret = false;
        for (Object x : c)
            ret = removeAll((E)x) || ret;      
        return ret;
    }
        

    // implementatino of Iterable
    public Iterator<E> iterator() {
        return new Iter();
    }

    // clears collection
    public void clear() {
        sortedCount = 0;
        addedCount = 0;
        removedCount = 0;
    }

    // string representation
    public String toString() {
        StringBuffer s = new StringBuffer(this.size() * 2 + 1); // minimum
        s.append("{");
        for (E x : this) {
            // s.append(x.toString());
            s.append(x);
            s.append(" ");
        }
        if (this.isEmpty())
            s.append("}");
        else
            s.setCharAt(s.length()-1, '}');

        return s.toString();
    }


    // internal helper method

    // return -1 if not found, index if found
    // if finds from added, returns sortedCount + ind(addedElements)
    @SuppressWarnings("unchecked")
    private int find(E x) {

        /*
        // this would work if we had no nulls
        int ind = Arrays.binarySearch(sortedElements, x);
        if (ind >= 0)
            return ind;
        */

        int v = 0;
        int o = sortedCount-1;
        while (v <= o && sortedElements[v] == null)
            v++;    // skip initial nulls

        while (v <= o && sortedElements[o] == null)
            o--;    // skip end nulls

        while (v <= o) {
            int k = (v+o)/2;
            if (sortedElements[k] == null) {
                // we hit null
                // progress right
                while (sortedElements[k] == null)
                    k++;
            }

            // normal binary search step
            int cmp = ((Comparable)(sortedElements[k])).compareTo(x);
            if (cmp == 0)
                return k;

            else if (cmp < 0) {
                v = k + 1;
                while (v <= o && sortedElements[v] == null)
                    v++;    // vielä null:t

            } else {
                o = k - 1;
                while (v <= o && sortedElements[o] == null)
                    o--;    // vielä null:t
            }

        }   // while


        for (int i = 0; i < addedCount; i++)
            if (((Comparable)(addedElements[i])).compareTo(x) == 0)
                return sortedCount + i;

        return -1;
    }


    // enlarges and sorts array
    private void expandsortedElements(int newSIze) {
        compact();
        int oldSIze = sortedElements.length;
        if (oldSIze < newSIze) {
            modCount++;
            Object[] oldsortedElements = sortedElements;
            sortedElements = new Object[oldSIze * 2];
            System.arraycopy(oldsortedElements, 0, sortedElements, 0, sortedCount);

            addMax = addMax + 1;
        }
    }

    // sorts added into sorted array
    @SuppressWarnings("unchecked")
    private void sort() {

        if (addedCount == 0)
            return;

        compact();

        expandsortedElements(sortedCount + addedCount);

        modCount++;

        Arrays.sort(addedElements, 0, addedCount);

        int j = sortedCount-1;
        int u = sortedCount + addedCount - 1;
        int s = addedCount-1;

        while (u >= 0 && s >= 0) {
            if ((j < 0) || ((Comparable)(addedElements[s])).compareTo(sortedElements[j]) > 0) {
                sortedElements[u] = addedElements[s];
                s--;
            } else {
                sortedElements[u] = sortedElements[j];
                j--;
            }
            u--;
        }

        sortedCount += addedCount;
        addedCount = 0;
    }

    // removed nulls (removed positions)
    private void compact() {

        if (removedCount == 0)
            return;

        modCount++;

        int u = 0;
        for (int i = 0; i < sortedCount; i++)
            if (sortedElements[i] != null)
                sortedElements[u++] = sortedElements[i];

        if (u + removedCount != sortedCount)
            throw new NoSuchElementException("Compact failed !?!");

        sortedCount = u;
        removedCount = 0;
    }

    // Iterator class that impelents Iterable
    private class Iter implements Iterator<E> {

        // position on iteration
        int ind;

        // maintain info about the modCount in the beginning of iteration
        // to get info about a concurrent change
        int originalModCount;

        public Iter() {
            ind = 0;
            sort();
            compact();
            originalModCount = modCount;
        }

        public boolean hasNext() {
            check();
            return ind < sortedCount;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            check();
            if (ind >= sortedCount) {
                throw new NoSuchElementException(
                      "next() called without hasNext()");
            }
            return (E) sortedElements[ind++];

        }

        // removed element given by previous next()
        public void remove() {
            sortedElements[ind-1] = null;
            removedCount++;
            modCount++; // here we can make change
            originalModCount = modCount;    // remember new modCount
        }

        // check if modCount was changed elsewhere
        void check() {
            if (modCount != originalModCount)
                throw new ConcurrentModificationException(
                      "Bag changed during iteration");
        }
    }   // class Iter


}   // class SortedBag