rasdaman complete source
srptindexlogic.hh
Go to the documentation of this file.
1 /*
2 * This file is part of rasdaman community.
3 *
4 * Rasdaman community is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
8 *
9 * Rasdaman community is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with rasdaman community. If not, see <http://www.gnu.org/licenses/>.
16 *
17 * Copyright 2003, 2004, 2005, 2006, 2007, 2008, 2009 Peter Baumann /
18 rasdaman GmbH.
19 *
20 * For more information please see <http://www.rasdaman.org>
21 * or contact Peter Baumann via <baumann@rasdaman.com>.
22 */
23 
24 #ifndef _SRPTINDEXLOGIC_HH_
25 #define _SRPTINDEXLOGIC_HH_
26 
27 #include "indexmgr/hierindexds.hh"
28 #include "reladminif/lists.h"
29 class r_Point;
30 class StorageLayout;
31 
32 
39 /*@Doc:
40 This class contains the logic for access, insertion and removal of objects
41 into an index data structure. The logic is based on the R-Plus Tree. Objects
42 inserted in this index don`t have to be regular. The leaf object`s domain
43 must not overlap.
44 
45 The leaf objects are sorted into nodes which are split when needed. Nodes
46 are split when the number of objects in them is equal to the maximum size
47 specified by the underlying index data structure. This check should be done
48 using the IndexDS::isOverFull() method.
49 
50 This class uses functionality supplied by SDirIndexLogic.
51 
52 This class was converted to pure static methods because it is fast to use stack.
53 */
54 
56 {
57 public:
58  static bool insertObject2(IndexDS* ixDS, const KeyObject& newObject, const StorageLayout& sl);
59  /*@Doc:
60  Inserts a new object in the index.
61  Must have a name different from the other insertObject because of the stupid compiler.
62  */
63 
64  static bool removeObject(IndexDS* ixDS, const KeyObject& tileToRemove, const StorageLayout& sl);
65  /*@Doc:
66  Removes the object from the indexx.
67  */
68 
69  static void intersect2(const IndexDS* ixDS, const r_Minterval& searchInter, KeyObjectVector& objs, const StorageLayout& sl);
70  /*@Doc:
71  Search the index for a search region.
72  Determines all the tiles in the index which intersect a given
73  search interval (given by {\tt searchInter}).
74  Must have a name different from other intersect because of compiler.
75  */
76 
77  static void containPointQuery2(const IndexDS* ixDS, const r_Point& searchPoint, KeyObject& result, const StorageLayout& sl);
78  /*@Doc:
79  Passes a pointer to the searched item.
80  Must have different name from other containPointQuery because of compiler.
81  */
82 
83  static void getObjects(const IndexDS* ixDS, KeyObjectVector& objs, const StorageLayout& sl);
84  /*@Doc:
85  Returns all the tiles belonging to the object.
86  */
87 
88  static int insertObject( const KeyObject& newObject,
89  HierIndexDS* ix,
90  IndexPVector& leafNodes2Split,
91  const StorageLayout& sl);
92  /*@Doc:
93  Inserts a new object in the index.
94  Recursive function which does the real job.
95  The return value is 1 if the current node was split, 0 otherwise. This is
96  used internally by the algorithm (?really - better not touch it?).
97  In {\tt leafNodes2Split}, the set of overflowed leaf nodes is returned.
98  It should be passed to {\tt splitNodes()}.
99  */
100 
101 
102  static void extendFaces(HierIndexDS* ix,
103  const r_Minterval& newKeyObjectDom,
104  const r_Minterval& oldCurrDom,
105  const bool* facesToExtendLo,
106  const bool* facesToExtendHi);
107  /*@Doc:
108  This method extends the domains of all index nodes which
109  intersect with the object that will be inserted.
110  This is neccessary because subsequently all nodes which
111  intersect with the object to be inserted are retrieved by
112  DirIndexLogic.
113  */
114 
115  static void splitNodes( HierIndexDS* ixDS,
116  IndexPVector& leafNodes2Split,
117  const StorageLayout& sl);
118  /*@Doc:
119  Splits all nodes after insert
120  Full nodes are split all at once, to avoid repetition of splits.
121  Uses splitLeaf and splitNonLeaf to carry out the task.
122  */
123 
124  static void splitLeaf( HierIndexDS* n1,
125  HierIndexDS* n2,
126  KeyObjectVector& keyvec,
127  r_Dimension axis,
128  r_Range value,
129  r_Minterval& domain,
130  const StorageLayout& sl);
131  /*@Doc:
132  Splits a leaf node
133  {\tt n1} has the entries which intersect (leafNodeDomain and x(axis) <= value),
134  {\tt n2 } the ones intersecting (leafNodeDomain and x(axis) > value).
135  The keyvec holds the tiles which will be inserted into the 2 new leafs.
136  The domain is the complete assigned domain of both leafs. It will be divided into 2 parts
137  based on axis and value. Then the tiles are assigned to the leaf that covers them - or both.
138  */
139 
140  static void splitNonLeaf( HierIndexDS* n1,
141  HierIndexDS* n2,
142  KeyObjectVector& keyvec,
143  IndexPVector& leafNodes2Split,
144  r_Dimension axis,
145  r_Range value,
146  const r_Minterval& domain,
147  const StorageLayout& sl);
148  /*@Doc:
149  Splits a nonleaf node
150  Does semantically the same as splitLeaf. Syntactically it is quite different because it has to check
151  for over full nodes and treat them.
152  */
153 
154  static void redistributeEntries(IndexDS* node,
155  KeyObjectVector& listMinKO,
156  const StorageLayout& sl);
157  /*@Doc:
158  stores the Keyobjects in the node. could do some more
159  fancy stuff in the future (like checking for under full and then redistribute those nodes).
160  */
161 
162  static void calculatePartition( r_Dimension& axis,
163  r_Range& value,
164  const HierIndexDS* node);
165  /*@Doc:
166  Calculates the optimal partition for this node Partition is returned in {\tt axis}, {\tt value}.
167  This is the most problematic stuff because it depends on the order of insertion.
168  The index nodes are not optimally filled. But you know: we are the fastest anyway ; )
169  */
170 
171  static void calculateDistribution( r_Dimension axis,
172  r_Range value,
173  float& dist1,
174  float& dist2,
175  const HierIndexDS* node);
176  /*@Doc:
177  Caluculates the distribution of entries for a given partition
178  Used by calculate partition.
179  Calculates resulting distribution of children of a node {\ttnode} if
180  it is split at axis = value. Distributions are returned in {\ttdist1}
181  (percentage of nodes intersecting x(axis) <= value) and {\ttdist2}
182  (percentage of nodes intersecting x(axis) > value).
183  */
184 
185  static void intersect( const r_Minterval& searchInter,
186  const r_Minterval& parentDomain,
187  KeyObjectVector& intersectedObjs,
188  const HierIndexDS* ix,
189  r_Area& area);
190  /*@Doc:
191  This method helps you get the data out of the index again : )
192  searchInter will tell you for what to look.
193  parentDomain is used to determin if you should include a matching object or not.
194  you might not want to include a matching object because of duplicate entries in the index.
195  this choice is made by intersectNoDuplicates.
196  intersectedObjs holds the found entries.
197  the area is used to determine if we got everything.
198  */
199 
200  static bool intersectNoDuplicates( const r_Minterval& searchInter,
201  const r_Minterval& entryDomain,
202  const r_Minterval& parentDomain);
203  /*@Doc:
204  Decides if the entry at hand should be included from this index or if it is in another
205  one and will be included from there.
206  */
207 
208 
209  static int binaryRegionSearch( const HierIndexDS* ixNode,
210  const r_Minterval& mint,
211  r_Area& area,
212  KeyObjectVector& intersectedObjects,
213  int first,
214  int last,
215  const r_Minterval& parentEntryDom);
216  /*@Doc:
217  This will use a binary search algorithm to quickly find the nodes we want.
218  */
219 
220  static int regionSearch(const HierIndexDS* ixNode,
221  const r_Minterval& mint,
222  r_Area& area,
223  KeyObjectVector& intersectedObjects,
224  const r_Minterval& parentDomain);
225  /*@Doc:
226  This is a not binary search algorithm for doing the same as binaryRegionSearch.
227  */
228 
229  static void containPointQuery(const r_Point& searchPoint, const HierIndexDS* ix, KeyObject& result, const StorageLayout& sl);
230  /*@Doc:
231  */
232 
233  static HierIndexDS* convert(const KeyObject& toConvert);
234  /*@Doc:
235  Helper method for converting a keyobject to a hierindex object.
236  the parameter must be deleted by the caller.
237  the returned object must be deleted by the caller.
238  */
239 
240  static KeyObject convert(HierIndexDS* toConvert);
241  /*@Doc:
242  Helper method for converting a hierindex to a keyobject.
243  the parameter must be deleted by the caller.
244  the returned object must be deleted by the caller.
245  */
246 
247 };
248 
249 #endif
static void splitLeaf(HierIndexDS *n1, HierIndexDS *n2, KeyObjectVector &keyvec, r_Dimension axis, r_Range value, r_Minterval &domain, const StorageLayout &sl)
static void getObjects(const IndexDS *ixDS, KeyObjectVector &objs, const StorageLayout &sl)
std::vector< IndexDS * > IndexPVector
Definition: lists.h:87
Definition: point.hh:59
static void redistributeEntries(IndexDS *node, KeyObjectVector &listMinKO, const StorageLayout &sl)
std::vector< KeyObject > KeyObjectVector
Definition: lists.h:79
static bool insertObject2(IndexDS *ixDS, const KeyObject &newObject, const StorageLayout &sl)
int r_Range
Definition: mddtypes.hh:100
unsigned int r_Dimension
Definition: mddtypes.hh:118
Definition: hierindexds.hh:50
Definition: indexds.hh:51
static bool removeObject(IndexDS *ixDS, const KeyObject &tileToRemove, const StorageLayout &sl)
Definition: keyobject.hh:43
static bool intersectNoDuplicates(const r_Minterval &searchInter, const r_Minterval &entryDomain, const r_Minterval &parentDomain)
static HierIndexDS * convert(const KeyObject &toConvert)
static void extendFaces(HierIndexDS *ix, const r_Minterval &newKeyObjectDom, const r_Minterval &oldCurrDom, const bool *facesToExtendLo, const bool *facesToExtendHi)
static void intersect2(const IndexDS *ixDS, const r_Minterval &searchInter, KeyObjectVector &objs, const StorageLayout &sl)
static void calculateDistribution(r_Dimension axis, r_Range value, float &dist1, float &dist2, const HierIndexDS *node)
static void containPointQuery(const r_Point &searchPoint, const HierIndexDS *ix, KeyObject &result, const StorageLayout &sl)
static void containPointQuery2(const IndexDS *ixDS, const r_Point &searchPoint, KeyObject &result, const StorageLayout &sl)
static int insertObject(const KeyObject &newObject, HierIndexDS *ix, IndexPVector &leafNodes2Split, const StorageLayout &sl)
uint64_t r_Area
Definition: mddtypes.hh:85
static void intersect(const r_Minterval &searchInter, const r_Minterval &parentDomain, KeyObjectVector &intersectedObjs, const HierIndexDS *ix, r_Area &area)
static void calculatePartition(r_Dimension &axis, r_Range &value, const HierIndexDS *node)
static void splitNodes(HierIndexDS *ixDS, IndexPVector &leafNodes2Split, const StorageLayout &sl)
static void splitNonLeaf(HierIndexDS *n1, HierIndexDS *n2, KeyObjectVector &keyvec, IndexPVector &leafNodes2Split, r_Dimension axis, r_Range value, const r_Minterval &domain, const StorageLayout &sl)
static int regionSearch(const HierIndexDS *ixNode, const r_Minterval &mint, r_Area &area, KeyObjectVector &intersectedObjects, const r_Minterval &parentDomain)
Definition: sstoragelayout.hh:65
static int binaryRegionSearch(const HierIndexDS *ixNode, const r_Minterval &mint, r_Area &area, KeyObjectVector &intersectedObjects, int first, int last, const r_Minterval &parentEntryDom)
Definition: minterval.hh:249
Definition: srptindexlogic.hh:55