From f90bd4b957938c1ce050b3f5783ead37b297ddc2 Mon Sep 17 00:00:00 2001 From: xie xingguo Date: Thu, 21 Sep 2017 13:40:40 +0800 Subject: [PATCH] common/interval_set: override subset_of for given range E.g.: subset_of([5~10,20~5], 0, 100) -> [5~10,20~5] subset_of([5~10,20~5], 5, 25) -> [5~10,20~5] subset_of([5~10,20~5], 1, 10) -> [5~5] subset_of([5~10,20~5], 8, 24) -> [8~7, 20~4] Signed-off-by: xie xingguo --- src/include/btree_interval_set.h | 42 ++++++++++++++++++++++++ src/include/interval_set.h | 42 ++++++++++++++++++++++++ src/test/common/test_interval_set.cc | 49 +++++++++++++++++++++++++++- 3 files changed, 132 insertions(+), 1 deletion(-) diff --git a/src/include/btree_interval_set.h b/src/include/btree_interval_set.h index 828fead2ae0b9..c0c35e1a28110 100644 --- a/src/include/btree_interval_set.h +++ b/src/include/btree_interval_set.h @@ -514,6 +514,48 @@ class btree_interval_set { return true; } + /* + * build a subset of @other for given range [@start, @end) + * E.g.: + * subset_of([5~10,20~5], 0, 100) -> [5~10,20~5] + * subset_of([5~10,20~5], 5, 25) -> [5~10,20~5] + * subset_of([5~10,20~5], 1, 10) -> [5~5] + * subset_of([5~10,20~5], 8, 24) -> [8~7, 20~4] + */ + void subset_of(const btree_interval_set &other, T start, T end) { + assert(end >= start); + clear(); + if (end == start) { + return; + } + typename map_t::const_iterator p = other.find_inc(start); + if (p == other.m.end()) + return; + if (p->first < start) { + if (p->first + p->second >= end) { + insert(start, end - start); + return; + } else { + insert(start, p->first + p->second - start); + ++p; + } + } + while (p != other.m.end()) { + assert(p->first >= start); + if (p->first >= end) { + return; + } + if (p->first + p->second >= end) { + insert(p->first, end - p->first); + return; + } else { + // whole + insert(p->first, p->second); + ++p; + } + } + } + /* * build a subset of @other, starting at or after @start, and including * @len worth of values, skipping holes. e.g., diff --git a/src/include/interval_set.h b/src/include/interval_set.h index 67b7ac2e53e3b..ee6da3a87dd92 100644 --- a/src/include/interval_set.h +++ b/src/include/interval_set.h @@ -660,6 +660,48 @@ class interval_set { return true; } + /* + * build a subset of @other for given rage [@start, @end) + * E.g.: + * subset_of([5~10,20~5], 0, 100) -> [5~10,20~5] + * subset_of([5~10,20~5], 5, 25) -> [5~10,20~5] + * subset_of([5~10,20~5], 1, 10) -> [5~5] + * subset_of([5~10,20~5], 8, 24) -> [8~7, 20~4] + */ + void subset_of(const interval_set &other, T start, T end) { + assert(end >= start); + clear(); + if (end == start) { + return; + } + typename std::map::const_iterator p = other.find_inc(start); + if (p == other.m.end()) + return; + if (p->first < start) { + if (p->first + p->second >= end) { + insert(start, end - start); + return; + } else { + insert(start, p->first + p->second - start); + ++p; + } + } + while (p != other.m.end()) { + assert(p->first >= start); + if (p->first >= end) { + return; + } + if (p->first + p->second >= end) { + insert(p->first, end - p->first); + return; + } else { + // whole + insert(p->first, p->second); + ++p; + } + } + } + /* * build a subset of @other, starting at or after @start, and including * @len worth of values, skipping holes. e.g., diff --git a/src/test/common/test_interval_set.cc b/src/test/common/test_interval_set.cc index f44f35e316fa2..ca723125610df 100644 --- a/src/test/common/test_interval_set.cc +++ b/src/test/common/test_interval_set.cc @@ -557,6 +557,53 @@ TYPED_TEST(IntervalSetTest, subset_of) { iset1.insert( 50, 5); iset2.insert( 55, 2); ASSERT_FALSE(iset1.subset_of(iset2)); + + ISet iset3, iset4, expected; + iset3.insert(5, 10); + iset3.insert(20, 5); + + iset4.subset_of(iset3, 0, 100); + expected.insert(5, 10); + expected.insert(20, 5); + ASSERT_TRUE(iset4 == expected); + + iset4.clear(); + iset4.subset_of(iset3, 5, 25); + ASSERT_TRUE(iset4 == expected); + + iset4.clear(); + iset4.subset_of(iset3, 1, 10); + expected.clear(); + expected.insert(5, 5); + ASSERT_TRUE(iset4 == expected); + + iset4.clear(); + iset4.subset_of(iset3, 8, 24); + expected.clear(); + expected.insert(8, 7); + expected.insert(20, 4); + ASSERT_TRUE(iset4 == expected); + + iset4.clear(); + iset4.subset_of(iset3, 0, 0); + expected.clear(); + ASSERT_TRUE(iset4 == expected); + + iset4.clear(); + iset4.subset_of(iset3, 0, 1); + ASSERT_TRUE(iset4 == expected); + + iset4.clear(); + iset4.subset_of(iset3, 0, 5); + ASSERT_TRUE(iset4 == expected); + + iset4.clear(); + iset4.subset_of(iset3, 25, 30); + ASSERT_TRUE(iset4 == expected); + + iset4.clear(); + iset4.subset_of(iset3, 26, 40); + ASSERT_TRUE(iset4 == expected); } TYPED_TEST(IntervalSetTest, span_of) { @@ -592,4 +639,4 @@ TYPED_TEST(IntervalSetTest, span_of) { iset1.span_of( iset2, 100, 5 ); ASSERT_EQ( iset1.num_intervals(), 0); ASSERT_EQ( iset1.size(), 0); -} \ No newline at end of file +} -- 2.39.5