< Summary

Information
Class: MoreStructures.Lists.Searching.LinearSearch
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Searching/LinearSearch.cs
Line coverage
100%
Covered lines: 56
Uncovered lines: 0
Coverable lines: 56
Total lines: 198
Line coverage: 100%
Branch coverage
100%
Covered branches: 36
Total branches: 36
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
GetIndexedItemsInRangeEqualTo(...)100%10100%
First(...)100%2100%
FirstAll(...)100%8100%
Last(...)100%2100%
Interval(...)100%8100%
Nth(...)100%6100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Searching/LinearSearch.cs

#LineLine coverage
 1using MoreLinq;
 2using MoreStructures.Utilities;
 3
 4namespace MoreStructures.Lists.Searching;
 5
 6/// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 7///
 8/// <summary>
 9/// An object able to search in linear time for items in direct random access structures, such as lists and
 10/// arrays, which are monodimensional and implement the <see cref="IEnumerable{T}"/> interface.
 11/// </summary>
 12/// <remarks>
 13///     <inheritdoc cref="ISearch"/>
 14///     <br/>
 15///     Unlike <see cref="BinarySearch"/>, this implementation doesn't make any assumption on the order of items in
 16///     in the data structure.
 17/// </remarks>
 18public class LinearSearch : ISearch
 19{
 20    private static IEnumerable<KeyValuePair<int, T>> GetIndexedItemsInRangeEqualTo<T>(
 21        IEnumerable<T> source, T item, IComparer<T>? comparer, int? fromIndex, int? toIndex, bool reverse)
 54022    {
 54023        var length = SearchHelperMethods.ValidateIndexesAndGetLength(source, fromIndex, toIndex);
 53124        fromIndex ??= 0;
 53125        toIndex ??= length - 1;
 26
 53127        comparer ??= Comparer<T>.Default;
 28
 53129        var count = toIndex.Value! - fromIndex.Value! + 1;
 30
 53131        var indexes = Enumerable.Range(fromIndex.Value!, count);
 32
 53133        if (reverse)
 6234        {
 6235            source = source.Reverse();
 63536            indexes = indexes.Select(i => count - 1 - i);
 6237        }
 38
 53139        return source
 53140            .SkipO1(fromIndex.Value!)
 53141            .Take(count)
 53142            .Zip(indexes)
 348943            .Where(c => comparer.Compare(c.First, item) == 0)
 116144            .Select(c => KeyValuePair.Create(c.Second, c.First));
 53145    }
 46
 47    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 48    /// <summary>
 49    ///     <inheritdoc/>
 50    ///     <br/>
 51    ///     This specific implementation does not make any assunption on <paramref name="source"/> being sorted.
 52    /// </summary>
 53    /// <remarks>
 54    /// The algorithm linearly scans the search space from <paramref name="fromIndex"/> to <paramref name="toIndex"/>,
 55    /// one index at every iteration, reducing it linearly to a single item or to an empty set.
 56    /// <br/>
 57    /// Time Complexity = O(n), Space Complexity = O(1), where n = number of items between
 58    /// <paramref name="fromIndex"/> and <paramref name="toIndex"/>.
 59    /// </remarks>
 60    public int First<T>(
 61        IEnumerable<T> source, T item, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null) =>
 62
 34763        GetIndexedItemsInRangeEqualTo(source, item, comparer, fromIndex, toIndex, false)
 33664            .Select(e => e.Key as int?)
 34765            .FirstOrDefault(-1)!
 34766            .Value;
 67
 68    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 69    /// <summary>
 70    ///     <inheritdoc/>
 71    ///     <br/>
 72    ///     This specific implementation does not make any assunption on <paramref name="source"/> being sorted.
 73    /// </summary>
 74    /// <remarks>
 75    ///     <para id="algo">
 76    ///     ALGORITHM
 77    ///     <br/>
 78    ///     The algorithm linearly scans the search space from <paramref name="fromIndex"/> to
 79    ///     <paramref name="toIndex"/>, one index at every iteration, collecting first occurrences into a
 80    ///     <see cref="IDictionary{TKey, TValue}"/>.
 81    ///     </para>
 82    ///     <para id="complexity">
 83    ///     COMPLEXITY
 84    ///     <br/>
 85    ///     Time Complexity = O(n), Space Complexity = O(sigma), where:
 86    ///     <br/>
 87    ///     - n is the <b>number of items</b> between <paramref name="fromIndex"/> and <paramref name="toIndex"/>.
 88    ///       <br/>
 89    ///     - For "large alphabets" scenarios (such as when the alphabet is int - 2^32 possible values, but
 90    ///       <paramref name="source"/> is way smaller than that), sigma is the <b>number of distinct elements </b> of
 91    ///       <paramref name="source"/>.
 92    ///       <br/>
 93    ///     - For "small alphabets" scenarios (such as when the alphabet is comprised of few symbols only), sigma is
 94    ///       the size of the alphabet.
 95    ///       <br/>
 96    ///     - In either scenario the worst case of the O(sigma) Space Complexity is O(n), which is when all the symbols
 97    ///       in <paramref name="source"/> are different from each other).
 98    ///     </para>
 99    /// </remarks>
 100    public IDictionary<T, int> FirstAll<T>(
 101        IEnumerable<T> source, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null)
 102        where T : notnull
 88103    {
 88104        var length = SearchHelperMethods.ValidateIndexesAndGetLength(source, fromIndex, toIndex);
 84105        fromIndex ??= 0;
 84106        toIndex ??= length - 1;
 107
 84108        var result = new Dictionary<T, int> { };
 109
 84110        var sourceWindow = source
 84111            .SkipO1(fromIndex.Value!)
 84112            .Take(toIndex.Value! - fromIndex.Value! + 1);
 113
 84114        var index = fromIndex.Value!;
 3024115        foreach (var item in sourceWindow)
 1386116        {
 1386117            if (!result.TryGetValue(item, out var value))
 741118                result[item] = index;
 1386119            index++;
 1386120        }
 121
 84122        return result;
 84123    }
 124
 125    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 126    /// <summary>
 127    ///     <inheritdoc/>
 128    ///     <br/>
 129    ///     This specific implementation does not make any assunption on <paramref name="source"/> being sorted.
 130    /// </summary>
 131    /// <remarks>
 132    /// The algorithm linearly scans the search space from <paramref name="toIndex"/> to <paramref name="fromIndex"/>,
 133    /// one index at every iteration, reducing it linearly to a single item or to an empty set.
 134    /// <br/>
 135    /// Time Complexity = O(n), Space Complexity = O(1), where n = number of items between <paramref name="fromIndex"/>
 136    /// and <paramref name="toIndex"/>.
 137    /// </remarks>
 138    public int Last<T>(
 139        IEnumerable<T> source, T item, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null) =>
 140
 66141        GetIndexedItemsInRangeEqualTo(source, item, comparer, fromIndex, toIndex, true)
 58142            .Select(e => e.Key as int?)
 66143            .FirstOrDefault(-1)!
 66144            .Value;
 145
 146    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 147    /// <summary>
 148    ///     <inheritdoc/>
 149    ///     <br/>
 150    ///     This specific implementation does not make any assunption on <paramref name="source"/> being sorted.
 151    /// </summary>
 152    /// <remarks>
 153    /// The algorithm linearly scans the search space from <paramref name="fromIndex"/> to <paramref name="toIndex"/>,
 154    /// one index at every iteration.
 155    /// <br/>
 156    /// It just stores the smallest and the biggest index among the ones which correspond to items equal to
 157    /// <paramref name="item"/>. So it has constant, and not linear, space requirements.
 158    /// <br/>
 159    /// Time Complexity = O(n), Space Complexity = O(1), where n = number of items between <paramref name="fromIndex"/>
 160    /// and <paramref name="toIndex"/>.
 161    /// </remarks>
 162    public (int first, int last) Interval<T>(
 163        IEnumerable<T> source, T item, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null) =>
 164
 62165        GetIndexedItemsInRangeEqualTo(source, item, comparer, fromIndex, toIndex, false)
 136166            .Select(e => e.Key)
 198167            .Aggregate((-1, -1), (acc, i) => (
 198168                acc.Item1 < 0 ? i : Math.Min(acc.Item1, i),
 198169                acc.Item2 < 0 ? i : Math.Max(acc.Item2, i)));
 170
 171    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 172    /// <summary>
 173    ///     <inheritdoc/>
 174    ///     <br/>
 175    ///     This specific implementation does not make any assunption on <paramref name="source"/> being sorted.
 176    /// </summary>
 177    /// <remarks>
 178    /// The algorithm linearly scans the search space from <paramref name="toIndex"/> to <paramref name="fromIndex"/>,
 179    /// one index at every iteration, reducing it linearly to a single item or to an empty set.
 180    /// <br/>
 181    /// It just stores the current counter of occurrences of <paramref name="item"/> in <paramref name="source"/>,
 182    /// not all of them. So it has constant, and not linear, space requirements.
 183    /// <br/>
 184    /// Time Complexity = O(n), Space Complexity = O(1), where n = number of items between
 185    /// <paramref name="fromIndex"/> and <paramref name="toIndex"/>.
 186    /// </remarks>
 187    public int Nth<T>(
 188        IEnumerable<T> source, T item, int occurrenceRank, IComparer<T>? comparer = null, int? fromIndex = null,
 189        int? toIndex = null)
 66190    {
 66191        if (occurrenceRank < 0)
 1192            throw new ArgumentOutOfRangeException(nameof(occurrenceRank), "Must be non-negative.");
 193
 65194        return GetIndexedItemsInRangeEqualTo(source, item, comparer, fromIndex, toIndex, false)
 100195            .Select(e => e.Key as int?)
 65196            .ElementAtOrDefault(occurrenceRank) ?? -1;
 65197    }
 198}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

GetIndexedItemsInRangeEqualTo(System.Collections.Generic.IEnumerable`1<T>,T,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>,System.Boolean)
First(System.Collections.Generic.IEnumerable`1<T>,T,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>)
FirstAll(System.Collections.Generic.IEnumerable`1<T>,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>)
Last(System.Collections.Generic.IEnumerable`1<T>,T,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>)
Interval(System.Collections.Generic.IEnumerable`1<T>,T,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>)
Nth(System.Collections.Generic.IEnumerable`1<T>,T,System.Int32,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>)