QuadTree.java

Go to the documentation of this file.

/* *********************************************************************** *
 * project: org.matsim.*
 * QuadTree.java
 *                                                                         *
 * *********************************************************************** *
 *                                                                         *
 * copyright       : (C) 2007 by the members listed in the COPYING,        *
 *                   LICENSE and WARRANTY file.                            *
 * email           : info at matsim dot org                                *
 *                                                                         *
 * *********************************************************************** *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *   See also COPYING, LICENSE and WARRANTY file                           *
 *                                                                         *
 * *********************************************************************** */

package org.matsim.core.utils.collections;

import java.io.Serializable;
import java.util.*;

public class QuadTree<T> implements Serializable {

    private static final long serialVersionUID = 1L;

    protected Node<T> top = null;

    private int size = 0;

    private transient int modCount = 0;

    transient volatile Collection<T> values = null;

    private void incrementSize() { this.modCount++; this.size++; this.values = null; }
    private void decrementSize() { this.modCount++; this.size--; this.values = null; }

    public QuadTree(final double minX, final double minY, final double maxX, final double maxY) {
        this.top = new Node<>(minX, minY, maxX, maxY);
    }

    public boolean put(final double x, final double y, final T value) {
        if (!this.top.bounds.containsOrEquals(x, y)) {
            throw new IllegalArgumentException("cannot add a point at x=" + x + ", y=" + y + " with bounds " + this.top.bounds);
        }
        if (this.top.put(x, y, value)) {
            incrementSize();
            return true;
        }
        return false;
    }

    public boolean remove(final double x, final double y, final T value) {
        if (this.top.remove(x, y, value)) {
            decrementSize();
            return true;
        }
        return false;
    }

    public void clear() {
        this.top.clear();
        this.size = 0;
        this.modCount++;
    }

    public T getClosest(final double x, final double y) {
        return this.top.get(x, y, new MutableDouble(Double.POSITIVE_INFINITY));
    }

    public Collection<T> getDisk(final double x, final double y, final double distance) {
        return this.top.get(x, y, distance * distance, new ArrayList<>());
    }

    public Collection<T> getRing(final double x, final double y, final double rMin, final double rMax) {
        return this.top.get(x, y, rMin * rMin, rMax * rMax, new ArrayList<>());
    }

    public Collection<T> getElliptical(
            final double x1,
            final double y1,
            final double x2,
            final double y2,
            final double distance) {
        if ( Math.pow( distance , 2 ) < Math.pow( (x1 - x2), 2 ) + Math.pow( (y1 - y2) , 2 ) ) {
            throw new IllegalArgumentException( "wrong ellipse specification: distance must be greater than distance between foci."
                    +" x1="+x1
                    +" y1="+y1
                    +" x2="+x2
                    +" y2="+y2
                    +" distance="+distance );
        }
        return this.top.getElliptical(x1, y1, x2, y2, distance, new ArrayList<>());
    }


    public Collection<T> getRectangle(final Rect bounds, final Collection<T> values1) {
        return this.top.get(bounds, values1);
    }

    public Collection<T> getRectangle(final double minX, final double minY, final double maxX, final double maxY, final Collection<T> values1) {
        return getRectangle(new Rect(minX, minY, maxX, maxY), values1);
    }

    public int execute(final Rect bounds, final Executor<T> executor) {
        if (bounds == null) {
            return this.top.execute(this.top.getBounds(), executor);
        }
        return this.top.execute(bounds, executor);
    }

    public int execute(final double minX, final double minY, final double maxX, final double maxY, final Executor<T> executor) {
        return execute(new Rect(minX, minY, maxX, maxY), executor);
    }

    public int size() {
        return this.size;
    }

    public double getMinEasting() {
        return this.top.getBounds().minX;
    }

    public double getMaxEasting() {
        return this.top.getBounds().maxX;
    }

    public double getMinNorthing() {
        return this.top.getBounds().minY;
    }

    public double getMaxNorthing() {
        return this.top.getBounds().maxY;
    }

