← Back to branch summary

~ubuntu-branches/ubuntu/utopic/qgis/utopic

« back to all changes in this revision

Viewing changes to src/core/spatialindex/rtree/Node.cc

  • Committer: Bazaar Package Importer
  • Author(s): Johan Van de Wauw
  • Date: 2010-07-11 20:23:24 UTC
  • mfrom: (3.1.4 squeeze)
  • Revision ID: james.westby@ubuntu.com-20100711202324-5ktghxa7hracohmr
Tags: 1.4.0+12730-3ubuntu1
https://launchpad.net/bugs/540941
* Merge from Debian unstable (LP: #540941).
* Fix compilation issues with QT 4.7
* Add build-depends on libqt4-webkit-dev 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/spatialindex/rtree/Node.cc
 
1
// Spatial Index Library
 
2
//
 
3
// Copyright (C) 2002 Navel Ltd.
 
4
//
 
5
// This library is free software; you can redistribute it and/or
 
6
// modify it under the terms of the GNU Lesser General Public
 
7
// License as published by the Free Software Foundation; either
 
8
// version 2.1 of the License, or (at your option) any later version.
 
9
//
 
10
// This library is distributed in the hope that it will be useful,
 
11
// but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
13
// Lesser General Public License for more details.
 
14
//
 
15
// You should have received a copy of the GNU Lesser General Public
 
16
// License along with this library; if not, write to the Free Software
 
17
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
18
//
 
19
//  Email:
 
20
//    mhadji@gmail.com
 
21
 
 
22
#include "../spatialindex/SpatialIndexImpl.h"
 
23
 
 
24
#include "RTree.h"
 
25
#include "Node.h"
 
26
#include "Index.h"
 
27
 
 
28
using std::stack;
 
29
using std::vector;
 
30
using namespace SpatialIndex::RTree;
 
31
 
 
32
//
 
33
// Tools::IObject interface
 
34
//
 
35
Tools::IObject* Node::clone()
 
36
{
 
37
  throw Tools::NotSupportedException( "IObject::clone should never be called." );
 
38
}
 
39
 
 
40
//
 
41
// Tools::ISerializable interface
 
42
//
 
43
unsigned long Node::getByteArraySize()
 
44
{
 
45
  return
 
46
    ( sizeof( long ) +
 
47
      sizeof( long ) +
 
48
      sizeof( long ) +
 
49
      ( m_children *( m_pTree->m_dimension * sizeof( double ) * 2 + sizeof( long ) + sizeof( unsigned long ) ) ) +
 
50
      m_totalDataLength +
 
51
      ( 2 * m_pTree->m_dimension * sizeof( double ) ) );
 
52
}
 
53
 
 
54
void Node::loadFromByteArray( const byte* ptr )
 
55
{
 
56
  m_nodeMBR = m_pTree->m_infiniteRegion;
 
57
 
 
58
  // skip the node type information, it is not needed.
 
59
  ptr += sizeof( long );
 
60
 
 
61
  memcpy( &m_level, ptr, sizeof( long ) );
 
62
  ptr += sizeof( long );
 
63
 
 
64
  memcpy( &m_children, ptr, sizeof( long ) );
 
65
  ptr += sizeof( long );
 
66
 
 
67
  for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
 
68
  {
 
69
    m_ptrMBR[cChild] = m_pTree->m_regionPool.acquire();
 
70
    *( m_ptrMBR[cChild] ) = m_pTree->m_infiniteRegion;
 
71
 
 
72
    memcpy( m_ptrMBR[cChild]->m_pLow, ptr, m_pTree->m_dimension * sizeof( double ) );
 
73
    ptr += m_pTree->m_dimension * sizeof( double );
 
74
    memcpy( m_ptrMBR[cChild]->m_pHigh, ptr, m_pTree->m_dimension * sizeof( double ) );
 
75
    ptr += m_pTree->m_dimension * sizeof( double );
 
76
    memcpy( &( m_pIdentifier[cChild] ), ptr, sizeof( long ) );
 
77
    ptr += sizeof( long );
 
78
 
 
79
    memcpy( &( m_pDataLength[cChild] ), ptr, sizeof( unsigned long ) );
 
80
    ptr += sizeof( unsigned long );
 
81
 
 
82
    if ( m_pDataLength[cChild] > 0 )
 
83
    {
 
84
      m_totalDataLength += m_pDataLength[cChild];
 
85
      m_pData[cChild] = new byte[m_pDataLength[cChild]];
 
86
      memcpy( m_pData[cChild], ptr, m_pDataLength[cChild] );
 
87
      ptr += m_pDataLength[cChild];
 
88
    }
 
89
    else
 
90
    {
 
91
      m_pData[cChild] = 0;
 
92
    }
 
93
 
 
94
    //m_nodeMBR.combineRegion(*(m_ptrMBR[cChild]));
 
95
  }
 
96
 
 
97
  memcpy( m_nodeMBR.m_pLow, ptr, m_pTree->m_dimension * sizeof( double ) );
 
98
  ptr += m_pTree->m_dimension * sizeof( double );
 
99
  memcpy( m_nodeMBR.m_pHigh, ptr, m_pTree->m_dimension * sizeof( double ) );
 
100
  //ptr += m_pTree->m_dimension * sizeof(double);
 
101
}
 
102
 
 
103
void Node::storeToByteArray( byte** data, unsigned long& len )
 
104
{
 
105
  len = getByteArraySize();
 
106
 
 
107
  *data = new byte[len];
 
108
  byte* ptr = *data;
 
109
 
 
110
  long type;
 
111
 
 
112
  if ( m_level == 0 ) type = PersistentLeaf;
 
113
  else type = PersistentIndex;
 
114
 
 
115
  memcpy( ptr, &type, sizeof( long ) );
 
116
  ptr += sizeof( long );
 
117
 
 
118
  memcpy( ptr, &m_level, sizeof( long ) );
 
119
  ptr += sizeof( long );
 
120
 
 
121
  memcpy( ptr, &m_children, sizeof( long ) );
 
122
  ptr += sizeof( long );
 
123
 
 
124
  for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
 
125
  {
 
126
    memcpy( ptr, m_ptrMBR[cChild]->m_pLow, m_pTree->m_dimension * sizeof( double ) );
 
127
    ptr += m_pTree->m_dimension * sizeof( double );
 
128
    memcpy( ptr, m_ptrMBR[cChild]->m_pHigh, m_pTree->m_dimension * sizeof( double ) );
 
129
    ptr += m_pTree->m_dimension * sizeof( double );
 
130
    memcpy( ptr, &( m_pIdentifier[cChild] ), sizeof( long ) );
 
131
    ptr += sizeof( long );
 
132
 
 
133
    memcpy( ptr, &( m_pDataLength[cChild] ), sizeof( unsigned long ) );
 
134
    ptr += sizeof( unsigned long );
 
135
 
 
136
    if ( m_pDataLength[cChild] > 0 )
 
137
    {
 
138
      memcpy( ptr, m_pData[cChild], m_pDataLength[cChild] );
 
139
      ptr += m_pDataLength[cChild];
 
140
    }
 
141
  }
 
142
 
 
143
  // store the node MBR for efficiency. This increases the node size a little bit.
 
144
  memcpy( ptr, m_nodeMBR.m_pLow, m_pTree->m_dimension * sizeof( double ) );
 
145
  ptr += m_pTree->m_dimension * sizeof( double );
 
146
  memcpy( ptr, m_nodeMBR.m_pHigh, m_pTree->m_dimension * sizeof( double ) );
 
147
  //ptr += m_pTree->m_dimension * sizeof(double);
 
148
 
 
149
  assert( len == ( ptr - *data ) + m_pTree->m_dimension * sizeof( double ) );
 
150
}
 
151
 
 
152
//
 
153
// SpatialIndex::IEntry interface
 
154
//
 
155
long Node::getIdentifier() const
 
156
{
 
157
  return m_identifier;
 
158
}
 
159
 
 
160
void Node::getShape( IShape** out ) const
 
161
{
 
162
  *out = new Region( m_nodeMBR );
 
163
}
 
164
 
 
165
//
 
166
// SpatialIndex::INode interface
 
167
//
 
168
unsigned long Node::getChildrenCount() const
 
169
{
 
170
  return m_children;
 
171
}
 
172
 
 
173
long Node::getChildIdentifier( unsigned long index ) const
 
174
{
 
175
  if ( index < 0 || index >= m_children ) throw Tools::IndexOutOfBoundsException( index );
 
176
 
 
177
  return m_pIdentifier[index];
 
178
}
 
179
 
 
180
void Node::getChildShape( unsigned long index, IShape** out ) const
 
181
{
 
182
  if ( index < 0 || index >= m_children ) throw Tools::IndexOutOfBoundsException( index );
 
183
 
 
184
  *out = new Region( *( m_ptrMBR[index] ) );
 
185
}
 
186
 
 
187
unsigned long Node::getLevel() const
 
188
{
 
189
  return m_level;
 
190
}
 
191
 
 
192
bool Node::isLeaf() const
 
193
{
 
194
  return ( m_level == 0 );
 
195
}
 
196
 
 
197
bool Node::isIndex() const
 
198
{
 
199
  return ( m_level != 0 );
 
200
}
 
201
 
 
202
//
 
203
// Internal
 
204
//
 
205
 
 
206
Node::Node() :
 
207
    m_pTree( 0 ),
 
208
    m_level( 0 ),
 
209
    m_identifier( -1 ),
 
210
    m_children( 0 ),
 
211
    m_capacity( 0 ),
 
212
    m_pData( 0 ),
 
213
    m_ptrMBR( 0 ),
 
214
    m_pIdentifier( 0 ),
 
215
    m_pDataLength( 0 ),
 
216
    m_totalDataLength( 0 )
 
217
{
 
218
}
 
219
 
 
220
#ifdef _MSC_VER
 
221
// MSVC seems to find RTree* pTree ambiguous
 
222
Node::Node( SpatialIndex::RTree::RTree* pTree, long id, unsigned long level, unsigned long capacity ) :
 
223
#else
 
224
Node::Node( RTree* pTree, long id, unsigned long level, unsigned long capacity ) :
 
225
#endif//_MSC_VER
 
226
    m_pTree( pTree ),
 
227
    m_level( level ),
 
228
    m_identifier( id ),
 
229
    m_children( 0 ),
 
230
    m_capacity( capacity ),
 
231
    m_pData( 0 ),
 
232
    m_ptrMBR( 0 ),
 
233
    m_pIdentifier( 0 ),
 
234
    m_pDataLength( 0 ),
 
235
    m_totalDataLength( 0 )
 
236
{
 
237
  m_nodeMBR.makeInfinite( m_pTree->m_dimension );
 
238
 
 
239
  try
 
240
  {
 
241
    m_pDataLength = new unsigned long[m_capacity + 1];
 
242
    m_pData = new byte*[m_capacity + 1];
 
243
    m_ptrMBR = new RegionPtr[m_capacity + 1];
 
244
    m_pIdentifier = new long[m_capacity + 1];
 
245
  }
 
246
  catch ( ... )
 
247
  {
 
248
    delete[] m_pDataLength;
 
249
    delete[] m_pData;
 
250
    delete[] m_ptrMBR;
 
251
    delete[] m_pIdentifier;
 
252
    throw;
 
253
  }
 
254
}
 
255
 
 
256
Node::~Node()
 
257
{
 
258
  if ( m_pData != 0 )
 
259
  {
 
260
    for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
 
261
    {
 
262
      if ( m_pData[cChild] != 0 ) delete[] m_pData[cChild];
 
263
    }
 
264
 
 
265
    delete[] m_pData;
 
266
  }
 
267
 
 
268
  delete[] m_pDataLength;
 
269
  delete[] m_ptrMBR;
 
270
  delete[] m_pIdentifier;
 
271
}
 
272
 
 
273
Node& Node::operator=( const Node & n )
 
274
{
 
275
  throw Tools::IllegalStateException( "operator =: This should never be called." );
 
276
}
 
277
 
 
278
void Node::insertEntry( unsigned long dataLength, byte* pData, Region& mbr, long id )
 
279
{
 
280
  assert( m_children < m_capacity );
 
281
 
 
282
  m_pDataLength[m_children] = dataLength;
 
283
  m_pData[m_children] = pData;
 
284
  m_ptrMBR[m_children] = m_pTree->m_regionPool.acquire();
 
285
  *( m_ptrMBR[m_children] ) = mbr;
 
286
  m_pIdentifier[m_children] = id;
 
287
 
 
288
  m_totalDataLength += dataLength;
 
289
  m_children++;
 
290
 
 
291
  m_nodeMBR.combineRegion( mbr );
 
292
}
 
293
 
 
294
void Node::deleteEntry( unsigned long index )
 
295
{
 
296
  assert( index >= 0 && index < m_children );
 
297
 
 
298
  // cache it, since I might need it for "touches" later.
 
299
  RegionPtr ptrR = m_ptrMBR[index];
 
300
 
 
301
  m_totalDataLength -= m_pDataLength[index];
 
302
  if ( m_pData[index] != 0 ) delete[] m_pData[index];
 
303
 
 
304
  if ( m_children > 1 && index != m_children - 1 )
 
305
  {
 
306
    m_pDataLength[index] = m_pDataLength[m_children - 1];
 
307
    m_pData[index] = m_pData[m_children - 1];
 
308
    m_ptrMBR[index] = m_ptrMBR[m_children - 1];
 
309
    m_pIdentifier[index] = m_pIdentifier[m_children - 1];
 
310
  }
 
311
 
 
312
  m_children--;
 
313
 
 
314
  // WARNING: index has now changed. Do not use it below here.
 
315
 
 
316
  if ( m_children == 0 )
 
317
  {
 
318
    m_nodeMBR = m_pTree->m_infiniteRegion;
 
319
  }
 
320
  else if ( m_pTree->m_bTightMBRs && m_nodeMBR.touchesRegion( *ptrR ) )
 
321
  {
 
322
    for ( unsigned long cDim = 0; cDim < m_nodeMBR.m_dimension; cDim++ )
 
323
    {
 
324
      m_nodeMBR.m_pLow[cDim] = std::numeric_limits<double>::max();
 
325
      m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();
 
326
 
 
327
      for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
 
328
      {
 
329
        m_nodeMBR.m_pLow[cDim] = std::min( m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->m_pLow[cDim] );
 
330
        m_nodeMBR.m_pHigh[cDim] = std::max( m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->m_pHigh[cDim] );
 
331
      }
 
332
    }
 
333
  }
 
334
}
 
335
 
 
336
bool Node::insertData( unsigned long dataLength, byte* pData, Region& mbr, long id, stack<long>& pathBuffer, byte* overflowTable )
 
337
{
 
338
  if ( m_children < m_capacity )
 
339
  {
 
340
    bool adjusted = false;
 
341
 
 
342
    // this has to happen before insertEntry modifies m_nodeMBR.
 
343
    bool b = m_nodeMBR.containsRegion( mbr );
 
344
 
 
345
    insertEntry( dataLength, pData, mbr, id );
 
346
    m_pTree->writeNode( this );
 
347
 
 
348
    if (( ! b ) && ( ! pathBuffer.empty() ) )
 
349
    {
 
350
      long cParent = pathBuffer.top(); pathBuffer.pop();
 
351
      NodePtr ptrN = m_pTree->readNode( cParent );
 
352
      Index* p = static_cast<Index*>( ptrN.get() );
 
353
      p->adjustTree( this, pathBuffer );
 
354
      adjusted = true;
 
355
    }
 
356
 
 
357
    return adjusted;
 
358
  }
 
359
  else if ( m_pTree->m_treeVariant == RV_RSTAR && ( ! pathBuffer.empty() ) && overflowTable[m_level] == 0 )
 
360
  {
 
361
    overflowTable[m_level] = 1;
 
362
 
 
363
    vector<long> vReinsert, vKeep;
 
364
    reinsertData( dataLength, pData, mbr, id, vReinsert, vKeep );
 
365
 
 
366
    unsigned long lReinsert = vReinsert.size();
 
367
    unsigned long lKeep = vKeep.size();
 
368
 
 
369
    byte** reinsertdata = 0;
 
370
    RegionPtr* reinsertmbr = 0;
 
371
    long* reinsertid = 0;
 
372
    unsigned long* reinsertlen = 0;
 
373
    byte** keepdata = 0;
 
374
    RegionPtr* keepmbr = 0;
 
375
    long* keepid = 0;
 
376
    unsigned long* keeplen = 0;
 
377
 
 
378
    try
 
379
    {
 
380
      reinsertdata = new byte*[lReinsert];
 
381
      reinsertmbr = new RegionPtr[lReinsert];
 
382
      reinsertid = new long[lReinsert];
 
383
      reinsertlen = new unsigned long[lReinsert];
 
384
 
 
385
      keepdata = new byte*[m_capacity + 1];
 
386
      keepmbr = new RegionPtr[m_capacity + 1];
 
387
      keepid = new long[m_capacity + 1];
 
388
      keeplen = new unsigned long[m_capacity + 1];
 
389
    }
 
390
    catch ( ... )
 
391
    {
 
392
      delete[] reinsertdata;
 
393
      delete[] reinsertmbr;
 
394
      delete[] reinsertid;
 
395
      delete[] reinsertlen;
 
396
      delete[] keepdata;
 
397
      delete[] keepmbr;
 
398
      delete[] keepid;
 
399
      delete[] keeplen;
 
400
      throw;
 
401
    }
 
402
 
 
403
    unsigned long cIndex;
 
404
 
 
405
    for ( cIndex = 0; cIndex < lReinsert; cIndex++ )
 
406
    {
 
407
      reinsertlen[cIndex] = m_pDataLength[vReinsert[cIndex]];
 
408
      reinsertdata[cIndex] = m_pData[vReinsert[cIndex]];
 
409
      reinsertmbr[cIndex] = m_ptrMBR[vReinsert[cIndex]];
 
410
      reinsertid[cIndex] = m_pIdentifier[vReinsert[cIndex]];
 
411
    }
 
412
 
 
413
    for ( cIndex = 0; cIndex < lKeep; cIndex++ )
 
414
    {
 
415
      keeplen[cIndex] = m_pDataLength[vKeep[cIndex]];
 
416
      keepdata[cIndex] = m_pData[vKeep[cIndex]];
 
417
      keepmbr[cIndex] = m_ptrMBR[vKeep[cIndex]];
 
418
      keepid[cIndex] = m_pIdentifier[vKeep[cIndex]];
 
419
    }
 
420
 
 
421
    delete[] m_pDataLength;
 
422
    delete[] m_pData;
 
423
    delete[] m_ptrMBR;
 
424
    delete[] m_pIdentifier;
 
425
 
 
426
    m_pDataLength = keeplen;
 
427
    m_pData = keepdata;
 
428
    m_ptrMBR = keepmbr;
 
429
    m_pIdentifier = keepid;
 
430
    m_children = lKeep;
 
431
    m_totalDataLength = 0;
 
432
 
 
433
    for ( unsigned long cChild = 0; cChild < m_children; cChild++ ) m_totalDataLength += m_pDataLength[cChild];
 
434
 
 
435
    for ( unsigned long cDim = 0; cDim < m_nodeMBR.m_dimension; cDim++ )
 
436
    {
 
437
      m_nodeMBR.m_pLow[cDim] = std::numeric_limits<double>::max();
 
438
      m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();
 
439
 
 
440
      for ( unsigned long cChild = 0; cChild < m_children; cChild++ )
 
441
      {
 
442
        m_nodeMBR.m_pLow[cDim] = std::min( m_nodeMBR.m_pLow[cDim], m_ptrMBR[cChild]->m_pLow[cDim] );
 
443
        m_nodeMBR.m_pHigh[cDim] = std::max( m_nodeMBR.m_pHigh[cDim], m_ptrMBR[cChild]->m_pHigh[cDim] );
 
444
      }
 
445
    }
 
446
 
 
447
    m_pTree->writeNode( this );
 
448
 
 
449
    // Divertion from R*-Tree algorithm here. First adjust
 
450
    // the path to the root, then start reinserts, to avoid complicated handling
 
451
    // of changes to the same node from multiple insertions.
 
452
    long cParent = pathBuffer.top(); pathBuffer.pop();
 
453
    NodePtr ptrN = m_pTree->readNode( cParent );
 
454
    Index* p = static_cast<Index*>( ptrN.get() );
 
455
    p->adjustTree( this, pathBuffer );
 
456
 
 
457
    for ( cIndex = 0; cIndex < lReinsert; cIndex++ )
 
458
    {
 
459
      m_pTree->insertData_impl(
 
460
        reinsertlen[cIndex], reinsertdata[cIndex],
 
461
        *( reinsertmbr[cIndex] ), reinsertid[cIndex],
 
462
        m_level, overflowTable );
 
463
    }
 
464
 
 
465
    delete[] reinsertdata;
 
466
    delete[] reinsertmbr;
 
467
    delete[] reinsertid;
 
468
    delete[] reinsertlen;
 
469
 
 
470
    return true;
 
471
  }
 
472
  else
 
473
  {
 
474
    NodePtr n;
 
475
    NodePtr nn;
 
476
    split( dataLength, pData, mbr, id, n, nn );
 
477
 
 
478
    if ( pathBuffer.empty() )
 
479
    {
 
480
      n->m_level = m_level;
 
481
      nn->m_level = m_level;
 
482
      n->m_identifier = -1;
 
483
      nn->m_identifier = -1;
 
484
      m_pTree->writeNode( n.get() );
 
485
      m_pTree->writeNode( nn.get() );
 
486
 
 
487
      NodePtr ptrR = m_pTree->m_indexPool.acquire();
 
488
      if ( ptrR.get() == 0 )
 
489
      {
 
490
        ptrR = NodePtr( new Index( m_pTree, m_pTree->m_rootID, m_level + 1 ), &( m_pTree->m_indexPool ) );
 
491
      }
 
492
      else
 
493
      {
 
494
        //ptrR->m_pTree = m_pTree;
 
495
        ptrR->m_identifier = m_pTree->m_rootID;
 
496
        ptrR->m_level = m_level + 1;
 
497
        ptrR->m_nodeMBR = m_pTree->m_infiniteRegion;
 
498
      }
 
499
 
 
500
      ptrR->insertEntry( 0, 0, n->m_nodeMBR, n->m_identifier );
 
501
      ptrR->insertEntry( 0, 0, nn->m_nodeMBR, nn->m_identifier );
 
502
 
 
503
      m_pTree->writeNode( ptrR.get() );
 
504
 
 
505
      m_pTree->m_stats.m_nodesInLevel[m_level] = 2;
 
506
      m_pTree->m_stats.m_nodesInLevel.push_back( 1 );
 
507
      m_pTree->m_stats.m_treeHeight = m_level + 2;
 
508
    }
 
509
    else
 
510
    {
 
511
      n->m_level = m_level;
 
512
      nn->m_level = m_level;
 
513
      n->m_identifier = m_identifier;
 
514
      nn->m_identifier = -1;
 
515
 
 
516
      m_pTree->writeNode( n.get() );
 
517
      m_pTree->writeNode( nn.get() );
 
518
 
 
519
      long cParent = pathBuffer.top(); pathBuffer.pop();
 
520
      NodePtr ptrN = m_pTree->readNode( cParent );
 
521
      Index* p = static_cast<Index*>( ptrN.get() );
 
522
      p->adjustTree( n.get(), nn.get(), pathBuffer, overflowTable );
 
523
    }
 
524
 
 
525
    return true;
 
526
  }
 
527
}
 
528
 
 
529
void Node::reinsertData( unsigned long dataLength, byte* pData, Region& mbr, long id, vector<long>& reinsert, vector<long>& keep )
 
530
{
 
531
  ReinsertEntry** v = new ReinsertEntry*[m_capacity + 1];
 
532
 
 
533
  m_pDataLength[m_children] = dataLength;
 
534
  m_pData[m_children] = pData;
 
535
  m_ptrMBR[m_children] = m_pTree->m_regionPool.acquire();
 
536
  *( m_ptrMBR[m_children] ) = mbr;
 
537
  m_pIdentifier[m_children] = id;
 
538
 
 
539
  PointPtr nc = m_pTree->m_pointPool.acquire();
 
540
  m_nodeMBR.getCenter( *nc );
 
541
  PointPtr c = m_pTree->m_pointPool.acquire();
 
542
 
 
543
  for ( unsigned long cChild = 0; cChild < m_capacity + 1; cChild++ )
 
544
  {
 
545
    try
 
546
    {
 
547
      v[cChild] = new ReinsertEntry( cChild, 0.0 );
 
548
    }
 
549
    catch ( ... )
 
550
    {
 
551
      for ( unsigned long i = 0; i < cChild; i++ ) delete v[i];
 
552
      delete[] v;
 
553
      throw;
 
554
    }
 
555
 
 
556
    m_ptrMBR[cChild]->getCenter( *c );
 
557
 
 
558
    // calculate relative distance of every entry from the node MBR (ignore square root.)
 
559
    for ( unsigned long cDim = 0; cDim < m_nodeMBR.m_dimension; cDim++ )
 
560
    {
 
561
      double d = nc->m_pCoords[cDim] - c->m_pCoords[cDim];
 
562
      v[cChild]->m_dist += d * d;
 
563
    }
 
564
  }
 
565
 
 
566
  // sort by increasing order of distances.
 
567
  ::qsort( v, m_capacity + 1, sizeof( ReinsertEntry* ), ReinsertEntry::compareReinsertEntry );
 
568
 
 
569
  unsigned long cReinsert = ( unsigned long ) std::floor(( m_capacity + 1 ) * m_pTree->m_reinsertFactor );
 
570
 
 
571
  unsigned long cCount;
 
572
 
 
573
  for ( cCount = 0; cCount < cReinsert; cCount++ )
 
574
  {
 
575
    reinsert.push_back( v[cCount]->m_id );
 
576
    delete v[cCount];
 
577
  }
 
578
 
 
579
  for ( cCount = cReinsert; cCount < m_capacity + 1; cCount++ )
 
580
  {
 
581
    keep.push_back( v[cCount]->m_id );
 
582
    delete v[cCount];
 
583
  }
 
584
 
 
585
  delete[] v;
 
586
}
 
587
 
 
588
void Node::rtreeSplit( unsigned long dataLength, byte* pData, Region& mbr, long id, vector<long>& group1, vector<long>& group2 )
 
589
{
 
590
  unsigned long cChild;
 
591
  unsigned long minimumLoad = static_cast<unsigned long>( std::floor( m_capacity * m_pTree->m_fillFactor ) );
 
592
 
 
593
  // use this mask array for marking visited entries.
 
594
  byte* mask = new byte[m_capacity + 1];
 
595
  memset( mask, 0, m_capacity + 1 );
 
596
 
 
597
  // insert new data in the node for easier manipulation. Data arrays are always
 
598
  // by one larger than node capacity.
 
599
  m_pDataLength[m_capacity] = dataLength;
 
600
  m_pData[m_capacity] = pData;
 
601
  m_ptrMBR[m_capacity] = m_pTree->m_regionPool.acquire();
 
602
  *( m_ptrMBR[m_capacity] ) = mbr;
 
603
  m_pIdentifier[m_capacity] = id;
 
604
  // m_totalDataLength does not need to be increased here.
 
605
 
 
606
  // initialize each group with the seed entries.
 
607
  unsigned long seed1, seed2;
 
608
  pickSeeds( seed1, seed2 );
 
609
 
 
610
  group1.push_back( seed1 );
 
611
  group2.push_back( seed2 );
 
612
 
 
613
  mask[seed1] = 1;
 
614
  mask[seed2] = 1;
 
615
 
 
616
  // find MBR of each group.
 
617
  RegionPtr mbr1 = m_pTree->m_regionPool.acquire();
 
618
  *mbr1 = *( m_ptrMBR[seed1] );
 
619
  RegionPtr mbr2 = m_pTree->m_regionPool.acquire();
 
620
  *mbr2 = *( m_ptrMBR[seed2] );
 
621
 
 
622
  // count how many entries are left unchecked (exclude the seeds here.)
 
623
  unsigned long cRemaining = m_capacity + 1 - 2;
 
624
 
 
625
  while ( cRemaining > 0 )
 
626
  {
 
627
    if ( minimumLoad - group1.size() == cRemaining )
 
628
    {
 
629
      // all remaining entries must be assigned to group1 to comply with minimun load requirement.
 
630
      for ( cChild = 0; cChild < m_capacity + 1; cChild++ )
 
631
      {
 
632
        if ( mask[cChild] == 0 )
 
633
        {
 
634
          group1.push_back( cChild );
 
635
          mask[cChild] = 1;
 
636
          cRemaining--;
 
637
        }
 
638
      }
 
639
    }
 
640
    else if ( minimumLoad - group2.size() == cRemaining )
 
641
    {
 
642
      // all remaining entries must be assigned to group2 to comply with minimun load requirement.
 
643
      for ( cChild = 0; cChild < m_capacity + 1; cChild++ )
 
644
      {
 
645
        if ( mask[cChild] == 0 )
 
646
        {
 
647
          group2.push_back( cChild );
 
648
          mask[cChild] = 1;
 
649
          cRemaining--;
 
650
        }
 
651
      }
 
652
    }
 
653
    else
 
654
    {
 
655
      // For all remaining entries compute the difference of the cost of grouping an
 
656
      // entry in either group. When done, choose the entry that yielded the maximum
 
657
      // difference. In case of linear split, select any entry (e.g. the first one.)
 
658
      long sel = -1;
 
659
      double md1 = 0.0, md2 = 0.0;
 
660
      double m = -std::numeric_limits<double>::max();
 
661
      double d1, d2, d;
 
662
      double a1 = mbr1->getArea();
 
663
      double a2 = mbr2->getArea();
 
664
 
 
665
      RegionPtr a = m_pTree->m_regionPool.acquire();
 
666
      RegionPtr b = m_pTree->m_regionPool.acquire();
 
667
 
 
668
      for ( cChild = 0; cChild < m_capacity + 1; cChild++ )
 
669
      {
 
670
        if ( mask[cChild] == 0 )
 
671
        {
 
672
          mbr1->getCombinedRegion( *a, *( m_ptrMBR[cChild] ) );
 
673
          d1 = a->getArea() - a1;
 
674
          mbr2->getCombinedRegion( *b, *( m_ptrMBR[cChild] ) );
 
675
          d2 = b->getArea() - a2;
 
676
          d = std::abs( d1 - d2 );
 
677
 
 
678
          if ( d > m )
 
679
          {
 
680
            m = d;
 
681
            md1 = d1; md2 = d2;
 
682
            sel = cChild;
 
683
            if ( m_pTree->m_treeVariant == RV_LINEAR || m_pTree->m_treeVariant == RV_RSTAR ) break;
 
684
          }
 
685
        }
 
686
      }
 
687
 
 
688
      // determine the group where we should add the new entry.
 
689
      long group = -1;
 
690
 
 
691
      if ( md1 < md2 )
 
692
      {
 
693
        group1.push_back( sel );
 
694
        group = 1;
 
695
      }
 
696
      else if ( md2 < md1 )
 
697
      {
 
698
        group2.push_back( sel );
 
699
        group = 2;
 
700
      }
 
701
      else if ( a1 < a2 )
 
702
      {
 
703
        group1.push_back( sel );
 
704
        group = 1;
 
705
      }
 
706
      else if ( a2 < a1 )
 
707
      {
 
708
        group2.push_back( sel );
 
709
        group = 2;
 
710
      }
 
711
      else if ( group1.size() < group2.size() )
 
712
      {
 
713
        group1.push_back( sel );
 
714
        group = 1;
 
715
      }
 
716
      else if ( group2.size() < group1.size() )
 
717
      {
 
718
        group2.push_back( sel );
 
719
        group = 2;
 
720
      }
 
721
      else
 
722
      {
 
723
        group1.push_back( sel );
 
724
        group = 1;
 
725
      }
 
726
      mask[sel] = 1;
 
727
      cRemaining--;
 
728
      if ( group == 1 )
 
729
      {
 
730
        mbr1->combineRegion( *( m_ptrMBR[sel] ) );
 
731
      }
 
732
      else
 
733
      {
 
734
        mbr2->combineRegion( *( m_ptrMBR[sel] ) );
 
735
      }
 
736
    }
 
737
  }
 
738
 
 
739
  delete[] mask;
 
740
}
 
741
 
 
742
void Node::rstarSplit( unsigned long dataLength, byte* pData, Region& mbr, long id, std::vector<long>& group1, std::vector<long>& group2 )
 
743
{
 
744
  RstarSplitEntry** dataLow = 0;
 
745
  RstarSplitEntry** dataHigh = 0;
 
746
 
 
747
  try
 
748
  {
 
749
    dataLow = new RstarSplitEntry*[m_capacity + 1];
 
750
    dataHigh = new RstarSplitEntry*[m_capacity + 1];
 
751
  }
 
752
  catch ( ... )
 
753
  {
 
754
    delete[] dataLow;
 
755
    throw;
 
756
  }
 
757
 
 
758
  m_pDataLength[m_capacity] = dataLength;
 
759
  m_pData[m_capacity] = pData;
 
760
  m_ptrMBR[m_capacity] = m_pTree->m_regionPool.acquire();
 
761
  *( m_ptrMBR[m_capacity] ) = mbr;
 
762
  m_pIdentifier[m_capacity] = id;
 
763
  // m_totalDataLength does not need to be increased here.
 
764
 
 
765
  unsigned long nodeSPF = static_cast<unsigned long>( std::floor(( m_capacity + 1 ) * m_pTree->m_splitDistributionFactor ) );
 
766
  unsigned long splitDistribution = ( m_capacity + 1 ) - ( 2 * nodeSPF ) + 2;
 
767
 
 
768
  unsigned long cChild = 0, cDim, cIndex;
 
769
 
 
770
  for ( cChild = 0; cChild <= m_capacity; cChild++ )
 
771
  {
 
772
    try
 
773
    {
 
774
      dataLow[cChild] = new RstarSplitEntry( m_ptrMBR[cChild].get(), cChild, 0 );
 
775
    }
 
776
    catch ( ... )
 
777
    {
 
778
      for ( unsigned long i = 0; i < cChild; i++ ) delete dataLow[i];
 
779
      delete[] dataLow;
 
780
      delete[] dataHigh;
 
781
      throw;
 
782
    }
 
783
 
 
784
    dataHigh[cChild] = dataLow[cChild];
 
785
  }
 
786
 
 
787
  double minimumMargin = std::numeric_limits<double>::max();
 
788
  long splitAxis = -1;
 
789
  long sortOrder = -1;
 
790
 
 
791
  // chooseSplitAxis.
 
792
  for ( cDim = 0; cDim < m_pTree->m_dimension; cDim++ )
 
793
  {
 
794
    ::qsort( dataLow, m_capacity + 1, sizeof( RstarSplitEntry* ), RstarSplitEntry::compareLow );
 
795
    ::qsort( dataHigh, m_capacity + 1, sizeof( RstarSplitEntry* ), RstarSplitEntry::compareHigh );
 
796
 
 
797
    // calculate sum of margins and overlap for all distributions.
 
798
    double marginl = 0.0;
 
799
    double marginh = 0.0;
 
800
 
 
801
    Region bbl1, bbl2, bbh1, bbh2;
 
802
 
 
803
    for ( cChild = 1; cChild <= splitDistribution; cChild++ )
 
804
    {
 
805
      unsigned long l = nodeSPF - 1 + cChild;
 
806
 
 
807
      bbl1 = *( dataLow[0]->m_pRegion );
 
808
      bbh1 = *( dataHigh[0]->m_pRegion );
 
809
 
 
810
      for ( cIndex = 1; cIndex < l; cIndex++ )
 
811
      {
 
812
        bbl1.combineRegion( *( dataLow[cIndex]->m_pRegion ) );
 
813
        bbh1.combineRegion( *( dataHigh[cIndex]->m_pRegion ) );
 
814
      }
 
815
 
 
816
      bbl2 = *( dataLow[l]->m_pRegion );
 
817
      bbh2 = *( dataHigh[l]->m_pRegion );
 
818
 
 
819
      for ( cIndex = l + 1; cIndex <= m_capacity; cIndex++ )
 
820
      {
 
821
        bbl2.combineRegion( *( dataLow[cIndex]->m_pRegion ) );
 
822
        bbh2.combineRegion( *( dataHigh[cIndex]->m_pRegion ) );
 
823
      }
 
824
 
 
825
      marginl += bbl1.getMargin() + bbl2.getMargin();
 
826
      marginh += bbh1.getMargin() + bbh2.getMargin();
 
827
    } // for (cChild)
 
828
 
 
829
    double margin = std::min( marginl, marginh );
 
830
 
 
831
    // keep minimum margin as split axis.
 
832
    if ( margin < minimumMargin )
 
833
    {
 
834
      minimumMargin = margin;
 
835
      splitAxis = cDim;
 
836
      sortOrder = ( marginl < marginh ) ? 0 : 1;
 
837
    }
 
838
 
 
839
    // increase the dimension according to which the data entries should be sorted.
 
840
    for ( cChild = 0; cChild <= m_capacity; cChild++ )
 
841
    {
 
842
      dataLow[cChild]->m_sortDim = cDim + 1;
 
843
    }
 
844
  } // for (cDim)
 
845
 
 
846
  for ( cChild = 0; cChild <= m_capacity; cChild++ )
 
847
  {
 
848
    dataLow[cChild]->m_sortDim = splitAxis;
 
849
  }
 
850
 
 
851
  ::qsort( dataLow, m_capacity + 1, sizeof( RstarSplitEntry* ), ( sortOrder == 0 ) ? RstarSplitEntry::compareLow : RstarSplitEntry::compareHigh );
 
852
 
 
853
  double ma = std::numeric_limits<double>::max();
 
854
  double mo = std::numeric_limits<double>::max();
 
855
  long splitPoint = -1;
 
856
 
 
857
  Region bb1, bb2;
 
858
 
 
859
  for ( cChild = 1; cChild <= splitDistribution; cChild++ )
 
860
  {
 
861
    unsigned long l = nodeSPF - 1 + cChild;
 
862
 
 
863
    bb1 = *( dataLow[0]->m_pRegion );
 
864
 
 
865
    for ( cIndex = 1; cIndex < l; cIndex++ )
 
866
    {
 
867
      bb1.combineRegion( *( dataLow[cIndex]->m_pRegion ) );
 
868
    }
 
869
 
 
870
    bb2 = *( dataLow[l]->m_pRegion );
 
871
 
 
872
    for ( cIndex = l + 1; cIndex <= m_capacity; cIndex++ )
 
873
    {
 
874
      bb2.combineRegion( *( dataLow[cIndex]->m_pRegion ) );
 
875
    }
 
876
 
 
877
    double o = bb1.getIntersectingArea( bb2 );
 
878
 
 
879
    if ( o < mo )
 
880
    {
 
881
      splitPoint = cChild;
 
882
      mo = o;
 
883
      ma = bb1.getArea() + bb2.getArea();
 
884
    }
 
885
    else if ( o == mo )
 
886
    {
 
887
      double a = bb1.getArea() + bb2.getArea();
 
888
 
 
889
      if ( a < ma )
 
890
      {
 
891
        splitPoint = cChild;
 
892
        ma = a;
 
893
      }
 
894
    }
 
895
  } // for (cChild)
 
896
 
 
897
  unsigned long l1 = nodeSPF - 1 + splitPoint;
 
898
 
 
899
  for ( cIndex = 0; cIndex < l1; cIndex++ )
 
900
  {
 
901
    group1.push_back( dataLow[cIndex]->m_id );
 
902
    delete dataLow[cIndex];
 
903
  }
 
904
 
 
905
  for ( cIndex = l1; cIndex <= m_capacity; cIndex++ )
 
906
  {
 
907
    group2.push_back( dataLow[cIndex]->m_id );
 
908
    delete dataLow[cIndex];
 
909
  }
 
910
 
 
911
  delete[] dataLow;
 
912
  delete[] dataHigh;
 
913
}
 
914
 
 
915
void Node::pickSeeds( unsigned long& index1, unsigned long& index2 )
 
916
{
 
917
  double separation = -std::numeric_limits<double>::max();
 
918
  double inefficiency = -std::numeric_limits<double>::max();
 
919
  unsigned long cDim, cChild, cIndex;
 
920
 
 
921
  switch ( m_pTree->m_treeVariant )
 
922
  {
 
923
    case RV_LINEAR:
 
924
    case RV_RSTAR:
 
925
      for ( cDim = 0; cDim < m_pTree->m_dimension; cDim++ )
 
926
      {
 
927
        double leastLower = m_ptrMBR[0]->m_pLow[cDim];
 
928
        double greatestUpper = m_ptrMBR[0]->m_pHigh[cDim];
 
929
        unsigned long greatestLower = 0;
 
930
        unsigned long leastUpper = 0;
 
931
        double width;
 
932
 
 
933
        for ( cChild = 1; cChild <= m_capacity; cChild++ )
 
934
        {
 
935
          if ( m_ptrMBR[cChild]->m_pLow[cDim] > m_ptrMBR[greatestLower]->m_pLow[cDim] ) greatestLower = cChild;
 
936
          if ( m_ptrMBR[cChild]->m_pHigh[cDim] < m_ptrMBR[leastUpper]->m_pHigh[cDim] ) leastUpper = cChild;
 
937
 
 
938
          leastLower = std::min( m_ptrMBR[cChild]->m_pLow[cDim], leastLower );
 
939
          greatestUpper = std::max( m_ptrMBR[cChild]->m_pHigh[cDim], greatestUpper );
 
940
        }
 
941
 
 
942
        width = greatestUpper - leastLower;
 
943
        if ( width <= 0 ) width = 1;
 
944
 
 
945
        double f = ( m_ptrMBR[greatestLower]->m_pLow[cDim] - m_ptrMBR[leastUpper]->m_pHigh[cDim] ) / width;
 
946
 
 
947
        if ( f > separation )
 
948
        {
 
949
          index1 = leastUpper;
 
950
          index2 = greatestLower;
 
951
          separation = f;
 
952
        }
 
953
      }  // for (cDim)
 
954
 
 
955
      if ( index1 == index2 )
 
956
      {
 
957
        if ( index2 == 0 ) index2++;
 
958
        else index2--;
 
959
      }
 
960
 
 
961
      break;
 
962
    case RV_QUADRATIC:
 
963
      // for each pair of Regions (account for overflow Region too!)
 
964
      for ( cChild = 0; cChild < m_capacity; cChild++ )
 
965
      {
 
966
        double a = m_ptrMBR[cChild]->getArea();
 
967
 
 
968
        for ( cIndex = cChild + 1; cIndex <= m_capacity; cIndex++ )
 
969
        {
 
970
          // get the combined MBR of those two entries.
 
971
          Region r;
 
972
          m_ptrMBR[cChild]->getCombinedRegion( r, *( m_ptrMBR[cIndex] ) );
 
973
 
 
974
          // find the inefficiency of grouping these entries together.
 
975
          double d = r.getArea() - a - m_ptrMBR[cIndex]->getArea();
 
976
 
 
977
          if ( d > inefficiency )
 
978
          {
 
979
            inefficiency = d;
 
980
            index1 = cChild;
 
981
            index2 = cIndex;
 
982
          }
 
983
        }  // for (cIndex)
 
984
      } // for (cChild)
 
985
 
 
986
      break;
 
987
    default:
 
988
      throw Tools::NotSupportedException( "Node::pickSeeds: Tree variant not supported." );
 
989
  }
 
990
}
 
991
 
 
992
void Node::condenseTree( stack<NodePtr>& toReinsert, stack<long>& pathBuffer, NodePtr& ptrThis )
 
993
{
 
994
  unsigned long minimumLoad = static_cast<unsigned long>( std::floor( m_capacity * m_pTree->m_fillFactor ) );
 
995
 
 
996
  if ( pathBuffer.empty() )
 
997
  {
 
998
    // eliminate root if it has only one child.
 
999
    if ( m_level != 0 && m_children == 1 )
 
1000
    {
 
1001
      NodePtr ptrN = m_pTree->readNode( m_pIdentifier[0] );
 
1002
      m_pTree->deleteNode( ptrN.get() );
 
1003
      ptrN->m_identifier = m_pTree->m_rootID;
 
1004
      m_pTree->writeNode( ptrN.get() );
 
1005
 
 
1006
      m_pTree->m_stats.m_nodesInLevel.pop_back();
 
1007
      m_pTree->m_stats.m_treeHeight -= 1;
 
1008
      // HACK: pending deleteNode for deleted child will decrease nodesInLevel, later on.
 
1009
      m_pTree->m_stats.m_nodesInLevel[m_pTree->m_stats.m_treeHeight - 1] = 2;
 
1010
    }
 
1011
  }
 
1012
  else
 
1013
  {
 
1014
    long cParent = pathBuffer.top(); pathBuffer.pop();
 
1015
    NodePtr ptrParent = m_pTree->readNode( cParent );
 
1016
    Index* p = static_cast<Index*>( ptrParent.get() );
 
1017
 
 
1018
    // find the entry in the parent, that points to this node.
 
1019
    unsigned long child;
 
1020
 
 
1021
    for ( child = 0; child != p->m_children; child++ )
 
1022
    {
 
1023
      if ( p->m_pIdentifier[child] == m_identifier ) break;
 
1024
    }
 
1025
 
 
1026
    if ( m_children < minimumLoad )
 
1027
    {
 
1028
      // used space less than the minimum
 
1029
      // 1. eliminate node entry from the parent. deleteEntry will fix the parent's MBR.
 
1030
      p->deleteEntry( child );
 
1031
      // 2. add this node to the stack in order to reinsert its entries.
 
1032
      toReinsert.push( ptrThis );
 
1033
    }
 
1034
    else
 
1035
    {
 
1036
      // adjust the entry in 'p' to contain the new bounding region of this node.
 
1037
      *( p->m_ptrMBR[child] ) = m_nodeMBR;
 
1038
 
 
1039
      // global recalculation necessary since the MBR can only shrink in size,
 
1040
      // due to data removal.
 
1041
      if ( m_pTree->m_bTightMBRs )
 
1042
      {
 
1043
        for ( unsigned long cDim = 0; cDim < p->m_nodeMBR.m_dimension; cDim++ )
 
1044
        {
 
1045
          p->m_nodeMBR.m_pLow[cDim] = std::numeric_limits<double>::max();
 
1046
          p->m_nodeMBR.m_pHigh[cDim] = -std::numeric_limits<double>::max();
 
1047
 
 
1048
          for ( unsigned long cChild = 0; cChild < p->m_children; cChild++ )
 
1049
          {
 
1050
            p->m_nodeMBR.m_pLow[cDim] = std::min( p->m_nodeMBR.m_pLow[cDim], p->m_ptrMBR[cChild]->m_pLow[cDim] );
 
1051
            p->m_nodeMBR.m_pHigh[cDim] = std::max( p->m_nodeMBR.m_pHigh[cDim], p->m_ptrMBR[cChild]->m_pHigh[cDim] );
 
1052
          }
 
1053
        }
 
1054
      }
 
1055
    }
 
1056
 
 
1057
    // write parent node back to storage.
 
1058
    m_pTree->writeNode( p );
 
1059
 
 
1060
    p->condenseTree( toReinsert, pathBuffer, ptrParent );
 
1061
  }
 
1062
}