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