41 : m_id(id), m_region(r), m_pData(nullptr), m_dataLength(len)
100 ptr +=
sizeof(uint32_t);
116 uint8_t* regiondata =
nullptr;
121 *data =
new uint8_t[len];
122 uint8_t* ptr = *data;
127 ptr +=
sizeof(uint32_t);
135 memcpy(ptr, regiondata, regionsize);
149 uint32_t indexCapacity,
150 uint32_t leafCapacity,
205 m_pStorageManager(&sm),
206 m_rootID(StorageManager::
NewPage),
207 m_headerID(StorageManager::
NewPage),
210 m_indexCapacity(100),
212 m_nearMinimumOverlapFactor(32),
213 m_splitDistributionFactor(0.4),
214 m_reinsertFactor(0.3),
276 mr->
m_endTime = std::numeric_limits<double>::max();
278 uint8_t* buffer =
nullptr;
282 buffer =
new uint8_t[len];
283 memcpy(buffer, pData, len);
287 insertData_impl(len, buffer, *mr,
id);
315 mr->
m_endTime = std::numeric_limits<double>::max();
318 bool ret = deleteData_impl(*mr,
id);
461 m_readNodeCommands.push_back(std::shared_ptr<ICommand>(pCommand));
464 m_writeNodeCommands.push_back(std::shared_ptr<ICommand>(pCommand));
467 m_deleteNodeCommands.push_back(std::shared_ptr<ICommand>(pCommand));
476 std::stack<ValidateEntry> st;
477 NodePtr root = readNode(m_rootID);
479 if (root->m_level != m_stats.m_treeHeight - 1)
481 std::cerr <<
"Invalid tree height." << std::endl;
485 std::map<uint32_t, uint32_t> nodesInLevel;
486 nodesInLevel.insert(std::pair<uint32_t, uint32_t>(root->m_level, 1));
488 ValidateEntry e(root->m_nodeMBR, root);
493 e = st.top(); st.pop();
496 tmpRegion = m_infiniteRegion;
503 for (uint32_t cDim = 0; cDim < tmpRegion.
m_dimension; ++cDim)
505 tmpRegion.
m_pLow[cDim] = std::numeric_limits<double>::max();
506 tmpRegion.
m_pHigh[cDim] = -std::numeric_limits<double>::max();
507 tmpRegion.
m_pVLow[cDim] = std::numeric_limits<double>::max();
508 tmpRegion.
m_pVHigh[cDim] = -std::numeric_limits<double>::max();
510 for (uint32_t cChild = 0; cChild < e.m_pNode->m_children; ++cChild)
512 tmpRegion.
m_pLow[cDim] = std::min(tmpRegion.
m_pLow[cDim], e.m_pNode->m_ptrMBR[cChild]->getExtrapolatedLow(cDim, tmpRegion.
m_startTime));
513 tmpRegion.
m_pHigh[cDim] = std::max(tmpRegion.
m_pHigh[cDim], e.m_pNode->m_ptrMBR[cChild]->getExtrapolatedHigh(cDim, tmpRegion.
m_startTime));
514 tmpRegion.
m_pVLow[cDim] = std::min(tmpRegion.
m_pVLow[cDim], e.m_pNode->m_ptrMBR[cChild]->m_pVLow[cDim]);
515 tmpRegion.
m_pVHigh[cDim] = std::max(tmpRegion.
m_pVHigh[cDim], e.m_pNode->m_ptrMBR[cChild]->m_pVHigh[cDim]);
517 tmpRegion.
m_pLow[cDim] -= 2.0 * std::numeric_limits<double>::epsilon();
518 tmpRegion.
m_pHigh[cDim] += 2.0 * std::numeric_limits<double>::epsilon();
521 if (! (tmpRegion == e.m_pNode->m_nodeMBR))
523 std::cerr <<
"Invalid parent information." << std::endl;
526 if (! (tmpRegion == e.m_parentMBR))
528 std::cerr <<
"Error in parent." << std::endl;
532 if (e.m_pNode->m_level != 0)
534 for (uint32_t cChild = 0; cChild < e.m_pNode->m_children; ++cChild)
536 NodePtr ptrN = readNode(e.m_pNode->m_pIdentifier[cChild]);
537 ValidateEntry tmpEntry(*(e.m_pNode->m_ptrMBR[cChild]), ptrN);
539 auto itNodes = nodesInLevel.find(tmpEntry.m_pNode->m_level);
541 if (itNodes == nodesInLevel.end())
543 nodesInLevel.insert(std::pair<uint32_t, uint32_t>(tmpEntry.m_pNode->m_level, 1l));
547 nodesInLevel[tmpEntry.m_pNode->m_level] = nodesInLevel[tmpEntry.m_pNode->m_level] + 1;
556 for (uint32_t cLevel = 0; cLevel < m_stats.m_treeHeight; ++cLevel)
558 if (nodesInLevel[cLevel] != m_stats.m_nodesInLevel[cLevel])
560 std::cerr <<
"Invalid nodesInLevel information." << std::endl;
564 nodes += m_stats.m_nodesInLevel[cLevel];
567 if (nodes != m_stats.m_nodes)
569 std::cerr <<
"Invalid number of nodes information." << std::endl;
624 var.
m_val.
dblVal == std::numeric_limits<double>::max())
659 throw Tools::IllegalArgumentException(
"initNew: Property NearMinimumOverlapFactor must be Tools::VT_ULONG and less than both index and leaf capacities");
754 m_stats.m_treeHeight = 1;
755 m_stats.m_nodesInLevel.push_back(0);
758 m_rootID = writeNode(&root);
791 var.
m_val.
dblVal == std::numeric_limits<double>::max())
806 throw Tools::IllegalArgumentException(
"initOld: Property NearMinimumOverlapFactor must be Tools::VT_ULONG and less than both index and leaf capacities");
879 void SpatialIndex::TPRTree::TPRTree::storeHeader()
881 const uint32_t headerSize =
897 m_stats.m_treeHeight *
sizeof(uint32_t);
899 uint8_t* header =
new uint8_t[headerSize];
900 uint8_t* ptr = header;
902 memcpy(ptr, &m_rootID,
sizeof(
id_type));
906 memcpy(ptr, &m_fillFactor,
sizeof(
double));
907 ptr +=
sizeof(double);
908 memcpy(ptr, &m_indexCapacity,
sizeof(uint32_t));
909 ptr +=
sizeof(uint32_t);
910 memcpy(ptr, &m_leafCapacity,
sizeof(uint32_t));
911 ptr +=
sizeof(uint32_t);
912 memcpy(ptr, &m_nearMinimumOverlapFactor,
sizeof(uint32_t));
913 ptr +=
sizeof(uint32_t);
914 memcpy(ptr, &m_splitDistributionFactor,
sizeof(
double));
915 ptr +=
sizeof(double);
916 memcpy(ptr, &m_reinsertFactor,
sizeof(
double));
917 ptr +=
sizeof(double);
918 memcpy(ptr, &m_dimension,
sizeof(uint32_t));
919 ptr +=
sizeof(uint32_t);
920 char c = (char) m_bTightMBRs;
921 memcpy(ptr, &c,
sizeof(
char));
923 memcpy(ptr, &(m_stats.m_nodes),
sizeof(uint32_t));
924 ptr +=
sizeof(uint32_t);
925 memcpy(ptr, &(m_stats.m_data),
sizeof(uint64_t));
926 ptr +=
sizeof(uint64_t);
927 memcpy(ptr, &m_currentTime,
sizeof(
double));
928 ptr +=
sizeof(double);
929 memcpy(ptr, &m_horizon,
sizeof(
double));
930 ptr +=
sizeof(double);
931 memcpy(ptr, &(m_stats.m_treeHeight),
sizeof(uint32_t));
932 ptr +=
sizeof(uint32_t);
934 for (uint32_t cLevel = 0; cLevel < m_stats.m_treeHeight; ++cLevel)
936 memcpy(ptr, &(m_stats.m_nodesInLevel[cLevel]),
sizeof(uint32_t));
937 ptr +=
sizeof(uint32_t);
940 m_pStorageManager->
storeByteArray(m_headerID, headerSize, header);
945 void SpatialIndex::TPRTree::TPRTree::loadHeader()
948 uint8_t* header =
nullptr;
949 m_pStorageManager->
loadByteArray(m_headerID, headerSize, &header);
951 uint8_t* ptr = header;
953 memcpy(&m_rootID, ptr,
sizeof(
id_type));
957 memcpy(&m_fillFactor, ptr,
sizeof(
double));
958 ptr +=
sizeof(double);
959 memcpy(&m_indexCapacity, ptr,
sizeof(uint32_t));
960 ptr +=
sizeof(uint32_t);
961 memcpy(&m_leafCapacity, ptr,
sizeof(uint32_t));
962 ptr +=
sizeof(uint32_t);
963 memcpy(&m_nearMinimumOverlapFactor, ptr,
sizeof(uint32_t));
964 ptr +=
sizeof(uint32_t);
965 memcpy(&m_splitDistributionFactor, ptr,
sizeof(
double));
966 ptr +=
sizeof(double);
967 memcpy(&m_reinsertFactor, ptr,
sizeof(
double));
968 ptr +=
sizeof(double);
969 memcpy(&m_dimension, ptr,
sizeof(uint32_t));
970 ptr +=
sizeof(uint32_t);
972 memcpy(&c, ptr,
sizeof(
char));
973 m_bTightMBRs = (c != 0);
975 memcpy(&(m_stats.m_nodes), ptr,
sizeof(uint32_t));
976 ptr +=
sizeof(uint32_t);
977 memcpy(&(m_stats.m_data), ptr,
sizeof(uint64_t));
978 ptr +=
sizeof(uint64_t);
979 memcpy(&m_currentTime, ptr,
sizeof(
double));
980 ptr +=
sizeof(double);
981 memcpy(&m_horizon, ptr,
sizeof(
double));
982 ptr +=
sizeof(double);
983 memcpy(&(m_stats.m_treeHeight), ptr,
sizeof(uint32_t));
984 ptr +=
sizeof(uint32_t);
986 for (uint32_t cLevel = 0; cLevel < m_stats.m_treeHeight; ++cLevel)
989 memcpy(&cNodes, ptr,
sizeof(uint32_t));
990 ptr +=
sizeof(uint32_t);
991 m_stats.m_nodesInLevel.push_back(cNodes);
997 void SpatialIndex::TPRTree::TPRTree::insertData_impl(uint32_t dataLength, uint8_t* pData,
MovingRegion& mr,
id_type id)
1002 std::stack<id_type> pathBuffer;
1003 uint8_t* overflowTable =
nullptr;
1007 NodePtr root = readNode(m_rootID);
1009 overflowTable =
new uint8_t[root->m_level];
1010 memset(overflowTable, 0, root->m_level);
1012 NodePtr l = root->chooseSubtree(mr, 0, pathBuffer);
1013 if (l.
get() == root.
get())
1018 l->insertData(dataLength, pData, mr,
id, pathBuffer, overflowTable);
1020 delete[] overflowTable;
1025 delete[] overflowTable;
1030 void SpatialIndex::TPRTree::TPRTree::insertData_impl(uint32_t dataLength, uint8_t* pData,
MovingRegion& mr,
id_type id, uint32_t level, uint8_t* overflowTable)
1034 std::stack<id_type> pathBuffer;
1035 NodePtr root = readNode(m_rootID);
1036 NodePtr n = root->chooseSubtree(mr, level, pathBuffer);
1038 assert(n->m_level == level);
1040 if (n.
get() == root.
get())
1045 n->insertData(dataLength, pData, mr,
id, pathBuffer, overflowTable);
1052 std::stack<id_type> pathBuffer;
1054 NodePtr root = readNode(m_rootID);
1055 NodePtr l = root->findLeaf(mr,
id, pathBuffer);
1056 if (l.
get() == root.
get())
1062 if (l.
get() !=
nullptr)
1065 pL->deleteData(
id, pathBuffer);
1076 uint32_t dataLength;
1081 else page = n->m_identifier;
1091 std::cerr << e.
what() << std::endl;
1096 if (n->m_identifier < 0)
1098 n->m_identifier = page;
1099 ++(m_stats.m_nodes);
1104 m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel.at(n->m_level) + 1;
1111 m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel[n->m_level] + 1;
1115 ++(m_stats.m_writes);
1117 for (
size_t cIndex = 0; cIndex < m_writeNodeCommands.size(); ++cIndex)
1119 m_writeNodeCommands[cIndex]->execute(*n);
1127 uint32_t dataLength;
1136 std::cerr << e.
what() << std::endl;
1144 memcpy(&nodeType, buffer,
sizeof(uint32_t));
1152 if (n.
get() ==
nullptr)
1159 n->m_identifier = id;
1162 ++(m_stats.m_reads);
1164 for (
size_t cIndex = 0; cIndex < m_readNodeCommands.size(); ++cIndex)
1166 m_readNodeCommands[cIndex]->execute(*n);
1179 void SpatialIndex::TPRTree::TPRTree::deleteNode(
Node* n)
1187 std::cerr << e.
what() << std::endl;
1192 --(m_stats.m_nodes);
1193 m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel[n->m_level] - 1;
1195 for (
size_t cIndex = 0; cIndex < m_deleteNodeCommands.size(); ++cIndex)
1197 m_deleteNodeCommands[cIndex]->execute(*n);
1208 std::stack<NodePtr> st;
1209 NodePtr root = readNode(m_rootID);
1213 while (! st.empty())
1215 NodePtr n = st.top(); st.pop();
1217 if (n->m_level == 0)
1221 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
1229 Data data =
Data(n->m_pDataLength[cChild], n->m_pData[cChild], *(n->m_ptrMBR[cChild]), n->m_pIdentifier[cChild]);
1231 ++(m_stats.m_queryResults);
1239 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
1249 os <<
"Dimension: " << t.m_dimension << std::endl
1250 <<
"Fill factor: " << t.m_fillFactor << std::endl
1251 <<
"Horizon: " << t.m_horizon << std::endl
1252 <<
"Index capacity: " << t.m_indexCapacity << std::endl
1253 <<
"Leaf capacity: " << t.m_leafCapacity << std::endl
1254 <<
"Tight MBRs: " << ((t.m_bTightMBRs) ?
"enabled" :
"disabled") << std::endl;
1258 os <<
"Near minimum overlap factor: " << t.m_nearMinimumOverlapFactor << std::endl
1259 <<
"Reinsert factor: " << t.m_reinsertFactor << std::endl
1260 <<
"Split distribution factor: " << t.m_splitDistributionFactor << std::endl;
1268 os <<
"Leaf pool hits: " << t.m_leafPool.
m_hits << std::endl
1269 <<
"Leaf pool misses: " << t.m_leafPool.
m_misses << std::endl
1270 <<
"Index pool hits: " << t.m_indexPool.
m_hits << std::endl
1271 <<
"Index pool misses: " << t.m_indexPool.
m_misses << std::endl
1272 <<
"Region pool hits: " << t.m_regionPool.
m_hits << std::endl
1273 <<
"Region pool misses: " << t.m_regionPool.
m_misses << std::endl
1274 <<
"Point pool hits: " << t.m_pointPool.m_hits << std::endl
1275 <<
"Point pool misses: " << t.m_pointPool.m_misses << std::endl;
uint64_t getNumberOfData() const override
uint32_t getByteArraySize() override
virtual void selfJoinQuery(const IShape &s, IVisitor &v)
virtual void deleteByteArray(const id_type id)=0
virtual void insertData(uint32_t len, const uint8_t *pData, const IShape &shape, id_type shapeIdentifier)
std::ostream & operator<<(std::ostream &os, const Statistics &s)
void makeDimension(uint32_t dimension) override
virtual bool containsRegionInTime(const MovingRegion &r) const
virtual void containsWhatQuery(const IShape &query, IVisitor &v)
virtual void addCommand(ICommand *pCommand, CommandType ct)
virtual bool deleteData(const IShape &shape, id_type id)
void makeInfinite(uint32_t dimension) override
virtual void nearestNeighborQuery(uint32_t k, const IShape &query, IVisitor &v, INearestNeighborComparator &)
id_type getIdentifier() const override
void storeToByteArray(uint8_t **data, uint32_t &len) override
void storeToByteArray(uint8_t **data, uint32_t &len) override
Data(uint32_t len, uint8_t *pData, MovingRegion &r, id_type id)
virtual void storeByteArray(id_type &id, const uint32_t len, const uint8_t *const data)=0
void loadFromByteArray(const uint8_t *data) override
virtual void loadByteArray(const id_type id, uint32_t &len, uint8_t **data)=0
virtual void getStatistics(IStatistics **out) const
virtual void queryStrategy(IQueryStrategy &qs)
virtual uint32_t getDimension() const =0
void loadFromByteArray(const uint8_t *data) override
virtual void intersectsWithQuery(const IShape &query, IVisitor &v)
virtual void visitNode(const INode &in)=0
void storeToByteArray(uint8_t **data, uint32_t &len) override
virtual void getIndexProperties(Tools::PropertySet &out) const
virtual void visitData(const IData &in)=0
virtual void getVMBR(Region &out) const =0
Tools::PoolPointer< Node > NodePtr
virtual void internalNodesQuery(const IShape &query, IVisitor &v)
void getData(uint32_t &len, uint8_t **data) const override
virtual void pointLocationQuery(const Point &query, IVisitor &v)
uint32_t getDimension() const override
void getShape(IShape **out) const override
SIDX_DLL ISpatialIndex * createNewTPRTree(IStorageManager &sm, double fillFactor, uint32_t indexCapacity, uint32_t leafCapacity, uint32_t dimension, TPRTreeVariant rv, double horizon, id_type &indexIdentifier)
void loadFromByteArray(const uint8_t *data) override
virtual void getMBR(Region &out) const =0
virtual bool isIndexValid()
virtual uint32_t getNumberOfNodesInLevel(uint32_t l) const
virtual void getNextEntry(const IEntry &previouslyFetched, id_type &nextEntryToFetch, bool &bFetchNextEntry)=0
SIDX_DLL ISpatialIndex * loadTPRTree(IStorageManager &in, id_type indexIdentifier)
uint32_t getByteArraySize() override
SIDX_DLL ISpatialIndex * returnTPRTree(IStorageManager &ind, Tools::PropertySet &in)
std::string what() override
TPRTree(IStorageManager &, Tools::PropertySet &)
virtual bool intersectsRegionInTime(const MovingRegion &r) const