51 return NodePtr(
this, &(m_pTree->m_leafPool));
56 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
60 if (m_pIdentifier[cChild] ==
id && mbr == *(m_ptrMBR[cChild]))
return NodePtr(
this, &(m_pTree->m_leafPool));
68 ++(m_pTree->m_stats.m_u64Splits);
70 std::vector<uint32_t> g1, g2;
72 switch (m_pTree->m_treeVariant)
76 rtreeSplit(dataLength, pData, mbr,
id, g1, g2);
79 rstarSplit(dataLength, pData, mbr,
id, g1, g2);
85 pLeft = m_pTree->m_leafPool.acquire();
86 pRight = m_pTree->m_leafPool.acquire();
88 if (pLeft.
get() ==
nullptr) pLeft =
NodePtr(
new Leaf(m_pTree, -1), &(m_pTree->m_leafPool));
89 if (pRight.
get() ==
nullptr) pRight =
NodePtr(
new Leaf(m_pTree, -1), &(m_pTree->m_leafPool));
91 pLeft->m_nodeMBR = m_pTree->m_infiniteRegion;
92 pRight->m_nodeMBR = m_pTree->m_infiniteRegion;
96 for (cIndex = 0; cIndex < g1.size(); ++cIndex)
98 pLeft->insertEntry(m_pDataLength[g1[cIndex]], m_pData[g1[cIndex]], *(m_ptrMBR[g1[cIndex]]), m_pIdentifier[g1[cIndex]]);
100 m_pData[g1[cIndex]] =
nullptr;
103 for (cIndex = 0; cIndex < g2.size(); ++cIndex)
105 pRight->insertEntry(m_pDataLength[g2[cIndex]], m_pData[g2[cIndex]], *(m_ptrMBR[g2[cIndex]]), m_pIdentifier[g2[cIndex]]);
107 m_pData[g2[cIndex]] =
nullptr;
115 for (child = 0; child < m_children; ++child)
117 if (m_pIdentifier[child] ==
id && mbr == *(m_ptrMBR[child]))
break;
121 m_pTree->writeNode(
this);
123 std::stack<NodePtr> toReinsert;
124 NodePtr ptrThis(
this, &(m_pTree->m_leafPool));
125 condenseTree(toReinsert, pathBuffer, ptrThis);
129 while (! toReinsert.empty())
131 NodePtr n = toReinsert.top(); toReinsert.pop();
132 m_pTree->deleteNode(n.
get());
134 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
137 uint8_t* overflowTable =
new uint8_t[m_pTree->m_stats.m_u32TreeHeight];
138 memset(overflowTable, 0, m_pTree->m_stats.m_u32TreeHeight);
139 m_pTree->insertData_impl(n->m_pDataLength[cChild], n->m_pData[cChild], *(n->m_ptrMBR[cChild]), n->m_pIdentifier[cChild], n->m_level, overflowTable);
140 n->m_pData[cChild] =
nullptr;
141 delete[] overflowTable;
NodePtr findLeaf(const Region &mbr, id_type id, std::stack< id_type > &pathBuffer) override
NodePtr chooseSubtree(const Region &mbr, uint32_t level, std::stack< id_type > &pathBuffer) override
Leaf(RTree *pTree, id_type id)
Tools::PoolPointer< Node > NodePtr
void split(uint32_t dataLength, uint8_t *pData, Region &mbr, id_type id, NodePtr &left, NodePtr &right) override
virtual void deleteData(const Region &mbr, id_type id, std::stack< id_type > &pathBuffer)