algorithms.h

/*
 * AUI Framework - Declarative UI toolkit for modern C++20
 * Copyright (C) 2020-2025 Alex2772 and Contributors
 *
 * SPDX-License-Identifier: MPL-2.0
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */
 
//
// Created by Alex2772 on 11/28/2021.
//
 
#pragma once
 
#include <cstdint>
#include <cstddef>
#include <cmath>
#include "iterators.h"
 
namespace aui {

   enum class BinarySearchResult {
       MATCH,

        LEFT,

       RIGHT
   };
 

   template<typename Predicate, typename Iterator>
   struct BinarySearchNearestToZero {
   public:
       BinarySearchNearestToZero(Predicate predicate, aui::range<Iterator> range): mPredicate(std::move(predicate)), mRange(range) {}
 
       BinarySearchResult operator()(Iterator c) {
           auto next = std::next(c);
           if (next == mRange.end()) {
               return BinarySearchResult::MATCH;
           }
 
           auto v1 = mPredicate(c);
           auto v2 = mPredicate(next);
 
           if (v1 <= 0 && v2 > 0) {
               if (v2 + v1 < 0) {
                   return BinarySearchResult::RIGHT;
               }
               return BinarySearchResult::MATCH;
           }
           if (v1 > 0) {
               if (mRange.begin() == c) {
                   return BinarySearchResult::MATCH;
               }
               if (auto v0 = mPredicate(std::prev(c)); v1 + v0 < 0) {
                   return BinarySearchResult::MATCH;
               }
               return BinarySearchResult::LEFT;
           }
 
           return BinarySearchResult::RIGHT;
       }
   private:
       Predicate mPredicate;
       aui::range<Iterator> mRange;
   };
 

   template<typename Iterator, typename Predicate>
   Iterator binary_search(Iterator begin, Iterator end, Predicate predicate) {
       static_assert(std::is_same_v<BinarySearchResult, decltype(predicate(std::declval<Iterator>()))>, "predicate should return BinarySearchResult");
 
       size_t rangeEnd = end - begin;
       size_t rangeBegin = 0;
 
 
       for (size_t i; rangeBegin < rangeEnd; ) {
           i = (rangeEnd - rangeBegin - 1) / 2 + rangeBegin;
           auto it = begin + i;
           switch (predicate(it)) {
               case BinarySearchResult::MATCH:
                   return it;
 
               case BinarySearchResult::RIGHT:
                   rangeBegin = i + 1;
                   break;
               case BinarySearchResult::LEFT:
                   rangeEnd = i;
                   break;
           }
 
       }
       return end;
   }
}

© 2025 AUI Framework Contributors. Documentation contributions included herein are the copyrights of their respective owners. The documentation provided herein is licensed under the terms of the GNU Free Documentation License version 1.3 as published by the Free Software Foundation. All trademarks are property of their respective owners.