Added cvec_X_lower_bound() function for sorted array search.

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;

 }