Mailing-List: contact commits-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@lucene.apache.org
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
From: kwright@apache.org
To: commits@lucene.apache.org
Message-Id: <199ab055b18840b78a21fa4419b435ed@git.apache.org>
Subject: lucene-solr:master: LUCENE-7270: Perofmance improvements related to
 tree structure.
Date: Tue,  3 May 2016 17:15:58 +0000 (UTC)
archived-at: Tue, 03 May 2016 17:16:00 -0000

Repository: lucene-solr
Updated Branches:
  refs/heads/master 1b746be0f -> d3d754e91


LUCENE-7270: Perofmance improvements related to tree structure.


Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/d3d754e9
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/d3d754e9
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/d3d754e9

Branch: refs/heads/master
Commit: d3d754e91de95115a105861ca4b45029f33252e2
Parents: 1b746be
Author: Karl Wright <DaddyWri@gmail.com>
Authored: Tue May 3 13:15:37 2016 -0400
Committer: Karl Wright <DaddyWri@gmail.com>
Committed: Tue May 3 13:15:37 2016 -0400

----------------------------------------------------------------------
 .../spatial3d/geom/GeoComplexPolygon.java       | 50 ++++++++++++++++----
 1 file changed, 40 insertions(+), 10 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/d3d754e9/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
index 1ee899b..e5a340b 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
@@ -16,7 +16,9 @@
  */
 package org.apache.lucene.spatial3d.geom;
 
+import java.util.Arrays;
 import java.util.List;
+import java.util.ArrayList;
 import java.util.Set;
 import java.util.HashSet;
 
@@ -33,9 +35,9 @@ import java.util.HashSet;
  */
 class GeoComplexPolygon extends GeoBasePolygon {
   
-  private final Tree xTree = new XTree();
-  private final Tree yTree = new YTree();
-  private final Tree zTree = new ZTree();
+  private final Tree xTree;
+  private final Tree yTree;
+  private final Tree zTree;
   
   private final boolean testPointInSet;
   private final GeoPoint testPoint;
@@ -82,17 +84,17 @@ class GeoComplexPolygon extends GeoBasePolygon {
 
     this.edgePoints = new GeoPoint[pointsList.size()];
     this.shapeStartEdges = new Edge[pointsList.size()];
+    final ArrayList<Edge> allEdges = new ArrayList<>();
     int edgePointIndex = 0;
     for (final List<GeoPoint> shapePoints : pointsList) {
+      allEdges.ensureCapacity(allEdges.size() + shapePoints.size());
       GeoPoint lastGeoPoint = shapePoints.get(shapePoints.size()-1);
       edgePoints[edgePointIndex] = lastGeoPoint;
       Edge lastEdge = null;
       Edge firstEdge = null;
       for (final GeoPoint thisGeoPoint : shapePoints) {
         final Edge edge = new Edge(planetModel, lastGeoPoint, thisGeoPoint);
-        xTree.add(edge);
-        yTree.add(edge);
-        zTree.add(edge);
+        allEdges.add(edge);
         // Now, link
         if (firstEdge == null) {
           firstEdge = edge;
@@ -109,6 +111,10 @@ class GeoComplexPolygon extends GeoBasePolygon {
       shapeStartEdges[edgePointIndex] = firstEdge;
       edgePointIndex++;
     }
+
+    xTree = new XTree(allEdges);
+    yTree = new YTree(allEdges);
+    zTree = new ZTree(allEdges);
   }
 
   @Override
@@ -447,10 +453,31 @@ class GeoComplexPolygon extends GeoBasePolygon {
     protected static final int GREATER = 5;
     protected static final int EXACT = 6;
     
+    private final static Edge[] NO_EDGES = new Edge[0];
+    
+    /** Create a tree.
+     * @param edges is the list of edges.
+     */
+    public Tree(final List<Edge> allEdges) {
+      final Edge[] edges = allEdges.toArray(NO_EDGES);
+      // Sort by edge length, and then by minimum value
+      Arrays.sort(edges, (left, right) -> {
+        int ret = Double.compare(getMaximum(left) - getMinimum(left), getMaximum(right) - getMinimum(right));
+        if (ret == 0) {
+          ret = Double.compare(getMinimum(left), getMinimum(right));
+        }
+        return ret;
+      });
+
+      for (final Edge edge : edges) {
+        add(edge);
+      }
+    }
+    
     /** Add a new edge to the tree.
      * @param edge is the edge to add.
      */
-    public void add(final Edge edge) {
+    private void add(final Edge edge) {
       rootNode = addEdge(rootNode, edge, getMinimum(edge), getMaximum(edge));
     }
 
@@ -646,7 +673,8 @@ class GeoComplexPolygon extends GeoBasePolygon {
   private static class ZTree extends Tree {
     public Node rootNode = null;
     
-    public ZTree() {
+    public ZTree(final List<Edge> allEdges) {
+      super(allEdges);
     }
     
     /*
@@ -673,7 +701,8 @@ class GeoComplexPolygon extends GeoBasePolygon {
    */
   private static class YTree extends Tree {
     
-    public YTree() {
+    public YTree(final List<Edge> allEdges) {
+      super(allEdges);
     }
 
     /*
@@ -700,7 +729,8 @@ class GeoComplexPolygon extends GeoBasePolygon {
    */
   private static class XTree extends Tree {
     
-    public XTree() {
+    public XTree(final List<Edge> allEdges) {
+      super(allEdges);
     }
     
     /*