third_party/blink/renderer/platform/geometry/region.cc - chromium/src - Git at Google

 /*
  * Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  * THE POSSIBILITY OF SUCH DAMAGE.
  */

 #include "third_party/blink/renderer/platform/geometry/region.h"

 #include <stdio.h>

 namespace blink {

 Region::Region() = default;

 Region::Region(const IntRect& rect) : bounds_(rect), shape_(rect) {}

 Vector<IntRect> Region::Rects() const {
   Vector<IntRect> rects;

   for (Shape::SpanIterator span = shape_.SpansBegin(), end = shape_.SpansEnd();
        span != end && span + 1 != end; ++span) {
     int y = span->y;
     int height = (span + 1)->y - y;

     for (Shape::SegmentIterator segment = shape_.SegmentsBegin(span),
                                 segment_end = shape_.SegmentsEnd(span);
          segment != segment_end && segment + 1 != segment_end; segment += 2) {
       int x = *segment;
       int width = *(segment + 1) - x;

       rects.push_back(IntRect(x, y, width, height));
     }
   }

   return rects;
 }

 bool Region::Contains(const Region& region) const {
   if (!bounds_.Contains(region.bounds_))
     return false;

   return Shape::CompareShapes<Shape::CompareContainsOperation>(shape_,
                                                                region.shape_);
 }

 bool Region::Contains(const IntPoint& point) const {
   if (!bounds_.Contains(point))
     return false;

   for (Shape::SpanIterator span = shape_.SpansBegin(), end = shape_.SpansEnd();
        span != end && span + 1 != end; ++span) {
     int y = span->y;
     int max_y = (span + 1)->y;

     if (y > point.Y())
       break;
     if (max_y <= point.Y())
       continue;

     for (Shape::SegmentIterator segment = shape_.SegmentsBegin(span),
                                 segment_end = shape_.SegmentsEnd(span);
          segment != segment_end && segment + 1 != segment_end; segment += 2) {
       int x = *segment;
       int max_x = *(segment + 1);

       if (x > point.X())
         break;
       if (max_x > point.X())
         return true;
     }
   }

   return false;
 }

 bool Region::Intersects(const Region& region) const {
   if (!bounds_.Intersects(region.bounds_))
     return false;

   return Shape::CompareShapes<Shape::CompareIntersectsOperation>(shape_,
                                                                  region.shape_);
 }

 uint64_t Region::Area() const {
   uint64_t area = 0;
   for (Shape::SpanIterator span = shape_.SpansBegin(), end = shape_.SpansEnd();
        span != end && span + 1 != end; ++span) {
     int height = (span + 1)->y - span->y;

     for (Shape::SegmentIterator segment = shape_.SegmentsBegin(span),
                                 segment_end = shape_.SegmentsEnd(span);
          segment != segment_end && segment + 1 != segment_end; segment += 2) {
       int width = *(segment + 1) - *segment;
       area += (uint64_t)height * (uint64_t)width;
     }
   }
   return area;
 }

 template <typename CompareOperation>
 bool Region::Shape::CompareShapes(const Shape& a_shape, const Shape& b_shape) {
   bool result = CompareOperation::kDefaultResult;

   Shape::SpanIterator a_span = a_shape.SpansBegin();
   Shape::SpanIterator a_span_end = a_shape.SpansEnd();
   Shape::SpanIterator b_span = b_shape.SpansBegin();
   Shape::SpanIterator b_span_end = b_shape.SpansEnd();

   bool a_had_segment_in_previous_span = false;
   bool b_had_segment_in_previous_span = false;
   while (a_span != a_span_end && a_span + 1 != a_span_end &&
          b_span != b_span_end && b_span + 1 != b_span_end) {
     int a_y = a_span->y;
     int a_max_y = (a_span + 1)->y;
     int b_y = b_span->y;
     int b_max_y = (b_span + 1)->y;

     Shape::SegmentIterator a_segment = a_shape.SegmentsBegin(a_span);
     Shape::SegmentIterator a_segment_end = a_shape.SegmentsEnd(a_span);
     Shape::SegmentIterator b_segment = b_shape.SegmentsBegin(b_span);
     Shape::SegmentIterator b_segment_end = b_shape.SegmentsEnd(b_span);

     // Look for a non-overlapping part of the spans. If B had a segment in its
     // previous span, then we already tested A against B within that span.
     bool a_has_segment_in_span = a_segment != a_segment_end;
     bool b_has_segment_in_span = b_segment != b_segment_end;
     if (a_y < b_y && !b_had_segment_in_previous_span && a_has_segment_in_span &&
         CompareOperation::AOutsideB(result))
       return result;
     if (b_y < a_y && !a_had_segment_in_previous_span && b_has_segment_in_span &&
         CompareOperation::BOutsideA(result))
       return result;

     a_had_segment_in_previous_span = a_has_segment_in_span;
     b_had_segment_in_previous_span = b_has_segment_in_span;

     bool spans_overlap = b_max_y > a_y && b_y < a_max_y;
     if (spans_overlap) {
       while (a_segment != a_segment_end && b_segment != b_segment_end) {
         int a_x = *a_segment;
         int a_max_x = *(a_segment + 1);
         int b_x = *b_segment;
         int b_max_x = *(b_segment + 1);

         bool segments_overlap = b_max_x > a_x && b_x < a_max_x;
         if (segments_overlap && CompareOperation::AOverlapsB(result))
           return result;
         if (a_x < b_x && CompareOperation::AOutsideB(result))
           return result;
         if (b_x < a_x && CompareOperation::BOutsideA(result))
           return result;

         if (a_max_x < b_max_x) {
           a_segment += 2;
         } else if (b_max_x < a_max_x) {
           b_segment += 2;
         } else {
           a_segment += 2;
           b_segment += 2;
         }
       }

       if (a_segment != a_segment_end && CompareOperation::AOutsideB(result))
         return result;
       if (b_segment != b_segment_end && CompareOperation::BOutsideA(result))
         return result;
     }

     if (a_max_y < b_max_y) {
       a_span += 1;
     } else if (b_max_y < a_max_y) {
       b_span += 1;
     } else {
       a_span += 1;
       b_span += 1;
     }
   }

   if (a_span != a_span_end && a_span + 1 != a_span_end &&
       CompareOperation::AOutsideB(result))
     return result;
   if (b_span != b_span_end && b_span + 1 != b_span_end &&
       CompareOperation::BOutsideA(result))
     return result;

   return result;
 }

 void Region::Shape::TrimCapacities() {
   segments_.ShrinkToReasonableCapacity();
   spans_.ShrinkToReasonableCapacity();
 }

 struct Region::Shape::CompareContainsOperation {
   STATIC_ONLY(CompareContainsOperation);
   const static bool kDefaultResult = true;
   inline static bool AOutsideB(bool& /* result */) { return false; }
   inline static bool BOutsideA(bool& result) {
     result = false;
     return true;
   }
   inline static bool AOverlapsB(bool& /* result */) { return false; }
 };

 struct Region::Shape::CompareIntersectsOperation {
   STATIC_ONLY(CompareIntersectsOperation);
   const static bool kDefaultResult = false;
   inline static bool AOutsideB(bool& /* result */) { return false; }
   inline static bool BOutsideA(bool& /* result */) { return false; }
   inline static bool AOverlapsB(bool& result) {
     result = true;
     return true;
   }
 };

 Region::Shape::Shape() = default;

 Region::Shape::Shape(const IntRect& rect) {
   AppendSpan(rect.Y());
   AppendSegment(rect.X());
   AppendSegment(rect.MaxX());
   AppendSpan(rect.MaxY());
 }

 Region::Shape::Shape(wtf_size_t segments_capacity, wtf_size_t spans_capacity) {
   segments_.ReserveCapacity(segments_capacity);
   spans_.ReserveCapacity(spans_capacity);
 }

 void Region::Shape::AppendSpan(int y) {
   spans_.push_back(Span(y, segments_.size()));
 }

 bool Region::Shape::CanCoalesce(SegmentIterator begin, SegmentIterator end) {
   if (spans_.IsEmpty())
     return false;

   SegmentIterator last_span_begin =
       segments_.data() + spans_.back().segment_index;
   SegmentIterator last_span_end = segments_.data() + segments_.size();

   // Check if both spans have an equal number of segments.
   if (last_span_end - last_span_begin != end - begin)
     return false;

   // Check if both spans are equal.
   if (!std::equal(begin, end, last_span_begin))
     return false;

   // Since the segments are equal the second segment can just be ignored.
   return true;
 }

 void Region::Shape::AppendSpan(int y,
                                SegmentIterator begin,
                                SegmentIterator end) {
   if (CanCoalesce(begin, end))
     return;

   AppendSpan(y);
   segments_.AppendRange(begin, end);
 }

 void Region::Shape::AppendSpans(const Shape& shape,
                                 SpanIterator begin,
                                 SpanIterator end) {
   for (SpanIterator it = begin; it != end; ++it)
     AppendSpan(it->y, shape.SegmentsBegin(it), shape.SegmentsEnd(it));
 }

 void Region::Shape::AppendSegment(int x) {
   segments_.push_back(x);
 }

 Region::Shape::SpanIterator Region::Shape::SpansBegin() const {
   return spans_.data();
 }

 Region::Shape::SpanIterator Region::Shape::SpansEnd() const {
   return spans_.data() + spans_.size();
 }

 Region::Shape::SegmentIterator Region::Shape::SegmentsBegin(
     SpanIterator it) const {
   DCHECK_GE(it, spans_.data());
   DCHECK_LT(it, spans_.data() + spans_.size());

   // Check if this span has any segments.
   if (it->segment_index == segments_.size())
     return nullptr;

   return &segments_[it->segment_index];
 }

 Region::Shape::SegmentIterator Region::Shape::SegmentsEnd(
     SpanIterator it) const {
   DCHECK_GE(it, spans_.data());
   DCHECK_LT(it, spans_.data() + spans_.size());

   // Check if this span has any segments.
   if (it->segment_index == segments_.size())
     return nullptr;

   DCHECK_LT(it + 1, spans_.data() + spans_.size());
   wtf_size_t segment_index = (it + 1)->segment_index;

   SECURITY_DCHECK(segment_index <= segments_.size());
   return segments_.data() + segment_index;
 }

 #ifndef NDEBUG
 void Region::Shape::Dump() const {
   for (Shape::SpanIterator span = SpansBegin(), end = SpansEnd(); span != end;
        ++span) {
     printf("%6d: (", span->y);

     for (Shape::SegmentIterator segment = SegmentsBegin(span),
                                 segment_end = SegmentsEnd(span);
          segment != segment_end; ++segment)
       printf("%d ", *segment);
     printf(")\n");
   }

   printf("\n");
 }
 #endif

 IntRect Region::Shape::Bounds() const {
   if (IsEmpty())
     return IntRect();

   SpanIterator span = SpansBegin();
   int min_y = span->y;

   SpanIterator last_span = SpansEnd() - 1;
   int max_y = last_span->y;

   int min_x = std::numeric_limits<int>::max();
   int max_x = std::numeric_limits<int>::min();

   while (span != last_span) {
     SegmentIterator first_segment = SegmentsBegin(span);
     SegmentIterator last_segment = SegmentsEnd(span) - 1;

     if (first_segment && last_segment) {
       DCHECK_NE(first_segment, last_segment);

       if (*first_segment < min_x)
         min_x = *first_segment;

       if (*last_segment > max_x)
         max_x = *last_segment;
     }

     ++span;
   }

   DCHECK_LE(min_x, max_x);
   DCHECK_LE(min_y, max_y);

   return IntRect(min_x, min_y, max_x - min_x, max_y - min_y);
 }

 void Region::Shape::Translate(const IntSize& offset) {
   for (wtf_size_t i = 0; i < segments_.size(); ++i)
     segments_[i] += offset.Width();
   for (wtf_size_t i = 0; i < spans_.size(); ++i)
     spans_[i].y += offset.Height();
 }

 void Region::Shape::Swap(Shape& other) {
   segments_.swap(other.segments_);
   spans_.swap(other.spans_);
 }

 enum {
   kShape1,
   kShape2,
 };

 template <typename Operation>
 Region::Shape Region::Shape::ShapeOperation(const Shape& shape1,
                                             const Shape& shape2) {
   static_assert(!(!Operation::kShouldAddRemainingSegmentsFromSpan1 &&
                   Operation::kShouldAddRemainingSegmentsFromSpan2),
                 "invalid segment combination");
   static_assert(!(!Operation::kShouldAddRemainingSpansFromShape1 &&
                   Operation::kShouldAddRemainingSpansFromShape2),
                 "invalid span combination");

   wtf_size_t segments_capacity = shape1.SegmentsSize() + shape2.SegmentsSize();
   wtf_size_t spans_capacity = shape1.SpansSize() + shape2.SpansSize();
   Shape result(segments_capacity, spans_capacity);
   if (Operation::TrySimpleOperation(shape1, shape2, result))
     return result;

   SpanIterator spans1 = shape1.SpansBegin();
   SpanIterator spans1_end = shape1.SpansEnd();

   SpanIterator spans2 = shape2.SpansBegin();
   SpanIterator spans2_end = shape2.SpansEnd();

   SegmentIterator segments1 = nullptr;
   SegmentIterator segments1_end = nullptr;

   SegmentIterator segments2 = nullptr;
   SegmentIterator segments2_end = nullptr;

   Vector<int, 32> segments;
   segments.ReserveCapacity(
       std::max(shape1.SegmentsSize(), shape2.SegmentsSize()));

   // Iterate over all spans.
   while (spans1 != spans1_end && spans2 != spans2_end) {
     int y = 0;
     int y_diff = spans1->y - spans2->y;

     if (y_diff <= 0) {
       y = spans1->y;

       segments1 = shape1.SegmentsBegin(spans1);
       segments1_end = shape1.SegmentsEnd(spans1);
       ++spans1;
     }
     if (y_diff >= 0) {
       y = spans2->y;

       segments2 = shape2.SegmentsBegin(spans2);
       segments2_end = shape2.SegmentsEnd(spans2);
       ++spans2;
     }

     int flag = 0;
     int old_flag = 0;

     SegmentIterator s1 = segments1;
     SegmentIterator s2 = segments2;

     // Clear vector without dropping capacity.
     segments.resize(0);
     DCHECK(segments.capacity());

     // Now iterate over the segments in each span and construct a new vector of
     // segments.
     while (s1 != segments1_end && s2 != segments2_end) {
       int s_diff = *s1 - *s2;
       int x;

       if (s_diff <= 0) {
         x = *s1;
         flag = flag ^ 1;
         ++s1;
       }
       if (s_diff >= 0) {
         x = *s2;
         flag = flag ^ 2;
         ++s2;
       }

       if (flag == Operation::kOpCode || old_flag == Operation::kOpCode)
         segments.push_back(x);

       old_flag = flag;
     }

     // Add any remaining segments.
     if (Operation::kShouldAddRemainingSegmentsFromSpan1 && s1 != segments1_end)
       segments.AppendRange(s1, segments1_end);
     else if (Operation::kShouldAddRemainingSegmentsFromSpan2 &&
              s2 != segments2_end)
       segments.AppendRange(s2, segments2_end);

     // Add the span.
     if (!segments.IsEmpty() || !result.IsEmpty())
       result.AppendSpan(y, segments.data(), segments.data() + segments.size());
   }

   // Add any remaining spans.
   if (Operation::kShouldAddRemainingSpansFromShape1 && spans1 != spans1_end)
     result.AppendSpans(shape1, spans1, spans1_end);
   else if (Operation::kShouldAddRemainingSpansFromShape2 &&
            spans2 != spans2_end)
     result.AppendSpans(shape2, spans2, spans2_end);

   result.TrimCapacities();

   return result;
 }

 struct Region::Shape::UnionOperation {
   STATIC_ONLY(UnionOperation);
   static bool TrySimpleOperation(const Shape& shape1,
                                  const Shape& shape2,
                                  Shape& result) {
     if (shape1.IsEmpty()) {
       result = shape2;
       return true;
     }

     return false;
   }

   static const int kOpCode = 0;

   static const bool kShouldAddRemainingSegmentsFromSpan1 = true;
   static const bool kShouldAddRemainingSegmentsFromSpan2 = true;
   static const bool kShouldAddRemainingSpansFromShape1 = true;
   static const bool kShouldAddRemainingSpansFromShape2 = true;
 };

 Region::Shape Region::Shape::UnionShapes(const Shape& shape1,
                                          const Shape& shape2) {
   return ShapeOperation<UnionOperation>(shape1, shape2);
 }

 struct Region::Shape::IntersectOperation {
   STATIC_ONLY(IntersectOperation);
   static bool TrySimpleOperation(const Shape&, const Shape&, Shape&) {
     return false;
   }

   static const int kOpCode = 3;

   static const bool kShouldAddRemainingSegmentsFromSpan1 = false;
   static const bool kShouldAddRemainingSegmentsFromSpan2 = false;
   static const bool kShouldAddRemainingSpansFromShape1 = false;
   static const bool kShouldAddRemainingSpansFromShape2 = false;
 };

 Region::Shape Region::Shape::IntersectShapes(const Shape& shape1,
                                              const Shape& shape2) {
   return ShapeOperation<IntersectOperation>(shape1, shape2);
 }

 struct Region::Shape::SubtractOperation {
   STATIC_ONLY(SubtractOperation);
   static bool TrySimpleOperation(const Shape&, const Shape&, Region::Shape&) {
     return false;
   }

   static const int kOpCode = 1;

   static const bool kShouldAddRemainingSegmentsFromSpan1 = true;
   static const bool kShouldAddRemainingSegmentsFromSpan2 = false;
   static const bool kShouldAddRemainingSpansFromShape1 = true;
   static const bool kShouldAddRemainingSpansFromShape2 = false;
 };

 Region::Shape Region::Shape::SubtractShapes(const Shape& shape1,
                                             const Shape& shape2) {
   return ShapeOperation<SubtractOperation>(shape1, shape2);
 }

 #ifndef NDEBUG
 void Region::Dump() const {
   printf("Bounds: (%d, %d, %d, %d)\n", bounds_.X(), bounds_.Y(),
          bounds_.Width(), bounds_.Height());
   shape_.Dump();
 }
 #endif

 void Region::Intersect(const Region& region) {
   if (bounds_.IsEmpty())
     return;
   if (!bounds_.Intersects(region.bounds_)) {
     shape_ = Shape();
     bounds_ = IntRect();
     return;
   }

   Shape intersected_shape = Shape::IntersectShapes(shape_, region.shape_);

   shape_.Swap(intersected_shape);
   bounds_ = shape_.Bounds();
 }

 void Region::Unite(const Region& region) {
   if (region.IsEmpty())
     return;
   if (IsRect() && bounds_.Contains(region.bounds_))
     return;
   if (region.IsRect() && region.bounds_.Contains(bounds_)) {
     shape_ = region.shape_;
     bounds_ = region.bounds_;
     return;
   }
   // FIXME: We may want another way to construct a Region without doing this
   // test when we expect it to be false.
   if (!IsRect() && Contains(region))
     return;

   Shape united_shape = Shape::UnionShapes(shape_, region.shape_);

   shape_.Swap(united_shape);
   bounds_.Unite(region.bounds_);
 }

 void Region::Subtract(const Region& region) {
   if (bounds_.IsEmpty())
     return;
   if (region.IsEmpty())
     return;
   if (!bounds_.Intersects(region.bounds_))
     return;

   Shape subtracted_shape = Shape::SubtractShapes(shape_, region.shape_);

   shape_.Swap(subtracted_shape);
   bounds_ = shape_.Bounds();
 }

 void Region::Translate(const IntSize& offset) {
   bounds_.Move(offset);
   shape_.Translate(offset);
 }

 }  // namespace blink
	/*
	* Copyright (C) 2010, 2011 Apple Inc. All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	*
	* THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
	* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
	* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
	* THE POSSIBILITY OF SUCH DAMAGE.
	*/

	#include "third_party/blink/renderer/platform/geometry/region.h"

	#include <stdio.h>

	namespace blink {

	Region::Region() = default;

	Region::Region(const IntRect& rect) : bounds_(rect), shape_(rect) {}

	Vector<IntRect> Region::Rects() const {
	Vector<IntRect> rects;

	for (Shape::SpanIterator span = shape_.SpansBegin(), end = shape_.SpansEnd();
	span != end && span + 1 != end; ++span) {
	int y = span->y;
	int height = (span + 1)->y - y;

	for (Shape::SegmentIterator segment = shape_.SegmentsBegin(span),
	segment_end = shape_.SegmentsEnd(span);
	segment != segment_end && segment + 1 != segment_end; segment += 2) {
	int x = *segment;
	int width = *(segment + 1) - x;

	rects.push_back(IntRect(x, y, width, height));
	}
	}

	return rects;
	}

	bool Region::Contains(const Region& region) const {
	if (!bounds_.Contains(region.bounds_))
	return false;

	return Shape::CompareShapes<Shape::CompareContainsOperation>(shape_,
	region.shape_);
	}

	bool Region::Contains(const IntPoint& point) const {
	if (!bounds_.Contains(point))
	return false;

	for (Shape::SpanIterator span = shape_.SpansBegin(), end = shape_.SpansEnd();
	span != end && span + 1 != end; ++span) {
	int y = span->y;
	int max_y = (span + 1)->y;

	if (y > point.Y())
	break;
	if (max_y <= point.Y())
	continue;

	for (Shape::SegmentIterator segment = shape_.SegmentsBegin(span),
	segment_end = shape_.SegmentsEnd(span);
	segment != segment_end && segment + 1 != segment_end; segment += 2) {
	int x = *segment;
	int max_x = *(segment + 1);

	if (x > point.X())
	break;
	if (max_x > point.X())
	return true;
	}
	}

	return false;
	}

	bool Region::Intersects(const Region& region) const {
	if (!bounds_.Intersects(region.bounds_))
	return false;

	return Shape::CompareShapes<Shape::CompareIntersectsOperation>(shape_,
	region.shape_);
	}

	uint64_t Region::Area() const {
	uint64_t area = 0;
	for (Shape::SpanIterator span = shape_.SpansBegin(), end = shape_.SpansEnd();
	span != end && span + 1 != end; ++span) {
	int height = (span + 1)->y - span->y;

	for (Shape::SegmentIterator segment = shape_.SegmentsBegin(span),
	segment_end = shape_.SegmentsEnd(span);
	segment != segment_end && segment + 1 != segment_end; segment += 2) {
	int width = (segment + 1) - segment;
	area += (uint64_t)height * (uint64_t)width;
	}
	}
	return area;
	}

	template <typename CompareOperation>
	bool Region::Shape::CompareShapes(const Shape& a_shape, const Shape& b_shape) {
	bool result = CompareOperation::kDefaultResult;

	Shape::SpanIterator a_span = a_shape.SpansBegin();
	Shape::SpanIterator a_span_end = a_shape.SpansEnd();
	Shape::SpanIterator b_span = b_shape.SpansBegin();
	Shape::SpanIterator b_span_end = b_shape.SpansEnd();

	bool a_had_segment_in_previous_span = false;
	bool b_had_segment_in_previous_span = false;
	while (a_span != a_span_end && a_span + 1 != a_span_end &&
	b_span != b_span_end && b_span + 1 != b_span_end) {
	int a_y = a_span->y;
	int a_max_y = (a_span + 1)->y;
	int b_y = b_span->y;
	int b_max_y = (b_span + 1)->y;

	Shape::SegmentIterator a_segment = a_shape.SegmentsBegin(a_span);
	Shape::SegmentIterator a_segment_end = a_shape.SegmentsEnd(a_span);
	Shape::SegmentIterator b_segment = b_shape.SegmentsBegin(b_span);
	Shape::SegmentIterator b_segment_end = b_shape.SegmentsEnd(b_span);

	// Look for a non-overlapping part of the spans. If B had a segment in its
	// previous span, then we already tested A against B within that span.
	bool a_has_segment_in_span = a_segment != a_segment_end;
	bool b_has_segment_in_span = b_segment != b_segment_end;
	if (a_y < b_y && !b_had_segment_in_previous_span && a_has_segment_in_span &&
	CompareOperation::AOutsideB(result))
	return result;
	if (b_y < a_y && !a_had_segment_in_previous_span && b_has_segment_in_span &&
	CompareOperation::BOutsideA(result))
	return result;

	a_had_segment_in_previous_span = a_has_segment_in_span;
	b_had_segment_in_previous_span = b_has_segment_in_span;

	bool spans_overlap = b_max_y > a_y && b_y < a_max_y;
	if (spans_overlap) {
	while (a_segment != a_segment_end && b_segment != b_segment_end) {
	int a_x = *a_segment;
	int a_max_x = *(a_segment + 1);
	int b_x = *b_segment;
	int b_max_x = *(b_segment + 1);

	bool segments_overlap = b_max_x > a_x && b_x < a_max_x;
	if (segments_overlap && CompareOperation::AOverlapsB(result))
	return result;
	if (a_x < b_x && CompareOperation::AOutsideB(result))
	return result;
	if (b_x < a_x && CompareOperation::BOutsideA(result))
	return result;

	if (a_max_x < b_max_x) {
	a_segment += 2;
	} else if (b_max_x < a_max_x) {
	b_segment += 2;
	} else {
	a_segment += 2;
	b_segment += 2;
	}
	}

	if (a_segment != a_segment_end && CompareOperation::AOutsideB(result))
	return result;
	if (b_segment != b_segment_end && CompareOperation::BOutsideA(result))
	return result;
	}

	if (a_max_y < b_max_y) {
	a_span += 1;
	} else if (b_max_y < a_max_y) {
	b_span += 1;
	} else {
	a_span += 1;
	b_span += 1;
	}
	}

	if (a_span != a_span_end && a_span + 1 != a_span_end &&
	CompareOperation::AOutsideB(result))
	return result;
	if (b_span != b_span_end && b_span + 1 != b_span_end &&
	CompareOperation::BOutsideA(result))
	return result;

	return result;
	}

	void Region::Shape::TrimCapacities() {
	segments_.ShrinkToReasonableCapacity();
	spans_.ShrinkToReasonableCapacity();
	}

	struct Region::Shape::CompareContainsOperation {
	STATIC_ONLY(CompareContainsOperation);
	const static bool kDefaultResult = true;
	inline static bool AOutsideB(bool& /* result */) { return false; }
	inline static bool BOutsideA(bool& result) {
	result = false;
	return true;
	}
	inline static bool AOverlapsB(bool& /* result */) { return false; }
	};

	struct Region::Shape::CompareIntersectsOperation {
	STATIC_ONLY(CompareIntersectsOperation);
	const static bool kDefaultResult = false;
	inline static bool AOutsideB(bool& /* result */) { return false; }
	inline static bool BOutsideA(bool& /* result */) { return false; }
	inline static bool AOverlapsB(bool& result) {
	result = true;
	return true;
	}
	};

	Region::Shape::Shape() = default;

	Region::Shape::Shape(const IntRect& rect) {
	AppendSpan(rect.Y());
	AppendSegment(rect.X());
	AppendSegment(rect.MaxX());
	AppendSpan(rect.MaxY());
	}

	Region::Shape::Shape(wtf_size_t segments_capacity, wtf_size_t spans_capacity) {
	segments_.ReserveCapacity(segments_capacity);
	spans_.ReserveCapacity(spans_capacity);
	}

	void Region::Shape::AppendSpan(int y) {
	spans_.push_back(Span(y, segments_.size()));
	}

	bool Region::Shape::CanCoalesce(SegmentIterator begin, SegmentIterator end) {
	if (spans_.IsEmpty())
	return false;

	SegmentIterator last_span_begin =
	segments_.data() + spans_.back().segment_index;
	SegmentIterator last_span_end = segments_.data() + segments_.size();

	// Check if both spans have an equal number of segments.
	if (last_span_end - last_span_begin != end - begin)
	return false;

	// Check if both spans are equal.
	if (!std::equal(begin, end, last_span_begin))
	return false;

	// Since the segments are equal the second segment can just be ignored.
	return true;
	}

	void Region::Shape::AppendSpan(int y,
	SegmentIterator begin,
	SegmentIterator end) {
	if (CanCoalesce(begin, end))
	return;

	AppendSpan(y);
	segments_.AppendRange(begin, end);
	}

	void Region::Shape::AppendSpans(const Shape& shape,
	SpanIterator begin,
	SpanIterator end) {
	for (SpanIterator it = begin; it != end; ++it)
	AppendSpan(it->y, shape.SegmentsBegin(it), shape.SegmentsEnd(it));
	}

	void Region::Shape::AppendSegment(int x) {
	segments_.push_back(x);
	}

	Region::Shape::SpanIterator Region::Shape::SpansBegin() const {
	return spans_.data();
	}

	Region::Shape::SpanIterator Region::Shape::SpansEnd() const {
	return spans_.data() + spans_.size();
	}

	Region::Shape::SegmentIterator Region::Shape::SegmentsBegin(
	SpanIterator it) const {
	DCHECK_GE(it, spans_.data());
	DCHECK_LT(it, spans_.data() + spans_.size());

	// Check if this span has any segments.
	if (it->segment_index == segments_.size())
	return nullptr;

	return &segments_[it->segment_index];
	}

	Region::Shape::SegmentIterator Region::Shape::SegmentsEnd(
	SpanIterator it) const {
	DCHECK_GE(it, spans_.data());
	DCHECK_LT(it, spans_.data() + spans_.size());

	// Check if this span has any segments.
	if (it->segment_index == segments_.size())
	return nullptr;

	DCHECK_LT(it + 1, spans_.data() + spans_.size());
	wtf_size_t segment_index = (it + 1)->segment_index;

	SECURITY_DCHECK(segment_index <= segments_.size());
	return segments_.data() + segment_index;
	}

	#ifndef NDEBUG
	void Region::Shape::Dump() const {
	for (Shape::SpanIterator span = SpansBegin(), end = SpansEnd(); span != end;
	++span) {
	printf("%6d: (", span->y);

	for (Shape::SegmentIterator segment = SegmentsBegin(span),
	segment_end = SegmentsEnd(span);
	segment != segment_end; ++segment)
	printf("%d ", *segment);
	printf(")\n");
	}

	printf("\n");
	}
	#endif

	IntRect Region::Shape::Bounds() const {
	if (IsEmpty())
	return IntRect();

	SpanIterator span = SpansBegin();
	int min_y = span->y;

	SpanIterator last_span = SpansEnd() - 1;
	int max_y = last_span->y;

	int min_x = std::numeric_limits<int>::max();
	int max_x = std::numeric_limits<int>::min();

	while (span != last_span) {
	SegmentIterator first_segment = SegmentsBegin(span);
	SegmentIterator last_segment = SegmentsEnd(span) - 1;

	if (first_segment && last_segment) {
	DCHECK_NE(first_segment, last_segment);

	if (*first_segment < min_x)
	min_x = *first_segment;

	if (*last_segment > max_x)
	max_x = *last_segment;
	}

	++span;
	}

	DCHECK_LE(min_x, max_x);
	DCHECK_LE(min_y, max_y);

	return IntRect(min_x, min_y, max_x - min_x, max_y - min_y);
	}

	void Region::Shape::Translate(const IntSize& offset) {
	for (wtf_size_t i = 0; i < segments_.size(); ++i)
	segments_[i] += offset.Width();
	for (wtf_size_t i = 0; i < spans_.size(); ++i)
	spans_[i].y += offset.Height();
	}

	void Region::Shape::Swap(Shape& other) {
	segments_.swap(other.segments_);
	spans_.swap(other.spans_);
	}

	enum {
	kShape1,
	kShape2,
	};

	template <typename Operation>
	Region::Shape Region::Shape::ShapeOperation(const Shape& shape1,
	const Shape& shape2) {
	static_assert(!(!Operation::kShouldAddRemainingSegmentsFromSpan1 &&
	Operation::kShouldAddRemainingSegmentsFromSpan2),
	"invalid segment combination");
	static_assert(!(!Operation::kShouldAddRemainingSpansFromShape1 &&
	Operation::kShouldAddRemainingSpansFromShape2),
	"invalid span combination");

	wtf_size_t segments_capacity = shape1.SegmentsSize() + shape2.SegmentsSize();
	wtf_size_t spans_capacity = shape1.SpansSize() + shape2.SpansSize();
	Shape result(segments_capacity, spans_capacity);
	if (Operation::TrySimpleOperation(shape1, shape2, result))
	return result;

	SpanIterator spans1 = shape1.SpansBegin();
	SpanIterator spans1_end = shape1.SpansEnd();

	SpanIterator spans2 = shape2.SpansBegin();
	SpanIterator spans2_end = shape2.SpansEnd();

	SegmentIterator segments1 = nullptr;
	SegmentIterator segments1_end = nullptr;

	SegmentIterator segments2 = nullptr;
	SegmentIterator segments2_end = nullptr;

	Vector<int, 32> segments;
	segments.ReserveCapacity(
	std::max(shape1.SegmentsSize(), shape2.SegmentsSize()));

	// Iterate over all spans.
	while (spans1 != spans1_end && spans2 != spans2_end) {
	int y = 0;
	int y_diff = spans1->y - spans2->y;

	if (y_diff <= 0) {
	y = spans1->y;

	segments1 = shape1.SegmentsBegin(spans1);
	segments1_end = shape1.SegmentsEnd(spans1);
	++spans1;
	}
	if (y_diff >= 0) {
	y = spans2->y;

	segments2 = shape2.SegmentsBegin(spans2);
	segments2_end = shape2.SegmentsEnd(spans2);
	++spans2;
	}

	int flag = 0;
	int old_flag = 0;

	SegmentIterator s1 = segments1;
	SegmentIterator s2 = segments2;

	// Clear vector without dropping capacity.
	segments.resize(0);
	DCHECK(segments.capacity());

	// Now iterate over the segments in each span and construct a new vector of
	// segments.
	while (s1 != segments1_end && s2 != segments2_end) {
	int s_diff = s1 - s2;
	int x;

	if (s_diff <= 0) {
	x = *s1;
	flag = flag ^ 1;
	++s1;
	}
	if (s_diff >= 0) {
	x = *s2;
	flag = flag ^ 2;
	++s2;
	}

	if (flag == Operation::kOpCode \|\| old_flag == Operation::kOpCode)
	segments.push_back(x);

	old_flag = flag;
	}

	// Add any remaining segments.
	if (Operation::kShouldAddRemainingSegmentsFromSpan1 && s1 != segments1_end)
	segments.AppendRange(s1, segments1_end);
	else if (Operation::kShouldAddRemainingSegmentsFromSpan2 &&
	s2 != segments2_end)
	segments.AppendRange(s2, segments2_end);

	// Add the span.
	if (!segments.IsEmpty() \|\| !result.IsEmpty())
	result.AppendSpan(y, segments.data(), segments.data() + segments.size());
	}

	// Add any remaining spans.
	if (Operation::kShouldAddRemainingSpansFromShape1 && spans1 != spans1_end)
	result.AppendSpans(shape1, spans1, spans1_end);
	else if (Operation::kShouldAddRemainingSpansFromShape2 &&
	spans2 != spans2_end)
	result.AppendSpans(shape2, spans2, spans2_end);

	result.TrimCapacities();

	return result;
	}

	struct Region::Shape::UnionOperation {
	STATIC_ONLY(UnionOperation);
	static bool TrySimpleOperation(const Shape& shape1,
	const Shape& shape2,
	Shape& result) {
	if (shape1.IsEmpty()) {
	result = shape2;
	return true;
	}

	return false;
	}

	static const int kOpCode = 0;

	static const bool kShouldAddRemainingSegmentsFromSpan1 = true;
	static const bool kShouldAddRemainingSegmentsFromSpan2 = true;
	static const bool kShouldAddRemainingSpansFromShape1 = true;
	static const bool kShouldAddRemainingSpansFromShape2 = true;
	};

	Region::Shape Region::Shape::UnionShapes(const Shape& shape1,
	const Shape& shape2) {
	return ShapeOperation<UnionOperation>(shape1, shape2);
	}

	struct Region::Shape::IntersectOperation {
	STATIC_ONLY(IntersectOperation);
	static bool TrySimpleOperation(const Shape&, const Shape&, Shape&) {
	return false;
	}

	static const int kOpCode = 3;

	static const bool kShouldAddRemainingSegmentsFromSpan1 = false;
	static const bool kShouldAddRemainingSegmentsFromSpan2 = false;
	static const bool kShouldAddRemainingSpansFromShape1 = false;
	static const bool kShouldAddRemainingSpansFromShape2 = false;
	};

	Region::Shape Region::Shape::IntersectShapes(const Shape& shape1,
	const Shape& shape2) {
	return ShapeOperation<IntersectOperation>(shape1, shape2);
	}

	struct Region::Shape::SubtractOperation {
	STATIC_ONLY(SubtractOperation);
	static bool TrySimpleOperation(const Shape&, const Shape&, Region::Shape&) {
	return false;
	}

	static const int kOpCode = 1;

	static const bool kShouldAddRemainingSegmentsFromSpan1 = true;
	static const bool kShouldAddRemainingSegmentsFromSpan2 = false;
	static const bool kShouldAddRemainingSpansFromShape1 = true;
	static const bool kShouldAddRemainingSpansFromShape2 = false;
	};

	Region::Shape Region::Shape::SubtractShapes(const Shape& shape1,
	const Shape& shape2) {
	return ShapeOperation<SubtractOperation>(shape1, shape2);
	}

	#ifndef NDEBUG
	void Region::Dump() const {
	printf("Bounds: (%d, %d, %d, %d)\n", bounds_.X(), bounds_.Y(),
	bounds_.Width(), bounds_.Height());
	shape_.Dump();
	}
	#endif

	void Region::Intersect(const Region& region) {
	if (bounds_.IsEmpty())
	return;
	if (!bounds_.Intersects(region.bounds_)) {
	shape_ = Shape();
	bounds_ = IntRect();
	return;
	}

	Shape intersected_shape = Shape::IntersectShapes(shape_, region.shape_);

	shape_.Swap(intersected_shape);
	bounds_ = shape_.Bounds();
	}

	void Region::Unite(const Region& region) {
	if (region.IsEmpty())
	return;
	if (IsRect() && bounds_.Contains(region.bounds_))
	return;
	if (region.IsRect() && region.bounds_.Contains(bounds_)) {
	shape_ = region.shape_;
	bounds_ = region.bounds_;
	return;
	}
	// FIXME: We may want another way to construct a Region without doing this
	// test when we expect it to be false.
	if (!IsRect() && Contains(region))
	return;

	Shape united_shape = Shape::UnionShapes(shape_, region.shape_);

	shape_.Swap(united_shape);
	bounds_.Unite(region.bounds_);
	}

	void Region::Subtract(const Region& region) {
	if (bounds_.IsEmpty())
	return;
	if (region.IsEmpty())
	return;
	if (!bounds_.Intersects(region.bounds_))
	return;

	Shape subtracted_shape = Shape::SubtractShapes(shape_, region.shape_);

	shape_.Swap(subtracted_shape);
	bounds_ = shape_.Bounds();
	}

	void Region::Translate(const IntSize& offset) {
	bounds_.Move(offset);
	shape_.Translate(offset);
	}

	} // namespace blink