    public Collection<T> values() {
        if (this.values == null) {
            this.values = new AbstractCollection<>() {
                @Override
                public Iterator<T> iterator() {
                    return new Iterator<>() {
                        private final int expectedModCount = QuadTree.this.modCount;
                        private Leaf<T> currentLeaf = firstLeaf();
                        private int nextIndex = 0;
                        private T next = first();

                        private T first() {
                            if (this.currentLeaf == null) {
                                return null;
                            }
                            this.nextIndex = 0;
                            loadNext();
                            return this.next;
                        }

                        @Override
                        public boolean hasNext() {
                            return this.next != null;
                        }

                        @Override
                        public T next() {
                            if (this.next == null) {
                                return null;
                            }
                            if (QuadTree.this.modCount != this.expectedModCount) {
                                throw new ConcurrentModificationException();
                            }
                            T current = this.next;
                            loadNext();
                            return current;
                        }

                        private void loadNext() {
                            boolean searching = true;
                            while (searching) {
                                int size = this.currentLeaf.value != null ? 1 : this.currentLeaf.values.size();
                                if (this.nextIndex < size) {
                                    this.nextIndex++;
                                    this.next = this.currentLeaf.value != null ? this.currentLeaf.value : this.currentLeaf.values.get(this.nextIndex - 1);
                                    searching = false;
                                } else {
                                    this.currentLeaf = nextLeaf(this.currentLeaf);
                                    if (this.currentLeaf == null) {
                                        this.next = null;
                                        searching = false;
                                    } else {
                                        this.nextIndex = 0;
                                    }
                                }
                            }
                        }

                        @Override
                        public void remove() {
                            throw new UnsupportedOperationException();
                        }

                    };
                }

                @Override
                public int size() {
                    return QuadTree.this.size;
                }
            };
        }
        return this.values;
    }

    private Leaf<T> firstLeaf() {
        return this.top.firstLeaf();
    }

    private Leaf<T> nextLeaf(final Leaf<T> currentLeaf) {
        return this.top.nextLeaf(currentLeaf);
    }

    private static class MutableDouble {
        public double value;

        public MutableDouble(final double value) {
            this.value = value;
        }
    }

    private static class MutableLeaf<T> {
        public Leaf<T> value;

        public MutableLeaf(final Leaf<T> value) {
            this.value = value;
        }
    }

    public static class Rect implements Serializable {
        private static final long serialVersionUID = -837712701959689133L;
        public final double minX;
        public final double minY;
        public final double maxX;
        public final double maxY;
        public final double centerX;
        public final double centerY;

        public Rect(final double minX, final double minY, final double maxX, final double maxY) {
            this.minX = Math.min(minX, maxX);
            this.minY = Math.min(minY, maxY);
            this.maxX = Math.max(minX, maxX);
            this.maxY = Math.max(minY, maxY);
            this.centerX = (minX + maxX) / 2;
            this.centerY = (minY + maxY) / 2;
        }

        public double calcDistance(final double x, final double y) {
            double distanceX;
            double distanceY;

            if (this.minX <= x && x <= this.maxX) {
                distanceX = 0;
            } else {
                distanceX = Math.min(Math.abs(this.minX - x), Math.abs(this.maxX - x));
            }
            if (this.minY <= y && y <= this.maxY) {
                distanceY = 0;
            } else {
                distanceY = Math.min(Math.abs(this.minY - y), Math.abs(this.maxY - y));
            }

            return Math.sqrt(distanceX * distanceX + distanceY * distanceY);
        }

        public double calcDistanceSqr(final double x, final double y) {
            double distanceX;
            double distanceY;

            if (this.minX <= x && x <= this.maxX) {
                distanceX = 0;
            } else {
                distanceX = Math.min(Math.abs(this.minX - x), Math.abs(this.maxX - x));
            }
            if (this.minY <= y && y <= this.maxY) {
                distanceY = 0;
            } else {
                distanceY = Math.min(Math.abs(this.minY - y), Math.abs(this.maxY - y));
            }

            return distanceX * distanceX + distanceY * distanceY;
        }

