public class RTree<T> {

    public enum SeedPicker {
        LINEAR, QUADRATIC
    }

    /**
     * 每个节点包含的最大entry数目
     */
    private final int M;

    /**
     * 每个节点包含的最小entry数目
     */
    private final int m;

    /**
     * 空间的维度,如平面则为2,空间点则为3
     */
    private final int D;

    private final float[] pointDims;

    private final SeedPicker seedPicker;

    /**
     * 根节点
     */
    private Node root;

    private volatile int size;

    /**
     * 构造默认R-Tree的参数
     * DEFAULT_M : M
     * DEFAULT_m : m
     * DEFAULT_D : D
     */
    private static final int DEFAULT_M = 50;
    private static final int DEFAULT_m = 2;
    private static final int DEFAULT_D = 2;

    /**
     * 创建一颗新的R-Tree
     * 
     * @param M maximum number of entries per node
     * @param m minimum number of entries per node (except for the root node)
     * @param D the number of dimensions of the RTree.
     */
    public RTree(int M, int m, int D, SeedPicker seedPicker) {
        assert (m <= (M / 2));
        this.D = D;
        this.M = M;
        this.m = m;
        this.seedPicker = seedPicker;
        pointDims = new float[D];
        root = buildRoot(true);
    }

    public RTree(int M, int m, int D) {
        this(M, m, D, SeedPicker.LINEAR);
    }

    /**
     * 使用默认参数构造一个R-Tree
     */
    public RTree() {
        this(DEFAULT_M, DEFAULT_m, DEFAULT_D, SeedPicker.LINEAR);
    }

    /**
     * 构造根节点
     *
     * @param asLeaf : 根节点是否为叶子节点
     * @return
     */
    private Node buildRoot(boolean asLeaf) {
        float[] initCoords = new float[D];
        float[] initDimensions = new float[D];
        for (int i = 0; i < this.D; i++) {
            initCoords[i] = (float) Math.sqrt(Float.MAX_VALUE);
            initDimensions[i] = -2.0f * (float) Math.sqrt(Float.MAX_VALUE);
        }
        return new Node(initCoords, initDimensions, asLeaf);
    }

    /**
     * getter
     */
    public int getMaxEntries() {
        return M;
    }

    public int getMinEntries() {
        return m;
    }

    public int getNumDims() {
        return D;
    }

    public int size() {
        return size;
    }

    /**
     * 在R-Tee中搜索和给定矩形有重叠(overlapping)的对象
     * 
     * @param coords 矩形的一个顶点(比如左上角)
     * @param dimensions 矩形长度.
     * 返回对象List,这些对象的最小边界矩形(MBR)和给定矩形重叠
     */
    public List<T> search(float[] coords, float[] dimensions) {
        assert (coords.length == D);
        assert (dimensions.length == D);

        LinkedList<T> results = new LinkedList<T>();
        search(coords, dimensions, root, results);

        return results;
    }

    private void search(float[] coords, float[] dimensions, Node n, LinkedList<T> results) {
        if (n.leaf) {
            for (Node e : n.children) {
                if (isOverlap(coords, dimensions, e.coords, e.dimensions)) {
                    results.add(((Entry) e).entry);
                }
            }
        } else {
            for (Node c : n.children) {
                if (isOverlap(coords, dimensions, c.coords, c.dimensions)) {
                    search(coords, dimensions, c, results); //继续在孩子节点中搜索
                }
            }
        }
    }

    /**
     * 删除R-Tree中在矩形rect内的数据entry
     * 
     * @param coords : 矩形的一个顶点(比如左上角)
     * @param dimensions : 矩形长度
     * @param entry : 待删除数据
     * 删除成功返回true
     */
    public boolean delete(float[] coords, float[] dimensions, T entry) {
        assert (coords.length == D);
        assert (dimensions.length == D);
        Node l = findLeaf(root, coords, dimensions, entry);
        if (l == null) {
            System.out.println("WTF?");
            findLeaf(root, coords, dimensions, entry);
        }
        assert (l != null) : "Could not find leaf for entry to delete";
        assert (l.leaf) : "Entry is not found at leaf?!?";
        ListIterator<Node> li = l.children.listIterator();
        T removed = null;
        while (li.hasNext()) {
            @SuppressWarnings("unchecked")
            Entry e = (Entry) li.next();
            if (e.entry.equals(entry)) {
                removed = e.entry;
                li.remove();
                break;
            }
        }
        if (removed != null) {
            condenseTree(l);
            size--;
        }
        if (size == 0) {
            root = buildRoot(true);
        }
        return (removed != null);
    }

