| | | 1 | | using MoreStructures.Utilities; |
| | | 2 | | |
| | | 3 | | namespace MoreStructures; |
| | | 4 | | |
| | | 5 | | /// <summary> |
| | | 6 | | /// A text string with a terminator character which has been rotated leftwards or rightwards, of a number of positions |
| | | 7 | | /// (0 included). |
| | | 8 | | /// </summary> |
| | | 9 | | /// <param name="Underlying">The <see cref="TextWithTerminator"/> instance which has been rotated.</param> |
| | | 10 | | /// <param name="Rotation"> |
| | | 11 | | /// The number of characters to rotate: positive = rightwards, negative = leftwards. |
| | | 12 | | /// </param> |
| | | 13 | | /// <remarks> |
| | | 14 | | /// A virtually rotated terminator-terminated text is required by Burrows-Wheeler Transform construction, when the |
| | | 15 | | /// length of the text is too high to build the Burrows-Wheeler Matrix, which would have n^2 items. |
| | | 16 | | /// </remarks> |
| | 184614 | 17 | | public record VirtuallyRotatedTextWithTerminator(RotatedTextWithTerminator Underlying, int Rotation) |
| | 10440 | 18 | | : IValueEnumerable<char>, IComparable<VirtuallyRotatedTextWithTerminator> |
| | 10440 | 19 | | { |
| | 10440 | 20 | | // CharOrTerminatorComparer is a record, so compared by value |
| | 10440 | 21 | | private readonly IComparer<char> _charsComparer = CharOrTerminatorComparer.Build(Underlying.Terminator); |
| | 10440 | 22 | | |
| | 10440 | 23 | | private sealed class Enumerator : IEnumerator<char> |
| | 10440 | 24 | | { |
| | 10440 | 25 | | private readonly RotatedTextWithTerminator _underlying; |
| | 10440 | 26 | | private readonly int _rotation; |
| | 10440 | 27 | | private int _current; |
| | 10440 | 28 | | |
| | 62769 | 29 | | public Enumerator(RotatedTextWithTerminator underlying, int rotation) |
| | 62769 | 30 | | { |
| | 62769 | 31 | | _underlying = underlying; |
| | 62769 | 32 | | _rotation = rotation; |
| | 62769 | 33 | | Reset(); |
| | 62769 | 34 | | } |
| | 10440 | 35 | | |
| | 10440 | 36 | | public char Current |
| | 10440 | 37 | | { |
| | 10440 | 38 | | get |
| | 170318 | 39 | | { |
| | 170318 | 40 | | if (_current < 0) |
| | 1 | 41 | | throw new InvalidOperationException($"Enumeration has not started. Call {nameof(MoveNext)}."); |
| | 170317 | 42 | | if (_current >= _underlying.Length) |
| | 1 | 43 | | throw new InvalidOperationException("Enumeration already finished"); |
| | 170316 | 44 | | var index = (_current - _rotation) % _underlying.Length; |
| | 170316 | 45 | | return _underlying[index >= 0 ? index : _underlying.Length + index]; |
| | 170316 | 46 | | } |
| | 10440 | 47 | | } |
| | 10440 | 48 | | |
| | 15 | 49 | | object System.Collections.IEnumerator.Current => Current; |
| | 10440 | 50 | | |
| | 10440 | 51 | | public void Dispose() |
| | 62767 | 52 | | { |
| | 10440 | 53 | | // Nothing, for the time being |
| | 62767 | 54 | | } |
| | 107608 | 55 | | public bool MoveNext() => ++_current < _underlying.Length; |
| | 62771 | 56 | | public void Reset() => _current = -1; |
| | 10440 | 57 | | } |
| | 10440 | 58 | | |
| | 10440 | 59 | | /// <summary> |
| | 10440 | 60 | | /// Select a part of <see cref="Underlying"/> by the provided index (either w.r.t. the start or to the end of the |
| | 10440 | 61 | | /// text), applying the <see cref="Rotation"/>. Treat <paramref name="index"/> as circular, over modulo the length |
| | 10440 | 62 | | /// of <see cref="Underlying"/>. |
| | 10440 | 63 | | /// </summary> |
| | 10440 | 64 | | /// <param name="index">The index applied to the underlying string.</param> |
| | 10440 | 65 | | /// <returns>A char containing the selected part.</returns> |
| | 10440 | 66 | | public char this[Index index] |
| | 10440 | 67 | | { |
| | 10440 | 68 | | get |
| | 9252 | 69 | | { |
| | 9252 | 70 | | var length = Underlying.Length; |
| | 9252 | 71 | | var rotatedIndex = (index.GetOffset(length) - Rotation) % length; |
| | 9252 | 72 | | return Underlying[rotatedIndex >= 0 ? rotatedIndex : length + rotatedIndex]; |
| | 9252 | 73 | | } |
| | 10440 | 74 | | } |
| | 10440 | 75 | | |
| | 10440 | 76 | | /// <inheritdoc/> |
| | 10440 | 77 | | public IEnumerator<char> GetEnumerator() => |
| | 62769 | 78 | | new Enumerator(Underlying, Rotation); |
| | 10440 | 79 | | |
| | 10440 | 80 | | /// <inheritdoc/> |
| | 10440 | 81 | | System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => |
| | 2 | 82 | | GetEnumerator(); |
| | 10440 | 83 | | |
| | 10440 | 84 | | /// <inheritdoc/> |
| | 10440 | 85 | | public int CompareTo(VirtuallyRotatedTextWithTerminator? other) |
| | 31383 | 86 | | { |
| | 31383 | 87 | | if (other == null) |
| | 1 | 88 | | throw new ArgumentNullException(nameof(other), "Cannot compare to null."); |
| | 10440 | 89 | | |
| | 31382 | 90 | | using var enumerator = GetEnumerator(); |
| | 31382 | 91 | | using var otherEnumerator = other.GetEnumerator(); |
| | 10440 | 92 | | |
| | 31382 | 93 | | var moveNext = enumerator.MoveNext(); |
| | 31382 | 94 | | var otherMoveNext = otherEnumerator.MoveNext(); |
| | 10440 | 95 | | |
| | 53783 | 96 | | while (moveNext && otherMoveNext && enumerator.Current == otherEnumerator.Current) |
| | 22401 | 97 | | { |
| | 22401 | 98 | | moveNext = enumerator.MoveNext(); |
| | 22401 | 99 | | otherMoveNext = otherEnumerator.MoveNext(); |
| | 22401 | 100 | | } |
| | 10440 | 101 | | |
| | 31383 | 102 | | if (moveNext && !otherMoveNext) return 1; |
| | 31382 | 103 | | if (!moveNext && otherMoveNext) return -1; |
| | 62751 | 104 | | if (moveNext) return _charsComparer.Compare(enumerator.Current, otherEnumerator.Current); |
| | 9 | 105 | | return 0; |
| | 31382 | 106 | | } |
| | 10440 | 107 | | } |