search the index in the array, that has the largest value smaller than or equal to the given value, given array must be sorted (if no value is smaller, it returns the size of the given array)*/
| 1296 | /*search the index in the array, that has the largest value smaller than or equal to the given value, |
| 1297 | given array must be sorted (if no value is smaller, it returns the size of the given array)*/ |
| 1298 | static size_t searchCodeIndex(const unsigned* array, size_t array_size, size_t value) |
| 1299 | { |
| 1300 | /*linear search implementation*/ |
| 1301 | /*for(size_t i = 1; i < array_size; i++) if(array[i] > value) return i - 1; |
| 1302 | return array_size - 1;*/ |
| 1303 | |
| 1304 | /*binary search implementation (not that much faster) (precondition: array_size > 0)*/ |
| 1305 | size_t left = 1; |
| 1306 | size_t right = array_size - 1; |
| 1307 | while(left <= right) |
| 1308 | { |
| 1309 | size_t mid = (left + right) / 2; |
| 1310 | if(array[mid] <= value) left = mid + 1; /*the value to find is more to the right*/ |
| 1311 | else if(array[mid - 1] > value) right = mid - 1; /*the value to find is more to the left*/ |
| 1312 | else return mid - 1; |
| 1313 | } |
| 1314 | return array_size - 1; |
| 1315 | } |
| 1316 | |
| 1317 | static void addLengthDistance(uivector* values, size_t length, size_t distance) |
| 1318 | { |