ShiftAllZerosToRightTest

import junit.framework.TestCase;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class ShiftAllZerosToRightTest extends TestCase {

    private static int[] shiftZerosToRight(final int[] inputArray) {

        // Go "right to left", pushing non-zero values onto the stack, and setting all array values to zero:
        final IntStack stack = new IntStack(inputArray.length);
        for (int idx = inputArray.length - 1; idx >= 0; --idx) {
            final int value = inputArray[idx];
            if (value != 0) {
                stack.push(value);
            }
            inputArray[idx] = 0;
        }

        // "Left to right" to "lay the valued down from the stack"  (... preserving the order, as we're popping in the reverse direction from when we pushed.)
        int idx = 0;
        while (stack.hasElements()) {
            inputArray[idx++] = stack.pop();
        }

        // Return the array, "modified in place."
        return inputArray;
    }

    /**
     * Simplistic specialized Stack, as I don't like the synchronized methods of the Java Stack class, nor its lack of
     * initialization to a given size.
     */
    private static class IntStack {
        int _idx = 0;
        final int[] _values;

        public IntStack(final int initialSize) {
            _values = new int[initialSize];
        }

        public void push(final int value) {
            _values[_idx++] = value;
        }

        public boolean hasElements() {
            return _idx > 0;
        }

        public int pop() {
            return _values[--_idx];
        }
    }

    private static int[] mostEfficient(final int[] inputArray) {
        int position = 0;
        for (int i = 0; i < inputArray.length; i++) {
            if (inputArray[i] != 0) {
                inputArray[position] = inputArray[i];
                position++;
            }
        }

        /*Assign zero to remaining elements*/
        while (position < inputArray.length) {
            inputArray[position] = 0;

            position++;
        }

        return inputArray;
    }

    private static int[] arrayCopyNonZeros(final int[] inputArray) {
        final int[] copy = new int[inputArray.length];
        // Copy non-zero values to the new array:
        int idx = 0;
        for (int value : inputArray) {
            if (value != 0) {
                copy[idx++] = value;
            }
        }
        // (Remaining cells in "copy" array were initialized by Java to be zero.

        // Copy the result back:
        idx = 0;
        for (int value : copy) {
            inputArray[idx++] = value;
        }

        return inputArray;
    }

    private static int[] quickCopy(final int[] inputArray) {
        for (int leftIdx = 0, rightIdx = 1; rightIdx < inputArray.length; rightIdx++) {
            if (inputArray[leftIdx] == 0) {
                if (inputArray[rightIdx] != 0) {
                    inputArray[leftIdx] = inputArray[rightIdx];
                    inputArray[rightIdx] = 0;
                    leftIdx++;
                }
            } else {
                leftIdx++;
            }
        }
        return inputArray;
    }

    private static Integer[] withStreams(final Integer[] nums) {
        List<Integer> nonzeros = Arrays.stream(nums).filter(num -> num != 0).collect(Collectors.toList());
        List<Integer> zeros = Arrays.stream(nums).filter(num -> num == 0).collect(Collectors.toList());
        List<Integer> result = Stream.concat(nonzeros.stream(), zeros.stream()).collect(Collectors.toList());
        return result.toArray(new Integer[nums.length]);
    }


    public void testEmpty() {
        assertEqualsAfterShifting(new int[]{}, new int[]{});
    }

    public void testNoZeros() {
        assertEqualsAfterShifting(new int[]{1}, new int[]{1});
        assertEqualsAfterShifting(new int[]{1, 2}, new int[]{1, 2});
        assertEqualsAfterShifting(new int[]{1, 2, 3}, new int[]{1, 2, 3});
    }

    public void testZerosAtEnd() {
        assertEqualsAfterShifting(new int[]{1, 0}, new int[]{1, 0});
        assertEqualsAfterShifting(new int[]{1, 0, 0}, new int[]{1, 0, 0});
        assertEqualsAfterShifting(new int[]{1, 2, 0}, new int[]{1, 2, 0});
    }

    public void testOneZeroToMove() {
        assertEqualsAfterShifting(new int[]{1, 0}, new int[]{0, 1});
        assertEqualsAfterShifting(new int[]{1, 2, 0}, new int[]{1, 0, 2});
        assertEqualsAfterShifting(new int[]{1, 2, 0}, new int[]{0, 1, 2});
    }

    public void testOneDigitTwoZeros() {
        assertEqualsAfterShifting(new int[]{1, 0, 0}, new int[]{0, 1, 0});
        assertEqualsAfterShifting(new int[]{1, 0, 0}, new int[]{0, 0, 1});
    }

    public void testAllZeros() {
        assertEqualsAfterShifting(new int[]{0}, new int[]{0});
        assertEqualsAfterShifting(new int[]{0, 0}, new int[]{0, 0});
        assertEqualsAfterShifting(new int[]{0, 0, 0}, new int[]{0, 0, 0});
        assertEqualsAfterShifting(new int[]{0, 0, 0, 0}, new int[]{0, 0, 0, 0});
    }

    public void testNegativeValues() {
        assertEqualsAfterShifting(new int[]{-1, -2, 0, 0, 0}, new int[]{0, -1, 0, -2, 0});
    }

    public void testMultipleZerosAndNumbers() {
        assertEqualsAfterShifting(new int[]{1, 2, 3, 4, 0, 0, 0, 0, 0, 0}, new int[]{0, 0, 1, 2, 0, 0, 3, 4, 0, 0});
    }

    public void testMinAndMaxIntegerValues() {
        assertEqualsAfterShifting(new int[]{1, Integer.MAX_VALUE, -1, 11, Integer.MIN_VALUE, -45, 0}, new int[]{1, Integer.MAX_VALUE, -1, 0, 11, Integer.MIN_VALUE, -45});
    }

    public void testOtherValues() {
        assertEqualsAfterShifting(new int[]{-3, -2, -1, 1, 2, 3, 0}, new int[]{-3, -2, -1, 0, 1, 2, 3});
    }

    public void testAssertArraysAreEquals() {
        try {
            assertEquals("YourMessageHere;", new int[]{1, 2, 3}, new int[]{3, 2, 1});
            throw new IllegalArgumentException("Expected AssertionError.");
        } catch (final AssertionError ex) {
            assertEquals("YourMessageHere; Arrays are not equal: expected <[1, 2, 3]> but was <[3, 2, 1]>", ex.getMessage());
        }
    }

    private static void assertEqualsAfterShifting(final int[] expectedValues, final int[] inputValues) {
        assertEquals("shiftZerosToRight;", expectedValues, shiftZerosToRight(Arrays.copyOf(inputValues, inputValues.length)));
        assertEquals("mostEfficient;", expectedValues, mostEfficient(Arrays.copyOf(inputValues, inputValues.length)));
        assertEquals("arrayCopyNonZeros;", expectedValues, arrayCopyNonZeros(Arrays.copyOf(inputValues, inputValues.length)));
        assertEquals("quickCopy;", expectedValues, quickCopy(Arrays.copyOf(inputValues, inputValues.length)));

        assertEquals("withStreams;", expectedValues, toIntArray(withStreams(toIntegerArray(inputValues))));
    }

    private static Integer[] toIntegerArray(final int[] inputValues) {
        final Integer[] result = new Integer[inputValues.length];
        int idx = 0;
        for (int value : inputValues) {
            result[idx++] = value;
        }
        return result;
    }

    private static int[] toIntArray(final Integer[] inputValues) {
        final int[] result = new int[inputValues.length];
        int idx = 0;
        for (int value : inputValues) {
            result[idx++] = value;
        }
        return result;
    }

    private static void assertEquals(final String message, final int[] expectedValues, final int[] actualValues) {
        if (!Arrays.equals(expectedValues, actualValues)) {
            throw new AssertionError(message + " Arrays are not equal: expected <" + Arrays.toString(expectedValues) + "> but was <" + Arrays.toString(actualValues) + ">");
        }
    }

}