< Summary

Information
Class: LeetCode.Algorithms.ImplementRouter.ImplementRouterDictionaryWithBinarySearch
Assembly: LeetCode
File(s): D:\a\LeetCode-CS\LeetCode-CS\source\LeetCode\Algorithms\ImplementRouter\ImplementRouterDictionaryWithBinarySearch.cs
Line coverage
95%
Covered lines: 77
Uncovered lines: 4
Coverable lines: 81
Total lines: 204
Line coverage: 95%
Branch coverage
80%
Covered branches: 16
Total branches: 20
Branch coverage: 80%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.cctor()100%11100%
.ctor(...)100%11100%
AddPacket(...)100%66100%
ForwardPacket()100%22100%
GetCount(...)50%22100%
GetForwardBuffer(...)100%11100%
.ctor()100%11100%
Add(...)100%11100%
RemoveHead()100%11100%
GetCountInRange(...)50%7666.66%
FindLowerBound(...)100%44100%

File(s)

D:\a\LeetCode-CS\LeetCode-CS\source\LeetCode\Algorithms\ImplementRouter\ImplementRouterDictionaryWithBinarySearch.cs

#LineLine coverage
 1// --------------------------------------------------------------------------------
 2// Copyright (C) 2026 Eugene Eremeev (also known as Yevhenii Yeriemeieiv).
 3// All Rights Reserved.
 4// --------------------------------------------------------------------------------
 5// This software is the confidential and proprietary information of Eugene Eremeev
 6// (also known as Yevhenii Yeriemeieiv) ("Confidential Information"). You shall not
 7// disclose such Confidential Information and shall use it only in accordance with
 8// the terms of the license agreement you entered into with Eugene Eremeev (also
 9// known as Yevhenii Yeriemeieiv).
 10// --------------------------------------------------------------------------------
 11
 12namespace LeetCode.Algorithms.ImplementRouter;
 13
 14/// <inheritdoc />
 15public sealed class ImplementRouterDictionaryWithBinarySearch : IImplementRouter
 16{
 117    private static readonly int[] ForwardBuffer = new int[3];
 18    private readonly Dictionary<int, TimestampBuffer> _destinationToTimestampBufferDictionary;
 19    private readonly int _memoryLimit;
 20    private readonly HashSet<(int Source, int Destination, int Timestamp)> _packetsHashSet;
 21    private readonly Queue<(int Source, int Destination, int Timestamp)> _packetsQueue;
 22
 23    /// <summary>
 24    ///     Time complexity - O(1)
 25    ///     Space complexity - O(n)
 26    /// </summary>
 27    /// <param name="memoryLimit"></param>
 428    public ImplementRouterDictionaryWithBinarySearch(int memoryLimit)
 429    {
 430        _memoryLimit = memoryLimit;
 431        _packetsHashSet = new HashSet<(int Source, int Destination, int Timestamp)>(memoryLimit);
 432        _packetsQueue = new Queue<(int Source, int Destination, int Timestamp)>(memoryLimit);
 433        _destinationToTimestampBufferDictionary = new Dictionary<int, TimestampBuffer>(memoryLimit);
 434    }
 35
 36    /// <summary>
 37    ///     Time complexity - O(1)
 38    ///     Space complexity - O(1)
 39    /// </summary>
 40    /// <param name="source"></param>
 41    /// <param name="destination"></param>
 42    /// <param name="timestamp"></param>
 43    /// <returns></returns>
 44    public bool AddPacket(int source, int destination, int timestamp)
 1145    {
 1146        var packet = (source, destination, timestamp);
 47
 1148        if (!_packetsHashSet.Add(packet))
 249        {
 250            return false;
 51        }
 52
 953        if (_packetsQueue.Count == _memoryLimit)
 154        {
 155            ForwardPacket();
 156        }
 57
 958        _packetsQueue.Enqueue(packet);
 59
 960        if (!_destinationToTimestampBufferDictionary.TryGetValue(destination, out var timestampBuffer))
 661        {
 662            timestampBuffer = new TimestampBuffer();
 63
 664            _destinationToTimestampBufferDictionary[destination] = timestampBuffer;
 665        }
 66
 967        timestampBuffer.Add(timestamp);
 68
 969        return true;
 1170    }
 71
 72    /// <summary>
 73    ///     Time complexity - O(1)
 74    ///     Space complexity - O(1)
 75    /// </summary>
 76    /// <returns></returns>
 77    public int[] ForwardPacket()
 478    {
 479        if (_packetsQueue.Count == 0)
 180        {
 181            return [];
 82        }
 83
 384        var packet = _packetsQueue.Dequeue();
 85
 386        _packetsHashSet.Remove(packet);
 87
 388        _destinationToTimestampBufferDictionary[packet.Destination].RemoveHead();
 89
 390        return GetForwardBuffer(packet.Source, packet.Destination, packet.Timestamp);
 491    }
 92
 93    /// <summary>
 94    ///     Time complexity - O(log m), where m is the number of timestamps for this destination
 95    ///     Space complexity - O(1)
 96    /// </summary>
 97    /// <param name="destination"></param>
 98    /// <param name="startTime"></param>
 99    /// <param name="endTime"></param>
 100    /// <returns></returns>
 101    public int GetCount(int destination, int startTime, int endTime)
 3102    {
 3103        return _destinationToTimestampBufferDictionary.TryGetValue(destination, out var packetBuffer)
 3104            ? packetBuffer.GetCountInRange(startTime, endTime)
 3105            : 0;
 3106    }
 107
 108    /// <summary>
 109    ///     Time complexity - O(1)
 110    ///     Space complexity - O(1)
 111    /// </summary>
 112    /// <param name="source"></param>
 113    /// <param name="destination"></param>
 114    /// <param name="timestamp"></param>
 115    /// <returns></returns>
 116    private static int[] GetForwardBuffer(int source, int destination, int timestamp)
 3117    {
 3118        ForwardBuffer[0] = source;
 3119        ForwardBuffer[1] = destination;
 3120        ForwardBuffer[2] = timestamp;
 121
 3122        return ForwardBuffer;
 3123    }
 124
 125    private class TimestampBuffer
 126    {
 6127        private readonly List<int> _timestamps = [];
 128        private int _head;
 129
 130        /// <summary>
 131        ///     Time complexity - O(1), O(n) in worst-case on resize
 132        ///     Space complexity - O(1)
 133        /// </summary>
 134        /// <param name="packet"></param>
 135        public void Add(int packet)
 9136        {
 9137            _timestamps.Add(packet);
 9138        }
 139
 140        /// <summary>
 141        ///     Time complexity - O(1)
 142        ///     Space complexity - O(1)
 143        /// </summary>
 144        public void RemoveHead()
 3145        {
 3146            _head++;
 3147        }
 148
 149        /// <summary>
 150        ///     Time complexity - O(log m), where m is the number of timestamps currently stored
 151        ///     Space complexity - O(1)
 152        /// </summary>
 153        /// <param name="startTime"></param>
 154        /// <param name="endTime"></param>
 155        /// <returns></returns>
 156        public int GetCountInRange(int startTime, int endTime)
 3157        {
 3158            if (_timestamps.Count - _head == 0)
 0159            {
 0160                return 0;
 161            }
 162
 3163            var packetsCount = _timestamps.Count;
 164
 3165            var left = FindLowerBound(startTime);
 3166            var right = FindLowerBound(endTime + 1);
 167
 3168            if (left > right || left >= packetsCount)
 0169            {
 0170                return 0;
 171            }
 172
 3173            return right - left;
 3174        }
 175
 176        /// <summary>
 177        ///     Time complexity - O(log m), where m is the number of timestamps currently stored
 178        ///     Space complexity - O(1)
 179        /// </summary>
 180        /// <param name="target"></param>
 181        /// <returns></returns>
 182        private int FindLowerBound(int target)
 6183        {
 6184            var low = _head;
 6185            var high = _timestamps.Count;
 186
 14187            while (low < high)
 8188            {
 8189                var mid = low + ((high - low) / 2);
 190
 8191                if (_timestamps[mid] < target)
 4192                {
 4193                    low = mid + 1;
 4194                }
 195                else
 4196                {
 4197                    high = mid;
 4198                }
 8199            }
 200
 6201            return high;
 6202        }
 203    }
 204}
Generated by: ReportGenerator 5.5.4.0
4/15/2026 - 11:20:12 AM
GitHub | reportgenerator.io

Methods/Properties

.cctor()
.ctor(System.Int32)
AddPacket(System.Int32,System.Int32,System.Int32)
ForwardPacket()
GetCount(System.Int32,System.Int32,System.Int32)
GetForwardBuffer(System.Int32,System.Int32,System.Int32)
.ctor()
Add(System.Int32)
RemoveHead()
GetCountInRange(System.Int32,System.Int32)
FindLowerBound(System.Int32)