michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public michael@0: * License, v. 2.0. If a copy of the MPL was not distributed with this michael@0: * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ michael@0: michael@0: michael@0: #include "nsRegion.h" michael@0: #include "nsPrintfCString.h" michael@0: #include "nsTArray.h" michael@0: michael@0: michael@0: bool nsRegion::Contains(const nsRegion& aRgn) const michael@0: { michael@0: // XXX this could be made faster michael@0: nsRegionRectIterator iter(aRgn); michael@0: while (const nsRect* r = iter.Next()) { michael@0: if (!Contains (*r)) { michael@0: return false; michael@0: } michael@0: } michael@0: return true; michael@0: } michael@0: michael@0: bool nsRegion::Intersects(const nsRect& aRect) const michael@0: { michael@0: // XXX this could be made faster michael@0: nsRegionRectIterator iter(*this); michael@0: while (const nsRect* r = iter.Next()) { michael@0: if (r->Intersects(aRect)) { michael@0: return true; michael@0: } michael@0: } michael@0: return false; michael@0: } michael@0: michael@0: void nsRegion::Inflate(const nsMargin& aMargin) michael@0: { michael@0: int n; michael@0: pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n); michael@0: for (int i=0; i= 1, "Invalid max rect count"); michael@0: michael@0: if (GetNumRects() <= aMaxRects) michael@0: return; michael@0: michael@0: pixman_box32_t *boxes; michael@0: int n; michael@0: boxes = pixman_region32_rectangles(&mImpl, &n); michael@0: michael@0: // Try combining rects in horizontal bands into a single rect michael@0: int dest = 0; michael@0: for (int src = 1; src < n; src++) michael@0: { michael@0: // The goal here is to try to keep groups of rectangles that are vertically michael@0: // discontiguous as separate rectangles in the final region. This is michael@0: // simple and fast to implement and page contents tend to vary more michael@0: // vertically than horizontally (which is why our rectangles are stored michael@0: // sorted by y-coordinate, too). michael@0: // michael@0: // Note: if boxes share y1 because of the canonical representation they michael@0: // will share y2 michael@0: while ((src < (n)) && boxes[dest].y1 == boxes[src].y1) { michael@0: // merge box[i] and box[i+1] michael@0: boxes[dest].x2 = boxes[src].x2; michael@0: src++; michael@0: } michael@0: if (src < n) { michael@0: dest++; michael@0: boxes[dest] = boxes[src]; michael@0: } michael@0: } michael@0: michael@0: uint32_t reducedCount = dest+1; michael@0: // pixman has a special representation for michael@0: // regions of 1 rectangle. So just use the michael@0: // bounds in that case michael@0: if (reducedCount > 1 && reducedCount <= aMaxRects) { michael@0: // reach into pixman and lower the number michael@0: // of rects stored in data. michael@0: mImpl.data->numRects = reducedCount; michael@0: } else { michael@0: *this = GetBounds(); michael@0: } michael@0: } michael@0: michael@0: // compute the covered area difference between two rows. michael@0: // by iterating over both rows simultaneously and adding up michael@0: // the additional increase in area caused by extending each michael@0: // of the rectangles to the combined height of both rows michael@0: static uint32_t ComputeMergedAreaIncrease(pixman_box32_t *topRects, michael@0: pixman_box32_t *topRectsEnd, michael@0: pixman_box32_t *bottomRects, michael@0: pixman_box32_t *bottomRectsEnd) michael@0: { michael@0: uint32_t totalArea = 0; michael@0: struct pt { michael@0: int32_t x, y; michael@0: }; michael@0: michael@0: michael@0: pt *i = (pt*)topRects; michael@0: pt *end_i = (pt*)topRectsEnd; michael@0: pt *j = (pt*)bottomRects; michael@0: pt *end_j = (pt*)bottomRectsEnd; michael@0: bool top = false; michael@0: bool bottom = false; michael@0: michael@0: int cur_x = i->x; michael@0: bool top_next = top; michael@0: bool bottom_next = bottom; michael@0: //XXX: we could probably simplify this condition and perhaps move it into the loop below michael@0: if (j->x < cur_x) { michael@0: cur_x = j->x; michael@0: j++; michael@0: bottom_next = !bottom; michael@0: } else if (j->x == cur_x) { michael@0: i++; michael@0: top_next = !top; michael@0: bottom_next = !bottom; michael@0: j++; michael@0: } else { michael@0: top_next = !top; michael@0: i++; michael@0: } michael@0: michael@0: int topRectsHeight = topRects->y2 - topRects->y1; michael@0: int bottomRectsHeight = bottomRects->y2 - bottomRects->y1; michael@0: int inbetweenHeight = bottomRects->y1 - topRects->y2; michael@0: int width = cur_x; michael@0: // top and bottom are the in-status to the left of cur_x michael@0: do { michael@0: if (top && !bottom) { michael@0: totalArea += (inbetweenHeight+bottomRectsHeight)*width; michael@0: } else if (bottom && !top) { michael@0: totalArea += (inbetweenHeight+topRectsHeight)*width; michael@0: } else if (bottom && top) { michael@0: totalArea += (inbetweenHeight)*width; michael@0: } michael@0: top = top_next; michael@0: bottom = bottom_next; michael@0: // find the next edge michael@0: if (i->x < j->x) { michael@0: top_next = !top; michael@0: width = i->x - cur_x; michael@0: cur_x = i->x; michael@0: i++; michael@0: } else if (j->x < i->x) { michael@0: bottom_next = !bottom; michael@0: width = j->x - cur_x; michael@0: cur_x = j->x; michael@0: j++; michael@0: } else { // i->x == j->x michael@0: top_next = !top; michael@0: bottom_next = !bottom; michael@0: width = i->x - cur_x; michael@0: cur_x = i->x; michael@0: i++; michael@0: j++; michael@0: } michael@0: } while (i < end_i && j < end_j); michael@0: michael@0: // handle any remaining rects michael@0: while (i < end_i) { michael@0: width = i->x - cur_x; michael@0: cur_x = i->x; michael@0: i++; michael@0: if (top) michael@0: totalArea += (inbetweenHeight+bottomRectsHeight)*width; michael@0: top = !top; michael@0: } michael@0: michael@0: while (j < end_j) { michael@0: width = j->x - cur_x; michael@0: cur_x = j->x; michael@0: j++; michael@0: if (bottom) michael@0: totalArea += (inbetweenHeight+topRectsHeight)*width; michael@0: bottom = !bottom; michael@0: } michael@0: return totalArea; michael@0: } michael@0: michael@0: static pixman_box32_t * michael@0: CopyRow(pixman_box32_t *dest_it, pixman_box32_t *src_start, pixman_box32_t *src_end) michael@0: { michael@0: // XXX: std::copy michael@0: pixman_box32_t *src_it = src_start; michael@0: while (src_it < src_end) { michael@0: *dest_it++ = *src_it++; michael@0: } michael@0: return dest_it; michael@0: } michael@0: michael@0: static pixman_box32_t * michael@0: MergeRects(pixman_box32_t *topRects, pixman_box32_t *topRectsEnd, michael@0: pixman_box32_t *bottomRects, pixman_box32_t *bottomRectsEnd, michael@0: pixman_box32_t *tmpRect) michael@0: { michael@0: struct pt { michael@0: int32_t x, y; michael@0: }; michael@0: michael@0: pixman_box32_t *rect; michael@0: // merge the two spans of rects michael@0: pt *i = (pt*)topRects; michael@0: pt *end_i = (pt*)topRectsEnd; michael@0: pt *j = (pt*)bottomRects; michael@0: pt *end_j = (pt*)bottomRectsEnd; michael@0: bool top; michael@0: bool bottom; michael@0: michael@0: int cur_x = i->x; michael@0: int32_t y1 = topRects->y1; michael@0: int32_t y2 = bottomRects->y2; michael@0: if (j->x < cur_x) { michael@0: top = false; michael@0: bottom = true; michael@0: cur_x = j->x; michael@0: j++; michael@0: } else if (j->x == cur_x) { michael@0: top = true; michael@0: bottom = true; michael@0: i++; michael@0: j++; michael@0: } else { michael@0: top = true; michael@0: bottom = false; michael@0: i++; michael@0: } michael@0: michael@0: rect = tmpRect; michael@0: bool started = false; michael@0: do { michael@0: if (started && !top && !bottom) { michael@0: rect->x2 = cur_x; michael@0: rect->y2 = y2; michael@0: rect++; michael@0: started = false; michael@0: } else if (!started) { michael@0: rect->x1 = cur_x; michael@0: rect->y1 = y1; michael@0: started = true; michael@0: } michael@0: michael@0: if (i >= end_i || j >= end_j) michael@0: break; michael@0: michael@0: if (i->x < j->x) { michael@0: top = !top; michael@0: cur_x = i->x; michael@0: i++; michael@0: } else if (j->x < i->x) { michael@0: bottom = !bottom; michael@0: cur_x = j->x; michael@0: j++; michael@0: } else { // i->x == j->x michael@0: top = !top; michael@0: bottom = !bottom; michael@0: cur_x = i->x; michael@0: i++; michael@0: j++; michael@0: } michael@0: } while (true); michael@0: michael@0: // handle any remaining rects michael@0: while (i < end_i) { michael@0: top = !top; michael@0: cur_x = i->x; michael@0: i++; michael@0: if (!top) { michael@0: rect->x2 = cur_x; michael@0: rect->y2 = y2; michael@0: rect++; michael@0: } else { michael@0: rect->x1 = cur_x; michael@0: rect->y1 = y1; michael@0: } michael@0: } michael@0: michael@0: while (j < end_j) { michael@0: bottom = !bottom; michael@0: cur_x = j->x; michael@0: j++; michael@0: if (!bottom) { michael@0: rect->x2 = cur_x; michael@0: rect->y2 = y2; michael@0: rect++; michael@0: } else { michael@0: rect->x1 = cur_x; michael@0: rect->y1 = y1; michael@0: } michael@0: } michael@0: return rect; michael@0: } michael@0: michael@0: void nsRegion::SimplifyOutwardByArea(uint32_t aThreshold) michael@0: { michael@0: michael@0: pixman_box32_t *boxes; michael@0: int n; michael@0: boxes = pixman_region32_rectangles(&mImpl, &n); michael@0: michael@0: // if we have no rectangles then we're done michael@0: if (!n) michael@0: return; michael@0: michael@0: pixman_box32_t *end = boxes + n; michael@0: pixman_box32_t *topRectsEnd = boxes+1; michael@0: pixman_box32_t *topRects = boxes; michael@0: michael@0: // we need some temporary storage for merging both rows of rectangles michael@0: nsAutoTArray tmpStorage; michael@0: tmpStorage.SetCapacity(n); michael@0: pixman_box32_t *tmpRect = tmpStorage.Elements(); michael@0: michael@0: pixman_box32_t *destRect = boxes; michael@0: pixman_box32_t *rect = tmpRect; michael@0: // find the end of the first span of rectangles michael@0: while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) { michael@0: topRectsEnd++; michael@0: } michael@0: michael@0: // if we only have one row we are done michael@0: if (topRectsEnd == end) michael@0: return; michael@0: michael@0: pixman_box32_t *bottomRects = topRectsEnd; michael@0: pixman_box32_t *bottomRectsEnd = bottomRects+1; michael@0: do { michael@0: // find the end of the bottom span of rectangles michael@0: while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) { michael@0: bottomRectsEnd++; michael@0: } michael@0: uint32_t totalArea = ComputeMergedAreaIncrease(topRects, topRectsEnd, michael@0: bottomRects, bottomRectsEnd); michael@0: michael@0: if (totalArea <= aThreshold) { michael@0: // merge the rects into tmpRect michael@0: rect = MergeRects(topRects, topRectsEnd, bottomRects, bottomRectsEnd, tmpRect); michael@0: michael@0: // copy the merged rects back into the destination michael@0: topRectsEnd = CopyRow(destRect, tmpRect, rect); michael@0: topRects = destRect; michael@0: bottomRects = bottomRectsEnd; michael@0: destRect = topRects; michael@0: } else { michael@0: // copy the unmerged rects michael@0: destRect = CopyRow(destRect, topRects, topRectsEnd); michael@0: michael@0: topRects = bottomRects; michael@0: topRectsEnd = bottomRectsEnd; michael@0: bottomRects = bottomRectsEnd; michael@0: if (bottomRectsEnd == end) { michael@0: // copy the last row when we are done michael@0: topRectsEnd = CopyRow(destRect, topRects, topRectsEnd); michael@0: } michael@0: } michael@0: } while (bottomRectsEnd != end); michael@0: michael@0: michael@0: uint32_t reducedCount = topRectsEnd - pixman_region32_rectangles(&this->mImpl, &n); michael@0: // pixman has a special representation for michael@0: // regions of 1 rectangle. So just use the michael@0: // bounds in that case michael@0: if (reducedCount > 1) { michael@0: // reach into pixman and lower the number michael@0: // of rects stored in data. michael@0: this->mImpl.data->numRects = reducedCount; michael@0: } else { michael@0: *this = GetBounds(); michael@0: } michael@0: } michael@0: michael@0: michael@0: void nsRegion::SimplifyInward (uint32_t aMaxRects) michael@0: { michael@0: NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count"); michael@0: michael@0: if (GetNumRects() <= aMaxRects) michael@0: return; michael@0: michael@0: SetEmpty(); michael@0: } michael@0: michael@0: uint64_t nsRegion::Area () const michael@0: { michael@0: uint64_t area = 0; michael@0: nsRegionRectIterator iter(*this); michael@0: const nsRect* r; michael@0: while ((r = iter.Next()) != nullptr) { michael@0: area += uint64_t(r->width)*r->height; michael@0: } michael@0: return area; michael@0: } michael@0: michael@0: nsRegion& nsRegion::ScaleRoundOut (float aXScale, float aYScale) michael@0: { michael@0: int n; michael@0: pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n); michael@0: for (int i=0; iScaleToNearestPixels(aScaleX, aScaleY, aAppUnitsPerPixel); michael@0: result.Or(result, deviceRect); michael@0: } michael@0: return result; michael@0: } michael@0: michael@0: nsIntRegion nsRegion::ScaleToOutsidePixels (float aScaleX, float aScaleY, michael@0: nscoord aAppUnitsPerPixel) const michael@0: { michael@0: nsIntRegion result; michael@0: nsRegionRectIterator rgnIter(*this); michael@0: const nsRect* currentRect; michael@0: while ((currentRect = rgnIter.Next())) { michael@0: nsIntRect deviceRect = michael@0: currentRect->ScaleToOutsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel); michael@0: result.Or(result, deviceRect); michael@0: } michael@0: return result; michael@0: } michael@0: michael@0: nsIntRegion nsRegion::ScaleToInsidePixels (float aScaleX, float aScaleY, michael@0: nscoord aAppUnitsPerPixel) const michael@0: { michael@0: /* When scaling a rect, walk forward through the rect list up until the y value is greater michael@0: * than the current rect's YMost() value. michael@0: * michael@0: * For each rect found, check if the rects have a touching edge (in unscaled coordinates), michael@0: * and if one edge is entirely contained within the other. michael@0: * michael@0: * If it is, then the contained edge can be moved (in scaled pixels) to ensure that no michael@0: * gap exists. michael@0: * michael@0: * Since this could be potentially expensive - O(n^2), we only attempt this algorithm michael@0: * for the first rect. michael@0: */ michael@0: michael@0: // make a copy of this region so that we can mutate it in place michael@0: nsRegion region = *this; michael@0: int n; michael@0: pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n); michael@0: michael@0: nsIntRegion intRegion; michael@0: if (n) { michael@0: nsRect first = BoxToRect(boxes[0]); michael@0: nsIntRect firstDeviceRect = michael@0: first.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel); michael@0: michael@0: for (int i=1; i= first.XMost()) { michael@0: // The top of rect contains the bottom of the first rect michael@0: firstDeviceRect.SetBottomEdge(deviceRect.y); michael@0: } else if (rect.x >= first.x && rect.XMost() <= first.XMost()) { michael@0: // The bottom of the first contains the top of rect michael@0: deviceRect.SetTopEdge(firstDeviceRect.YMost()); michael@0: } michael@0: } michael@0: } michael@0: michael@0: boxes[i] = RectToBox(deviceRect); michael@0: } michael@0: michael@0: boxes[0] = RectToBox(firstDeviceRect); michael@0: michael@0: pixman_region32_fini(&intRegion.mImpl.mImpl); michael@0: // This will union all of the rectangles and runs in about O(n lg(n)) michael@0: pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n); michael@0: } michael@0: return intRegion; michael@0: michael@0: } michael@0: michael@0: // A cell's "value" is a pair consisting of michael@0: // a) the area of the subrectangle it corresponds to, if it's in michael@0: // aContainingRect and in the region, 0 otherwise michael@0: // b) the area of the subrectangle it corresponds to, if it's in the region, michael@0: // 0 otherwise michael@0: // Addition, subtraction and identity are defined on these values in the michael@0: // obvious way. Partial order is lexicographic. michael@0: // A "large negative value" is defined with large negative numbers for both michael@0: // fields of the pair. This negative value has the property that adding any michael@0: // number of non-negative values to it always results in a negative value. michael@0: // michael@0: // The GetLargestRectangle algorithm works in three phases: michael@0: // 1) Convert the region into a grid by adding vertical/horizontal lines for michael@0: // each edge of each rectangle in the region. michael@0: // 2) For each rectangle in the region, for each cell it contains, set that michael@0: // cells's value as described above. michael@0: // 3) Calculate the submatrix with the largest sum such that none of its cells michael@0: // contain any 0s (empty regions). The rectangle represented by the michael@0: // submatrix is the largest rectangle in the region. michael@0: // michael@0: // Let k be the number of rectangles in the region. michael@0: // Let m be the height of the grid generated in step 1. michael@0: // Let n be the width of the grid generated in step 1. michael@0: // michael@0: // Step 1 is O(k) in time and O(m+n) in space for the sparse grid. michael@0: // Step 2 is O(mn) in time and O(mn) in additional space for the full grid. michael@0: // Step 3 is O(m^2 n) in time and O(mn) in additional space michael@0: // michael@0: // The implementation of steps 1 and 2 are rather straightforward. However our michael@0: // implementation of step 3 uses dynamic programming to achieve its efficiency. michael@0: // michael@0: // Psuedo code for step 3 is as follows where G is the grid from step 1 and A michael@0: // is the array from step 2: michael@0: // Phase3 = function (G, A, m, n) { michael@0: // let (t,b,l,r,_) = MaxSum2D(A,m,n) michael@0: // return rect(G[t],G[l],G[r],G[b]); michael@0: // } michael@0: // MaxSum2D = function (A, m, n) { michael@0: // S = array(m+1,n+1) michael@0: // S[0][i] = 0 for i in [0,n] michael@0: // S[j][0] = 0 for j in [0,m] michael@0: // S[j][i] = (if A[j-1][i-1] = 0 then some large negative value else A[j-1][i-1]) michael@0: // + S[j-1][n] + S[j][i-1] - S[j-1][i-1] michael@0: // michael@0: // // top, bottom, left, right, area michael@0: // var maxRect = (-1, -1, -1, -1, 0); michael@0: // michael@0: // for all (m',m'') in [0, m]^2 { michael@0: // let B = { S[m'][i] - S[m''][i] | 0 <= i <= n } michael@0: // let ((l,r),area) = MaxSum1D(B,n+1) michael@0: // if (area > maxRect.area) { michael@0: // maxRect := (m', m'', l, r, area) michael@0: // } michael@0: // } michael@0: // michael@0: // return maxRect; michael@0: // } michael@0: // michael@0: // Originally taken from Improved algorithms for the k-maximum subarray problem michael@0: // for small k - SE Bae, T Takaoka but modified to show the explicit tracking michael@0: // of indices and we already have the prefix sums from our one call site so michael@0: // there's no need to construct them. michael@0: // MaxSum1D = function (A,n) { michael@0: // var minIdx = 0; michael@0: // var min = 0; michael@0: // var maxIndices = (0,0); michael@0: // var max = 0; michael@0: // for i in range(n) { michael@0: // let cand = A[i] - min; michael@0: // if (cand > max) { michael@0: // max := cand; michael@0: // maxIndices := (minIdx, i) michael@0: // } michael@0: // if (min > A[i]) { michael@0: // min := A[i]; michael@0: // minIdx := i; michael@0: // } michael@0: // } michael@0: // return (minIdx, maxIdx, max); michael@0: // } michael@0: michael@0: namespace { michael@0: // This class represents a partitioning of an axis delineated by coordinates. michael@0: // It internally maintains a sorted array of coordinates. michael@0: class AxisPartition { michael@0: public: michael@0: // Adds a new partition at the given coordinate to this partitioning. If michael@0: // the coordinate is already present in the partitioning, this does nothing. michael@0: void InsertCoord(nscoord c) { michael@0: uint32_t i = mStops.IndexOfFirstElementGt(c); michael@0: if (i == 0 || mStops[i-1] != c) { michael@0: mStops.InsertElementAt(i, c); michael@0: } michael@0: } michael@0: michael@0: // Returns the array index of the given partition point. The partition michael@0: // point must already be present in the partitioning. michael@0: int32_t IndexOf(nscoord p) const { michael@0: return mStops.BinaryIndexOf(p); michael@0: } michael@0: michael@0: // Returns the partition at the given index which must be non-zero and michael@0: // less than the number of partitions in this partitioning. michael@0: nscoord StopAt(int32_t index) const { michael@0: return mStops[index]; michael@0: } michael@0: michael@0: // Returns the size of the gap between the partition at the given index and michael@0: // the next partition in this partitioning. If the index is the last index michael@0: // in the partitioning, the result is undefined. michael@0: nscoord StopSize(int32_t index) const { michael@0: return mStops[index+1] - mStops[index]; michael@0: } michael@0: michael@0: // Returns the number of partitions in this partitioning. michael@0: int32_t GetNumStops() const { return mStops.Length(); } michael@0: michael@0: private: michael@0: nsTArray mStops; michael@0: }; michael@0: michael@0: const int64_t kVeryLargeNegativeNumber = 0xffff000000000000ll; michael@0: michael@0: struct SizePair { michael@0: int64_t mSizeContainingRect; michael@0: int64_t mSize; michael@0: michael@0: SizePair() : mSizeContainingRect(0), mSize(0) {} michael@0: michael@0: static SizePair VeryLargeNegative() { michael@0: SizePair result; michael@0: result.mSize = result.mSizeContainingRect = kVeryLargeNegativeNumber; michael@0: return result; michael@0: } michael@0: SizePair& operator=(const SizePair& aOther) { michael@0: mSizeContainingRect = aOther.mSizeContainingRect; michael@0: mSize = aOther.mSize; michael@0: return *this; michael@0: } michael@0: bool operator<(const SizePair& aOther) const { michael@0: if (mSizeContainingRect < aOther.mSizeContainingRect) michael@0: return true; michael@0: if (mSizeContainingRect > aOther.mSizeContainingRect) michael@0: return false; michael@0: return mSize < aOther.mSize; michael@0: } michael@0: bool operator>(const SizePair& aOther) const { michael@0: return aOther.operator<(*this); michael@0: } michael@0: SizePair operator+(const SizePair& aOther) const { michael@0: SizePair result = *this; michael@0: result.mSizeContainingRect += aOther.mSizeContainingRect; michael@0: result.mSize += aOther.mSize; michael@0: return result; michael@0: } michael@0: SizePair operator-(const SizePair& aOther) const { michael@0: SizePair result = *this; michael@0: result.mSizeContainingRect -= aOther.mSizeContainingRect; michael@0: result.mSize -= aOther.mSize; michael@0: return result; michael@0: } michael@0: }; michael@0: michael@0: // Returns the sum and indices of the subarray with the maximum sum of the michael@0: // given array (A,n), assuming the array is already in prefix sum form. michael@0: SizePair MaxSum1D(const nsTArray &A, int32_t n, michael@0: int32_t *minIdx, int32_t *maxIdx) { michael@0: // The min/max indicies of the largest subarray found so far michael@0: SizePair min, max; michael@0: int32_t currentMinIdx = 0; michael@0: michael@0: *minIdx = 0; michael@0: *maxIdx = 0; michael@0: michael@0: // Because we're given the array in prefix sum form, we know the first michael@0: // element is 0 michael@0: for(int32_t i = 1; i < n; i++) { michael@0: SizePair cand = A[i] - min; michael@0: if (cand > max) { michael@0: max = cand; michael@0: *minIdx = currentMinIdx; michael@0: *maxIdx = i; michael@0: } michael@0: if (min > A[i]) { michael@0: min = A[i]; michael@0: currentMinIdx = i; michael@0: } michael@0: } michael@0: michael@0: return max; michael@0: } michael@0: } michael@0: michael@0: nsRect nsRegion::GetLargestRectangle (const nsRect& aContainingRect) const { michael@0: nsRect bestRect; michael@0: michael@0: if (GetNumRects() <= 1) { michael@0: bestRect = GetBounds(); michael@0: return bestRect; michael@0: } michael@0: michael@0: AxisPartition xaxis, yaxis; michael@0: michael@0: // Step 1: Calculate the grid lines michael@0: nsRegionRectIterator iter(*this); michael@0: const nsRect *currentRect; michael@0: while ((currentRect = iter.Next())) { michael@0: xaxis.InsertCoord(currentRect->x); michael@0: xaxis.InsertCoord(currentRect->XMost()); michael@0: yaxis.InsertCoord(currentRect->y); michael@0: yaxis.InsertCoord(currentRect->YMost()); michael@0: } michael@0: if (!aContainingRect.IsEmpty()) { michael@0: xaxis.InsertCoord(aContainingRect.x); michael@0: xaxis.InsertCoord(aContainingRect.XMost()); michael@0: yaxis.InsertCoord(aContainingRect.y); michael@0: yaxis.InsertCoord(aContainingRect.YMost()); michael@0: } michael@0: michael@0: // Step 2: Fill out the grid with the areas michael@0: // Note: due to the ordering of rectangles in the region, it is not always michael@0: // possible to combine steps 2 and 3 so we don't try to be clever. michael@0: int32_t matrixHeight = yaxis.GetNumStops() - 1; michael@0: int32_t matrixWidth = xaxis.GetNumStops() - 1; michael@0: int32_t matrixSize = matrixHeight * matrixWidth; michael@0: nsTArray areas(matrixSize); michael@0: areas.SetLength(matrixSize); michael@0: michael@0: iter.Reset(); michael@0: while ((currentRect = iter.Next())) { michael@0: int32_t xstart = xaxis.IndexOf(currentRect->x); michael@0: int32_t xend = xaxis.IndexOf(currentRect->XMost()); michael@0: int32_t y = yaxis.IndexOf(currentRect->y); michael@0: int32_t yend = yaxis.IndexOf(currentRect->YMost()); michael@0: michael@0: for (; y < yend; y++) { michael@0: nscoord height = yaxis.StopSize(y); michael@0: for (int32_t x = xstart; x < xend; x++) { michael@0: nscoord width = xaxis.StopSize(x); michael@0: int64_t size = width*int64_t(height); michael@0: if (currentRect->Intersects(aContainingRect)) { michael@0: areas[y*matrixWidth+x].mSizeContainingRect = size; michael@0: } michael@0: areas[y*matrixWidth+x].mSize = size; michael@0: } michael@0: } michael@0: } michael@0: michael@0: // Step 3: Find the maximum submatrix sum that does not contain a rectangle michael@0: { michael@0: // First get the prefix sum array michael@0: int32_t m = matrixHeight + 1; michael@0: int32_t n = matrixWidth + 1; michael@0: nsTArray pareas(m*n); michael@0: pareas.SetLength(m*n); michael@0: for (int32_t y = 1; y < m; y++) { michael@0: for (int32_t x = 1; x < n; x++) { michael@0: SizePair area = areas[(y-1)*matrixWidth+x-1]; michael@0: if (!area.mSize) { michael@0: area = SizePair::VeryLargeNegative(); michael@0: } michael@0: area = area + pareas[ y*n+x-1] michael@0: + pareas[(y-1)*n+x ] michael@0: - pareas[(y-1)*n+x-1]; michael@0: pareas[y*n+x] = area; michael@0: } michael@0: } michael@0: michael@0: // No longer need the grid michael@0: areas.SetLength(0); michael@0: michael@0: SizePair bestArea; michael@0: struct { michael@0: int32_t left, top, right, bottom; michael@0: } bestRectIndices = { 0, 0, 0, 0 }; michael@0: for (int32_t m1 = 0; m1 < m; m1++) { michael@0: for (int32_t m2 = m1+1; m2 < m; m2++) { michael@0: nsTArray B; michael@0: B.SetLength(n); michael@0: for (int32_t i = 0; i < n; i++) { michael@0: B[i] = pareas[m2*n+i] - pareas[m1*n+i]; michael@0: } michael@0: int32_t minIdx, maxIdx; michael@0: SizePair area = MaxSum1D(B, n, &minIdx, &maxIdx); michael@0: if (area > bestArea) { michael@0: bestRectIndices.left = minIdx; michael@0: bestRectIndices.top = m1; michael@0: bestRectIndices.right = maxIdx; michael@0: bestRectIndices.bottom = m2; michael@0: bestArea = area; michael@0: } michael@0: } michael@0: } michael@0: michael@0: bestRect.MoveTo(xaxis.StopAt(bestRectIndices.left), michael@0: yaxis.StopAt(bestRectIndices.top)); michael@0: bestRect.SizeTo(xaxis.StopAt(bestRectIndices.right) - bestRect.x, michael@0: yaxis.StopAt(bestRectIndices.bottom) - bestRect.y); michael@0: } michael@0: michael@0: return bestRect; michael@0: } michael@0: michael@0: nsCString michael@0: nsRegion::ToString() const { michael@0: nsCString result; michael@0: result.AppendLiteral("["); michael@0: michael@0: int n; michael@0: pixman_box32_t *boxes = pixman_region32_rectangles(const_cast(&mImpl), &n); michael@0: for (int i=0; iToAppUnits(aAppUnitsPerPixel); michael@0: result.Or(result, appRect); michael@0: } michael@0: return result; michael@0: }