libs/ui/Region.cpp - platform/frameworks/base - Git at Google

 /*
  * Copyright (C) 2007 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #define LOG_TAG "Region"

 #include <limits.h>

 #include <utils/Log.h>
 #include <utils/String8.h>

 #include <ui/Rect.h>
 #include <ui/Region.h>
 #include <ui/Point.h>

 #include <private/ui/RegionHelper.h>

 // ----------------------------------------------------------------------------
 #define VALIDATE_REGIONS        (false)
 #define VALIDATE_WITH_CORECG    (false)
 // ----------------------------------------------------------------------------

 #if VALIDATE_WITH_CORECG
 #include <core/SkRegion.h>
 #endif

 namespace android {
 // ----------------------------------------------------------------------------

 enum {
     op_nand = region_operator<Rect>::op_nand,
     op_and  = region_operator<Rect>::op_and,
     op_or   = region_operator<Rect>::op_or,
     op_xor  = region_operator<Rect>::op_xor
 };

 // ----------------------------------------------------------------------------

 Region::Region()
     : mBounds(0,0)
 {
 }

 Region::Region(const Region& rhs)
     : mBounds(rhs.mBounds), mStorage(rhs.mStorage)
 {
 }

 Region::Region(const Rect& rhs)
     : mBounds(rhs)
 {
 }

 Region::Region(const void* buffer)
 {
     status_t err = read(buffer);
     LOGE_IF(err<0, "error %s reading Region from buffer", strerror(err));
 }

 Region::~Region()
 {
 }

 Region& Region::operator = (const Region& rhs)
 {
 #if VALIDATE_REGIONS
     validate(rhs, "operator=");
 #endif
     mBounds = rhs.mBounds;
     mStorage = rhs.mStorage;
     return *this;
 }

 Region& Region::makeBoundsSelf()
 {
     mStorage.clear();
     return *this;
 }

 void Region::clear()
 {
     mBounds.clear();
     mStorage.clear();
 }

 void Region::set(const Rect& r)
 {
     mBounds = r;
     mStorage.clear();
 }

 void Region::set(uint32_t w, uint32_t h)
 {
     mBounds = Rect(int(w), int(h));
     mStorage.clear();
 }

 // ----------------------------------------------------------------------------

 void Region::addRectUnchecked(int l, int t, int r, int b)
 {
     mStorage.add(Rect(l,t,r,b));
 #if VALIDATE_REGIONS
     validate(*this, "addRectUnchecked");
 #endif
 }

 // ----------------------------------------------------------------------------

 Region& Region::orSelf(const Rect& r) {
     return operationSelf(r, op_or);
 }
 Region& Region::andSelf(const Rect& r) {
     return operationSelf(r, op_and);
 }
 Region& Region::subtractSelf(const Rect& r) {
     return operationSelf(r, op_nand);
 }
 Region& Region::operationSelf(const Rect& r, int op) {
     Region lhs(*this);
     boolean_operation(op, *this, lhs, r);
     return *this;
 }

 // ----------------------------------------------------------------------------

 Region& Region::orSelf(const Region& rhs) {
     return operationSelf(rhs, op_or);
 }
 Region& Region::andSelf(const Region& rhs) {
     return operationSelf(rhs, op_and);
 }
 Region& Region::subtractSelf(const Region& rhs) {
     return operationSelf(rhs, op_nand);
 }
 Region& Region::operationSelf(const Region& rhs, int op) {
     Region lhs(*this);
     boolean_operation(op, *this, lhs, rhs);
     return *this;
 }

 Region& Region::translateSelf(int x, int y) {
     if (x|y) translate(*this, x, y);
     return *this;
 }

 // ----------------------------------------------------------------------------

 const Region Region::merge(const Rect& rhs) const {
     return operation(rhs, op_or);
 }
 const Region Region::intersect(const Rect& rhs) const {
     return operation(rhs, op_and);
 }
 const Region Region::subtract(const Rect& rhs) const {
     return operation(rhs, op_nand);
 }
 const Region Region::operation(const Rect& rhs, int op) const {
     Region result;
     boolean_operation(op, result, *this, rhs);
     return result;
 }

 // ----------------------------------------------------------------------------

 const Region Region::merge(const Region& rhs) const {
     return operation(rhs, op_or);
 }
 const Region Region::intersect(const Region& rhs) const {
     return operation(rhs, op_and);
 }
 const Region Region::subtract(const Region& rhs) const {
     return operation(rhs, op_nand);
 }
 const Region Region::operation(const Region& rhs, int op) const {
     Region result;
     boolean_operation(op, result, *this, rhs);
     return result;
 }

 const Region Region::translate(int x, int y) const {
     Region result;
     translate(result, *this, x, y);
     return result;
 }

 // ----------------------------------------------------------------------------

 Region& Region::orSelf(const Region& rhs, int dx, int dy) {
     return operationSelf(rhs, dx, dy, op_or);
 }
 Region& Region::andSelf(const Region& rhs, int dx, int dy) {
     return operationSelf(rhs, dx, dy, op_and);
 }
 Region& Region::subtractSelf(const Region& rhs, int dx, int dy) {
     return operationSelf(rhs, dx, dy, op_nand);
 }
 Region& Region::operationSelf(const Region& rhs, int dx, int dy, int op) {
     Region lhs(*this);
     boolean_operation(op, *this, lhs, rhs, dx, dy);
     return *this;
 }

 // ----------------------------------------------------------------------------

 const Region Region::merge(const Region& rhs, int dx, int dy) const {
     return operation(rhs, dx, dy, op_or);
 }
 const Region Region::intersect(const Region& rhs, int dx, int dy) const {
     return operation(rhs, dx, dy, op_and);
 }
 const Region Region::subtract(const Region& rhs, int dx, int dy) const {
     return operation(rhs, dx, dy, op_nand);
 }
 const Region Region::operation(const Region& rhs, int dx, int dy, int op) const {
     Region result;
     boolean_operation(op, result, *this, rhs, dx, dy);
     return result;
 }

 // ----------------------------------------------------------------------------

 // This is our region rasterizer, which merges rects and spans together
 // to obtain an optimal region.
 class Region::rasterizer : public region_operator<Rect>::region_rasterizer
 {
     Rect& bounds;
     Vector<Rect>& storage;
     Rect* head;
     Rect* tail;
     Vector<Rect> span;
     Rect* cur;
 public:
     rasterizer(Region& reg)
         : bounds(reg.mBounds), storage(reg.mStorage), head(), tail(), cur() {
         bounds.top = bounds.bottom = 0;
         bounds.left   = INT_MAX;
         bounds.right  = INT_MIN;
         storage.clear();
     }

     ~rasterizer() {
         if (span.size()) {
             flushSpan();
         }
         if (storage.size()) {
             bounds.top = storage.itemAt(0).top;
             bounds.bottom = storage.top().bottom;
             if (storage.size() == 1) {
                 storage.clear();
             }
         } else {
             bounds.left  = 0;
             bounds.right = 0;
         }
     }

     virtual void operator()(const Rect& rect) {
         //LOGD(">>> %3d, %3d, %3d, %3d",
         //        rect.left, rect.top, rect.right, rect.bottom);
         if (span.size()) {
             if (cur->top != rect.top) {
                 flushSpan();
             } else if (cur->right == rect.left) {
                 cur->right = rect.right;
                 return;
             }
         }
         span.add(rect);
         cur = span.editArray() + (span.size() - 1);
     }
 private:
     template<typename T>
     static inline T min(T rhs, T lhs) { return rhs < lhs ? rhs : lhs; }
     template<typename T>
     static inline T max(T rhs, T lhs) { return rhs > lhs ? rhs : lhs; }
     void flushSpan() {
         bool merge = false;
         if (tail-head == ssize_t(span.size())) {
             Rect const* p = cur;
             Rect const* q = head;
             if (p->top == q->bottom) {
                 merge = true;
                 while (q != tail) {
                     if ((p->left != q->left) || (p->right != q->right)) {
                         merge = false;
                         break;
                     }
                     p++, q++;
                 }
             }
         }
         if (merge) {
             const int bottom = span[0].bottom;
             Rect* r = head;
             while (r != tail) {
                 r->bottom = bottom;
                 r++;
             }
         } else {
             bounds.left = min(span.itemAt(0).left, bounds.left);
             bounds.right = max(span.top().right, bounds.right);
             storage.appendVector(span);
             tail = storage.editArray() + storage.size();
             head = tail - span.size();
         }
         span.clear();
     }
 };

 bool Region::validate(const Region& reg, const char* name)
 {
     bool result = true;
     const_iterator cur = reg.begin();
     const_iterator const tail = reg.end();
     const_iterator prev = cur++;
     Rect b(*prev);
     while (cur != tail) {
         b.left   = b.left   < cur->left   ? b.left   : cur->left;
         b.top    = b.top    < cur->top    ? b.top    : cur->top;
         b.right  = b.right  > cur->right  ? b.right  : cur->right;
         b.bottom = b.bottom > cur->bottom ? b.bottom : cur->bottom;
         if (cur->top == prev->top) {
             if (cur->bottom != prev->bottom) {
                 LOGE("%s: invalid span %p", name, cur);
                 result = false;
             } else if (cur->left < prev->right) {
                 LOGE("%s: spans overlap horizontally prev=%p, cur=%p",
                         name, prev, cur);
                 result = false;
             }
         } else if (cur->top < prev->bottom) {
             LOGE("%s: spans overlap vertically prev=%p, cur=%p",
                     name, prev, cur);
             result = false;
         }
         prev = cur;
         cur++;
     }
     if (b != reg.getBounds()) {
         result = false;
         LOGE("%s: invalid bounds [%d,%d,%d,%d] vs. [%d,%d,%d,%d]", name,
                 b.left, b.top, b.right, b.bottom,
                 reg.getBounds().left, reg.getBounds().top,
                 reg.getBounds().right, reg.getBounds().bottom);
     }
     if (result == false) {
         reg.dump(name);
     }
     return result;
 }

 void Region::boolean_operation(int op, Region& dst,
         const Region& lhs,
         const Region& rhs, int dx, int dy)
 {
     size_t lhs_count;
     Rect const * const lhs_rects = lhs.getArray(&lhs_count);

     size_t rhs_count;
     Rect const * const rhs_rects = rhs.getArray(&rhs_count);

     region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
     region_operator<Rect>::region rhs_region(rhs_rects, rhs_count, dx, dy);
     region_operator<Rect> operation(op, lhs_region, rhs_region);
     { // scope for rasterizer (dtor has side effects)
         rasterizer r(dst);
         operation(r);
     }

 #if VALIDATE_REGIONS
     validate(lhs, "boolean_operation: lhs");
     validate(rhs, "boolean_operation: rhs");
     validate(dst, "boolean_operation: dst");
 #endif

 #if VALIDATE_WITH_CORECG
     SkRegion sk_lhs;
     SkRegion sk_rhs;
     SkRegion sk_dst;

     for (size_t i=0 ; i<lhs_count ; i++)
         sk_lhs.op(
                 lhs_rects[i].left   + dx,
                 lhs_rects[i].top    + dy,
                 lhs_rects[i].right  + dx,
                 lhs_rects[i].bottom + dy,
                 SkRegion::kUnion_Op);

     for (size_t i=0 ; i<rhs_count ; i++)
         sk_rhs.op(
                 rhs_rects[i].left   + dx,
                 rhs_rects[i].top    + dy,
                 rhs_rects[i].right  + dx,
                 rhs_rects[i].bottom + dy,
                 SkRegion::kUnion_Op);

     const char* name = "---";
     SkRegion::Op sk_op;
     switch (op) {
         case op_or: sk_op = SkRegion::kUnion_Op; name="OR"; break;
         case op_and: sk_op = SkRegion::kIntersect_Op; name="AND"; break;
         case op_nand: sk_op = SkRegion::kDifference_Op; name="NAND"; break;
     }
     sk_dst.op(sk_lhs, sk_rhs, sk_op);

     if (sk_dst.isEmpty() && dst.isEmpty())
         return;

     bool same = true;
     Region::const_iterator head = dst.begin();
     Region::const_iterator const tail = dst.end();
     SkRegion::Iterator it(sk_dst);
     while (!it.done()) {
         if (head != tail) {
             if (
                     head->left != it.rect().fLeft ||
                     head->top != it.rect().fTop ||
                     head->right != it.rect().fRight ||
                     head->bottom != it.rect().fBottom
             ) {
                 same = false;
                 break;
             }
         } else {
             same = false;
             break;
         }
         head++;
         it.next();
     }

     if (head != tail) {
         same = false;
     }

     if(!same) {
         LOGD("---\nregion boolean %s failed", name);
         lhs.dump("lhs");
         rhs.dump("rhs");
         dst.dump("dst");
         LOGD("should be");
         SkRegion::Iterator it(sk_dst);
         while (!it.done()) {
             LOGD("    [%3d, %3d, %3d, %3d]",
                 it.rect().fLeft,
                 it.rect().fTop,
                 it.rect().fRight,
                 it.rect().fBottom);
             it.next();
         }
     }
 #endif
 }

 void Region::boolean_operation(int op, Region& dst,
         const Region& lhs,
         const Rect& rhs, int dx, int dy)
 {
 #if VALIDATE_WITH_CORECG || VALIDATE_REGIONS
     boolean_operation(op, dst, lhs, Region(rhs), dx, dy);
 #else
     size_t lhs_count;
     Rect const * const lhs_rects = lhs.getArray(&lhs_count);

     region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
     region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy);
     region_operator<Rect> operation(op, lhs_region, rhs_region);
     { // scope for rasterizer (dtor has side effects)
         rasterizer r(dst);
         operation(r);
     }

 #endif
 }

 void Region::boolean_operation(int op, Region& dst,
         const Region& lhs, const Region& rhs)
 {
     boolean_operation(op, dst, lhs, rhs, 0, 0);
 }

 void Region::boolean_operation(int op, Region& dst,
         const Region& lhs, const Rect& rhs)
 {
     boolean_operation(op, dst, lhs, rhs, 0, 0);
 }

 void Region::translate(Region& reg, int dx, int dy)
 {
     if (!reg.isEmpty()) {
 #if VALIDATE_REGIONS
         validate(reg, "translate (before)");
 #endif
         reg.mBounds.translate(dx, dy);
         size_t count = reg.mStorage.size();
         Rect* rects = reg.mStorage.editArray();
         while (count) {
             rects->translate(dx, dy);
             rects++;
             count--;
         }
 #if VALIDATE_REGIONS
         validate(reg, "translate (after)");
 #endif
     }
 }

 void Region::translate(Region& dst, const Region& reg, int dx, int dy)
 {
     dst = reg;
     translate(dst, dx, dy);
 }

 // ----------------------------------------------------------------------------

 ssize_t Region::write(void* buffer, size_t size) const
 {
 #if VALIDATE_REGIONS
     validate(*this, "write(buffer)");
 #endif
     const size_t count = mStorage.size();
     const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect);
     if (buffer != NULL) {
         if (sizeNeeded > size) return NO_MEMORY;
         int32_t* const p = static_cast<int32_t*>(buffer);
         *p = count;
         memcpy(p+1, &mBounds, sizeof(Rect));
         if (count) {
             memcpy(p+5, mStorage.array(), count*sizeof(Rect));
         }
     }
     return ssize_t(sizeNeeded);
 }

 ssize_t Region::read(const void* buffer)
 {
     int32_t const* const p = static_cast<int32_t const*>(buffer);
     const size_t count = *p;
     memcpy(&mBounds, p+1, sizeof(Rect));
     mStorage.clear();
     if (count) {
         mStorage.insertAt(0, count);
         memcpy(mStorage.editArray(), p+5, count*sizeof(Rect));
     }
 #if VALIDATE_REGIONS
     validate(*this, "read(buffer)");
 #endif
     return ssize_t(sizeof(int32_t) + (1+count)*sizeof(Rect));
 }

 ssize_t Region::writeEmpty(void* buffer, size_t size)
 {
     const size_t sizeNeeded = sizeof(int32_t) + sizeof(Rect);
     if (sizeNeeded > size) return NO_MEMORY;
     int32_t* const p = static_cast<int32_t*>(buffer);
     memset(p, 0, sizeNeeded);
     return ssize_t(sizeNeeded);
 }

 bool Region::isEmpty(void* buffer)
 {
     int32_t const* const p = static_cast<int32_t const*>(buffer);
     Rect const* const b = reinterpret_cast<Rect const *>(p+1);
     return b->isEmpty();
 }

 // ----------------------------------------------------------------------------

 Region::const_iterator Region::begin() const {
     return isRect() ? &mBounds : mStorage.array();
 }

 Region::const_iterator Region::end() const {
     return isRect() ? ((&mBounds) + 1) : (mStorage.array() + mStorage.size());
 }

 Rect const* Region::getArray(size_t* count) const {
     const_iterator const b(begin());
     const_iterator const e(end());
     if (count) *count = e-b;
     return b;
 }

 size_t Region::getRects(Vector<Rect>& rectList) const
 {
     rectList = mStorage;
     if (rectList.isEmpty()) {
         rectList.clear();
         rectList.add(mBounds);
     }
     return rectList.size();
 }

 // ----------------------------------------------------------------------------

 void Region::dump(String8& out, const char* what, uint32_t flags) const
 {
     (void)flags;
     const_iterator head = begin();
     const_iterator const tail = end();

     size_t SIZE = 256;
     char buffer[SIZE];

     snprintf(buffer, SIZE, "  Region %s (this=%p, count=%d)\n",
             what, this, tail-head);
     out.append(buffer);
     while (head != tail) {
         snprintf(buffer, SIZE, "    [%3d, %3d, %3d, %3d]\n",
                 head->left, head->top, head->right, head->bottom);
         out.append(buffer);
         head++;
     }
 }

 void Region::dump(const char* what, uint32_t flags) const
 {
     (void)flags;
     const_iterator head = begin();
     const_iterator const tail = end();
     LOGD("  Region %s (this=%p, count=%d)\n", what, this, tail-head);
     while (head != tail) {
         LOGD("    [%3d, %3d, %3d, %3d]\n",
                 head->left, head->top, head->right, head->bottom);
         head++;
     }
 }

 // ----------------------------------------------------------------------------

 }; // namespace android
	/*
	* Copyright (C) 2007 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#define LOG_TAG "Region"

	#include <limits.h>

	#include <utils/Log.h>
	#include <utils/String8.h>

	#include <ui/Rect.h>
	#include <ui/Region.h>
	#include <ui/Point.h>

	#include <private/ui/RegionHelper.h>

	// ----------------------------------------------------------------------------
	#define VALIDATE_REGIONS (false)
	#define VALIDATE_WITH_CORECG (false)
	// ----------------------------------------------------------------------------

	#if VALIDATE_WITH_CORECG
	#include <core/SkRegion.h>
	#endif

	namespace android {
	// ----------------------------------------------------------------------------

	enum {
	op_nand = region_operator<Rect>::op_nand,
	op_and = region_operator<Rect>::op_and,
	op_or = region_operator<Rect>::op_or,
	op_xor = region_operator<Rect>::op_xor
	};

	// ----------------------------------------------------------------------------

	Region::Region()
	: mBounds(0,0)
	{
	}

	Region::Region(const Region& rhs)
	: mBounds(rhs.mBounds), mStorage(rhs.mStorage)
	{
	}

	Region::Region(const Rect& rhs)
	: mBounds(rhs)
	{
	}

	Region::Region(const void* buffer)
	{
	status_t err = read(buffer);
	LOGE_IF(err<0, "error %s reading Region from buffer", strerror(err));
	}

	Region::~Region()
	{
	}

	Region& Region::operator = (const Region& rhs)
	{
	#if VALIDATE_REGIONS
	validate(rhs, "operator=");
	#endif
	mBounds = rhs.mBounds;
	mStorage = rhs.mStorage;
	return *this;
	}

	Region& Region::makeBoundsSelf()
	{
	mStorage.clear();
	return *this;
	}

	void Region::clear()
	{
	mBounds.clear();
	mStorage.clear();
	}

	void Region::set(const Rect& r)
	{
	mBounds = r;
	mStorage.clear();
	}

	void Region::set(uint32_t w, uint32_t h)
	{
	mBounds = Rect(int(w), int(h));
	mStorage.clear();
	}

	// ----------------------------------------------------------------------------

	void Region::addRectUnchecked(int l, int t, int r, int b)
	{
	mStorage.add(Rect(l,t,r,b));
	#if VALIDATE_REGIONS
	validate(*this, "addRectUnchecked");
	#endif
	}

	// ----------------------------------------------------------------------------

	Region& Region::orSelf(const Rect& r) {
	return operationSelf(r, op_or);
	}
	Region& Region::andSelf(const Rect& r) {
	return operationSelf(r, op_and);
	}
	Region& Region::subtractSelf(const Rect& r) {
	return operationSelf(r, op_nand);
	}
	Region& Region::operationSelf(const Rect& r, int op) {
	Region lhs(*this);
	boolean_operation(op, *this, lhs, r);
	return *this;
	}

	// ----------------------------------------------------------------------------

	Region& Region::orSelf(const Region& rhs) {
	return operationSelf(rhs, op_or);
	}
	Region& Region::andSelf(const Region& rhs) {
	return operationSelf(rhs, op_and);
	}
	Region& Region::subtractSelf(const Region& rhs) {
	return operationSelf(rhs, op_nand);
	}
	Region& Region::operationSelf(const Region& rhs, int op) {
	Region lhs(*this);
	boolean_operation(op, *this, lhs, rhs);
	return *this;
	}

	Region& Region::translateSelf(int x, int y) {
	if (x\|y) translate(*this, x, y);
	return *this;
	}

	// ----------------------------------------------------------------------------

	const Region Region::merge(const Rect& rhs) const {
	return operation(rhs, op_or);
	}
	const Region Region::intersect(const Rect& rhs) const {
	return operation(rhs, op_and);
	}
	const Region Region::subtract(const Rect& rhs) const {
	return operation(rhs, op_nand);
	}
	const Region Region::operation(const Rect& rhs, int op) const {
	Region result;
	boolean_operation(op, result, *this, rhs);
	return result;
	}

	// ----------------------------------------------------------------------------

	const Region Region::merge(const Region& rhs) const {
	return operation(rhs, op_or);
	}
	const Region Region::intersect(const Region& rhs) const {
	return operation(rhs, op_and);
	}
	const Region Region::subtract(const Region& rhs) const {
	return operation(rhs, op_nand);
	}
	const Region Region::operation(const Region& rhs, int op) const {
	Region result;
	boolean_operation(op, result, *this, rhs);
	return result;
	}

	const Region Region::translate(int x, int y) const {
	Region result;
	translate(result, *this, x, y);
	return result;
	}

	// ----------------------------------------------------------------------------

	Region& Region::orSelf(const Region& rhs, int dx, int dy) {
	return operationSelf(rhs, dx, dy, op_or);
	}
	Region& Region::andSelf(const Region& rhs, int dx, int dy) {
	return operationSelf(rhs, dx, dy, op_and);
	}
	Region& Region::subtractSelf(const Region& rhs, int dx, int dy) {
	return operationSelf(rhs, dx, dy, op_nand);
	}
	Region& Region::operationSelf(const Region& rhs, int dx, int dy, int op) {
	Region lhs(*this);
	boolean_operation(op, *this, lhs, rhs, dx, dy);
	return *this;
	}

	// ----------------------------------------------------------------------------

	const Region Region::merge(const Region& rhs, int dx, int dy) const {
	return operation(rhs, dx, dy, op_or);
	}
	const Region Region::intersect(const Region& rhs, int dx, int dy) const {
	return operation(rhs, dx, dy, op_and);
	}
	const Region Region::subtract(const Region& rhs, int dx, int dy) const {
	return operation(rhs, dx, dy, op_nand);
	}
	const Region Region::operation(const Region& rhs, int dx, int dy, int op) const {
	Region result;
	boolean_operation(op, result, *this, rhs, dx, dy);
	return result;
	}

	// ----------------------------------------------------------------------------

	// This is our region rasterizer, which merges rects and spans together
	// to obtain an optimal region.
	class Region::rasterizer : public region_operator<Rect>::region_rasterizer
	{
	Rect& bounds;
	Vector<Rect>& storage;
	Rect* head;
	Rect* tail;
	Vector<Rect> span;
	Rect* cur;
	public:
	rasterizer(Region& reg)
	: bounds(reg.mBounds), storage(reg.mStorage), head(), tail(), cur() {
	bounds.top = bounds.bottom = 0;
	bounds.left = INT_MAX;
	bounds.right = INT_MIN;
	storage.clear();
	}

	~rasterizer() {
	if (span.size()) {
	flushSpan();
	}
	if (storage.size()) {
	bounds.top = storage.itemAt(0).top;
	bounds.bottom = storage.top().bottom;
	if (storage.size() == 1) {
	storage.clear();
	}
	} else {
	bounds.left = 0;
	bounds.right = 0;
	}
	}

	virtual void operator()(const Rect& rect) {
	//LOGD(">>> %3d, %3d, %3d, %3d",
	// rect.left, rect.top, rect.right, rect.bottom);
	if (span.size()) {
	if (cur->top != rect.top) {
	flushSpan();
	} else if (cur->right == rect.left) {
	cur->right = rect.right;
	return;
	}
	}
	span.add(rect);
	cur = span.editArray() + (span.size() - 1);
	}
	private:
	template<typename T>
	static inline T min(T rhs, T lhs) { return rhs < lhs ? rhs : lhs; }
	template<typename T>
	static inline T max(T rhs, T lhs) { return rhs > lhs ? rhs : lhs; }
	void flushSpan() {
	bool merge = false;
	if (tail-head == ssize_t(span.size())) {
	Rect const* p = cur;
	Rect const* q = head;
	if (p->top == q->bottom) {
	merge = true;
	while (q != tail) {
	if ((p->left != q->left) \|\| (p->right != q->right)) {
	merge = false;
	break;
	}
	p++, q++;
	}
	}
	}
	if (merge) {
	const int bottom = span[0].bottom;
	Rect* r = head;
	while (r != tail) {
	r->bottom = bottom;
	r++;
	}
	} else {
	bounds.left = min(span.itemAt(0).left, bounds.left);
	bounds.right = max(span.top().right, bounds.right);
	storage.appendVector(span);
	tail = storage.editArray() + storage.size();
	head = tail - span.size();
	}
	span.clear();
	}
	};

	bool Region::validate(const Region& reg, const char* name)
	{
	bool result = true;
	const_iterator cur = reg.begin();
	const_iterator const tail = reg.end();
	const_iterator prev = cur++;
	Rect b(*prev);
	while (cur != tail) {
	b.left = b.left < cur->left ? b.left : cur->left;
	b.top = b.top < cur->top ? b.top : cur->top;
	b.right = b.right > cur->right ? b.right : cur->right;
	b.bottom = b.bottom > cur->bottom ? b.bottom : cur->bottom;
	if (cur->top == prev->top) {
	if (cur->bottom != prev->bottom) {
	LOGE("%s: invalid span %p", name, cur);
	result = false;
	} else if (cur->left < prev->right) {
	LOGE("%s: spans overlap horizontally prev=%p, cur=%p",
	name, prev, cur);
	result = false;
	}
	} else if (cur->top < prev->bottom) {
	LOGE("%s: spans overlap vertically prev=%p, cur=%p",
	name, prev, cur);
	result = false;
	}
	prev = cur;
	cur++;
	}
	if (b != reg.getBounds()) {
	result = false;
	LOGE("%s: invalid bounds [%d,%d,%d,%d] vs. [%d,%d,%d,%d]", name,
	b.left, b.top, b.right, b.bottom,
	reg.getBounds().left, reg.getBounds().top,
	reg.getBounds().right, reg.getBounds().bottom);
	}
	if (result == false) {
	reg.dump(name);
	}
	return result;
	}

	void Region::boolean_operation(int op, Region& dst,
	const Region& lhs,
	const Region& rhs, int dx, int dy)
	{
	size_t lhs_count;
	Rect const * const lhs_rects = lhs.getArray(&lhs_count);

	size_t rhs_count;
	Rect const * const rhs_rects = rhs.getArray(&rhs_count);

	region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
	region_operator<Rect>::region rhs_region(rhs_rects, rhs_count, dx, dy);
	region_operator<Rect> operation(op, lhs_region, rhs_region);
	{ // scope for rasterizer (dtor has side effects)
	rasterizer r(dst);
	operation(r);
	}

	#if VALIDATE_REGIONS
	validate(lhs, "boolean_operation: lhs");
	validate(rhs, "boolean_operation: rhs");
	validate(dst, "boolean_operation: dst");
	#endif

	#if VALIDATE_WITH_CORECG
	SkRegion sk_lhs;
	SkRegion sk_rhs;
	SkRegion sk_dst;

	for (size_t i=0 ; i<lhs_count ; i++)
	sk_lhs.op(
	lhs_rects[i].left + dx,
	lhs_rects[i].top + dy,
	lhs_rects[i].right + dx,
	lhs_rects[i].bottom + dy,
	SkRegion::kUnion_Op);

	for (size_t i=0 ; i<rhs_count ; i++)
	sk_rhs.op(
	rhs_rects[i].left + dx,
	rhs_rects[i].top + dy,
	rhs_rects[i].right + dx,
	rhs_rects[i].bottom + dy,
	SkRegion::kUnion_Op);

	const char* name = "---";
	SkRegion::Op sk_op;
	switch (op) {
	case op_or: sk_op = SkRegion::kUnion_Op; name="OR"; break;
	case op_and: sk_op = SkRegion::kIntersect_Op; name="AND"; break;
	case op_nand: sk_op = SkRegion::kDifference_Op; name="NAND"; break;
	}
	sk_dst.op(sk_lhs, sk_rhs, sk_op);

	if (sk_dst.isEmpty() && dst.isEmpty())
	return;

	bool same = true;
	Region::const_iterator head = dst.begin();
	Region::const_iterator const tail = dst.end();
	SkRegion::Iterator it(sk_dst);
	while (!it.done()) {
	if (head != tail) {
	if (
	head->left != it.rect().fLeft \|\|
	head->top != it.rect().fTop \|\|
	head->right != it.rect().fRight \|\|
	head->bottom != it.rect().fBottom
	) {
	same = false;
	break;
	}
	} else {
	same = false;
	break;
	}
	head++;
	it.next();
	}

	if (head != tail) {
	same = false;
	}

	if(!same) {
	LOGD("---\nregion boolean %s failed", name);
	lhs.dump("lhs");
	rhs.dump("rhs");
	dst.dump("dst");
	LOGD("should be");
	SkRegion::Iterator it(sk_dst);
	while (!it.done()) {
	LOGD(" [%3d, %3d, %3d, %3d]",
	it.rect().fLeft,
	it.rect().fTop,
	it.rect().fRight,
	it.rect().fBottom);
	it.next();
	}
	}
	#endif
	}

	void Region::boolean_operation(int op, Region& dst,
	const Region& lhs,
	const Rect& rhs, int dx, int dy)
	{
	#if VALIDATE_WITH_CORECG \|\| VALIDATE_REGIONS
	boolean_operation(op, dst, lhs, Region(rhs), dx, dy);
	#else
	size_t lhs_count;
	Rect const * const lhs_rects = lhs.getArray(&lhs_count);

	region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
	region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy);
	region_operator<Rect> operation(op, lhs_region, rhs_region);
	{ // scope for rasterizer (dtor has side effects)
	rasterizer r(dst);
	operation(r);
	}

	#endif
	}

	void Region::boolean_operation(int op, Region& dst,
	const Region& lhs, const Region& rhs)
	{
	boolean_operation(op, dst, lhs, rhs, 0, 0);
	}

	void Region::boolean_operation(int op, Region& dst,
	const Region& lhs, const Rect& rhs)
	{
	boolean_operation(op, dst, lhs, rhs, 0, 0);
	}

	void Region::translate(Region& reg, int dx, int dy)
	{
	if (!reg.isEmpty()) {
	#if VALIDATE_REGIONS
	validate(reg, "translate (before)");
	#endif
	reg.mBounds.translate(dx, dy);
	size_t count = reg.mStorage.size();
	Rect* rects = reg.mStorage.editArray();
	while (count) {
	rects->translate(dx, dy);
	rects++;
	count--;
	}
	#if VALIDATE_REGIONS
	validate(reg, "translate (after)");
	#endif
	}
	}

	void Region::translate(Region& dst, const Region& reg, int dx, int dy)
	{
	dst = reg;
	translate(dst, dx, dy);
	}

	// ----------------------------------------------------------------------------

	ssize_t Region::write(void* buffer, size_t size) const
	{
	#if VALIDATE_REGIONS
	validate(*this, "write(buffer)");
	#endif
	const size_t count = mStorage.size();
	const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect);
	if (buffer != NULL) {
	if (sizeNeeded > size) return NO_MEMORY;
	int32_t* const p = static_cast<int32_t*>(buffer);
	*p = count;
	memcpy(p+1, &mBounds, sizeof(Rect));
	if (count) {
	memcpy(p+5, mStorage.array(), count*sizeof(Rect));
	}
	}
	return ssize_t(sizeNeeded);
	}

	ssize_t Region::read(const void* buffer)
	{
	int32_t const* const p = static_cast<int32_t const*>(buffer);
	const size_t count = *p;
	memcpy(&mBounds, p+1, sizeof(Rect));
	mStorage.clear();
	if (count) {
	mStorage.insertAt(0, count);
	memcpy(mStorage.editArray(), p+5, count*sizeof(Rect));
	}
	#if VALIDATE_REGIONS
	validate(*this, "read(buffer)");
	#endif
	return ssize_t(sizeof(int32_t) + (1+count)*sizeof(Rect));
	}

	ssize_t Region::writeEmpty(void* buffer, size_t size)
	{
	const size_t sizeNeeded = sizeof(int32_t) + sizeof(Rect);
	if (sizeNeeded > size) return NO_MEMORY;
	int32_t* const p = static_cast<int32_t*>(buffer);
	memset(p, 0, sizeNeeded);
	return ssize_t(sizeNeeded);
	}

	bool Region::isEmpty(void* buffer)
	{
	int32_t const* const p = static_cast<int32_t const*>(buffer);
	Rect const* const b = reinterpret_cast<Rect const *>(p+1);
	return b->isEmpty();
	}

	// ----------------------------------------------------------------------------

	Region::const_iterator Region::begin() const {
	return isRect() ? &mBounds : mStorage.array();
	}

	Region::const_iterator Region::end() const {
	return isRect() ? ((&mBounds) + 1) : (mStorage.array() + mStorage.size());
	}

	Rect const* Region::getArray(size_t* count) const {
	const_iterator const b(begin());
	const_iterator const e(end());
	if (count) *count = e-b;
	return b;
	}

	size_t Region::getRects(Vector<Rect>& rectList) const
	{
	rectList = mStorage;
	if (rectList.isEmpty()) {
	rectList.clear();
	rectList.add(mBounds);
	}
	return rectList.size();
	}

	// ----------------------------------------------------------------------------

	void Region::dump(String8& out, const char* what, uint32_t flags) const
	{
	(void)flags;
	const_iterator head = begin();
	const_iterator const tail = end();

	size_t SIZE = 256;
	char buffer[SIZE];

	snprintf(buffer, SIZE, " Region %s (this=%p, count=%d)\n",
	what, this, tail-head);
	out.append(buffer);
	while (head != tail) {
	snprintf(buffer, SIZE, " [%3d, %3d, %3d, %3d]\n",
	head->left, head->top, head->right, head->bottom);
	out.append(buffer);
	head++;
	}
	}

	void Region::dump(const char* what, uint32_t flags) const
	{
	(void)flags;
	const_iterator head = begin();
	const_iterator const tail = end();
	LOGD(" Region %s (this=%p, count=%d)\n", what, this, tail-head);
	while (head != tail) {
	LOGD(" [%3d, %3d, %3d, %3d]\n",
	head->left, head->top, head->right, head->bottom);
	head++;
	}
	}

	// ----------------------------------------------------------------------------

	}; // namespace android