Меня интересует использование range-v3 для построения и запроса линейных структур данных quadtree. Я смог успешно использовать range-v3 для построения линейной структуры данных quadtree с использованием существующих представлений в библиотеке. Я рад возможности выражать логику запросов в качестве адаптера представления, поскольку вы можете выполнять итерации по узлам в квадродереве, продвигая RandomAccessIterator из производного диапазона, что удобно помогает отделить поведение запроса от структуры квадродерева.
Мой адаптер представления имеет единственный аргумент: пользовательскую функцию лямбда-предиката, которая используется для оценки узла и определения, следует ли входить или выходить. Шаг в результате приводит к оценке дочерних узлов, тогда как шаг приводит к посещению следующего родного брата (или, возможно, следующего родного брата узла), пока либо не будет успешно оценен листовой узел, либо мы «выйдем» через корневой узел. (Вы можете думать об этом как о шаблоне DFS.)
Таким образом, мы можем определить этот диапазон в терминах RandomAccessIterator (из производного диапазона) и Sentinel (в отличие от другого Iterator).
Вот некоторый урезанный код, который показывает общую структуру. (Мои извинения, если отсутствуют данные / структура члена):
template<typename Rng, typename Fun>
class quadtree_query_view
: public ranges::view_adaptor<quadtree_query_view<Rng, Fun>, Rng>
{
friend ranges::range_access;
using base_iterator_t = ranges::iterator_t<Rng>;
ranges::semiregular_t<Fun> fun;
uint tree_depth;
struct query_termination_adaptor : public ranges::adaptor_base
{
query_termination_adaptor() = default;
query_termination_adaptor(uint tree_depth) : tree_depth(tree_depth) {};
uint tree_depth;
uint end(quadtree_query_view const&) {
return tree_depth;
}
};
struct query_adaptor : public ranges::adaptor_base
{
query_adaptor() = default;
query_adaptor(ranges::semiregular_t<Fun> const& fun) : fun(fun) {};
ranges::semiregular_t<Fun> fun;
bool exited = false;
uint current_node_depth = 0;
base_iterator_t begin(quadtree_query_view const& rng) {
return ranges::begin(rng.base());
}
// TODO: implement equal?
// TODO: implement empty?
auto read(base_iterator_t const& it) const
{
return *it; // I'm not concerned about the value returned by this range yet.
}
CONCEPT_REQUIRES(ranges::RandomAccessIterator<base_iterator_t>())
void next(base_iterator_t& it ){
if (fun(*it)) { // Step in
// Advance base iterator (step in)
// Increment current_node_depth
} else { // Step out
// Advance base iterator (step out)
// Set "exited = true" if stepping out past root node.
// Decrement current_node_depth
}
}
};
public:
quadtree_query_view() = default;
quadtree_query_view(Rng&& rng, uint tree_depth, Fun fun)
: quadtree_query_view::view_adaptor{std::forward<Rng>(rng)}
, tree_depth(tree_depth)
, fun(std::move(fun))
{}
query_adaptor begin_adaptor() const {
return {std::move(fun)};
}
query_termination_adaptor end_adaptor() const {
return {tree_depth};
}
};
Я пытаюсь выяснить последние несколько шагов для завершения этой реализации:
Мой диапазон не соответствует концепции Range из-за того, что требование WeaklyEqualityComparable не реализовано для моей пары итератор / страж. Как лучше всего это делать?
Нужно ли реализовать equal метод-член для query_adaptor? Чему соответствуют два аргумента итератора?
Я предполагаю, что мне нужно реализовать метод empty member для query_adaptor. Это где логика критериев выхода запроса? Основываясь на документации, аргумент сегмента должен быть типом, связанным с часовым. Это тот же тип, который возвращается query_termination_adaptor::end(), например, uint? Или это должен быть другой тип?
Спасибо за любые идеи, которыми вы можете поделиться. Я действительно рад видеть, что диапазоны включены в C ++ 20!