        public double calcMaxDistanceSqr(final double x, final double y) {
            double distanceX = Math.max(Math.abs(this.minX - x), Math.abs(this.maxX - x));
            double distanceY = Math.max(Math.abs(this.minY - y), Math.abs(this.maxY - y));

            return distanceX * distanceX + distanceY * distanceY;
        }


        public boolean contains(final double x, final double y) {
            return (x >= this.minX &&
                    y >= this.minY &&
                    x < this.maxX &&
                    y < this.maxY);
        }

        public boolean containsOrEquals(final double x, final double y) {
            return (x >= this.minX &&
                    y >= this.minY &&
                    x <= this.maxX &&
                    y <= this.maxY);
        }

        public boolean containsOrEquals(final Rect rect) {
            return (rect.minX >= this.minX &&
                    rect.minY >= this.minY &&
                    rect.maxX <= this.maxX &&
                    rect.maxY <= this.maxY);
        }

        public boolean intersects(final Rect other) {
            if ((this.maxX-this.minX) < 0 || (this.maxY-this.minY) < 0) {
                return false;
            }
            return (other.maxX >= this.minX &&
                    other.maxY >= this.minY &&
                    other.minX <= this.maxX &&
                    other.minY <= this.maxY);
        }

        public Rect intersection(final Rect r) {
            double tx1 = this.minX;
            double ty1 = this.minY;
            double tx2 = this.maxX;
            double ty2 = this.maxY;
            if (this.minX < r.minX) tx1 = r.minX;
            if (this.minY < r.minY) ty1 = r.minY;
            if (tx2 > r.maxX) tx2 = r.maxX;
            if (ty2 > r.maxY) ty2 = r.maxY;
            // did they intersect at all?
            if(tx2-tx1 <=0.f || ty2-ty1 <= 0.f) return null;

            return new Rect(tx1, ty1, tx2, ty2);
        }

        public Rect union(final Rect r) {
            return new Rect( Math.min(this.minX, r.minX),
                    Math.min(this.minY, r.minY),
                    Math.max(this.maxX, r.maxX),
                    Math.max(this.maxY, r.maxY));
        }

        public Rect scale(double scaleX, double scaleY) {
            scaleY *= this.centerY - this.minY;
            scaleX *= this.centerX - this.minX;
            return new Rect(this.minX - scaleX, this.minY-scaleY, this.maxX + scaleX, this.maxY + scaleY);
        }

        @Override
        public String toString() {
            return "topLeft: ("+minX+","+minY+") bottomRight: ("+maxX+","+maxY+")";
        }

    }

    protected static class Leaf<T> implements Serializable {
        private static final long serialVersionUID = -6527830222532634476L;
        final public double x;
        final public double y;
        /* a leaf can contain one more multiple objects at the same coordinate.
         * in many cases it will be only one, so to save memory, we'll store it in "value".
         * only if actually multiple objects at the same coordinate need to be stored,
         * we create the values-list and add all objects there.
         * So either value or values is non-null. it should never be the case that both are null
         * or both are non-null. mrieser/oct2018
         */
        public T value;
        public ArrayList<T> values;

        public Leaf(final double x, final double y, final T value) {
            this.x = x;
            this.y = y;
            this.value = value;
            this.values = null;
        }
    }

    protected static class Node<T> implements Serializable {
        private static final long serialVersionUID = 8151154226742383421L;

        private static final int MAX_CHILDS = 128;

        private ArrayList<Leaf<T>> leaves = null;

        private boolean hasChilds = false;
        private Node<T> northwest = null;
        private Node<T> northeast = null;
        private Node<T> southeast = null;
        private Node<T> southwest = null;
        private final Rect bounds;

        public Node(final double minX, final double minY, final double maxX, final double maxY) {
            this.bounds = new Rect(minX, minY, maxX, maxY);
        }

