1 /* 2 =========================================================================== 3 Copyright (C) 2000 - 2013, Raven Software, Inc. 4 Copyright (C) 2001 - 2013, Activision, Inc. 5 Copyright (C) 2013 - 2015, OpenJK contributors 6 7 This file is part of the OpenJK source code. 8 9 OpenJK is free software; you can redistribute it and/or modify it 10 under the terms of the GNU General Public License version 2 as 11 published by the Free Software Foundation. 12 13 This program is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with this program; if not, see <http://www.gnu.org/licenses/>. 20 =========================================================================== 21 */ 22 23 //////////////////////////////////////////////////////////////////////////////////////// 24 // RAVEN STANDARD TEMPLATE LIBRARY 25 // (c) 2002 Activision 26 // 27 // 28 // Grid 29 // ---- 30 // There are two versions of the Grid class. Simply, they apply a discreet function 31 // mapping from a n dimensional space to a linear aray. 32 // 33 // 34 // 35 // 36 // 37 // 38 // NOTES: 39 // 40 // 41 // 42 //////////////////////////////////////////////////////////////////////////////////////// 43 #if !defined(RATL_GRID_VS_INC) 44 #define RATL_GRID_VS_INC 45 46 47 //////////////////////////////////////////////////////////////////////////////////////// 48 // Includes 49 //////////////////////////////////////////////////////////////////////////////////////// 50 #if !defined(RATL_COMMON_INC) 51 #include "ratl_common.h" 52 #endif 53 #if !defined(RATL_ARRAY_VS) 54 #include "array_vs.h" 55 #endif 56 namespace ratl 57 { 58 59 60 61 //////////////////////////////////////////////////////////////////////////////////////// 62 // The 2D Grid Class 63 //////////////////////////////////////////////////////////////////////////////////////// 64 template <class T, int XSIZE_MAX, int YSIZE_MAX> 65 class grid2_vs : public ratl_base 66 { 67 public: 68 //////////////////////////////////////////////////////////////////////////////////// 69 // Constructor 70 //////////////////////////////////////////////////////////////////////////////////// grid2_vs()71 grid2_vs() 72 { 73 clear(); 74 } 75 76 enum 77 { 78 RANGE_NULL = 12345, 79 }; 80 81 82 //////////////////////////////////////////////////////////////////////////////////// 83 // Assignment Operator 84 //////////////////////////////////////////////////////////////////////////////////// 85 grid2_vs& operator=(const grid2_vs& other) 86 { 87 mData = other.mData; 88 for (int i=0; i<2; i++) 89 { 90 mSize[i] = other.mSize[i]; 91 mMins[i] = other.mMins[i]; 92 mMaxs[i] = other.mMaxs[i]; 93 mScale[i] = other.mScale[i]; 94 } 95 return (*this); 96 } 97 set_size(int xSize,int ySize)98 void set_size(int xSize, int ySize) 99 { 100 if (xSize<XSIZE_MAX) 101 { 102 mSize[0] = xSize; 103 } 104 if (ySize<YSIZE_MAX) 105 { 106 mSize[1] = ySize; 107 } 108 } 109 snap_scale()110 void snap_scale() 111 { 112 mScale[0] = (float)((int)(mScale[0])); 113 mScale[1] = (float)((int)(mScale[1])); 114 } 115 get_size(int & xSize,int & ySize)116 void get_size(int& xSize, int& ySize) 117 { 118 xSize = mSize[0]; 119 ySize = mSize[1]; 120 } 121 122 123 124 //////////////////////////////////////////////////////////////////////////////////// 125 // Clear 126 //////////////////////////////////////////////////////////////////////////////////// clear()127 void clear() 128 { 129 mSize[0] = XSIZE_MAX; 130 mSize[1] = YSIZE_MAX; 131 mData.clear(); 132 for (int i=0; i<2; i++) 133 { 134 mMins[i] = RANGE_NULL; 135 mMaxs[i] = RANGE_NULL; 136 mScale[i] = 0.0f; 137 } 138 } 139 140 141 //////////////////////////////////////////////////////////////////////////////////// 142 // Initialize The Entire Grid To A Value 143 //////////////////////////////////////////////////////////////////////////////////// init(const T & val)144 void init(const T& val) 145 { 146 for (int i=0; i<(XSIZE_MAX*YSIZE_MAX); i++) 147 { 148 mData[i] = val; 149 } 150 } 151 152 //////////////////////////////////////////////////////////////////////////////////// 153 // Copy The Bounds Of Another Grid 154 //////////////////////////////////////////////////////////////////////////////////// copy_bounds(const grid2_vs & other)155 void copy_bounds(const grid2_vs& other) 156 { 157 for (int i=0; i<2; i++) 158 { 159 mSize[i] = other.mSize[i]; 160 mMins[i] = other.mMins[i]; 161 mMaxs[i] = other.mMaxs[i]; 162 mScale[i] = other.mScale[i]; 163 } 164 } 165 166 //////////////////////////////////////////////////////////////////////////////////// 167 // Accessor 168 //////////////////////////////////////////////////////////////////////////////////// get(const int x,const int y)169 T& get(const int x, const int y) 170 { 171 assert(x>=0 && y>=0 && x<mSize[0] && y<mSize[1]); 172 return mData[(x + y*XSIZE_MAX)]; 173 } 174 175 //////////////////////////////////////////////////////////////////////////////////// 176 // Accessor 177 //////////////////////////////////////////////////////////////////////////////////// get(float x,float y)178 T& get(float x, float y) 179 { 180 assert(mScale[0]!=0.0f && mScale[1]!=0.0f); 181 truncate_position_to_bounds(x, y); 182 183 int xint = (int)( (x-mMins[0]) / mScale[0] ); 184 int yint = (int)( (y-mMins[1]) / mScale[1] ); 185 186 assert(xint>=0 && yint>=0 && xint<mSize[0] && yint<mSize[1]); 187 return mData[(xint + yint*XSIZE_MAX)]; 188 } 189 190 //////////////////////////////////////////////////////////////////////////////////// 191 // Convert The Scaled Coordinates To A Grid Coordinate 192 //////////////////////////////////////////////////////////////////////////////////// get_cell_coords(float x,float y,int & xint,int & yint)193 void get_cell_coords(float x, float y, int& xint, int& yint) 194 { 195 assert(mScale[0]!=0.0f && mScale[1]!=0.0f); 196 truncate_position_to_bounds(x, y); 197 198 xint = (int)( (x-mMins[0]) / mScale[0] ); 199 yint = (int)( (y-mMins[1]) / mScale[1] ); 200 201 assert(xint>=0 && yint>=0 && xint<mSize[0] && yint<mSize[1]); 202 } 203 204 //////////////////////////////////////////////////////////////////////////////////// 205 // Expand 206 // 207 // NOTE: This MUST be at least a 2 dimensional point 208 //////////////////////////////////////////////////////////////////////////////////// expand_bounds(float xReal,float yReal)209 void expand_bounds(float xReal, float yReal) 210 { 211 float point[2] = {xReal, yReal}; 212 for (int i=0; i<2; i++) 213 { 214 if (point[i]<mMins[i] || mMins[i]==RANGE_NULL) 215 { 216 mMins[i] = point[i]; 217 } 218 if (point[i]>mMaxs[i] || mMaxs[i]==RANGE_NULL) 219 { 220 mMaxs[i] = point[i]; 221 } 222 } 223 assert(mSize[0]>0 && mSize[1]>0); 224 225 mScale[0] = ((mMaxs[0] - mMins[0])/mSize[0]); 226 mScale[1] = ((mMaxs[1] - mMins[1])/mSize[1]); 227 } 228 229 //////////////////////////////////////////////////////////////////////////////////// 230 // 231 //////////////////////////////////////////////////////////////////////////////////// truncate_position_to_bounds(float & xReal,float & yReal)232 void truncate_position_to_bounds(float& xReal, float& yReal) 233 { 234 if (xReal<mMins[0]) 235 { 236 xReal = mMins[0]; 237 } 238 if (xReal>(mMaxs[0]-1.0f)) 239 { 240 xReal = mMaxs[0]-1.0f; 241 } 242 if (yReal<mMins[1]) 243 { 244 yReal = mMins[1]; 245 } 246 if (yReal>(mMaxs[1]-1.0f)) 247 { 248 yReal = mMaxs[1]-1.0f; 249 } 250 } 251 252 //////////////////////////////////////////////////////////////////////////////////// 253 // 254 //////////////////////////////////////////////////////////////////////////////////// get_cell_position(int x,int y,float & xReal,float & yReal)255 void get_cell_position(int x, int y, float& xReal, float& yReal) 256 { 257 // assert(mScale[0]!=0.0f && mScale[1]!=0.0f); 258 xReal = (x * mScale[0]) + mMins[0] + (mScale[0] * 0.5f); 259 yReal = (y * mScale[1]) + mMins[1] + (mScale[1] * 0.5f); 260 } get_cell_upperleft(int x,int y,float & xReal,float & yReal)261 void get_cell_upperleft(int x, int y, float& xReal, float& yReal) 262 { 263 // assert(mScale[0]!=0.0f && mScale[1]!=0.0f); 264 xReal = (x * mScale[0]) + mMins[0]; 265 yReal = (y * mScale[1]) + mMins[1]; 266 } get_cell_lowerright(int x,int y,float & xReal,float & yReal)267 void get_cell_lowerright(int x, int y, float& xReal, float& yReal) 268 { 269 // assert(mScale[0]!=0.0f && mScale[1]!=0.0f); 270 xReal = (x * mScale[0]) + mMins[0] + (mScale[0]); 271 yReal = (y * mScale[1]) + mMins[1] + (mScale[1]); 272 } scale_by_largest_axis(float & dist)273 void scale_by_largest_axis(float& dist) 274 { 275 assert(mScale[0]!=0.0f && mScale[1]!=0.0f); 276 if (mScale[0]>mScale[1]) 277 { 278 dist /= mScale[0]; 279 } 280 else 281 { 282 dist /= mScale[1]; 283 } 284 } 285 286 287 288 289 //////////////////////////////////////////////////////////////////////////////////// 290 // Data 291 //////////////////////////////////////////////////////////////////////////////////// 292 private: 293 array_vs<T, XSIZE_MAX*YSIZE_MAX> mData; 294 295 int mSize[2]; 296 float mMins[2]; 297 float mMaxs[2]; 298 float mScale[2]; 299 300 301 302 303 public: 304 //////////////////////////////////////////////////////////////////////////////////// 305 // Raw Get - For The Iterator Dereference Function 306 //////////////////////////////////////////////////////////////////////////////////// rawGet(int Loc)307 T& rawGet(int Loc) 308 { 309 assert(Loc>=0 && Loc<XSIZE_MAX*YSIZE_MAX); 310 return mData[Loc]; 311 } 312 313 314 315 //////////////////////////////////////////////////////////////////////////////////// 316 // Iterator 317 //////////////////////////////////////////////////////////////////////////////////// 318 class iterator 319 { 320 public: 321 322 // Constructors 323 //-------------- iterator()324 iterator() {} iterator(grid2_vs * p,int t)325 iterator(grid2_vs* p, int t) : mOwner(p), mLoc(t) {} 326 327 // Assignment Operator 328 //--------------------- 329 void operator= (const iterator &t) {mOwner=t.mOwner; mLoc=t.mLoc;} 330 331 // Equality & Inequality Operators 332 //--------------------------------- 333 bool operator!=(const iterator &t) {return (mLoc!=t.mLoc);} 334 bool operator==(const iterator &t) {return (mLoc==t.mLoc);} 335 336 // Dereference Operator 337 //---------------------- 338 T& operator* () {return (mOwner->rawGet(mLoc));} 339 340 // Inc Operator 341 //-------------- 342 void operator++(int) {mLoc++;} 343 344 345 // Row & Col Offsets 346 //------------------- offsetRows(int num)347 void offsetRows(int num) {mLoc += (YSIZE_MAX*num);} offsetCols(int num)348 void offsetCols(int num) {mLoc += (num);} 349 350 351 // Return True If On Frist Column Of A Row 352 //----------------------------------------- onColZero()353 bool onColZero() 354 { 355 return (mLoc%XSIZE_MAX)==0; 356 } 357 358 // Evaluate The XY Position Of This Iterator 359 //------------------------------------------- position(int & X,int & Y)360 void position(int& X, int& Y) 361 { 362 Y = mLoc / XSIZE_MAX; 363 X = mLoc - (Y*XSIZE_MAX); 364 } 365 366 private: 367 int mLoc; 368 grid2_vs* mOwner; 369 }; 370 371 //////////////////////////////////////////////////////////////////////////////////// 372 // Iterator Begin 373 //////////////////////////////////////////////////////////////////////////////////// 374 iterator begin(int x=0, int y=0) 375 { 376 assert(x>=0 && y>=0 && x<mSize[0] && y<mSize[1]); 377 378 return iterator(this, (x + y*XSIZE_MAX)); 379 } 380 381 //////////////////////////////////////////////////////////////////////////////////// 382 // Iterator Begin (scaled position, use mins and maxs to calc real position) 383 //////////////////////////////////////////////////////////////////////////////////// begin(float xReal,float yReal)384 iterator begin(float xReal, float yReal) 385 { 386 assert(mScale[0]!=0.0f && mScale[1]!=0.0f); 387 truncate_position_to_bounds(xReal, yReal); 388 389 int x = (int)( (xReal-mMins[0]) / mScale[0] ); 390 int y = (int)( (yReal-mMins[1]) / mScale[1] ); 391 392 return begin(x,y); 393 } 394 395 //////////////////////////////////////////////////////////////////////////////////// 396 // Iterator End 397 //////////////////////////////////////////////////////////////////////////////////// end()398 iterator end() 399 { 400 return iterator(this, (XSIZE_MAX*YSIZE_MAX)); 401 } 402 403 404 405 406 407 408 409 410 //////////////////////////////////////////////////////////////////////////////////// 411 // Ranged Iterator 412 //////////////////////////////////////////////////////////////////////////////////// 413 class riterator 414 { 415 public: 416 417 // Constructors 418 //-------------- riterator()419 riterator() 420 {} riterator(grid2_vs * p,int Range,int SX,int SY)421 riterator(grid2_vs* p, int Range, int SX, int SY) : 422 mOwner(p) 423 { 424 int Start[2] = {SX, SY}; 425 int Bounds[2] = {XSIZE_MAX-1, YSIZE_MAX-1}; 426 427 for (int i=0; i<2; i++) 428 { 429 mMins[i] = Start[i] - Range; 430 mMaxs[i] = Start[i] + Range; 431 432 if (mMins[i]<0) 433 { 434 mMins[i] = 0; 435 } 436 if (mMaxs[i] > Bounds[i]) 437 { 438 mMaxs[i] = Bounds[i]; 439 } 440 441 mLoc[i] = mMins[i]; 442 } 443 } 444 445 // Assignment Operator 446 //--------------------- 447 void operator= (const riterator &t) 448 { 449 mOwner = t.mOwner; 450 for (int i=0; i<2; i++) 451 { 452 mMins[i] = t.mMins[i]; 453 mMaxs[i] = t.mMaxs[i]; 454 mLoc[i] = t.mLoc[i]; 455 } 456 } 457 458 // Equality & Inequality Operators 459 //--------------------------------- 460 bool operator!=(const riterator &t) 461 { 462 return (mLoc[0]!=t.mLoc[0] || mLoc[1]!=t.mLoc[1]); 463 } 464 bool operator==(const riterator &t) 465 { 466 return (mLoc[0]==t.mLoc[0] && mLoc[1]==t.mLoc[1]); 467 } 468 469 // Dereference Operator 470 //---------------------- 471 T& operator* () 472 { 473 return (mOwner->get(mLoc[0], mLoc[1])); 474 } 475 476 // Inc Operator 477 //-------------- 478 void operator++(int) 479 { 480 if (mLoc[1] <= mMaxs[1]) 481 { 482 mLoc[0]++; 483 if (mLoc[0]>(mMaxs[0])) 484 { 485 mLoc[0] = mMins[0]; 486 mLoc[1]++; 487 } 488 } 489 } 490 at_end()491 bool at_end() 492 { 493 return (mLoc[1]>mMaxs[1]); 494 } 495 496 497 // Return True If On Frist Column Of A Row 498 //----------------------------------------- onColZero()499 bool onColZero() 500 { 501 return (mLoc[0]==mMins[0]); 502 } 503 504 // Evaluate The XY Position Of This Iterator 505 //------------------------------------------- position(int & X,int & Y)506 void position(int& X, int& Y) 507 { 508 Y = mLoc[1]; 509 X = mLoc[0]; 510 } 511 512 private: 513 int mMins[2]; 514 int mMaxs[2]; 515 int mLoc[2]; 516 grid2_vs* mOwner; 517 }; 518 519 //////////////////////////////////////////////////////////////////////////////////// 520 // Ranged Iterator Begin (x and y are the center of the range) 521 //////////////////////////////////////////////////////////////////////////////////// rangeBegin(int range,int x,int y)522 riterator rangeBegin(int range, int x, int y) 523 { 524 assert(x>=0 && y>=0 && x<XSIZE_MAX && y<YSIZE_MAX); 525 return riterator(this, range, x, y); 526 } 527 528 //////////////////////////////////////////////////////////////////////////////////// 529 // 530 //////////////////////////////////////////////////////////////////////////////////// rangeBegin(int range,float xReal,float yReal)531 riterator rangeBegin(int range, float xReal, float yReal) 532 { 533 float position[2] = {xReal, yReal}; 534 assert(mScale[0]!=0.0f && mScale[1]!=0.0f); 535 truncate_position_to_bounds(xReal, yReal); 536 int x = ( (position[0]-mMins[0]) / mScale[0] ); 537 int y = ( (position[1]-mMins[1]) / mScale[1] ); 538 539 assert(x>=0 && y>=0 && x<XSIZE_MAX && y<YSIZE_MAX); 540 return riterator(this, range, x, y); 541 } 542 }; 543 544 } 545 #endif 546 547 548 549