Initial import.
Performance improvements to S2Loop:
1. We now cache the edge index in an instance field as the C++ library does, so we don't calculate it more than once.
2. We now use a vertex index to improve findVertex() performance from O(n) to O(1), as the C++ library does.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=24293413
This CL replaces the edge index data structure, a
TreeMap<S2CellId,TreeSet<Integer>>, with an alternate that is an order of
magnitude smaller and faster. Inspiration for this work is owed to Frank
Warmerdam, who first recognized the performance consequences of the TreeMap as
implemented in Java.

Storing the index this way requires 10 fewer references for all edges A that are
alone in their cell, and 5 fewer references for all edges B that share a cell.
So assuming 64 bits/reference, this saves 80*size(A)+40*size(B) bytes. With the
consideration that A>>B for most large real world polygons, the RAM savings here
are quite significant.

Querying the index this way is also significantly faster. We got the submap of
the tree under the cell and tested the size of the submap, but because the cell
testing starts at the top and therefore the submaps initially enclose most of
the loop's edges, and because size() is a linear operation on a TreeMap's
submap, this made index queries linear on the number of elements instead of the
expected O(log n).  The double binary search to find the edges of the query
region is truly O(log N) because size() on a subList() is O(1).

The javatests suite passed.  A robust set of measurements was taken against the
old and new algorithms with millions of real GT polygons. The plot of all these
measurements shows quadratic and nearly linear curves for the old and new data
structures, respectively. At the low end, constructing S2Polygons with loops
just big enough to require an edge index takes essentially the same time as
before. Anything above about 5000 vertices is several times faster. And at the
high end, constructing huge country polygons, a process that was taking over a
minute for the bad cases now takes milliseconds.

Incredible find Frank!
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=24623432
Modify S2EdgeIndex to prune in "XYZ" instead of longitude as it is much
cheaper to compute from S2Point x/y/z.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=24686270
Use PrimitiveType.valueOf() or autoboxing (which uses #valueOf) instead of new PrimitiveType(primitive) to
enable caching of common primitive values.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=24780147
The checkEdgeCrossings() method now uses the edge index of the context loop, instead of iterating over the product of all edges against all other edges filtered only by bounding volume. This method is integral to the performance of intersects(), contains(), containsOrCrosses(), etc. This matches the c++ algorithm in the corresponding method S2Loop::AreBoundariesCrossing.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=24938116
Removed DoubleMath from geometry package and inlined the one function that was
actually ever being invoked into S2.java.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=24952377
A more complex CL to avoid exposing the 'bounds' arrays from several of the
geometry class (paving the way for them to be made immutable later).
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=24952612
Needing owners approval for removing final keyword from S2LatLngRect in order to
fix broken build (http://test/ui#p=geo.gt) of java/com/google/geo/gt/geometry/GTLatLngRect.java
(introduced by CL 24952612)

Tested:
javatests/com/google/common/geometry:all
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=24955423
A tidyup CL for the geometry package. Each change in the CL is isolated to the
file it is in, so each file can be reviewed independantly.

Basically this tackles some very low hanging fruit with respect to immutability
and some minor style issues.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=24987273
Made 'constant' classes fully immutable by either removing or wrapping final
static arrays.

The IJ_TO_POS array was never being called so for now I removed it. We can
trivially add it back (with appropriate lookup function) if we need it later.

The other arrays were wrapped and given (hopefully) better JavaDoc.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=25078833
Made S1Interval and R1Interval immutable.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=25081675
Automatic refactoring to encapsulate fields of R2Vector.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=25130844
Split S2Edge and UndirectedEdge up to make equals() method correct.
Before this CL it was possible to have instances of S2Edge such that:

a.equals(b) ==/==> b.equals(a)
b.equals(a) && b.equals(c) ==/==> a.equals(c)

Undirected edges are just fundamentally a different type to an S2Edge
and should be treated as such. Additionally they are only used privately
in one place and never using polymorphic behaviour.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=25140523
Removing very slow precondition checks. Removing these yields 10%
speedup of S2Polygon.isValid().

This particular hot spot was identified using YourKit profiler.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=25256987
Per discussion with kirilll, some checks that we desire to run at debug time only have been converted to asserts, and commented out pending an answer from the java libraries team on how best to handle debug time only checks.  One of these changes overlaps a change started by ikaushan in CL 25025671 -- hopefully he beats me to the punch.

S2EdgeIndex incorrectly copied the S2 Minimum Width metric, rather than referring to the metric in S2Projections.  This change should have no effect, except in the case that the projection in S2 is changed, in which case it may work fine now, but would certainly have been incredibly wrong before.

Vital performance fixes:

- Several classes and methods are now final, to avoid subclasses tampering with them and/or to allow the jvm to apply additional runtime optimizations.

- Fixed performance of S2PolygonBuilder#assembleLoop(), which was removing N vertices from the start of an ArrayList *one at a time*, by calling ArrayList.remove(0) N times.  Which of course takes N*list.size() steps, aka very quadratic performance in the common case of many loops in the builder. Instead we now call list.subList(n, list.size()), to just skip past the vertices we don't care about.

- Fixed S2Polygon.S2PolygonIndex creating a copy of the whole array of vertices in *every call* to edgeFromTo(), because S2Loop's copy constructor was being used, for no apparent reason, which clones the vertices. Since edgeFromTo() is called twice per vertex to create the polygon index, a polygon with N vertices was inadverdantly copying 2*N^2 vertices to build the polygon index.

- Fixed performance of S2Polygon#clipBoundary(), which was testing every vertex of a polygon b for containment in polygon a, only to emit a log message that essentially never occurs.  In C++, this check is a debug time only check, so the pattern has been followed of making this a commented-out assertion instead of doing this extremely expensive check in production code.  Also greatly simplified the addition of edges to the S2PolygonBuilder by relying on the checks already being done in the builder.

- Fixed performance of S2Loop#vertex(int), which was doing a check before indexing into the vertices array, which itself does a range check. Since we don't need or want want both checks, the array dereference exception is caught and rethrown so the external behavior of the method is unchanged, but it is now significantly faster.

- Fixed performance of S2Polygon.S2LoopSequenceIndex, which was suffering from using List<Integer>. By using int[] instead, we save extra method calls and a lot of boxing/unboxing in this performance critical area.

- S2EdgeIndex now stores cells and edges more efficiently in parallel arrays, and edge lookups have been made significantly faster by a local implementation of binary search.

- S2EdgeIndex methods getEdgesInParentCells and getEdgesInChildrenCells now take a Set instead of a List that is then filtered through a set. This saves an extra copy of all the edges, and keeps us from accumulating redundant copies of the same edge as the search progresses.
-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=25397727
Inline checkEqualsAndHashCodeMethods calls in preparation for deprecating the method.

-------------
Created by MOE: http://code.google.com/p/moe-java
MOE_MIGRATED_REVID=25471702
Merge branch 'master' of github.com:pwheimann/s2-geometry-library-java