1 /******************************************************************************
2 * Project: libspatialindex - A C++ library for spatial indexing
3 * Author: Marios Hadjieleftheriou, mhadji@gmail.com
4 ******************************************************************************
5 * Copyright (c) 2003, 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 <spatialindex/tools/Tools.h>
29 #include <cmath>
30 #include <limits>
31
32 using namespace std;
33
34 #define DELETE 0
35 #define INSERT 1
36 #define QUERY 2
37
38 class Region
39 {
40 public:
41 double m_xmin, m_ymin, m_xmax, m_ymax;
42 bool m_bIsDead;
43
Region()44 Region() : m_xmin(numeric_limits<double>::max()), m_ymin(numeric_limits<double>::max()),
45 m_xmax(numeric_limits<double>::max()), m_ymax(numeric_limits<double>::max()) {}
46
Region(double x1,double y1,double x2,double y2)47 Region(double x1, double y1, double x2, double y2)
48 {
49 m_xmin = (x1 < x2) ? x1 : x2;
50 m_ymin = (y1 < y2) ? y1 : y2;
51 m_xmax = (x1 > x2) ? x1 : x2;
52 m_ymax = (y1 > y2) ? y1 : y2;
53 m_bIsDead = false;
54 }
55 };
56
main(int argc,char ** argv)57 int main(int argc, char** argv)
58 {
59 if (argc != 2)
60 {
61 cerr << "Usage: " << argv[0] << " number_of_data." << endl;
62 return -1;
63 }
64
65 size_t numberOfObjects = atoi(argv[1]);
66 map<size_t, Region> data;
67 Tools::Random rnd;
68
69 for (size_t i = 0; i < numberOfObjects; i++)
70 {
71 double x = rnd.nextUniformDouble();
72 double y = rnd.nextUniformDouble();
73 double dx = rnd.nextUniformDouble(0.0001, 0.1);
74 double dy = rnd.nextUniformDouble(0.0001, 0.1);
75 Region r = Region(x, y, x + dx, y + dy);
76
77 data.insert(pair<size_t, Region>(i, r));
78
79 cout << "0 " << INSERT << " " << i << " " << r.m_xmin << " " << r.m_ymin << " "
80 << r.m_xmax << " " << r.m_ymax << endl;
81 }
82
83 size_t nextID = numberOfObjects;
84 size_t A = static_cast<size_t>(std::floor(static_cast<double>(numberOfObjects) * 0.05));
85
86 for (size_t T = 1; T <= 100; T++)
87 {
88 cerr << (101 - T) << endl;
89
90 if (T == 50)
91 {
92 // delete all entries and reinsert
93 for (map<size_t, Region>::iterator itMap = data.begin(); itMap != data.end(); itMap++)
94 {
95 if (! (*itMap).second.m_bIsDead)
96 {
97 (*itMap).second.m_bIsDead = true;
98 cout << "50 " << DELETE << " " << (*itMap).first << " " << (*itMap).second.m_xmin << " " << (*itMap).second.m_ymin << " "
99 << (*itMap).second.m_xmax << " " << (*itMap).second.m_ymax << endl;
100 }
101 }
102
103 for (size_t i = nextID; i < nextID + numberOfObjects; i++)
104 {
105 double x = rnd.nextUniformDouble();
106 double y = rnd.nextUniformDouble();
107 double dx = rnd.nextUniformDouble(0.0001, 0.1);
108 double dy = rnd.nextUniformDouble(0.0001, 0.1);
109 Region r = Region(x, y, x + dx, y + dy);
110
111 data.insert(pair<size_t, Region>(i, r));
112
113 cout << "50 " << INSERT << " " << i << " " << r.m_xmin << " " << r.m_ymin << " "
114 << r.m_xmax << " " << r.m_ymax << endl;
115 }
116
117 nextID += numberOfObjects;
118 continue;
119 }
120
121 set<size_t> examined;
122
123 for (size_t a = 0; a < A; a++)
124 {
125 // find an id that is not examined yet.
126 size_t id = static_cast<size_t>(rnd.nextUniformLongLong(0, nextID));
127 set<size_t>::iterator itSet = examined.find(id);
128 while (itSet != examined.end() || data[id].m_bIsDead == true)
129 {
130 id = static_cast<size_t>(rnd.nextUniformLongLong(0, nextID));
131 itSet = examined.find(id);
132 }
133 examined.insert(id);
134
135 map<size_t, Region>::iterator itMap = data.find(id);
136 assert(itMap != data.end() && (*itMap).second.m_bIsDead == false);
137
138 cout << T << " " << DELETE << " " << id << " " << (*itMap).second.m_xmin << " " << (*itMap).second.m_ymin << " "
139 << (*itMap).second.m_xmax << " " << (*itMap).second.m_ymax << endl;
140 (*itMap).second.m_bIsDead = true;
141
142 double x = rnd.nextUniformDouble();
143 double y = rnd.nextUniformDouble();
144 double dx = rnd.nextUniformDouble(0.0001, 0.1);
145 double dy = rnd.nextUniformDouble(0.0001, 0.1);
146 Region r = Region(x, y, x + dx, y + dy);
147
148 data.insert(pair<size_t, Region>(nextID, r));
149
150 cout << T << " " << INSERT << " " << nextID << " " << r.m_xmin << " " << r.m_ymin << " "
151 << r.m_xmax << " " << r.m_ymax << endl;
152 examined.insert(nextID);
153 nextID++;
154 }
155
156 double stx = rnd.nextUniformDouble();
157 double sty = rnd.nextUniformDouble();
158 size_t qt = rnd.nextUniformLongLong(0, T);
159 cout << T << " " << QUERY << " 9999999 " << stx << " " << sty << " " << (stx + 0.01) << " " << (sty + 0.01) << " " << qt << " " << qt + 2<< endl;
160 stx = rnd.nextUniformDouble();
161 sty = rnd.nextUniformDouble();
162 qt = rnd.nextUniformLongLong(0, T);
163 cout << T << " " << QUERY << " 9999999 " << stx << " " << sty << " " << (stx + 0.01) << " " << (sty + 0.01) << " " << qt << " " << qt + 2<< endl;
164 stx = rnd.nextUniformDouble();
165 sty = rnd.nextUniformDouble();
166 qt = rnd.nextUniformLongLong(0, T);
167 cout << T << " " << QUERY << " 9999999 " << stx << " " << sty << " " << (stx + 0.01) << " " << (sty + 0.01) << " " << qt << " " << qt + 2<< endl;
168 }
169
170 // delete everything at the end (for testing the special case when the tree dies out completely)
171 for (map<size_t, Region>::iterator it = data.begin(); it != data.end(); it++)
172 {
173 if (! it->second.m_bIsDead)
174 {
175 cout << 102 << " " << DELETE << " " << it->first << " " << it->second.m_xmin << " " << it->second.m_ymin << " "
176 << it->second.m_xmax << " " << it->second.m_ymax << endl;
177 }
178 }
179
180 return 0;
181 }
182