types.hpp

/* SPDX-License-Identifier: MIT */
/* Copyright © 2020 Max Bachmann */
 
#pragma once
 
#include <algorithm>
#include <rapidfuzz/details/config.hpp>
#include <stddef.h>
#include <stdexcept>
#include <vector>
 
namespace rapidfuzz {
 
struct StringAffix {
    size_t prefix_len;
    size_t suffix_len;
};
 
struct LevenshteinWeightTable {
    size_t insert_cost;
    size_t delete_cost;
    size_t replace_cost;
};
 
enum class EditType {
    None = 0,    
    Replace = 1, 
    Insert = 2,  
    Delete = 3   
};
 
struct EditOp {
    EditType type;   
    size_t src_pos;  
    size_t dest_pos; 
    EditOp() : type(EditType::None), src_pos(0), dest_pos(0)
    {}
 
    EditOp(EditType type_, size_t src_pos_, size_t dest_pos_)
        : type(type_), src_pos(src_pos_), dest_pos(dest_pos_)
    {}
};
 
inline bool operator==(EditOp a, EditOp b)
{
    return (a.type == b.type) && (a.src_pos == b.src_pos) && (a.dest_pos == b.dest_pos);
}
 
inline bool operator!=(EditOp a, EditOp b)
{
    return !(a == b);
}
 
struct Opcode {
    EditType type;     
    size_t src_begin;  
    size_t src_end;    
    size_t dest_begin; 
    size_t dest_end;   
    Opcode() : type(EditType::None), src_begin(0), src_end(0), dest_begin(0), dest_end(0)
    {}
 
    Opcode(EditType type_, size_t src_begin_, size_t src_end_, size_t dest_begin_, size_t dest_end_)
        : type(type_), src_begin(src_begin_), src_end(src_end_), dest_begin(dest_begin_), dest_end(dest_end_)
    {}
};
 
inline bool operator==(Opcode a, Opcode b)
{
    return (a.type == b.type) && (a.src_begin == b.src_begin) && (a.src_end == b.src_end) &&
           (a.dest_begin == b.dest_begin) && (a.dest_end == b.dest_end);
}
 
inline bool operator!=(Opcode a, Opcode b)
{
    return !(a == b);
}
 
namespace detail {
template <typename Vec>
auto vector_slice(const Vec& vec, int start, int stop, int step) -> Vec
{
    Vec new_vec;
 
    if (step == 0) throw std::invalid_argument("slice step cannot be zero");
    if (step < 0) throw std::invalid_argument("step sizes below 0 lead to an invalid order of editops");
 
    if (start < 0)
        start = std::max<int>(start + static_cast<int>(vec.size()), 0);
    else if (start > static_cast<int>(vec.size()))
        start = static_cast<int>(vec.size());
 
    if (stop < 0)
        stop = std::max<int>(stop + static_cast<int>(vec.size()), 0);
    else if (stop > static_cast<int>(vec.size()))
        stop = static_cast<int>(vec.size());
 
    if (start >= stop) return new_vec;
 
    int count = (stop - 1 - start) / step + 1;
    new_vec.reserve(static_cast<size_t>(count));
 
    for (int i = start; i < stop; i += step)
        new_vec.push_back(vec[static_cast<size_t>(i)]);
 
    return new_vec;
}
 
template <typename Vec>
void vector_remove_slice(Vec& vec, int start, int stop, int step)
{
    if (step == 0) throw std::invalid_argument("slice step cannot be zero");
    if (step < 0) throw std::invalid_argument("step sizes below 0 lead to an invalid order of editops");
 
    if (start < 0)
        start = std::max<int>(start + static_cast<int>(vec.size()), 0);
    else if (start > static_cast<int>(vec.size()))
        start = static_cast<int>(vec.size());
 
    if (stop < 0)
        stop = std::max<int>(stop + static_cast<int>(vec.size()), 0);
    else if (stop > static_cast<int>(vec.size()))
        stop = static_cast<int>(vec.size());
 
    if (start >= stop) return;
 
    auto iter = vec.begin() + start;
    for (int i = start; i < static_cast<int>(vec.size()); i++)
        if (i >= stop || ((i - start) % step != 0)) *(iter++) = vec[static_cast<size_t>(i)];
 
    vec.resize(static_cast<size_t>(std::distance(vec.begin(), iter)));
    vec.shrink_to_fit();
}
 
} // namespace detail
 
class Opcodes;
 
class Editops : private std::vector<EditOp> {
public:
    using std::vector<EditOp>::size_type;
 
