// ---------
// Find.java
// ---------

import java.util.Arrays;
import java.util.List;
import java.util.ListIterator;

final class Find {
    /**
     * O(1) in space
     * O(n) in time
     */
    public static int eval (long[] a, int b, int e, long v) {
        assert b <= e;
        while (b != e) {
            if (a[b] == v)
                return b;
            ++b;}
        return b;}

    /**
     * O(1) in space
     * O(n) in time
     */
    public static int eval (Object[] a, int b, int e, Object v) {
        assert b <= e;
        if (v == null)
            while (b != e) {
                if (a[b] == null)
                    return b;
                ++b;}
        else
            while (b != e) {
                if (v.equals(a[b]))
                    return b;
                ++b;}
        return b;}

    /**
     * O(1) in space
     * O(n) in time
     */
    public static <T> int eval (List<? extends T> x, T v) {
        final ListIterator<? extends T> p = x.listIterator();
        if (v == null) {
            while (p.hasNext())
                if (p.next() == null)
                    return p.previousIndex();}
        else {
            while (p.hasNext())
                if (v.equals(p.next()))
                    return p.previousIndex();}
        return p.nextIndex();}}

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

        {
        final long[] a = {2, 4, 6};
        assert Find.eval(a, 0, a.length, 2) == 0;
        assert Find.eval(a, 0, a.length, 4) == 1;
        assert Find.eval(a, 0, a.length, 6) == 2;
        assert Find.eval(a, 0, a.length, 5) == 3;
        }

        {
        final String[] a = {"abc", null, "def"};
        assert Find.eval(a, 0, a.length, "abc") == 0;
        assert Find.eval(a, 0, a.length, null)  == 1;
        assert Find.eval(a, 0, a.length, "def") == 2;
        assert Find.eval(a, 0, a.length, "ghi") == 3;
        }

        {
        final List<String> x = Arrays.asList("abc", null, "def");
        assert Find.eval(x, "abc") == 0;
        assert Find.eval(x, null)  == 1;
        assert Find.eval(x, "def") == 2;
        assert Find.eval(x, "ghi") == 3;
        }

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