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),
135 validateConstruction();
145 nodeCapacity(p_nodeCapacity),
148 auto finalSize = treeSize(itemCapacity);
149 nodes.reserve(finalSize);
150 validateConstruction();
158 nodeCapacity(other.nodeCapacity),
159 numItems(other.numItems) {
166 nodeCapacity = other.nodeCapacity;
167 numItems = other.numItems;
178 insert(BoundsTraits::fromItem(item), std::forward<ItemType>(item));
183 insert(BoundsTraits::fromItem(item), item);
187 void insert(
const BoundsType& itemEnv, ItemType&& item) {
188 if (!BoundsTraits::isNull(itemEnv)) {
189 createLeafNode(std::forward<ItemType>(item), itemEnv);
194 void insert(
const BoundsType& itemEnv,
const ItemType& item) {
195 if (!BoundsTraits::isNull(itemEnv)) {
196 createLeafNode(item, itemEnv);
205 template<
typename ItemDistance>
211 template<
typename ItemDistance>
217 template<
typename ItemDistance>
221 return {
nullptr,
nullptr };
224 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(distance);
225 return td.nearestNeighbour(*root, *other.root);
229 template<
typename ItemDistance>
235 template<
typename ItemDistance>
243 TemplateSTRNode<ItemType, BoundsTraits> bnd(item, env);
244 TemplateSTRNodePair<ItemType, BoundsTraits, ItemDistance> pair(*
getRoot(), bnd, itemDist);
246 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(itemDist);
247 return td.nearestNeighbour(pair).first;
250 template<
typename ItemDistance>
256 template<
typename ItemDistance>
257 bool isWithinDistance(TemplateSTRtreeImpl<ItemType, BoundsTraits>& other,
double maxDistance) {
258 ItemDistance itemDist;
260 if (!
getRoot() || !other.getRoot()) {
264 TemplateSTRtreeDistance<ItemType, BoundsTraits, ItemDistance> td(itemDist);
265 return td.isWithinDistance(*root, *other.root, maxDistance);
277 template<
typename Visitor>
278 void query(
const BoundsType& queryEnv, Visitor &&visitor) {
283 if (root && root->boundsIntersect(queryEnv)) {
284 if (root->isLeaf()) {
285 visitLeaf(visitor, *root);
287 query(queryEnv, *root, visitor);
298 template<
typename Visitor>
299 void queryPairs(Visitor&& visitor) {
308 for (std::size_t i = 0; i < numItems; i++) {
309 queryPairs(nodes[i], *root, visitor);
314 void query(
const BoundsType& queryEnv, std::vector<ItemType>& results) {
315 query(queryEnv, [&results](
const ItemType& x) {
316 results.push_back(x);
334 auto n =
built() ? numItems : nodes.size();
335 for (
size_t i = 0; i < n; i++) {
336 if (!nodes[i].isDeleted()) {
337 func(nodes[i].getItem());
346 bool remove(
const BoundsType& itemEnv,
const ItemType& item) {
349 if (root ==
nullptr) {
353 if (root->isLeaf()) {
354 if (!root->isDeleted() && root->getItem() == item) {
361 return remove(itemEnv, *root, item);
370 return root !=
nullptr;
383 std::lock_guard<std::mutex> lock(lock_);
393 numItems = nodes.size();
397 auto finalSize = treeSize(numItems);
398 nodes.reserve(finalSize);
401 auto begin = nodes.begin();
402 auto number =
static_cast<size_t>(std::distance(begin, nodes.end()));
405 createParentNodes(begin, number);
406 std::advance(begin,
static_cast<long>(number));
407 number =
static_cast<size_t>(std::distance(begin, nodes.end()));
410 assert(finalSize == nodes.size());
412 root = &nodes.back();
425 void createLeafNode(ItemType&& item,
const BoundsType& env) {
426 nodes.emplace_back(std::forward<ItemType>(item), env);
429 void createLeafNode(
const ItemType& item,
const BoundsType& env) {
430 nodes.emplace_back(item, env);
433 void createBranchNode(
const Node *begin,
const Node *end) {
434 assert(nodes.size() < nodes.capacity());
435 nodes.emplace_back(begin, end);
440 size_t treeSize(
size_t numLeafNodes) {
441 size_t nodesInTree = numLeafNodes;
443 size_t nodesWithoutParents = numLeafNodes;
444 while (nodesWithoutParents > 1) {
445 auto numSlices = sliceCount(nodesWithoutParents);
446 auto nodesPerSlice = sliceCapacity(nodesWithoutParents, numSlices);
448 size_t parentNodesAdded = 0;
449 for (
size_t j = 0; j < numSlices; j++) {
450 auto nodesInSlice = std::min(nodesWithoutParents, nodesPerSlice);
451 nodesWithoutParents -= nodesInSlice;
453 parentNodesAdded +=
static_cast<size_t>(std::ceil(
454 static_cast<double>(nodesInSlice) /
static_cast<double>(nodeCapacity)));
457 nodesInTree += parentNodesAdded;
458 nodesWithoutParents = parentNodesAdded;
464 void createParentNodes(
const NodeListIterator& begin,
size_t number) {
468 auto numSlices = sliceCount(number);
469 std::size_t nodesPerSlice = sliceCapacity(number, numSlices);
475 auto end = begin +
static_cast<long>(number);
476 sortNodesX(begin, end);
478 auto startOfSlice = begin;
479 for (
decltype(numSlices) j = 0; j < numSlices; j++) {
481 end = begin +
static_cast<long>(number);
482 auto nodesRemaining =
static_cast<size_t>(std::distance(startOfSlice, end));
483 auto nodesInSlice = std::min(nodesRemaining, nodesPerSlice);
484 auto endOfSlice = std::next(startOfSlice,
static_cast<long>(nodesInSlice));
491 addParentNodesFromVerticalSlice(startOfSlice, endOfSlice);
493 startOfSlice = endOfSlice;
497 void addParentNodesFromVerticalSlice(
const NodeListIterator& begin,
const NodeListIterator& end) {
498 if (BoundsTraits::TwoDimensional::value) {
499 sortNodesY(begin, end);
505 auto firstChild = begin;
506 while (firstChild != end) {
507 auto childrenRemaining =
static_cast<size_t>(std::distance(firstChild, end));
508 auto childrenForNode = std::min(nodeCapacity, childrenRemaining);
509 auto lastChild = std::next(firstChild,
static_cast<long>(childrenForNode));
517 const Node *ptr_first = &*firstChild;
518 const Node *ptr_end = ptr_first + childrenForNode;
520 createBranchNode(ptr_first, ptr_end);
521 firstChild = lastChild;
525 void sortNodesX(
const NodeListIterator& begin,
const NodeListIterator& end) {
526 std::sort(begin, end, [](
const Node &a,
const Node &b) {
527 return BoundsTraits::getX(a.getBounds()) < BoundsTraits::getX(b.getBounds());
531 void sortNodesY(
const NodeListIterator& begin,
const NodeListIterator& end) {
532 std::sort(begin, end, [](
const Node &a,
const Node &b) {
533 return BoundsTraits::getY(a.getBounds()) < BoundsTraits::getY(b.getBounds());
540 template<
typename Visitor,
541 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
542 bool visitLeaf(Visitor&& visitor,
const Node& node)
544 visitor(node.getItem());
548 template<
typename Visitor,
549 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
550 bool visitLeaves(Visitor&& visitor,
const Node& node1,
const Node& node2)
552 visitor(node1.getItem(), node2.getItem());
558#if !defined(_MSC_VER) || _MSC_VER >= 1910
559 template<
typename Visitor,
560 typename std::enable_if<std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
561 bool visitLeaf(Visitor&& visitor,
const Node& node)
563 visitor(node.getBounds(), node.getItem());
570 template<
typename Visitor,
571 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr>
572 bool visitLeaf(Visitor&& visitor,
const Node& node)
574 return visitor(node.getItem());
577 template<
typename Visitor,
578 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<ItemType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr >
579 bool visitLeaves(Visitor&& visitor,
const Node& node1,
const Node& node2)
581 return visitor(node1.getItem(), node2.getItem());
586#if !defined(_MSC_VER) || _MSC_VER >= 1910
587 template<
typename Visitor,
588 typename std::enable_if<!std::is_void<decltype(std::declval<Visitor>()(std::declval<BoundsType>(), std::declval<ItemType>()))>::value, std::nullptr_t>::type =
nullptr>
589 bool visitLeaf(Visitor&& visitor,
const Node& node)
591 return visitor(node.getBounds(), node.getItem());
595 template<
typename Visitor>
596 bool query(
const BoundsType& queryEnv,
600 assert(!node.isLeaf());
602 for (
auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
603 if (child->boundsIntersect(queryEnv)) {
604 if (child->isLeaf()) {
605 if (!child->isDeleted()) {
606 if (!visitLeaf(visitor, *child)) {
611 if (!query(queryEnv, *child, visitor)) {
620 template<
typename Visitor>
621 bool queryPairs(
const Node& queryNode,
622 const Node& searchNode,
625 assert(!searchNode.isLeaf());
627 for (
auto* child = searchNode.beginChildren(); child < searchNode.endChildren(); ++child) {
628 if (child->isLeaf()) {
631 if (child > &queryNode && !child->isDeleted() && child->boundsIntersect(queryNode.getBounds())) {
632 if (!visitLeaves(visitor, queryNode, *child)) {
637 if (child->boundsIntersect(queryNode.getBounds())) {
638 if (!queryPairs(queryNode, *child, visitor)) {
648 bool remove(
const BoundsType& queryEnv,
650 const ItemType& item) {
652 assert(!node.isLeaf());
654 for (
auto *child = node.beginChildren(); child < node.endChildren(); ++child) {
655 if (child->boundsIntersect(queryEnv)) {
656 if (child->isLeaf()) {
657 if (!child->isDeleted() && child->getItem() == item) {
660 auto mutableChild =
const_cast<Node*
>(child);
661 mutableChild->removeItem();
665 bool removed = remove(queryEnv, *child, item);
676 size_t sliceCount(
size_t numNodes)
const {
677 double minLeafCount = std::ceil(
static_cast<double>(numNodes) /
static_cast<double>(nodeCapacity));
679 return static_cast<size_t>(std::ceil(std::sqrt(minLeafCount)));
682 static size_t sliceCapacity(
size_t numNodes,
size_t numSlices) {
683 return static_cast<size_t>(std::ceil(
static_cast<double>(numNodes) /
static_cast<double>(numSlices)));
686 void validateConstruction()
const {
687 if (nodeCapacity < 2) {
688 throw util::IllegalArgumentException(
"STRTree node capacity must be >= 2");