59 (m_children * (4 * m_pTree->m_dimension *
sizeof(
double) +
sizeof(
double) +
sizeof(
id_type) +
sizeof(uint32_t))) +
61 (4 * m_pTree->m_dimension *
sizeof(
double)));
66 m_nodeMBR = m_pTree->m_infiniteRegion;
69 ptr +=
sizeof(uint32_t);
71 memcpy(&m_level, ptr,
sizeof(uint32_t));
72 ptr +=
sizeof(uint32_t);
74 memcpy(&m_children, ptr,
sizeof(uint32_t));
75 ptr +=
sizeof(uint32_t);
77 memcpy(&(m_nodeMBR.
m_startTime), ptr,
sizeof(
double));
78 ptr +=
sizeof(double);
79 m_nodeMBR.
m_endTime = std::numeric_limits<double>::max();
83 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
85 m_ptrMBR[cChild] = m_pTree->m_regionPool.
acquire();
88 memcpy(m_ptrMBR[cChild]->m_pLow, ptr, m_pTree->m_dimension *
sizeof(
double));
89 ptr += m_pTree->m_dimension *
sizeof(double);
90 memcpy(m_ptrMBR[cChild]->m_pHigh, ptr, m_pTree->m_dimension *
sizeof(
double));
91 ptr += m_pTree->m_dimension *
sizeof(double);
92 memcpy(m_ptrMBR[cChild]->m_pVLow, ptr, m_pTree->m_dimension *
sizeof(
double));
93 ptr += m_pTree->m_dimension *
sizeof(double);
94 memcpy(m_ptrMBR[cChild]->m_pVHigh, ptr, m_pTree->m_dimension *
sizeof(
double));
95 ptr += m_pTree->m_dimension *
sizeof(double);
96 memcpy(&(m_ptrMBR[cChild]->m_startTime), ptr,
sizeof(
double));
97 ptr +=
sizeof(double);
98 m_ptrMBR[cChild]->
m_endTime = std::numeric_limits<double>::max();
100 memcpy(&(m_pIdentifier[cChild]), ptr,
sizeof(
id_type));
103 memcpy(&(m_pDataLength[cChild]), ptr,
sizeof(uint32_t));
104 ptr +=
sizeof(uint32_t);
106 if (m_pDataLength[cChild] > 0)
108 m_totalDataLength += m_pDataLength[cChild];
109 m_pData[cChild] =
new uint8_t[m_pDataLength[cChild]];
110 memcpy(m_pData[cChild], ptr, m_pDataLength[cChild]);
111 ptr += m_pDataLength[cChild];
115 m_pData[cChild] =
nullptr;
121 memcpy(m_nodeMBR.
m_pLow, ptr, m_pTree->m_dimension *
sizeof(
double));
122 ptr += m_pTree->m_dimension *
sizeof(double);
123 memcpy(m_nodeMBR.
m_pHigh, ptr, m_pTree->m_dimension *
sizeof(
double));
124 ptr += m_pTree->m_dimension *
sizeof(double);
125 memcpy(m_nodeMBR.
m_pVLow, ptr, m_pTree->m_dimension *
sizeof(
double));
126 ptr += m_pTree->m_dimension *
sizeof(double);
127 memcpy(m_nodeMBR.
m_pVHigh, ptr, m_pTree->m_dimension *
sizeof(
double));
135 *data =
new uint8_t[len];
136 uint8_t* ptr = *data;
143 memcpy(ptr, &nodeType,
sizeof(uint32_t));
144 ptr +=
sizeof(uint32_t);
146 memcpy(ptr, &m_level,
sizeof(uint32_t));
147 ptr +=
sizeof(uint32_t);
149 memcpy(ptr, &m_children,
sizeof(uint32_t));
150 ptr +=
sizeof(uint32_t);
152 memcpy(ptr, &(m_nodeMBR.
m_startTime),
sizeof(
double));
153 ptr +=
sizeof(double);
155 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
157 memcpy(ptr, m_ptrMBR[cChild]->m_pLow, m_pTree->m_dimension *
sizeof(
double));
158 ptr += m_pTree->m_dimension *
sizeof(double);
159 memcpy(ptr, m_ptrMBR[cChild]->m_pHigh, m_pTree->m_dimension *
sizeof(
double));
160 ptr += m_pTree->m_dimension *
sizeof(double);
161 memcpy(ptr, m_ptrMBR[cChild]->m_pVLow, m_pTree->m_dimension *
sizeof(
double));
162 ptr += m_pTree->m_dimension *
sizeof(double);
163 memcpy(ptr, m_ptrMBR[cChild]->m_pVHigh, m_pTree->m_dimension *
sizeof(
double));
164 ptr += m_pTree->m_dimension *
sizeof(double);
165 memcpy(ptr, &(m_ptrMBR[cChild]->m_startTime),
sizeof(
double));
166 ptr +=
sizeof(double);
168 memcpy(ptr, &(m_pIdentifier[cChild]),
sizeof(
id_type));
171 memcpy(ptr, &(m_pDataLength[cChild]),
sizeof(uint32_t));
172 ptr +=
sizeof(uint32_t);
174 if (m_pDataLength[cChild] > 0)
176 memcpy(ptr, m_pData[cChild], m_pDataLength[cChild]);
177 ptr += m_pDataLength[cChild];
182 memcpy(ptr, m_nodeMBR.
m_pLow, m_pTree->m_dimension *
sizeof(
double));
183 ptr += m_pTree->m_dimension *
sizeof(double);
184 memcpy(ptr, m_nodeMBR.
m_pHigh, m_pTree->m_dimension *
sizeof(
double));
185 ptr += m_pTree->m_dimension *
sizeof(double);
186 memcpy(ptr, m_nodeMBR.
m_pVLow, m_pTree->m_dimension *
sizeof(
double));
187 ptr += m_pTree->m_dimension *
sizeof(double);
188 memcpy(ptr, m_nodeMBR.
m_pVHigh, m_pTree->m_dimension *
sizeof(
double));
191 assert(len == (ptr - *data) + m_pTree->m_dimension *
sizeof(
double));
219 return m_pIdentifier[
index];
232 if (m_pData[index] ==
nullptr)
239 length = m_pDataLength[
index];
240 *data = m_pData[
index];
251 return (m_level == 0);
256 return (m_level != 0);
271 m_capacity(capacity),
274 m_pIdentifier(
nullptr),
275 m_pDataLength(
nullptr),
282 m_pDataLength =
new uint32_t[m_capacity + 1];
283 m_pData =
new uint8_t*[m_capacity + 1];
285 m_pIdentifier =
new id_type[m_capacity + 1];
289 delete[] m_pDataLength;
292 delete[] m_pIdentifier;
299 if (m_pData !=
nullptr)
301 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
303 if (m_pData[cChild] !=
nullptr)
delete[] m_pData[cChild];
309 delete[] m_pDataLength;
311 delete[] m_pIdentifier;
321 assert(m_children < m_capacity);
323 m_pDataLength[m_children] = dataLength;
324 m_pData[m_children] = pData;
325 m_ptrMBR[m_children] = m_pTree->m_regionPool.
acquire();
326 *(m_ptrMBR[m_children]) = mbr;
327 m_pIdentifier[m_children] = id;
329 m_totalDataLength += dataLength;
332 if (m_nodeMBR.
m_startTime != m_pTree->m_currentTime)
336 for (uint32_t cDim = 0; cDim < m_nodeMBR.
m_dimension; ++cDim)
338 m_nodeMBR.
m_pLow[cDim] = std::numeric_limits<double>::max();
339 m_nodeMBR.
m_pHigh[cDim] = -std::numeric_limits<double>::max();
340 m_nodeMBR.
m_pVLow[cDim] = std::numeric_limits<double>::max();
341 m_nodeMBR.
m_pVHigh[cDim] = -std::numeric_limits<double>::max();
343 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
350 m_nodeMBR.
m_pLow[cDim] -= 2.0 * std::numeric_limits<double>::epsilon();
351 m_nodeMBR.
m_pHigh[cDim] += 2.0 * std::numeric_limits<double>::epsilon();
358 for (uint32_t cDim = 0; cDim < m_nodeMBR.
m_dimension; ++cDim)
364 m_nodeMBR.
m_pLow[cDim] = rl - 2.0 * std::numeric_limits<double>::epsilon();
371 m_nodeMBR.
m_pHigh[cDim] = rh + 2.0 * std::numeric_limits<double>::epsilon();
380 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
389 void Node::deleteEntry(uint32_t
index)
391 assert(index >= 0 && index < m_children);
396 m_totalDataLength -= m_pDataLength[
index];
397 if (m_pData[index] !=
nullptr)
delete[] m_pData[
index];
399 if (m_children > 1 && index != m_children - 1)
401 m_pDataLength[
index] = m_pDataLength[m_children - 1];
402 m_pData[
index] = m_pData[m_children - 1];
403 m_ptrMBR[
index] = m_ptrMBR[m_children - 1];
404 m_pIdentifier[
index] = m_pIdentifier[m_children - 1];
413 m_nodeMBR = m_pTree->m_infiniteRegion;
419 for (uint32_t cDim = 0; cDim < m_nodeMBR.
m_dimension; ++cDim)
421 m_nodeMBR.
m_pLow[cDim] = std::numeric_limits<double>::max();
422 m_nodeMBR.
m_pHigh[cDim] = -std::numeric_limits<double>::max();
423 m_nodeMBR.
m_pVLow[cDim] = std::numeric_limits<double>::max();
424 m_nodeMBR.
m_pVHigh[cDim] = -std::numeric_limits<double>::max();
426 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
433 m_nodeMBR.
m_pLow[cDim] -= 2.0 * std::numeric_limits<double>::epsilon();
434 m_nodeMBR.
m_pHigh[cDim] += 2.0 * std::numeric_limits<double>::epsilon();
438 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
446 bool Node::insertData(uint32_t dataLength, uint8_t* pData,
MovingRegion& mbr,
id_type id, std::stack<id_type>& pathBuffer, uint8_t* overflowTable)
448 if (m_children < m_capacity)
450 bool bNeedToAdjust = insertEntry(dataLength, pData, mbr,
id);
451 m_pTree->writeNode(
this);
453 if (bNeedToAdjust && ! pathBuffer.empty())
455 id_type cParent = pathBuffer.top(); pathBuffer.pop();
456 NodePtr ptrN = m_pTree->readNode(cParent);
458 p->adjustTree(
this, pathBuffer);
461 return bNeedToAdjust;
465 !pathBuffer.empty() &&
466 overflowTable[m_level] == 0)
468 overflowTable[m_level] = 1;
470 std::vector<uint32_t> vReinsert, vKeep;
471 reinsertData(dataLength, pData, mbr,
id, vReinsert, vKeep);
473 uint32_t lReinsert =
static_cast<uint32_t
>(vReinsert.size());
474 uint32_t lKeep =
static_cast<uint32_t
>(vKeep.size());
476 uint8_t** reinsertdata =
nullptr;
479 uint32_t* reinsertlen =
nullptr;
480 uint8_t** keepdata =
nullptr;
483 uint32_t* keeplen =
nullptr;
487 reinsertdata =
new uint8_t*[lReinsert];
489 reinsertid =
new id_type[lReinsert];
490 reinsertlen =
new uint32_t[lReinsert];
492 keepdata =
new uint8_t*[m_capacity + 1];
494 keepid =
new id_type[m_capacity + 1];
495 keeplen =
new uint32_t[m_capacity + 1];
499 delete[] reinsertdata;
500 delete[] reinsertmbr;
502 delete[] reinsertlen;
512 for (cIndex = 0; cIndex < lReinsert; ++cIndex)
514 reinsertlen[cIndex] = m_pDataLength[vReinsert[cIndex]];
515 reinsertdata[cIndex] = m_pData[vReinsert[cIndex]];
516 reinsertmbr[cIndex] = m_ptrMBR[vReinsert[cIndex]];
517 reinsertid[cIndex] = m_pIdentifier[vReinsert[cIndex]];
520 for (cIndex = 0; cIndex < lKeep; ++cIndex)
522 keeplen[cIndex] = m_pDataLength[vKeep[cIndex]];
523 keepdata[cIndex] = m_pData[vKeep[cIndex]];
524 keepmbr[cIndex] = m_ptrMBR[vKeep[cIndex]];
525 keepid[cIndex] = m_pIdentifier[vKeep[cIndex]];
528 delete[] m_pDataLength;
531 delete[] m_pIdentifier;
533 m_pDataLength = keeplen;
536 m_pIdentifier = keepid;
538 m_totalDataLength = 0;
540 for (uint32_t cChild = 0; cChild < m_children; ++cChild) m_totalDataLength += m_pDataLength[cChild];
544 for (uint32_t cDim = 0; cDim < m_nodeMBR.
m_dimension; ++cDim)
546 m_nodeMBR.
m_pLow[cDim] = std::numeric_limits<double>::max();
547 m_nodeMBR.
m_pHigh[cDim] = -std::numeric_limits<double>::max();
548 m_nodeMBR.
m_pVLow[cDim] = std::numeric_limits<double>::max();
549 m_nodeMBR.
m_pVHigh[cDim] = -std::numeric_limits<double>::max();
551 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
558 m_nodeMBR.
m_pLow[cDim] -= 2.0 * std::numeric_limits<double>::epsilon();
559 m_nodeMBR.
m_pHigh[cDim] += 2.0 * std::numeric_limits<double>::epsilon();
563 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
569 m_pTree->writeNode(
this);
574 id_type cParent = pathBuffer.top(); pathBuffer.pop();
575 NodePtr ptrN = m_pTree->readNode(cParent);
577 p->adjustTree(
this, pathBuffer);
579 for (cIndex = 0; cIndex < lReinsert; ++cIndex)
581 m_pTree->insertData_impl(
582 reinsertlen[cIndex], reinsertdata[cIndex],
583 *(reinsertmbr[cIndex]), reinsertid[cIndex],
584 m_level, overflowTable);
587 delete[] reinsertdata;
588 delete[] reinsertmbr;
590 delete[] reinsertlen;
598 split(dataLength, pData, mbr,
id, n, nn);
600 if (pathBuffer.empty())
602 n->m_level = m_level;
603 nn->m_level = m_level;
604 n->m_identifier = -1;
605 nn->m_identifier = -1;
608 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
612 for (uint32_t cChild = 0; cChild < nn->m_children; ++cChild)
618 m_pTree->writeNode(n.
get());
619 m_pTree->writeNode(nn.
get());
622 if (ptrR.
get() ==
nullptr)
624 ptrR =
NodePtr(
new Index(m_pTree, m_pTree->m_rootID, m_level + 1), &(m_pTree->m_indexPool));
629 ptrR->m_identifier = m_pTree->m_rootID;
630 ptrR->m_level = m_level + 1;
631 ptrR->m_nodeMBR = m_pTree->m_infiniteRegion;
634 ptrR->insertEntry(0,
nullptr, n->m_nodeMBR, n->m_identifier);
635 ptrR->insertEntry(0,
nullptr, nn->m_nodeMBR, nn->m_identifier);
637 m_pTree->writeNode(ptrR.
get());
639 m_pTree->m_stats.m_nodesInLevel[m_level] = 2;
640 m_pTree->m_stats.m_nodesInLevel.push_back(1);
641 m_pTree->m_stats.m_treeHeight = m_level + 2;
645 n->m_level = m_level;
646 nn->m_level = m_level;
647 n->m_identifier = m_identifier;
648 nn->m_identifier = -1;
651 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
655 for (uint32_t cChild = 0; cChild < nn->m_children; ++cChild)
661 m_pTree->writeNode(n.
get());
662 m_pTree->writeNode(nn.
get());
664 id_type cParent = pathBuffer.top(); pathBuffer.pop();
665 NodePtr ptrN = m_pTree->readNode(cParent);
667 p->adjustTree(n.
get(), nn.
get(), pathBuffer, overflowTable);
674 void Node::reinsertData(uint32_t dataLength, uint8_t* pData,
MovingRegion& mbr,
id_type id, std::vector<uint32_t>& reinsert, std::vector<uint32_t>& keep)
676 ReinsertEntry** v =
new ReinsertEntry*[m_capacity + 1];
678 m_pDataLength[m_children] = dataLength;
679 m_pData[m_children] = pData;
680 m_ptrMBR[m_children] = m_pTree->m_regionPool.
acquire();
681 *(m_ptrMBR[m_children]) = mbr;
682 m_pIdentifier[m_children] = id;
684 Tools::Interval ivT(m_pTree->m_currentTime, m_pTree->m_currentTime + m_pTree->m_horizon);
686 for (uint32_t cChild = 0; cChild < m_capacity + 1; ++cChild)
690 v[cChild] =
new ReinsertEntry(cChild, 0.0);
694 for (uint32_t i = 0; i < cChild; ++i)
delete v[i];
703 ::qsort(v, m_capacity + 1,
sizeof(ReinsertEntry*), ReinsertEntry::compareReinsertEntry);
705 uint32_t cReinsert =
static_cast<uint32_t
>(std::floor((m_capacity + 1) * m_pTree->m_reinsertFactor));
709 for (cCount = 0; cCount < cReinsert; ++cCount)
711 reinsert.push_back(v[cCount]->m_index);
715 for (cCount = cReinsert; cCount < m_capacity + 1; ++cCount)
717 keep.push_back(v[cCount]->m_index);
879 void Node::rstarSplit(uint32_t dataLength, uint8_t* pData,
MovingRegion& mbr,
id_type id, std::vector<uint32_t>& group1, std::vector<uint32_t>& group2)
881 RstarSplitEntry** dataLow =
nullptr;
882 RstarSplitEntry** dataHigh =
nullptr;
883 RstarSplitEntry** dataVLow =
nullptr;
884 RstarSplitEntry** dataVHigh =
nullptr;
888 dataLow =
new RstarSplitEntry*[m_capacity + 1];
889 dataHigh =
new RstarSplitEntry*[m_capacity + 1];
890 dataVLow =
new RstarSplitEntry*[m_capacity + 1];
891 dataVHigh =
new RstarSplitEntry*[m_capacity + 1];
902 m_pDataLength[m_capacity] = dataLength;
903 m_pData[m_capacity] = pData;
904 m_ptrMBR[m_capacity] = m_pTree->m_regionPool.
acquire();
905 *(m_ptrMBR[m_capacity]) = mbr;
906 m_pIdentifier[m_capacity] = id;
908 uint32_t nodeSPF =
static_cast<uint32_t
>(std::floor((m_capacity + 1) * m_pTree->m_splitDistributionFactor));
909 uint32_t splitDistribution = (m_capacity + 1) - (2 * nodeSPF) + 2;
911 Tools::Interval ivT(m_pTree->m_currentTime, m_pTree->m_currentTime + m_pTree->m_horizon);
913 uint32_t cChild = 0, cDim, cIndex;
915 for (cChild = 0; cChild <= m_capacity; ++cChild)
919 dataLow[cChild] =
new RstarSplitEntry(m_ptrMBR[cChild].
get(), cChild, 0);
923 for (uint32_t i = 0; i < cChild; ++i)
delete dataLow[i];
929 dataHigh[cChild] = dataLow[cChild];
930 dataVLow[cChild] = dataLow[cChild];
931 dataVHigh[cChild] = dataLow[cChild];
934 double minimumMargin = std::numeric_limits<double>::max();
935 uint32_t splitAxis = std::numeric_limits<uint32_t>::max();
936 uint32_t sortOrder = std::numeric_limits<uint32_t>::max();
939 for (cDim = 0; cDim < m_pTree->m_dimension; ++cDim)
941 ::qsort(dataLow, m_capacity + 1,
sizeof(RstarSplitEntry*), RstarSplitEntry::compareLow);
942 ::qsort(dataHigh, m_capacity + 1,
sizeof(RstarSplitEntry*), RstarSplitEntry::compareHigh);
943 ::qsort(dataVLow, m_capacity + 1,
sizeof(RstarSplitEntry*), RstarSplitEntry::compareVLow);
944 ::qsort(dataVHigh, m_capacity + 1,
sizeof(RstarSplitEntry*), RstarSplitEntry::compareVHigh);
947 double marginl = 0.0;
948 double marginh = 0.0;
949 double marginvl = 0.0;
950 double marginvh = 0.0;
955 for (cChild = 1; cChild <= splitDistribution; ++cChild)
957 uint32_t l = nodeSPF - 1 + cChild;
959 bbl1 = *(dataLow[0]->m_pRegion);
960 bbh1 = *(dataHigh[0]->m_pRegion);
961 bbvl1 = *(dataVLow[0]->m_pRegion);
962 bbvh1 = *(dataVHigh[0]->m_pRegion);
964 for (cIndex = 1; cIndex < l; ++cIndex)
972 bbl2 = *(dataLow[l]->m_pRegion);
973 bbh2 = *(dataHigh[l]->m_pRegion);
974 bbvl2 = *(dataVLow[l]->m_pRegion);
975 bbvh2 = *(dataVHigh[l]->m_pRegion);
977 for (cIndex = l + 1; cIndex <= m_capacity; ++cIndex)
991 double margin = std::min(std::min(marginl, marginh), std::min(marginvl, marginvh));
994 if (margin < minimumMargin)
996 minimumMargin = margin;
998 if (marginl < marginh && marginl < marginvl && marginl < marginvh) sortOrder = 0;
999 else if (marginh < marginl && marginh < marginvl && marginh < marginvh) sortOrder = 1;
1000 else if (marginvl < marginl && marginvl < marginh && marginvl < marginvh) sortOrder = 2;
1001 else if (marginvh < marginl && marginvh < marginh && marginvh < marginvl) sortOrder = 3;
1005 for (cChild = 0; cChild <= m_capacity; ++cChild)
1007 dataLow[cChild]->m_sortDim = cDim + 1;
1011 for (cChild = 0; cChild <= m_capacity; ++cChild)
1013 dataLow[cChild]->m_sortDim = splitAxis;
1017 ::qsort(dataLow, m_capacity + 1,
sizeof(RstarSplitEntry*), RstarSplitEntry::compareLow);
1018 else if (sortOrder == 1)
1019 ::qsort(dataLow, m_capacity + 1,
sizeof(RstarSplitEntry*), RstarSplitEntry::compareHigh);
1020 else if (sortOrder == 2)
1021 ::qsort(dataLow, m_capacity + 1,
sizeof(RstarSplitEntry*), RstarSplitEntry::compareVLow);
1022 else if (sortOrder == 3)
1023 ::qsort(dataLow, m_capacity + 1,
sizeof(RstarSplitEntry*), RstarSplitEntry::compareVHigh);
1025 double ma = std::numeric_limits<double>::max();
1026 double mo = std::numeric_limits<double>::max();
1027 uint32_t splitPoint = std::numeric_limits<uint32_t>::max();
1031 for (cChild = 1; cChild <= splitDistribution; ++cChild)
1033 uint32_t l = nodeSPF - 1 + cChild;
1035 bb1 = *(dataLow[0]->m_pRegion);
1037 for (cIndex = 1; cIndex < l; ++cIndex)
1042 bb2 = *(dataLow[l]->m_pRegion);
1044 for (cIndex = l + 1; cIndex <= m_capacity; ++cIndex)
1053 splitPoint = cChild;
1063 splitPoint = cChild;
1069 uint32_t l1 = nodeSPF - 1 + splitPoint;
1071 for (cIndex = 0; cIndex < l1; ++cIndex)
1073 group1.push_back(dataLow[cIndex]->m_index);
1074 delete dataLow[cIndex];
1077 for (cIndex = l1; cIndex <= m_capacity; ++cIndex)
1079 group2.push_back(dataLow[cIndex]->m_index);
1080 delete dataLow[cIndex];
1168 void Node::condenseTree(std::stack<NodePtr>& toReinsert, std::stack<id_type>& pathBuffer,
NodePtr& ptrThis)
1170 uint32_t minimumLoad =
static_cast<uint32_t
>(std::floor(m_capacity * m_pTree->m_fillFactor));
1172 if (pathBuffer.empty())
1175 if (m_level != 0 && m_children == 1)
1177 NodePtr ptrN = m_pTree->readNode(m_pIdentifier[0]);
1178 m_pTree->deleteNode(ptrN.
get());
1179 ptrN->m_identifier = m_pTree->m_rootID;
1180 m_pTree->writeNode(ptrN.
get());
1182 m_pTree->m_stats.m_nodesInLevel.pop_back();
1183 m_pTree->m_stats.m_treeHeight -= 1;
1185 m_pTree->m_stats.m_nodesInLevel[m_pTree->m_stats.m_treeHeight - 1] = 2;
1190 id_type cParent = pathBuffer.top(); pathBuffer.pop();
1191 NodePtr ptrParent = m_pTree->readNode(cParent);
1197 for (child = 0; child != p->m_children; ++child)
1199 if (p->m_pIdentifier[child] == m_identifier)
break;
1202 if (m_children < minimumLoad)
1206 p->deleteEntry(child);
1208 toReinsert.push(ptrThis);
1213 *(p->m_ptrMBR[child]) = m_nodeMBR;
1220 p->m_nodeMBR.m_startTime = m_pTree->m_currentTime;
1222 for (uint32_t cDim = 0; cDim < p->m_nodeMBR.m_dimension; ++cDim)
1224 p->m_nodeMBR.m_pLow[cDim] = std::numeric_limits<double>::max();
1225 p->m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();
1226 p->m_nodeMBR.m_pVLow[cDim] = std::numeric_limits<double>::max();
1227 p->m_nodeMBR.m_pVHigh[cDim] = -std::numeric_limits<double>::max();
1229 for (uint32_t cChild = 0; cChild < p->m_children; ++cChild)
1231 p->m_nodeMBR.m_pLow[cDim] = std::min(p->m_nodeMBR.m_pLow[cDim], p->m_ptrMBR[cChild]->getExtrapolatedLow(cDim, m_pTree->m_currentTime));
1232 p->m_nodeMBR.m_pHigh[cDim] = std::max(p->m_nodeMBR.m_pHigh[cDim], p->m_ptrMBR[cChild]->getExtrapolatedHigh(cDim, m_pTree->m_currentTime));
1233 p->m_nodeMBR.m_pVLow[cDim] = std::min(p->m_nodeMBR.m_pVLow[cDim], p->m_ptrMBR[cChild]->m_pVLow[cDim]);
1234 p->m_nodeMBR.m_pVHigh[cDim] = std::max(p->m_nodeMBR.m_pVHigh[cDim], p->m_ptrMBR[cChild]->m_pVHigh[cDim]);
1236 p->m_nodeMBR.m_pLow[cDim] -= 2.0 * std::numeric_limits<double>::epsilon();
1237 p->m_nodeMBR.m_pHigh[cDim] += 2.0 * std::numeric_limits<double>::epsilon();
1243 m_pTree->writeNode(p);
1245 p->condenseTree(toReinsert, pathBuffer, ptrParent);
virtual double getExtrapolatedHigh(uint32_t index, double t) const
bool isLeaf() const override
void makeDimension(uint32_t dimension) override
virtual double getExtrapolatedLow(uint32_t index, double t) const
id_type getChildIdentifier(uint32_t index) const override
void makeInfinite(uint32_t dimension) override
void storeToByteArray(uint8_t **data, uint32_t &len) override
virtual double getCenterDistanceInTime(const MovingRegion &r) const
virtual double getProjectedSurfaceAreaInTime() const
void loadFromByteArray(const uint8_t *data) override
virtual double getIntersectingAreaInTime(const MovingRegion &r) const
void getChildShape(uint32_t index, IShape **out) const override
double getAreaInTime() const override
Tools::PoolPointer< Node > NodePtr
virtual void combineRegionAfterTime(double t, const MovingRegion &r)
bool isIndex() const override
uint32_t getLevel() const override
Tools::IObject * clone() override
void getChildData(uint32_t index, uint32_t &length, uint8_t **data) const override
SpatialIndex::ISpatialIndex & index()
id_type getIdentifier() const override
uint32_t getByteArraySize() override
uint32_t getChildrenCount() const override
void getShape(IShape **out) const override
virtual bool containsRegionAfterTime(double t, const MovingRegion &r) const