Fix integer overflow issue in ZoneInfo.

The least messy fix is to change mTransitions to long[] despite
the underlying tzdata being ints. This leads to neater code than
comparing the unix time (as a long) against the first and last
element of the transitions array.

bug: 18839557

Change-Id: Ife562749e8b2160f664d566a0a2aae14a0aea36e
Add a zero-copy path for Collections.sort() on ArrayList.

Given that ArrayLists are array backed, we can sort the underlying
array in place. A similar optimisation can be applied to Vector and
CopyOnWriteArrayList but vector isn't used often enough to slow
everything else down with an instanceof check and nobody should be
daft enough to try sorting a CopyOnWriteArrayList.

Note that it's possible to apply the same optimisation to
Collections.sort(List<T>, Comparator<? super T>) but it involves a
larger refactoring to allow us to use Object[] instead of T[] and is
accompanied by a general loss of readability.

ArrayList performance improves for all array sizes :

BEFORE

Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=4} 39021.26 ns; σ=206.27 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=16} 120903.59 ns; σ=1188.88 ns @ 5 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=64} 435484.98 ns; σ=19141.88 ns @ 10 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=256} 1772876.81 ns; σ=5542.74 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=1024} 7289431.83 ns; σ=110869.13 ns @ 10 trials

AFTER

Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=4} 9161.79 ns; σ=90.04 ns @ 6 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=16} 29988.90 ns; σ=74.05 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=64} 118142.86 ns; σ=1133.52 ns @ 7 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=256} 456091.11 ns; σ=9110.18 ns @ 10 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_arrayList, arrayListLength=1024} 1851939.39 ns; σ=69542.41 ns @ 10 trials

For all other lists, there's no measurable difference for
most sizes. length == 4 is harder to be sure about, given the
large standard deviations and we'd expect the time spent in
instanceof to be larger relative to the rest of what's going on.

BEFORE

Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=4} 49002.02 ns; σ=1392.58 ns @ 10 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=16} 154967.88 ns; σ=332.29 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=64} 588207.14 ns; σ=1863.60 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=256} 2292967.79 ns; σ=4578.14 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=1024} 9299582.60 ns; σ=179459.24 ns @ 10 trials

AFTER

Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=4} 49324.98 ns; σ=240.86 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=16} 155639.91 ns; σ=215.12 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=64} 581950.81 ns; σ=938.11 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=256} 2285933.64 ns; σ=13265.42 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=Sort_vector, arrayListLength=1024} 8981475.84 ns; σ=431676.48 ns @ 10 trials

bug: 18821961

Change-Id: I30a3eaf89ff478663f555c93556167107da10873