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 <cstring>
29
30 #include <spatialindex/SpatialIndex.h>
31
32 #include "TPRTree.h"
33 #include "Node.h"
34 #include "Index.h"
35 #include "Leaf.h"
36
37 using namespace SpatialIndex;
38 using namespace SpatialIndex::TPRTree;
39
~Leaf()40 Leaf::~Leaf()
41 {
42 }
43
Leaf(SpatialIndex::TPRTree::TPRTree * pTree,id_type id)44 Leaf::Leaf(SpatialIndex::TPRTree::TPRTree* pTree, id_type id)
45 : Node(pTree, id, 0, pTree->m_leafCapacity)
46 {
47 }
48
chooseSubtree(const MovingRegion &,uint32_t,std::stack<id_type> &)49 NodePtr Leaf::chooseSubtree(const MovingRegion&, uint32_t, std::stack<id_type>&)
50 {
51 // should make sure to relinquish other PoolPointer lists that might be pointing to the
52 // same leaf.
53 return NodePtr(this, &(m_pTree->m_leafPool));
54 }
55
findLeaf(const MovingRegion &,id_type id,std::stack<id_type> &)56 NodePtr Leaf::findLeaf(const MovingRegion&, id_type id, std::stack<id_type>&)
57 {
58 for (uint32_t cChild = 0; cChild < m_children; ++cChild)
59 {
60 // should make sure to relinquish other PoolPointer lists that might be pointing to the
61 // same leaf.
62 if (m_pIdentifier[cChild] == id /*&& mbr == *(m_ptrMBR[cChild])*/) return NodePtr(this, &(m_pTree->m_leafPool));
63 }
64
65 return NodePtr();
66 }
67
split(uint32_t dataLength,byte * pData,MovingRegion & mbr,id_type id,NodePtr & pLeft,NodePtr & pRight)68 void Leaf::split(uint32_t dataLength, byte* pData, MovingRegion& mbr, id_type id, NodePtr& pLeft, NodePtr& pRight)
69 {
70 ++(m_pTree->m_stats.m_splits);
71
72 std::vector<uint32_t> g1, g2;
73
74 switch (m_pTree->m_treeVariant)
75 {
76 case TPRV_RSTAR:
77 rstarSplit(dataLength, pData, mbr, id, g1, g2);
78 break;
79 default:
80 throw Tools::NotSupportedException("Leaf::split: Tree variant not supported.");
81 }
82
83 pLeft = m_pTree->m_leafPool.acquire();
84 pRight = m_pTree->m_leafPool.acquire();
85
86 if (pLeft.get() == 0) pLeft = NodePtr(new Leaf(m_pTree, -1), &(m_pTree->m_leafPool));
87 if (pRight.get() == 0) pRight = NodePtr(new Leaf(m_pTree, -1), &(m_pTree->m_leafPool));
88
89 pLeft->m_nodeMBR = m_pTree->m_infiniteRegion;
90 pRight->m_nodeMBR = m_pTree->m_infiniteRegion;
91
92 uint32_t cIndex;
93
94 for (cIndex = 0; cIndex < g1.size(); ++cIndex)
95 {
96 pLeft->insertEntry(m_pDataLength[g1[cIndex]], m_pData[g1[cIndex]], *(m_ptrMBR[g1[cIndex]]), m_pIdentifier[g1[cIndex]]);
97 // we don't want to delete the data array from this node's destructor!
98 m_pData[g1[cIndex]] = 0;
99 }
100
101 for (cIndex = 0; cIndex < g2.size(); ++cIndex)
102 {
103 pRight->insertEntry(m_pDataLength[g2[cIndex]], m_pData[g2[cIndex]], *(m_ptrMBR[g2[cIndex]]), m_pIdentifier[g2[cIndex]]);
104 // we don't want to delete the data array from this node's destructor!
105 m_pData[g2[cIndex]] = 0;
106 }
107 }
108
deleteData(id_type id,std::stack<id_type> & pathBuffer)109 void Leaf::deleteData(id_type id, std::stack<id_type>& pathBuffer)
110 {
111 uint32_t child;
112
113 for (child = 0; child < m_children; ++child)
114 {
115 if (m_pIdentifier[child] == id) break;
116 }
117
118 deleteEntry(child);
119 m_pTree->writeNode(this);
120
121 std::stack<NodePtr> toReinsert;
122 NodePtr ptrThis(this, &(m_pTree->m_leafPool));
123 condenseTree(toReinsert, pathBuffer, ptrThis);
124 ptrThis.relinquish();
125
126 // re-insert eliminated nodes.
127 while (! toReinsert.empty())
128 {
129 NodePtr n = toReinsert.top(); toReinsert.pop();
130 m_pTree->deleteNode(n.get());
131
132 for (uint32_t cChild = 0; cChild < n->m_children; ++cChild)
133 {
134 // keep this in the for loop. The tree height might change after insertions.
135 byte* overflowTable = new byte[m_pTree->m_stats.m_treeHeight];
136 memset(overflowTable, 0, m_pTree->m_stats.m_treeHeight);
137 m_pTree->insertData_impl(n->m_pDataLength[cChild], n->m_pData[cChild], *(n->m_ptrMBR[cChild]), n->m_pIdentifier[cChild], n->m_level, overflowTable);
138 n->m_pData[cChild] = 0;
139 delete[] overflowTable;
140 }
141 if (n.get() == this) n.relinquish();
142 }
143 }
144