oculus1

annotate libovr/Src/Kernel/OVR_Alg.h @ 1:e2f9e4603129

find changesets by author, revision, files, or words in the commit message
added LibOVR and started a simple vr wrapper.
author John Tsiombikas <nuclear@member.fsf.org>
date Sat, 14 Sep 2013 16:14:59 +0300
parents
children b069a5c27388
rev   line source
nuclear@1 1 /************************************************************************************
nuclear@1 2
nuclear@1 3 PublicHeader: OVR.h
nuclear@1 4 Filename : OVR_Alg.h
nuclear@1 5 Content : Simple general purpose algorithms: Sort, Binary Search, etc.
nuclear@1 6 Created : September 19, 2012
nuclear@1 7 Notes :
nuclear@1 8
nuclear@1 9 Copyright : Copyright 2012 Oculus VR, Inc. All Rights reserved.
nuclear@1 10
nuclear@1 11 Use of this software is subject to the terms of the Oculus license
nuclear@1 12 agreement provided at the time of installation or download, or which
nuclear@1 13 otherwise accompanies this software in either electronic or hard copy form.
nuclear@1 14
nuclear@1 15 ************************************************************************************/
nuclear@1 16
nuclear@1 17 #ifndef OVR_Alg_h
nuclear@1 18 #define OVR_Alg_h
nuclear@1 19
nuclear@1 20 #include "OVR_Types.h"
nuclear@1 21 #include <string.h>
nuclear@1 22
nuclear@1 23 namespace OVR { namespace Alg {
nuclear@1 24
nuclear@1 25
nuclear@1 26 //-----------------------------------------------------------------------------------
nuclear@1 27 // ***** Operator extensions
nuclear@1 28
nuclear@1 29 template <typename T> OVR_FORCE_INLINE void Swap(T &a, T &b)
nuclear@1 30 { T temp(a); a = b; b = temp; }
nuclear@1 31
nuclear@1 32
nuclear@1 33 // ***** min/max are not implemented in Visual Studio 6 standard STL
nuclear@1 34
nuclear@1 35 template <typename T> OVR_FORCE_INLINE const T Min(const T a, const T b)
nuclear@1 36 { return (a < b) ? a : b; }
nuclear@1 37
nuclear@1 38 template <typename T> OVR_FORCE_INLINE const T Max(const T a, const T b)
nuclear@1 39 { return (b < a) ? a : b; }
nuclear@1 40
nuclear@1 41 template <typename T> OVR_FORCE_INLINE const T Clamp(const T v, const T minVal, const T maxVal)
nuclear@1 42 { return Max<T>(minVal, Min<T>(v, maxVal)); }
nuclear@1 43
nuclear@1 44 template <typename T> OVR_FORCE_INLINE int Chop(T f)
nuclear@1 45 { return (int)f; }
nuclear@1 46
nuclear@1 47 template <typename T> OVR_FORCE_INLINE T Lerp(T a, T b, T f)
nuclear@1 48 { return (b - a) * f + a; }
nuclear@1 49
nuclear@1 50
nuclear@1 51 // These functions stand to fix a stupid VC++ warning (with /Wp64 on):
nuclear@1 52 // "warning C4267: 'argument' : conversion from 'size_t' to 'const unsigned', possible loss of data"
nuclear@1 53 // Use these functions instead of gmin/gmax if the argument has size
nuclear@1 54 // of the pointer to avoid the warning. Though, functionally they are
nuclear@1 55 // absolutelly the same as regular gmin/gmax.
nuclear@1 56 template <typename T> OVR_FORCE_INLINE const T PMin(const T a, const T b)
nuclear@1 57 {
nuclear@1 58 OVR_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt));
nuclear@1 59 return (a < b) ? a : b;
nuclear@1 60 }
nuclear@1 61 template <typename T> OVR_FORCE_INLINE const T PMax(const T a, const T b)
nuclear@1 62 {
nuclear@1 63 OVR_COMPILER_ASSERT(sizeof(T) == sizeof(UPInt));
nuclear@1 64 return (b < a) ? a : b;
nuclear@1 65 }
nuclear@1 66
nuclear@1 67
nuclear@1 68 template <typename T> OVR_FORCE_INLINE const T Abs(const T v)
nuclear@1 69 { return (v>=0) ? v : -v; }
nuclear@1 70
nuclear@1 71
nuclear@1 72 //-----------------------------------------------------------------------------------
nuclear@1 73 // ***** OperatorLess
nuclear@1 74 //
nuclear@1 75 template<class T> struct OperatorLess
nuclear@1 76 {
nuclear@1 77 static bool Compare(const T& a, const T& b)
nuclear@1 78 {
nuclear@1 79 return a < b;
nuclear@1 80 }
nuclear@1 81 };
nuclear@1 82
nuclear@1 83
nuclear@1 84 //-----------------------------------------------------------------------------------
nuclear@1 85 // ***** QuickSortSliced
nuclear@1 86 //
nuclear@1 87 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
nuclear@1 88 // The range is specified with start, end, where "end" is exclusive!
nuclear@1 89 // The comparison predicate must be specified.
nuclear@1 90 template<class Array, class Less>
nuclear@1 91 void QuickSortSliced(Array& arr, UPInt start, UPInt end, Less less)
nuclear@1 92 {
nuclear@1 93 enum
nuclear@1 94 {
nuclear@1 95 Threshold = 9
nuclear@1 96 };
nuclear@1 97
nuclear@1 98 if(end - start < 2) return;
nuclear@1 99
nuclear@1 100 SPInt stack[80];
nuclear@1 101 SPInt* top = stack;
nuclear@1 102 SPInt base = (SPInt)start;
nuclear@1 103 SPInt limit = (SPInt)end;
nuclear@1 104
nuclear@1 105 for(;;)
nuclear@1 106 {
nuclear@1 107 SPInt len = limit - base;
nuclear@1 108 SPInt i, j, pivot;
nuclear@1 109
nuclear@1 110 if(len > Threshold)
nuclear@1 111 {
nuclear@1 112 // we use base + len/2 as the pivot
nuclear@1 113 pivot = base + len / 2;
nuclear@1 114 Swap(arr[base], arr[pivot]);
nuclear@1 115
nuclear@1 116 i = base + 1;
nuclear@1 117 j = limit - 1;
nuclear@1 118
nuclear@1 119 // now ensure that *i <= *base <= *j
nuclear@1 120 if(less(arr[j], arr[i])) Swap(arr[j], arr[i]);
nuclear@1 121 if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
nuclear@1 122 if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
nuclear@1 123
nuclear@1 124 for(;;)
nuclear@1 125 {
nuclear@1 126 do i++; while( less(arr[i], arr[base]) );
nuclear@1 127 do j--; while( less(arr[base], arr[j]) );
nuclear@1 128
nuclear@1 129 if( i > j )
nuclear@1 130 {
nuclear@1 131 break;
nuclear@1 132 }
nuclear@1 133
nuclear@1 134 Swap(arr[i], arr[j]);
nuclear@1 135 }
nuclear@1 136
nuclear@1 137 Swap(arr[base], arr[j]);
nuclear@1 138
nuclear@1 139 // now, push the largest sub-array
nuclear@1 140 if(j - base > limit - i)
nuclear@1 141 {
nuclear@1 142 top[0] = base;
nuclear@1 143 top[1] = j;
nuclear@1 144 base = i;
nuclear@1 145 }
nuclear@1 146 else
nuclear@1 147 {
nuclear@1 148 top[0] = i;
nuclear@1 149 top[1] = limit;
nuclear@1 150 limit = j;
nuclear@1 151 }
nuclear@1 152 top += 2;
nuclear@1 153 }
nuclear@1 154 else
nuclear@1 155 {
nuclear@1 156 // the sub-array is small, perform insertion sort
nuclear@1 157 j = base;
nuclear@1 158 i = j + 1;
nuclear@1 159
nuclear@1 160 for(; i < limit; j = i, i++)
nuclear@1 161 {
nuclear@1 162 for(; less(arr[j + 1], arr[j]); j--)
nuclear@1 163 {
nuclear@1 164 Swap(arr[j + 1], arr[j]);
nuclear@1 165 if(j == base)
nuclear@1 166 {
nuclear@1 167 break;
nuclear@1 168 }
nuclear@1 169 }
nuclear@1 170 }
nuclear@1 171 if(top > stack)
nuclear@1 172 {
nuclear@1 173 top -= 2;
nuclear@1 174 base = top[0];
nuclear@1 175 limit = top[1];
nuclear@1 176 }
nuclear@1 177 else
nuclear@1 178 {
nuclear@1 179 break;
nuclear@1 180 }
nuclear@1 181 }
nuclear@1 182 }
nuclear@1 183 }
nuclear@1 184
nuclear@1 185
nuclear@1 186 //-----------------------------------------------------------------------------------
nuclear@1 187 // ***** QuickSortSliced
nuclear@1 188 //
nuclear@1 189 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
nuclear@1 190 // The range is specified with start, end, where "end" is exclusive!
nuclear@1 191 // The data type must have a defined "<" operator.
nuclear@1 192 template<class Array>
nuclear@1 193 void QuickSortSliced(Array& arr, UPInt start, UPInt end)
nuclear@1 194 {
nuclear@1 195 typedef typename Array::ValueType ValueType;
nuclear@1 196 QuickSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
nuclear@1 197 }
nuclear@1 198
nuclear@1 199 // Same as corresponding G_QuickSortSliced but with checking array limits to avoid
nuclear@1 200 // crash in the case of wrong comparator functor.
nuclear@1 201 template<class Array, class Less>
nuclear@1 202 bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end, Less less)
nuclear@1 203 {
nuclear@1 204 enum
nuclear@1 205 {
nuclear@1 206 Threshold = 9
nuclear@1 207 };
nuclear@1 208
nuclear@1 209 if(end - start < 2) return true;
nuclear@1 210
nuclear@1 211 SPInt stack[80];
nuclear@1 212 SPInt* top = stack;
nuclear@1 213 SPInt base = (SPInt)start;
nuclear@1 214 SPInt limit = (SPInt)end;
nuclear@1 215
nuclear@1 216 for(;;)
nuclear@1 217 {
nuclear@1 218 SPInt len = limit - base;
nuclear@1 219 SPInt i, j, pivot;
nuclear@1 220
nuclear@1 221 if(len > Threshold)
nuclear@1 222 {
nuclear@1 223 // we use base + len/2 as the pivot
nuclear@1 224 pivot = base + len / 2;
nuclear@1 225 Swap(arr[base], arr[pivot]);
nuclear@1 226
nuclear@1 227 i = base + 1;
nuclear@1 228 j = limit - 1;
nuclear@1 229
nuclear@1 230 // now ensure that *i <= *base <= *j
nuclear@1 231 if(less(arr[j], arr[i])) Swap(arr[j], arr[i]);
nuclear@1 232 if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
nuclear@1 233 if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
nuclear@1 234
nuclear@1 235 for(;;)
nuclear@1 236 {
nuclear@1 237 do
nuclear@1 238 {
nuclear@1 239 i++;
nuclear@1 240 if (i >= limit)
nuclear@1 241 return false;
nuclear@1 242 } while( less(arr[i], arr[base]) );
nuclear@1 243 do
nuclear@1 244 {
nuclear@1 245 j--;
nuclear@1 246 if (j < 0)
nuclear@1 247 return false;
nuclear@1 248 } while( less(arr[base], arr[j]) );
nuclear@1 249
nuclear@1 250 if( i > j )
nuclear@1 251 {
nuclear@1 252 break;
nuclear@1 253 }
nuclear@1 254
nuclear@1 255 Swap(arr[i], arr[j]);
nuclear@1 256 }
nuclear@1 257
nuclear@1 258 Swap(arr[base], arr[j]);
nuclear@1 259
nuclear@1 260 // now, push the largest sub-array
nuclear@1 261 if(j - base > limit - i)
nuclear@1 262 {
nuclear@1 263 top[0] = base;
nuclear@1 264 top[1] = j;
nuclear@1 265 base = i;
nuclear@1 266 }
nuclear@1 267 else
nuclear@1 268 {
nuclear@1 269 top[0] = i;
nuclear@1 270 top[1] = limit;
nuclear@1 271 limit = j;
nuclear@1 272 }
nuclear@1 273 top += 2;
nuclear@1 274 }
nuclear@1 275 else
nuclear@1 276 {
nuclear@1 277 // the sub-array is small, perform insertion sort
nuclear@1 278 j = base;
nuclear@1 279 i = j + 1;
nuclear@1 280
nuclear@1 281 for(; i < limit; j = i, i++)
nuclear@1 282 {
nuclear@1 283 for(; less(arr[j + 1], arr[j]); j--)
nuclear@1 284 {
nuclear@1 285 Swap(arr[j + 1], arr[j]);
nuclear@1 286 if(j == base)
nuclear@1 287 {
nuclear@1 288 break;
nuclear@1 289 }
nuclear@1 290 }
nuclear@1 291 }
nuclear@1 292 if(top > stack)
nuclear@1 293 {
nuclear@1 294 top -= 2;
nuclear@1 295 base = top[0];
nuclear@1 296 limit = top[1];
nuclear@1 297 }
nuclear@1 298 else
nuclear@1 299 {
nuclear@1 300 break;
nuclear@1 301 }
nuclear@1 302 }
nuclear@1 303 }
nuclear@1 304 return true;
nuclear@1 305 }
nuclear@1 306
nuclear@1 307 template<class Array>
nuclear@1 308 bool QuickSortSlicedSafe(Array& arr, UPInt start, UPInt end)
nuclear@1 309 {
nuclear@1 310 typedef typename Array::ValueType ValueType;
nuclear@1 311 return QuickSortSlicedSafe(arr, start, end, OperatorLess<ValueType>::Compare);
nuclear@1 312 }
nuclear@1 313
nuclear@1 314 //-----------------------------------------------------------------------------------
nuclear@1 315 // ***** QuickSort
nuclear@1 316 //
nuclear@1 317 // Sort an array Array, ArrayPaged, ArrayUnsafe.
nuclear@1 318 // The array must have GetSize() function.
nuclear@1 319 // The comparison predicate must be specified.
nuclear@1 320 template<class Array, class Less>
nuclear@1 321 void QuickSort(Array& arr, Less less)
nuclear@1 322 {
nuclear@1 323 QuickSortSliced(arr, 0, arr.GetSize(), less);
nuclear@1 324 }
nuclear@1 325
nuclear@1 326 // checks for boundaries
nuclear@1 327 template<class Array, class Less>
nuclear@1 328 bool QuickSortSafe(Array& arr, Less less)
nuclear@1 329 {
nuclear@1 330 return QuickSortSlicedSafe(arr, 0, arr.GetSize(), less);
nuclear@1 331 }
nuclear@1 332
nuclear@1 333
nuclear@1 334 //-----------------------------------------------------------------------------------
nuclear@1 335 // ***** QuickSort
nuclear@1 336 //
nuclear@1 337 // Sort an array Array, ArrayPaged, ArrayUnsafe.
nuclear@1 338 // The array must have GetSize() function.
nuclear@1 339 // The data type must have a defined "<" operator.
nuclear@1 340 template<class Array>
nuclear@1 341 void QuickSort(Array& arr)
nuclear@1 342 {
nuclear@1 343 typedef typename Array::ValueType ValueType;
nuclear@1 344 QuickSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
nuclear@1 345 }
nuclear@1 346
nuclear@1 347 template<class Array>
nuclear@1 348 bool QuickSortSafe(Array& arr)
nuclear@1 349 {
nuclear@1 350 typedef typename Array::ValueType ValueType;
nuclear@1 351 return QuickSortSlicedSafe(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
nuclear@1 352 }
nuclear@1 353
nuclear@1 354 //-----------------------------------------------------------------------------------
nuclear@1 355 // ***** InsertionSortSliced
nuclear@1 356 //
nuclear@1 357 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
nuclear@1 358 // The range is specified with start, end, where "end" is exclusive!
nuclear@1 359 // The comparison predicate must be specified.
nuclear@1 360 // Unlike Quick Sort, the Insertion Sort works much slower in average,
nuclear@1 361 // but may be much faster on almost sorted arrays. Besides, it guarantees
nuclear@1 362 // that the elements will not be swapped if not necessary. For example,
nuclear@1 363 // an array with all equal elements will remain "untouched", while
nuclear@1 364 // Quick Sort will considerably shuffle the elements in this case.
nuclear@1 365 template<class Array, class Less>
nuclear@1 366 void InsertionSortSliced(Array& arr, UPInt start, UPInt end, Less less)
nuclear@1 367 {
nuclear@1 368 UPInt j = start;
nuclear@1 369 UPInt i = j + 1;
nuclear@1 370 UPInt limit = end;
nuclear@1 371
nuclear@1 372 for(; i < limit; j = i, i++)
nuclear@1 373 {
nuclear@1 374 for(; less(arr[j + 1], arr[j]); j--)
nuclear@1 375 {
nuclear@1 376 Swap(arr[j + 1], arr[j]);
nuclear@1 377 if(j <= start)
nuclear@1 378 {
nuclear@1 379 break;
nuclear@1 380 }
nuclear@1 381 }
nuclear@1 382 }
nuclear@1 383 }
nuclear@1 384
nuclear@1 385
nuclear@1 386 //-----------------------------------------------------------------------------------
nuclear@1 387 // ***** InsertionSortSliced
nuclear@1 388 //
nuclear@1 389 // Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
nuclear@1 390 // The range is specified with start, end, where "end" is exclusive!
nuclear@1 391 // The data type must have a defined "<" operator.
nuclear@1 392 template<class Array>
nuclear@1 393 void InsertionSortSliced(Array& arr, UPInt start, UPInt end)
nuclear@1 394 {
nuclear@1 395 typedef typename Array::ValueType ValueType;
nuclear@1 396 InsertionSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
nuclear@1 397 }
nuclear@1 398
nuclear@1 399 //-----------------------------------------------------------------------------------
nuclear@1 400 // ***** InsertionSort
nuclear@1 401 //
nuclear@1 402 // Sort an array Array, ArrayPaged, ArrayUnsafe.
nuclear@1 403 // The array must have GetSize() function.
nuclear@1 404 // The comparison predicate must be specified.
nuclear@1 405
nuclear@1 406 template<class Array, class Less>
nuclear@1 407 void InsertionSort(Array& arr, Less less)
nuclear@1 408 {
nuclear@1 409 InsertionSortSliced(arr, 0, arr.GetSize(), less);
nuclear@1 410 }
nuclear@1 411
nuclear@1 412 //-----------------------------------------------------------------------------------
nuclear@1 413 // ***** InsertionSort
nuclear@1 414 //
nuclear@1 415 // Sort an array Array, ArrayPaged, ArrayUnsafe.
nuclear@1 416 // The array must have GetSize() function.
nuclear@1 417 // The data type must have a defined "<" operator.
nuclear@1 418 template<class Array>
nuclear@1 419 void InsertionSort(Array& arr)
nuclear@1 420 {
nuclear@1 421 typedef typename Array::ValueType ValueType;
nuclear@1 422 InsertionSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
nuclear@1 423 }
nuclear@1 424
nuclear@1 425
nuclear@1 426
nuclear@1 427 //-----------------------------------------------------------------------------------
nuclear@1 428 // ***** LowerBoundSliced
nuclear@1 429 //
nuclear@1 430 template<class Array, class Value, class Less>
nuclear@1 431 UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less)
nuclear@1 432 {
nuclear@1 433 SPInt first = (SPInt)start;
nuclear@1 434 SPInt len = (SPInt)(end - start);
nuclear@1 435 SPInt half;
nuclear@1 436 SPInt middle;
nuclear@1 437
nuclear@1 438 while(len > 0)
nuclear@1 439 {
nuclear@1 440 half = len >> 1;
nuclear@1 441 middle = first + half;
nuclear@1 442 if(less(arr[middle], val))
nuclear@1 443 {
nuclear@1 444 first = middle + 1;
nuclear@1 445 len = len - half - 1;
nuclear@1 446 }
nuclear@1 447 else
nuclear@1 448 {
nuclear@1 449 len = half;
nuclear@1 450 }
nuclear@1 451 }
nuclear@1 452 return (UPInt)first;
nuclear@1 453 }
nuclear@1 454
nuclear@1 455
nuclear@1 456 //-----------------------------------------------------------------------------------
nuclear@1 457 // ***** LowerBoundSliced
nuclear@1 458 //
nuclear@1 459 template<class Array, class Value>
nuclear@1 460 UPInt LowerBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val)
nuclear@1 461 {
nuclear@1 462 return LowerBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
nuclear@1 463 }
nuclear@1 464
nuclear@1 465 //-----------------------------------------------------------------------------------
nuclear@1 466 // ***** LowerBoundSized
nuclear@1 467 //
nuclear@1 468 template<class Array, class Value>
nuclear@1 469 UPInt LowerBoundSized(const Array& arr, UPInt size, const Value& val)
nuclear@1 470 {
nuclear@1 471 return LowerBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
nuclear@1 472 }
nuclear@1 473
nuclear@1 474 //-----------------------------------------------------------------------------------
nuclear@1 475 // ***** LowerBound
nuclear@1 476 //
nuclear@1 477 template<class Array, class Value, class Less>
nuclear@1 478 UPInt LowerBound(const Array& arr, const Value& val, Less less)
nuclear@1 479 {
nuclear@1 480 return LowerBoundSliced(arr, 0, arr.GetSize(), val, less);
nuclear@1 481 }
nuclear@1 482
nuclear@1 483
nuclear@1 484 //-----------------------------------------------------------------------------------
nuclear@1 485 // ***** LowerBound
nuclear@1 486 //
nuclear@1 487 template<class Array, class Value>
nuclear@1 488 UPInt LowerBound(const Array& arr, const Value& val)
nuclear@1 489 {
nuclear@1 490 return LowerBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
nuclear@1 491 }
nuclear@1 492
nuclear@1 493
nuclear@1 494
nuclear@1 495 //-----------------------------------------------------------------------------------
nuclear@1 496 // ***** UpperBoundSliced
nuclear@1 497 //
nuclear@1 498 template<class Array, class Value, class Less>
nuclear@1 499 UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val, Less less)
nuclear@1 500 {
nuclear@1 501 SPInt first = (SPInt)start;
nuclear@1 502 SPInt len = (SPInt)(end - start);
nuclear@1 503 SPInt half;
nuclear@1 504 SPInt middle;
nuclear@1 505
nuclear@1 506 while(len > 0)
nuclear@1 507 {
nuclear@1 508 half = len >> 1;
nuclear@1 509 middle = first + half;
nuclear@1 510 if(less(val, arr[middle]))
nuclear@1 511 {
nuclear@1 512 len = half;
nuclear@1 513 }
nuclear@1 514 else
nuclear@1 515 {
nuclear@1 516 first = middle + 1;
nuclear@1 517 len = len - half - 1;
nuclear@1 518 }
nuclear@1 519 }
nuclear@1 520 return (UPInt)first;
nuclear@1 521 }
nuclear@1 522
nuclear@1 523
nuclear@1 524 //-----------------------------------------------------------------------------------
nuclear@1 525 // ***** UpperBoundSliced
nuclear@1 526 //
nuclear@1 527 template<class Array, class Value>
nuclear@1 528 UPInt UpperBoundSliced(const Array& arr, UPInt start, UPInt end, const Value& val)
nuclear@1 529 {
nuclear@1 530 return UpperBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
nuclear@1 531 }
nuclear@1 532
nuclear@1 533
nuclear@1 534 //-----------------------------------------------------------------------------------
nuclear@1 535 // ***** UpperBoundSized
nuclear@1 536 //
nuclear@1 537 template<class Array, class Value>
nuclear@1 538 UPInt UpperBoundSized(const Array& arr, UPInt size, const Value& val)
nuclear@1 539 {
nuclear@1 540 return UpperBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
nuclear@1 541 }
nuclear@1 542
nuclear@1 543
nuclear@1 544 //-----------------------------------------------------------------------------------
nuclear@1 545 // ***** UpperBound
nuclear@1 546 //
nuclear@1 547 template<class Array, class Value, class Less>
nuclear@1 548 UPInt UpperBound(const Array& arr, const Value& val, Less less)
nuclear@1 549 {
nuclear@1 550 return UpperBoundSliced(arr, 0, arr.GetSize(), val, less);
nuclear@1 551 }
nuclear@1 552
nuclear@1 553
nuclear@1 554 //-----------------------------------------------------------------------------------
nuclear@1 555 // ***** UpperBound
nuclear@1 556 //
nuclear@1 557 template<class Array, class Value>
nuclear@1 558 UPInt UpperBound(const Array& arr, const Value& val)
nuclear@1 559 {
nuclear@1 560 return UpperBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
nuclear@1 561 }
nuclear@1 562
nuclear@1 563
nuclear@1 564 //-----------------------------------------------------------------------------------
nuclear@1 565 // ***** ReverseArray
nuclear@1 566 //
nuclear@1 567 template<class Array> void ReverseArray(Array& arr)
nuclear@1 568 {
nuclear@1 569 SPInt from = 0;
nuclear@1 570 SPInt to = arr.GetSize() - 1;
nuclear@1 571 while(from < to)
nuclear@1 572 {
nuclear@1 573 Swap(arr[from], arr[to]);
nuclear@1 574 ++from;
nuclear@1 575 --to;
nuclear@1 576 }
nuclear@1 577 }
nuclear@1 578
nuclear@1 579
nuclear@1 580 // ***** AppendArray
nuclear@1 581 //
nuclear@1 582 template<class CDst, class CSrc>
nuclear@1 583 void AppendArray(CDst& dst, const CSrc& src)
nuclear@1 584 {
nuclear@1 585 UPInt i;
nuclear@1 586 for(i = 0; i < src.GetSize(); i++)
nuclear@1 587 dst.PushBack(src[i]);
nuclear@1 588 }
nuclear@1 589
nuclear@1 590 //-----------------------------------------------------------------------------------
nuclear@1 591 // ***** ArrayAdaptor
nuclear@1 592 //
nuclear@1 593 // A simple adapter that provides the GetSize() method and overloads
nuclear@1 594 // operator []. Used to wrap plain arrays in QuickSort and such.
nuclear@1 595 template<class T> class ArrayAdaptor
nuclear@1 596 {
nuclear@1 597 public:
nuclear@1 598 typedef T ValueType;
nuclear@1 599 ArrayAdaptor() : Data(0), Size(0) {}
nuclear@1 600 ArrayAdaptor(T* ptr, UPInt size) : Data(ptr), Size(size) {}
nuclear@1 601 UPInt GetSize() const { return Size; }
nuclear@1 602 const T& operator [] (UPInt i) const { return Data[i]; }
nuclear@1 603 T& operator [] (UPInt i) { return Data[i]; }
nuclear@1 604 private:
nuclear@1 605 T* Data;
nuclear@1 606 UPInt Size;
nuclear@1 607 };
nuclear@1 608
nuclear@1 609
nuclear@1 610 //-----------------------------------------------------------------------------------
nuclear@1 611 // ***** GConstArrayAdaptor
nuclear@1 612 //
nuclear@1 613 // A simple const adapter that provides the GetSize() method and overloads
nuclear@1 614 // operator []. Used to wrap plain arrays in LowerBound and such.
nuclear@1 615 template<class T> class ConstArrayAdaptor
nuclear@1 616 {
nuclear@1 617 public:
nuclear@1 618 typedef T ValueType;
nuclear@1 619 ConstArrayAdaptor() : Data(0), Size(0) {}
nuclear@1 620 ConstArrayAdaptor(const T* ptr, UPInt size) : Data(ptr), Size(size) {}
nuclear@1 621 UPInt GetSize() const { return Size; }
nuclear@1 622 const T& operator [] (UPInt i) const { return Data[i]; }
nuclear@1 623 private:
nuclear@1 624 const T* Data;
nuclear@1 625 UPInt Size;
nuclear@1 626 };
nuclear@1 627
nuclear@1 628
nuclear@1 629
nuclear@1 630 //-----------------------------------------------------------------------------------
nuclear@1 631 extern const UByte UpperBitTable[256];
nuclear@1 632 extern const UByte LowerBitTable[256];
nuclear@1 633
nuclear@1 634
nuclear@1 635
nuclear@1 636 //-----------------------------------------------------------------------------------
nuclear@1 637 inline UByte UpperBit(UPInt val)
nuclear@1 638 {
nuclear@1 639 #ifndef OVR_64BIT_POINTERS
nuclear@1 640
nuclear@1 641 if (val & 0xFFFF0000)
nuclear@1 642 {
nuclear@1 643 return (val & 0xFF000000) ?
nuclear@1 644 UpperBitTable[(val >> 24) ] + 24:
nuclear@1 645 UpperBitTable[(val >> 16) & 0xFF] + 16;
nuclear@1 646 }
nuclear@1 647 return (val & 0xFF00) ?
nuclear@1 648 UpperBitTable[(val >> 8) & 0xFF] + 8:
nuclear@1 649 UpperBitTable[(val ) & 0xFF];
nuclear@1 650
nuclear@1 651 #else
nuclear@1 652
nuclear@1 653 if (val & 0xFFFFFFFF00000000)
nuclear@1 654 {
nuclear@1 655 if (val & 0xFFFF000000000000)
nuclear@1 656 {
nuclear@1 657 return (val & 0xFF00000000000000) ?
nuclear@1 658 UpperBitTable[(val >> 56) ] + 56:
nuclear@1 659 UpperBitTable[(val >> 48) & 0xFF] + 48;
nuclear@1 660 }
nuclear@1 661 return (val & 0xFF0000000000) ?
nuclear@1 662 UpperBitTable[(val >> 40) & 0xFF] + 40:
nuclear@1 663 UpperBitTable[(val >> 32) & 0xFF] + 32;
nuclear@1 664 }
nuclear@1 665 else
nuclear@1 666 {
nuclear@1 667 if (val & 0xFFFF0000)
nuclear@1 668 {
nuclear@1 669 return (val & 0xFF000000) ?
nuclear@1 670 UpperBitTable[(val >> 24) ] + 24:
nuclear@1 671 UpperBitTable[(val >> 16) & 0xFF] + 16;
nuclear@1 672 }
nuclear@1 673 return (val & 0xFF00) ?
nuclear@1 674 UpperBitTable[(val >> 8) & 0xFF] + 8:
nuclear@1 675 UpperBitTable[(val ) & 0xFF];
nuclear@1 676 }
nuclear@1 677
nuclear@1 678 #endif
nuclear@1 679 }
nuclear@1 680
nuclear@1 681 //-----------------------------------------------------------------------------------
nuclear@1 682 inline UByte LowerBit(UPInt val)
nuclear@1 683 {
nuclear@1 684 #ifndef OVR_64BIT_POINTERS
nuclear@1 685
nuclear@1 686 if (val & 0xFFFF)
nuclear@1 687 {
nuclear@1 688 return (val & 0xFF) ?
nuclear@1 689 LowerBitTable[ val & 0xFF]:
nuclear@1 690 LowerBitTable[(val >> 8) & 0xFF] + 8;
nuclear@1 691 }
nuclear@1 692 return (val & 0xFF0000) ?
nuclear@1 693 LowerBitTable[(val >> 16) & 0xFF] + 16:
nuclear@1 694 LowerBitTable[(val >> 24) & 0xFF] + 24;
nuclear@1 695
nuclear@1 696 #else
nuclear@1 697
nuclear@1 698 if (val & 0xFFFFFFFF)
nuclear@1 699 {
nuclear@1 700 if (val & 0xFFFF)
nuclear@1 701 {
nuclear@1 702 return (val & 0xFF) ?
nuclear@1 703 LowerBitTable[ val & 0xFF]:
nuclear@1 704 LowerBitTable[(val >> 8) & 0xFF] + 8;
nuclear@1 705 }
nuclear@1 706 return (val & 0xFF0000) ?
nuclear@1 707 LowerBitTable[(val >> 16) & 0xFF] + 16:
nuclear@1 708 LowerBitTable[(val >> 24) & 0xFF] + 24;
nuclear@1 709 }
nuclear@1 710 else
nuclear@1 711 {
nuclear@1 712 if (val & 0xFFFF00000000)
nuclear@1 713 {
nuclear@1 714 return (val & 0xFF00000000) ?
nuclear@1 715 LowerBitTable[(val >> 32) & 0xFF] + 32:
nuclear@1 716 LowerBitTable[(val >> 40) & 0xFF] + 40;
nuclear@1 717 }
nuclear@1 718 return (val & 0xFF000000000000) ?
nuclear@1 719 LowerBitTable[(val >> 48) & 0xFF] + 48:
nuclear@1 720 LowerBitTable[(val >> 56) & 0xFF] + 56;
nuclear@1 721 }
nuclear@1 722
nuclear@1 723 #endif
nuclear@1 724 }
nuclear@1 725
nuclear@1 726
nuclear@1 727
nuclear@1 728 // ******* Special (optimized) memory routines
nuclear@1 729 // Note: null (bad) pointer is not tested
nuclear@1 730 class MemUtil
nuclear@1 731 {
nuclear@1 732 public:
nuclear@1 733
nuclear@1 734 // Memory compare
nuclear@1 735 static int Cmp (const void* p1, const void* p2, UPInt byteCount) { return memcmp(p1, p2, byteCount); }
nuclear@1 736 static int Cmp16(const void* p1, const void* p2, UPInt int16Count);
nuclear@1 737 static int Cmp32(const void* p1, const void* p2, UPInt int32Count);
nuclear@1 738 static int Cmp64(const void* p1, const void* p2, UPInt int64Count);
nuclear@1 739 };
nuclear@1 740
nuclear@1 741 // ** Inline Implementation
nuclear@1 742
nuclear@1 743 inline int MemUtil::Cmp16(const void* p1, const void* p2, UPInt int16Count)
nuclear@1 744 {
nuclear@1 745 SInt16* pa = (SInt16*)p1;
nuclear@1 746 SInt16* pb = (SInt16*)p2;
nuclear@1 747 unsigned ic = 0;
nuclear@1 748 if (int16Count == 0)
nuclear@1 749 return 0;
nuclear@1 750 while (pa[ic] == pb[ic])
nuclear@1 751 if (++ic==int16Count)
nuclear@1 752 return 0;
nuclear@1 753 return pa[ic] > pb[ic] ? 1 : -1;
nuclear@1 754 }
nuclear@1 755 inline int MemUtil::Cmp32(const void* p1, const void* p2, UPInt int32Count)
nuclear@1 756 {
nuclear@1 757 SInt32* pa = (SInt32*)p1;
nuclear@1 758 SInt32* pb = (SInt32*)p2;
nuclear@1 759 unsigned ic = 0;
nuclear@1 760 if (int32Count == 0)
nuclear@1 761 return 0;
nuclear@1 762 while (pa[ic] == pb[ic])
nuclear@1 763 if (++ic==int32Count)
nuclear@1 764 return 0;
nuclear@1 765 return pa[ic] > pb[ic] ? 1 : -1;
nuclear@1 766 }
nuclear@1 767 inline int MemUtil::Cmp64(const void* p1, const void* p2, UPInt int64Count)
nuclear@1 768 {
nuclear@1 769 SInt64* pa = (SInt64*)p1;
nuclear@1 770 SInt64* pb = (SInt64*)p2;
nuclear@1 771 unsigned ic = 0;
nuclear@1 772 if (int64Count == 0)
nuclear@1 773 return 0;
nuclear@1 774 while (pa[ic] == pb[ic])
nuclear@1 775 if (++ic==int64Count)
nuclear@1 776 return 0;
nuclear@1 777 return pa[ic] > pb[ic] ? 1 : -1;
nuclear@1 778 }
nuclear@1 779
nuclear@1 780 // ** End Inline Implementation
nuclear@1 781
nuclear@1 782
nuclear@1 783 //-----------------------------------------------------------------------------------
nuclear@1 784 // ******* Byte Order Conversions
nuclear@1 785 namespace ByteUtil {
nuclear@1 786
nuclear@1 787 // *** Swap Byte Order
nuclear@1 788
nuclear@1 789 // Swap the byte order of a byte array
nuclear@1 790 inline void SwapOrder(void* pv, int size)
nuclear@1 791 {
nuclear@1 792 UByte* pb = (UByte*)pv;
nuclear@1 793 UByte temp;
nuclear@1 794 for (int i = 0; i < size>>1; i++)
nuclear@1 795 {
nuclear@1 796 temp = pb[size-1-i];
nuclear@1 797 pb[size-1-i] = pb[i];
nuclear@1 798 pb[i] = temp;
nuclear@1 799 }
nuclear@1 800 }
nuclear@1 801
nuclear@1 802 // Swap the byte order of primitive types
nuclear@1 803 inline UByte SwapOrder(UByte v) { return v; }
nuclear@1 804 inline SByte SwapOrder(SByte v) { return v; }
nuclear@1 805 inline UInt16 SwapOrder(UInt16 v) { return UInt16(v>>8)|UInt16(v<<8); }
nuclear@1 806 inline SInt16 SwapOrder(SInt16 v) { return SInt16((UInt16(v)>>8)|(v<<8)); }
nuclear@1 807 inline UInt32 SwapOrder(UInt32 v) { return (v>>24)|((v&0x00FF0000)>>8)|((v&0x0000FF00)<<8)|(v<<24); }
nuclear@1 808 inline SInt32 SwapOrder(SInt32 p) { return (SInt32)SwapOrder(UInt32(p)); }
nuclear@1 809 inline UInt64 SwapOrder(UInt64 v)
nuclear@1 810 {
nuclear@1 811 return (v>>56) |
nuclear@1 812 ((v&UInt64(0x00FF000000000000))>>40) |
nuclear@1 813 ((v&UInt64(0x0000FF0000000000))>>24) |
nuclear@1 814 ((v&UInt64(0x000000FF00000000))>>8) |
nuclear@1 815 ((v&UInt64(0x00000000FF000000))<<8) |
nuclear@1 816 ((v&UInt64(0x0000000000FF0000))<<24) |
nuclear@1 817 ((v&UInt64(0x000000000000FF00))<<40) |
nuclear@1 818 (v<<56);
nuclear@1 819 }
nuclear@1 820 inline SInt64 SwapOrder(SInt64 v) { return (SInt64)SwapOrder(UInt64(v)); }
nuclear@1 821 inline float SwapOrder(float p)
nuclear@1 822 {
nuclear@1 823 union {
nuclear@1 824 float p;
nuclear@1 825 UInt32 v;
nuclear@1 826 } u;
nuclear@1 827 u.p = p;
nuclear@1 828 u.v = SwapOrder(u.v);
nuclear@1 829 return u.p;
nuclear@1 830 }
nuclear@1 831
nuclear@1 832 inline double SwapOrder(double p)
nuclear@1 833 {
nuclear@1 834 union {
nuclear@1 835 double p;
nuclear@1 836 UInt64 v;
nuclear@1 837 } u;
nuclear@1 838 u.p = p;
nuclear@1 839 u.v = SwapOrder(u.v);
nuclear@1 840 return u.p;
nuclear@1 841 }
nuclear@1 842
nuclear@1 843 // *** Byte-order conversion
nuclear@1 844
nuclear@1 845 #if (OVR_BYTE_ORDER == OVR_LITTLE_ENDIAN)
nuclear@1 846 // Little Endian to System (LE)
nuclear@1 847 inline UByte LEToSystem(UByte v) { return v; }
nuclear@1 848 inline SByte LEToSystem(SByte v) { return v; }
nuclear@1 849 inline UInt16 LEToSystem(UInt16 v) { return v; }
nuclear@1 850 inline SInt16 LEToSystem(SInt16 v) { return v; }
nuclear@1 851 inline UInt32 LEToSystem(UInt32 v) { return v; }
nuclear@1 852 inline SInt32 LEToSystem(SInt32 v) { return v; }
nuclear@1 853 inline UInt64 LEToSystem(UInt64 v) { return v; }
nuclear@1 854 inline SInt64 LEToSystem(SInt64 v) { return v; }
nuclear@1 855 inline float LEToSystem(float v) { return v; }
nuclear@1 856 inline double LEToSystem(double v) { return v; }
nuclear@1 857
nuclear@1 858 // Big Endian to System (LE)
nuclear@1 859 inline UByte BEToSystem(UByte v) { return SwapOrder(v); }
nuclear@1 860 inline SByte BEToSystem(SByte v) { return SwapOrder(v); }
nuclear@1 861 inline UInt16 BEToSystem(UInt16 v) { return SwapOrder(v); }
nuclear@1 862 inline SInt16 BEToSystem(SInt16 v) { return SwapOrder(v); }
nuclear@1 863 inline UInt32 BEToSystem(UInt32 v) { return SwapOrder(v); }
nuclear@1 864 inline SInt32 BEToSystem(SInt32 v) { return SwapOrder(v); }
nuclear@1 865 inline UInt64 BEToSystem(UInt64 v) { return SwapOrder(v); }
nuclear@1 866 inline SInt64 BEToSystem(SInt64 v) { return SwapOrder(v); }
nuclear@1 867 inline float BEToSystem(float v) { return SwapOrder(v); }
nuclear@1 868 inline double BEToSystem(double v) { return SwapOrder(v); }
nuclear@1 869
nuclear@1 870 // System (LE) to Little Endian
nuclear@1 871 inline UByte SystemToLE(UByte v) { return v; }
nuclear@1 872 inline SByte SystemToLE(SByte v) { return v; }
nuclear@1 873 inline UInt16 SystemToLE(UInt16 v) { return v; }
nuclear@1 874 inline SInt16 SystemToLE(SInt16 v) { return v; }
nuclear@1 875 inline UInt32 SystemToLE(UInt32 v) { return v; }
nuclear@1 876 inline SInt32 SystemToLE(SInt32 v) { return v; }
nuclear@1 877 inline UInt64 SystemToLE(UInt64 v) { return v; }
nuclear@1 878 inline SInt64 SystemToLE(SInt64 v) { return v; }
nuclear@1 879 inline float SystemToLE(float v) { return v; }
nuclear@1 880 inline double SystemToLE(double v) { return v; }
nuclear@1 881
nuclear@1 882 // System (LE) to Big Endian
nuclear@1 883 inline UByte SystemToBE(UByte v) { return SwapOrder(v); }
nuclear@1 884 inline SByte SystemToBE(SByte v) { return SwapOrder(v); }
nuclear@1 885 inline UInt16 SystemToBE(UInt16 v) { return SwapOrder(v); }
nuclear@1 886 inline SInt16 SystemToBE(SInt16 v) { return SwapOrder(v); }
nuclear@1 887 inline UInt32 SystemToBE(UInt32 v) { return SwapOrder(v); }
nuclear@1 888 inline SInt32 SystemToBE(SInt32 v) { return SwapOrder(v); }
nuclear@1 889 inline UInt64 SystemToBE(UInt64 v) { return SwapOrder(v); }
nuclear@1 890 inline SInt64 SystemToBE(SInt64 v) { return SwapOrder(v); }
nuclear@1 891 inline float SystemToBE(float v) { return SwapOrder(v); }
nuclear@1 892 inline double SystemToBE(double v) { return SwapOrder(v); }
nuclear@1 893
nuclear@1 894 #elif (OVR_BYTE_ORDER == OVR_BIG_ENDIAN)
nuclear@1 895 // Little Endian to System (BE)
nuclear@1 896 inline UByte LEToSystem(UByte v) { return SwapOrder(v); }
nuclear@1 897 inline SByte LEToSystem(SByte v) { return SwapOrder(v); }
nuclear@1 898 inline UInt16 LEToSystem(UInt16 v) { return SwapOrder(v); }
nuclear@1 899 inline SInt16 LEToSystem(SInt16 v) { return SwapOrder(v); }
nuclear@1 900 inline UInt32 LEToSystem(UInt32 v) { return SwapOrder(v); }
nuclear@1 901 inline SInt32 LEToSystem(SInt32 v) { return SwapOrder(v); }
nuclear@1 902 inline UInt64 LEToSystem(UInt64 v) { return SwapOrder(v); }
nuclear@1 903 inline SInt64 LEToSystem(SInt64 v) { return SwapOrder(v); }
nuclear@1 904 inline float LEToSystem(float v) { return SwapOrder(v); }
nuclear@1 905 inline double LEToSystem(double v) { return SwapOrder(v); }
nuclear@1 906
nuclear@1 907 // Big Endian to System (BE)
nuclear@1 908 inline UByte BEToSystem(UByte v) { return v; }
nuclear@1 909 inline SByte BEToSystem(SByte v) { return v; }
nuclear@1 910 inline UInt16 BEToSystem(UInt16 v) { return v; }
nuclear@1 911 inline SInt16 BEToSystem(SInt16 v) { return v; }
nuclear@1 912 inline UInt32 BEToSystem(UInt32 v) { return v; }
nuclear@1 913 inline SInt32 BEToSystem(SInt32 v) { return v; }
nuclear@1 914 inline UInt64 BEToSystem(UInt64 v) { return v; }
nuclear@1 915 inline SInt64 BEToSystem(SInt64 v) { return v; }
nuclear@1 916 inline float BEToSystem(float v) { return v; }
nuclear@1 917 inline double BEToSystem(double v) { return v; }
nuclear@1 918
nuclear@1 919 // System (BE) to Little Endian
nuclear@1 920 inline UByte SystemToLE(UByte v) { return SwapOrder(v); }
nuclear@1 921 inline SByte SystemToLE(SByte v) { return SwapOrder(v); }
nuclear@1 922 inline UInt16 SystemToLE(UInt16 v) { return SwapOrder(v); }
nuclear@1 923 inline SInt16 SystemToLE(SInt16 v) { return SwapOrder(v); }
nuclear@1 924 inline UInt32 SystemToLE(UInt32 v) { return SwapOrder(v); }
nuclear@1 925 inline SInt32 SystemToLE(SInt32 v) { return SwapOrder(v); }
nuclear@1 926 inline UInt64 SystemToLE(UInt64 v) { return SwapOrder(v); }
nuclear@1 927 inline SInt64 SystemToLE(SInt64 v) { return SwapOrder(v); }
nuclear@1 928 inline float SystemToLE(float v) { return SwapOrder(v); }
nuclear@1 929 inline double SystemToLE(double v) { return SwapOrder(v); }
nuclear@1 930
nuclear@1 931 // System (BE) to Big Endian
nuclear@1 932 inline UByte SystemToBE(UByte v) { return v; }
nuclear@1 933 inline SByte SystemToBE(SByte v) { return v; }
nuclear@1 934 inline UInt16 SystemToBE(UInt16 v) { return v; }
nuclear@1 935 inline SInt16 SystemToBE(SInt16 v) { return v; }
nuclear@1 936 inline UInt32 SystemToBE(UInt32 v) { return v; }
nuclear@1 937 inline SInt32 SystemToBE(SInt32 v) { return v; }
nuclear@1 938 inline UInt64 SystemToBE(UInt64 v) { return v; }
nuclear@1 939 inline SInt64 SystemToBE(SInt64 v) { return v; }
nuclear@1 940 inline float SystemToBE(float v) { return v; }
nuclear@1 941 inline double SystemToBE(double v) { return v; }
nuclear@1 942
nuclear@1 943 #else
nuclear@1 944 #error "OVR_BYTE_ORDER must be defined to OVR_LITTLE_ENDIAN or OVR_BIG_ENDIAN"
nuclear@1 945 #endif
nuclear@1 946
nuclear@1 947 } // namespace ByteUtil
nuclear@1 948
nuclear@1 949
nuclear@1 950
nuclear@1 951 }} // OVR::Alg
nuclear@1 952
nuclear@1 953 #endif