    public boolean delete(float[] coords, T entry) {
        return delete(coords, pointDims, entry);
    }

    /**
     * 查找数据 entry 对应的叶子节点
     * @param n
     * @param coords
     * @param dimensions
     * @param entry
     * @return
     */
    private Node findLeaf(Node n, float[] coords, float[] dimensions, T entry) {
        if (n.leaf) {
            for (Node c : n.children) {
                if (((Entry) c).entry.equals(entry)) {
                    return n;
                }
            }
            return null;
        } else {
            for (Node c : n.children) {
                if (isOverlap(c.coords, c.dimensions, coords, dimensions)) {
                    Node result = findLeaf(c, coords, dimensions, entry);
                    if (result != null) {
                        return result;
                    }
                }
            }
            return null;
        }
    }

    /**
     * 压缩树
     * @param n
     */
    private void condenseTree(Node n) {
        Set<Node> q = new HashSet<Node>();
        while (n != root) {
            if (n.leaf && (n.children.size() < m)) {
                q.addAll(n.children);
                n.parent.children.remove(n);
            } else if (!n.leaf && (n.children.size() < m)) {
                // probably a more efficient way to do this...
                LinkedList<Node> toVisit = new LinkedList<Node>(n.children);
                while (!toVisit.isEmpty()) {
                    Node c = toVisit.pop();
                    if (c.leaf) {
                        q.addAll(c.children);
                    } else {
                        toVisit.addAll(c.children);
                    }
                }
                n.parent.children.remove(n);
            } else {
                tighten(n);
            }
            n = n.parent;
        }
        if (root.children.size() == 0) {
            root = buildRoot(true);
        } else if ((root.children.size() == 1) && (!root.leaf)) {
            root = root.children.get(0);
            root.parent = null;
        } else {
            tighten(root);
        }
        for (Node ne : q) {
            @SuppressWarnings("unchecked")
            Entry e = (Entry) ne;
            insert(e.coords, e.dimensions, e.entry);
        }
        size -= q.size();
    }

    /**
     * 清空整个R-Tree
     */
    public void clear() {
        root = buildRoot(true);
        //让GC做剩余的事情...
    }

    /**
     * 在RTree中插入数据entry, 和矩形匹配.
     * 
     * @param coords : 矩形的一个顶点(比如左上角)
     * @param dimensions : 矩形长度
     * @param entry : 待出入数据
     */
    public void insert(float[] coords, float[] dimensions, T entry) {
        assert (coords.length == D);
        assert (dimensions.length == D);
        Entry e = new Entry(coords, dimensions, entry);
        Node l = chooseLeaf(root, e);
        l.children.add(e);
        size++;
        e.parent = l;
        if (l.children.size() > M) {
            Node[] splits = splitNode(l);
            adjustTree(splits[0], splits[1]);
        } else {
            adjustTree(l, null);
        }
    }

    /**
     * Convenience method for inserting a point
     * 
     * @param coords
     * @param entry
     */
    public void insert(float[] coords, T entry) {
        insert(coords, pointDims, entry);
    }

    private void adjustTree(Node n, Node nn) {
        if (n == root) {
            if (nn != null) {
                // build new root and add children.
                root = buildRoot(false);
                root.children.add(n);
                n.parent = root;
                root.children.add(nn);
                nn.parent = root;
            }
            tighten(root);
            return;
        }
        tighten(n);
        if (nn != null) {
            tighten(nn);
            if (n.parent.children.size() > M) {
                Node[] splits = splitNode(n.parent);
                adjustTree(splits[0], splits[1]);
            }
        }
        if (n.parent != null) {
            adjustTree(n.parent, null);
        }
    }

