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

public class Bench {

    public static void main(String[] args){

        // First solution
        Random r = new Random();
        List<String> initialList = new ArrayList<String>(21);
        for (int i=0;i<160;i++) {
            initialList.add("test");
        }
        for (int i=0; i<40; i++) {
            initialList.add(r.nextInt(initialList.size()-1), "test2");
        }

        // Test
        List<String> newList1 = new ArrayList<String>(initialList);
        for (String item : initialList) {
            if (item.length() > 4) {
                newList1.remove(item);
            }
        }
        assert(newList1.size() == 160);

        long startTime = System.currentTimeMillis();

        for (int i=0;i<1000000;i++) {
            List<String> newList = new ArrayList<String>(initialList);
            for (String item : initialList) {
                if (item.length() > 4) {
                    newList.remove(item);
                }
            }
        }

        long endTime = System.currentTimeMillis();
        System.out.println("First : "
                        + (endTime - startTime)+ " ms");



        // Second solution

        // Test
        List<String> newList2 = new ArrayList<String>();
        for (String item : initialList) {
            if (item.length() <= 4) {
                newList2.add(item);
            }
        }
        assert(newList2.size() == 16);

        long startTime1 = System.currentTimeMillis();

        for (int i=0;i<1000000;i++) {
            List<String> newList = new ArrayList<String>();
            for (String item : initialList) {
                if (item.length() <= 4) {
                    newList.add(item);
                }
            }
        }

        long endTime1 = System.currentTimeMillis();
        System.out.println("Second :  "
                        + (endTime1 - startTime1)+ " ms");



        // Third solution

        // Test
        List<String> newList3 = new ArrayList<String>(initialList.size()+1);
        for (String item : initialList) {
            if (item.length() <= 4) {
                newList3.add(item);
            }
        }
        assert(newList3.size() == 160);

        long startTime2 = System.currentTimeMillis();

        for (int i=0;i<1000000;i++) {
            List<String> newList = new ArrayList<String>(initialList.size()+1);
            for (String item : initialList) {
                if (item.length() <= 4) {
                    newList.add(item);
                }
            }
        }

        long endTime2 = System.currentTimeMillis();
        System.out.println("Third :  "
                        + (endTime2 - startTime2)+ " ms");




        // Fourth solution

        // Test
        List<String> newList4 = new ArrayList<String>(initialList.size());
        for (String item : initialList) {
            if (item.length() <= 4) {
                newList4.add(item);
            }
        }
        assert(newList4.size() == 160);

        long startTime4 = System.currentTimeMillis();

        for (int i=0;i<1000000;i++) {
            List<String> newList = new ArrayList<String>(initialList.size());
            for (String item : initialList) {
                if (item.length() <= 4) {
                    newList.add(item);
                }
            }
        }

        long endTime4 = System.currentTimeMillis();
        System.out.println("Fourth :  "
                        + (endTime4 - startTime4)+ " ms");

        // Fifth solution

        // Test
        {
            String[] arr = new String[initialList.size()];
            String[] src = initialList.toArray(new String[initialList.size()]);
            int dstIndex = 0, blockStartIdx=0, blockSize=0;
            for (int currIdx=0; currIdx < initialList.size(); currIdx++) {
                String item = src[currIdx];
                if (item.length() <= 4) {
                    if (blockSize > 0)
                        System.arraycopy(src, blockStartIdx, arr, dstIndex, blockSize);
                    dstIndex += blockSize;
                    blockSize = 0;
                } else {
                    if (blockSize == 0)
                        blockStartIdx = currIdx;
                    blockSize++;
                }
            }
            assert(arr.length == 160);
        }

        long startTime5 = System.currentTimeMillis();

        for (int i=0;i<1000000;i++) {
            String[] arr = new String[initialList.size()];
            String[] src = initialList.toArray(new String[initialList.size()]);
            int dstIndex = 0, blockStartIdx=0, blockSize=0;
            for (int currIdx=0; currIdx < initialList.size(); currIdx++) {
                String item = src[currIdx];
                if (item.length() <= 4) {
                    if (blockSize > 0)
                        System.arraycopy(src, blockStartIdx, arr, dstIndex, blockSize);
                    dstIndex += blockSize;
                    blockSize = 0;
                } else {
                    if (blockSize == 0)
                        blockStartIdx = currIdx;
                    blockSize++;
                }
            }
            assert(arr.length == 160);
        }

        long endTime5 = System.currentTimeMillis();
        System.out.println("Fifth :  "
                        + (endTime5 - startTime5)+ " ms");

    }

}