//===-- llvm/ADT/edit_distance.h - Array edit distance function --- C++ -*-===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// /// /// \file /// This file defines a Levenshtein distance function that works for any two /// sequences, with each element of each sequence being analogous to a character /// in a string. /// //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_EDIT_DISTANCE_H #define LLVM_ADT_EDIT_DISTANCE_H #include "llvm/ADT/ArrayRef.h" #include <algorithm> namespace llvm { /// Determine the edit distance between two sequences. /// /// \param FromArray the first sequence to compare. /// /// \param ToArray the second sequence to compare. /// /// \param Map A Functor to apply to each item of the sequences before /// comparison. /// /// \param AllowReplacements whether to allow element replacements (change one /// element into another) as a single operation, rather than as two operations /// (an insertion and a removal). /// /// \param MaxEditDistance If non-zero, the maximum edit distance that this /// routine is allowed to compute. If the edit distance will exceed that /// maximum, returns \c MaxEditDistance+1. /// /// \returns the minimum number of element insertions, removals, or (if /// \p AllowReplacements is \c true) replacements needed to transform one of /// the given sequences into the other. If zero, the sequences are identical. template <typename T, typename Functor> unsigned ComputeMappedEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray, Functor Map, bool AllowReplacements = true, unsigned MaxEditDistance = 0) { … } template <typename T> unsigned ComputeEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray, bool AllowReplacements = true, unsigned MaxEditDistance = 0) { … } } // End llvm namespace #endif