dl_region2.cc

class DlRegion2 {
 public:
  void addRects(std::vector<SkIRect>&& rects);
  std::vector<SkIRect> getRects(bool deband = true) const;

 private:
  struct Span {
    int32_t left;
    int32_t right;
  };
  struct SpanLine {
    int32_t top;
    int32_t bottom;
    std::vector<Span> spans;

    void insertSpan(int32_t left, int32_t right);
  };

  std::vector<SpanLine> lines_;
};

void DlRegion2::SpanLine::insertSpan(int32_t left, int32_t right) {
  auto size = spans.size();
  for (size_t i = 0; i < size; ++i) {
    Span& span = spans[i];
    if (right < span.left) {
      spans.insert(spans.begin() + i, {left, right});
      return;
    }
    if (left > span.right) {
      continue;
    }
    size_t last_index = i;
    while (last_index + 1 < size && right >= spans[last_index + 1].left) {
      ++last_index;
    }
    span.left = std::min(span.left, left);
    span.right = std::max(spans[last_index].right, right);
    if (last_index > i) {
      spans.erase(spans.begin() + i + 1, spans.begin() + last_index + 1);
    }
    return;
  }

  spans.push_back({left, right});
}

void DlRegion2::addRects(std::vector<SkIRect>&& rects) {
  std::sort(rects.begin(), rects.end(), [](const SkIRect& a, const SkIRect& b) {
    if (a.top() == b.top()) {
      return a.left() < b.left();
    } else {
      return a.top() < b.top();
    }
  });

  size_t span_start = 0;
  while (span_start < rects.size()) {
    size_t span_end = span_start;
    int32_t span_top = rects[span_start].fTop;
    int32_t span_bottom = rects[span_start].fBottom;
    while (true) {
      ++span_end;
      if (span_end == rects.size()) {
        break;
      }
      if (rects[span_end].fTop != span_top) {
        span_bottom = std::min(span_bottom, rects[span_end].fTop);
        break;
      }
      span_bottom = std::min(span_bottom, rects[span_end].fBottom);
    }
    SpanLine line;
    line.top = span_top;
    line.bottom = span_bottom;

    for (size_t i = span_start; i < span_end; ++i) {
      line.insertSpan(rects[i].fLeft, rects[i].fRight);
      rects[i].fTop = span_bottom;
      if (rects[i].fBottom == span_bottom) {
        if (i > span_start) {
          std::memmove(&rects[span_start + 1], &rects[span_start],
                       (i - span_start) * sizeof(SkIRect));
        }
        ++span_start;
      }
    }

    if (!lines_.empty() && lines_.back().bottom == line.top &&
        lines_.back().spans.size() == line.spans.size() &&
        memcmp(lines_.back().spans.data(), line.spans.data(),
               line.spans.size() * sizeof(Span)) == 0) {
      lines_.back().bottom = line.bottom;
    } else {
      lines_.push_back(std::move(line));
    }
  }
}

std::vector<SkIRect> DlRegion2::getRects(bool deband) const {
  std::vector<SkIRect> rects;
  size_t previous_span_end = 0;
  for (const auto& line : lines_) {
    for (const Span& span : line.spans) {
      SkIRect rect{span.left, line.top, span.right, line.bottom};
      if (deband) {
        auto iter = rects.begin() + previous_span_end;
        // If there is rectangle previously in rects on which this one is a
        // vertical continuation, remove the previous rectangle and expand
        // this one vertically to cover the area.
        while (iter != rects.begin()) {
          --iter;
          if (iter->bottom() < rect.top()) {
            // Went all the way to previous span line.
            break;
          } else if (iter->bottom() == rect.top() &&
                     iter->left() == rect.left() &&
                     iter->right() == rect.right()) {
            rect.fTop = iter->fTop;
            rects.erase(iter);
            break;
          }
        }
      }
      rects.push_back(rect);
    }
    previous_span_end = rects.size();
  }
  return rects;
}

std::vector<SkIRect> DlRegionSorted::getRects(bool deband) const {
  std::vector<SkIRect> rects;
  size_t previous_span_end = 0;
  for (const auto& line : lines_) {
    for (const Span& span : *line.spans) {
      SkIRect rect{span.left, line.top, span.right, line.bottom};
      if (deband) {
        auto iter = rects.begin() + previous_span_end;
        // If there is rectangle previously in rects on which this one is a
        // vertical continuation, remove the previous rectangle and expand
        // this one vertically to cover the area.
        while (iter != rects.begin()) {
          --iter;
          if (iter->bottom() < rect.top()) {
            // Went all the way to previous span line.
            break;
          } else if (iter->bottom() == rect.top() &&
                     iter->left() == rect.left() &&
                     iter->right() == rect.right()) {
            rect.fTop = iter->fTop;
            rects.erase(iter);
            break;
          }
        }
      }
      rects.push_back(rect);
    }
    previous_span_end = rects.size();
  }
  return rects;
}