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 }