        public boolean put(final Leaf<T> leaf) {
            if (this.hasChilds) return getChild(leaf.x, leaf.y).put(leaf);
            if (this.leaves == null) {
                this.leaves = new ArrayList<>();
                this.leaves.add(leaf);
                return true;
            }
            for (Leaf<T> l : this.leaves) {
                if (l.x == leaf.x && l.y == leaf.y) {
                    if (leaf.value == l.value) {
                        return false;
                    }
                    if (l.values != null) {
                        if (l.values.contains(leaf.value)) {
                            return false;
                        }
                        l.values.add(leaf.value);
                        return true;
                    }
                    if (l.value == null) {
                        l.value = leaf.value;
                        return true;
                    } else {
                        l.values = new ArrayList<>(3);
                        l.values.add(l.value);
                        l.value = null;
                        l.values.add(leaf.value);
                        return true;
                    }
                }

            }
            if (this.leaves.size() < MAX_CHILDS) {
                this.leaves.add(leaf);
                return true;
            }
            this.split();
            return getChild(leaf.x, leaf.y).put(leaf);
        }

        public boolean put(final double x, final double y, final T value) {
            return put(new Leaf<>(x, y, value));
        }

        public boolean remove(final double x, final double y, final T value) {
            if (this.hasChilds) return getChild(x, y).remove(x, y, value);
            if (this.leaves != null) {
                for (Leaf<T> leaf : this.leaves) {
                    if (leaf.x == x && leaf.y == y) {
                        if (leaf.value == value) {
                            leaf.value = null;
                            this.leaves.remove(leaf);
                            return true;
                        }
                        if (leaf.values != null) {
                            if (leaf.values.remove(value)) {
                                if (leaf.values.isEmpty()) {
                                    this.leaves.remove(leaf);
                                }
                                return true;
                            }
                        }
                    }
                }
            }
            return false;
        }

        public void clear() {
            // we could as well just set everything to null and let the
            // garbage collection do its job.
            if (this.hasChilds) {
                this.northwest.clear();
                this.northeast.clear();
                this.southeast.clear();
                this.southwest.clear();
                this.northwest = null;
                this.northeast = null;
                this.southeast = null;
                this.southwest = null;
                this.hasChilds = false;
            } else {
                if (this.leaves != null) {
                    this.leaves = null;
                }
            }
        }

        /* default */ T get(final double x, final double y, final MutableDouble bestDistanceSqr) {
            if (this.hasChilds) {
                T closest = null;
                Node<T> bestChild = this.getChild(x, y);
                if (bestChild != null) {
                    closest = bestChild.get(x, y, bestDistanceSqr);
                }
                if (bestChild != this.northwest && this.northwest.bounds.calcDistanceSqr(x, y) < bestDistanceSqr.value) {
                    T value = this.northwest.get(x, y, bestDistanceSqr);
                    if (value != null) { closest = value; }
                }
                if (bestChild != this.northeast && this.northeast.bounds.calcDistanceSqr(x, y) < bestDistanceSqr.value) {
                    T value = this.northeast.get(x, y, bestDistanceSqr);
                    if (value != null) { closest = value; }
                }
                if (bestChild != this.southeast && this.southeast.bounds.calcDistanceSqr(x, y) < bestDistanceSqr.value) {
                    T value = this.southeast.get(x, y, bestDistanceSqr);
                    if (value != null) { closest = value; }
                }
                if (bestChild != this.southwest && this.southwest.bounds.calcDistanceSqr(x, y) < bestDistanceSqr.value) {
                    T value = this.southwest.get(x, y, bestDistanceSqr);
                    if (value != null) { closest = value; }
                }
                return closest;
            }
            // no more childs, so we must contain the closest object
            T closest = null;
            if (this.leaves != null) {
                for (Leaf<T> leaf : this.leaves) {
                    double deltaX = leaf.x - x;
                    double deltaY = leaf.y - y;
                    double distanceSqr = deltaX * deltaX + deltaY * deltaY;
                    if (distanceSqr < bestDistanceSqr.value) {
                        bestDistanceSqr.value = distanceSqr;
                        closest = leaf.value != null ? leaf.value : leaf.values.get(0);
                    }
                }
            }
            return closest;
        }