    private Node[] splitNode(Node n) {
        // TODO: this class probably calls "tighten" a little too often.
        // For instance the call at the end of the "while (!cc.isEmpty())" loop
        // could be modified and inlined because it's only adjusting for the addition
        // of a single node. Left as-is for now for readability.
        @SuppressWarnings("unchecked")
        Node[] nn = new RTree.Node[] { n, new Node(n.coords, n.dimensions, n.leaf) };
        nn[1].parent = n.parent;
        if (nn[1].parent != null) {
            nn[1].parent.children.add(nn[1]);
        }
        LinkedList<Node> cc = new LinkedList<Node>(n.children);
        n.children.clear();
        Node[] ss = seedPicker == SeedPicker.LINEAR ? lPickSeeds(cc) : qPickSeeds(cc);
        nn[0].children.add(ss[0]);
        nn[1].children.add(ss[1]);
        tighten(nn);
        while (!cc.isEmpty()) {
            if ((nn[0].children.size() >= m) && (nn[1].children.size() + cc.size() == m)) {
                nn[1].children.addAll(cc);
                cc.clear();
                tighten(nn); // Not sure this is required.
                return nn;
            } else if ((nn[1].children.size() >= m) && (nn[0].children.size() + cc.size() == m)) {
                nn[0].children.addAll(cc);
                cc.clear();
                tighten(nn); // Not sure this is required.
                return nn;
            }
            Node c = seedPicker == SeedPicker.LINEAR ? lPickNext(cc) : qPickNext(cc, nn);
            Node preferred;
            float e0 = getRequiredExpansion(nn[0].coords, nn[0].dimensions, c);
            float e1 = getRequiredExpansion(nn[1].coords, nn[1].dimensions, c);
            if (e0 < e1) {
                preferred = nn[0];
            } else if (e0 > e1) {
                preferred = nn[1];
            } else {
                float a0 = getArea(nn[0].dimensions);
                float a1 = getArea(nn[1].dimensions);
                if (a0 < a1) {
                    preferred = nn[0];
                } else if (e0 > a1) {
                    preferred = nn[1];
                } else {
                    if (nn[0].children.size() < nn[1].children.size()) {
                        preferred = nn[0];
                    } else if (nn[0].children.size() > nn[1].children.size()) {
                        preferred = nn[1];
                    } else {
                        preferred = nn[(int) Math.round(Math.random())];
                    }
                }
            }
            preferred.children.add(c);
            tighten(preferred);
        }
        return nn;
    }

    // Implementation of Quadratic PickSeeds
    private RTree<T>.Node[] qPickSeeds(LinkedList<Node> nn) {
        @SuppressWarnings("unchecked")
        RTree<T>.Node[] bestPair = new RTree.Node[2];
        float maxWaste = -1.0f * Float.MAX_VALUE;
        for (Node n1 : nn) {
            for (Node n2 : nn) {
                if (n1 == n2)
                    continue;
                float n1a = getArea(n1.dimensions);
                float n2a = getArea(n2.dimensions);
                float ja = 1.0f;
                for (int i = 0; i < D; i++) {
                    float jc0 = Math.min(n1.coords[i], n2.coords[i]);
                    float jc1 = Math.max(n1.coords[i] + n1.dimensions[i], n2.coords[i] + n2.dimensions[i]);
                    ja *= (jc1 - jc0);
                }
                float waste = ja - n1a - n2a;
                if (waste > maxWaste) {
                    maxWaste = waste;
                    bestPair[0] = n1;
                    bestPair[1] = n2;
                }
            }
        }
        nn.remove(bestPair[0]);
        nn.remove(bestPair[1]);
        return bestPair;
    }

