Time complexity O(1) with O(N) extra space
First, we can store all the indices where the array holds true values and thus have a constant time access to the next index. Pre-processing (constructing an array of indices) still takes linear time, so this approach makes sense when you want to iterate through your true indices many times.
This code shows a static version, while dynamic will require O(N) time to modify values in the array.
#include <array>
#include <vector>
template <unsigned N>
class BoolArray {
public:
using true_iterator = std::vector<unsigned>::const_iterator;
BoolArray(std::array<bool, N> &&Init) : Data(std::move(Init)) {
init();
}
true_iterator tbegin() const {
return TrueValues.begin();
}
true_iterator tend() const {
return TrueValues.end();
}
bool operator[](unsigned Index) {
return Data[Index];
}
private:
void init() {
TrueValues.reserve(N);
// O(N) time to pre-process the data
for (unsigned i = 0; i < N; ++i) {
if (Data[i]) {
TrueValues.push_back(i);
}
}
}
std::array<bool, N> Data;
// extra O(N) space for fast fetching of the next index
std::vector<unsigned> TrueValues;
};
Time complexity O(N) with O(1) extra space
This is a more straightforward approach. Iterate further where we left off and iterate all the way till the end.
Implemented iterator is only a prototype and can be implemented to be bidirectional.
#include <array>
template <unsigned N>
class BoolArray {
public:
BoolArray(std::array<bool, N> &&Init) : Data(std::move(Init)) {}
class true_iterator : public std::forward_iterator_tag {
public:
true_iterator(const true_iterator &) = default;
true_iterator &operator=(const true_iterator &) = default;
true_iterator(true_iterator &&) = default;
true_iterator &operator=(true_iterator &&) = default;
unsigned operator*() const {
// O(1) for random-access iterators, which is true for
// array iterators (it's just a difference between indices)
return std::distance(Data.begin(), Iterator);
}
true_iterator &operator++() {
++Iterator;
skipFalseValues();
return *this;
}
true_iterator &operator++(int) {
true_iterator tmp(*this);
operator++();
return tmp;
}
bool operator==(const true_iterator& rhs) const {
return Iterator == rhs.Iterator;
}
bool operator!=(const true_iterator& rhs) const {
return Iterator != rhs.Iterator;
}
private:
using UnderlyingIterator = typename std::array<bool, N>::const_iterator;
void skipFalseValues() {
// O(N) time to find next true element
for (;Iterator != Data.end() and not *Iterator; ++Iterator) {};
}
friend class BoolArray<N>;
true_iterator(const std::array<bool, N> &Data, UnderlyingIterator Current)
: Data(Data), Iterator(Current) {
skipFalseValues();
}
const std::array<bool, N> &Data;
UnderlyingIterator Iterator;
};
true_iterator tbegin() const {
return {Data, Data.begin()};
}
true_iterator tend() const {
return {Data, Data.end()};
}
bool operator[](unsigned Index) {
return Data[Index];
}
private:
std::array<bool, N> Data;
};
Test
In both cases, the following code:
int main() {
constexpr unsigned Size = 6;
BoolArray<Size> TestArray{ {false, true, false, false, false, true} };
for (auto It = TestArray.tbegin(), End = TestArray.tend(); It != End; ++It) {
std::cout <<
(TestArray[*It] ? "true" : "false") << " at index " << *It << std::endl;
}
}
produces this output:
true at index 1
true at index 5
for(int i=index + 1; i != index; i = (i+1) % arr.size())return arr[i];should bereturn i;