        /* default */ Collection<T> getElliptical(
                final double x1,
                final double y1,
                final double x2,
                final double y2,
                final double maxDistance,
                final Collection<T> values) {
            assert Math.pow( maxDistance , 2 ) >= Math.pow( (x1 - x2), 2 ) + Math.pow( (y1 - y2) , 2 );
            if (this.hasChilds) {
                // note: this could probably be improved. The idea here
                // is NOT to dive in quadrants which we know do not contain points
                // in the ellipse.
                // This is done, but we will also dive in some quadrants not intersecting
                // the ellipse, which is just a loss of time (the sum of the minimum distances
                // to an area is always lower than the munimum of the sum of the distances,
                // and the difference can be substantial. Just not sure how efficiently
                // one can estimate the minimum of the sum of the distances).

                // this is a trick to avoid computing distance of quadrant to second focus
                // if the quandrant is already too far from first focus.
                // Some tests showed a huge improvement with this, when a large part
                // of the space has to be pruned (which is typically the case in
                // real applications). By "huge improvement", I mean several times
                // faster (how much depends on the particular instance).
                final double nw1 = this.northwest.bounds.calcDistance(x1, y1);
                if ( nw1 <= maxDistance && nw1 + this.northwest.bounds.calcDistance(x2, y2) <= maxDistance) {
                    this.northwest.getElliptical(x1, y1, x2, y2, maxDistance, values);
                }
                final double ne1 = this.northeast.bounds.calcDistance(x1, y1);
                if (ne1 <= maxDistance && ne1 + this.northeast.bounds.calcDistance(x2, y2) <= maxDistance) {
                    this.northeast.getElliptical(x1, y1, x2, y2, maxDistance, values);
                }
                final double se1 = this.southeast.bounds.calcDistance(x1, y1);
                if (se1 <= maxDistance && se1 + this.southeast.bounds.calcDistance(x2, y2) <= maxDistance) {
                    this.southeast.getElliptical(x1, y1, x2, y2, maxDistance, values);
                }
                final double sw1 = this.southwest.bounds.calcDistance(x1, y1);
                if (sw1 <= maxDistance && sw1 + this.southwest.bounds.calcDistance(x2, y2) <= maxDistance) {
                    this.southwest.getElliptical(x1, y1, x2, y2, maxDistance, values);
                }
                return values;
            }
            // no more childs, so we must contain the closest object
            if (this.leaves != null) {
                for (Leaf<T> leaf : this.leaves) {
                    final double distance1 = Math.sqrt(
                            (leaf.x - x1) * (leaf.x - x1)
                                    + (leaf.y - y1) * (leaf.y - y1));
                    // same trick as above, though it should not be useul in the vast
                    // majority of cases
                    if (distance1 <= maxDistance) {
                        final double distance2 = Math.sqrt(
                                (leaf.x - x2) * (leaf.x - x2)
                                        + (leaf.y - y2) * (leaf.y - y2));
                        if (distance1 + distance2 <= maxDistance) {
                            if (leaf.value != null) {
                                values.add(leaf.value);
                            } else {
                                values.addAll(leaf.values);
                            }
                        }
                    }
                }
            }
            return values;
        }

        /* default */ Collection<T> get(final double x, final double y, final double maxDistanceSqr, final Collection<T> values) {
            if (this.hasChilds) {
                if (this.northwest.bounds.calcDistanceSqr(x, y) <= maxDistanceSqr) {
                    this.northwest.get(x, y, maxDistanceSqr, values);
                }
                if (this.northeast.bounds.calcDistanceSqr(x, y) <= maxDistanceSqr) {
                    this.northeast.get(x, y, maxDistanceSqr, values);
                }
                if (this.southeast.bounds.calcDistanceSqr(x, y) <= maxDistanceSqr) {
                    this.southeast.get(x, y, maxDistanceSqr, values);
                }
                if (this.southwest.bounds.calcDistanceSqr(x, y) <= maxDistanceSqr) {
                    this.southwest.get(x, y, maxDistanceSqr, values);
                }
                return values;
            }
            // no more childs, so we must contain the closest object
            if (this.leaves != null) {
                for (Leaf<T> leaf : this.leaves) {
                    double distanceSqr = (leaf.x - x) * (leaf.x - x) + (leaf.y - y) * (leaf.y - y);
                    if (distanceSqr <= maxDistanceSqr) {
                        if (leaf.value != null) {
                            values.add(leaf.value);
                        } else {
                            values.addAll(leaf.values);
                        }
                    }
                }
            }
            return values;
        }

