libspatialindex API Reference  (git-trunk)
TPRTree.cc
Go to the documentation of this file.
1 /******************************************************************************
2  * Project: libspatialindex - A C++ library for spatial indexing
3  * Author: Marios Hadjieleftheriou, mhadji@gmail.com
4  ******************************************************************************
5  * Copyright (c) 2002, Marios Hadjieleftheriou
6  *
7  * All rights reserved.
8  *
9  * Permission is hereby granted, free of charge, to any person obtaining a
10  * copy of this software and associated documentation files (the "Software"),
11  * to deal in the Software without restriction, including without limitation
12  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
13  * and/or sell copies of the Software, and to permit persons to whom the
14  * Software is furnished to do so, subject to the following conditions:
15  *
16  * The above copyright notice and this permission notice shall be included
17  * in all copies or substantial portions of the Software.
18  *
19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
20  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
22  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25  * DEALINGS IN THE SOFTWARE.
26 ******************************************************************************/
27 
28 #include <limits>
29 
31 #include "Node.h"
32 #include "Leaf.h"
33 #include "Index.h"
34 #include "TPRTree.h"
35 
36 #include <cstring>
37 
38 using namespace SpatialIndex::TPRTree;
39 
40 SpatialIndex::TPRTree::Data::Data(uint32_t len, uint8_t* pData, MovingRegion& r, id_type id)
41  : m_id(id), m_region(r), m_pData(nullptr), m_dataLength(len)
42 {
43  if (m_dataLength > 0)
44  {
45  m_pData = new uint8_t[m_dataLength];
46  memcpy(m_pData, pData, m_dataLength);
47  }
48 }
49 
51 {
52  delete[] m_pData;
53 }
54 
56 {
57  return new Data(m_dataLength, m_pData, m_region, m_id);
58 }
59 
61 {
62  return m_id;
63 }
64 
66 {
67  *out = new MovingRegion(m_region);
68 }
69 
70 void SpatialIndex::TPRTree::Data::getData(uint32_t& len, uint8_t** data) const
71 {
72  len = m_dataLength;
73  *data = nullptr;
74 
75  if (m_dataLength > 0)
76  {
77  *data = new uint8_t[m_dataLength];
78  memcpy(*data, m_pData, m_dataLength);
79  }
80 }
81 
83 {
84  return
85  sizeof(id_type) +
86  sizeof(uint32_t) +
87  m_dataLength +
89 }
90 
92 {
93  memcpy(&m_id, ptr, sizeof(id_type));
94  ptr += sizeof(id_type);
95 
96  delete[] m_pData;
97  m_pData = nullptr;
98 
99  memcpy(&m_dataLength, ptr, sizeof(uint32_t));
100  ptr += sizeof(uint32_t);
101 
102  if (m_dataLength > 0)
103  {
104  m_pData = new uint8_t[m_dataLength];
105  memcpy(m_pData, ptr, m_dataLength);
106  ptr += m_dataLength;
107  }
108 
110 }
111 
112 void SpatialIndex::TPRTree::Data::storeToByteArray(uint8_t** data, uint32_t& len)
113 {
114  // it is thread safe this way.
115  uint32_t regionsize;
116  uint8_t* regiondata = nullptr;
117  m_region.storeToByteArray(&regiondata, regionsize);
118 
119  len = sizeof(id_type) + sizeof(uint32_t) + m_dataLength + regionsize;
120 
121  *data = new uint8_t[len];
122  uint8_t* ptr = *data;
123 
124  memcpy(ptr, &m_id, sizeof(id_type));
125  ptr += sizeof(id_type);
126  memcpy(ptr, &m_dataLength, sizeof(uint32_t));
127  ptr += sizeof(uint32_t);
128 
129  if (m_dataLength > 0)
130  {
131  memcpy(ptr, m_pData, m_dataLength);
132  ptr += m_dataLength;
133  }
134 
135  memcpy(ptr, regiondata, regionsize);
136  delete[] regiondata;
137  // ptr += regionsize;
138 }
139 
141 {
143  return si;
144 }
145 
148  double fillFactor,
149  uint32_t indexCapacity,
150  uint32_t leafCapacity,
151  uint32_t dimension,
152  TPRTreeVariant rv,
153  double horizon,
154  id_type& indexIdentifier)
155 {
156  Tools::Variant var;
158 
160  var.m_val.dblVal = fillFactor;
161  ps.setProperty("FillFactor", var);
162 
164  var.m_val.dblVal = horizon;
165  ps.setProperty("Horizon", var);
166 
168  var.m_val.ulVal = indexCapacity;
169  ps.setProperty("IndexCapacity", var);
170 
172  var.m_val.ulVal = leafCapacity;
173  ps.setProperty("LeafCapacity", var);
174 
176  var.m_val.ulVal = dimension;
177  ps.setProperty("Dimension", var);
178 
180  var.m_val.lVal = rv;
181  ps.setProperty("TreeVariant", var);
182 
183  ISpatialIndex* ret = returnTPRTree(sm, ps);
184 
186  var = ps.getProperty("IndexIdentifier");
187  indexIdentifier = var.m_val.llVal;
188 
189  return ret;
190 }
191 
193 {
194  Tools::Variant var;
196 
198  var.m_val.llVal = indexIdentifier;
199  ps.setProperty("IndexIdentifier", var);
200 
201  return returnTPRTree(sm, ps);
202 }
203 
205  m_pStorageManager(&sm),
206  m_rootID(StorageManager::NewPage),
207  m_headerID(StorageManager::NewPage),
208  m_treeVariant(TPRV_RSTAR),
209  m_fillFactor(0.7),
210  m_indexCapacity(100),
211  m_leafCapacity(100),
212  m_nearMinimumOverlapFactor(32),
213  m_splitDistributionFactor(0.4),
214  m_reinsertFactor(0.3),
215  m_dimension(2),
216  m_bTightMBRs(true),
217  m_currentTime(0.0),
218  m_horizon(20.0),
219  m_pointPool(500),
220  m_regionPool(1000),
221  m_indexPool(100),
222  m_leafPool(100)
223 {
224  Tools::Variant var = ps.getProperty("IndexIdentifier");
225  if (var.m_varType != Tools::VT_EMPTY)
226  {
227  if (var.m_varType == Tools::VT_LONGLONG) m_headerID = var.m_val.llVal;
228  else if (var.m_varType == Tools::VT_LONG) m_headerID = var.m_val.lVal;
229  // for backward compatibility only.
230  else throw Tools::IllegalArgumentException("TPRTree: Property IndexIdentifier must be Tools::VT_LONGLONG");
231 
232  initOld(ps);
233  }
234  else
235  {
236  initNew(ps);
238  var.m_val.llVal = m_headerID;
239  ps.setProperty("IndexIdentifier", var);
240  }
241 }
242 
244 {
245  storeHeader();
246 }
247 
248 //
249 // ISpatialIndex interface
250 //
251 
252 void SpatialIndex::TPRTree::TPRTree::insertData(uint32_t len, const uint8_t* pData, const IShape& shape, id_type id)
253 {
254  if (shape.getDimension() != m_dimension) throw Tools::IllegalArgumentException("insertData: Shape has the wrong number of dimensions.");
255  const IEvolvingShape* es = dynamic_cast<const IEvolvingShape*>(&shape);
256  if (es == nullptr) throw Tools::IllegalArgumentException("insertData: Shape does not support the Tools::IEvolvingShape interface.");
257  const Tools::IInterval *pivI = dynamic_cast<const Tools::IInterval*>(&shape);
258  if (pivI == nullptr) throw Tools::IllegalArgumentException("insertData: Shape does not support the Tools::IInterval interface.");
259 
260  if (pivI->getLowerBound() < m_currentTime) throw Tools::IllegalArgumentException("insertData: Shape start time is older than tree current time.");
261 
262  Region mbr;
263  shape.getMBR(mbr);
264  Region vbr;
265  es->getVMBR(vbr);
266  assert(mbr.m_dimension == vbr.m_dimension);
267 
268  MovingRegionPtr mr = m_regionPool.acquire();
269  mr->makeDimension(mbr.m_dimension);
270 
271  memcpy(mr->m_pLow, mbr.m_pLow, mbr.m_dimension * sizeof(double));
272  memcpy(mr->m_pHigh, mbr.m_pHigh, mbr.m_dimension * sizeof(double));
273  memcpy(mr->m_pVLow, vbr.m_pLow, vbr.m_dimension * sizeof(double));
274  memcpy(mr->m_pVHigh, vbr.m_pHigh, vbr.m_dimension * sizeof(double));
275  mr->m_startTime = pivI->getLowerBound();
276  mr->m_endTime = std::numeric_limits<double>::max();
277 
278  uint8_t* buffer = nullptr;
279 
280  if (len > 0)
281  {
282  buffer = new uint8_t[len];
283  memcpy(buffer, pData, len);
284  }
285 
286  m_currentTime = mr->m_startTime;
287  insertData_impl(len, buffer, *mr, id);
288  // the buffer is stored in the tree. Do not delete here.
289 }
290 
291 // shape.m_startTime should be the time when the object was inserted initially.
292 // shape.m_endTime should be the time of the deletion (current time).
294 {
295  if (shape.getDimension() != m_dimension) throw Tools::IllegalArgumentException("insertData: Shape has the wrong number of dimensions.");
296  const IEvolvingShape* es = dynamic_cast<const IEvolvingShape*>(&shape);
297  if (es == nullptr) throw Tools::IllegalArgumentException("insertData: Shape does not support the Tools::IEvolvingShape interface.");
298  const Tools::IInterval *pivI = dynamic_cast<const Tools::IInterval*>(&shape);
299  if (pivI == nullptr) throw Tools::IllegalArgumentException("insertData: Shape does not support the Tools::IInterval interface.");
300 
301  Region mbr;
302  shape.getMBR(mbr);
303  Region vbr;
304  es->getVMBR(vbr);
305  assert(mbr.m_dimension == vbr.m_dimension);
306 
307  MovingRegionPtr mr = m_regionPool.acquire();
308  mr->makeDimension(mbr.m_dimension);
309 
310  memcpy(mr->m_pLow, mbr.m_pLow, mbr.m_dimension * sizeof(double));
311  memcpy(mr->m_pHigh, mbr.m_pHigh, mbr.m_dimension * sizeof(double));
312  memcpy(mr->m_pVLow, vbr.m_pLow, vbr.m_dimension * sizeof(double));
313  memcpy(mr->m_pVHigh, vbr.m_pHigh, vbr.m_dimension * sizeof(double));
314  mr->m_startTime = pivI->getLowerBound();
315  mr->m_endTime = std::numeric_limits<double>::max();
316 
317  m_currentTime = pivI->getUpperBound();
318  bool ret = deleteData_impl(*mr, id);
319 
320  return ret;
321 }
322 
324 {
325  throw Tools::IllegalStateException("internalNodesQuery: not impelmented yet.");
326 }
327 
329 {
330  if (query.getDimension() != m_dimension) throw Tools::IllegalArgumentException("containsWhatQuery: Shape has the wrong number of dimensions.");
331  rangeQuery(ContainmentQuery, query, v);
332 }
333 
335 {
336  if (query.getDimension() != m_dimension) throw Tools::IllegalArgumentException("intersectsWithQuery: Shape has the wrong number of dimensions.");
337  rangeQuery(IntersectionQuery, query, v);
338 }
339 
341 {
342  if (query.m_dimension != m_dimension) throw Tools::IllegalArgumentException("pointLocationQuery: Shape has the wrong number of dimensions.");
343  Region r(query, query);
344  rangeQuery(IntersectionQuery, r, v);
345 }
346 
348 {
349  throw Tools::IllegalStateException("nearestNeighborQuery: not impelmented yet.");
350 }
351 
353 {
354  if (query.getDimension() != m_dimension) throw Tools::IllegalArgumentException("nearestNeighborQuery: Shape has the wrong number of dimensions.");
355  NNComparator nnc;
356  nearestNeighborQuery(k, query, v, nnc);
357 }
358 
360 {
361  throw Tools::IllegalStateException("selfJoinQuery: not impelmented yet.");
362 }
363 
365 {
366  id_type next = m_rootID;
367  bool hasNext = true;
368 
369  while (hasNext)
370  {
371  NodePtr n = readNode(next);
372  qs.getNextEntry(*n, next, hasNext);
373  }
374 }
375 
377 {
378  Tools::Variant var;
379 
380  // dimension
382  var.m_val.ulVal = m_dimension;
383  out.setProperty("Dimension", var);
384 
385  // index capacity
387  var.m_val.ulVal = m_indexCapacity;
388  out.setProperty("IndexCapacity", var);
389 
390  // leaf capacity
392  var.m_val.ulVal = m_leafCapacity;
393  out.setProperty("LeafCapacity", var);
394 
395  // Tree variant
397  var.m_val.lVal = m_treeVariant;
398  out.setProperty("TreeVariant", var);
399 
400  // fill factor
402  var.m_val.dblVal = m_fillFactor;
403  out.setProperty("FillFactor", var);
404 
405  // horizon
407  var.m_val.dblVal = m_horizon;
408  out.setProperty("Horizon", var);
409 
410  // near minimum overlap factor
412  var.m_val.ulVal = m_nearMinimumOverlapFactor;
413  out.setProperty("NearMinimumOverlapFactor", var);
414 
415  // split distribution factor
417  var.m_val.dblVal = m_splitDistributionFactor;
418  out.setProperty("SplitDistributionFactor", var);
419 
420  // reinsert factor
422  var.m_val.dblVal = m_reinsertFactor;
423  out.setProperty("ReinsertFactor", var);
424 
425  // tight MBRs
427  var.m_val.blVal = m_bTightMBRs;
428  out.setProperty("EnsureTightMBRs", var);
429 
430  // index pool capacity
432  var.m_val.ulVal = m_indexPool.getCapacity();
433  out.setProperty("IndexPoolCapacity", var);
434 
435  // leaf pool capacity
437  var.m_val.ulVal = m_leafPool.getCapacity();
438  out.setProperty("LeafPoolCapacity", var);
439 
440  // region pool capacity
442  var.m_val.ulVal = m_regionPool.getCapacity();
443  out.setProperty("RegionPoolCapacity", var);
444 
445  // point pool capacity
447  var.m_val.ulVal = m_pointPool.getCapacity();
448  out.setProperty("PointPoolCapacity", var);
449 
451  var.m_val.llVal = m_headerID;
452  out.setProperty("IndexIdentifier", var);
453 
454 }
455 
457 {
458  switch (ct)
459  {
460  case CT_NODEREAD:
461  m_readNodeCommands.push_back(std::shared_ptr<ICommand>(pCommand));
462  break;
463  case CT_NODEWRITE:
464  m_writeNodeCommands.push_back(std::shared_ptr<ICommand>(pCommand));
465  break;
466  case CT_NODEDELETE:
467  m_deleteNodeCommands.push_back(std::shared_ptr<ICommand>(pCommand));
468  break;
469  }
470 }
471 
473 {
474  bool ret = true;
475 
476  std::stack<ValidateEntry> st;
477  NodePtr root = readNode(m_rootID);
478 
479  if (root->m_level != m_stats.m_treeHeight - 1)
480  {
481  std::cerr << "Invalid tree height." << std::endl;
482  return false;
483  }
484 
485  std::map<uint32_t, uint32_t> nodesInLevel;
486  nodesInLevel.insert(std::pair<uint32_t, uint32_t>(root->m_level, 1));
487 
488  ValidateEntry e(root->m_nodeMBR, root);
489  st.push(e);
490 
491  while (! st.empty())
492  {
493  e = st.top(); st.pop();
494 
495  MovingRegion tmpRegion;
496  tmpRegion = m_infiniteRegion;
497 
498  // I have to rely on the parent information here, since none of the node's
499  // children might have a reference time equal to their parents (e.g., after
500  // a split).
501  tmpRegion.m_startTime = e.m_parentMBR.m_startTime;
502 
503  for (uint32_t cDim = 0; cDim < tmpRegion.m_dimension; ++cDim)
504  {
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();
509 
510  for (uint32_t cChild = 0; cChild < e.m_pNode->m_children; ++cChild)
511  {
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]);
516  }
517  tmpRegion.m_pLow[cDim] -= 2.0 * std::numeric_limits<double>::epsilon();
518  tmpRegion.m_pHigh[cDim] += 2.0 * std::numeric_limits<double>::epsilon();
519  }
520 
521  if (! (tmpRegion == e.m_pNode->m_nodeMBR))
522  {
523  std::cerr << "Invalid parent information." << std::endl;
524  ret = false;
525  }
526  if (! (tmpRegion == e.m_parentMBR))
527  {
528  std::cerr << "Error in parent." << std::endl;
529  ret = false;
530  }
531 
532  if (e.m_pNode->m_level != 0)
533  {
534  for (uint32_t cChild = 0; cChild < e.m_pNode->m_children; ++cChild)
535  {
536  NodePtr ptrN = readNode(e.m_pNode->m_pIdentifier[cChild]);
537  ValidateEntry tmpEntry(*(e.m_pNode->m_ptrMBR[cChild]), ptrN);
538 
539  auto itNodes = nodesInLevel.find(tmpEntry.m_pNode->m_level);
540 
541  if (itNodes == nodesInLevel.end())
542  {
543  nodesInLevel.insert(std::pair<uint32_t, uint32_t>(tmpEntry.m_pNode->m_level, 1l));
544  }
545  else
546  {
547  nodesInLevel[tmpEntry.m_pNode->m_level] = nodesInLevel[tmpEntry.m_pNode->m_level] + 1;
548  }
549 
550  st.push(tmpEntry);
551  }
552  }
553  }
554 
555  uint32_t nodes = 0;
556  for (uint32_t cLevel = 0; cLevel < m_stats.m_treeHeight; ++cLevel)
557  {
558  if (nodesInLevel[cLevel] != m_stats.m_nodesInLevel[cLevel])
559  {
560  std::cerr << "Invalid nodesInLevel information." << std::endl;
561  ret = false;
562  }
563 
564  nodes += m_stats.m_nodesInLevel[cLevel];
565  }
566 
567  if (nodes != m_stats.m_nodes)
568  {
569  std::cerr << "Invalid number of nodes information." << std::endl;
570  ret = false;
571  }
572 
573  return ret;
574 }
575 
577 {
578  *out = new Statistics(m_stats);
579 }
580 
582 {
583  storeHeader();
584 }
585 
586 void SpatialIndex::TPRTree::TPRTree::initNew(Tools::PropertySet& ps)
587 {
588  Tools::Variant var;
589 
590  // tree variant
591  var = ps.getProperty("TreeVariant");
592  if (var.m_varType != Tools::VT_EMPTY)
593  {
594  if (
595  var.m_varType != Tools::VT_LONG ||
596  (var.m_val.lVal != TPRV_RSTAR))
597  throw Tools::IllegalArgumentException("initNew: Property TreeVariant must be Tools::VT_LONG and of TPRTreeVariant type");
598 
599  m_treeVariant = static_cast<TPRTreeVariant>(var.m_val.lVal);
600  }
601 
602  // fill factor
603  // it cannot be larger than 50%, since linear and quadratic split algorithms
604  // require assigning to both nodes the same number of entries.
605  var = ps.getProperty("FillFactor");
606  if (var.m_varType != Tools::VT_EMPTY)
607  {
608  if (
609  var.m_varType != Tools::VT_DOUBLE ||
610  var.m_val.dblVal <= 0.0 ||
611  var.m_val.dblVal >= 1.0)
612  throw Tools::IllegalArgumentException("initNew: Property FillFactor must be Tools::VT_DOUBLE and in (0.0, 1.0) for RSTAR");
613 
614  m_fillFactor = var.m_val.dblVal;
615  }
616 
617  // horizon
618  var = ps.getProperty("Horizon");
619  if (var.m_varType != Tools::VT_EMPTY)
620  {
621  if (
622  var.m_varType != Tools::VT_DOUBLE ||
623  var.m_val.dblVal <= 0.0 ||
624  var.m_val.dblVal == std::numeric_limits<double>::max())
625  throw Tools::IllegalArgumentException("initNew: Property Horizon must be Tools::VT_DOUBLE and a positive constant");
626 
627  m_horizon = var.m_val.dblVal;
628  }
629 
630  // index capacity
631  var = ps.getProperty("IndexCapacity");
632  if (var.m_varType != Tools::VT_EMPTY)
633  {
634  if (var.m_varType != Tools::VT_ULONG || var.m_val.ulVal < 4)
635  throw Tools::IllegalArgumentException("initNew: Property IndexCapacity must be Tools::VT_ULONG and >= 4");
636 
637  m_indexCapacity = var.m_val.ulVal;
638  }
639 
640  // leaf capacity
641  var = ps.getProperty("LeafCapacity");
642  if (var.m_varType != Tools::VT_EMPTY)
643  {
644  if (var.m_varType != Tools::VT_ULONG || var.m_val.ulVal < 4)
645  throw Tools::IllegalArgumentException("initNew: Property LeafCapacity must be Tools::VT_ULONG and >= 4");
646 
647  m_leafCapacity = var.m_val.ulVal;
648  }
649 
650  // near minimum overlap factor
651  var = ps.getProperty("NearMinimumOverlapFactor");
652  if (var.m_varType != Tools::VT_EMPTY)
653  {
654  if (
655  var.m_varType != Tools::VT_ULONG ||
656  var.m_val.ulVal < 1 ||
657  var.m_val.ulVal > m_indexCapacity ||
658  var.m_val.ulVal > m_leafCapacity)
659  throw Tools::IllegalArgumentException("initNew: Property NearMinimumOverlapFactor must be Tools::VT_ULONG and less than both index and leaf capacities");
660 
661  m_nearMinimumOverlapFactor = var.m_val.ulVal;
662  }
663 
664  // split distribution factor
665  var = ps.getProperty("SplitDistributionFactor");
666  if (var.m_varType != Tools::VT_EMPTY)
667  {
668  if (
669  var.m_varType != Tools::VT_DOUBLE ||
670  var.m_val.dblVal <= 0.0 ||
671  var.m_val.dblVal >= 1.0)
672  throw Tools::IllegalArgumentException("initNew: Property SplitDistributionFactor must be Tools::VT_DOUBLE and in (0.0, 1.0)");
673 
674  m_splitDistributionFactor = var.m_val.dblVal;
675  }
676 
677  // reinsert factor
678  var = ps.getProperty("ReinsertFactor");
679  if (var.m_varType != Tools::VT_EMPTY)
680  {
681  if (
682  var.m_varType != Tools::VT_DOUBLE ||
683  var.m_val.dblVal <= 0.0 ||
684  var.m_val.dblVal >= 1.0)
685  throw Tools::IllegalArgumentException("initNew: Property ReinsertFactor must be Tools::VT_DOUBLE and in (0.0, 1.0)");
686 
687  m_reinsertFactor = var.m_val.dblVal;
688  }
689 
690  // dimension
691  var = ps.getProperty("Dimension");
692  if (var.m_varType != Tools::VT_EMPTY)
693  {
694  if (var.m_varType != Tools::VT_ULONG)
695  throw Tools::IllegalArgumentException("initNew: Property Dimension must be Tools::VT_ULONG");
696  if (var.m_val.ulVal <= 1)
697  throw Tools::IllegalArgumentException("initNew: Property Dimension must be greater than 1");
698 
699  m_dimension = var.m_val.ulVal;
700  }
701 
702  // tight MBRs
703  var = ps.getProperty("EnsureTightMBRs");
704  if (var.m_varType != Tools::VT_EMPTY)
705  {
706  if (var.m_varType != Tools::VT_BOOL)
707  throw Tools::IllegalArgumentException("initNew: Property EnsureTightMBRs must be Tools::VT_BOOL");
708 
709  m_bTightMBRs = var.m_val.blVal;
710  }
711 
712  // index pool capacity
713  var = ps.getProperty("IndexPoolCapacity");
714  if (var.m_varType != Tools::VT_EMPTY)
715  {
716  if (var.m_varType != Tools::VT_ULONG)
717  throw Tools::IllegalArgumentException("initNew: Property IndexPoolCapacity must be Tools::VT_ULONG");
718 
719  m_indexPool.setCapacity(var.m_val.ulVal);
720  }
721 
722  // leaf pool capacity
723  var = ps.getProperty("LeafPoolCapacity");
724  if (var.m_varType != Tools::VT_EMPTY)
725  {
726  if (var.m_varType != Tools::VT_ULONG)
727  throw Tools::IllegalArgumentException("initNew: Property LeafPoolCapacity must be Tools::VT_ULONG");
728 
729  m_leafPool.setCapacity(var.m_val.ulVal);
730  }
731 
732  // region pool capacity
733  var = ps.getProperty("RegionPoolCapacity");
734  if (var.m_varType != Tools::VT_EMPTY)
735  {
736  if (var.m_varType != Tools::VT_ULONG)
737  throw Tools::IllegalArgumentException("initNew: Property RegionPoolCapacity must be Tools::VT_ULONG");
738 
739  m_regionPool.setCapacity(var.m_val.ulVal);
740  }
741 
742  // point pool capacity
743  var = ps.getProperty("PointPoolCapacity");
744  if (var.m_varType != Tools::VT_EMPTY)
745  {
746  if (var.m_varType != Tools::VT_ULONG)
747  throw Tools::IllegalArgumentException("initNew: Property PointPoolCapacity must be Tools::VT_ULONG");
748 
749  m_pointPool.setCapacity(var.m_val.ulVal);
750  }
751 
752  m_infiniteRegion.makeInfinite(m_dimension);
753 
754  m_stats.m_treeHeight = 1;
755  m_stats.m_nodesInLevel.push_back(0);
756 
757  Leaf root(this, -1);
758  m_rootID = writeNode(&root);
759 
760  storeHeader();
761 }
762 
763 void SpatialIndex::TPRTree::TPRTree::initOld(Tools::PropertySet& ps)
764 {
765  loadHeader();
766 
767  // only some of the properties may be changed.
768  // the rest are just ignored.
769 
770  Tools::Variant var;
771 
772  // tree variant
773  var = ps.getProperty("TreeVariant");
774  if (var.m_varType != Tools::VT_EMPTY)
775  {
776  if (
777  var.m_varType != Tools::VT_LONG ||
778  (var.m_val.lVal != TPRV_RSTAR))
779  throw Tools::IllegalArgumentException("initOld: Property TreeVariant must be Tools::VT_LONG and of TPRTreeVariant type");
780 
781  m_treeVariant = static_cast<TPRTreeVariant>(var.m_val.lVal);
782  }
783 
784  // horizon
785  var = ps.getProperty("Horizon");
786  if (var.m_varType != Tools::VT_EMPTY)
787  {
788  if (
789  var.m_varType != Tools::VT_DOUBLE ||
790  var.m_val.dblVal <= 0.0 ||
791  var.m_val.dblVal == std::numeric_limits<double>::max())
792  throw Tools::IllegalArgumentException("initOld: Property Horizon must be Tools::VT_DOUBLE and a positive constant");
793 
794  m_horizon = var.m_val.dblVal;
795  }
796 
797  // near minimum overlap factor
798  var = ps.getProperty("NearMinimumOverlapFactor");
799  if (var.m_varType != Tools::VT_EMPTY)
800  {
801  if (
802  var.m_varType != Tools::VT_ULONG ||
803  var.m_val.ulVal < 1 ||
804  var.m_val.ulVal > m_indexCapacity ||
805  var.m_val.ulVal > m_leafCapacity)
806  throw Tools::IllegalArgumentException("initOld: Property NearMinimumOverlapFactor must be Tools::VT_ULONG and less than both index and leaf capacities");
807 
808  m_nearMinimumOverlapFactor = var.m_val.ulVal;
809  }
810 
811  // split distribution factor
812  var = ps.getProperty("SplitDistributionFactor");
813  if (var.m_varType != Tools::VT_EMPTY)
814  {
815  if (var.m_varType != Tools::VT_DOUBLE || var.m_val.dblVal <= 0.0 || var.m_val.dblVal >= 1.0)
816  throw Tools::IllegalArgumentException("initOld: Property SplitDistributionFactor must be Tools::VT_DOUBLE and in (0.0, 1.0)");
817 
818  m_splitDistributionFactor = var.m_val.dblVal;
819  }
820 
821  // reinsert factor
822  var = ps.getProperty("ReinsertFactor");
823  if (var.m_varType != Tools::VT_EMPTY)
824  {
825  if (var.m_varType != Tools::VT_DOUBLE || var.m_val.dblVal <= 0.0 || var.m_val.dblVal >= 1.0)
826  throw Tools::IllegalArgumentException("initOld: Property ReinsertFactor must be Tools::VT_DOUBLE and in (0.0, 1.0)");
827 
828  m_reinsertFactor = var.m_val.dblVal;
829  }
830 
831  // tight MBRs
832  var = ps.getProperty("EnsureTightMBRs");
833  if (var.m_varType != Tools::VT_EMPTY)
834  {
835  if (var.m_varType != Tools::VT_BOOL) throw Tools::IllegalArgumentException("initOld: Property EnsureTightMBRs must be Tools::VT_BOOL");
836 
837  m_bTightMBRs = var.m_val.blVal;
838  }
839 
840  // index pool capacity
841  var = ps.getProperty("IndexPoolCapacity");
842  if (var.m_varType != Tools::VT_EMPTY)
843  {
844  if (var.m_varType != Tools::VT_ULONG) throw Tools::IllegalArgumentException("initOld: Property IndexPoolCapacity must be Tools::VT_ULONG");
845 
846  m_indexPool.setCapacity(var.m_val.ulVal);
847  }
848 
849  // leaf pool capacity
850  var = ps.getProperty("LeafPoolCapacity");
851  if (var.m_varType != Tools::VT_EMPTY)
852  {
853  if (var.m_varType != Tools::VT_ULONG) throw Tools::IllegalArgumentException("initOld: Property LeafPoolCapacity must be Tools::VT_ULONG");
854 
855  m_leafPool.setCapacity(var.m_val.ulVal);
856  }
857 
858  // region pool capacity
859  var = ps.getProperty("RegionPoolCapacity");
860  if (var.m_varType != Tools::VT_EMPTY)
861  {
862  if (var.m_varType != Tools::VT_ULONG) throw Tools::IllegalArgumentException("initOld: Property RegionPoolCapacity must be Tools::VT_ULONG");
863 
864  m_regionPool.setCapacity(var.m_val.ulVal);
865  }
866 
867  // point pool capacity
868  var = ps.getProperty("PointPoolCapacity");
869  if (var.m_varType != Tools::VT_EMPTY)
870  {
871  if (var.m_varType != Tools::VT_ULONG) throw Tools::IllegalArgumentException("initOld: Property PointPoolCapacity must be Tools::VT_ULONG");
872 
873  m_pointPool.setCapacity(var.m_val.ulVal);
874  }
875 
876  m_infiniteRegion.makeInfinite(m_dimension);
877 }
878 
879 void SpatialIndex::TPRTree::TPRTree::storeHeader()
880 {
881  const uint32_t headerSize =
882  sizeof(id_type) + // m_rootID
883  sizeof(TPRTreeVariant) + // m_treeVariant
884  sizeof(double) + // m_fillFactor
885  sizeof(uint32_t) + // m_indexCapacity
886  sizeof(uint32_t) + // m_leafCapacity
887  sizeof(uint32_t) + // m_nearMinimumOverlapFactor
888  sizeof(double) + // m_splitDistributionFactor
889  sizeof(double) + // m_reinsertFactor
890  sizeof(uint32_t) + // m_dimension
891  sizeof(char) + // m_bTightMBRs
892  sizeof(uint32_t) + // m_stats.m_nodes
893  sizeof(uint64_t) + // m_stats.m_data
894  sizeof(double) + // m_currentTime
895  sizeof(double) + // m_horizon
896  sizeof(uint32_t) + // m_stats.m_treeHeight
897  m_stats.m_treeHeight * sizeof(uint32_t);// m_stats.m_nodesInLevel
898 
899  uint8_t* header = new uint8_t[headerSize];
900  uint8_t* ptr = header;
901 
902  memcpy(ptr, &m_rootID, sizeof(id_type));
903  ptr += sizeof(id_type);
904  memcpy(ptr, &m_treeVariant, sizeof(TPRTreeVariant));
905  ptr += sizeof(TPRTreeVariant);
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));
922  ptr += 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);
933 
934  for (uint32_t cLevel = 0; cLevel < m_stats.m_treeHeight; ++cLevel)
935  {
936  memcpy(ptr, &(m_stats.m_nodesInLevel[cLevel]), sizeof(uint32_t));
937  ptr += sizeof(uint32_t);
938  }
939 
940  m_pStorageManager->storeByteArray(m_headerID, headerSize, header);
941 
942  delete[] header;
943 }
944 
945 void SpatialIndex::TPRTree::TPRTree::loadHeader()
946 {
947  uint32_t headerSize;
948  uint8_t* header = nullptr;
949  m_pStorageManager->loadByteArray(m_headerID, headerSize, &header);
950 
951  uint8_t* ptr = header;
952 
953  memcpy(&m_rootID, ptr, sizeof(id_type));
954  ptr += sizeof(id_type);
955  memcpy(&m_treeVariant, ptr, sizeof(TPRTreeVariant));
956  ptr += sizeof(TPRTreeVariant);
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);
971  char c;
972  memcpy(&c, ptr, sizeof(char));
973  m_bTightMBRs = (c != 0);
974  ptr += sizeof(char);
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);
985 
986  for (uint32_t cLevel = 0; cLevel < m_stats.m_treeHeight; ++cLevel)
987  {
988  uint32_t cNodes;
989  memcpy(&cNodes, ptr, sizeof(uint32_t));
990  ptr += sizeof(uint32_t);
991  m_stats.m_nodesInLevel.push_back(cNodes);
992  }
993 
994  delete[] header;
995 }
996 
997 void SpatialIndex::TPRTree::TPRTree::insertData_impl(uint32_t dataLength, uint8_t* pData, MovingRegion& mr, id_type id)
998 {
999  assert(mr.getDimension() == m_dimension);
1000  assert(m_currentTime <= mr.m_startTime);
1001 
1002  std::stack<id_type> pathBuffer;
1003  uint8_t* overflowTable = nullptr;
1004 
1005  try
1006  {
1007  NodePtr root = readNode(m_rootID);
1008 
1009  overflowTable = new uint8_t[root->m_level];
1010  memset(overflowTable, 0, root->m_level);
1011 
1012  NodePtr l = root->chooseSubtree(mr, 0, pathBuffer);
1013  if (l.get() == root.get())
1014  {
1015  assert(root.unique());
1016  root.relinquish();
1017  }
1018  l->insertData(dataLength, pData, mr, id, pathBuffer, overflowTable);
1019 
1020  delete[] overflowTable;
1021  ++(m_stats.m_data);
1022  }
1023  catch (...)
1024  {
1025  delete[] overflowTable;
1026  throw;
1027  }
1028 }
1029 
1030 void SpatialIndex::TPRTree::TPRTree::insertData_impl(uint32_t dataLength, uint8_t* pData, MovingRegion& mr, id_type id, uint32_t level, uint8_t* overflowTable)
1031 {
1032  assert(mr.getDimension() == m_dimension);
1033 
1034  std::stack<id_type> pathBuffer;
1035  NodePtr root = readNode(m_rootID);
1036  NodePtr n = root->chooseSubtree(mr, level, pathBuffer);
1037 
1038  assert(n->m_level == level);
1039 
1040  if (n.get() == root.get())
1041  {
1042  assert(root.unique());
1043  root.relinquish();
1044  }
1045  n->insertData(dataLength, pData, mr, id, pathBuffer, overflowTable);
1046 }
1047 
1048 bool SpatialIndex::TPRTree::TPRTree::deleteData_impl(const MovingRegion& mr, id_type id)
1049 {
1050  assert(mr.m_dimension == m_dimension);
1051 
1052  std::stack<id_type> pathBuffer;
1053 
1054  NodePtr root = readNode(m_rootID);
1055  NodePtr l = root->findLeaf(mr, id, pathBuffer);
1056  if (l.get() == root.get())
1057  {
1058  assert(root.unique());
1059  root.relinquish();
1060  }
1061 
1062  if (l.get() != nullptr)
1063  {
1064  Leaf* pL = static_cast<Leaf*>(l.get());
1065  pL->deleteData(id, pathBuffer);
1066  --(m_stats.m_data);
1067  return true;
1068  }
1069 
1070  return false;
1071 }
1072 
1073 SpatialIndex::id_type SpatialIndex::TPRTree::TPRTree::writeNode(Node* n)
1074 {
1075  uint8_t* buffer;
1076  uint32_t dataLength;
1077  n->storeToByteArray(&buffer, dataLength);
1078 
1079  id_type page;
1080  if (n->m_identifier < 0) page = StorageManager::NewPage;
1081  else page = n->m_identifier;
1082 
1083  try
1084  {
1085  m_pStorageManager->storeByteArray(page, dataLength, buffer);
1086  delete[] buffer;
1087  }
1088  catch (InvalidPageException& e)
1089  {
1090  delete[] buffer;
1091  std::cerr << e.what() << std::endl;
1092  //std::cerr << *this << std::endl;
1093  throw Tools::IllegalStateException("writeNode: failed with Tools::InvalidPageException");
1094  }
1095 
1096  if (n->m_identifier < 0)
1097  {
1098  n->m_identifier = page;
1099  ++(m_stats.m_nodes);
1100 
1101 #ifndef NDEBUG
1102  try
1103  {
1104  m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel.at(n->m_level) + 1;
1105  }
1106  catch(...)
1107  {
1108  throw Tools::IllegalStateException("writeNode: writing past the end of m_nodesInLevel.");
1109  }
1110 #else
1111  m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel[n->m_level] + 1;
1112 #endif
1113  }
1114 
1115  ++(m_stats.m_writes);
1116 
1117  for (size_t cIndex = 0; cIndex < m_writeNodeCommands.size(); ++cIndex)
1118  {
1119  m_writeNodeCommands[cIndex]->execute(*n);
1120  }
1121 
1122  return page;
1123 }
1124 
1125 SpatialIndex::TPRTree::NodePtr SpatialIndex::TPRTree::TPRTree::readNode(id_type id)
1126 {
1127  uint32_t dataLength;
1128  uint8_t* buffer;
1129 
1130  try
1131  {
1132  m_pStorageManager->loadByteArray(id, dataLength, &buffer);
1133  }
1134  catch (InvalidPageException& e)
1135  {
1136  std::cerr << e.what() << std::endl;
1137  //std::cerr << *this << std::endl;
1138  throw Tools::IllegalStateException("readNode: failed with Tools::InvalidPageException");
1139  }
1140 
1141  try
1142  {
1143  uint32_t nodeType;
1144  memcpy(&nodeType, buffer, sizeof(uint32_t));
1145 
1146  NodePtr n;
1147 
1148  if (nodeType == PersistentIndex) n = m_indexPool.acquire();
1149  else if (nodeType == PersistentLeaf) n = m_leafPool.acquire();
1150  else throw Tools::IllegalStateException("readNode: failed reading the correct node type information");
1151 
1152  if (n.get() == nullptr)
1153  {
1154  if (nodeType == PersistentIndex) n = NodePtr(new Index(this, -1, 0), &m_indexPool);
1155  else if (nodeType == PersistentLeaf) n = NodePtr(new Leaf(this, -1), &m_leafPool);
1156  }
1157 
1158  //n->m_pTree = this;
1159  n->m_identifier = id;
1160  n->loadFromByteArray(buffer);
1161 
1162  ++(m_stats.m_reads);
1163 
1164  for (size_t cIndex = 0; cIndex < m_readNodeCommands.size(); ++cIndex)
1165  {
1166  m_readNodeCommands[cIndex]->execute(*n);
1167  }
1168 
1169  delete[] buffer;
1170  return n;
1171  }
1172  catch (...)
1173  {
1174  delete[] buffer;
1175  throw;
1176  }
1177 }
1178 
1179 void SpatialIndex::TPRTree::TPRTree::deleteNode(Node* n)
1180 {
1181  try
1182  {
1183  m_pStorageManager->deleteByteArray(n->m_identifier);
1184  }
1185  catch (InvalidPageException& e)
1186  {
1187  std::cerr << e.what() << std::endl;
1188  //std::cerr << *this << std::endl;
1189  throw Tools::IllegalStateException("deleteNode: failed with Tools::InvalidPageException");
1190  }
1191 
1192  --(m_stats.m_nodes);
1193  m_stats.m_nodesInLevel[n->m_level] = m_stats.m_nodesInLevel[n->m_level] - 1;
1194 
1195  for (size_t cIndex = 0; cIndex < m_deleteNodeCommands.size(); ++cIndex)
1196  {
1197  m_deleteNodeCommands[cIndex]->execute(*n);
1198  }
1199 }
1200 
1201 void SpatialIndex::TPRTree::TPRTree::rangeQuery(RangeQueryType type, const IShape& query, IVisitor& v)
1202 {
1203  const MovingRegion* mr = dynamic_cast<const MovingRegion*>(&query);
1204  if (mr == nullptr) throw Tools::IllegalArgumentException("rangeQuery: Shape has to be a moving region.");
1205  if (mr->m_startTime < m_currentTime || mr->m_endTime >= m_currentTime + m_horizon)
1206  throw Tools::IllegalArgumentException("rangeQuery: Query time interval does not intersect current horizon.");
1207 
1208  std::stack<NodePtr> st;
1209  NodePtr root = readNode(m_rootID);
1210 
1211  if (root->m_children > 0 && mr->intersectsRegionInTime(root->m_nodeMBR)) st.push(root);
1212 
1213  while (! st.empty())
1214  {
1215  NodePtr n = st.top(); st.pop();
1216 
1217  if (n->m_level == 0)
1218  {
1219  v.visitNode(*n);
1220 
1221  for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
1222  {
1223  bool b;
1224  if (type == ContainmentQuery) b = mr->containsRegionInTime(*(n->m_ptrMBR[cChild]));
1225  else b = mr->intersectsRegionInTime(*(n->m_ptrMBR[cChild]));
1226 
1227  if (b)
1228  {
1229  Data data = Data(n->m_pDataLength[cChild], n->m_pData[cChild], *(n->m_ptrMBR[cChild]), n->m_pIdentifier[cChild]);
1230  v.visitData(data);
1231  ++(m_stats.m_queryResults);
1232  }
1233  }
1234  }
1235  else
1236  {
1237  v.visitNode(*n);
1238 
1239  for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
1240  {
1241  if (mr->intersectsRegionInTime(*(n->m_ptrMBR[cChild]))) st.push(readNode(n->m_pIdentifier[cChild]));
1242  }
1243  }
1244  }
1245 }
1246 
1247 std::ostream& SpatialIndex::TPRTree::operator<<(std::ostream& os, const TPRTree& t)
1248 {
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;
1255 
1256  if (t.m_treeVariant == TPRV_RSTAR)
1257  {
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;
1261  }
1262 
1263  if (t.m_stats.getNumberOfNodesInLevel(0) > 0)
1264  os << "Utilization: " << 100 * t.m_stats.getNumberOfData() / (t.m_stats.getNumberOfNodesInLevel(0) * t.m_leafCapacity) << "%" << std::endl
1265  << t.m_stats;
1266 
1267  #ifndef NDEBUG
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;
1276  #endif
1277 
1278  return os;
1279 }
uint64_t getNumberOfData() const override
uint32_t getByteArraySize() override
Definition: TPRTree.cc:82
virtual void selfJoinQuery(const IShape &s, IVisitor &v)
Definition: TPRTree.cc:359
virtual void deleteByteArray(const id_type id)=0
VariantType m_varType
Definition: Tools.h:277
uint32_t ulVal
Definition: Tools.h:289
virtual void insertData(uint32_t len, const uint8_t *pData, const IShape &shape, id_type shapeIdentifier)
Definition: TPRTree.cc:252
void setProperty(std::string property, Variant const &v)
Definition: Tools.cc:354
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)
Definition: TPRTree.cc:328
virtual void addCommand(ICommand *pCommand, CommandType ct)
Definition: TPRTree.cc:456
virtual bool deleteData(const IShape &shape, id_type id)
Definition: TPRTree.cc:293
Data * clone() override
Definition: TPRTree.cc:55
void makeInfinite(uint32_t dimension) override
PoolPointer< X > acquire()
Definition: PointerPool.h:64
virtual double getLowerBound() const =0
virtual void nearestNeighborQuery(uint32_t k, const IShape &query, IVisitor &v, INearestNeighborComparator &)
Definition: TPRTree.cc:347
id_type getIdentifier() const override
Definition: TPRTree.cc:60
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)
Definition: TPRTree.cc:40
virtual void storeByteArray(id_type &id, const uint32_t len, const uint8_t *const data)=0
double * m_pLow
Definition: Region.h:98
uint32_t m_dimension
Definition: Point.h:77
void loadFromByteArray(const uint8_t *data) override
Definition: tprtree/Node.cc:64
virtual void loadByteArray(const id_type id, uint32_t &len, uint8_t **data)=0
virtual void getStatistics(IStatistics **out) const
Definition: TPRTree.cc:576
virtual void queryStrategy(IQueryStrategy &qs)
Definition: TPRTree.cc:364
virtual uint32_t getDimension() const =0
void loadFromByteArray(const uint8_t *data) override
Definition: TPRTree.cc:91
virtual void intersectsWithQuery(const IShape &query, IVisitor &v)
Definition: TPRTree.cc:334
union Tools::Variant::@0 m_val
virtual void visitNode(const INode &in)=0
int64_t llVal
Definition: Tools.h:283
void storeToByteArray(uint8_t **data, uint32_t &len) override
Definition: TPRTree.cc:112
virtual void getIndexProperties(Tools::PropertySet &out) const
Definition: TPRTree.cc:376
uint32_t m_dimension
Definition: Region.h:97
double * m_pHigh
Definition: Region.h:99
bool unique() const noexcept
Definition: PoolPointer.h:56
X * get() const noexcept
Definition: PoolPointer.h:55
virtual void visitData(const IData &in)=0
virtual void getVMBR(Region &out) const =0
Tools::PoolPointer< Node > NodePtr
Definition: tprtree/Node.h:39
virtual void internalNodesQuery(const IShape &query, IVisitor &v)
Definition: TPRTree.cc:323
void getData(uint32_t &len, uint8_t **data) const override
Definition: TPRTree.cc:70
virtual void pointLocationQuery(const Point &query, IVisitor &v)
Definition: TPRTree.cc:340
uint32_t getDimension() const override
Definition: Region.cc:229
void setCapacity(uint32_t c)
Definition: PointerPool.h:105
void getShape(IShape **out) const override
Definition: TPRTree.cc:65
int32_t lVal
Definition: Tools.h:282
SIDX_DLL ISpatialIndex * createNewTPRTree(IStorageManager &sm, double fillFactor, uint32_t indexCapacity, uint32_t leafCapacity, uint32_t dimension, TPRTreeVariant rv, double horizon, id_type &indexIdentifier)
Definition: TPRTree.cc:146
void loadFromByteArray(const uint8_t *data) override
double dblVal
Definition: Tools.h:286
virtual void getMBR(Region &out) const =0
uint32_t getCapacity() const
Definition: PointerPool.h:104
virtual bool isIndexValid()
Definition: TPRTree.cc:472
int64_t id_type
Definition: SpatialIndex.h:41
Variant getProperty(std::string property) const
Definition: Tools.cc:346
virtual uint32_t getNumberOfNodesInLevel(uint32_t l) const
bool blVal
Definition: Tools.h:291
virtual void getNextEntry(const IEntry &previouslyFetched, id_type &nextEntryToFetch, bool &bFetchNextEntry)=0
SIDX_DLL ISpatialIndex * loadTPRTree(IStorageManager &in, id_type indexIdentifier)
Definition: TPRTree.cc:192
uint32_t getByteArraySize() override
SIDX_DLL ISpatialIndex * returnTPRTree(IStorageManager &ind, Tools::PropertySet &in)
Definition: TPRTree.cc:140
void relinquish() noexcept
Definition: PoolPointer.h:57
TPRTree(IStorageManager &, Tools::PropertySet &)
Definition: TPRTree.cc:204
virtual double getUpperBound() const =0
virtual bool intersectsRegionInTime(const MovingRegion &r) const