← Back to branch summary

~fluidity-core/fluidity/refactor-netcdf

« back to all changes in this revision

Viewing changes to spatialindex-1.5/src/tprtree/Node.h

  • Committer: Jon Hill
  • Date: 2013-02-16 09:01:40 UTC
  • mfrom: (3981.7.159 fluidity)
  • Revision ID: jon.hill@imperial.ac.uk-20130216090140-bplzxqzdk1eik4za
Megre from trunk, fixing several conflicts

Show diffs side-by-side

added added

removed removed

Lines of Context:
spatialindex-1.5/src/tprtree/Node.h
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
 
#pragma once
23
 
 
24
 
namespace SpatialIndex
25
 
{
26
 
        namespace TPRTree
27
 
        {
28
 
                class TPRTree;
29
 
                class Leaf;
30
 
                class Index;
31
 
                class Node;
32
 
 
33
 
                typedef Tools::PoolPointer<Node> NodePtr;
34
 
 
35
 
                class Node : public SpatialIndex::INode
36
 
                {
37
 
                public:
38
 
                        virtual ~Node();
39
 
 
40
 
                        //
41
 
                        // Tools::IObject interface
42
 
                        //
43
 
                        virtual Tools::IObject* clone();
44
 
 
45
 
                        //
46
 
                        // Tools::ISerializable interface
47
 
                        //
48
 
                        virtual uint32_t getByteArraySize();
49
 
                        virtual void loadFromByteArray(const byte* data);
50
 
                        virtual void storeToByteArray(byte** data, uint32_t& len);
51
 
 
52
 
                        //
53
 
                        // SpatialIndex::IEntry interface
54
 
                        //
55
 
                        virtual id_type getIdentifier() const;
56
 
                        virtual void getShape(IShape** out) const;
57
 
 
58
 
                        //
59
 
                        // SpatialIndex::INode interface
60
 
                        //
61
 
                        virtual uint32_t getChildrenCount() const;
62
 
                        virtual id_type getChildIdentifier(uint32_t index)  const;
63
 
                        virtual void getChildShape(uint32_t index, IShape** out)  const;
64
 
                        virtual void getChildData(uint32_t index, uint32_t& length, byte** data) const;
65
 
                        virtual uint32_t getLevel() const;
66
 
                        virtual bool isIndex() const;
67
 
                        virtual bool isLeaf() const;
68
 
 
69
 
                private:
70
 
                        Node();
71
 
                        Node(TPRTree* pTree, id_type id, uint32_t level, uint32_t capacity);
72
 
 
73
 
                        virtual Node& operator=(const Node&);
74
 
 
75
 
                        virtual bool insertEntry(uint32_t dataLength, byte* pData, MovingRegion& mbr, id_type id);
76
 
                        virtual void deleteEntry(uint32_t index);
77
 
 
78
 
                        virtual bool insertData(uint32_t dataLength, byte* pData, MovingRegion& mbr, id_type id, std::stack<id_type>& pathBuffer, byte* overflowTable);
79
 
                        virtual void reinsertData(uint32_t dataLength, byte* pData, MovingRegion& mbr, id_type id, std::vector<uint32_t>& reinsert, std::vector<uint32_t>& keep);
80
 
 
81
 
                        virtual void rstarSplit(uint32_t dataLength, byte* pData, MovingRegion& mbr, id_type id, std::vector<uint32_t>& group1, std::vector<uint32_t>& group2);
82
 
 
83
 
                        virtual void condenseTree(std::stack<NodePtr>& toReinsert, std::stack<id_type>& pathBuffer, NodePtr& ptrThis);
84
 
 
85
 
                        virtual NodePtr chooseSubtree(const MovingRegion& mbr, uint32_t level, std::stack<id_type>& pathBuffer) = 0;
86
 
                        virtual NodePtr findLeaf(const MovingRegion& mbr, id_type id, std::stack<id_type>& pathBuffer) = 0;
87
 
 
88
 
                        virtual void split(uint32_t dataLength, byte* pData, MovingRegion& mbr, id_type id, NodePtr& left, NodePtr& right) = 0;
89
 
 
90
 
                        TPRTree* m_pTree;
91
 
                                // Parent of all nodes.
92
 
 
93
 
                        uint32_t m_level;
94
 
                                // The level of the node in the tree.
95
 
                                // Leaves are always at level 0.
96
 
 
97
 
                        id_type m_identifier;
98
 
                                // The unique ID of this node.
99
 
 
100
 
                        uint32_t m_children;
101
 
                                // The number of children pointed by this node.
102
 
 
103
 
                        uint32_t m_capacity;
104
 
                                // Specifies the node capacity.
105
 
 
106
 
                        MovingRegion m_nodeMBR;
107
 
                                // The minimum bounding region enclosing all data contained in the node.
108
 
 
109
 
                        byte** m_pData;
110
 
                                // The data stored in the node.
111
 
 
112
 
                        MovingRegionPtr* m_ptrMBR;
113
 
                                // The corresponding data MBRs.
114
 
 
115
 
                        id_type* m_pIdentifier;
116
 
                                // The corresponding data identifiers.
117
 
 
118
 
                        uint32_t* m_pDataLength;
119
 
 
120
 
                        uint32_t m_totalDataLength;
121
 
 
122
 
                        class RstarSplitEntry
123
 
                        {
124
 
                        public:
125
 
                                MovingRegion* m_pRegion;
126
 
                                uint32_t m_index;
127
 
                                uint32_t m_sortDim;
128
 
 
129
 
                                RstarSplitEntry(MovingRegion* pr, uint32_t index, uint32_t dimension)
130
 
                                        : m_pRegion(pr), m_index(index), m_sortDim(dimension) {}
131
 
 
132
 
                                static int compareLow(const void* pv1, const void* pv2)
133
 
                                {
134
 
                                        RstarSplitEntry* pe1 = * (RstarSplitEntry**) pv1;
135
 
                                        RstarSplitEntry* pe2 = * (RstarSplitEntry**) pv2;
136
 
 
137
 
                                        if (pe1->m_pRegion->m_pLow[pe1->m_sortDim] < pe2->m_pRegion->m_pLow[pe1->m_sortDim]) return -1;
138
 
                                        if (pe1->m_pRegion->m_pLow[pe1->m_sortDim] > pe2->m_pRegion->m_pLow[pe1->m_sortDim]) return 1;
139
 
                                        return 0;
140
 
                                }
141
 
 
142
 
                                static int compareHigh(const void* pv1, const void* pv2)
143
 
                                {
144
 
                                        RstarSplitEntry* pe1 = * (RstarSplitEntry**) pv1;
145
 
                                        RstarSplitEntry* pe2 = * (RstarSplitEntry**) pv2;
146
 
 
147
 
                                        if (pe1->m_pRegion->m_pHigh[pe1->m_sortDim] < pe2->m_pRegion->m_pHigh[pe1->m_sortDim]) return -1;
148
 
                                        if (pe1->m_pRegion->m_pHigh[pe1->m_sortDim] > pe2->m_pRegion->m_pHigh[pe1->m_sortDim]) return 1;
149
 
                                        return 0;
150
 
                                }
151
 
 
152
 
                                static int compareVLow(const void* pv1, const void* pv2)
153
 
                                {
154
 
                                        RstarSplitEntry* pe1 = * (RstarSplitEntry**) pv1;
155
 
                                        RstarSplitEntry* pe2 = * (RstarSplitEntry**) pv2;
156
 
 
157
 
                                        if (pe1->m_pRegion->m_pVLow[pe1->m_sortDim] < pe2->m_pRegion->m_pVLow[pe1->m_sortDim]) return -1;
158
 
                                        if (pe1->m_pRegion->m_pVLow[pe1->m_sortDim] > pe2->m_pRegion->m_pVLow[pe1->m_sortDim]) return 1;
159
 
                                        return 0;
160
 
                                }
161
 
 
162
 
                                static int compareVHigh(const void* pv1, const void* pv2)
163
 
                                {
164
 
                                        RstarSplitEntry* pe1 = * (RstarSplitEntry**) pv1;
165
 
                                        RstarSplitEntry* pe2 = * (RstarSplitEntry**) pv2;
166
 
 
167
 
                                        if (pe1->m_pRegion->m_pVHigh[pe1->m_sortDim] < pe2->m_pRegion->m_pVHigh[pe1->m_sortDim]) return -1;
168
 
                                        if (pe1->m_pRegion->m_pVHigh[pe1->m_sortDim] > pe2->m_pRegion->m_pVHigh[pe1->m_sortDim]) return 1;
169
 
                                        return 0;
170
 
                                }
171
 
                        }; // RstarSplitEntry
172
 
 
173
 
                        class ReinsertEntry
174
 
                        {
175
 
                        public:
176
 
                                uint32_t m_index;
177
 
                                double m_dist;
178
 
 
179
 
                                ReinsertEntry(uint32_t index, double dist) : m_index(index), m_dist(dist) {}
180
 
 
181
 
                                static int compareReinsertEntry(const void* pv1, const void* pv2)
182
 
                                {
183
 
                                        ReinsertEntry* pe1 = * (ReinsertEntry**) pv1;
184
 
                                        ReinsertEntry* pe2 = * (ReinsertEntry**) pv2;
185
 
 
186
 
                                        if (pe1->m_dist < pe2->m_dist) return -1;
187
 
                                        if (pe1->m_dist > pe2->m_dist) return 1;
188
 
                                        return 0;
189
 
                                }
190
 
                        }; // ReinsertEntry
191
 
 
192
 
                        // Needed to access protected members without having to cast from Node.
193
 
                        // It is more efficient than using member functions to access protected members.
194
 
                        friend class TPRTree;
195
 
                        friend class Leaf;
196
 
                        friend class Index;
197
 
                        friend class Tools::PointerPool<Node>;
198
 
                }; // Node
199
 
        }
200
 
}