1 /// Algorithms for searching in a range. 2 module tern.algorithm.searching; 3 4 // TODO: Barter? 5 import tern.traits; 6 import tern.typecons; 7 import tern.functional; 8 import tern.object : loadLength; 9 import tern.memory : memchr, reference; 10 11 public: 12 /** 13 * Searches for the index of the given argument in `range`. 14 * 15 * Params: 16 * range = The range to search in. 17 * 18 * Returns: 19 * The index of the given argument in `range` or -1 if not found. 20 */ 21 size_t indexOf(A, B)(A range, B elem) 22 if (isIndexable!A && isElement!(A, B)) 23 { 24 static if ((B.sizeof == 1 || B.sizeof == 2 || B.sizeof == 4 || 25 B.sizeof == 8 || B.sizeof == 16) && (isDynamicArray!A || isStaticArray!A)) 26 { 27 if ((B.sizeof * range.loadLength) % 16 == 0) 28 return memchr!0(reference!range, B.sizeof * range.loadLength, elem); 29 } 30 31 foreach (i; 0..range.loadLength) 32 { 33 if (range[i] == elem) 34 return i; 35 } 36 return -1; 37 } 38 39 /// ditto 40 size_t indexOf(A, B)(A range, B subrange) 41 if (isIndexable!A && !isElement!(A, B) && isIndexable!B) 42 { 43 if (subrange.loadLength > range.loadLength) 44 return -1; 45 46 foreach (i; 0..(range.loadLength - subrange.loadLength + 1)) 47 { 48 if (range[i..(i + subrange.loadLength)] == subrange) 49 return i; 50 } 51 return -1; 52 } 53 54 /// ditto 55 size_t indexOf(alias F, A)(A range) 56 if (isIndexable!A && isCallable!F) 57 { 58 foreach (i; 0..range.loadLength) 59 { 60 if (F(range[i])) 61 return i; 62 } 63 return -1; 64 } 65 66 /** 67 * Searches for the last index of the given argument in `range`. 68 * 69 * Params: 70 * range = The range to search in. 71 * 72 * Returns: 73 * The last index of the given argument in `range` or -1 if not found. 74 */ 75 size_t lastIndexOf(A, B)(A range, B elem) 76 if (isIndexable!A && isElement!(A, B)) 77 { 78 static if ((B.sizeof == 1 || B.sizeof == 2 || B.sizeof == 4 || 79 B.sizeof == 8 || B.sizeof == 16) && (isDynamicArray!A || isStaticArray!A)) 80 { 81 if ((B.sizeof * range.loadLength) % 16 == 0) 82 return memchr!1(reference!range, B.sizeof * range.loadLength, elem); 83 } 84 85 foreach (i; 0..range.loadLength) 86 { 87 if (range[i] == elem) 88 return i; 89 } 90 return -1; 91 } 92 93 /// ditto 94 size_t lastIndexOf(A, B)(A range, B subrange) 95 if (isIndexable!A && !isElement!(A, B) && isIndexable!B) 96 { 97 if (subrange.loadLength >= range.loadLength) 98 return -1; 99 100 foreach_reverse (i; 0..(range.loadLength - subrange.loadLength + 1)) 101 { 102 if (range[i..(i + subrange.loadLength)] == subrange) 103 return i; 104 } 105 return -1; 106 } 107 108 /// ditto 109 size_t lastIndexOf(alias F, A)(A range) 110 if (isIndexable!A && isCallable!F) 111 { 112 foreach_reverse (i; 0..range.loadLength) 113 { 114 if (F(range[i])) 115 return i; 116 } 117 return -1; 118 } 119 120 /** 121 * Portions `range` into blocks of `blockSize`, with optional padding. 122 * 123 * Params: 124 * range = The range to be portioned. 125 * blockSize = The size of the blocks to be portioned. 126 * pad = Should the range be padded? Defaults to true. 127 * 128 * Returns: 129 * `range` portioned into blocks of `blockSize`. 130 */ 131 T[] portionBy(T)(ref T range, size_t blockSize, bool pad = true) 132 if (isIndexable!T) 133 { 134 if (pad) 135 range ~= new ElementType!T[blockSize - (range.loadLength % blockSize)]; 136 137 T[] ret; 138 foreach (i; 0..((range.loadLength / 8) - 1)) 139 ret ~= range[(i * 8)..((i + 1) * 8)]; 140 return ret; 141 } 142 143 /** 144 * Portions `range` into blocks of `blockSize`. 145 * 146 * Params: 147 * range = The range to be portioned. 148 * blockSize = The size of the blocks to be portioned. 149 * pad = Should the range be padded? Defaults to true. 150 * 151 * Returns: 152 * `range` portioned into blocks of `blockSize`. 153 */ 154 P[] portionTo(P, T)(ref T range) 155 if (isIndexable!T) 156 { 157 static if (!isStaticArray!T) 158 range ~= new ElementType!T[P.sizeof - (range.loadLength % P.sizeof)]; 159 else 160 static assert(Length!T % P.sizeof == 0, "Static range cannot be portioned, does not align to size!"); 161 162 P[] ret; 163 foreach (i; 0..((range.loadLength / P.sizeof) - 1)) 164 ret ~= *cast(P*)(&range[(i * P.sizeof)]); 165 return ret; 166 } 167 168 /** 169 * Searches for the index of the given argument in `range`. 170 * 171 * Params: 172 * range = The range to search in. 173 * 174 * Returns: 175 * The index of the given argument in `range` or -1 if not found. 176 */ 177 size_t countUntil(A, B)(A range, B elem) 178 if (isIndexable!A && isElement!(A, B)) 179 { 180 return range.indexOf(elem); 181 } 182 183 /// ditto 184 size_t countUntil(A, B)(A range, B subrange) 185 if (isIndexable!A && !isElement!(A, B) && isIndexable!B) 186 { 187 return range.indexOf(subrange); 188 } 189 190 /// ditto 191 size_t countUntil(alias F, A)(A range) 192 if (isForward!A) 193 { 194 return range.indexOf!F; 195 } 196 197 /** 198 * Searches for the last index of the given argument in `range`. 199 * 200 * Params: 201 * range = The range to search in. 202 * 203 * Returns: 204 * The last index of the given argument in `range` with 1-based indexing or -1 if not found. 205 */ 206 size_t among(alias F, A)(A range) 207 if (isIndexable!A) 208 { 209 return range.indexOf!F + 1; 210 } 211 212 /** 213 * Checks if `range` contains `elem`. 214 * 215 * Params: 216 * range = The range to search in. 217 * elem = The element to search for. 218 * 219 * Returns: 220 * True if `range` contains `elem`. 221 */ 222 bool contains(A, B)(A range, B elem) 223 if (isIndexable!A && isElement!(A, B)) 224 { 225 return range.indexOf(elem) != -1; 226 } 227 228 /** 229 * Checks if `range` contains `subrange`. 230 * 231 * Params: 232 * range = The range to search in. 233 * subrange = The range to search for. 234 * 235 * Returns: 236 * True if `range` contains `subrange`. 237 */ 238 bool contains(A, B)(A range, B subrange) 239 if (isIndexable!A && !isElement!(A, B) && isIndexable!B) 240 { 241 return range.indexOf(subrange) != -1; 242 } 243 244 /// ditto 245 bool contains(alias F, A)(A range) 246 if (isIndexable!A && isCallable!F) 247 { 248 return range.indexOf!F != -1; 249 } 250 251 /// ditto 252 bool canFind(A, B)(A range, B elem) 253 if (isIndexable!A && isElement!(A, B)) 254 { 255 return indexOf(range, elem) != -1; 256 } 257 258 /// ditto 259 bool canFind(A, B)(A range, B subrange) 260 if (isIndexable!A && !isElement!(A, B) && isIndexable!B) 261 { 262 return indexOf(range, subrange) != -1; 263 } 264 265 /// ditto 266 bool canFind(alias F, A)(A range) 267 if (isIndexable!A && isCallable!F) 268 { 269 return range.indexOf!F != -1; 270 } 271 272 /** 273 * Checks if all elements in `range` fulfill a given predicate `F`. 274 * 275 * Params: 276 * F = The function predicate to use. 277 * range = The range of values to check if fulfill `F`. 278 * 279 * Returns: 280 * True if all elements in `range` fulfill `F`. 281 */ 282 size_t all(alias F, A)(A range) 283 if (isForward!A) 284 { 285 return range.filter!F.length == range.loadLength; 286 } 287 288 /** 289 * Checks if any elements in `range` fulfill a given predicate `F`. 290 * 291 * Params: 292 * F = The function predicate to use. 293 * range = The range of values to check if fulfill `F`. 294 * 295 * Returns: 296 * True if any elements in `range` fulfill `F`. 297 */ 298 size_t any(alias F, A)(A range) 299 if (isForward!A) 300 { 301 return range.indexOf!F != -1; 302 } 303 304 /** 305 * Checks if `range` starts with a given element. 306 * 307 * Params: 308 * range = The range of values to check if starts with `elem`. 309 * elem = The element to check if `range` starts with. 310 * 311 * Returns: 312 * True if `range` starts with `elem`. 313 */ 314 bool startsWith(A, B)(A range, B elem) 315 if (isIndexable!A && isElement!(A, B)) 316 { 317 return range.length >= 1 && range[0..1].contains(elem); 318 } 319 320 /// ditto 321 bool startsWith(A, B)(A range, B subrange) 322 if (isIndexable!A && !isElement!(A, B) && isIndexable!B) 323 { 324 return range.length >= subrange.length && range[0..subrange.length].contains(subrange); 325 } 326 327 /** 328 * Checks if `range` ends with a given element. 329 * 330 * Params: 331 * range = The range of values to check if ends with `elem`. 332 * elem = The element to check if `range` ends with. 333 * 334 * Returns: 335 * True if `range` ends with `elem`. 336 */ 337 bool endsWith(A, B)(A range, B elem) 338 if (isIndexable!A && isElement!(A, B)) 339 { 340 return range.length >= 1 && range[$-1..$].contains(elem); 341 } 342 343 /// ditto 344 bool endsWith(A, B)(A range, B subrange) 345 if (isIndexable!A && !isElement!(A, B) && isIndexable!B) 346 { 347 return range.length >= subrange.length && range[$-subrange.length..$].contains(subrange); 348 } 349 350 /** 351 * Counts all occurrences of `elem` in `range`. 352 * 353 * Params: 354 * range = The range of values to count in. 355 * elem = The element to count for in `range`. 356 * 357 * Returns: 358 * Number of occurrences of `elem` in range. 359 */ 360 size_t count(A, B)(A range, B elem) 361 if (isIndexable!A && isElement!(A, B)) 362 { 363 size_t count; 364 foreach (u; range) 365 { 366 if (u == elem) 367 count++; 368 } 369 return count; 370 } 371 372 /// ditto 373 size_t count(A, B)(A range, B subrange) 374 if (isIndexable!A && !isElement!(A, B) && isIndexable!B) 375 { 376 size_t count; 377 range.plane!((ref i) { 378 count++; 379 })(subrange); 380 return count; 381 }