[Bf-blender-cvs] [34294449059] master: BLI: add index mask utilities
Jacques Lucke
noreply at git.blender.org
Wed Feb 23 11:18:40 CET 2022
Commit: 34294449059744ba4b3d4b16eb5fb14a48c16265
Author: Jacques Lucke
Date: Wed Feb 23 11:13:54 2022 +0100
Branches: master
https://developer.blender.org/rB34294449059744ba4b3d4b16eb5fb14a48c16265
BLI: add index mask utilities
Sometimes it is useful to get the index ranges that are in an index mask.
That is because some algorithms can process index ranges more efficiently
than generic index masks.
Extracting ranges from an index mask is relatively efficient, because it is
cheap to check if a span of indices contains a contiguous range.
===================================================================
M source/blender/blenlib/BLI_index_mask.hh
M source/blender/blenlib/intern/index_mask.cc
M source/blender/blenlib/tests/BLI_index_mask_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_index_mask.hh b/source/blender/blenlib/BLI_index_mask.hh
index 7f4e7be543b..3decd8b9441 100644
--- a/source/blender/blenlib/BLI_index_mask.hh
+++ b/source/blender/blenlib/BLI_index_mask.hh
@@ -209,6 +209,18 @@ class IndexMask {
return indices_.is_empty();
}
+ bool contained_in(const IndexRange range) const
+ {
+ if (indices_.is_empty()) {
+ return true;
+ }
+ if (range.size() < indices_.size()) {
+ return false;
+ }
+ return indices_.first() >= range.first() && indices_.last() <= range.last();
+ }
+
+ IndexMask slice(int64_t start, int64_t size) const;
IndexMask slice(IndexRange slice) const;
/**
* Create a sub-mask that is also shifted to the beginning.
@@ -229,6 +241,30 @@ class IndexMask {
* so that the first index in the output is zero.
*/
IndexMask slice_and_offset(IndexRange slice, Vector<int64_t> &r_new_indices) const;
+
+ /**
+ * Get a new mask that contains all the indices that are not in the current mask.
+ * If necessary, the indices referenced by the new mask are inserted in #r_new_indices.
+ */
+ IndexMask invert(const IndexRange full_range, Vector<int64_t> &r_new_indices) const;
+
+ /**
+ * Get all contiguous index ranges within the mask.
+ */
+ Vector<IndexRange> extract_ranges() const;
+
+ /**
+ * Similar to #extract ranges, but works on the inverted mask. So the returned ranges are
+ * in-between the indices in the mask.
+ *
+ * Using this method is generally more efficient than first inverting the index mask and then
+ * extracting the ranges.
+ *
+ * If #r_skip_amounts is passed in, it will contain the number of indices that have been skipped
+ * before each range in the return value starts.
+ */
+ Vector<IndexRange> extract_ranges_invert(const IndexRange full_range,
+ Vector<int64_t> *r_skip_amounts) const;
};
} // namespace blender
diff --git a/source/blender/blenlib/intern/index_mask.cc b/source/blender/blenlib/intern/index_mask.cc
index b55de6a9264..8c03df2d4c3 100644
--- a/source/blender/blenlib/intern/index_mask.cc
+++ b/source/blender/blenlib/intern/index_mask.cc
@@ -4,6 +4,11 @@
namespace blender {
+IndexMask IndexMask::slice(int64_t start, int64_t size) const
+{
+ return this->slice(IndexRange(start, size));
+}
+
IndexMask IndexMask::slice(IndexRange slice) const
{
return IndexMask(indices_.slice(slice));
@@ -30,4 +35,94 @@ IndexMask IndexMask::slice_and_offset(const IndexRange slice, Vector<int64_t> &r
return IndexMask(r_new_indices.as_span());
}
+IndexMask IndexMask::invert(const IndexRange full_range, Vector<int64_t> &r_new_indices) const
+{
+ BLI_assert(this->contained_in(full_range));
+ if (full_range.size() == indices_.size()) {
+ return {};
+ }
+ if (indices_.is_empty()) {
+ return full_range;
+ }
+ r_new_indices.clear();
+
+ const Vector<IndexRange> ranges = this->extract_ranges_invert(full_range, nullptr);
+ for (const IndexRange &range : ranges) {
+ for (const int64_t index : range) {
+ r_new_indices.append(index);
+ }
+ }
+ return r_new_indices.as_span();
+}
+
+Vector<IndexRange> IndexMask::extract_ranges() const
+{
+ Vector<IndexRange> ranges;
+ int64_t range_start = 0;
+ while (range_start < indices_.size()) {
+ int64_t current_range_end = range_start + 1;
+ int64_t step_size = 1;
+
+ while (true) {
+ const int64_t possible_range_end = current_range_end + step_size;
+ if (possible_range_end > indices_.size()) {
+ break;
+ }
+ if (!this->slice(range_start, possible_range_end - range_start).is_range()) {
+ break;
+ }
+ current_range_end = possible_range_end;
+ step_size *= 2;
+ }
+
+ /* This step size was tried already, no need to try it again. */
+ step_size /= 2;
+
+ while (step_size > 0) {
+ const int64_t possible_range_end = current_range_end + step_size;
+ step_size /= 2;
+ if (possible_range_end > indices_.size()) {
+ continue;
+ }
+ if (!this->slice(range_start, possible_range_end - range_start).is_range()) {
+ continue;
+ }
+ current_range_end = possible_range_end;
+ }
+
+ ranges.append(IndexRange{indices_[range_start], current_range_end - range_start});
+ range_start = current_range_end;
+ }
+ return ranges;
+}
+
+Vector<IndexRange> IndexMask::extract_ranges_invert(const IndexRange full_range,
+ Vector<int64_t> *r_skip_amounts) const
+{
+ BLI_assert(this->contained_in(full_range));
+ const Vector<IndexRange> ranges = this->extract_ranges();
+ Vector<IndexRange> inverted_ranges;
+
+ int64_t skip_amount = 0;
+ int64_t next_start = full_range.start();
+ for (const int64_t i : ranges.index_range()) {
+ const IndexRange range = ranges[i];
+ if (range.start() > next_start) {
+ inverted_ranges.append({next_start, range.start() - next_start});
+ if (r_skip_amounts != nullptr) {
+ r_skip_amounts->append(skip_amount);
+ }
+ }
+ next_start = range.one_after_last();
+ skip_amount += range.size();
+ }
+ if (next_start < full_range.one_after_last()) {
+ inverted_ranges.append({next_start, full_range.one_after_last() - next_start});
+ if (r_skip_amounts != nullptr) {
+ r_skip_amounts->append(skip_amount);
+ }
+ }
+ return inverted_ranges;
+}
+
} // namespace blender
diff --git a/source/blender/blenlib/tests/BLI_index_mask_test.cc b/source/blender/blenlib/tests/BLI_index_mask_test.cc
index 179c1c58cc4..86ae31cedcc 100644
--- a/source/blender/blenlib/tests/BLI_index_mask_test.cc
+++ b/source/blender/blenlib/tests/BLI_index_mask_test.cc
@@ -64,4 +64,153 @@ TEST(index_mask, SliceAndOffset)
}
}
+TEST(index_mask, ExtractRanges)
+{
+ {
+ Vector<int64_t> indices = {1, 2, 3, 5, 7, 8};
+ Vector<IndexRange> ranges = IndexMask(indices).extract_ranges();
+ EXPECT_EQ(ranges.size(), 3);
+ EXPECT_EQ(ranges[0], IndexRange(1, 3));
+ EXPECT_EQ(ranges[1], IndexRange(5, 1));
+ EXPECT_EQ(ranges[2], IndexRange(7, 2));
+ }
+ {
+ Vector<int64_t> indices;
+ Vector<IndexRange> ranges = IndexMask(indices).extract_ranges();
+ EXPECT_EQ(ranges.size(), 0);
+ }
+ {
+ Vector<int64_t> indices = {5, 6, 7, 8, 9, 10};
+ Vector<IndexRange> ranges = IndexMask(indices).extract_ranges();
+ EXPECT_EQ(ranges.size(), 1);
+ EXPECT_EQ(ranges[0], IndexRange(5, 6));
+ }
+ {
+ Vector<int64_t> indices = {1, 3, 6, 8};
+ Vector<IndexRange> ranges = IndexMask(indices).extract_ranges();
+ EXPECT_EQ(ranges.size(), 4);
+ EXPECT_EQ(ranges[0], IndexRange(1, 1));
+ EXPECT_EQ(ranges[1], IndexRange(3, 1));
+ EXPECT_EQ(ranges[2], IndexRange(6, 1));
+ EXPECT_EQ(ranges[3], IndexRange(8, 1));
+ }
+ {
+ Vector<int64_t> indices;
+ IndexRange range1{4, 10};
+ IndexRange range2{20, 30};
+ IndexRange range3{100, 1};
+ IndexRange range4{150, 100};
+ for (const IndexRange &range : {range1, range2, range3, range4}) {
+ for (const int64_t i : range) {
+ indices.append(i);
+ }
+ }
+ Vector<IndexRange> ranges = IndexMask(indices).extract_ranges();
+ EXPECT_EQ(ranges.size(), 4);
+ EXPECT_EQ(ranges[0], range1);
+ EXPECT_EQ(ranges[1], range2);
+ EXPECT_EQ(ranges[2], range3);
+ EXPECT_EQ(ranges[3], range4);
+ }
+ {
+ const int64_t max_test_range_size = 50;
+ Vector<int64_t> indices;
+ int64_t offset = 0;
+ for (const int64_t range_size : IndexRange(1, max_test_range_size)) {
+ for (const int i : IndexRange(range_size)) {
+ indices.append(offset + i);
+ }
+ offset += range_size + 1;
+ }
+ Vector<IndexRange> ranges = IndexMask(indices).extract_ranges();
+ EXPECT_EQ(ranges.size(), max_test_range_size);
+ for (const int64_t range_size : IndexRange(1, max_test_range_size)) {
+ const IndexRange range = ranges[range_size - 1];
+ EXPECT_EQ(range.size(), range_size);
+ }
+ }
+}
+
+TEST(index_mask, Invert)
+{
+ {
+ Vector<int64_t> indices;
+ Vector<int64_t> new_indices;
+ IndexMask inverted_mask = IndexMask(indices).invert(IndexRange(10), new_indices);
+ EXPECT_EQ(inverted_mask.size(), 10);
+ EXPECT_TRUE(new_indices.is_empty());
+ }
+ {
+ Vector<int64_t> indices = {3, 4, 5, 6};
+ Vector<int64_t> new_indices;
+ IndexMask inverted_mask = IndexMask(indices).invert(IndexRange(3, 4), new_indices);
+ EXPECT_TRUE(inverted_mask.is_empty());
+ }
+ {
+ Vector<int64_t> indices = {5};
+ Vector<int64_t> new_indices;
+ IndexMask inverted_mask = IndexMask(indices).invert(IndexRange(10), new_indices);
+ EXPECT_EQ(inverted_mask.size(), 9);
+ EXPECT_EQ(inverted_mask.indices(), Span<int64_t>({0, 1, 2, 3, 4, 6, 7, 8, 9}));
+ }
+ {
+ Vector<int64_t> indices = {0, 1, 2, 6, 7, 9};
+ Vector<int64_t> new_indices;
+ IndexMask inverted_mask = IndexMask(indices).invert(IndexRange(10), new_indices);
+ EXPECT_EQ(inverted_mask.size(), 4);
+ EXPECT_EQ(inverted_mask.indices(), Span<int64_t>({3, 4, 5, 8}));
+ }
+}
+
+TEST(index_mask, ExtractRangesInvert)
+{
+ {
+ Vector<int64_t> indices;
+ Vector<IndexRange> ranges = IndexMask(indices).extract_ranges_invert(IndexRange(10), nullptr);
+ EXPECT_EQ(ranges.size(), 1);
+ EXPECT_EQ(ranges[0], IndexRange(10));
+ }
+ {
+ Vector<int64_t> indices = {1, 2, 3, 6, 7};
+ Vector<int64_t> skip_amounts;
+ Vector<IndexRange> ranges = IndexMask(indices).extract_ranges_invert(IndexRange(10),
+ &skip_amounts);
+ EXPECT_EQ(ranges.size(), 3);
+ EXPECT_EQ(ranges[0], IndexRange(0, 1));
+ EXPECT_EQ(ranges[1], IndexRange(4, 2));
+ EXPECT_EQ(ranges[2], IndexRange(8, 2));
+ EXPECT_EQ(skip_amounts[0], 0);
+ EXPECT_EQ(skip_amounts[1], 3);
+ EXPECT_EQ(skip_amounts[2], 5);
+ }
+ {
+ Vector<int64_t> indices = {0, 1, 2, 3, 4};
+ Vector<int64_t> skip_amounts;
+ Vector<IndexRange> ranges = IndexMask(indices).extract_ranges_invert(IndexRange(5),
+ &skip_amounts);
+ EXPECT_TRUE(ranges.is_empty());
+ EXPEC
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list