iverase commented on a change in pull request #1464:
URL: https://github.com/apache/lucene-solr/pull/1464#discussion_r418033425



##########
File path: lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
##########
@@ -665,55 +663,45 @@ assert valuesInOrderAndBounds(leafCount, 0, 
ArrayUtil.copyOfSubArray(leafValues,
     }
   }
 
-  // TODO: there must be a simpler way?
-  private void rotateToTree(int nodeID, int offset, int count, byte[] index, 
List<byte[]> leafBlockStartValues) {
-    //System.out.println("ROTATE: nodeID=" + nodeID + " offset=" + offset + " 
count=" + count + " bpd=" + bytesPerDim + " index.length=" + index.length);
-    if (count == 1) {
+  private void rotateToTree(int nodeID, int offset, int numNodes, byte[] 
index, List<byte[]> leafBlockStartValues) {
+    if (numNodes == 1) {
       // Leaf index node
-      //System.out.println("  leaf index node");
-      //System.out.println("  index[" + nodeID + "] = blockStartValues[" + 
offset + "]");
       System.arraycopy(leafBlockStartValues.get(offset), 0, index, 
nodeID*(1+bytesPerDim)+1, bytesPerDim);
-    } else if (count > 1) {
-      // Internal index node: binary partition of count
-      int countAtLevel = 1;
-      int totalCount = 0;
-      while (true) {
-        int countLeft = count - totalCount;
-        //System.out.println("    cycle countLeft=" + countLeft + " 
coutAtLevel=" + countAtLevel);
-        if (countLeft <= countAtLevel) {
-          // This is the last level, possibly partially filled:
-          int lastLeftCount = Math.min(countAtLevel/2, countLeft);
-          assert lastLeftCount >= 0;
-          int leftHalf = (totalCount-1)/2 + lastLeftCount;
-
-          int rootOffset = offset + leftHalf;
-          /*
-          System.out.println("  last left count " + lastLeftCount);
-          System.out.println("  leftHalf " + leftHalf + " rightHalf=" + 
(count-leftHalf-1));
-          System.out.println("  rootOffset=" + rootOffset);
-          */
-
-          System.arraycopy(leafBlockStartValues.get(rootOffset), 0, index, 
nodeID*(1+bytesPerDim)+1, bytesPerDim);
-          //System.out.println("  index[" + nodeID + "] = blockStartValues[" + 
rootOffset + "]");
-
-          // TODO: we could optimize/specialize, when we know it's simply 
fully balanced binary tree
-          // under here, to save this while loop on each recursion
-
-          // Recurse left
-          rotateToTree(2*nodeID, offset, leftHalf, index, 
leafBlockStartValues);
-
-          // Recurse right
-          rotateToTree(2*nodeID+1, rootOffset+1, count-leftHalf-1, index, 
leafBlockStartValues);
-          return;
-        }
-        totalCount += countAtLevel;
-        countAtLevel *= 2;
-      }
+    } else if (numNodes > 1) {
+      // Internal index node
+      // numNodes + 1 is the number of leaves
+      // -1 because there is one less inner node
+      int leftHalf = getNumLeftLeafNodes(numNodes + 1) - 1;
+      int rootOffset = offset + leftHalf;
+
+      System.arraycopy(leafBlockStartValues.get(rootOffset), 0, index, 
nodeID*(1+bytesPerDim)+1, bytesPerDim);
+
+      // Recurse left
+      rotateToTree(2*nodeID, offset, leftHalf, index, leafBlockStartValues);
+      // Recurse right
+      rotateToTree(2*nodeID+1, rootOffset+1, numNodes-leftHalf-1, index, 
leafBlockStartValues);
     } else {
-      assert count == 0;
+      assert numNodes == 0;
     }
   }
 
+  private int getNumLeftLeafNodes(int numLeaves) {
+    assert numLeaves > 1: "getNumLeftLeaveNodes() called with " + numLeaves;
+    // return the level that can be filled with this number of leaves
+    int lastFullLevel = 31 - Integer.numberOfLeadingZeros(numLeaves);
+    // how many leaf nodes are in the full level
+    int leavesFullLevel = 1 << lastFullLevel;
+    // half of the leaf nodes from the full level goes to the left
+    int numLeftLeafNodes = leavesFullLevel / 2;
+    // leaf nodes that do not fit in the full level
+    int unbalancedLeafNodes = numLeaves - leavesFullLevel;
+    // distribute unbalanced leaf nodes
+    numLeftLeafNodes += Math.min(unbalancedLeafNodes, numLeftLeafNodes);
+    // we should always place unbalanced leaf nodes on the left
+    assert numLeftLeafNodes >= numLeaves - numLeftLeafNodes;

Review comment:
       needs to be `<=` to support the case of a balanced tree. 




----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
[email protected]



---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to