1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
// 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"
#include "pw_preprocessor/compiler.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);
PW_UNREACHABLE;
}
} // namespace pw::containers
|
