Flow.Collections.GapBufferList

package Flow.Collection;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import Flow.InvalidOperationException;
import Flow.NotSupportedException;

public class GapBufferList<T> implements List<T>
{
    public GapBufferList()
    {
        this(32);
    }
    @SuppressWarnings("unchecked")
    public GapBufferList(int cap)
    {
        if (cap < 0) throw new InvalidOperationException("Initial capacity must be >= 0");
        gapPos = 0;
        gapSize = cap;
        back = (T[])new Object[cap];
    }

    private T[] back;
    private int gapPos, gapSize;

    @Override
    public int size()
    {
        return back.length - gapSize;
    }
    @Override
    public boolean isEmpty()
    {
        return back.length == gapSize;
    }

    @Override
    public int indexOf(Object obj)
    {
        int sz = back.length - gapSize;
        for (int q = 0; q < sz; q++)
            if (obj == null ? get(q) == null : obj.equals(get(q))) return q;
        return -1;
    }
    @Override
    public int lastIndexOf(Object obj)
    {
        int sz = back.length - gapSize;
        for (int q = sz - 1; q >= 0; q++)
            if (obj == null ? get(q) == null : obj.equals(get(q))) return q;
        return -1;
    }

    @Override
    public T get(int index)
    {
        if (index < 0 || index >= back.length - gapSize) throw new IndexOutOfBoundsException();
        if (index < gapPos) return back[index];
        else return back[index + gapSize];
    }

    @Override
    public boolean contains(Object obj)
    {
        return indexOf(obj) >= 0;
    }
    @Override
    public boolean containsAll(Collection<?> c)
    {
        for (Object obj : c)
            if (!contains(obj)) return false;
        return true;
    }

    @Override
    public Iterator<T> iterator()
    {
        throw new NotSupportedException();
    }
    @Override
    public ListIterator<T> listIterator()
    {
        throw new NotSupportedException();
    }
    @Override
    public ListIterator<T> listIterator(int index)
    {
        throw new NotSupportedException();
    }



    private void increaseSize()
    {
        int newcap = Math.max(back.length * 3, 4);
        @SuppressWarnings("unchecked")
        T[] temp = (T[])new Object[newcap];
        for (int q = 0; q < gapPos; q++)
            temp[q] = back[q];
        gapSize = temp.length - back.length;
        for (int q = back.length - 1; q >= gapPos; q--)
            temp[q + gapSize] = temp[q];
        back = temp;
    }

    @Override
    public boolean add(T t)
    {
        int pos = back.length - gapSize;
        if (gapPos != pos)
        {
            if (gapSize != 0)
            {
                if (gapSize != 0)
                {
                    int diff = gapPos - pos;
                    for (int q = 1; q <= diff; q++)
                        back[gapPos - q + gapSize] = back[gapPos - q];
                    diff = -diff; //pos - gapPos
                    for (int q = 0; q < diff; q++)
                        back[gapPos + q] = back[gapPos + gapSize + q];
                }
            }
            gapPos = pos;
        }
        //moveGap(back.length - gapSize);
        if (gapSize == 0) increaseSize();
        back[gapPos++] = t; gapSize--;
        return true;
    }
    @Override
    public void add(int index, T t)
    {
        if (index < 0 || index > back.length - gapSize) throw new IndexOutOfBoundsException();
        if (gapPos > index)
        {
            int diff = gapPos - index;
            for (int q = 1; q <= diff; q++)
                back[gapPos - q + gapSize] = back[gapPos - q];
        }
        else if (index > gapPos)
        {
            int diff = gapPos - index;
            for (int q = 0; q < diff; q++)
                back[gapPos + q] = back[gapPos + gapSize + q];
        }
        gapPos = index;
        if (gapSize == 0) increaseSize();
        back[gapPos++] = t; gapSize--;
    }
    @Override
    public boolean addAll(Collection<? extends T> c)
    {
        for (T t : c)
            if (!add(t)) return false;
        return true;
    }
    @Override
    public boolean addAll(int index, Collection<? extends T> c)
    {
        for (T t : c)
            add(index++, t);
        return true;
    }

    @Override
    public T set(int index, T t)
    {
        int sz = back.length - gapSize;
        if (index < 0 || index > sz) throw new IndexOutOfBoundsException();
        if (index == sz)
        {
            add(t);
            return null;
        }
        else if (index < gapPos)
        {
            T temp = back[index];
            back[index] = t;
            return temp;
        }
        else
        {
            T temp = back[index + gapSize];
            back[index + gapSize] = t;
            return temp;
        }
    }

    @Override
    public boolean remove(Object obj)
    {
        int idx = indexOf(obj);
        if (idx >= 0)
        {
            remove(idx);
            return true;
        }
        return false;
    }
    @Override
    public T remove(int index)
    {
        if (index < 0 || index >= back.length - gapSize) throw new IndexOutOfBoundsException();
        if (gapPos > index + 1)
        {
            int diff = gapPos - (index + 1);
            for (int q = 1; q <= diff; q++)
                back[gapPos - q + gapSize] = back[gapPos - q];
        }
        else
        {
            int diff = (index + 1) - gapPos;
            for (int q = 0; q < diff; q++)
                back[gapPos + q] = back[gapPos + gapSize + q];
        }
        gapSize++;
        return back[gapPos = index];
    }
    @Override
    public boolean removeAll(Collection<?> c)
    {
        for (Object obj : c)
            if (!remove(obj)) return false;
        return true;
    }
    @Override
    public void clear()
    {
        gapPos = 0;
        gapSize = back.length;
    }

    @Override
    public boolean retainAll(Collection<?> c)
    {
        //Slightly inefficient method, could definitely be improved
        int sz = back.length - gapSize;
        for (int q = sz - 1; q >= 0; q--)
            if (!c.contains(get(q)))
                remove(q);
        return true;
    }

    @Override
    public List<T> subList(int fromIndex, int toIndex)
    {
        List<T> list = new ArrayList<T>();
        for (int q = fromIndex; q < toIndex; q++)
            list.add(get(q));
        return list;
    }
    @Override
    public Object[] toArray()
    {
        Object[] temp = new Object[back.length - gapSize];
        for (int q = 0; q < temp.length; q++)
            temp[q] = get(q);
        return temp;
    }
    @SuppressWarnings({ "unchecked", "hiding" })
    @Override
    public <T> T[] toArray(T[] a)
    {
        T[] temp = (T[])Array.newInstance(a.getClass().getComponentType(), back.length - gapSize);
        for (int q = 0; q < temp.length; q++)
            temp[q] = (T)get(q);
        return temp;
    }
}