import java.util.ArrayList;
import java.util.List;

public class SplitList<T> {
    class Block<T>{
        ArrayList<T> blockData;
        Block<T> last;
        Block<T> next;
        Block(int size){
            blockData = new ArrayList<>(size);
        }
    }

    class EleInfo<T>{
        Block<T> block;
        int eleLoc;

        public EleInfo(Block<T> block, int eleLoc) {
            this.block = block;
            this.eleLoc = eleLoc;
        }
    }

    private int blockMaxSize;
    private long eleCount;
    private long blockCount;
    private Block<T> head;
    private Block<T> tail;

    private void initSplitList(int blockMaxSize){
        head = new Block<>(blockMaxSize);
        this.blockCount = 1;
        this.blockMaxSize = blockMaxSize;
        tail = head;
    }

    public SplitList(){
        initSplitList(1000);
    }

    public SplitList(int blockMaxSize){
        initSplitList(blockMaxSize);
    }

    private void appendBlock(Block<T> tmpBlock){
        Block<T> newBlock = new Block<>(blockMaxSize);
        newBlock.next = tmpBlock.next;
        newBlock.last = tmpBlock;
        tmpBlock.next = newBlock;
        if(newBlock.next != null) {
            newBlock.next.last = newBlock;
        }
        else{
            tail = newBlock;
        }
        blockCount++;
    }

    private void removeBlock(Block<T> tmpBlock){
        Block<T> lastBlock = tmpBlock.last;
        Block<T> nextBlock = tmpBlock.next;
        if(lastBlock != null){
            lastBlock.next = nextBlock;
        }
        else{
            head = nextBlock;
        }
        if(nextBlock != null){
            nextBlock.last = lastBlock;
        }
        else{
            tail = lastBlock;
        }
        blockCount--;
    }

    private EleInfo getEleInfo(long loc) throws IndexOutOfBoundsException{
        if(loc >= eleCount){
            throw new IndexOutOfBoundsException();
        }
        Block<T> tmpBlock = head;
        while(tmpBlock != null){
            int tmpSize = tmpBlock.blockData.size();
            if(loc < tmpSize){
                break;
            }
            loc -= tmpSize;
            tmpBlock = tmpBlock.next;
        }
        return new EleInfo(tmpBlock, (int) loc);
    }

    public long getEleCount(){
        return eleCount;
    }

    public long getBlockCount(){
        return blockCount;
    }

    public T get(long loc){
        EleInfo<T> eleInfo = getEleInfo(loc);
        return eleInfo.block.blockData.get(eleInfo.eleLoc);
    }

    public void set(long loc, T ele){
        EleInfo<T> eleInfo = getEleInfo(loc);
        eleInfo.block.blockData.set(eleInfo.eleLoc, ele);
    }

    public void add(T ele){
        int tailSize = tail.blockData.size();
        if(tailSize >= blockMaxSize){
            appendBlock(tail);
        }
        tail.blockData.add(ele);
        eleCount++;
    }

    public void add(long loc, T ele){
        EleInfo<T> eleInfo = getEleInfo(loc);
        Block<T> tmpBlock = eleInfo.block;
        List<T> tmpData = tmpBlock.blockData;
        while(tmpData.size() >= blockMaxSize){
            if(tmpBlock.next == null){
                appendBlock(tmpBlock);
            }
            T remEle = tmpData.remove(tmpData.size()-1);
            tmpBlock.next.blockData.add(0, remEle);
        }
        tmpData.add(eleInfo.eleLoc, ele);
        eleCount++;
    }

    public T remove(long loc){
        EleInfo<T> eleInfo = getEleInfo(loc);
        Block<T> tmpBlock = eleInfo.block;
        List<T> tmpData = tmpBlock.blockData;
        T remEle = tmpData.remove(eleInfo.eleLoc);
        eleCount--;
        if(tmpData.isEmpty()){
            removeBlock(tmpBlock);
        }
        return remEle;
    }

    public static void main(String[] args) {
        SplitList<Integer> splitList = new SplitList<>(10000);

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            splitList.add(i);
        }
        System.out.println(System.currentTimeMillis() - startTime);

        startTime = System.currentTimeMillis();
        for (int i = 0; i < 100; i++) {
            splitList.add(i, i);
        }
        System.out.println(System.currentTimeMillis() - startTime);

        startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            splitList.get(i);
        }
        System.out.println(System.currentTimeMillis() - startTime);
//        for (int i = 95; i < 100; i++) {
//            splitList.add(i, i);
//        }
//        for (int i = 100; i < 105; i++) {
//            splitList.remove(100);
//        }
//        for (int i = 0; i < 100; i++) {
//            System.out.println(splitList.get(i));
//        }
    }

}