/* Copyright (c) 2015-2016 Boundless and others.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Distribution License v1.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/org/documents/edl-v10.html
 *
 * Contributors:
 * Gabriel Roldan (Boundless) - initial implementation
 */
package org.locationtech.geogig.model.internal;

import java.util.ArrayList;
import java.util.List;

import org.eclipse.jdt.annotation.Nullable;
import org.locationtech.geogig.model.Node;
import org.locationtech.geogig.model.RevTree;

import com.google.common.base.Optional;
import com.vividsolutions.jts.geom.Envelope;

class QuadTreeClusteringStrategy extends ClusteringStrategy {

    private final Envelope maxBounds;

    private final int maxDepth;

    public QuadTreeClusteringStrategy(RevTree original, DAGStorageProvider storageProvider,
            Envelope maxBounds, int maxDepth) {
        super(original, storageProvider);
        this.maxBounds = maxBounds;
        this.maxDepth = maxDepth;
    }

    // @Override
    // protected int maxDepth() {
    // return 12;
    // }
    //
    @Override
    protected int maxBuckets(final int depthIndex) {
        return 4;
    }

    @Override
    public int normalizedSizeLimit(final int depthIndex) {
        return 128;
    }

    public int getMaxDepth() {
        return maxDepth;
    }

    public Envelope getMaxBound() {
        return maxBounds;
    }

    @Override
    public @Nullable QuadTreeNodeId computeId(final Node node) {
        Optional<Envelope> bounds = node.bounds();
        if (!bounds.isPresent() || bounds.get().isNull()) {
            return null; //no bounds -> not in tree
        }
        return computeIdInternal(node, bounds.get());
    }

    private QuadTreeNodeId computeIdInternal(Node node, Envelope nodeBounds) {

        final int maxDepth = this.maxDepth;
        List<Quadrant> quadrantsByDepth = new ArrayList<>(maxDepth);

        final Quadrant[] quadrants = QuadTreeNodeId.QUADRANTS;

        Envelope parentQuadrantBounds = this.maxBounds;

        for (int depth = 0; depth < maxDepth; depth++) {
            for (int q = 0; q < 4; q++) {
                Quadrant quadrant = quadrants[q];
                Envelope qBounds = quadrant.slice(parentQuadrantBounds);
                if (qBounds.contains(nodeBounds)) {
                    quadrantsByDepth.add(quadrant);
                    parentQuadrantBounds = qBounds;
                    break;
                }
            }
        }

        Quadrant[] nodeQuadrants = quadrantsByDepth.toArray(new Quadrant[quadrantsByDepth.size()]);
        return new QuadTreeNodeId(node.getName(), nodeQuadrants);
    }

}
@@ -703,16 +703,1751 @@
 elope;%0A%0A
+%0A/**%0A *  This class determines how the quadtree clustering strategy puts features in the tree.%0A *%0A *  NOTE: This also supports polygons/lines (i.e. non-point objects).%0A *        Each feature is only put in ONE location in the tree - the quad that it%0A *        is fully enclosed by (which might be the root node).%0A *%0A *  NOTE: if the feature doesn't have a bounds (i.e. null or empty), then it is%0A *        NOT put in the tree (null QuadTreeNodeId).%0A *%0A *  The main entry point is computeId(), which returns a QuadTreeNodeId that defines%0A *  where that Node should be in the QuadTree.%0A *  The QuadTreeNodeId contains a list of Quandrants defining which quadrant the feature%0A *  lies completely inside for EACH level of the quadtree.%0A *%0A *  If QuadTreeNodeId contains quadrants NE, then SE, then NW then it means that:%0A *%0A *  The feature is completely in the NE quadrant for the %22world%22 (level 0).%0A *%0A *  Looking at the world's NE quadrant and subdividing it into 4 quads,%0A *   the feature would be fully in the SE quadrant (level 1).%0A *%0A *  The world's NE quadrant (level 0), then that quad's sub SE quadrant (level 1),%0A *  the feature will be contains in that quad's NW quad (level 2).%0A *%0A *  This continues until;%0A *     + the max depth of the tree is reached%0A *     + the feature in not fully contained in a single quad%0A *%0A *  Typically, large features will need to be contained %22higher%22 up in the tree.%0A *  However, this can happen with very small features that are %22unlucky%22 enough to cross%0A *  ANY quad boundary.  If this happens a lot, then the tree could become more degenerative%0A *  and have large numbers of features associated with a single node that can NOT be moved%0A *  into %22lower%22 level nodes in the hierarchy.%0A *%0A *%0A */%0A
 class Qu
@@ -2836,92 +2836,8 @@
  %7D%0A%0A
-    // @Override%0A    // protected int maxDepth() %7B%0A    // return 12;%0A    // %7D%0A    //
 %0A   

add comment to QuadTreeClusteringStrategy