    Editops() noexcept : src_len(0), dest_len(0)
    {}
 
    Editops(size_type count, const EditOp& value) : std::vector<EditOp>(count, value), src_len(0), dest_len(0)
    {}
 
    explicit Editops(size_type count) : std::vector<EditOp>(count), src_len(0), dest_len(0)
    {}
 
    Editops(const Editops& other)
        : std::vector<EditOp>(other), src_len(other.src_len), dest_len(other.dest_len)
    {}
 
    Editops(const Opcodes& other);
 
    Editops(Editops&& other) noexcept
    {
        swap(other);
    }
 
    Editops& operator=(Editops other) noexcept
    {
        swap(other);
        return *this;
    }
 
    /* Element access */
    using std::vector<EditOp>::at;
    using std::vector<EditOp>::operator[];
    using std::vector<EditOp>::front;
    using std::vector<EditOp>::back;
    using std::vector<EditOp>::data;
 
    /* Iterators */
    using std::vector<EditOp>::begin;
    using std::vector<EditOp>::cbegin;
    using std::vector<EditOp>::end;
    using std::vector<EditOp>::cend;
    using std::vector<EditOp>::rbegin;
    using std::vector<EditOp>::crbegin;
    using std::vector<EditOp>::rend;
    using std::vector<EditOp>::crend;
 
    /* Capacity */
    using std::vector<EditOp>::empty;
    using std::vector<EditOp>::size;
    using std::vector<EditOp>::max_size;
    using std::vector<EditOp>::reserve;
    using std::vector<EditOp>::capacity;
    using std::vector<EditOp>::shrink_to_fit;
 
    /* Modifiers */
    using std::vector<EditOp>::clear;
    using std::vector<EditOp>::insert;
    using std::vector<EditOp>::emplace;
    using std::vector<EditOp>::erase;
    using std::vector<EditOp>::push_back;
    using std::vector<EditOp>::emplace_back;
    using std::vector<EditOp>::pop_back;
    using std::vector<EditOp>::resize;
 
    void swap(Editops& rhs) noexcept
    {
        std::swap(src_len, rhs.src_len);
        std::swap(dest_len, rhs.dest_len);
        std::vector<EditOp>::swap(rhs);
    }
 
    Editops slice(int start, int stop, int step = 1) const
    {
        Editops ed_slice = detail::vector_slice(*this, start, stop, step);
        ed_slice.src_len = src_len;
        ed_slice.dest_len = dest_len;
        return ed_slice;
    }
 
    void remove_slice(int start, int stop, int step = 1)
    {
        detail::vector_remove_slice(*this, start, stop, step);
    }
 
    Editops reverse() const
    {
        Editops reversed = *this;
        std::reverse(reversed.begin(), reversed.end());
        return reversed;
    }
 
    size_t get_src_len() const noexcept
    {
        return src_len;
    }
    void set_src_len(size_t len) noexcept
    {
        src_len = len;
    }
    size_t get_dest_len() const noexcept
    {
        return dest_len;
    }
    void set_dest_len(size_t len) noexcept
    {
        dest_len = len;
    }
 
    Editops inverse() const
    {
        Editops inv_ops = *this;
        std::swap(inv_ops.src_len, inv_ops.dest_len);
        for (auto& op : inv_ops) {
            std::swap(op.src_pos, op.dest_pos);
            if (op.type == EditType::Delete)
                op.type = EditType::Insert;
            else if (op.type == EditType::Insert)
                op.type = EditType::Delete;
        }
        return inv_ops;
    }
 