    /**
     * Implementation of QuadraticPickNext
     * 
     * @param cc the children to be divided between the new nodes, one item will be removed from this list.
     * @param nn the candidate nodes for the children to be added to.
     */
    private Node qPickNext(LinkedList<Node> cc, Node[] nn) {
        float maxDiff = -1.0f * Float.MAX_VALUE;
        Node nextC = null;
        for (Node c : cc) {
            float n0Exp = getRequiredExpansion(nn[0].coords, nn[0].dimensions, c);
            float n1Exp = getRequiredExpansion(nn[1].coords, nn[1].dimensions, c);
            float diff = Math.abs(n1Exp - n0Exp);
            if (diff > maxDiff) {
                maxDiff = diff;
                nextC = c;
            }
        }
        assert (nextC != null) : "No node selected from qPickNext";
        cc.remove(nextC);
        return nextC;
    }

    // Implementation of LinearPickSeeds
    private RTree<T>.Node[] lPickSeeds(LinkedList<Node> nn) {
        @SuppressWarnings("unchecked")
        RTree<T>.Node[] bestPair = new RTree.Node[2];
        boolean foundBestPair = false;
        float bestSep = 0.0f;
        for (int i = 0; i < D; i++) {
            float dimLb = Float.MAX_VALUE, dimMinUb = Float.MAX_VALUE;
            float dimUb = -1.0f * Float.MAX_VALUE, dimMaxLb = -1.0f * Float.MAX_VALUE;
            Node nMaxLb = null, nMinUb = null;
            for (Node n : nn) {
                if (n.coords[i] < dimLb) {
                    dimLb = n.coords[i];
                }
                if (n.dimensions[i] + n.coords[i] > dimUb) {
                    dimUb = n.dimensions[i] + n.coords[i];
                }
                if (n.coords[i] > dimMaxLb) {
                    dimMaxLb = n.coords[i];
                    nMaxLb = n;
                }
                if (n.dimensions[i] + n.coords[i] < dimMinUb) {
                    dimMinUb = n.dimensions[i] + n.coords[i];
                    nMinUb = n;
                }
            }
            float sep = (nMaxLb == nMinUb) ? -1.0f : Math.abs((dimMinUb - dimMaxLb) / (dimUb - dimLb));
            if (sep >= bestSep) {
                bestPair[0] = nMaxLb;
                bestPair[1] = nMinUb;
                bestSep = sep;
                foundBestPair = true;
            }
        }
        // In the degenerate case where all points are the same, the above
        // algorithm does not find a best pair. Just pick the first 2
        // children.
        if (!foundBestPair) {
            bestPair = new RTree.Node[] { nn.get(0), nn.get(1) };
        }
        nn.remove(bestPair[0]);
        nn.remove(bestPair[1]);
        return bestPair;
    }

    /**
     * Implementation of LinearPickNext
     * 
     * @param cc the children to be divided between the new nodes, one item will be removed from this list.
     */
    private Node lPickNext(LinkedList<Node> cc) {
        return cc.pop();
    }

    private void tighten(Node... nodes) {
        assert (nodes.length >= 1) : "Pass some nodes to tighten!";
        for (Node n : nodes) {
            assert (n.children.size() > 0) : "tighten() called on empty node!";
            float[] minCoords = new float[D];
            float[] maxCoords = new float[D];
            for (int i = 0; i < D; i++) {
                minCoords[i] = Float.MAX_VALUE;
                maxCoords[i] = Float.MIN_VALUE;

                for (Node c : n.children) {
                    // we may have bulk-added a bunch of children to a node (eg. in
                    // splitNode)
                    // so here we just enforce the child->parent relationship.
                    c.parent = n;
                    if (c.coords[i] < minCoords[i]) {
                        minCoords[i] = c.coords[i];
                    }
                    if ((c.coords[i] + c.dimensions[i]) > maxCoords[i]) {
                        maxCoords[i] = (c.coords[i] + c.dimensions[i]);
                    }
                }
            }
            for (int i = 0; i < D; i++) {
                // Convert max coords to dimensions
                maxCoords[i] -= minCoords[i];
            }
            System.arraycopy(minCoords, 0, n.coords, 0, D);
            System.arraycopy(maxCoords, 0, n.dimensions, 0, D);
        }
    }

