59 using Node = TemplateSTRNode<ItemType, BoundsTraits>;
60 using NodeList = std::vector<Node>;
61 using NodeListIterator =
typename NodeList::iterator;
62 using BoundsType =
typename BoundsTraits::BoundsType;
66 using iterator_category = std::forward_iterator_tag;
67 using value_type = ItemType;
68 using difference_type =
typename NodeList::const_iterator::difference_type;
69 using pointer = ItemType*;
70 using reference = ItemType&;
72 Iterator(
typename NodeList::const_iterator&& iter,
73 typename NodeList::const_iterator&& end) : m_iter(iter), m_end(end) {
77 const ItemType& operator*()
const {
78 return m_iter->getItem();
81 Iterator& operator++() {
87 friend bool operator==(
const Iterator& a,
const Iterator& b) {
88 return a.m_iter == b.m_iter;
91 friend bool operator!=(
const Iterator& a,
const Iterator& b) {
92 return a.m_iter != b.m_iter;
97 while(m_iter != m_end && m_iter->isDeleted()) {
102 typename NodeList::const_iterator m_iter;
103 typename NodeList::const_iterator m_end;
111 return Iterator(m_tree.nodes.cbegin(),
112 std::next(m_tree.nodes.cbegin(),
static_cast<long>(m_tree.numItems)));
116 return Iterator(std::next(m_tree.nodes.cbegin(),
static_cast<long>(m_tree.numItems)),
117 std::next(m_tree.nodes.cbegin(),
static_cast<long>(m_tree.numItems)));
132 nodeCapacity(p_nodeCapacity),
143 nodeCapacity(p_nodeCapacity),
145 auto finalSize = treeSize(itemCapacity);
146 nodes.reserve(finalSize);
154 nodeCapacity(other.nodeCapacity),
155 numItems(other.numItems) {
162 nodeCapacity = other.nodeCapacity;
163 numItems = other.numItems;
174 insert(BoundsTraits::fromItem(item), std::forward<ItemType>(item));
179 insert(BoundsTraits::fromItem(item), item);
183 void insert(
const BoundsType& itemEnv, ItemType&& item) {
184 if (!BoundsTraits::isNull(itemEnv)) {
185 createLeafNode(std::forward<ItemType>(item), itemEnv);
190 void insert(
const BoundsType& itemEnv,
const ItemType& item) {
191 if (!BoundsTraits::isNull(itemEnv)) {
192 createLeafNode(item, itemEnv);
201 template<
typename ItemDistance>
207 template<
typename ItemDistance>
213 template<
typename ItemDistance>
217 return {
nullptr,
nullptr };
220 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(distance);
221 return td.nearestNeighbour(*root, *other.root);
225 template<
typename ItemDistance>
231 template<
typename ItemDistance>
239 TemplateSTRNode<ItemType, BoundsTraits> bnd(item, env);
240 TemplateSTRNodePair<ItemType, BoundsTraits, ItemDistance> pair(*
getRoot(), bnd, itemDist);
242 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(itemDist);
243 return td.nearestNeighbour(pair).first;
246 template<
typename ItemDistance>
252 template<
typename ItemDistance>
253 bool isWithinDistance(TemplateSTRtreeImpl<ItemType, BoundsTraits>& other,
double maxDistance) {
254 ItemDistance itemDist;
256 if (!
getRoot() || !other.getRoot()) {
260 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(itemDist);
261 return td.isWithinDistance(*root, *other.root, maxDistance);
273 template<
typename Visitor>
274 void query(
const BoundsType& queryEnv, Visitor &&visitor) {
279 if (root && root->boundsIntersect(queryEnv)) {
280 if (root->isLeaf()) {
281 visitLeaf(visitor, *root);
283 query(queryEnv, *root, visitor);
294 template<
typename Visitor>
295 void queryPairs(Visitor&& visitor) {
304 for (std::size_t i = 0; i < numItems; i++) {
305 queryPairs(nodes[i], *root, visitor);
310 void query(
const BoundsType& queryEnv, std::vector<ItemType>& results) {
311 query(queryEnv, [&results](
const ItemType& x) {
312 results.push_back(x);
330 auto n =
built() ? numItems : nodes.size();
331 for (
size_t i = 0; i < n; i++) {
332 if (!nodes[i].isDeleted()) {
333 func(nodes[i].getItem());
342 bool remove(
const BoundsType& itemEnv,
const ItemType& item) {
345 if (root ==
nullptr) {
349 if (root->isLeaf()) {
350 if (!root->isDeleted() && root->getItem() == item) {
357 return remove(itemEnv, *root, item);
366 return root !=
nullptr;
379 std::lock_guard<std::mutex> lock(lock_);
389 numItems = nodes.size();
393 auto finalSize = treeSize(numItems);
394 nodes.reserve(finalSize);
397 auto begin = nodes.begin();
398 auto number =
static_cast<size_t>(std::distance(begin, nodes.end()));
401 createParentNodes(begin, number);
402 std::advance(begin,
static_cast<long>(number));
403 number =
static_cast<size_t>(std::distance(begin, nodes.end()));
406 assert(finalSize == nodes.size());
408 root = &nodes.back();
421 void createLeafNode(ItemType&& item,
const BoundsType& env) {
422 nodes.emplace_back(std::forward<ItemType>(item), env);
425 void createLeafNode(
const ItemType& item,
const BoundsType& env) {
426 nodes.emplace_back(item, env);
429 void createBranchNode(
const Node *begin,
const Node *end) {
430 assert(nodes.size() < nodes.capacity());
431 nodes.emplace_back(begin, end);
436 size_t treeSize(
size_t numLeafNodes) {
437 size_t nodesInTree = numLeafNodes;
439 size_t nodesWithoutParents = numLeafNodes;
440 while (nodesWithoutParents > 1) {
441 auto numSlices = sliceCount(nodesWithoutParents);
442 auto nodesPerSlice = sliceCapacity(nodesWithoutParents, numSlices);
444 size_t parentNodesAdded = 0;
445 for (
size_t j = 0; j < numSlices; j++) {
446 auto nodesInSlice = std::min(nodesWithoutParents, nodesPerSlice);
447 nodesWithoutParents -= nodesInSlice;
449 parentNodesAdded +=
static_cast<size_t>(std::ceil(
450 static_cast<double>(nodesInSlice) /
static_cast<double>(nodeCapacity)));
453 nodesInTree += parentNodesAdded;
454 nodesWithoutParents = parentNodesAdded;
460 void createParentNodes(
const NodeListIterator& begin,
size_t number) {
464 auto numSlices = sliceCount(number);
465 std::size_t nodesPerSlice = sliceCapacity(number, numSlices);
471 auto end = begin +
static_cast<long>(number);
472 sortNodesX(begin, end);
474 auto startOfSlice = begin;
475 for (
decltype(numSlices) j = 0; j < numSlices; j++) {
477 end = begin +
static_cast<long>(number);
478 auto nodesRemaining =
static_cast<size_t>(std::distance(startOfSlice, end));
479 auto nodesInSlice = std::min(nodesRemaining, nodesPerSlice);
480 auto endOfSlice = std::next(startOfSlice,
static_cast<long>(nodesInSlice));
487 addParentNodesFromVerticalSlice(startOfSlice, endOfSlice);
489 startOfSlice = endOfSlice;
493 void addParentNodesFromVerticalSlice(
const NodeListIterator& begin,
const NodeListIterator& end) {
494 if (BoundsTraits::TwoDimensional::value) {
495 sortNodesY(begin, end);
501 auto firstChild = begin;
502 while (firstChild != end) {
503 auto childrenRemaining =
static_cast<size_t>(std::distance(firstChild, end));
504 auto childrenForNode = std::min(nodeCapacity, childrenRemaining);
505 auto lastChild = std::next(firstChild,
static_cast<long>(childrenForNode));
513 const Node *ptr_first = &*firstChild;
514 const Node *ptr_end = ptr_first + childrenForNode;
516 createBranchNode(ptr_first, ptr_end);
517 firstChild = lastChild;
521 void sortNodesX(
const NodeListIterator& begin,
const NodeListIterator& end) {
522 std::sort(begin, end, [](
const Node &a,
const Node &b) {
523 return BoundsTraits::getX(a.getBounds()) < BoundsTraits::getX(b.getBounds());
527 void sortNodesY(
const NodeListIterator& begin,
const NodeListIterator& end) {
528 std::sort(begin, end, [](
const Node &a,
const Node &b) {
529 return BoundsTraits::getY(a.getBounds()) < BoundsTraits::getY(b.getBounds());
536 template<
typename Visitor,
537 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
538 bool visitLeaf(Visitor&& visitor,
const Node& node)
540 visitor(node.getItem());
544 template<
typename Visitor,
545 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
546 bool visitLeaves(Visitor&& visitor,
const Node& node1,
const Node& node2)
548 visitor(node1.getItem(), node2.getItem());
554#if !defined(_MSC_VER) || _MSC_VER >= 1910
555 template<
typename Visitor,
556 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
557 bool visitLeaf(Visitor&& visitor,
const Node& node)
559 visitor(node.getBounds(), node.getItem());
566 template<
typename Visitor,
567 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr>
568 bool visitLeaf(Visitor&& visitor,
const Node& node)
570 return visitor(node.getItem());
573 template<
typename Visitor,
574 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
575 bool visitLeaves(Visitor&& visitor,
const Node& node1,
const Node& node2)
577 return visitor(node1.getItem(), node2.getItem());
582#if !defined(_MSC_VER) || _MSC_VER >= 1910
583 template<
typename Visitor,
584 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr>
585 bool visitLeaf(Visitor&& visitor,
const Node& node)
587 return visitor(node.getBounds(), node.getItem());
591 template<
typename Visitor>
592 bool query(
const BoundsType& queryEnv,
596 assert(!node.isLeaf());
598 for (
auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
599 if (child->boundsIntersect(queryEnv)) {
600 if (child->isLeaf()) {
601 if (!child->isDeleted()) {
602 if (!visitLeaf(visitor, *child)) {
607 if (!query(queryEnv, *child, visitor)) {
616 template<
typename Visitor>
617 bool queryPairs(
const Node& queryNode,
618 const Node& searchNode,
621 assert(!searchNode.isLeaf());
623 for (
auto* child = searchNode.beginChildren(); child < searchNode.endChildren(); ++child) {
624 if (child->isLeaf()) {
627 if (child > &queryNode && !child->isDeleted() && child->boundsIntersect(queryNode.getBounds())) {
628 if (!visitLeaves(visitor, queryNode, *child)) {
633 if (child->boundsIntersect(queryNode.getBounds())) {
634 if (!queryPairs(queryNode, *child, visitor)) {
644 bool remove(
const BoundsType& queryEnv,
646 const ItemType& item) {
648 assert(!node.isLeaf());
650 for (
auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
651 if (child->boundsIntersect(queryEnv)) {
652 if (child->isLeaf()) {
653 if (!child->isDeleted() && child->getItem() == item) {
656 auto mutableChild =
const_cast<Node*
>(child);
657 mutableChild->removeItem();
661 bool removed = remove(queryEnv, *child, item);
672 size_t sliceCount(
size_t numNodes)
const {
673 double minLeafCount = std::ceil(
static_cast<double>(numNodes) /
static_cast<double>(nodeCapacity));
675 return static_cast<size_t>(std::ceil(std::sqrt(minLeafCount)));
678 static size_t sliceCapacity(
size_t numNodes,
size_t numSlices) {
679 return static_cast<size_t>(std::ceil(
static_cast<double>(numNodes) /
static_cast<double>(numSlices)));