    Editops remove_subsequence(const Editops& subsequence) const
    {
        Editops result;
        result.set_src_len(src_len);
        result.set_dest_len(dest_len);
 
        if (subsequence.size() > size()) throw std::invalid_argument("subsequence is not a subsequence");
 
        result.resize(size() - subsequence.size());
 
        /* offset to correct removed edit operations */
        int offset = 0;
        auto op_iter = begin();
        auto op_end = end();
        size_t result_pos = 0;
        for (const auto& sop : subsequence) {
            for (; op_iter != op_end && sop != *op_iter; op_iter++) {
                if (result_pos >= result.size()) throw std::invalid_argument("subsequence is not a subsequence");
 
                result[result_pos] = *op_iter;
                result[result_pos].src_pos =
                    static_cast<size_t>(static_cast<ptrdiff_t>(result[result_pos].src_pos) + offset);
                result_pos++;
            }
            /* element of subsequence not part of the sequence */
            if (op_iter == op_end) throw std::invalid_argument("subsequence is not a subsequence");
 
            if (sop.type == EditType::Insert)
                offset++;
            else if (sop.type == EditType::Delete)
                offset--;
            op_iter++;
        }
 
        /* add remaining elements */
        for (; op_iter != op_end; op_iter++) {
            result[result_pos] = *op_iter;
            result[result_pos].src_pos =
                static_cast<size_t>(static_cast<ptrdiff_t>(result[result_pos].src_pos) + offset);
            result_pos++;
        }
 
        return result;
    }
 
private:
    size_t src_len;
    size_t dest_len;
};
 
inline bool operator==(const Editops& lhs, const Editops& rhs)
{
    if (lhs.get_src_len() != rhs.get_src_len() || lhs.get_dest_len() != rhs.get_dest_len()) return false;
 
    if (lhs.size() != rhs.size()) return false;
 
    return std::equal(lhs.begin(), lhs.end(), rhs.begin());
}
 
inline bool operator!=(const Editops& lhs, const Editops& rhs)
{
    return !(lhs == rhs);
}
 
inline void swap(Editops& lhs, Editops& rhs) noexcept(noexcept(lhs.swap(rhs)))
{
    lhs.swap(rhs);
}
 
class Opcodes : private std::vector<Opcode> {
public:
    using std::vector<Opcode>::size_type;
 
    Opcodes() noexcept : src_len(0), dest_len(0)
    {}
 
    Opcodes(size_type count, const Opcode& value) : std::vector<Opcode>(count, value), src_len(0), dest_len(0)
    {}
 
    explicit Opcodes(size_type count) : std::vector<Opcode>(count), src_len(0), dest_len(0)
    {}
 
    Opcodes(const Opcodes& other)
        : std::vector<Opcode>(other), src_len(other.src_len), dest_len(other.dest_len)
    {}
 
    Opcodes(const Editops& other);
 
    Opcodes(Opcodes&& other) noexcept
    {
        swap(other);
    }
 
    Opcodes& operator=(Opcodes other) noexcept
    {
        swap(other);
        return *this;
    }
 
    /* Element access */
    using std::vector<Opcode>::at;
    using std::vector<Opcode>::operator[];
    using std::vector<Opcode>::front;
    using std::vector<Opcode>::back;
    using std::vector<Opcode>::data;
 
    /* Iterators */
    using std::vector<Opcode>::begin;
    using std::vector<Opcode>::cbegin;
    using std::vector<Opcode>::end;
    using std::vector<Opcode>::cend;
    using std::vector<Opcode>::rbegin;
    using std::vector<Opcode>::crbegin;
    using std::vector<Opcode>::rend;
    using std::vector<Opcode>::crend;
 
    /* Capacity */
    using std::vector<Opcode>::empty;
    using std::vector<Opcode>::size;
    using std::vector<Opcode>::max_size;
    using std::vector<Opcode>::reserve;
    using std::vector<Opcode>::capacity;
    using std::vector<Opcode>::shrink_to_fit;
 
    /* Modifiers */
    using std::vector<Opcode>::clear;
    using std::vector<Opcode>::insert;
    using std::vector<Opcode>::emplace;
    using std::vector<Opcode>::erase;
    using std::vector<Opcode>::push_back;
    using std::vector<Opcode>::emplace_back;
    using std::vector<Opcode>::pop_back;
    using std::vector<Opcode>::resize;
 
    void swap(Opcodes& rhs) noexcept
    {
        std::swap(src_len, rhs.src_len);
        std::swap(dest_len, rhs.dest_len);
        std::vector<Opcode>::swap(rhs);
    }
 
    Opcodes slice(int start, int stop, int step = 1) const
    {
        Opcodes ed_slice = detail::vector_slice(*this, start, stop, step);
        ed_slice.src_len = src_len;
        ed_slice.dest_len = dest_len;
        return ed_slice;
    }
 
    Opcodes reverse() const
    {
        Opcodes reversed = *this;
        std::reverse(reversed.begin(), reversed.end());
        return reversed;
    }
 
    size_t get_src_len() const noexcept
    {
        return src_len;
    }
    void set_src_len(size_t len) noexcept
    {
        src_len = len;
    }
    size_t get_dest_len() const noexcept
    {
        return dest_len;
    }
    void set_dest_len(size_t len) noexcept
    {
        dest_len = len;
    }
 
