/**********************************************************************

 *

 * GEOS - Geometry Engine Open Source

 * http://geos.osgeo.org

 *

 * Copyright (C) 2006 Refractions Research Inc.

 *

 * This is free software; you can redistribute and/or modify it under

 * the terms of the GNU Lesser General Public Licence as published

 * by the Free Software Foundation.

 * See the COPYING file for more information.

 *

 **********************************************************************

 *

 * Last port: index/quadtree/Quadtree.java rev. 1.16 (JTS-1.10)

 *

 **********************************************************************/

#pragma once

#include <geos/export.h>

#include <geos/geom/Envelope.h>

#include <geos/index/SpatialIndex.h> // for inheritance

#include <geos/index/quadtree/Root.h> // for composition

#include <memory>

#include <vector>

#include <string>

#ifdef _MSC_VER

#pragma warning(push)

#pragma warning(disable: 4251) // warning C4251: needs to have dll-interface to be used by clients of class

#endif

// Forward declarations

namespace geos {

namespace index {

namespace quadtree {

// class Root;

}

}

}

namespace geos {

namespace index { // geos::index

namespace quadtree { // geos::index::quadtree

/**

 * \brief

 * A Quadtree is a spatial index structure for efficient querying

 * of 2D rectangles.  If other kinds of spatial objects

 * need to be indexed they can be represented by their

 * envelopes

 *

 * The quadtree structure is used to provide a primary filter

 * for range rectangle queries.  The query() method returns a list of

 * all objects which <i>may</i> intersect the query rectangle.  Note that

 * it may return objects which do not in fact intersect.

 * A secondary filter is required to test for exact intersection.

 * Of course, this secondary filter may consist of other tests besides

 * intersection, such as testing other kinds of spatial relationships.

 *

 * This implementation does not require specifying the extent of the inserted

 * items beforehand.  It will automatically expand to accommodate any extent

 * of dataset.

 *

 * This data structure is also known as an <i>MX-CIF quadtree</i>

 * following the usage of Samet and others.

 */

class GEOS_DLL Quadtree: public SpatialIndex {

private:

    std::vector<std::unique_ptr<geom::Envelope>> newEnvelopes;

    void collectStats(const geom::Envelope& itemEnv);

    Root root;

    /**

     *  Statistics

     *

     * minExtent is the minimum envelope extent of all items

     * inserted into the tree so far. It is used as a heuristic value

     * to construct non-zero envelopes for features with zero X and/or

     * Y extent.

     * Start with a non-zero extent, in case the first feature inserted has

     * a zero extent in both directions.  This value may be non-optimal, but

     * only one feature will be inserted with this value.

     */

    double minExtent;

public:

    /**

     * \brief

     * Ensure that the envelope for the inserted item has non-zero extents.

     *

     * Use the current minExtent to pad the envelope, if necessary.

     * Can return a new Envelope or the given one (casted to non-const).

     */

    static geom::Envelope* ensureExtent(const geom::Envelope* itemEnv,

                                        double minExtent);

    /**

     * \brief

     * Constructs a Quadtree with zero items.

     */

    Quadtree()

        :

        root(),

        minExtent(1.0)

    {}

    ~Quadtree() override = default;

    /// Returns the number of levels in the tree.

    std::size_t depth();

    /// Returns the number of items in the tree.

    std::size_t size();

    void insert(const geom::Envelope* itemEnv, void* item) override;

    /** \brief

     * Queries the tree and returns items which may lie

     * in the given search envelope.

     *

     * Precisely, the items that are returned are all items in the tree

     * whose envelope <b>may</b> intersect the search Envelope.

     * Note that some items with non-intersecting envelopes may be

     * returned as well;

     * the client is responsible for filtering these out.

     * In most situations there will be many items in the tree which do not

     * intersect the search envelope and which are not returned - thus

     * providing improved performance over a simple linear scan.

     *

     * @param searchEnv the envelope of the desired query area.

     * @param ret a vector where items which may intersect the

     *        search envelope are pushed

     */

    void query(const geom::Envelope* searchEnv, std::vector<void*>& ret) override;

    /** \brief

     * Queries the tree and visits items which may lie in

     * the given search envelope.

     *

     * Precisely, the items that are visited are all items in the tree

     * whose envelope <b>may</b> intersect the search Envelope.

     * Note that some items with non-intersecting envelopes may be

     * visited as well;

     * the client is responsible for filtering these out.

     * In most situations there will be many items in the tree which do not

     * intersect the search envelope and which are not visited - thus

     * providing improved performance over a simple linear scan.

     *

     * @param searchEnv the envelope of the desired query area.

     * @param visitor a visitor object which is passed the visited items

     */

    void

    query(const geom::Envelope* searchEnv, ItemVisitor& visitor) override

    {

        /*

         * the items that are matched are the items in quads which

         * overlap the search envelope

         */

        root.visit(searchEnv, visitor);

    }

    /**

     * Removes a single item from the tree.

     *

     * @param itemEnv the Envelope of the item to be removed

     * @param item the item to remove

     * @return <code>true</code> if the item was found (and thus removed)

     */

    bool remove(const geom::Envelope* itemEnv, void* item) override;

    /// Return a list of all items in the Quadtree

    std::vector<void*>* queryAll();

    std::string toString() const;

    /**

     * Disable copy construction and assignment. Apparently needed to make this

     * class compile under MSVC. (See https://stackoverflow.com/q/29565299)

     */

    Quadtree(const Quadtree&) = delete;

    Quadtree& operator=(const Quadtree&) = delete;

    // Move constructor

    Quadtree(Quadtree&& other) noexcept :

        newEnvelopes(std::move(other.newEnvelopes)),

        root(other.root),

        minExtent(other.minExtent)

    {

        // The contents of 'other' are moved to 'this'

        // 'other' will be empty after the move

    };

    // Move assignment operator

    Quadtree& operator=(Quadtree&& other) noexcept

    {

        if (this != &other) {

            // Move the vector from 'other' to 'this'

            // 'newEnvelopes.data' will be empty after this operation

            newEnvelopes.clear();

            newEnvelopes = std::move(other.newEnvelopes);

            minExtent = other.minExtent;

            root = other.root;

        }

        return *this;

    };

};

} // namespace geos::index::quadtree

} // namespace geos::index

} // namespace geos

#ifdef _MSC_VER

#pragma warning(pop)

#endif