< Summary

Information
Class: MoreStructures.SuffixArrays.CyclicShifts.NaiveDoubleLengthPcsClassifier
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/SuffixArrays/CyclicShifts/NaiveDoubleLengthPcsClassifier.cs
Line coverage
100%
Covered lines: 42
Uncovered lines: 0
Coverable lines: 42
Total lines: 139
Line coverage: 100%
Branch coverage
100%
Covered branches: 12
Total branches: 12
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
get_PcsComparer()100%1100%
get_Input()100%1100%
get_PcsLength()100%1100%
.ctor(...)100%6100%
.ctor(...)100%1100%
Compare(...)100%2100%
Classify()100%4100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/SuffixArrays/CyclicShifts/NaiveDoubleLengthPcsClassifier.cs

#LineLine coverage
 1using MoreStructures.Utilities;
 2
 3namespace MoreStructures.SuffixArrays.CyclicShifts;
 4
 5/// <summary>
 6/// An implementation of <see cref="IDoubleLengthPcsClassifier"/> which solely depends on the input string, to generate
 7/// equivalence classes.
 8/// </summary>
 9/// <remarks>
 10///     <para id="advantages">
 11///     ADVANTAGES AND DISADVANTAGES
 12///     <br/>
 13///     - Unlike other implementations, such as <see cref="OrderBasedDoubleLengthPcsClassifier"/> or
 14///       <see cref="EqClassesBasedDoubleLengthPcsClassifier"/>, this classifier needs to know whether the input being
 15///       provided includes a terminator (i.e. its last char is "special" as it uniquely identify the end of the
 16///       string) or not.
 17///       <br/>
 18///     - This information is required since this classifier performs classification by actually sorting PCS, and
 19///       sorting PCS requires knowing whether a terminator is present or not (and which one it is).
 20///       <br/>
 21///     - Other implementations don't require such information, since they never compare PCS against each other: they
 22///       either use an externally provided position list or compare via the equivalence class list.
 23///     </para>
 24///     <para id="algo">
 25///     ALGORITHM
 26///     <br/>
 27///     - PCS of length L are generated as actual strings from the input string, then sorted in lexicographic order via
 28///       the <see cref="Enumerable.OrderBy{TSource, TKey}(IEnumerable{TSource}, Func{TSource, TKey})"/> method.
 29///       <br/>
 30///     - The ordered sequence of PCS with corresponding starting index in the input string is then iterated over.
 31///       <br/>
 32///     - A new equivalence class is generated (increasing the current counter) every time a PCS differs from the
 33///       previous one. The equivalence class is assigned to the output at the index of the PCS.
 34///       <br/>
 35///     - Finally, the equivalence class list is returned.
 36///     </para>
 37///     <para id="complexity">
 38///     COMPLEXITY
 39///     <br/>
 40///     - Extracting the n PCS of length L from the input string has O(n * L) Time and Space Complexity.
 41///       <br/>
 42///     - Sorting the n PCS of length L via the LINQ-provided QuickSort has O(n^2 * L) Time Complexity and O(n) Space
 43///       Complexity.
 44///       <br/>
 45///     - Iterating over the n PCS of length L is an O(n) operation. Each iteration does O(L) work, since, while
 46///       direct access to the equivalence class list is done in constant time, comparison between the current PCS
 47///       and the previous one is a comparison of two strings of length L, and requires all L chars to be comparerd in
 48///       the worst case.
 49///       <br/>
 50///     - Instantiating the equivalence class list of output is also an O(n) operation.
 51///       <br/>
 52///     - Therefore, Time Complexity, as driven by sorting, is O(n^2 * L) and Space Complexity, as driven by the PCS
 53///       generating and iteration, is O(n * L).
 54///     </para>
 55/// </remarks>
 56public class NaiveDoubleLengthPcsClassifier : IDoubleLengthPcsClassifier
 57{
 2358    private IComparer<string> PcsComparer { get; }
 59
 60    /// <summary>
 61    /// The input text, whose PCS of length <see cref="PcsLength"/> have to be classified.
 62    /// </summary>
 4663    public string Input { get; }
 64
 65    /// <summary>
 66    /// The length of the PCS of <see cref="Input"/> to be classified.
 67    /// </summary>
 2368    public int PcsLength { get; }
 69
 70    /// <summary>
 71    ///     <inheritdoc cref="NaiveDoubleLengthPcsClassifier"/>
 72    /// </summary>
 73    /// <param name="input"><inheritdoc cref="Input" path="/summary"/></param>
 74    /// <param name="pcsLength"><inheritdoc cref="PcsLength" path="/summary"/></param>
 75    /// <param name="inputWithTerminator">
 76    /// Whether <paramref name="input"/> is terminated by a terminator char. If so, the last char of
 77    /// <paramref name="input"/> will be treated as a terminator char when comparing PCS of the input.
 78    /// Otherwise, <see cref="Comparer{T}.Default"/> for <see cref="string"/> will be used.
 79    /// </param>
 2880    public NaiveDoubleLengthPcsClassifier(string input, int pcsLength, bool inputWithTerminator)
 2881    {
 2882        if (pcsLength <= 0 || pcsLength > input.Length)
 583            throw new ArgumentOutOfRangeException(
 584                nameof(pcsLength), $"Must be positive and at most the length of {nameof(input)}.");
 85
 2386        Input = input;
 2387        PcsLength = pcsLength;
 2388        PcsComparer = inputWithTerminator
 2389            ? StringIncludingTerminatorComparer.Build(input[^1])
 2390            : Comparer<string>.Default;
 2391    }
 92
 93    private sealed class PcsAndIndexComparer : IComparer<(string pcs, int index)>
 94    {
 95        private readonly IComparer<string> PcsComparer;
 96        private readonly IComparer<int> IndexComparer;
 97
 2398        public PcsAndIndexComparer(IComparer<string> pcsComparer)
 2399        {
 23100            PcsComparer = pcsComparer;
 23101            IndexComparer = Comparer<int>.Default;
 23102        }
 103
 104        public int Compare((string pcs, int index) x, (string pcs, int index) y)
 201105        {
 201106            var pcsComparison = PcsComparer.Compare(x.pcs, y.pcs);
 201107            if (pcsComparison != 0)
 193108                return pcsComparison;
 8109            return IndexComparer.Compare(x.index, y.index);
 201110        }
 111    }
 112
 113    /// <inheritdoc path="//*[not(self::remarks)]"/>
 114    /// <remarks>
 115    ///     <inheritdoc cref="NaiveDoubleLengthPcsClassifier" path="/remarks"/>
 116    /// </remarks>
 117    public IList<int> Classify()
 23118    {
 23119        var (headList, tail) = PcsUtils
 23120            .ExtractPcsOf(Input, PcsLength)
 114121            .OrderBy(s => s, new PcsAndIndexComparer(PcsComparer))
 23122            .EnumerateExactlyFirst(1);
 123
 23124        var (firstPcs, firstIndex) = headList.Single();
 23125        var eqClasses = new int[Input.Length];
 126
 23127        var currentEqClass = 0;
 23128        eqClasses[firstIndex] = currentEqClass;
 129
 23130        var previousPcs = firstPcs;
 251131        foreach (var (pcs, index) in tail)
 91132        {
 91133            eqClasses[index] = pcs == previousPcs ? currentEqClass : ++currentEqClass;
 91134            previousPcs = pcs;
 91135        }
 136
 23137        return eqClasses;
 23138    }
 139}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

get_PcsComparer()
get_Input()
get_PcsLength()
.ctor(System.String,System.Int32,System.Boolean)
.ctor(System.Collections.Generic.IComparer`1<System.String>)
Compare(System.ValueTuple`2<System.String,System.Int32>,System.ValueTuple`2<System.String,System.Int32>)
Classify()