| | | 1 | | using MoreStructures.SuffixArrays; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures.BurrowsWheelerTransform.Matching.Comparers; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// A <see cref="SuffixAgainstPatternComparer"/> which compares the suffix <see cref="string"/> corresponding to the |
| | | 7 | | /// i-th element (first <see cref="int"/> value) of the provided <see cref="SuffixArray"/>, against the provided |
| | | 8 | | /// <see cref="string"/> pattern, and ignores the second <see cref="int"/> value. |
| | | 9 | | /// </summary> |
| | | 10 | | /// <remarks> |
| | | 11 | | /// <para id="complexity"> |
| | | 12 | | /// COMPLEXITY |
| | | 13 | | /// <br/> |
| | | 14 | | /// - When the provided <see cref="SuffixArray"/> instance has a <see cref="SuffixArray.Indexes"/> sequence which |
| | | 15 | | /// doesn't implement <see cref="IList{T}"/>, the <see cref="SuffixArray.Indexes"/> enumerable has to be |
| | | 16 | | /// enumerated, resulting into a list of exactly n elements. |
| | | 17 | | /// <br/> |
| | | 18 | | /// - Because a complete Suffix Array with direct memory access is provided to <see cref="Compare(int, int)"/>, |
| | | 19 | | /// getting the starting index of the suffix corresponding to the i-th element is a constant-time operation. |
| | | 20 | | /// <br/> |
| | | 21 | | /// - Compare a suffix against the pattern requires comparing at most n chars, where n is the length of |
| | | 22 | | /// <see cref="SuffixAgainstPatternComparer.Text"/>. |
| | | 23 | | /// <br/> |
| | | 24 | | /// - So Time and Space Complexity are both O(n) in the worst case. Space Complexity is O(1) when |
| | | 25 | | /// <see cref="SuffixArray.Indexes"/> implements <see cref="IList{T}"/>. |
| | | 26 | | /// </para> |
| | | 27 | | /// </remarks> |
| | | 28 | | public class SuffixArrayAgainstPatternComparer : SuffixAgainstPatternComparer |
| | | 29 | | { |
| | | 30 | | private readonly IList<int> SuffixArrayIndexes; |
| | | 31 | | |
| | | 32 | | /// <summary> |
| | | 33 | | /// <inheritdoc cref="SuffixArrayAgainstPatternComparer"/> |
| | | 34 | | /// </summary> |
| | | 35 | | /// <param name="text">The text, to extract suffixes from via <paramref name="suffixArray"/>.</param> |
| | | 36 | | /// <param name="suffixArray"> |
| | | 37 | | /// The <see cref="SuffixArray"/> of <paramref name="text"/>, to map the first term of comparison |
| | | 38 | | /// to the starting index in <paramref name="text"/> of the corresponding suffix. |
| | | 39 | | /// </param> |
| | | 40 | | /// <param name="pattern">The pattern, to compare against each suffix of <paramref name="text"/>.</param> |
| | | 41 | | public SuffixArrayAgainstPatternComparer( |
| | | 42 | | TextWithTerminator text, SuffixArray suffixArray, IEnumerable<char> pattern) |
| | 57 | 43 | | : base(text, pattern) |
| | 57 | 44 | | { |
| | 57 | 45 | | SuffixArrayIndexes = suffixArray.Indexes is IList<int> list ? list : suffixArray.Indexes.ToList(); |
| | 57 | 46 | | } |
| | | 47 | | |
| | | 48 | | /// <inheritdoc path="//*[not(self::summary)]" /> |
| | | 49 | | /// <summary> |
| | | 50 | | /// Compares the suffix of text identified by the <paramref name="x"/>-th element of the |
| | | 51 | | /// <see cref="SuffixArray"/> against the pattern. |
| | | 52 | | /// </summary> |
| | | 53 | | public override int Compare(int x, int y) => |
| | 205 | 54 | | CompareSuffixAgainstPattern(x, SuffixArrayIndexes[x]); |
| | | 55 | | } |