pw_containers: FilteredView class
- The FilteredView class applies a filter to a container, allowing
iteration over only matching elements.
- Prevent copying an IntrusiveList::Item, since this would break the
intrusive list the item is in.
Change-Id: Ifefb95c421e057e746440532f0af6505fb2dc32d
Reviewed-on: https://pigweed-review.googlesource.com/c/pigweed/pigweed/+/64960
Commit-Queue: Wyatt Hepler <hepler@google.com>
Pigweed-Auto-Submit: Wyatt Hepler <hepler@google.com>
Reviewed-by: Keir Mierle <keir@google.com>
diff --git a/pw_containers/BUILD.bazel b/pw_containers/BUILD.bazel
index c3e9000..92c1f3f 100644
--- a/pw_containers/BUILD.bazel
+++ b/pw_containers/BUILD.bazel
@@ -53,6 +53,12 @@
)
pw_cc_library(
+ name = "filtered_view",
+ hdrs = ["public/pw_containers/filtered_view.h"],
+ includes = ["public"],
+)
+
+pw_cc_library(
name = "flat_map",
hdrs = [
"public/pw_containers/flat_map.h",
@@ -61,6 +67,15 @@
)
pw_cc_test(
+ name = "filtered_view_test",
+ srcs = ["filtered_view_test.cc"],
+ deps = [
+ ":filtered_view",
+ ":intrusive_list",
+ ],
+)
+
+pw_cc_test(
name = "flat_map_test",
srcs = [
"flat_map_test.cc",
diff --git a/pw_containers/BUILD.gn b/pw_containers/BUILD.gn
index d59ba21..82f482d 100644
--- a/pw_containers/BUILD.gn
+++ b/pw_containers/BUILD.gn
@@ -18,7 +18,7 @@
import("$dir_pw_docgen/docs.gni")
import("$dir_pw_unit_test/test.gni")
-config("default_config") {
+config("public_include_path") {
include_dirs = [ "public" ]
}
@@ -30,19 +30,24 @@
]
}
+pw_source_set("filtered_view") {
+ public_configs = [ ":public_include_path" ]
+ public = [ "public/pw_containers/filtered_view.h" ]
+}
+
pw_source_set("flat_map") {
- public_configs = [ ":default_config" ]
+ public_configs = [ ":public_include_path" ]
public = [ "public/pw_containers/flat_map.h" ]
}
pw_source_set("vector") {
- public_configs = [ ":default_config" ]
+ public_configs = [ ":public_include_path" ]
public_deps = [ dir_pw_assert ]
public = [ "public/pw_containers/vector.h" ]
}
pw_source_set("intrusive_list") {
- public_configs = [ ":default_config" ]
+ public_configs = [ ":public_include_path" ]
public = [
"public/pw_containers/internal/intrusive_list_impl.h",
"public/pw_containers/intrusive_list.h",
@@ -53,12 +58,21 @@
pw_test_group("tests") {
tests = [
+ ":filtered_view_test",
":flat_map_test",
":intrusive_list_test",
":vector_test",
]
}
+pw_test("filtered_view_test") {
+ sources = [ "filtered_view_test.cc" ]
+ deps = [
+ ":filtered_view",
+ ":intrusive_list",
+ ]
+}
+
pw_test("flat_map_test") {
sources = [ "flat_map_test.cc" ]
deps = [ ":flat_map" ]
diff --git a/pw_containers/docs.rst b/pw_containers/docs.rst
index 51b224b..be63a98 100644
--- a/pw_containers/docs.rst
+++ b/pw_containers/docs.rst
@@ -90,9 +90,26 @@
need to be sorted. During construction, ``pw::containers::FlatMap`` will
perform a constexpr insertion sort.
+pw::containers::FilteredView
+============================
+``pw::containers::FilteredView`` provides a view of a container that only
+contains elements that match the specified filter. This class is similar to
+C++20's `std::ranges::filter_view
+<https://en.cppreference.com/w/cpp/ranges/filter_view>`_.
+
+To create a ``FilteredView``, pass a container and a filter object, which may be
+a lambda or class that implements ``operator()`` for the container's value type.
+
+.. code-block:: cpp
+
+ std::array<int, 99> kNumbers = {3, 1, 4, 1, ...};
+
+ for (int even : FilteredView(kNumbers, [](int n) { return n % 2 == 0; })) {
+ PW_LOG_INFO("This number is even: %d", even);
+ }
+
Compatibility
=============
-* C
* C++17
Dependencies
diff --git a/pw_containers/filtered_view_test.cc b/pw_containers/filtered_view_test.cc
new file mode 100644
index 0000000..1583981
--- /dev/null
+++ b/pw_containers/filtered_view_test.cc
@@ -0,0 +1,176 @@
+// Copyright 2021 The Pigweed Authors
+//
+// 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
+//
+// https://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.
+
+#include "pw_containers/filtered_view.h"
+
+#include <array>
+#include <span>
+
+#include "gtest/gtest.h"
+#include "pw_containers/intrusive_list.h"
+
+namespace pw::containers {
+namespace {
+
+struct Item : IntrusiveList<Item>::Item {
+ constexpr Item(int x) : value(x) {}
+
+ int value;
+};
+
+constexpr std::array<int, 6> kArray{0, 1, 2, 3, 4, 5};
+
+TEST(FilteredView, Array_MatchSubset) {
+ FilteredView view(kArray, [](int x) { return x == 3 || x == 5; });
+
+ auto it = view.begin();
+ ASSERT_EQ(*it, 3);
+ ++it;
+ ASSERT_EQ(*it, 5);
+ ++it;
+ EXPECT_EQ(it, view.end());
+}
+
+TEST(FilteredView, Array_MatchAll) {
+ FilteredView view(kArray, [](int) { return true; });
+
+ std::array<bool, 6> found = {};
+ for (int value : view) {
+ found[value] = true;
+ }
+ EXPECT_TRUE(
+ std::all_of(found.begin(), found.end(), [](bool b) { return b; }));
+}
+
+TEST(FilteredView, Array_MatchNone) {
+ for (int unused : FilteredView(kArray, [](int) { return false; })) {
+ static_cast<void>(unused);
+ FAIL();
+ }
+}
+
+TEST(FilteredView, EmptyContainer) {
+ constexpr std::array<int, 0> nothing{};
+ for (int unused : FilteredView(nothing, [](int) { return true; })) {
+ static_cast<void>(unused);
+ FAIL();
+ }
+
+ IntrusiveList<Item> intrusive_list;
+ for (const Item& unused :
+ FilteredView(nothing, [](const Item&) { return true; })) {
+ static_cast<void>(unused);
+ FAIL();
+ }
+}
+
+TEST(FilteredView, IntrusiveList_MatchSubset) {
+ Item item_1{1};
+ Item item_2{2};
+ Item item_3{3};
+ IntrusiveList<Item> intrusive_list({&item_1, &item_2, &item_3});
+
+ FilteredView view(intrusive_list,
+ [](const Item& i) { return i.value % 2 != 0; });
+
+ auto it = view.begin();
+ ASSERT_EQ(it->value, 1);
+ ++it;
+ ASSERT_EQ((*it).value, 3);
+ ++it;
+ EXPECT_EQ(it, view.end());
+}
+
+TEST(FilteredView, IntrusiveList_MatchAll) {
+ Item item_1{0};
+ Item item_2{1};
+ Item item_3{2};
+ IntrusiveList<Item> intrusive_list({&item_1, &item_2, &item_3});
+
+ std::array<bool, 3> found = {};
+
+ for (const Item& item :
+ FilteredView(intrusive_list, [](const Item&) { return true; })) {
+ found[item.value] = true;
+ }
+ EXPECT_TRUE(
+ std::all_of(found.begin(), found.end(), [](bool b) { return b; }));
+}
+
+TEST(FilteredView, IntrusiveList_MatchNone) {
+ Item item_1{0};
+ Item item_2{1};
+ Item item_3{2};
+ IntrusiveList<Item> intrusive_list({&item_1, &item_2, &item_3});
+
+ for (const Item& unused :
+ FilteredView(kArray, [](const Item&) { return false; })) {
+ static_cast<void>(unused);
+ FAIL();
+ }
+}
+
+TEST(FilteredView, Front_OneElement) {
+ EXPECT_EQ(FilteredView(kArray, [](int x) { return x == 0; }).front(), 0);
+}
+
+TEST(FilteredView, Back_OneElement) {
+ EXPECT_EQ(FilteredView(kArray, [](int x) { return x == 0; }).back(), 0);
+}
+
+TEST(FilteredView, Front_MultipleElements) {
+ EXPECT_EQ(
+ FilteredView(kArray, [](int x) { return x == 3 || x == 5; }).front(), 3);
+}
+
+TEST(FilteredView, Back_MultipleElements) {
+ EXPECT_EQ(FilteredView(kArray, [](int x) { return x == 3 || x == 5; }).back(),
+ 5);
+}
+
+TEST(FilteredView, Size_Empty) {
+ EXPECT_EQ(FilteredView(kArray, [](int x) { return x < 0; }).size(), 0u);
+
+ EXPECT_TRUE(FilteredView(kArray, [](int x) { return x < 0; }).empty());
+
+ constexpr std::array<int, 0> empty{};
+ FilteredView empty_view(empty, [](const Item&) { return true; });
+ EXPECT_EQ(empty_view.size(), 0u);
+ EXPECT_TRUE(empty_view.empty());
+}
+
+TEST(FilteredView, Size_OneElement) {
+ EXPECT_EQ(FilteredView(kArray, [](int x) { return x == 0; }).size(), 1u);
+ EXPECT_EQ(FilteredView(kArray, [](int x) { return x == 3; }).size(), 1u);
+ EXPECT_EQ(FilteredView(kArray, [](int x) { return x == 5; }).size(), 1u);
+
+ EXPECT_FALSE(FilteredView(kArray, [](int x) { return x == 5; }).empty());
+}
+
+TEST(FilteredView, Size_MultipleElements) {
+ EXPECT_EQ(FilteredView(kArray, [](int x) { return x <= 1; }).size(), 2u);
+ EXPECT_EQ(FilteredView(kArray, [](int x) { return x > 1; }).size(), 4u);
+ EXPECT_EQ(FilteredView(kArray, [](int x) { return x < 5; }).size(), 5u);
+
+ EXPECT_FALSE(FilteredView(kArray, [](int x) { return x < 5; }).empty());
+}
+
+TEST(FilteredView, Size_AllElements) {
+ EXPECT_EQ(FilteredView(kArray, [](int) { return true; }).size(), 6u);
+
+ EXPECT_FALSE(FilteredView(kArray, [](int x) { return x < 5; }).empty());
+}
+
+} // namespace
+} // namespace pw::containers
diff --git a/pw_containers/public/pw_containers/filtered_view.h b/pw_containers/public/pw_containers/filtered_view.h
new file mode 100644
index 0000000..7daf821
--- /dev/null
+++ b/pw_containers/public/pw_containers/filtered_view.h
@@ -0,0 +1,165 @@
+// Copyright 2021 The Pigweed Authors
+//
+// 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
+//
+// https://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.
+#pragma once
+
+#include <cstddef>
+#include <iterator>
+
+#include "pw_assert/assert.h"
+
+namespace pw::containers {
+
+// FilteredView supports iterating over only elements that match a filter in a
+// container. FilteredView works with any container with an incrementable
+// iterator. The back() function currently requires a bidirectional iterator.
+//
+// FilteredView is similar to C++20's std::filter_view.
+template <typename Container, typename Filter>
+class FilteredView {
+ public:
+ // Iterator that only moves to elements that match the provided filter.
+ class iterator {
+ public:
+ using difference_type = std::ptrdiff_t;
+ using value_type = typename Container::value_type;
+ using pointer = typename Container::pointer;
+ using reference = typename Container::reference;
+ using iterator_category = std::bidirectional_iterator_tag;
+
+ constexpr iterator() : view_(nullptr), it_(0) {}
+
+ iterator& operator++();
+
+ iterator operator++(int) {
+ iterator original = *this;
+ operator++();
+ return original;
+ }
+
+ iterator& operator--();
+
+ iterator operator--(int) {
+ iterator original = *this;
+ operator--();
+ return original;
+ }
+
+ const auto& operator*() const { return value(); }
+
+ const auto* operator->() const { return &value(); }
+
+ constexpr bool operator==(const iterator& other) const {
+ return view_ == other.view_ && it_ == other.it_;
+ }
+
+ constexpr bool operator!=(const iterator& other) const {
+ return !(*this == other);
+ }
+
+ private:
+ friend class FilteredView;
+
+ enum EndIterator { kEnd };
+
+ explicit iterator(const FilteredView& view)
+ : view_(&view), it_(view.container_.begin()) {
+ FindMatch();
+ }
+
+ iterator(const FilteredView& view, EndIterator)
+ : view_(&view), it_(view.container_.end()) {}
+
+ // Accesses the value referred to by this iterator.
+ const auto& value() const { return *it_; }
+
+ // Iterates until a match is found, up to end().
+ void FindMatch();
+
+ bool MatchesItem(const value_type& value) const {
+ return view_->filter_(value);
+ }
+
+ const FilteredView* view_;
+ typename Container::const_iterator it_;
+ };
+
+ using const_iterator = iterator;
+
+ template <typename... FilterArgs>
+ constexpr FilteredView(const Container& container, Filter&& filter)
+ : container_(container), filter_(std::move(filter)) {}
+
+ constexpr FilteredView(const FilteredView&) = delete;
+ constexpr FilteredView& operator=(const FilteredView&) = delete;
+
+ const auto& operator[](size_t index) const {
+ auto it = begin();
+ std::advance(it, index);
+ return *it;
+ }
+
+ // Accesses the first matching element. Invalid if empty().
+ const auto& front() const { return *begin(); }
+
+ // Accesses the last matching element. Invalid if empty().
+ const auto& back() const { return *std::prev(end()); }
+
+ // The number of elements in the container that match the filter.
+ size_t size() const { return std::distance(begin(), end()); }
+
+ bool empty() const { return begin() == end(); }
+
+ iterator begin() const { return iterator(*this); }
+ iterator end() const { return iterator(*this, iterator::kEnd); }
+
+ private:
+ const Container& container_;
+ Filter filter_;
+};
+
+template <typename Container, typename Filter>
+void FilteredView<Container, Filter>::iterator::FindMatch() {
+ for (; it_ != view_->container_.end(); ++it_) {
+ if (MatchesItem(*it_)) {
+ break;
+ }
+ }
+}
+
+template <typename Container, typename Filter>
+typename FilteredView<Container, Filter>::iterator&
+FilteredView<Container, Filter>::iterator::operator++() {
+ PW_ASSERT(it_ != view_->container_.end());
+
+ ++it_;
+ FindMatch();
+ return *this;
+}
+
+template <typename Container, typename Filter>
+typename FilteredView<Container, Filter>::iterator&
+FilteredView<Container, Filter>::iterator::operator--() {
+ decltype(it_) new_it = view_->container_.end();
+ while (new_it != view_->container_.begin()) {
+ --new_it;
+ if (MatchesItem(*new_it)) {
+ it_ = new_it;
+ return *this;
+ }
+ }
+
+ PW_ASSERT(false);
+}
+
+} // namespace pw::containers
diff --git a/pw_containers/public/pw_containers/intrusive_list.h b/pw_containers/public/pw_containers/intrusive_list.h
index b7e800f..9232203 100644
--- a/pw_containers/public/pw_containers/intrusive_list.h
+++ b/pw_containers/public/pw_containers/intrusive_list.h
@@ -53,6 +53,10 @@
class IntrusiveList {
public:
class Item : public intrusive_list_impl::List::Item {
+ public:
+ Item(const Item&) = delete;
+ Item& operator=(const Item&) = delete;
+
protected:
constexpr Item() = default;
