18dffb485Schristos /* C++ implementation of a binary search. 28dffb485Schristos 3*5ba1f45fSchristos Copyright (C) 2019-2024 Free Software Foundation, Inc. 48dffb485Schristos 58dffb485Schristos This file is part of GDB. 68dffb485Schristos 78dffb485Schristos This program is free software; you can redistribute it and/or modify 88dffb485Schristos it under the terms of the GNU General Public License as published by 98dffb485Schristos the Free Software Foundation; either version 3 of the License, or 108dffb485Schristos (at your option) any later version. 118dffb485Schristos 128dffb485Schristos This program is distributed in the hope that it will be useful, 138dffb485Schristos but WITHOUT ANY WARRANTY; without even the implied warranty of 148dffb485Schristos MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 158dffb485Schristos GNU General Public License for more details. 168dffb485Schristos 178dffb485Schristos You should have received a copy of the GNU General Public License 188dffb485Schristos along with this program. If not, see <http://www.gnu.org/licenses/>. */ 198dffb485Schristos 208dffb485Schristos 218dffb485Schristos #ifndef GDBSUPPORT_GDB_BINARY_SEARCH_H 228dffb485Schristos #define GDBSUPPORT_GDB_BINARY_SEARCH_H 238dffb485Schristos 248dffb485Schristos #include <algorithm> 258dffb485Schristos 268dffb485Schristos namespace gdb { 278dffb485Schristos 288dffb485Schristos /* Implements a binary search using C++ iterators. 298dffb485Schristos This differs from std::binary_search in that it returns an iterator for 308dffb485Schristos the found element and in that the type of EL can be different from the 318dffb485Schristos type of the elements in the container. 328dffb485Schristos 338dffb485Schristos COMP is a C-style comparison function with signature: 348dffb485Schristos int comp(const value_type& a, const T& b); 358dffb485Schristos It should return -1, 0 or 1 if a is less than, equal to, or greater than 368dffb485Schristos b, respectively. 378dffb485Schristos [first, last) must be sorted. 388dffb485Schristos 398dffb485Schristos The return value is an iterator pointing to the found element, or LAST if 408dffb485Schristos no element was found. */ 418dffb485Schristos template<typename It, typename T, typename Comp> 428dffb485Schristos It binary_search (It first, It last, T el, Comp comp) 438dffb485Schristos { 448dffb485Schristos auto lt = [&] (const typename std::iterator_traits<It>::value_type &a, 458dffb485Schristos const T &b) 468dffb485Schristos { return comp (a, b) < 0; }; 478dffb485Schristos 488dffb485Schristos auto lb = std::lower_bound (first, last, el, lt); 498dffb485Schristos if (lb != last) 508dffb485Schristos { 518dffb485Schristos if (comp (*lb, el) == 0) 528dffb485Schristos return lb; 538dffb485Schristos } 548dffb485Schristos return last; 558dffb485Schristos } 568dffb485Schristos 578dffb485Schristos } /* namespace gdb */ 588dffb485Schristos 598dffb485Schristos #endif /* GDBSUPPORT_GDB_BINARY_SEARCH_H */ 60