        /* default */ Collection<T> get(final double x, final double y, final double rMinSqr, final double rMaxSqr,
                                                                        Collection<T> values) {
            if (this.hasChilds) {
                stepIntoSqr(this.northwest, x, y, rMinSqr, rMaxSqr, values);
                stepIntoSqr(this.northeast, x, y, rMinSqr, rMaxSqr, values);
                stepIntoSqr(this.southeast, x, y, rMinSqr, rMaxSqr, values);
                stepIntoSqr(this.southwest, x, y, rMinSqr, rMaxSqr, values);
                return values;
            }
            // no more childs, so we must contain the closest object
            if (this.leaves != null) {
                for (Leaf<T> leaf : this.leaves) {
                    double distanceSqr = (leaf.x - x) * (leaf.x - x) + (leaf.y - y) * (leaf.y - y);
                    if (distanceSqr <= rMaxSqr && distanceSqr >= rMinSqr) {
                        if (leaf.value != null) {
                            values.add(leaf.value);
                        } else {
                            values.addAll(leaf.values);
                        }
                    }
                }
            }
            return values;
        }

        private void stepIntoSqr(Node<T> node, double x, double y, double rMinSqr, double rMaxSqr, Collection<T> values) {
            double minDistanceSqr = node.bounds.calcDistanceSqr(x, y);
            double maxDistanceSqr = node.bounds.calcMaxDistanceSqr(x, y);

            if (minDistanceSqr <= rMaxSqr && maxDistanceSqr >= rMinSqr) {
                node.get(x, y, rMinSqr, rMaxSqr, values);
            }
        }

        /* default */ Collection<T> get(final Rect bounds, final Collection<T> values) {
            if (this.hasChilds) {
                if (this.northwest.bounds.intersects(bounds)) {
                    this.northwest.get(bounds, values);
                }
                if (this.northeast.bounds.intersects(bounds)) {
                    this.northeast.get(bounds, values);
                }
                if (this.southeast.bounds.intersects(bounds)) {
                    this.southeast.get(bounds, values);
                }
                if (this.southwest.bounds.intersects(bounds)) {
                    this.southwest.get(bounds, values);
                }
                return values;
            }
            // no more childs, so we must contain the closest object
            if (this.leaves != null) {
                for (Leaf<T> leaf : this.leaves) {
                    if (bounds.containsOrEquals(leaf.x, leaf.y)) {
                        if (leaf.value != null) {
                            values.add(leaf.value);
                        } else {
                            values.addAll(leaf.values);
                        }
                    }
                }
            }
            return values;
        }

        /* default */ int execute(final Rect globalBounds, final Executor<T> executor) {
            int count = 0;
            if (this.hasChilds) {
                if (this.northwest.bounds.intersects(globalBounds)) {
                    count += this.northwest.execute(globalBounds, executor);
                }
                if (this.northeast.bounds.intersects(globalBounds)) {
                    count += this.northeast.execute(globalBounds, executor);
                }
                if (this.southeast.bounds.intersects(globalBounds)) {
                    count += this.southeast.execute(globalBounds, executor);
                }
                if (this.southwest.bounds.intersects(globalBounds)) {
                    count += this.southwest.execute(globalBounds, executor);
                }
                return count;
            }
            // no more childs, so we must contain the closest object
            if (this.leaves != null) {
                for (Leaf<T> leaf : this.leaves) {
                    if (globalBounds.contains(leaf.x, leaf.y)) {
                        if (leaf.value != null) {
                            count++;
                            executor.execute(leaf.x, leaf.y, leaf.value);
                        } else {
                            count += leaf.values.size();
                            for (T object : leaf.values) executor.execute(leaf.x, leaf.y, object);
                        }
                    }
                }
            }
            return count;
        }

