| | | 1 | | using MoreLinq; |
| | | 2 | | using MoreStructures.Utilities; |
| | | 3 | | |
| | | 4 | | namespace MoreStructures.BurrowsWheelerTransform; |
| | | 5 | | |
| | | 6 | | /// <summary> |
| | | 7 | | /// The Burrows-Wheeler Matrix (BWM) of a <see cref="TextWithTerminator"/> is the square matrix all cyclic rotations of |
| | | 8 | | /// the provided <see cref="TextWithTerminator"/>, with rows sorted in ascending order and taking into account that |
| | | 9 | | /// <see cref="TextWithTerminator.Terminator"/> is to be considered smaller than any other char in the text. |
| | | 10 | | /// </summary> |
| | | 11 | | /// <param name="Text">The text, corresponding to the provided BWM.</param> |
| | | 12 | | /// <param name="Content">The content of the Burrows-Wheeler Matrix (BWM) of <see cref="Text"/>.</param> |
| | | 13 | | /// <remarks> |
| | | 14 | | /// This <see langword="record"/> is a typed wrapped of the underlying <see langword="IList{string}"/> representing |
| | | 15 | | /// the BWM. It guarantes immutability and strong typing, and also keeps together the <see cref="Text"/> and its |
| | | 16 | | /// matrix <see cref="Content"/>, providing BWM-specific functionalities. |
| | | 17 | | /// </remarks> |
| | 2512 | 18 | | public record BWMatrix(TextWithTerminator Text, IList<string> Content) |
| | 628 | 19 | | { |
| | 628 | 20 | | // CharOrTerminatorComparer is a record, so compared by value |
| | 628 | 21 | | private readonly IComparer<char> _charComparer = CharOrTerminatorComparer.Build(Text.Terminator); |
| | 628 | 22 | | |
| | 628 | 23 | | /// <summary> |
| | 628 | 24 | | /// <inheritdoc cref="BWMatrix(TextWithTerminator, IList{string})" path="/param[@name='Content']"/> |
| | 628 | 25 | | /// </summary> |
| | 628 | 26 | | /// <returns> |
| | 628 | 27 | | /// A readonly immutable list of strings, each one containing a row of the matrix, i.e. a string containing a |
| | 628 | 28 | | /// cyclic rotation of <see cref="Text"/>. |
| | 628 | 29 | | /// </returns> |
| | 628 | 30 | | /// <example> |
| | 628 | 31 | | /// Code: |
| | 628 | 32 | | /// <code> |
| | 628 | 33 | | /// new BWTMatrix(new("ab"), new string[] { "$ab", "ab$", "b$a" }).Content |
| | 628 | 34 | | /// </code> |
| | 628 | 35 | | /// |
| | 628 | 36 | | /// Result: |
| | 628 | 37 | | /// <code> |
| | 628 | 38 | | /// { |
| | 628 | 39 | | /// "$ab", |
| | 628 | 40 | | /// "ab$", |
| | 628 | 41 | | /// "b$a", |
| | 628 | 42 | | /// } |
| | 628 | 43 | | /// </code> |
| | 628 | 44 | | /// </example> |
| | 1144 | 45 | | public IList<string> Content { get; init; } = Content.ToValueReadOnlyCollection(); |
| | 628 | 46 | | |
| | 628 | 47 | | /// <summary> |
| | 628 | 48 | | /// Builds the Burrows-Wheeler Transform from this <see cref="BWMatrix"/>, which corresponds to the last column |
| | 628 | 49 | | /// of the matrix, stored in <see cref="Content"/>. |
| | 628 | 50 | | /// </summary> |
| | 628 | 51 | | /// <returns> |
| | 628 | 52 | | /// A <see cref="BWTransform"/> object wrapping the string containing the Burrows-Wheeler transform. |
| | 628 | 53 | | /// </returns> |
| | 628 | 54 | | /// <example> |
| | 628 | 55 | | /// Code: |
| | 628 | 56 | | /// <code> |
| | 628 | 57 | | /// new BWTMatrix(new("mississippi")).Transform; |
| | 628 | 58 | | /// </code> |
| | 628 | 59 | | /// |
| | 628 | 60 | | /// Result: |
| | 628 | 61 | | /// <code> |
| | 628 | 62 | | /// "ipssm$pissii" |
| | 628 | 63 | | /// </code> |
| | 628 | 64 | | /// </example> |
| | 628 | 65 | | /// <remarks> |
| | 628 | 66 | | /// Requires <see cref="Content"/> calculation. |
| | 628 | 67 | | /// <inheritdoc cref="BWMatrix" path="/remarks/para[@id='lazy-initialization']"/> |
| | 628 | 68 | | /// </remarks> |
| | 628 | 69 | | public BWTransform Transform => |
| | 9690 | 70 | | new(Text, new(Content.Select(r => r[^1]), Text.Terminator)); |
| | 628 | 71 | | |
| | 628 | 72 | | /// <summary> |
| | 628 | 73 | | /// Returns the first column of this <see cref="BWMatrix"/>. Corresponds to the sorted <see cref="Text"/> and |
| | 628 | 74 | | /// also to the sorted <see cref="Transform"/> of this <see cref="BWMatrix"/>. |
| | 628 | 75 | | /// </summary> |
| | 628 | 76 | | /// <example> |
| | 628 | 77 | | /// Code: |
| | 628 | 78 | | /// <code> |
| | 628 | 79 | | /// new BWTMatrix(new("mississippi")).FirstColumn |
| | 628 | 80 | | /// </code> |
| | 628 | 81 | | /// |
| | 628 | 82 | | /// Result: |
| | 628 | 83 | | /// <code> |
| | 628 | 84 | | /// "$iiiimppssss" |
| | 628 | 85 | | /// </code> |
| | 628 | 86 | | /// </example> |
| | 628 | 87 | | /// <remarks> |
| | 628 | 88 | | /// Unlike <see cref="LastColumn"/> and <see cref="Transform"/>, <see cref="FirstColumn"/> wouldn't require |
| | 628 | 89 | | /// computation of the <see cref="Content"/> of this <see cref="BWMatrix"/>, since the <see cref="FirstColumn"/> |
| | 628 | 90 | | /// can easily be calculated by sorting the input <see cref="Text"/>. |
| | 628 | 91 | | /// </remarks> |
| | 628 | 92 | | public string FirstColumn => |
| | 6036 | 93 | | string.Concat(Text.OrderBy(c => c, _charComparer)); |
| | 628 | 94 | | |
| | 628 | 95 | | /// <summary> |
| | 628 | 96 | | /// Returns the last column of this <see cref="BWMatrix"/>. Corresponds to the <see cref="BWTransform.Content"/> |
| | 628 | 97 | | /// of the <see cref="Transform"/> of this <see cref="BWMatrix"/>. |
| | 628 | 98 | | /// </summary> |
| | 628 | 99 | | /// <example> |
| | 628 | 100 | | /// Code: |
| | 628 | 101 | | /// <code> |
| | 628 | 102 | | /// new BWTMatrix(new("mississippi")).LastColumn |
| | 628 | 103 | | /// </code> |
| | 628 | 104 | | /// |
| | 628 | 105 | | /// Result: |
| | 628 | 106 | | /// <code> |
| | 628 | 107 | | /// "ipssm$pissii" |
| | 628 | 108 | | /// </code> |
| | 628 | 109 | | /// </example> |
| | 628 | 110 | | /// <remarks> |
| | 628 | 111 | | /// Requires <see cref="Content"/> calculation. |
| | 628 | 112 | | /// <inheritdoc cref="BWMatrix" path="/remarks/para[@id='lazy-initialization']"/> |
| | 628 | 113 | | /// </remarks> |
| | 628 | 114 | | public string LastColumn => |
| | 364 | 115 | | string.Concat(Transform.Content.RotatedText); |
| | 628 | 116 | | } |