/*
 * @author Ranides Atterwim <ranides@gmail.com>
 * @copyright Ranides Atterwim
 * @license WTFPL
 * @url http://ranides.net/projects/assira
 */
package net.ranides.assira.collection.lists;

import java.io.Serializable;
import java.util.AbstractList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.RandomAccess;
import java.util.Set;
import net.ranides.assira.collection.arrays.NativeArrayAllocator;
import net.ranides.assira.collection.iterators.RandomAccessIterator;
import net.ranides.assira.collection.sets.HashSet;

/**
 * Abstract class for easy creation "virtual lists". Algorithms in below implementation
 * try to minimize use of {@link #get} method, because of assumption that read operations
 * have high cost, although class doesn't use any buffering.
 * <p>
 * By default list is immutable. If you want to create mutable list, you shoud override:
 * </p>
 * <ul>
 *      <li> {@link #set(int index, Object value) set(int index, Object value)}</li>
 *      <li> {@link #add(int index, Object value) add(int index, Object value)}</li>
 *      <li> {@link #remove(int) remove(int index)}</li>
 * </ul>
 * @param <T>
 */
public abstract class VirtualList<T> extends AbstractList<T> implements RandomAccess, Serializable {
    
    private static final long serialVersionUID = 1L;

    private static final String NSE = "Not supported by immutable virtual lists.";

    @Override
    public abstract int size();

    @Override
    public abstract T get(int index);

    @Override
    public void add(int index, T element) {
        throw new UnsupportedOperationException(NSE);
    }

    @Override
    public T set(int index, T element) {
        throw new UnsupportedOperationException(NSE);
    }

    @Override
    public T remove(int index) {
        throw new UnsupportedOperationException(NSE);
    }

    @Override
    public final Iterator<T> iterator() {
        return listIterator();
    }

    @Override
    public final boolean containsAll(Collection<?> values) {
        // we don't use this#contains to avoid iteration over list many times
        Set<?> set = new HashSet<>(values);
        ListIterator<? extends T> iterator = listIterator();
        while(iterator.hasNext()) {
            set.remove( iterator.next() );
            if( set.isEmpty() ) { return true; }
        }
        return set.isEmpty();
    }

    @Override
    public final boolean removeAll(Collection<?> values) {
        // we don't use this#remove to avoid iteration over list many times
        boolean modified = false;
        Set<?> set = new HashSet<>(values);
        ListIterator<? extends T> iterator = listIterator();
        while(iterator.hasNext()) {
            T value = iterator.next();
            if(set.contains(value)) {
                iterator.remove();
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public final boolean retainAll(Collection<?> values) {
        // we don't use this#remove & this#contains to avoid iteration over list many times
        boolean modified = false;
        Set<?> set = new HashSet<>(values);
        ListIterator<? extends T> iterator = listIterator();
        while(iterator.hasNext()) {
            T value = iterator.next();
            if(!set.contains(value)) {
                iterator.remove();
                modified = true;
            }
        }
        return modified;
    }

    @Override
    public final ListIterator<T> listIterator() {
        // faster than default, but without concurrent "fail fast" 
        return new IIterator(0);
    }

    @Override
    public final ListIterator<T> listIterator(int index) {
        // faster than default, but without concurrent "fail fast" 
        return new IIterator(index);
    }

    @Override
    public final List<T> subList(int begin, int end) {
        // we use "our implementation" because we want to provide overriden #containsAll / #removeAll etc
        return new SubList<>(this, begin, end);
    }

    private class IIterator extends RandomAccessIterator<T> {

        public IIterator(int index) {
            super(index);
        }

        @Override
        protected void remove(int index) {
            VirtualList.this.remove(index);
        }

        @Override
        protected void add(int index, T value) {
            VirtualList.this.add(index, value);
        }

        @Override
        protected void set(int index, T value) {
            VirtualList.this.set(index, value);
        }

        @Override
        protected T get(int index) {
            return VirtualList.this.get(index);
        }

        @Override
        protected int size() {
            return VirtualList.this.size();
        }

    }

    private static class SubList<Q> extends VirtualList<Q> {
        
        private static final long serialVersionUID = 1L;

        private final List<Q> list;
        private final int begin;
        private int end;

        public SubList(List<Q> list, int begin, int end) {
			NativeArrayAllocator.ensureFromTo(list.size(), begin, end);
            this.list = list;
            this.begin = begin;
            this.end = end;
        }

        @Override
        public int size() {
            return Math.max(0, Math.min(end, list.size() ) - begin );
        }

        @Override
        public Q get(int index) {
            return list.get(begin+index);
        }

        @Override
        public void add(int index, Q element) {
            list.add(begin+index,element);
			end++;
        }

        @Override
        public Q set(int index, Q element) {
            return list.set(begin+index,element);
        }

        @Override
        public Q remove(int index) {
			Q prev = list.remove(begin + index);
			end--;
			return prev;
        }

    }
  
}
