// Järjestetty laukku
// perii (suuren) osan Collection toiminnallisuudesta AbstractCollection:lta
// Laukun toteutus: taulukon alkuosa on järjestyksessä, loppuosa sekaisin
// Tarvittaessa järjestetään koko taulukko.
// Poistoja ei tehdä suoraan, vaan merkitään alkiot poistetuiksi


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 JLaukku<E extends Comparable>
    extends AbstractCollection<E>
    implements Iterable<E>, Collection<E>
{
    private Object[] jarjT; // järjestetyt alkiot
    private int jarjMaara; // järjestettyjen määrä

    private Object[] lisT; // lisätyt alkiot (sekaisin)
    private int lisMaara; // sekaisten määrä

    private int smax; // suurin sallittu sekaisten määrä

    private int poistMaara; // järjestetyllä alueella olevien null:ien määrä

    private int modCount;   // muutoksen havaitseminen kesken toiston

    public JLaukku(int alkukapasiteetti) {
        if (alkukapasiteetti < 10)
            alkukapasiteetti = 10;

        jarjT = new Object[alkukapasiteetti];
        jarjMaara = 0;

        smax = (int)Math.floor( Math.log(alkukapasiteetti) / Math.log(2) ) + 1;

        // riittävän iso lisäysalue jotta sen koosta ei tarvitse huolehtia
        lisT = (new Object[33]);    // log2(maxint)+1
        lisMaara = 0;
        poistMaara = 0;

        modCount = 0;
    }


    public JLaukku() {
        this(10);
    }


    // Konstruktori joka kopioi tähän valmiin kokoelman
    public JLaukku(Collection<? extends E> c) {
        jarjMaara = c.size();
        jarjT = new Object[(int)(jarjMaara * 1.2)];
        c.toArray(jarjT);
    }

    // alkioiden lukumäärä
    public int size() {
        return jarjMaara + lisMaara - poistMaara;
    }

    // onko tyhjä
    public boolean isEmpty() {
        return ((jarjMaara + lisMaara - poistMaara) == 0);
    }

    // sisältääkö alkion
    public boolean contains(E x) {
        return etsi(x) != -1;
    }

    // lisää alkion
    // palauttaa toden, sillä lisäys onnistuu aina (jos muistia on)
    public boolean add(E x) {
        lisT[lisMaara++] = x;
        modCount++;
        if (lisMaara > smax)
            jarjesta();
        return true;
    }

    // poistaa alkion x
    public boolean remove(E x) {
        int ind = etsi(x);
        if (ind == -1)
            return false;

        if (ind < jarjMaara) {      // poistetaan järjestetyistä
            jarjT[ind] = null;
            poistMaara++;
        } else {                // poistetaan lisätyistä
            lisT[ind] = lisT[lisMaara-1];
            lisMaara--;
        }
        modCount++;
        return true;
    }

    // poistaa kaikki alkion x esiintymät
    @SuppressWarnings("unchecked")
    public boolean removeAll(Object x) {

        int ind = -1;
            ind = etsi((E)x);

        if (ind == -1)
            return false;

        if (ind < jarjMaara) {      // poistetaan järjestetyistä
            jarjT[ind] = null;
            poistMaara++;

            // poistetaan löytokohdasta vasemmalle
            int i = ind-1;
            while (i >= 0 && jarjT[i] != null &&
                   ((Comparable)(jarjT[i])).compareTo(x) == 0) {
                jarjT[i--] = null;
                poistMaara++;
            }

            // poistetaan löytökohdasta oikealle
            i = ind+1;
            while (i < jarjMaara && jarjT[i] != null &&
                   ((Comparable)(jarjT[i])).compareTo(x) == 0) {
                jarjT[i++] = null;
                poistMaara++;
            }
        }

        // poistetaan lisätyistä

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


    // poistaa kaikki c:n alkiot
    public boolean removeAll(Collection<?> c) {
        boolean ret = false;
        for (Object x : c)
            ret = removeAll(x) || ret;      // toivottavasti suoritetaan näinpäin
        return ret;
    }
        

    // Iterable:n toteutus
    public Iterator<E> iterator() {
        return new Iter();
    }

    // tyhjentää kokoelman
    public void clear() {
        jarjMaara = 0;
        lisMaara = 0;
        poistMaara = 0;
    }

    // merkkijonoesitys
    public String toString() {
        StringBuffer s = new StringBuffer(this.size() * 2 + 1); // ehdoton minimi
        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();
    }


    // sisäiset apumetodit

    // palauttaa -1 jollei löydy, indeksin jos löytyy.
    // jos löytyy sekaisista, palauttaa jarjMaara + ind(lisT)
    @SuppressWarnings("unchecked")
    private int etsi(E x) {

        /*
        // tämä toimisi jollei poistoja olisi
        int ind = Arrays.binarySearch(jarjT, x);
        if (ind >= 0)
            return ind;
        */

        int v = 0;
        int o = jarjMaara-1;
        while (v <= o && jarjT[v] == null)
            v++;    // ohitetaan alku null:t

        while (v <= o && jarjT[o] == null)
            o--;    // ohitetaan lopun null:t

        while (v <= o) {
            int k = (v+o)/2;
            if (jarjT[k] == null) {
                // osuttiin poistettuun alkioon
                // edetään oikealle, viimeistään listT[o] != null
                while (jarjT[k] == null)
                    k++;
            }

            // normaali binäärihaun askel
            int cmp = ((Comparable)(jarjT[k])).compareTo(x);
            if (cmp == 0)
                return k;

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

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

        }   // while


        for (int i = 0; i < lisMaara; i++)
            if (((Comparable)(lisT[i])).compareTo(x) == 0)
                return jarjMaara + i;

        return -1;
    }


    // laajentaa ja järjestää taulukon
    private void laajennajarjT(int uusiKoko) {
        tiivista();
        int vanhaKoko = jarjT.length;
        if (vanhaKoko < uusiKoko) {
            modCount++;
            Object[] vanhajarjT = jarjT;
            jarjT = new Object[vanhaKoko * 2];
            System.arraycopy(vanhajarjT, 0, jarjT, 0, jarjMaara);

            smax = smax + 1;
        }
    }

    // järjestää taulukon lopun järjestettyyn osaan
    @SuppressWarnings("unchecked")
    private void jarjesta() {

        if (lisMaara == 0)
            return;

        tiivista();

        laajennajarjT(jarjMaara + lisMaara);

        modCount++;

        Arrays.sort(lisT, 0, lisMaara);

        int j = jarjMaara-1;
        int u = jarjMaara + lisMaara - 1;
        int s = lisMaara-1;

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

        jarjMaara += lisMaara;
        lisMaara = 0;
    }

    // poistaa mahdolliset poistoista tulleet null:t järjestetystä taulukosta
    private void tiivista() {

        if (poistMaara == 0)
            return;

        modCount++;

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

        if (u + poistMaara != jarjMaara)
            throw new NoSuchElementException("Tiivistäminen epäonnistui !?!");

        jarjMaara = u;
        poistMaara = 0;
    }

    // Iteraattoriluokka joka tarvitaan Iterable:n iterator():n palauttamiseen
    private class Iter implements Iterator<E> {

        // läpikäynnin sijainti
        int ind;

        // Pidetään yllä tietoa varsinaisen laukun alkuperäisestä modCount:sta.
        // Jos muualla tehdään muutosta, niin se havaitaan täällä.
        int alkuModCount;

        public Iter() {
            ind = 0;
            jarjesta();
            tiivista();
            alkuModCount = modCount;
        }

        public boolean hasNext() {
            tarkista();
            return ind < jarjMaara;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            tarkista();
            if (ind >= jarjMaara) {
                throw new NoSuchElementException(
                      "next():ä kutsuttu ilman hasNext():ä");
            }
            return (E) jarjT[ind++];

        }

        // poistaa edellisen next():n antaman alkion
        public void remove() {
            jarjT[ind-1] = null;
            poistMaara++;
            modCount++; // täällä saa tehdä muutoksen
            alkuModCount = modCount;    // muistetaan uusi modCount
        }

        // tarkistaa onko modCount muuttunut muualla
        void tarkista() {
            if (modCount != alkuModCount)
                throw new ConcurrentModificationException(
                      "Joukkoa muutettu kesken läpikäynnin");
        }
    }   // class Iter


}   // class JLaukku