1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/LibOVR/Src/Kernel/OVR_Alg.h	Wed Jan 14 06:51:16 2015 +0200
     1.3 @@ -0,0 +1,1062 @@
     1.4 +/************************************************************************************
     1.5 +
     1.6 +PublicHeader:   OVR_Kernel.h
     1.7 +Filename    :   OVR_Alg.h
     1.8 +Content     :   Simple general purpose algorithms: Sort, Binary Search, etc.
     1.9 +Created     :   September 19, 2012
    1.10 +Notes       : 
    1.11 +
    1.12 +Copyright   :   Copyright 2014 Oculus VR, LLC All Rights reserved.
    1.13 +
    1.14 +Licensed under the Oculus VR Rift SDK License Version 3.2 (the "License"); 
    1.15 +you may not use the Oculus VR Rift SDK except in compliance with the License, 
    1.16 +which is provided at the time of installation or download, or which 
    1.17 +otherwise accompanies this software in either electronic or hard copy form.
    1.18 +
    1.19 +You may obtain a copy of the License at
    1.20 +
    1.21 +http://www.oculusvr.com/licenses/LICENSE-3.2 
    1.22 +
    1.23 +Unless required by applicable law or agreed to in writing, the Oculus VR SDK 
    1.24 +distributed under the License is distributed on an "AS IS" BASIS,
    1.25 +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    1.26 +See the License for the specific language governing permissions and
    1.27 +limitations under the License.
    1.28 +
    1.29 +************************************************************************************/
    1.30 +
    1.31 +#ifndef OVR_Alg_h
    1.32 +#define OVR_Alg_h
    1.33 +
    1.34 +#include "OVR_Types.h"
    1.35 +#include <string.h>
    1.36 +
    1.37 +namespace OVR { namespace Alg {
    1.38 +
    1.39 +
    1.40 +//-----------------------------------------------------------------------------------
    1.41 +// ***** Operator extensions
    1.42 +
    1.43 +template <typename T> OVR_FORCE_INLINE void Swap(T &a, T &b) 
    1.44 +{  T temp(a); a = b; b = temp; }
    1.45 +
    1.46 +
    1.47 +// ***** min/max are not implemented in Visual Studio 6 standard STL
    1.48 +
    1.49 +template <typename T> OVR_FORCE_INLINE const T Min(const T a, const T b)
    1.50 +{ return (a < b) ? a : b; }
    1.51 +
    1.52 +template <typename T> OVR_FORCE_INLINE const T Max(const T a, const T b)
    1.53 +{ return (b < a) ? a : b; }
    1.54 +
    1.55 +template <typename T> OVR_FORCE_INLINE const T Clamp(const T v, const T minVal, const T maxVal)
    1.56 +{ return Max<T>(minVal, Min<T>(v, maxVal)); }
    1.57 +
    1.58 +template <typename T> OVR_FORCE_INLINE int     Chop(T f)
    1.59 +{ return (int)f; }
    1.60 +
    1.61 +template <typename T> OVR_FORCE_INLINE T       Lerp(T a, T b, T f) 
    1.62 +{ return (b - a) * f + a; }
    1.63 +
    1.64 +
    1.65 +// These functions stand to fix a stupid VC++ warning (with /Wp64 on):
    1.66 +// "warning C4267: 'argument' : conversion from 'size_t' to 'const unsigned', possible loss of data"
    1.67 +// Use these functions instead of gmin/gmax if the argument has size
    1.68 +// of the pointer to avoid the warning. Though, functionally they are
    1.69 +// absolutelly the same as regular gmin/gmax.
    1.70 +template <typename T>   OVR_FORCE_INLINE const T PMin(const T a, const T b)
    1.71 +{
    1.72 +    OVR_COMPILER_ASSERT(sizeof(T) == sizeof(size_t));
    1.73 +    return (a < b) ? a : b;
    1.74 +}
    1.75 +template <typename T>   OVR_FORCE_INLINE const T PMax(const T a, const T b)
    1.76 +{
    1.77 +    OVR_COMPILER_ASSERT(sizeof(T) == sizeof(size_t));
    1.78 +    return (b < a) ? a : b;
    1.79 +}
    1.80 +
    1.81 +
    1.82 +template <typename T>   OVR_FORCE_INLINE const T Abs(const T v)
    1.83 +{ return (v>=0) ? v : -v; }
    1.84 +
    1.85 +
    1.86 +//-----------------------------------------------------------------------------------
    1.87 +// ***** OperatorLess
    1.88 +//
    1.89 +template<class T> struct OperatorLess
    1.90 +{
    1.91 +    static bool Compare(const T& a, const T& b)
    1.92 +    {
    1.93 +        return a < b;
    1.94 +    }
    1.95 +};
    1.96 +
    1.97 +
    1.98 +//-----------------------------------------------------------------------------------
    1.99 +// ***** QuickSortSliced
   1.100 +//
   1.101 +// Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
   1.102 +// The range is specified with start, end, where "end" is exclusive!
   1.103 +// The comparison predicate must be specified.
   1.104 +template<class Array, class Less> 
   1.105 +void QuickSortSliced(Array& arr, size_t start, size_t end, Less less)
   1.106 +{
   1.107 +    enum 
   1.108 +    {
   1.109 +        Threshold = 9
   1.110 +    };
   1.111 +
   1.112 +    if(end - start <  2) return;
   1.113 +
   1.114 +    intptr_t  stack[80];
   1.115 +    intptr_t* top   = stack; 
   1.116 +    intptr_t  base  = (intptr_t)start;
   1.117 +    intptr_t  limit = (intptr_t)end;
   1.118 +
   1.119 +    for(;;)
   1.120 +    {
   1.121 +        intptr_t len = limit - base;
   1.122 +        intptr_t i, j, pivot;
   1.123 +
   1.124 +        if(len > Threshold)
   1.125 +        {
   1.126 +            // we use base + len/2 as the pivot
   1.127 +            pivot = base + len / 2;
   1.128 +            Swap(arr[base], arr[pivot]);
   1.129 +
   1.130 +            i = base + 1;
   1.131 +            j = limit - 1;
   1.132 +
   1.133 +            // now ensure that *i <= *base <= *j 
   1.134 +            if(less(arr[j],    arr[i])) Swap(arr[j],    arr[i]);
   1.135 +            if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
   1.136 +            if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
   1.137 +
   1.138 +            for(;;)
   1.139 +            {
   1.140 +                do i++; while( less(arr[i], arr[base]) );
   1.141 +                do j--; while( less(arr[base], arr[j]) );
   1.142 +
   1.143 +                if( i > j )
   1.144 +                {
   1.145 +                    break;
   1.146 +                }
   1.147 +
   1.148 +                Swap(arr[i], arr[j]);
   1.149 +            }
   1.150 +
   1.151 +            Swap(arr[base], arr[j]);
   1.152 +
   1.153 +            // now, push the largest sub-array
   1.154 +            if(j - base > limit - i)
   1.155 +            {
   1.156 +                top[0] = base;
   1.157 +                top[1] = j;
   1.158 +                base   = i;
   1.159 +            }
   1.160 +            else
   1.161 +            {
   1.162 +                top[0] = i;
   1.163 +                top[1] = limit;
   1.164 +                limit  = j;
   1.165 +            }
   1.166 +            top += 2;
   1.167 +        }
   1.168 +        else
   1.169 +        {
   1.170 +            // the sub-array is small, perform insertion sort
   1.171 +            j = base;
   1.172 +            i = j + 1;
   1.173 +
   1.174 +            for(; i < limit; j = i, i++)
   1.175 +            {
   1.176 +                for(; less(arr[j + 1], arr[j]); j--)
   1.177 +                {
   1.178 +                    Swap(arr[j + 1], arr[j]);
   1.179 +                    if(j == base)
   1.180 +                    {
   1.181 +                        break;
   1.182 +                    }
   1.183 +                }
   1.184 +            }
   1.185 +            if(top > stack)
   1.186 +            {
   1.187 +                top  -= 2;
   1.188 +                base  = top[0];
   1.189 +                limit = top[1];
   1.190 +            }
   1.191 +            else
   1.192 +            {
   1.193 +                break;
   1.194 +            }
   1.195 +        }
   1.196 +    }
   1.197 +}
   1.198 +
   1.199 +
   1.200 +//-----------------------------------------------------------------------------------
   1.201 +// ***** QuickSortSliced
   1.202 +//
   1.203 +// Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
   1.204 +// The range is specified with start, end, where "end" is exclusive!
   1.205 +// The data type must have a defined "<" operator.
   1.206 +template<class Array> 
   1.207 +void QuickSortSliced(Array& arr, size_t start, size_t end)
   1.208 +{
   1.209 +    typedef typename Array::ValueType ValueType;
   1.210 +    QuickSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
   1.211 +}
   1.212 +
   1.213 +// Same as corresponding G_QuickSortSliced but with checking array limits to avoid
   1.214 +// crash in the case of wrong comparator functor.
   1.215 +template<class Array, class Less> 
   1.216 +bool QuickSortSlicedSafe(Array& arr, size_t start, size_t end, Less less)
   1.217 +{
   1.218 +    enum 
   1.219 +    {
   1.220 +        Threshold = 9
   1.221 +    };
   1.222 +
   1.223 +    if(end - start <  2) return true;
   1.224 +
   1.225 +    intptr_t  stack[80];
   1.226 +    intptr_t* top   = stack; 
   1.227 +    intptr_t  base  = (intptr_t)start;
   1.228 +    intptr_t  limit = (intptr_t)end;
   1.229 +
   1.230 +    for(;;)
   1.231 +    {
   1.232 +        intptr_t len = limit - base;
   1.233 +        intptr_t i, j, pivot;
   1.234 +
   1.235 +        if(len > Threshold)
   1.236 +        {
   1.237 +            // we use base + len/2 as the pivot
   1.238 +            pivot = base + len / 2;
   1.239 +            Swap(arr[base], arr[pivot]);
   1.240 +
   1.241 +            i = base + 1;
   1.242 +            j = limit - 1;
   1.243 +
   1.244 +            // now ensure that *i <= *base <= *j 
   1.245 +            if(less(arr[j],    arr[i])) Swap(arr[j],    arr[i]);
   1.246 +            if(less(arr[base], arr[i])) Swap(arr[base], arr[i]);
   1.247 +            if(less(arr[j], arr[base])) Swap(arr[j], arr[base]);
   1.248 +
   1.249 +            for(;;)
   1.250 +            {
   1.251 +                do 
   1.252 +                {   
   1.253 +                    i++; 
   1.254 +                    if (i >= limit)
   1.255 +                        return false;
   1.256 +                } while( less(arr[i], arr[base]) );
   1.257 +                do 
   1.258 +                {
   1.259 +                    j--; 
   1.260 +                    if (j < 0)
   1.261 +                        return false;
   1.262 +                } while( less(arr[base], arr[j]) );
   1.263 +
   1.264 +                if( i > j )
   1.265 +                {
   1.266 +                    break;
   1.267 +                }
   1.268 +
   1.269 +                Swap(arr[i], arr[j]);
   1.270 +            }
   1.271 +
   1.272 +            Swap(arr[base], arr[j]);
   1.273 +
   1.274 +            // now, push the largest sub-array
   1.275 +            if(j - base > limit - i)
   1.276 +            {
   1.277 +                top[0] = base;
   1.278 +                top[1] = j;
   1.279 +                base   = i;
   1.280 +            }
   1.281 +            else
   1.282 +            {
   1.283 +                top[0] = i;
   1.284 +                top[1] = limit;
   1.285 +                limit  = j;
   1.286 +            }
   1.287 +            top += 2;
   1.288 +        }
   1.289 +        else
   1.290 +        {
   1.291 +            // the sub-array is small, perform insertion sort
   1.292 +            j = base;
   1.293 +            i = j + 1;
   1.294 +
   1.295 +            for(; i < limit; j = i, i++)
   1.296 +            {
   1.297 +                for(; less(arr[j + 1], arr[j]); j--)
   1.298 +                {
   1.299 +                    Swap(arr[j + 1], arr[j]);
   1.300 +                    if(j == base)
   1.301 +                    {
   1.302 +                        break;
   1.303 +                    }
   1.304 +                }
   1.305 +            }
   1.306 +            if(top > stack)
   1.307 +            {
   1.308 +                top  -= 2;
   1.309 +                base  = top[0];
   1.310 +                limit = top[1];
   1.311 +            }
   1.312 +            else
   1.313 +            {
   1.314 +                break;
   1.315 +            }
   1.316 +        }
   1.317 +    }
   1.318 +    return true;
   1.319 +}
   1.320 +
   1.321 +template<class Array> 
   1.322 +bool QuickSortSlicedSafe(Array& arr, size_t start, size_t end)
   1.323 +{
   1.324 +    typedef typename Array::ValueType ValueType;
   1.325 +    return QuickSortSlicedSafe(arr, start, end, OperatorLess<ValueType>::Compare);
   1.326 +}
   1.327 +
   1.328 +//-----------------------------------------------------------------------------------
   1.329 +// ***** QuickSort
   1.330 +//
   1.331 +// Sort an array Array, ArrayPaged, ArrayUnsafe.
   1.332 +// The array must have GetSize() function.
   1.333 +// The comparison predicate must be specified.
   1.334 +template<class Array, class Less> 
   1.335 +void QuickSort(Array& arr, Less less)
   1.336 +{
   1.337 +    QuickSortSliced(arr, 0, arr.GetSize(), less);
   1.338 +}
   1.339 +
   1.340 +// checks for boundaries
   1.341 +template<class Array, class Less> 
   1.342 +bool QuickSortSafe(Array& arr, Less less)
   1.343 +{
   1.344 +    return QuickSortSlicedSafe(arr, 0, arr.GetSize(), less);
   1.345 +}
   1.346 +
   1.347 +
   1.348 +//-----------------------------------------------------------------------------------
   1.349 +// ***** QuickSort
   1.350 +//
   1.351 +// Sort an array Array, ArrayPaged, ArrayUnsafe.
   1.352 +// The array must have GetSize() function.
   1.353 +// The data type must have a defined "<" operator.
   1.354 +template<class Array> 
   1.355 +void QuickSort(Array& arr)
   1.356 +{
   1.357 +    typedef typename Array::ValueType ValueType;
   1.358 +    QuickSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
   1.359 +}
   1.360 +
   1.361 +template<class Array> 
   1.362 +bool QuickSortSafe(Array& arr)
   1.363 +{
   1.364 +    typedef typename Array::ValueType ValueType;
   1.365 +    return QuickSortSlicedSafe(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
   1.366 +}
   1.367 +
   1.368 +//-----------------------------------------------------------------------------------
   1.369 +// ***** InsertionSortSliced
   1.370 +//
   1.371 +// Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
   1.372 +// The range is specified with start, end, where "end" is exclusive!
   1.373 +// The comparison predicate must be specified.
   1.374 +// Unlike Quick Sort, the Insertion Sort works much slower in average, 
   1.375 +// but may be much faster on almost sorted arrays. Besides, it guarantees
   1.376 +// that the elements will not be swapped if not necessary. For example, 
   1.377 +// an array with all equal elements will remain "untouched", while 
   1.378 +// Quick Sort will considerably shuffle the elements in this case.
   1.379 +template<class Array, class Less> 
   1.380 +void InsertionSortSliced(Array& arr, size_t start, size_t end, Less less)
   1.381 +{
   1.382 +    size_t j = start;
   1.383 +    size_t i = j + 1;
   1.384 +    size_t limit = end;
   1.385 +
   1.386 +    for(; i < limit; j = i, i++)
   1.387 +    {
   1.388 +        for(; less(arr[j + 1], arr[j]); j--)
   1.389 +        {
   1.390 +            Swap(arr[j + 1], arr[j]);
   1.391 +            if(j <= start)
   1.392 +            {
   1.393 +                break;
   1.394 +            }
   1.395 +        }
   1.396 +    }
   1.397 +}
   1.398 +
   1.399 +
   1.400 +//-----------------------------------------------------------------------------------
   1.401 +// ***** InsertionSortSliced
   1.402 +//
   1.403 +// Sort any part of any array: plain, Array, ArrayPaged, ArrayUnsafe.
   1.404 +// The range is specified with start, end, where "end" is exclusive!
   1.405 +// The data type must have a defined "<" operator.
   1.406 +template<class Array> 
   1.407 +void InsertionSortSliced(Array& arr, size_t start, size_t end)
   1.408 +{
   1.409 +    typedef typename Array::ValueType ValueType;
   1.410 +    InsertionSortSliced(arr, start, end, OperatorLess<ValueType>::Compare);
   1.411 +}
   1.412 +
   1.413 +//-----------------------------------------------------------------------------------
   1.414 +// ***** InsertionSort
   1.415 +//
   1.416 +// Sort an array Array, ArrayPaged, ArrayUnsafe.
   1.417 +// The array must have GetSize() function.
   1.418 +// The comparison predicate must be specified.
   1.419 +
   1.420 +template<class Array, class Less> 
   1.421 +void InsertionSort(Array& arr, Less less)
   1.422 +{
   1.423 +    InsertionSortSliced(arr, 0, arr.GetSize(), less);
   1.424 +}
   1.425 +
   1.426 +//-----------------------------------------------------------------------------------
   1.427 +// ***** InsertionSort
   1.428 +//
   1.429 +// Sort an array Array, ArrayPaged, ArrayUnsafe.
   1.430 +// The array must have GetSize() function.
   1.431 +// The data type must have a defined "<" operator.
   1.432 +template<class Array> 
   1.433 +void InsertionSort(Array& arr)
   1.434 +{
   1.435 +    typedef typename Array::ValueType ValueType;
   1.436 +    InsertionSortSliced(arr, 0, arr.GetSize(), OperatorLess<ValueType>::Compare);
   1.437 +}
   1.438 +
   1.439 +//-----------------------------------------------------------------------------------
   1.440 +// ***** Median
   1.441 +// Returns a median value of the input array.
   1.442 +// Caveats: partially sorts the array, returns a reference to the array element
   1.443 +// TBD: This needs to be optimized and generalized
   1.444 +//
   1.445 +template<class Array> 
   1.446 +typename Array::ValueType& Median(Array& arr)
   1.447 +{
   1.448 +    size_t count = arr.GetSize();
   1.449 +    size_t mid = (count - 1) / 2;
   1.450 +    OVR_ASSERT(count > 0);
   1.451 +
   1.452 +	for (size_t j = 0; j <= mid; j++)
   1.453 +    {
   1.454 +		size_t min = j;
   1.455 +		for (size_t k = j + 1; k < count; k++)
   1.456 +            if (arr[k] < arr[min]) 
   1.457 +                min = k;
   1.458 +        Swap(arr[j], arr[min]);
   1.459 +    }
   1.460 +    return arr[mid];
   1.461 +}
   1.462 +
   1.463 +//-----------------------------------------------------------------------------------
   1.464 +// ***** LowerBoundSliced
   1.465 +//
   1.466 +template<class Array, class Value, class Less>
   1.467 +size_t LowerBoundSliced(const Array& arr, size_t start, size_t end, const Value& val, Less less)
   1.468 +{
   1.469 +    intptr_t first = (intptr_t)start;
   1.470 +    intptr_t len   = (intptr_t)(end - start);
   1.471 +    intptr_t half;
   1.472 +    intptr_t middle;
   1.473 +    
   1.474 +    while(len > 0) 
   1.475 +    {
   1.476 +        half = len >> 1;
   1.477 +        middle = first + half;
   1.478 +        if(less(arr[middle], val)) 
   1.479 +        {
   1.480 +            first = middle + 1;
   1.481 +            len   = len - half - 1;
   1.482 +        }
   1.483 +        else
   1.484 +        {
   1.485 +            len = half;
   1.486 +        }
   1.487 +    }
   1.488 +    return (size_t)first;
   1.489 +}
   1.490 +
   1.491 +
   1.492 +//-----------------------------------------------------------------------------------
   1.493 +// ***** LowerBoundSliced
   1.494 +//
   1.495 +template<class Array, class Value>
   1.496 +size_t LowerBoundSliced(const Array& arr, size_t start, size_t end, const Value& val)
   1.497 +{
   1.498 +    return LowerBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
   1.499 +}
   1.500 +
   1.501 +//-----------------------------------------------------------------------------------
   1.502 +// ***** LowerBoundSized
   1.503 +//
   1.504 +template<class Array, class Value>
   1.505 +size_t LowerBoundSized(const Array& arr, size_t size, const Value& val)
   1.506 +{
   1.507 +    return LowerBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
   1.508 +}
   1.509 +
   1.510 +//-----------------------------------------------------------------------------------
   1.511 +// ***** LowerBound
   1.512 +//
   1.513 +template<class Array, class Value, class Less>
   1.514 +size_t LowerBound(const Array& arr, const Value& val, Less less)
   1.515 +{
   1.516 +    return LowerBoundSliced(arr, 0, arr.GetSize(), val, less);
   1.517 +}
   1.518 +
   1.519 +
   1.520 +//-----------------------------------------------------------------------------------
   1.521 +// ***** LowerBound
   1.522 +//
   1.523 +template<class Array, class Value>
   1.524 +size_t LowerBound(const Array& arr, const Value& val)
   1.525 +{
   1.526 +    return LowerBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
   1.527 +}
   1.528 +
   1.529 +
   1.530 +
   1.531 +//-----------------------------------------------------------------------------------
   1.532 +// ***** UpperBoundSliced
   1.533 +//
   1.534 +template<class Array, class Value, class Less>
   1.535 +size_t UpperBoundSliced(const Array& arr, size_t start, size_t end, const Value& val, Less less)
   1.536 +{
   1.537 +    intptr_t first = (intptr_t)start;
   1.538 +    intptr_t len   = (intptr_t)(end - start);
   1.539 +    intptr_t half;
   1.540 +    intptr_t middle;
   1.541 +    
   1.542 +    while(len > 0) 
   1.543 +    {
   1.544 +        half = len >> 1;
   1.545 +        middle = first + half;
   1.546 +        if(less(val, arr[middle]))
   1.547 +        {
   1.548 +            len = half;
   1.549 +        }
   1.550 +        else 
   1.551 +        {
   1.552 +            first = middle + 1;
   1.553 +            len   = len - half - 1;
   1.554 +        }
   1.555 +    }
   1.556 +    return (size_t)first;
   1.557 +}
   1.558 +
   1.559 +
   1.560 +//-----------------------------------------------------------------------------------
   1.561 +// ***** UpperBoundSliced
   1.562 +//
   1.563 +template<class Array, class Value>
   1.564 +size_t UpperBoundSliced(const Array& arr, size_t start, size_t end, const Value& val)
   1.565 +{
   1.566 +    return UpperBoundSliced(arr, start, end, val, OperatorLess<Value>::Compare);
   1.567 +}
   1.568 +
   1.569 +
   1.570 +//-----------------------------------------------------------------------------------
   1.571 +// ***** UpperBoundSized
   1.572 +//
   1.573 +template<class Array, class Value>
   1.574 +size_t UpperBoundSized(const Array& arr, size_t size, const Value& val)
   1.575 +{
   1.576 +    return UpperBoundSliced(arr, 0, size, val, OperatorLess<Value>::Compare);
   1.577 +}
   1.578 +
   1.579 +
   1.580 +//-----------------------------------------------------------------------------------
   1.581 +// ***** UpperBound
   1.582 +//
   1.583 +template<class Array, class Value, class Less>
   1.584 +size_t UpperBound(const Array& arr, const Value& val, Less less)
   1.585 +{
   1.586 +    return UpperBoundSliced(arr, 0, arr.GetSize(), val, less);
   1.587 +}
   1.588 +
   1.589 +
   1.590 +//-----------------------------------------------------------------------------------
   1.591 +// ***** UpperBound
   1.592 +//
   1.593 +template<class Array, class Value>
   1.594 +size_t UpperBound(const Array& arr, const Value& val)
   1.595 +{
   1.596 +    return UpperBoundSliced(arr, 0, arr.GetSize(), val, OperatorLess<Value>::Compare);
   1.597 +}
   1.598 +
   1.599 +
   1.600 +//-----------------------------------------------------------------------------------
   1.601 +// ***** ReverseArray
   1.602 +//
   1.603 +template<class Array> void ReverseArray(Array& arr)
   1.604 +{
   1.605 +    intptr_t from = 0;
   1.606 +    intptr_t to   = arr.GetSize() - 1;
   1.607 +    while(from < to)
   1.608 +    {
   1.609 +        Swap(arr[from], arr[to]);
   1.610 +        ++from;
   1.611 +        --to;
   1.612 +    }
   1.613 +}
   1.614 +
   1.615 +
   1.616 +// ***** AppendArray
   1.617 +//
   1.618 +template<class CDst, class CSrc> 
   1.619 +void AppendArray(CDst& dst, const CSrc& src)
   1.620 +{
   1.621 +    size_t i;
   1.622 +    for(i = 0; i < src.GetSize(); i++) 
   1.623 +        dst.PushBack(src[i]);
   1.624 +}
   1.625 +
   1.626 +//-----------------------------------------------------------------------------------
   1.627 +// ***** ArrayAdaptor
   1.628 +//
   1.629 +// A simple adapter that provides the GetSize() method and overloads 
   1.630 +// operator []. Used to wrap plain arrays in QuickSort and such.
   1.631 +template<class T> class ArrayAdaptor
   1.632 +{
   1.633 +public:
   1.634 +    typedef T ValueType;
   1.635 +    ArrayAdaptor() : Data(0), Size(0) {}
   1.636 +    ArrayAdaptor(T* ptr, size_t size) : Data(ptr), Size(size) {}
   1.637 +    size_t GetSize() const { return Size; }
   1.638 +	int GetSizeI() const { return (int)GetSize(); }
   1.639 +    const T& operator [] (size_t i) const { return Data[i]; }
   1.640 +          T& operator [] (size_t i)       { return Data[i]; }
   1.641 +private:
   1.642 +    T*      Data;
   1.643 +    size_t  Size;
   1.644 +};
   1.645 +
   1.646 +
   1.647 +//-----------------------------------------------------------------------------------
   1.648 +// ***** GConstArrayAdaptor
   1.649 +//
   1.650 +// A simple const adapter that provides the GetSize() method and overloads 
   1.651 +// operator []. Used to wrap plain arrays in LowerBound and such.
   1.652 +template<class T> class ConstArrayAdaptor
   1.653 +{
   1.654 +public:
   1.655 +    typedef T ValueType;
   1.656 +    ConstArrayAdaptor() : Data(0), Size(0) {}
   1.657 +    ConstArrayAdaptor(const T* ptr, size_t size) : Data(ptr), Size(size) {}
   1.658 +    size_t GetSize() const { return Size; }
   1.659 +	int GetSizeI() const { return (int)GetSize(); }
   1.660 +	const T& operator [] (size_t i) const { return Data[i]; }
   1.661 +private:
   1.662 +    const T* Data;
   1.663 +    size_t   Size;
   1.664 +};
   1.665 +
   1.666 +
   1.667 +
   1.668 +//-----------------------------------------------------------------------------------
   1.669 +extern const uint8_t UpperBitTable[256];
   1.670 +extern const uint8_t LowerBitTable[256];
   1.671 +
   1.672 +
   1.673 +
   1.674 +//-----------------------------------------------------------------------------------
   1.675 +inline uint8_t UpperBit(size_t val)
   1.676 +{
   1.677 +#ifndef OVR_64BIT_POINTERS
   1.678 +
   1.679 +    if (val & 0xFFFF0000)
   1.680 +    {
   1.681 +        return (val & 0xFF000000) ? 
   1.682 +            UpperBitTable[(val >> 24)       ] + 24: 
   1.683 +            UpperBitTable[(val >> 16) & 0xFF] + 16;
   1.684 +    }
   1.685 +    return (val & 0xFF00) ?
   1.686 +        UpperBitTable[(val >> 8) & 0xFF] + 8:
   1.687 +        UpperBitTable[(val     ) & 0xFF];
   1.688 +
   1.689 +#else
   1.690 +
   1.691 +    if (val & 0xFFFFFFFF00000000)
   1.692 +    {
   1.693 +        if (val & 0xFFFF000000000000)
   1.694 +        {
   1.695 +            return (val & 0xFF00000000000000) ?
   1.696 +                UpperBitTable[(val >> 56)       ] + 56: 
   1.697 +                UpperBitTable[(val >> 48) & 0xFF] + 48;
   1.698 +        }
   1.699 +        return (val & 0xFF0000000000) ?
   1.700 +            UpperBitTable[(val >> 40) & 0xFF] + 40:
   1.701 +            UpperBitTable[(val >> 32) & 0xFF] + 32;
   1.702 +    }
   1.703 +    else
   1.704 +    {
   1.705 +        if (val & 0xFFFF0000)
   1.706 +        {
   1.707 +            return (val & 0xFF000000) ? 
   1.708 +                UpperBitTable[(val >> 24)       ] + 24: 
   1.709 +                UpperBitTable[(val >> 16) & 0xFF] + 16;
   1.710 +        }
   1.711 +        return (val & 0xFF00) ?
   1.712 +            UpperBitTable[(val >> 8) & 0xFF] + 8:
   1.713 +            UpperBitTable[(val     ) & 0xFF];
   1.714 +    }
   1.715 +
   1.716 +#endif
   1.717 +}
   1.718 +
   1.719 +//-----------------------------------------------------------------------------------
   1.720 +inline uint8_t LowerBit(size_t val)
   1.721 +{
   1.722 +#ifndef OVR_64BIT_POINTERS
   1.723 +
   1.724 +    if (val & 0xFFFF)
   1.725 +    {
   1.726 +        return (val & 0xFF) ?
   1.727 +            LowerBitTable[ val & 0xFF]:
   1.728 +            LowerBitTable[(val >> 8) & 0xFF] + 8;
   1.729 +    }
   1.730 +    return (val & 0xFF0000) ?
   1.731 +            LowerBitTable[(val >> 16) & 0xFF] + 16:
   1.732 +            LowerBitTable[(val >> 24) & 0xFF] + 24;
   1.733 +
   1.734 +#else
   1.735 +
   1.736 +    if (val & 0xFFFFFFFF)
   1.737 +    {
   1.738 +        if (val & 0xFFFF)
   1.739 +        {
   1.740 +            return (val & 0xFF) ?
   1.741 +                LowerBitTable[ val & 0xFF]:
   1.742 +                LowerBitTable[(val >> 8) & 0xFF] + 8;
   1.743 +        }
   1.744 +        return (val & 0xFF0000) ?
   1.745 +                LowerBitTable[(val >> 16) & 0xFF] + 16:
   1.746 +                LowerBitTable[(val >> 24) & 0xFF] + 24;
   1.747 +    }
   1.748 +    else
   1.749 +    {
   1.750 +        if (val & 0xFFFF00000000)
   1.751 +        {
   1.752 +             return (val & 0xFF00000000) ?
   1.753 +                LowerBitTable[(val >> 32) & 0xFF] + 32:
   1.754 +                LowerBitTable[(val >> 40) & 0xFF] + 40;
   1.755 +        }
   1.756 +        return (val & 0xFF000000000000) ?
   1.757 +            LowerBitTable[(val >> 48) & 0xFF] + 48:
   1.758 +            LowerBitTable[(val >> 56) & 0xFF] + 56;
   1.759 +    }
   1.760 +
   1.761 +#endif
   1.762 +}
   1.763 +
   1.764 +
   1.765 +
   1.766 +// ******* Special (optimized) memory routines
   1.767 +// Note: null (bad) pointer is not tested
   1.768 +class MemUtil
   1.769 +{
   1.770 +public:
   1.771 +                                    
   1.772 +    // Memory compare
   1.773 +    static int      Cmp  (const void* p1, const void* p2, size_t byteCount)      { return memcmp(p1, p2, byteCount); }
   1.774 +    static int      Cmp16(const void* p1, const void* p2, size_t int16Count);
   1.775 +    static int      Cmp32(const void* p1, const void* p2, size_t int32Count);
   1.776 +    static int      Cmp64(const void* p1, const void* p2, size_t int64Count); 
   1.777 +};
   1.778 +
   1.779 +// ** Inline Implementation
   1.780 +
   1.781 +inline int MemUtil::Cmp16(const void* p1, const void* p2, size_t int16Count)
   1.782 +{
   1.783 +    int16_t*  pa  = (int16_t*)p1; 
   1.784 +    int16_t*  pb  = (int16_t*)p2;
   1.785 +    unsigned ic  = 0;
   1.786 +    if (int16Count == 0)
   1.787 +        return 0;
   1.788 +    while (pa[ic] == pb[ic])
   1.789 +        if (++ic==int16Count)
   1.790 +            return 0;
   1.791 +    return pa[ic] > pb[ic] ? 1 : -1;
   1.792 +}
   1.793 +inline int MemUtil::Cmp32(const void* p1, const void* p2, size_t int32Count)
   1.794 +{
   1.795 +    int32_t*  pa  = (int32_t*)p1;
   1.796 +    int32_t*  pb  = (int32_t*)p2;
   1.797 +    unsigned ic  = 0;
   1.798 +    if (int32Count == 0)
   1.799 +        return 0;
   1.800 +    while (pa[ic] == pb[ic])
   1.801 +        if (++ic==int32Count)
   1.802 +            return 0;
   1.803 +    return pa[ic] > pb[ic] ? 1 : -1;
   1.804 +}
   1.805 +inline int MemUtil::Cmp64(const void* p1, const void* p2, size_t int64Count)
   1.806 +{
   1.807 +    int64_t*  pa  = (int64_t*)p1;
   1.808 +    int64_t*  pb  = (int64_t*)p2;
   1.809 +    unsigned ic  = 0;
   1.810 +    if (int64Count == 0)
   1.811 +        return 0;
   1.812 +    while (pa[ic] == pb[ic])
   1.813 +        if (++ic==int64Count)
   1.814 +            return 0;
   1.815 +    return pa[ic] > pb[ic] ? 1 : -1;
   1.816 +}
   1.817 +
   1.818 +// ** End Inline Implementation
   1.819 +
   1.820 +
   1.821 +//-----------------------------------------------------------------------------------
   1.822 +// ******* Byte Order Conversions
   1.823 +namespace ByteUtil {
   1.824 +
   1.825 +    // *** Swap Byte Order
   1.826 +
   1.827 +    // Swap the byte order of a byte array
   1.828 +    inline void     SwapOrder(void* pv, int size)
   1.829 +    {
   1.830 +        uint8_t*  pb = (uint8_t*)pv;
   1.831 +        uint8_t temp;
   1.832 +        for (int i = 0; i < size>>1; i++)
   1.833 +        { 
   1.834 +            temp            = pb[size-1-i];
   1.835 +            pb[size-1-i]    = pb[i];
   1.836 +            pb[i]           = temp; 
   1.837 +        }
   1.838 +    }
   1.839 +
   1.840 +    // Swap the byte order of primitive types
   1.841 +    inline uint8_t  SwapOrder(uint8_t v)    { return v; }
   1.842 +    inline int8_t   SwapOrder(int8_t v)     { return v; }
   1.843 +    inline uint16_t SwapOrder(uint16_t v)   { return uint16_t(v>>8)|uint16_t(v<<8); }
   1.844 +    inline int16_t  SwapOrder(int16_t v)    { return int16_t((uint16_t(v)>>8)|(v<<8)); }
   1.845 +    inline uint32_t SwapOrder(uint32_t v)   { return (v>>24)|((v&0x00FF0000)>>8)|((v&0x0000FF00)<<8)|(v<<24); }
   1.846 +    inline int32_t  SwapOrder(int32_t p)    { return (int32_t)SwapOrder(uint32_t(p)); }
   1.847 +    inline uint64_t SwapOrder(uint64_t v)
   1.848 +    { 
   1.849 +        return   (v>>56) |
   1.850 +                 ((v&uint64_t(0x00FF000000000000ULL))>>40) |
   1.851 +                 ((v&uint64_t(0x0000FF0000000000ULL))>>24) |
   1.852 +                 ((v&uint64_t(0x000000FF00000000ULL))>>8)  |
   1.853 +                 ((v&uint64_t(0x00000000FF000000ULL))<<8)  |
   1.854 +                 ((v&uint64_t(0x0000000000FF0000ULL))<<24) |
   1.855 +                 ((v&uint64_t(0x000000000000FF00ULL))<<40) |
   1.856 +                 (v<<56); 
   1.857 +    }
   1.858 +    inline int64_t  SwapOrder(int64_t v)     { return (int64_t)SwapOrder(uint64_t(v)); }
   1.859 +    inline float    SwapOrder(float p)      
   1.860 +    { 
   1.861 +        union {
   1.862 +            float p;
   1.863 +            uint32_t v;
   1.864 +        } u;
   1.865 +        u.p = p;
   1.866 +        u.v = SwapOrder(u.v);
   1.867 +        return u.p;
   1.868 +    }
   1.869 +
   1.870 +    inline double   SwapOrder(double p)
   1.871 +    { 
   1.872 +        union {
   1.873 +            double p;
   1.874 +            uint64_t v;
   1.875 +        } u;
   1.876 +        u.p = p;
   1.877 +        u.v = SwapOrder(u.v);
   1.878 +        return u.p;
   1.879 +    }
   1.880 +    
   1.881 +    // *** Byte-order conversion
   1.882 +
   1.883 +#if (OVR_BYTE_ORDER == OVR_LITTLE_ENDIAN)
   1.884 +    // Little Endian to System (LE)
   1.885 +    inline uint8_t  LEToSystem(uint8_t v)   { return v; }
   1.886 +    inline int8_t   LEToSystem(int8_t v)    { return v; }
   1.887 +    inline uint16_t LEToSystem(uint16_t v)  { return v; }
   1.888 +    inline int16_t  LEToSystem(int16_t v)   { return v; }
   1.889 +    inline uint32_t LEToSystem(uint32_t v)  { return v; }
   1.890 +    inline int32_t  LEToSystem(int32_t v)   { return v; }
   1.891 +    inline uint64_t LEToSystem(uint64_t v)  { return v; }
   1.892 +    inline int64_t  LEToSystem(int64_t v)    { return v; }
   1.893 +    inline float    LEToSystem(float  v)    { return v; }
   1.894 +    inline double   LEToSystem(double v)    { return v; }
   1.895 +
   1.896 +    // Big Endian to System (LE)
   1.897 +    inline uint8_t  BEToSystem(uint8_t v)   { return SwapOrder(v); }
   1.898 +    inline int8_t   BEToSystem(int8_t v)    { return SwapOrder(v); }
   1.899 +    inline uint16_t BEToSystem(uint16_t v)  { return SwapOrder(v); }
   1.900 +    inline int16_t  BEToSystem(int16_t v)   { return SwapOrder(v); }
   1.901 +    inline uint32_t BEToSystem(uint32_t v)  { return SwapOrder(v); }
   1.902 +    inline int32_t  BEToSystem(int32_t v)   { return SwapOrder(v); }
   1.903 +    inline uint64_t BEToSystem(uint64_t v)  { return SwapOrder(v); }
   1.904 +    inline int64_t  BEToSystem(int64_t v)    { return SwapOrder(v); }
   1.905 +    inline float    BEToSystem(float  v)    { return SwapOrder(v); }
   1.906 +    inline double   BEToSystem(double v)    { return SwapOrder(v); }
   1.907 +
   1.908 +    // System (LE) to Little Endian
   1.909 +    inline uint8_t  SystemToLE(uint8_t v)   { return v; }
   1.910 +    inline int8_t   SystemToLE(int8_t v)    { return v; }
   1.911 +    inline uint16_t SystemToLE(uint16_t v)  { return v; }
   1.912 +    inline int16_t  SystemToLE(int16_t v)   { return v; }
   1.913 +    inline uint32_t SystemToLE(uint32_t v)  { return v; }
   1.914 +    inline int32_t  SystemToLE(int32_t v)   { return v; }
   1.915 +    inline uint64_t SystemToLE(uint64_t v)  { return v; }
   1.916 +    inline int64_t  SystemToLE(int64_t v)    { return v; }
   1.917 +    inline float    SystemToLE(float  v)    { return v; }
   1.918 +    inline double   SystemToLE(double v)    { return v; }   
   1.919 +
   1.920 +    // System (LE) to Big Endian
   1.921 +    inline uint8_t  SystemToBE(uint8_t v)   { return SwapOrder(v); }
   1.922 +    inline int8_t   SystemToBE(int8_t v)    { return SwapOrder(v); }
   1.923 +    inline uint16_t SystemToBE(uint16_t v)  { return SwapOrder(v); }
   1.924 +    inline int16_t  SystemToBE(int16_t v)   { return SwapOrder(v); }
   1.925 +    inline uint32_t SystemToBE(uint32_t v)  { return SwapOrder(v); }
   1.926 +    inline int32_t  SystemToBE(int32_t v)   { return SwapOrder(v); }
   1.927 +    inline uint64_t SystemToBE(uint64_t v)  { return SwapOrder(v); }
   1.928 +    inline int64_t  SystemToBE(int64_t v)    { return SwapOrder(v); }
   1.929 +    inline float    SystemToBE(float  v)    { return SwapOrder(v); }
   1.930 +    inline double   SystemToBE(double v)    { return SwapOrder(v); }
   1.931 +
   1.932 +#elif (OVR_BYTE_ORDER == OVR_BIG_ENDIAN)
   1.933 +    // Little Endian to System (BE)
   1.934 +    inline uint8_t  LEToSystem(uint8_t  v)  { return SwapOrder(v); }
   1.935 +    inline int8_t   LEToSystem(int8_t v)    { return SwapOrder(v); }
   1.936 +    inline uint16_t LEToSystem(uint16_t v)  { return SwapOrder(v); }
   1.937 +    inline int16_t  LEToSystem(int16_t v)   { return SwapOrder(v); }
   1.938 +    inline uint32_t LEToSystem(uint32_t v)  { return SwapOrder(v); }
   1.939 +    inline int32_t  LEToSystem(int32_t v)   { return SwapOrder(v); }
   1.940 +    inline uint64_t LEToSystem(uint64_t v)  { return SwapOrder(v); }
   1.941 +    inline int64_t  LEToSystem(int64_t v)    { return SwapOrder(v); }
   1.942 +    inline float    LEToSystem(float  v)    { return SwapOrder(v); }
   1.943 +    inline double   LEToSystem(double v)    { return SwapOrder(v); }
   1.944 +
   1.945 +    // Big Endian to System (BE)
   1.946 +    inline uint8_t  BEToSystem(uint8_t v)   { return v; }
   1.947 +    inline int8_t   BEToSystem(int8_t v)    { return v; }
   1.948 +    inline uint16_t BEToSystem(uint16_t v)  { return v; }
   1.949 +    inline int16_t  BEToSystem(int16_t v)   { return v; }
   1.950 +    inline uint32_t BEToSystem(uint32_t v)  { return v; }
   1.951 +    inline int32_t  BEToSystem(int32_t v)   { return v; }
   1.952 +    inline uint64_t BEToSystem(uint64_t v)  { return v; }
   1.953 +    inline int64_t  BEToSystem(int64_t v)    { return v; }
   1.954 +    inline float    BEToSystem(float  v)    { return v; }
   1.955 +    inline double   BEToSystem(double v)    { return v; }
   1.956 +
   1.957 +    // System (BE) to Little Endian
   1.958 +    inline uint8_t  SystemToLE(uint8_t v)   { return SwapOrder(v); }
   1.959 +    inline int8_t   SystemToLE(int8_t v)    { return SwapOrder(v); }
   1.960 +    inline uint16_t SystemToLE(uint16_t v)  { return SwapOrder(v); }
   1.961 +    inline int16_t  SystemToLE(int16_t v)   { return SwapOrder(v); }
   1.962 +    inline uint32_t SystemToLE(uint32_t v)  { return SwapOrder(v); }
   1.963 +    inline int32_t  SystemToLE(int32_t v)   { return SwapOrder(v); }
   1.964 +    inline uint64_t SystemToLE(uint64_t v)  { return SwapOrder(v); }
   1.965 +    inline int64_t  SystemToLE(int64_t v)    { return SwapOrder(v); }
   1.966 +    inline float    SystemToLE(float  v)    { return SwapOrder(v); }
   1.967 +    inline double   SystemToLE(double v)    { return SwapOrder(v); }
   1.968 +
   1.969 +    // System (BE) to Big Endian
   1.970 +    inline uint8_t  SystemToBE(uint8_t v)   { return v; }
   1.971 +    inline int8_t   SystemToBE(int8_t v)    { return v; }
   1.972 +    inline uint16_t SystemToBE(uint16_t v)  { return v; }
   1.973 +    inline int16_t  SystemToBE(int16_t v)   { return v; }
   1.974 +    inline uint32_t SystemToBE(uint32_t v)  { return v; }
   1.975 +    inline int32_t  SystemToBE(int32_t v)   { return v; }
   1.976 +    inline uint64_t SystemToBE(uint64_t v)  { return v; }
   1.977 +    inline int64_t  SystemToBE(int64_t v)    { return v; }
   1.978 +    inline float    SystemToBE(float  v)    { return v; }
   1.979 +    inline double   SystemToBE(double v)    { return v; }
   1.980 +
   1.981 +#else
   1.982 +    #error "OVR_BYTE_ORDER must be defined to OVR_LITTLE_ENDIAN or OVR_BIG_ENDIAN"
   1.983 +#endif
   1.984 +
   1.985 +} // namespace ByteUtil
   1.986 +
   1.987 +
   1.988 +
   1.989 +// Used primarily for hardware interfacing such as sensor reports, firmware, etc.
   1.990 +// Reported data is all little-endian.
   1.991 +inline uint16_t DecodeUInt16(const uint8_t* buffer)
   1.992 +{
   1.993 +    return ByteUtil::LEToSystem ( *(const uint16_t*)buffer );
   1.994 +}
   1.995 +
   1.996 +inline int16_t DecodeSInt16(const uint8_t* buffer)
   1.997 +{
   1.998 +    return ByteUtil::LEToSystem ( *(const int16_t*)buffer );
   1.999 +}
  1.1000 +
  1.1001 +inline uint32_t DecodeUInt32(const uint8_t* buffer)
  1.1002 +{    
  1.1003 +    return ByteUtil::LEToSystem ( *(const uint32_t*)buffer );
  1.1004 +}
  1.1005 +
  1.1006 +inline int32_t DecodeSInt32(const uint8_t* buffer)
  1.1007 +{    
  1.1008 +    return ByteUtil::LEToSystem ( *(const int32_t*)buffer );
  1.1009 +}
  1.1010 +
  1.1011 +inline float DecodeFloat(const uint8_t* buffer)
  1.1012 +{
  1.1013 +    union {
  1.1014 +        uint32_t U;
  1.1015 +        float  F;
  1.1016 +    };
  1.1017 +
  1.1018 +    U = DecodeUInt32(buffer);
  1.1019 +    return F;
  1.1020 +}
  1.1021 +
  1.1022 +inline void EncodeUInt16(uint8_t* buffer, uint16_t val)
  1.1023 +{
  1.1024 +    *(uint16_t*)buffer = ByteUtil::SystemToLE ( val );
  1.1025 +}
  1.1026 +
  1.1027 +inline void EncodeSInt16(uint8_t* buffer, int16_t val)
  1.1028 +{
  1.1029 +    *(int16_t*)buffer = ByteUtil::SystemToLE ( val );
  1.1030 +}
  1.1031 +
  1.1032 +inline void EncodeUInt32(uint8_t* buffer, uint32_t val)
  1.1033 +{
  1.1034 +    *(uint32_t*)buffer = ByteUtil::SystemToLE ( val );
  1.1035 +}
  1.1036 +
  1.1037 +inline void EncodeSInt32(uint8_t* buffer, int32_t val)
  1.1038 +{
  1.1039 +    *(int32_t*)buffer = ByteUtil::SystemToLE ( val );
  1.1040 +}
  1.1041 +
  1.1042 +inline void EncodeFloat(uint8_t* buffer, float val)
  1.1043 +{
  1.1044 +    union {
  1.1045 +        uint32_t U;
  1.1046 +        float  F;
  1.1047 +    };
  1.1048 +
  1.1049 +    F = val;
  1.1050 +    EncodeUInt32(buffer, U);
  1.1051 +}
  1.1052 +
  1.1053 +// Converts an 8-bit binary-coded decimal
  1.1054 +inline int8_t DecodeBCD(uint8_t byte)
  1.1055 +{
  1.1056 +    uint8_t digit1 = (byte >> 4) & 0x0f;
  1.1057 +    uint8_t digit2 = byte & 0x0f;
  1.1058 +    int decimal = digit1 * 10 + digit2;   // maximum value = 99
  1.1059 +    return (int8_t)decimal;
  1.1060 +}
  1.1061 +
  1.1062 +
  1.1063 +}} // OVR::Alg
  1.1064 +
  1.1065 +#endif