From 770764da916b9e3783f2a95b2da62cb930b6702b Mon Sep 17 00:00:00 2001
From: Tyge Løvset <tylo@norceresearch.no>
Date: Fri, 8 Apr 2022 17:13:15 +0200
Subject: Added cvec_X_lower_bound() function for sorted array search.

---
 include/stc/alt/csmap.h |  2 +-
 include/stc/cvec.h      | 16 ++++++++++++----
 2 files changed, 13 insertions(+), 5 deletions(-)

(limited to 'include')

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