list literal gotcha and suggestion

[Neal Gafter]

On Wed, Oct 7, 2009 at 9:15 AM, Reinier Zwitserloot <reinier at zwitserloot.com
> wrote:

> Will you stop beating around the bush? What is it then?
>
> What will this code print, and will the call to test() take O(1) or O(n)
> time?
>
>
> public class Test {
>
>     public void test(Collection<?> t) {
>         System.out.println(t.size());
>         System.out.println(t.contains("Hello"));
>     }
>
>     public static void main(String[] args) {
>         test({"a", "b", "c", "a", "b", "c", /* 99,993 more strings */,
> "Hello"});
>     }
> }
>
>
> Will it take O(N) time and print '100000\ntrue\n', or will it take O(1)
> time and print '99997\ntrue\n'?
>

In practice, this will fail to compile because the size of the bytecode
required to express the body of the main method doesn't fit within the JVM's
limits.

Ignoring that for a moment, I would expect it to take O(N) time to construct
the collection, because it would be done as a sequence of operations to add
one element at a time.  That's the only way to reasonably extend this to
non-constants (note that a collection literal itself cannot be a
"compile-time constant").  It is a separate decision what kind of collection
you get in this case.  I suggest that it's result be some type that
implements Collection but not List or Set, is immutable, and whose
construction (via a factory) doesn't remove duplicates; I'd expect it to
print 100000.

In other words, it is the compile-time conversion from "collection
literal..." to "set" that causes the duplicates to be removed, and this
program doesn't trigger that conversion.  I would still expect the compiler
to produce warnings when it detects that a literal that is converted to a
set contains duplicate values.


> is this legal:
>
> int x = 0;
>
> {"a", "b"}.get(x)?
>

No, because the collection literal isn't subjected to a conversion to some
appropriate type.  Similarly, the following isn't legal:

3.getClass();

because the "3" isn't subjected to a boxing conversion.

Cheers,
Neal