00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030 #include "w_defines.h"
00031
00032
00033
00034 #define SM_SOURCE
00035 #define NBOX_C
00036 #ifdef __GNUC__
00037 # pragma implementation
00038 #endif
00039
00040 #include <w.h>
00041 #include <nbox.h>
00042
00043 #include <cstdlib>
00044 #include <cmath>
00045
00046 #include <iostream>
00047 #include <w_strstream.h>
00048 #include <cstdio>
00049
00050 #ifndef MIN
00051 #define MIN(x,y) ((x) < (y) ? (x) : (y))
00052 #endif
00053
00054 #ifndef MAX
00055 #define MAX(x,y) ((x) > (y) ? (x) : (y))
00056 #endif
00057
00058 #ifndef ABS
00059 #define ABS(x) ((x) >= 0 ? (x) : -(x))
00060 #endif
00061
00062
00063 #ifdef WANT_REGISTER
00064 #define REGISTER register
00065 #else
00066 #define REGISTER
00067 #endif
00068
00069
00070 nbox_t __Null__(0);
00071 nbox_t& nbox_t::Null = __Null__;
00072
00073 const nbox_t::int4_t nbox_t::max_int4 = w_base_t::int4_max;
00074 const nbox_t::int4_t nbox_t::min_int4 = w_base_t::int4_min;
00075
00076 nbox_t::nbox_t(int dimension)
00077 : dim(dimension)
00078 {
00079 w_assert9(dimension <= max_dimension);
00080 #ifdef ZERO_INIT
00081 memset(array, '\0', sizeof(array));
00082 #endif
00083 nullify();
00084 }
00085
00086 nbox_t::nbox_t(const nbox_t& r)
00087 {
00088 *this = r;
00089 }
00090
00091 nbox_t::nbox_t(int dimension, int box[])
00092 : dim(dimension)
00093 {
00094 w_assert9(dimension <= max_dimension);
00095 #ifdef ZERO_INIT
00096 memset(array, '\0', sizeof(array));
00097 #endif
00098 for (int i=0; i<dim; i++) {
00099 array[i] = box[i];
00100 array[i+dim] = box[i+dim];
00101 }
00102 }
00103
00104 nbox_t::nbox_t(const char* s, int len)
00105 : dim(len / (2 * sizeof(int)))
00106 {
00107 w_assert9(dim <= max_dimension);
00108 #ifdef ZERO_INIT
00109 memset(array, '\0', sizeof(array));
00110 #endif
00111 memcpy((void*) array, (void*) s, len);
00112 }
00113
00114
00115
00116
00117
00118 nbox_t::nbox_t(const char* s)
00119 {
00120 #ifdef ZERO_INIT
00121 memset(array, '\0', sizeof(array));
00122 #endif
00123 if (s==NULL) {
00124 dim = max_dimension;
00125 nullify();
00126 return;
00127 }
00128
00129 put(s);
00130 }
00131
00132 bool nbox_t::empty() const
00133 {
00134 return (area() < 0.0);
00135 }
00136
00137 void nbox_t::print(ostream &o, int level) const
00138 {
00139 REGISTER int i, j;
00140 for (j = 0; j < 5 - level; j++) o << "\t";
00141 o << "---------- :\n";
00142
00143 if(dim > 0) {
00144
00145
00146 for (j = 0; j < 5 - level; j++) o << "\t";
00147 o << array[0] ;
00148 for (i=1; i<dim; i++) {
00149 o << "," << array[i] ;
00150 }
00151 o << endl;
00152
00153 for (j = 0; j < 5 - level; j++) o << "\t";
00154 o << array[0+dim] ;
00155 for (i=1; i<dim; i++) {
00156 o << "," << array[i+dim] ;
00157 }
00158 o << endl;
00159 }
00160 if(dim == 0) { o << "<NULL>" <<endl; }
00161 }
00162
00163
00164
00165
00166
00167 void nbox_t::draw(int level, ostream &DrawFile, const nbox_t& CoverAll) const
00168 {
00169 static int seed;
00170 int thick;
00171 double x1, y1, x2, y2;
00172 double ScreenSize, WorldSize;
00173 double ratio, adjust;
00174 double adj,base;
00175
00176 if (empty()) return;
00177
00178 base = 2147483647.0;
00179 ScreenSize = 500.0;
00180 WorldSize = (double)MAX(CoverAll.array[2]-CoverAll.array[0],
00181 CoverAll.array[3]-CoverAll.array[1]);
00182
00183 switch (level-1) {
00184 case 0: thick = 5; break;
00185 case 1: thick = 1; break;
00186 case 2: thick = 4; break;
00187 case 3: thick = 2; break;
00188 case 4: thick = 6; break;
00189 default: thick = 3; break;
00190 }
00191
00192 adjust = 0.0;
00193 if (thick != 5) {
00194 srand(seed);
00195 adj = rand();
00196 adjust = (level-1) * 5.0 + (adj/base) * 5.0 ;
00197 }
00198
00199 ratio = ScreenSize / WorldSize;
00200
00201 if (thick!=5) {
00202 x1 = -1.0*ratio* ABS(array[0])*0.05;
00203 x2 = ratio*ABS(array[2])*0.05;
00204 y1 = -1.0*ratio*ABS(array[1])*0.05;
00205 y2 = ratio*ABS(array[3])*0.05;
00206 } else {
00207 x1 = x2 = y1 = y2 = 0.0;
00208 }
00209
00210 x1 = 32.0 + (array[0] - CoverAll.array[0]) * ratio - adjust;
00211 x2 = 32.0 + (array[2] - CoverAll.array[0]) * ratio + adjust;
00212 y1 = -64.0 + (array[1] - CoverAll.array[1]) * ratio - adjust;
00213 y2 = -64.0 + (array[3] - CoverAll.array[1]) * ratio + adjust;
00214
00215 W_FORM(DrawFile)("VECTOR\n");
00216 W_FORM(DrawFile)("%3.2f %3.2f\n",x1,y1);
00217 W_FORM(DrawFile)("%3.2f %3.2f\n",x2,y1);
00218 W_FORM(DrawFile)("%3.2f %3.2f\n",x2,y2);
00219 W_FORM(DrawFile)("%3.2f %3.2f\n",x1,y2);
00220 W_FORM(DrawFile)("%3.2f %3.2f\n",x1,y1);
00221 W_FORM(DrawFile)("*\n");
00222 W_FORM(DrawFile)("%1d 0\n",thick);
00223 W_FORM(DrawFile)("0\n");
00224 }
00225
00226 bool nbox_t::operator==(const nbox_t& other) const
00227 {
00228 REGISTER int i;
00229
00230 w_assert9(dim == other.dim);
00231
00232 for (i=0; i<dim; i++) {
00233 if (array[i] != other.array[i] || array[i+dim] != other.array[i+dim])
00234 return false;
00235 }
00236 return true;
00237 }
00238
00239 ostream& operator<<(ostream& os, const nbox_t& box)
00240 {
00241 REGISTER int i;
00242
00243 os << "[";
00244 if(box.dim > 0) {
00245
00246
00247 os << "<"<< box.array[0] ;
00248 for (i=1; i<box.dim; i++) {
00249 os << "," << box.array[i] ;
00250 }
00251 os << ">,<" ;
00252
00253 os << box.array[0+box.dim] ;
00254 for (i=1; i<box.dim; i++) {
00255 os << "," << box.array[i+box.dim] ;
00256 }
00257 os << ">";
00258 }
00259 os << "] " << endl;
00260
00261 return os;
00262 }
00263
00264 double nbox_t::area() const
00265 {
00266 if(is_Null()) return -1.0;
00267
00268 REGISTER int i;
00269 int point = true;
00270 int s;
00271 double product = 1.0;
00272 for (i=0; i<dim; i++) {
00273 if ((s=side(i)) < 0) return -1.0;
00274 if ((product *= (double)s) < 0) return (4.0*max_int4*max_int4);
00275 point = (point && !s);
00276 }
00277 if (point) return 1.0;
00278 else return product;
00279 }
00280
00281 int nbox_t::margin()
00282 {
00283 REGISTER int i, sum = 0;
00284 for (i=0; i<dim; i++) {
00285 sum += side(i);
00286 }
00287 return sum;
00288 }
00289
00290
00291
00292
00293
00294 nbox_t nbox_t::operator^(const nbox_t& other) const
00295 {
00296 REGISTER int i;
00297 w_assert1(dim == other.dim);
00298 int box[2*max_dimension];
00299
00300 for (i=0; i<dim; i++) {
00301 box[i] = MAX(array[i], other.array[i]);
00302 box[i+dim] = MIN(array[i+dim], other.array[i+dim]);
00303 }
00304 return nbox_t(dim, box);
00305 }
00306
00307 nbox_t nbox_t::operator+(const nbox_t& other) const
00308 {
00309 REGISTER int i;
00310 w_assert1(dim == other.dim);
00311 int box[2*max_dimension];
00312
00313 for (i=0; i<dim; i++) {
00314 box[i] = MIN(array[i], other.array[i]);
00315 box[i+dim] = MAX(array[i+dim], other.array[i+dim]);
00316 }
00317 return nbox_t(dim, box);
00318 }
00319
00320 nbox_t& nbox_t::operator+=(const nbox_t& other)
00321 {
00322 REGISTER int i;
00323 w_assert1(dim == other.dim);
00324 for (i=0; i<dim; i++) {
00325 array[i] = MIN(array[i], other.array[i]);
00326 array[i+dim] = MAX(array[i+dim], other.array[i+dim]);
00327 }
00328 return *this;
00329 }
00330
00331 bool nbox_t::operator||(const nbox_t& other) const
00332 {
00333 REGISTER int i;
00334
00335 w_assert1(dim == other.dim);
00336
00337 for (i=0; i<dim; i++)
00338 {
00339
00340 if ((array[i] > other.array[i+dim] || array[i+dim] < other.array[i]))
00341 return false;
00342 }
00343 return true;
00344 }
00345
00346 bool nbox_t::operator/(const nbox_t& other) const
00347 {
00348 REGISTER int i;
00349
00350 w_assert9(dim == other.dim);
00351
00352 for (i=0; i<dim; i++)
00353 if (array[i] > other.array[i]) return false;
00354
00355 for (i=dim; i<2*dim; i++)
00356 if (array[i] < other.array[i]) return false;
00357
00358 return true;
00359 }
00360
00361 bool nbox_t::operator>(const nbox_t& other) const
00362 {
00363 REGISTER int i;
00364
00365 w_assert1(dim == other.dim);
00366 for (i=0; i<dim*2; i++) {
00367 if (array[i] > other.array[i]) return true;
00368 else if (array[i] < other.array[i]) return false;
00369 }
00370 return false;
00371 }
00372
00373 bool nbox_t::operator<(const nbox_t& other) const
00374 {
00375 REGISTER int i;
00376
00377 w_assert1(dim == other.dim);
00378 for (i=0; i<dim*2; i++) {
00379 if (array[i] < other.array[i]) return true;
00380 else if (array[i] > other.array[i]) return false;
00381 }
00382 return false;
00383 }
00384
00385 double nbox_t::operator*(const nbox_t& other) const
00386 {
00387 REGISTER int i;
00388 w_assert1(dim == other.dim);
00389 double square = 0.0;
00390 for (i=0; i<dim; i++) {
00391 int diff = array[i]+array[i+dim]-other.array[i]-other.array[i+dim];
00392 square += (diff*diff/4.0);
00393 }
00394 return square;
00395 }
00396
00397
00398
00399
00400
00401
00402 nbox_t::operator char*()
00403 {
00404 static char s[40];
00405 w_ostrstream ss(s, sizeof(s));
00406
00407 W_FORM(ss)("%d.%ld.%ld.%ld.%ld", dim,
00408 array[0], array[1], array[2], array[3]);
00409 ss << ends;
00410
00411 return s;
00412 }
00413
00414 void nbox_t::bytes2box(const char* key, int klen)
00415 {
00416 dim = klen / (2*sizeof(int));
00417 memcpy((void*) array, (void*) key, klen);
00418 }
00419
00420
00421
00422
00423
00424 void nbox_t::put(const char* s)
00425 {
00426 int n;
00427 n = sscanf(C_STRING_BUG s, "%d.%d.%d.%d.%d", &dim,
00428 &array[0], &array[1], &array[2], &array[3]);
00429 w_assert1(n==5 && dim == 2);
00430 for (int i=2*dim; i<2*max_dimension; i++) {
00431 array[i] = 0;
00432 }
00433 }
00434
00435
00436
00437
00438 void nbox_t::squared()
00439 {
00440 int x_side = side(0);
00441 int y_side = side(1);
00442
00443 if (x_side > y_side) {
00444 array[1] -= (x_side-y_side)/2;
00445 array[3] += (x_side-y_side)/2;
00446 } else {
00447 array[0] -= (y_side-x_side)/2;
00448 array[2] += (y_side-x_side)/2;
00449 }
00450 }
00451
00452 void nbox_t::nullify()
00453 {
00454 for (int i=0; i<dim; i++) {
00455 array[i] = max_int4;
00456 array[i+dim] = min_int4;
00457 }
00458 }
00459
00460
00461
00462
00463 static const int rotation_table[4] = { 3, 0, 0, 1};
00464 static const int sense_table[4] = {-1, 1, 1, -1};
00465 static const int quad_table[4][2][2] = { {{0,1}, {3,2}}, {{1,2}, {0,3}},
00466 {{2,3}, {1,0}}, {{3,0}, {2,1}} };
00467
00468
00469 #ifdef WINNT
00470
00471 #undef log2
00472 #endif
00473
00474 static int log2(int value)
00475 {
00476 int ground = 1;
00477 REGISTER int i = 0;
00478 while (( ground = (ground<<1)) <= value) i++;
00479 return i;
00480 }
00481
00482 static int power(int base, int index)
00483 {
00484 REGISTER int val = 1;
00485 for (int i=0; i<index; i++) val *= base;
00486 return val;
00487 }
00488
00489
00490
00491
00492 int nbox_t::hvalue(const nbox_t& universe, int level) const
00493 {
00494 int min_side = MIN(universe.side(0), universe.side(1));
00495 if (level == 0)
00496 level = MIN(14, log2(min_side) );
00497
00498 int x_low = universe.bound(0), y_low = universe.bound(1);
00499 int ret_val = 0;
00500 int x = center(0), y = center(1);
00501
00502 int count = 0, rotation = 0, sense = 1;
00503
00504 REGISTER int i,j;
00505 for ( i=(universe.side(0)+1)/2, j=(universe.side(1)+1)/2;
00506 i>0 && j>0 && level>count; i=i/2, j=j/2) {
00507 count++;
00508 int x_val = (x - x_low) < i ? 0 : 1;
00509 int y_val = (y - y_low) < j ? 0 : 1;
00510 int quad = quad_table[rotation][x_val][y_val];
00511 x_low += (i*x_val);
00512 y_low += (j*y_val);
00513 ret_val += ((((sense==-1)?(3-quad):quad)-1)*power(4,level-count));
00514 rotation = (rotation + rotation_table[quad]) % 4;
00515
00516 sense *= sense_table[quad];
00517 }
00518
00519 return ret_val;
00520 }
00521
00522 int nbox_t::hcmp(const nbox_t& other, const nbox_t& universe, int level) const
00523 {
00524 int min_side = MIN(universe.side(0), universe.side(1));
00525 if (level == 0)
00526 level = MIN(14, log2(min_side) );
00527
00528 int x_low = universe.bound(0), y_low = universe.bound(1);
00529 int val1, val2;
00530 int x1 = center(0), y1 = center(1),
00531 x2 = other.center(0), y2 = other.center(1);
00532 int count = 0, rotation = 0, sense = 1;
00533
00534 REGISTER int i,j;
00535 for ( i=(universe.side(0)+1)/2, j=(universe.side(1)+1)/2;
00536 i>0 && j>0 && level>count; i=i/2, j=j/2) {
00537 count++;
00538 int x_val = (x2 - x_low) < i ? 0 : 1;
00539 int y_val = (y2 - y_low) < j ? 0 : 1;
00540 int quad = quad_table[rotation][x_val][y_val];
00541 val2 = (sense==-1)?(3-quad):quad;
00542 x_val = (x1 - x_low) < i ? 0 : 1;
00543 y_val = (y1 - y_low) < j ? 0 : 1;
00544 quad = quad_table[rotation][x_val][y_val];
00545 val1 = (sense==-1)?(3-quad):quad;
00546 if (val1!=val2) return (val1-val2);
00547
00548 rotation = (rotation + rotation_table[quad]) % 4;
00549 sense *= sense_table[quad];
00550 x_low += (i*x_val);
00551 y_low += (j*y_val);
00552 }
00553
00554 return 0;
00555 }
00556
00557 void
00558 nbox_t::canonize()
00559 {
00560 int x;
00561 for (int i=0; i<dim; i++) {
00562 if(array[i] > array[i+dim]) {
00563
00564 x = array[i];
00565 array[i] = array[i+dim];
00566 array[i+dim] = x;
00567 }
00568 }
00569 }