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 SkTileGrid_DEFINED
     10 #define SkTileGrid_DEFINED
     11 
     12 #include "SkBBoxHierarchy.h"
     13 #include "SkPictureStateTree.h"
     14 #include "SkTileGridPicture.h" // for TileGridInfo
     15 
     16 /**
     17  * Subclass of SkBBoxHierarchy that stores elements in buckets that correspond
     18  * to tile regions, disposed in a regular grid.  This is useful when the tile
     19  * structure that will be use in search() calls is known prior to insertion.
     20  * Calls to search will return in constant time.
     21  *
     22  * Note: Current implementation of search() only supports looking-up regions
     23  * that are an exact match to a single tile.  Implementation could be augmented
     24  * to support arbitrary rectangles, but performance would be sub-optimal.
     25  */
     26 class SkTileGrid : public SkBBoxHierarchy {
     27 public:
     28     typedef void* (*SkTileGridNextDatumFunctionPtr)(SkTDArray<void*>** tileData, SkTDArray<int>& tileIndices);
     29 
     30     SkTileGrid(int xTileCount, int yTileCount, const SkTileGridPicture::TileGridInfo& info,
     31         SkTileGridNextDatumFunctionPtr nextDatumFunction);
     32 
     33     virtual ~SkTileGrid();
     34 
     35     /**
     36      * Insert a data pointer and corresponding bounding box
     37      * @param data The data pointer, may be NULL
     38      * @param bounds The bounding box, should not be empty
     39      * @param defer Ignored, TileArray does not defer insertions
     40      */
     41     virtual void insert(void* data, const SkIRect& bounds, bool) SK_OVERRIDE;
     42 
     43     virtual void flushDeferredInserts() SK_OVERRIDE {};
     44 
     45     /**
     46      * Populate 'results' with data pointers corresponding to bounding boxes that intersect 'query'
     47      * The query argument is expected to be an exact match to a tile of the grid
     48      */
     49     virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
     50 
     51     virtual void clear() SK_OVERRIDE;
     52 
     53     /**
     54      * Gets the number of insertions
     55      */
     56     virtual int getCount() const SK_OVERRIDE;
     57 
     58     virtual void rewindInserts() SK_OVERRIDE;
     59 
     60     // Used by search() and in SkTileGridHelper implementations
     61     enum {
     62         kTileFinished = -1,
     63     };
     64 private:
     65     SkTDArray<void*>& tile(int x, int y);
     66 
     67     int fXTileCount, fYTileCount, fTileCount;
     68     SkTileGridPicture::TileGridInfo fInfo;
     69     SkTDArray<void*>* fTileData;
     70     int fInsertionCount;
     71     SkIRect fGridBounds;
     72     SkTileGridNextDatumFunctionPtr fNextDatumFunction;
     73 
     74     friend class TileGridTest;
     75     typedef SkBBoxHierarchy INHERITED;
     76 };
     77 
     78 /**
     79  * Generic implementation for SkTileGridNextDatumFunctionPtr. user code may instantiate
     80  * this template to get a valid SkTileGridNextDatumFunction implementation
     81  *
     82  * Returns the next element of tileData[i][tileIndices[i]] for all i and advances
     83  * tileIndices[] past them. The order in which data are returned by successive
     84  * calls to this method must reflect the order in which the were originally
     85  * recorded into the tile grid.
     86  *
     87  * \param tileData array of pointers to arrays of tile data
     88  * \param tileIndices per-tile data indices, indices are incremented for tiles that contain
     89  *     the next datum.
     90  * \tparam T a type to which it is safe to cast a datum and that has an operator <
     91  *     such that 'a < b' is true if 'a' was inserted into the tile grid before 'b'.
     92  */
     93 template <typename T>
     94 void* SkTileGridNextDatum(SkTDArray<void*>** tileData, SkTDArray<int>& tileIndices) {
     95     T* minVal = NULL;
     96     int tileCount = tileIndices.count();
     97     int minIndex = tileCount;
     98     int maxIndex = 0;
     99     // Find the next Datum; track where it's found so we reduce the size of the second loop.
    100     for (int tile = 0; tile < tileCount; ++tile) {
    101         int pos = tileIndices[tile];
    102         if (pos != SkTileGrid::kTileFinished) {
    103             T* candidate = (T*)(*tileData[tile])[pos];
    104             if (NULL == minVal || (*candidate) < (*minVal)) {
    105                 minVal = candidate;
    106                 minIndex = tile;
    107                 maxIndex = tile;
    108             } else if (!((*minVal) < (*candidate))) {
    109                 // We don't require operator==; if !(candidate<minVal) && !(minVal<candidate),
    110                 // candidate==minVal and we have to add this tile to the range searched.
    111                 maxIndex = tile;
    112             }
    113         }
    114     }
    115     // Increment indices past the next datum
    116     if (minVal != NULL) {
    117         for (int tile = minIndex; tile <= maxIndex; ++tile) {
    118             int pos = tileIndices[tile];
    119             if (pos != SkTileGrid::kTileFinished && (*tileData[tile])[pos] == minVal) {
    120                 if (++(tileIndices[tile]) >= tileData[tile]->count()) {
    121                     tileIndices[tile] = SkTileGrid::kTileFinished;
    122                 }
    123             }
    124         }
    125         return minVal;
    126     }
    127     return NULL;
    128 }
    129 
    130 #endif
    131