src/core/SkQuadTree.h

/*
 * 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"
#include "SkTInternalSList.h"
#include "SkTObjectPool.h"

/**
 * A 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)

    /**
     * Quad tree constructor.
     * @param bounds The bounding box for the root of the quad tree.
     *               giving the quad tree bounds that fall outside the root
     *               bounds may result in pathological but correct behavior.
     */
    SkQuadTree(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) const 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 fEntryPool.allocated() - fEntryPool.available();
    }

    virtual void rewindInserts() SK_OVERRIDE;

private:
    struct Entry {
        Entry() : fData(NULL) {}
        SkIRect fBounds;
        void* fData;
        SK_DECLARE_INTERNAL_SLIST_INTERFACE(Entry);
    };

    static const int kChildCount = 4;

    struct Node {
        Node() {
            for (int index=0; index<kChildCount; ++index) {
                fChildren[index] = NULL;
            }
        }
        SkTInternalSList<Entry> fEntries;
        SkIRect fBounds;
        SkIPoint fSplitPoint; // Only valid if the node has children.
        Node* fChildren[kChildCount];
        SK_DECLARE_INTERNAL_SLIST_ADAPTER(Node, fChildren[0]);
    };

    SkTObjectPool<Entry> fEntryPool;
    SkTObjectPool<Node> fNodePool;
    Node* fRoot;
    SkIRect fRootBounds;
    SkTInternalSList<Entry> fDeferred;

    void insert(Node* node, Entry* entry);
    void split(Node* node);
    void search(Node* node, const SkIRect& query, SkTDArray<void*>* results) const;
    void clear(Node* node);
    int getDepth(Node* node) const;

    typedef SkBBoxHierarchy INHERITED;
};

#endif