| | | 1 | | namespace MoreStructures.Lists.Counting; |
| | | 2 | | |
| | | 3 | | /// <summary> |
| | | 4 | | /// An implementation of <see cref="IOccurrencesCounter"/> which uses a <see cref="Dictionary{TKey, TValue}"/> to build |
| | | 5 | | /// the two-level <see cref="IDictionary{TKey, TValue}"/> of occurrences, indexed by distinct item values and index. |
| | | 6 | | /// </summary> |
| | | 7 | | public class DictionaryBasedOccurrencesCounter : IOccurrencesCounter |
| | | 8 | | { |
| | | 9 | | /// <inheritdoc path="//*[not(self::remarks or self::typeparam)]"/> |
| | | 10 | | /// <typeparam name="T"> |
| | | 11 | | /// The type of items of <paramref name="enumerable"/>. |
| | | 12 | | /// </typeparam> |
| | | 13 | | /// <remarks> |
| | | 14 | | /// Perform counting by keeping a <see cref="IDictionary{TKey, TValue}"/> of the current number of occurrences per |
| | | 15 | | /// item encountered, by distinct value of <typeparamref name="T"/> and index, while enumerating |
| | | 16 | | /// <paramref name="enumerable"/>. |
| | | 17 | | /// <br/> |
| | | 18 | | /// Both Time Complexity and Space Complexity are O(n * sigma), where n = number of items in |
| | | 19 | | /// <paramref name="enumerable"/> and sigma = number of the alphabet of <paramref name="enumerable"/>, i.e. the |
| | | 20 | | /// number of distinct items of type <typeparamref name="T"/> in <paramref name="enumerable"/>. |
| | | 21 | | /// </remarks> |
| | | 22 | | public IDictionary<T, IDictionary<int, int>> Count<T>(IEnumerable<T> enumerable) |
| | | 23 | | where T: notnull |
| | 29 | 24 | | { |
| | 29 | 25 | | var lastIndexSetByItem = new Dictionary<T, int> { }; |
| | 29 | 26 | | var counts = new Dictionary<T, IDictionary<int, int>> { }; |
| | 29 | 27 | | var index = 0; |
| | 615 | 28 | | foreach (var item in enumerable) |
| | 264 | 29 | | { |
| | 264 | 30 | | if (!counts.TryGetValue(item, out var countsOfItem)) |
| | 100 | 31 | | counts[item] = countsOfItem = new Dictionary<int, int> { }; |
| | | 32 | | |
| | | 33 | | // Set the count for item at the current index, to be one more than the previous index (or 1) |
| | 264 | 34 | | countsOfItem[index] = countsOfItem.ContainsKey(index - 1) ? countsOfItem[index - 1] + 1 : 1; |
| | | 35 | | |
| | | 36 | | // Set the counts for all indexes between index since the last update of counts[item] and the current one. |
| | 264 | 37 | | if (!lastIndexSetByItem.TryGetValue(item, out var lastIndexSet)) |
| | 100 | 38 | | lastIndexSet = -1; |
| | | 39 | | |
| | 1560 | 40 | | for (var priorIndex = lastIndexSet + 1; priorIndex < index; priorIndex++) |
| | 516 | 41 | | countsOfItem[priorIndex] = countsOfItem[index] - 1; |
| | | 42 | | |
| | 264 | 43 | | lastIndexSetByItem[item] = index; |
| | | 44 | | |
| | | 45 | | // Set the count for all other items at the current index, to be the same as for previous index (or 0) |
| | 2520 | 46 | | foreach (var otherItem in counts.Keys) |
| | 864 | 47 | | if (!Equals(otherItem, item)) |
| | 600 | 48 | | counts[otherItem][index] = counts[otherItem][index - 1]; |
| | | 49 | | |
| | 264 | 50 | | index++; |
| | 264 | 51 | | } |
| | | 52 | | |
| | 29 | 53 | | return counts; |
| | 29 | 54 | | } |
| | | 55 | | } |