DOOM-3-BFG

DOOM 3 BFG Edition
Log | Files | Refs

BinSearch.h (3861B)

      1 /*
      2 ===========================================================================
      3 
      4 Doom 3 BFG Edition GPL Source Code
      5 Copyright (C) 1993-2012 id Software LLC, a ZeniMax Media company. 
      6 
      7 This file is part of the Doom 3 BFG Edition GPL Source Code ("Doom 3 BFG Edition Source Code").  
      8 
      9 Doom 3 BFG Edition Source Code is free software: you can redistribute it and/or modify
     10 it under the terms of the GNU General Public License as published by
     11 the Free Software Foundation, either version 3 of the License, or
     12 (at your option) any later version.
     13 
     14 Doom 3 BFG Edition Source Code is distributed in the hope that it will be useful,
     15 but WITHOUT ANY WARRANTY; without even the implied warranty of
     16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     17 GNU General Public License for more details.
     18 
     19 You should have received a copy of the GNU General Public License
     20 along with Doom 3 BFG Edition Source Code.  If not, see <http://www.gnu.org/licenses/>.
     21 
     22 In addition, the Doom 3 BFG Edition Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 BFG Edition Source Code.  If not, please request a copy in writing from id Software at the address below.
     23 
     24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
     25 
     26 ===========================================================================
     27 */
     28 
     29 #ifndef __BINSEARCH_H__
     30 #define __BINSEARCH_H__
     31 
     32 /*
     33 ===============================================================================
     34 
     35 	Binary Search templates
     36 
     37 	The array elements have to be ordered in increasing order.
     38 
     39 ===============================================================================
     40 */
     41 
     42 /*
     43 ====================
     44 idBinSearch_GreaterEqual
     45 
     46 	Finds the last array element which is smaller than the given value.
     47 ====================
     48 */
     49 template< class type >
     50 ID_INLINE int idBinSearch_Less( const type *array, const int arraySize, const type &value ) {
     51 	int len = arraySize;
     52 	int mid = len;
     53 	int offset = 0;
     54 	while( mid > 0 ) {
     55 		mid = len >> 1;
     56 		if ( array[offset+mid] < value ) {
     57 			offset += mid;
     58 		}
     59 		len -= mid;
     60 	}
     61 	return offset;
     62 }
     63 
     64 /*
     65 ====================
     66 idBinSearch_GreaterEqual
     67 
     68 	Finds the last array element which is smaller than or equal to the given value.
     69 ====================
     70 */
     71 template< class type >
     72 ID_INLINE int idBinSearch_LessEqual( const type *array, const int arraySize, const type &value ) {
     73 	int len = arraySize;
     74 	int mid = len;
     75 	int offset = 0;
     76 	while( mid > 0 ) {
     77 		mid = len >> 1;
     78 		if ( array[offset+mid] <= value ) {
     79 			offset += mid;
     80 		}
     81 		len -= mid;
     82 	}
     83 	return offset;
     84 }
     85 
     86 /*
     87 ====================
     88 idBinSearch_Greater
     89 
     90 	Finds the first array element which is greater than the given value.
     91 ====================
     92 */
     93 template< class type >
     94 ID_INLINE int idBinSearch_Greater( const type *array, const int arraySize, const type &value ) {
     95 	int len = arraySize;
     96 	int mid = len;
     97 	int offset = 0;
     98 	int res = 0;
     99 	while( mid > 0 ) {
    100 		mid = len >> 1;
    101 		if ( array[offset+mid] > value ) {
    102 			res = 0;
    103 		} else {
    104 			offset += mid;
    105 			res = 1;
    106 		}
    107 		len -= mid;
    108 	}
    109 	return offset+res;
    110 }
    111 
    112 /*
    113 ====================
    114 idBinSearch_GreaterEqual
    115 
    116 	Finds the first array element which is greater than or equal to the given value.
    117 ====================
    118 */
    119 template< class type >
    120 ID_INLINE int idBinSearch_GreaterEqual( const type *array, const int arraySize, const type &value ) {
    121 	int len = arraySize;
    122 	int mid = len;
    123 	int offset = 0;
    124 	int res = 0;
    125 	while( mid > 0 ) {
    126 		mid = len >> 1;
    127 		if ( array[offset+mid] >= value ) {
    128 			res = 0;
    129 		} else {
    130 			offset += mid;
    131 			res = 1;
    132 		}
    133 		len -= mid;
    134 	}
    135 	return offset+res;
    136 }
    137 
    138 #endif /* !__BINSEARCH_H__ */