/*
 * Copyright 2014 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#ifndef SkQuadTree_DEFINED
#define SkQuadTree_DEFINED

#include "SkRect.h"
#include "SkTDArray.h"
#include "SkBBoxHierarchy.h"

/**
 * An QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles
 * in which each internal node has exactly four children.
 *
 * For more details see:
 *
 * http://en.wikipedia.org/wiki/Quadtree
 */
class SkQuadTree : public SkBBoxHierarchy {
public:
    SK_DECLARE_INST_COUNT(SkQuadTree)

    /**
     * Create a new QuadTree
     */
    static SkQuadTree* Create(const SkIRect& bounds);
    virtual ~SkQuadTree();

    /**
     * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
     * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
     * a large batch of nodes at once, which tends to be faster and produce a better tree).
     *  @param data The data value
     *  @param bounds The corresponding bounding box
     *  @param defer Can this insert be deferred? (this may be ignored)
     */
    virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;

    /**
     * If any inserts have been deferred, this will add them into the tree
     */
    virtual void flushDeferredInserts() SK_OVERRIDE {}

    /**
     * Given a query rectangle, populates the passed-in array with the elements it intersects
     */
    virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;

    virtual void clear() SK_OVERRIDE;

    /**
     * Gets the depth of the tree structure
     */
    virtual int getDepth() const SK_OVERRIDE;

    /**
     * This gets the insertion count (rather than the node count)
     */
    virtual int getCount() const SK_OVERRIDE { return fCount; }

    virtual void rewindInserts() SK_OVERRIDE;

private:
    class QuadTreeNode;

    SkQuadTree(const SkIRect& bounds);

    // This is the count of data elements (rather than total nodes in the tree)
    int fCount;

    QuadTreeNode* fRoot;

    typedef SkBBoxHierarchy INHERITED;
};

#endif