From 770764da916b9e3783f2a95b2da62cb930b6702b Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 8 Apr 2022 17:13:15 +0200 Subject: Added cvec_X_lower_bound() function for sorted array search. --- README.md | 2 +- docs/cvec_api.md | 6 ++++-- include/stc/alt/csmap.h | 2 +- include/stc/cvec.h | 16 ++++++++++++---- 4 files changed, 18 insertions(+), 8 deletions(-) diff --git a/README.md b/README.md index 552f4e69..c31eb59d 100644 --- a/README.md +++ b/README.md @@ -340,7 +340,7 @@ c_autovar (cstr s = cstr_new("a string literal"), cstr_drop(&s)) // c_autovar i cvec_str_emplace_back(&vec, "Yay, literal"); // internally constructs cstr from const char* cvec_str_emplace_back(&vec, cstr_clone(s)); // <-- COMPILE ERROR: expects const char* - cvec_str_emplace_back(&vec, s.str); // Ok: const char* input type. + cvec_str_emplace_back(&vec, cstr_str(&s)); // Ok: const char* input type. } ``` This is made possible because the type configuration may be given an optional diff --git a/docs/cvec_api.md b/docs/cvec_api.md index ef145b94..7aef79d9 100644 --- a/docs/cvec_api.md +++ b/docs/cvec_api.md @@ -50,8 +50,10 @@ const cvec_X_value* cvec_X_get(const cvec_X* self, i_valraw raw); cvec_X_value* cvec_X_get_mut(cvec_X* self, i_valraw raw); // get mutable value cvec_X_iter cvec_X_find(const cvec_X* self, i_valraw raw); cvec_X_iter cvec_X_find_in(cvec_X_iter i1, cvec_X_iter i2, i_valraw raw); -cvec_X_iter cvec_X_bsearch(const cvec_X* self, i_valraw raw); -cvec_X_iter cvec_X_bsearch_in(cvec_X_iter i1, cvec_X_iter i2, i_valraw raw); + // On sorted vectors: +cvec_X_iter cvec_X_bsearch(const cvec_X* self, i_valraw raw); // at elem == raw, else end +cvec_X_iter cvec_X_lower_bound(const cvec_X* self, i_valraw raw); // at first elem >= raw, else end +cvec_X_iter cvec_X_bsearch_in(cvec_X_iter i1, cvec_X_iter i2, i_valraw raw, cvec_X_iter* lower_bound = NULL); cvec_X_value* cvec_X_front(const cvec_X* self); cvec_X_value* cvec_X_back(const cvec_X* self); diff --git a/include/stc/alt/csmap.h b/include/stc/alt/csmap.h index 840e684a..0b989e22 100644 --- a/include/stc/alt/csmap.h +++ b/include/stc/alt/csmap.h @@ -160,7 +160,7 @@ int main(void) { res.ref->second = i_valfrom(rmapped); return res; \ } \ \ - STC_INLINE _cx_mapped* \ + STC_INLINE const _cx_mapped* \ _cx_memb(_at)(const _cx_self* self, i_keyraw rkey) { \ _cx_iter it; \ return &_cx_memb(_find_it)(self, rkey, &it)->second; \ diff --git a/include/stc/cvec.h b/include/stc/cvec.h index 81e5f7de..2b210519 100644 --- a/include/stc/cvec.h +++ b/include/stc/cvec.h @@ -89,7 +89,7 @@ STC_API _cx_iter _cx_memb(_insert_range_p)(_cx_self* self, _cx_value* pos #if !c_option(c_no_cmp) STC_API int _cx_memb(_value_cmp)(const _cx_value* x, const _cx_value* y); STC_API _cx_iter _cx_memb(_find_in)(_cx_iter it1, _cx_iter it2, i_valraw raw); -STC_API _cx_iter _cx_memb(_bsearch_in)(_cx_iter it1, _cx_iter it2, i_valraw raw); +STC_API _cx_iter _cx_memb(_bsearch_in)(_cx_iter it1, _cx_iter it2, i_valraw raw, _cx_iter* lower_bound); #endif #if !defined _i_no_clone @@ -219,7 +219,14 @@ _cx_memb(_get_mut)(const _cx_self* self, i_valraw raw) STC_INLINE _cx_iter _cx_memb(_bsearch)(const _cx_self* self, i_valraw raw) - { return _cx_memb(_bsearch_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), raw); } + { return _cx_memb(_bsearch_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), raw, NULL); } + +STC_INLINE _cx_iter +_cx_memb(_lower_bound)(const _cx_self* self, i_valraw raw) { + _cx_iter lower; + _cx_memb(_bsearch_in)(_cx_memb(_begin)(self), _cx_memb(_end)(self), raw, &lower); + return lower; +} STC_INLINE void _cx_memb(_sort_range)(_cx_iter i1, _cx_iter i2, @@ -374,15 +381,16 @@ _cx_memb(_find_in)(_cx_iter i1, _cx_iter i2, i_valraw raw) { } STC_DEF _cx_iter -_cx_memb(_bsearch_in)(_cx_iter i1, _cx_iter i2, i_valraw raw) { +_cx_memb(_bsearch_in)(_cx_iter i1, _cx_iter i2, i_valraw raw, _cx_iter* lower_bound) { _cx_iter mid, last = i2; while (i1.ref != i2.ref) { - mid.ref = i1.ref + ((i2.ref - i1.ref)>>1); + mid.ref = i1.ref + ((i2.ref - i1.ref) >> 1); int c; i_valraw m = i_valto(mid.ref); if ((c = i_cmp(&raw, &m)) == 0) return mid; else if (c < 0) i2.ref = mid.ref; else i1.ref = mid.ref + 1; } + if (lower_bound) *lower_bound = i1; return last; } -- cgit v1.2.3