Home | History | Annotate | Download | only in core 
      1 
      2 /*
      3  * Copyright 2012 Google Inc.
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 
      9 #ifndef SkBBoxHierarchy_DEFINED
     10 #define SkBBoxHierarchy_DEFINED
     11 
     12 #include "SkRect.h"
     13 #include "SkTDArray.h"
     14 #include "SkRefCnt.h"
     15 
     16 /**
     17  * Interface for a client class that implements utility methods needed
     18  * by SkBBoxHierarchy that require intrinsic knowledge of the data
     19  * object type that is stored in the bounding box hierarchy.
     20  */
     21 class SkBBoxHierarchyClient {
     22 public:
     23     virtual ~SkBBoxHierarchyClient() {}
     24 
     25     /**
     26      * Implements a rewind stop condition used by rewindInserts
     27      * Must returns true if 'data' points to an object that should be re-wound
     28      * by rewinfInserts.
     29      */
     30     virtual bool shouldRewind(void* data) = 0;
     31 };
     32 
     33 /**
     34  * Interface for a spatial data structure that associates user data pointers with axis-aligned
     35  * bounding boxes, and allows efficient retrieval of intersections with query rectangles.
     36  */
     37 class SkBBoxHierarchy : public SkRefCnt {
     38 public:
     39     SK_DECLARE_INST_COUNT(SkBBoxHierarchy)
     40 
     41     SkBBoxHierarchy() : fClient(NULL) {}
     42 
     43     /**
     44      * Insert a data pointer and corresponding bounding box
     45      * @param data The data pointer, may be NULL
     46      * @param bounds The bounding box, should not be empty
     47      * @param defer Whether or not it is acceptable to delay insertion of this element (building up
     48      *        an entire spatial data structure at once is often faster and produces better
     49      *        structures than repeated inserts) until flushDeferredInserts is called or the first
     50      *        search.
     51      */
     52     virtual void insert(void* data, const SkRect& bounds, bool defer = false) = 0;
     53 
     54     /**
     55      * If any insertions have been deferred, this forces them to be inserted
     56      */
     57     virtual void flushDeferredInserts() = 0;
     58 
     59     /**
     60      * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'
     61      */
     62     virtual void search(const SkRect& query, SkTDArray<void*>* results) const = 0;
     63 
     64     virtual void clear() = 0;
     65 
     66     /**
     67      * Gets the number of insertions actually made (does not include deferred insertions)
     68      */
     69     virtual int getCount() const = 0;
     70 
     71     /**
     72      * Returns the depth of the currently allocated tree. The root node counts for 1 level,
     73      * so it should be 1 or more if there's a root node. This information provides details
     74      * about the underlying structure, which is useful mainly for testing purposes.
     75      *
     76      * Returns 0 if there are currently no nodes in the tree.
     77      * Returns -1 if the structure isn't a tree.
     78      */
     79     virtual int getDepth() const = 0;
     80 
     81     /**
     82      * Rewinds all the most recently inserted data elements until an element
     83      * is encountered for which client->shouldRewind(data) returns false. May
     84      * not rewind elements that were inserted prior to the last call to
     85      * flushDeferredInserts.
     86      */
     87     virtual void rewindInserts() = 0;
     88 
     89     void setClient(SkBBoxHierarchyClient* client) { fClient = client; }
     90 
     91 protected:
     92     SkBBoxHierarchyClient* fClient;
     93 
     94 private:
     95     typedef SkRefCnt INHERITED;
     96 };
     97 
     98 #endif
     99