rasdaman complete source
sdirindexlogic.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 _DIRIX_HH_
25 #define _DIRIX_HH_
26 
27 #include "reladminif/lists.h"
28 class r_Point;
29 class StorageLayout;
30 
31 /***********************
32  *
33  * INCLUDE: dirix.hh
34  *
35  * MODULE: indexmgr
36  * CLASS: SDirIndexLogic
37  *
38  *
39  * COMMENTS:
40  *
41  ***********/
42 
49 /*@Doc:
50 
51  The SDirIndexLogic class implements a Directory of Interval Objects Index.
52 
53  Objects inserted in the index must be disjunctive, since optimizations
54  are made which assume nonoverlapping interval objects.
55 
56  It can be used as index on tiles of MDD objects.
57  A directory index consists solely of the current domain and
58  a list of entries, one for each interval object (for instance, a tile).
59  Interval objects must not overlap, since {\tt SDirIndexLogic} optimizes access
60  based on the assumption that entries don't overlap. Entries are
61  sorted by the lower vertice.
62  Each entry contains the interval domain and a reference to the object
63  itself.
64 
65  SDirIndexLogic implements the higher level index functionality and uses the
66  functionality of {\tt IndexDS} to do the operations.
67 
68  This way, {\tt SDirIndexLogic} can be used for both persistent or
69  main memory indexes, tiles index or intermediate nodes of a multidimensional
70  index, etc, by defining appropriate {\tt IndexDS} classes. Examples are
71  {\tt TransDirIx} and {\tt DBHierIndex}, for transient and persistent
72  indexes, respectively.A
73 
74  The logic classes are stack based for performance and memory reasons -> everything is static.
75 */
76 
78 {
79 public:
80 
81  static bool insertObject(IndexDS* theIx, const KeyObject& newObject, const StorageLayout& sl);
82  /*@Doc:
83  Inserts a new object in the index.
84  */
85 
86  static bool removeObject(IndexDS* theIx, const KeyObject& tileToRemove, const StorageLayout& sl);
87  /*@Doc:
88  Removes the tile from the object.
89  */
90 
91  static void intersect(const IndexDS* theIx, const r_Minterval& searchInter, KeyObjectVector& objs, const StorageLayout& sl);
92  /*@Doc:
93  Search the index for a search region.
94  Determines all the tiles in the index which intersect a given
95  search interval (given by {\tt searchInter}).
96  The memory space allocated by this function for the contents
97  of the keyobjects in the returned vector (only) must be released
98  afterwards by the caller.
99  */
100 
101  static void intersectUnOpt(const IndexDS* theIx, const r_Minterval& searchInter, KeyObjectVector& objs);
102  /*@Doc:
103  Search the index for a search region.
104  Old unoptimized version of intersect(). Just scans all the entries,
105  tests each one for intersection, returning all that intersect.
106  This method is actually used for removing of tiles (a tile can be stored in multiple nodes).
107  */
108 
109  static void containPointQuery(const IndexDS* theIx, const r_Point& searchPoint, KeyObject& result, const StorageLayout& sl);
110  /*@Doc:
111  Passes a pointer to the searched item.
112  Memory is for the KeyObject is not to be released by the caller.
113  */
114 
115  static void getObjects(const IndexDS* ixDS, KeyObjectVector& objs, const StorageLayout& sl);
116  /*@Doc:
117  Returns all the tiles belonging to the object.
118  */
119 
121  {
122  Highest = 1,
123  Lowest = 2,
124  None = 0
125  };
126  /*@Doc:
127  */
128 
129  static int compare( const r_Minterval& mint1,
130  const r_Minterval& mint2,
131  OrderPoint o1 = Lowest,
132  OrderPoint o2 = Lowest);
133  /*@Doc:
134  Compares two intervals based on two points from each one.
135  Returns : -1 if mint1.point(o1) < mint2.point(o2);
136  0 iff mint1.point(o1) == mint2.point(o2) and
137  1 iff mint1.point(o1) > mint2.point(o2); where
138  mint.point(o) is the lowest corner point of mint if o == Lowest,
139  mint.point(o) is the highest corner point of mint if o == Highest.
140  */
141 
142  static int binarySearch( const IndexDS* theIx,
143  const r_Minterval& newDomain,
144  OrderPoint o,
145  int first,
146  int last);
147  /*@Doc:
148  Returns position of searched item or position before the one where
149  it should be inserted to keep the order of the list (-1 means it should be
150  inserted at the beginning of the list).
151  */
152 
153  static int binaryPointSearch( const IndexDS* theIx,
154  const r_Point& pnt,
155  OrderPoint o,
156  int first,
157  int last);
158  /*@Doc:
159  Returns position of tile having the point, -1 if point not there.
160  */
161 
162  static int binaryRegionSearch( const IndexDS* theIx,
163  const r_Minterval& mint,
164  r_Area& area,
165  KeyObjectVector& intersectedObjects,
166  int first,
167  int last);
168  /*@Doc:
169  Assumes ordering according to the lowest corner of the tiles!!!
170  */
171 
172 };
173 
174 #endif
Definition: sdirindexlogic.hh:123
static bool insertObject(IndexDS *theIx, const KeyObject &newObject, const StorageLayout &sl)
std::vector< KeyObject > KeyObjectVector
Definition: lists.h:79
static int compare(const r_Minterval &mint1, const r_Minterval &mint2, OrderPoint o1=Lowest, OrderPoint o2=Lowest)
Definition: sdirindexlogic.hh:124
static void getObjects(const IndexDS *ixDS, KeyObjectVector &objs, const StorageLayout &sl)
static int binaryRegionSearch(const IndexDS *theIx, const r_Minterval &mint, r_Area &area, KeyObjectVector &intersectedObjects, int first, int last)
Definition: keyobject.hh:43
Definition: sdirindexlogic.hh:77
static void intersectUnOpt(const IndexDS *theIx, const r_Minterval &searchInter, KeyObjectVector &objs)
static void containPointQuery(const IndexDS *theIx, const r_Point &searchPoint, KeyObject &result, const StorageLayout &sl)
Definition: sdirindexlogic.hh:122
static bool removeObject(IndexDS *theIx, const KeyObject &tileToRemove, const StorageLayout &sl)
static void intersect(const IndexDS *theIx, const r_Minterval &searchInter, KeyObjectVector &objs, const StorageLayout &sl)
OrderPoint
Definition: sdirindexlogic.hh:120
Definition: sstoragelayout.hh:65
static int binarySearch(const IndexDS *theIx, const r_Minterval &newDomain, OrderPoint o, int first, int last)
static int binaryPointSearch(const IndexDS *theIx, const r_Point &pnt, OrderPoint o, int first, int last)