1 | /**************************************************************************/ |
2 | /* search_array.h */ |
3 | /**************************************************************************/ |
4 | /* This file is part of: */ |
5 | /* GODOT ENGINE */ |
6 | /* https://godotengine.org */ |
7 | /**************************************************************************/ |
8 | /* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */ |
9 | /* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */ |
10 | /* */ |
11 | /* Permission is hereby granted, free of charge, to any person obtaining */ |
12 | /* a copy of this software and associated documentation files (the */ |
13 | /* "Software"), to deal in the Software without restriction, including */ |
14 | /* without limitation the rights to use, copy, modify, merge, publish, */ |
15 | /* distribute, sublicense, and/or sell copies of the Software, and to */ |
16 | /* permit persons to whom the Software is furnished to do so, subject to */ |
17 | /* the following conditions: */ |
18 | /* */ |
19 | /* The above copyright notice and this permission notice shall be */ |
20 | /* included in all copies or substantial portions of the Software. */ |
21 | /* */ |
22 | /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ |
23 | /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ |
24 | /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */ |
25 | /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ |
26 | /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ |
27 | /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ |
28 | /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ |
29 | /**************************************************************************/ |
30 | |
31 | #ifndef SEARCH_ARRAY_H |
32 | #define SEARCH_ARRAY_H |
33 | |
34 | #include <core/templates/sort_array.h> |
35 | |
36 | template <class T, class Comparator = _DefaultComparator<T>> |
37 | class SearchArray { |
38 | public: |
39 | Comparator compare; |
40 | |
41 | inline int bisect(const T *p_array, int p_len, const T &p_value, bool p_before) const { |
42 | int lo = 0; |
43 | int hi = p_len; |
44 | if (p_before) { |
45 | while (lo < hi) { |
46 | const int mid = (lo + hi) / 2; |
47 | if (compare(p_array[mid], p_value)) { |
48 | lo = mid + 1; |
49 | } else { |
50 | hi = mid; |
51 | } |
52 | } |
53 | } else { |
54 | while (lo < hi) { |
55 | const int mid = (lo + hi) / 2; |
56 | if (compare(p_value, p_array[mid])) { |
57 | hi = mid; |
58 | } else { |
59 | lo = mid + 1; |
60 | } |
61 | } |
62 | } |
63 | return lo; |
64 | } |
65 | }; |
66 | |
67 | #endif // SEARCH_ARRAY_H |
68 | |