// ------------------------
// ArrayInitialization.java
// ------------------------

import java.util.Arrays;

interface Array<T> {
    public T    get (int i);
    public void set (int i, T v);}

final class LinearArray<T> implements Array<T> {
    private T[] a;

    /**
     * O(n)
     */
    public LinearArray (int n, T v) {
//      a = new T[n];
        a = (T[]) new Object[n];  // warning: unchecked cast
        Arrays.fill(a, v);}

    /**
     * O(1)
     */
    public T get (int i) {
        return a[i];}

    /**
     * O(1)
     */
    public void set (int i, T v) {
        a[i] = v;}}

final class ConstantArray<T> implements Array<T> {
    private T[]   a;
    private int[] b;
    private int[] c;
    private int   s;
    private T     v;

    /**
     * O(1)
     */
    private boolean check (int i) {
        if ((c[i] < 0) || (c[i] >= s) || (b[c[i]] != i)) {
            b[s] = i;
            c[i] = s;
            ++s;
            return true;}
        return false;}

    /**
     * O(1)
     */
    public ConstantArray (int n, T v) {
//      a      = new T[n];
        a      = (T[]) new Object[n];  // warning: unchecked cast
        b      = new int[n];
        c      = new int[n];
        s      = 0;
        this.v = v;}

    /**
     * O(1)
     */
    public T get (int i) {
        if (check(i))
            a[i] = v;
        return a[i];}

    /**
     * O(1)
     */
    public void set (int i, T v) {
        check(i);
        a[i] = v;}}

final class ArrayInitializationTest {
    public static void main (String[] args) {
        System.out.println("ArrayInitialization.java");

        {
        Array<String> x = new LinearArray<String>(10, "abc");
        assert x.get(2) == "abc";
        x.set(2, "def");
        assert x.get(2) == "def";
        x.set(3, "ghi");
        assert x.get(3) == "ghi";
        }

        {
        Array<String> x = new ConstantArray<String>(10, "abc");
        assert x.get(2) == "abc";
        x.set(2, "def");
        assert x.get(2) == "def";
        x.set(3, "ghi");
        assert x.get(3) == "ghi";
        }

        System.out.println("Done.");}}