        private void split() {
            this.northwest = new Node<>(this.bounds.minX, this.bounds.centerY, this.bounds.centerX, this.bounds.maxY);
            this.northeast = new Node<>(this.bounds.centerX, this.bounds.centerY, this.bounds.maxX, this.bounds.maxY);
            this.southeast = new Node<>(this.bounds.centerX, this.bounds.minY, this.bounds.maxX, this.bounds.centerY);
            this.southwest = new Node<>(this.bounds.minX, this.bounds.minY, this.bounds.centerX, this.bounds.centerY);
            this.hasChilds = true;
            if (this.leaves != null) {
                for (Leaf<T> leaf : this.leaves) {
                    getChild(leaf.x, leaf.y).put(leaf);
                }
                this.leaves= null;
            }
        }

        private Node<T> getChild(final double x, final double y) {
            if (this.hasChilds) {
                if (x < this.bounds.centerX) {
                    if (y < this.bounds.centerY)
                        return this.southwest;
                    return this.northwest;
                }
                if (y < this.bounds.centerY)
                    return this.southeast;
                return this.northeast;
            }
            return null;
        }

        /* default */ Leaf<T> firstLeaf() {
            if (this.hasChilds) {
                Leaf<T> leaf = this.southwest.firstLeaf();
                if (leaf == null) { leaf = this.northwest.firstLeaf(); }
                if (leaf == null) { leaf = this.southeast.firstLeaf(); }
                if (leaf == null) { leaf = this.northeast.firstLeaf(); }
                return leaf;
            }
            return (this.leaves == null || this.leaves.isEmpty()) ? null : this.leaves.get(0);
        }

        /* default */ boolean nextLeaf(final Leaf<T> currentLeaf, final MutableLeaf<T> nextLeaf) {
            if (this.hasChilds) {
                if (currentLeaf.x <= this.bounds.centerX && currentLeaf.y <= this.bounds.centerY) {
                    boolean found = this.southwest.nextLeaf(currentLeaf, nextLeaf);
                    if (found) {
                        if (nextLeaf.value == null) { nextLeaf.value = this.northwest.firstLeaf(); }
                        if (nextLeaf.value == null) { nextLeaf.value = this.southeast.firstLeaf(); }
                        if (nextLeaf.value == null) { nextLeaf.value = this.northeast.firstLeaf(); }
                        return true;
                    }
                }
                if (currentLeaf.x <= this.bounds.centerX && currentLeaf.y >= this.bounds.centerY) {
                    boolean found = this.northwest.nextLeaf(currentLeaf, nextLeaf);
                    if (found) {
                        if (nextLeaf.value == null) { nextLeaf.value = this.southeast.firstLeaf(); }
                        if (nextLeaf.value == null) { nextLeaf.value = this.northeast.firstLeaf(); }
                        return true;
                    }
                }
                if (currentLeaf.x >= this.bounds.centerX && currentLeaf.y <= this.bounds.centerY) {
                    boolean found = this.southeast.nextLeaf(currentLeaf, nextLeaf);
                    if (found) {
                        if (nextLeaf.value == null) { nextLeaf.value = this.northeast.firstLeaf(); }
                        return true;
                    }
                }
                if (currentLeaf.x >= this.bounds.centerX && currentLeaf.y >= this.bounds.centerY) {
                    return this.northeast.nextLeaf(currentLeaf, nextLeaf);
                }
                return false;
            }
            if (this.leaves != null) {
                int idx = this.leaves.indexOf(currentLeaf);
                if (idx >= 0) {
                    if (idx + 1 < this.leaves.size()) {
                        nextLeaf.value = this.leaves.get(idx + 1);
                    }
                    return true;
                }
            }
            return false;
        }

        public Leaf<T> nextLeaf(final Leaf<T> currentLeaf) {
            MutableLeaf<T> nextLeaf = new MutableLeaf<>(null);
            nextLeaf(currentLeaf, nextLeaf);
            return nextLeaf.value;
        }

        public Rect getBounds() {
            return this.bounds;
        }

    }

    public interface Executor<T> {
        void execute(double x, double y, T object);
    }
}