    private RTree<T>.Node chooseLeaf(RTree<T>.Node n, RTree<T>.Entry e) {
        if (n.leaf) {
            return n;
        }
        float minInc = Float.MAX_VALUE;
        Node next = null;
        for (RTree<T>.Node c : n.children) {
            float inc = getRequiredExpansion(c.coords, c.dimensions, e);
            if (inc < minInc) {
                minInc = inc;
                next = c;
            } else if (inc == minInc) {
                float curArea = 1.0f;
                float thisArea = 1.0f;
                for (int i = 0; i < c.dimensions.length; i++) {
                    curArea *= next.dimensions[i];
                    thisArea *= c.dimensions[i];
                }
                if (thisArea < curArea) {
                    next = c;
                }
            }
        }
        return chooseLeaf(next, e);
    }

    /**
     * Returns the increase in area necessary for the given rectangle to cover the given entry.
     */
    private float getRequiredExpansion(float[] coords, float[] dimensions, Node e) {
        float area = getArea(dimensions);
        float[] deltas = new float[dimensions.length];
        for (int i = 0; i < deltas.length; i++) {
            if (coords[i] + dimensions[i] < e.coords[i] + e.dimensions[i]) {
                deltas[i] = e.coords[i] + e.dimensions[i] - coords[i] - dimensions[i];
            } else if (coords[i] + dimensions[i] > e.coords[i] + e.dimensions[i]) {
                deltas[i] = coords[i] - e.coords[i];
            }
        }
        float expanded = 1.0f;
        for (int i = 0; i < dimensions.length; i++) {
            expanded *= dimensions[i] + deltas[i];
        }
        return (expanded - area);
    }

    private float getArea(float[] dimensions) {
        float area = 1.0f;
        for (int i = 0; i < dimensions.length; i++) {
            area *= dimensions[i];
        }
        return area;
    }

    private boolean isOverlap(float[] scoords, float[] sdimensions, float[] coords, float[] dimensions) {
        final float FUDGE_FACTOR = 1.001f;
        for (int i = 0; i < scoords.length; i++) {
            boolean overlapInThisDimension = false;
            if (scoords[i] == coords[i]) {
                overlapInThisDimension = true;
            } else if (scoords[i] < coords[i]) {
                if (scoords[i] + FUDGE_FACTOR * sdimensions[i] >= coords[i]) {
                    overlapInThisDimension = true;
                }
            } else if (scoords[i] > coords[i]) {
                if (coords[i] + FUDGE_FACTOR * dimensions[i] >= scoords[i]) {
                    overlapInThisDimension = true;
                }
            }
            if (!overlapInThisDimension) {
                return false;
            }
        }
        return true;
    }

    /**
     * 节点
     */
    private class Node {
        /**
         * 高维矩形的一个定点,如左下角
         */
        final float[] coords;

        /**
         * 矩形的长度
         */
        final float[] dimensions;

        /**
         * 孩子节点
         */
        final LinkedList<Node> children;

        /**
         * 是否为叶子节点
         */
        final boolean leaf;

        /**
         * 父亲节点
         */
        Node parent;

        private Node(float[] coords, float[] dimensions, boolean leaf) {
            this.coords = new float[coords.length];
            this.dimensions = new float[dimensions.length];
            System.arraycopy(coords, 0, this.coords, 0, coords.length);
            System.arraycopy(dimensions, 0, this.dimensions, 0, dimensions.length);
            this.leaf = leaf;
            children = new LinkedList<Node>();
        }
    }

    /**
     * 实体,代表一个数据项
     * 注意:不是叶子节点,其父亲才是叶子节点
     */
    private class Entry extends Node {
        /**
         * 数据
         */
        final T entry;

        public Entry(float[] coords, float[] dimensions, T entry) {
            super(coords, dimensions, true);
            this.entry = entry;
        }

        public String toString() {
            return "Entry: " + entry;
        }
    }
}