    Opcodes inverse() const
    {
        Opcodes inv_ops = *this;
        std::swap(inv_ops.src_len, inv_ops.dest_len);
        for (auto& op : inv_ops) {
            std::swap(op.src_begin, op.dest_begin);
            std::swap(op.src_end, op.dest_end);
            if (op.type == EditType::Delete)
                op.type = EditType::Insert;
            else if (op.type == EditType::Insert)
                op.type = EditType::Delete;
        }
        return inv_ops;
    }
 
private:
    size_t src_len;
    size_t dest_len;
};
 
inline bool operator==(const Opcodes& lhs, const Opcodes& rhs)
{
    if (lhs.get_src_len() != rhs.get_src_len() || lhs.get_dest_len() != rhs.get_dest_len()) return false;
 
    if (lhs.size() != rhs.size()) return false;
 
    return std::equal(lhs.begin(), lhs.end(), rhs.begin());
}
 
inline bool operator!=(const Opcodes& lhs, const Opcodes& rhs)
{
    return !(lhs == rhs);
}
 
inline void swap(Opcodes& lhs, Opcodes& rhs) noexcept(noexcept(lhs.swap(rhs)))
{
    lhs.swap(rhs);
}
 
inline Editops::Editops(const Opcodes& other)
{
    src_len = other.get_src_len();
    dest_len = other.get_dest_len();
    for (const auto& op : other) {
        switch (op.type) {
        case EditType::None: break;
 
        case EditType::Replace:
            for (size_t j = 0; j < op.src_end - op.src_begin; j++)
                push_back({EditType::Replace, op.src_begin + j, op.dest_begin + j});
            break;
 
        case EditType::Insert:
            for (size_t j = 0; j < op.dest_end - op.dest_begin; j++)
                push_back({EditType::Insert, op.src_begin, op.dest_begin + j});
            break;
 
        case EditType::Delete:
            for (size_t j = 0; j < op.src_end - op.src_begin; j++)
                push_back({EditType::Delete, op.src_begin + j, op.dest_begin});
            break;
        }
    }
}
 
inline Opcodes::Opcodes(const Editops& other)
{
    src_len = other.get_src_len();
    dest_len = other.get_dest_len();
    size_t src_pos = 0;
    size_t dest_pos = 0;
    for (size_t i = 0; i < other.size();) {
        if (src_pos < other[i].src_pos || dest_pos < other[i].dest_pos) {
            push_back({EditType::None, src_pos, other[i].src_pos, dest_pos, other[i].dest_pos});
            src_pos = other[i].src_pos;
            dest_pos = other[i].dest_pos;
        }
 
        size_t src_begin = src_pos;
        size_t dest_begin = dest_pos;
        EditType type = other[i].type;
        do {
            switch (type) {
            case EditType::None: break;
 
            case EditType::Replace:
                src_pos++;
                dest_pos++;
                break;
 
            case EditType::Insert: dest_pos++; break;
 
            case EditType::Delete: src_pos++; break;
            }
            i++;
        } while (i < other.size() && other[i].type == type && src_pos == other[i].src_pos &&
                 dest_pos == other[i].dest_pos);
 
        push_back({type, src_begin, src_pos, dest_begin, dest_pos});
    }
 
    if (src_pos < other.get_src_len() || dest_pos < other.get_dest_len()) {
        push_back({EditType::None, src_pos, other.get_src_len(), dest_pos, other.get_dest_len()});
    }
}
 
template <typename T>
struct ScoreAlignment {
    T score;           
    size_t src_start;  
    size_t src_end;    
    size_t dest_start; 
    size_t dest_end;   
    ScoreAlignment() : score(T()), src_start(0), src_end(0), dest_start(0), dest_end(0)
    {}
 
    ScoreAlignment(T score_, size_t src_start_, size_t src_end_, size_t dest_start_, size_t dest_end_)
        : score(score_),
          src_start(src_start_),
          src_end(src_end_),
          dest_start(dest_start_),
          dest_end(dest_end_)
    {}
};
 
template <typename T>
inline bool operator==(const ScoreAlignment<T>& a, const ScoreAlignment<T>& b)
{
    return (a.score == b.score) && (a.src_start == b.src_start) && (a.src_end == b.src_end) &&
           (a.dest_start == b.dest_start) && (a.dest_end == b.dest_end);
}
 
} // namespace rapidfuzz