| | | 1 | | namespace MoreStructures.BurrowsWheelerTransform.Builders.LastFirstFinders; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// A <see cref="NaiveFinder"/> refinement which iterates over <see cref="ILastFirstFinder.BWT"/> and uses |
| | | 5 | | /// binary search on <see cref="ILastFirstFinder.SortedBWT"/>, taking advantage of the fact that it is sorted. |
| | | 6 | | /// </summary> |
| | | 7 | | /// <remarks> |
| | | 8 | | /// <para id="complexity"> |
| | | 9 | | /// COMPLEXITY |
| | | 10 | | /// <br/> |
| | | 11 | | /// - Search over <see cref="ILastFirstFinder.BWT"/> has Time Complexity = O(n), as it is not sorted and there's |
| | | 12 | | /// nothing better than a linear scan without precomputing additional structures helping the search. |
| | | 13 | | /// <br/> |
| | | 14 | | /// - Search over <see cref="ILastFirstFinder.SortedBWT"/> has Time Complexity O(log(n)), as it is sorted and |
| | | 15 | | /// binary search can be applied. |
| | | 16 | | /// <br/> |
| | | 17 | | /// - Space Complexity = O(1) for both search operations, as no additional structure is precomputed and/or stored. |
| | | 18 | | /// </para> |
| | | 19 | | /// </remarks> |
| | | 20 | | public class BinarySearchFinder : NaiveFinder |
| | | 21 | | { |
| | | 22 | | /// <summary> |
| | | 23 | | /// The <see cref="Lists.Searching.ISearch"/> implementation to be used when searching for items in lists sorted |
| | | 24 | | /// in ascending order. |
| | | 25 | | /// </summary> |
| | 231 | 26 | | protected static Lists.Searching.ISearch OrderedAscListSearch { get; } = new Lists.Searching.BinarySearch(); |
| | | 27 | | |
| | | 28 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 29 | | /// <remarks> |
| | | 30 | | /// <inheritdoc cref="BinarySearchFinder" path="/summary"/> |
| | | 31 | | /// </remarks> |
| | | 32 | | public BinarySearchFinder(RotatedTextWithTerminator lastBWMColumn, RotatedTextWithTerminator firstBWMColumn) |
| | 105 | 33 | | : base(lastBWMColumn, firstBWMColumn) |
| | 105 | 34 | | { |
| | 105 | 35 | | } |
| | | 36 | | |
| | | 37 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 38 | | /// <remarks> |
| | | 39 | | /// This implementation takes advantage of the fact that <see cref="ILastFirstFinder.SortedBWT"/> is sorted. |
| | | 40 | | /// <br/> |
| | | 41 | | /// Time Complexity = O(log(n)). Space Complexity = O(1). |
| | | 42 | | /// </remarks> |
| | | 43 | | public override int FindIndexOfNthOccurrenceInSortedBWT(int indexOfCharInBWT, int occurrenceRank) |
| | 219 | 44 | | { |
| | 219 | 45 | | if (occurrenceRank < 0) |
| | 3 | 46 | | throw new ArgumentOutOfRangeException(nameof(occurrenceRank), $"Must be non-negative: {occurrenceRank}."); |
| | | 47 | | |
| | 216 | 48 | | var index = OrderedAscListSearch.Nth(SortedBWT, BWT[indexOfCharInBWT], occurrenceRank, CharComparer); |
| | | 49 | | |
| | 215 | 50 | | if (index < 0) |
| | 3 | 51 | | throw new ArgumentOutOfRangeException(nameof(occurrenceRank), $"Invalid value: {occurrenceRank}."); |
| | 212 | 52 | | return index; |
| | 212 | 53 | | } |
| | | 54 | | |
| | | 55 | | /// <inheritdoc path="//*[not(self::remarks)]"/> |
| | | 56 | | /// <remarks> |
| | | 57 | | /// This implementation takes advantage of the fact that <see cref="ILastFirstFinder.SortedBWT"/> is sorted. |
| | | 58 | | /// <br/> |
| | | 59 | | /// Time Complexity = O(log(n)). Space Complexity = O(1). |
| | | 60 | | /// </remarks> |
| | | 61 | | public override int FindOccurrenceRankOfCharInSortedBWT(int indexOfCharInSortedBWT) |
| | 9 | 62 | | { |
| | 9 | 63 | | if (indexOfCharInSortedBWT < 0 || indexOfCharInSortedBWT >= SortedBWT.Length) |
| | 2 | 64 | | throw new ArgumentOutOfRangeException( |
| | 2 | 65 | | nameof(indexOfCharInSortedBWT), $"Invalid value: {indexOfCharInSortedBWT}"); |
| | | 66 | | |
| | 7 | 67 | | return indexOfCharInSortedBWT - OrderedAscListSearch.First( |
| | 7 | 68 | | SortedBWT, SortedBWT[indexOfCharInSortedBWT], CharComparer, 0, indexOfCharInSortedBWT); |
| | 7 | 69 | | } |
| | | 70 | | } |