Line data    Source code

       1              : /*
       2              :  * SPDX-License-Identifier: GPL-3.0-only
       3              :  * MuseScore-CLA-applies
       4              :  *
       5              :  * MuseScore
       6              :  * Music Composition & Notation
       7              :  *
       8              :  * Copyright (C) 2026 MuseScore Limited and others
       9              :  *
      10              :  * This program is free software: you can redistribute it and/or modify
      11              :  * it under the terms of the GNU General Public License version 3 as
      12              :  * published by the Free Software Foundation.
      13              :  *
      14              :  * This program is distributed in the hope that it will be useful,
      15              :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      16              :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      17              :  * GNU General Public License for more details.
      18              :  *
      19              :  * You should have received a copy of the GNU General Public License
      20              :  * along with this program.  If not, see <https://www.gnu.org/licenses/>.
      21              :  */
      22              : 
      23              : #pragma once
      24              : 
      25              : #include <cstddef>
      26              : #include <iterator>
      27              : #include <optional>
      28              : #include <string_view>
      29              : #include <vector>
      30              : 
      31              : namespace muse {
      32              : struct FuzzyMatch {
      33              :     std::size_t beginPos = 0;
      34              :     std::size_t endPos = 0;
      35              :     std::size_t editDistance = 0;
      36              : };
      37              : 
      38              : bool operator==(const FuzzyMatch&, const FuzzyMatch&);
      39              : bool operator!=(const FuzzyMatch&, const FuzzyMatch&);
      40              : 
      41              : class FuzzyMatcher
      42              : {
      43              : public:
      44              :     using value_type = FuzzyMatch;
      45              : 
      46              :     static constexpr auto UNLIMITED_DISTANCE = static_cast<std::size_t>(-1);
      47              : 
      48            0 :     FuzzyMatcher() = default;
      49              : 
      50              :     FuzzyMatcher& operator()(std::u32string_view text, std::u32string_view pattern, std::size_t maxDistance = UNLIMITED_DISTANCE);
      51              :     FuzzyMatcher& match(std::u32string_view text, std::u32string_view pattern, std::size_t maxDistance = UNLIMITED_DISTANCE);
      52              : 
      53              :     bool empty() const;
      54              :     std::optional<FuzzyMatch> findMatch(std::size_t textBeginPos) const;
      55              : 
      56              :     void clear();
      57              : 
      58              :     class Iterator
      59              :     {
      60              :     public:
      61              :         using difference_type = std::ptrdiff_t;
      62              :         using value_type = FuzzyMatcher::value_type;
      63              :         using pointer = const value_type*;
      64              :         using reference = const value_type&;
      65              :         using iterator_category = std::input_iterator_tag;
      66              : 
      67           42 :         Iterator() = default;
      68              :         explicit Iterator(const FuzzyMatcher&);
      69              : 
      70              :         reference operator*() const;
      71              :         pointer operator->() const;
      72              : 
      73              :         Iterator& operator++();
      74              :         Iterator operator++(int);
      75              : 
      76              :         bool operator==(const Iterator&) const;
      77              :         bool operator!=(const Iterator&) const;
      78              : 
      79              :     private:
      80              :         void next(std::size_t textBeginPos);
      81              : 
      82              :         const FuzzyMatcher* m_matcher = nullptr;
      83              :         std::optional<FuzzyMatch> m_match;
      84              :     };
      85              : 
      86              :     using const_iterator = Iterator;
      87              : 
      88              :     const_iterator begin() const;
      89              :     const_iterator end() const;
      90              : 
      91              : private:
      92              :     struct SuffixMatch {
      93              :         std::size_t endPos = 0;
      94              :         std::size_t editDistance = 0;
      95              : 
      96         1770 :         friend bool operator<(const SuffixMatch& left, const SuffixMatch& right)
      97              :         {
      98         1770 :             return left.editDistance < right.editDistance;
      99              :         }
     100              :     };
     101              : 
     102              :     std::size_t index(std::size_t patternSuffixSize, std::size_t textSuffixSize) const;
     103              : 
     104              :     std::size_t m_textSize = 0;
     105              :     std::size_t m_patternSize = 0;
     106              :     std::size_t m_maxDistance = 0;
     107              :     std::vector<SuffixMatch> m_suffixTable;
     108              : };
     109              : }