home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2006 March / Gamestar_82_2006-03_dvd.iso / DVDStar / Editace / quake4_sdkv10.exe / source / idlib / containers / BinSearch.h next >
C/C++ Source or Header  |  2005-11-14  |  2KB  |  112 lines
  1.  
  2. #ifndef __BINSEARCH_H__
  3. #define __BINSEARCH_H__
  4.  
  5. /*
  6. ===============================================================================
  7.  
  8.     Binary Search templates
  9.  
  10.     The array elements have to be ordered in increasing order.
  11.  
  12. ===============================================================================
  13. */
  14.  
  15. /*
  16. ====================
  17. idBinSearch_GreaterEqual
  18.  
  19.     Finds the last array element which is smaller than the given value.
  20. ====================
  21. */
  22. template< class type >
  23. ID_INLINE int idBinSearch_Less( const type *array, const int arraySize, const type &value ) {
  24.     int len = arraySize;
  25.     int mid = len;
  26.     int offset = 0;
  27.     while( mid > 0 ) {
  28.         mid = len >> 1;
  29.         if ( array[offset+mid] < value ) {
  30.             offset += mid;
  31.         }
  32.         len -= mid;
  33.     }
  34.     return offset;
  35. }
  36.  
  37. /*
  38. ====================
  39. idBinSearch_GreaterEqual
  40.  
  41.     Finds the last array element which is smaller than or equal to the given value.
  42. ====================
  43. */
  44. template< class type >
  45. ID_INLINE int idBinSearch_LessEqual( const type *array, const int arraySize, const type &value ) {
  46.     int len = arraySize;
  47.     int mid = len;
  48.     int offset = 0;
  49.     while( mid > 0 ) {
  50.         mid = len >> 1;
  51.         if ( array[offset+mid] <= value ) {
  52.             offset += mid;
  53.         }
  54.         len -= mid;
  55.     }
  56.     return offset;
  57. }
  58.  
  59. /*
  60. ====================
  61. idBinSearch_Greater
  62.  
  63.     Finds the first array element which is greater than the given value.
  64. ====================
  65. */
  66. template< class type >
  67. ID_INLINE int idBinSearch_Greater( const type *array, const int arraySize, const type &value ) {
  68.     int len = arraySize;
  69.     int mid = len;
  70.     int offset = 0;
  71.     int res = 0;
  72.     while( mid > 0 ) {
  73.         mid = len >> 1;
  74.         if ( array[offset+mid] > value ) {
  75.             res = 0;
  76.         } else {
  77.             offset += mid;
  78.             res = 1;
  79.         }
  80.         len -= mid;
  81.     }
  82.     return offset+res;
  83. }
  84.  
  85. /*
  86. ====================
  87. idBinSearch_GreaterEqual
  88.  
  89.     Finds the first array element which is greater than or equal to the given value.
  90. ====================
  91. */
  92. template< class type >
  93. ID_INLINE int idBinSearch_GreaterEqual( const type *array, const int arraySize, const type &value ) {
  94.     int len = arraySize;
  95.     int mid = len;
  96.     int offset = 0;
  97.     int res = 0;
  98.     while( mid > 0 ) {
  99.         mid = len >> 1;
  100.         if ( array[offset+mid] >= value ) {
  101.             res = 0;
  102.         } else {
  103.             offset += mid;
  104.             res = 1;
  105.         }
  106.         len -= mid;
  107.     }
  108.     return offset+res;
  109. }
  110.  
  111. #endif /* !__BINSEARCH_H__ */
  112.