< 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
92%
Covered lines: 75
Uncovered lines: 6
Coverable lines: 81
Total lines: 204
Line coverage: 92.5%
Branch coverage
75%
Covered branches: 15
Total branches: 20
Branch coverage: 75%
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()50%2277.77%
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>
 228    public ImplementRouterDictionaryWithBinarySearch(int memoryLimit)
 229    {
 230        _memoryLimit = memoryLimit;
 231        _packetsHashSet = new HashSet<(int Source, int Destination, int Timestamp)>(memoryLimit);
 232        _packetsQueue = new Queue<(int Source, int Destination, int Timestamp)>(memoryLimit);
 233        _destinationToTimestampBufferDictionary = new Dictionary<int, TimestampBuffer>(memoryLimit);
 234    }
 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)
 845    {
 846        var packet = (source, destination, timestamp);
 47
 848        if (!_packetsHashSet.Add(packet))
 149        {
 150            return false;
 51        }
 52
 753        if (_packetsQueue.Count == _memoryLimit)
 154        {
 155            ForwardPacket();
 156        }
 57
 758        _packetsQueue.Enqueue(packet);
 59
 760        if (!_destinationToTimestampBufferDictionary.TryGetValue(destination, out var timestampBuffer))
 461        {
 462            timestampBuffer = new TimestampBuffer();
 63
 464            _destinationToTimestampBufferDictionary[destination] = timestampBuffer;
 465        }
 66
 767        timestampBuffer.Add(timestamp);
 68
 769        return true;
 870    }
 71
 72    /// <summary>
 73    ///     Time complexity - O(1)
 74    ///     Space complexity - O(1)
 75    /// </summary>
 76    /// <returns></returns>
 77    public int[] ForwardPacket()
 278    {
 279        if (_packetsQueue.Count == 0)
 080        {
 081            return [];
 82        }
 83
 284        var packet = _packetsQueue.Dequeue();
 85
 286        _packetsHashSet.Remove(packet);
 87
 288        _destinationToTimestampBufferDictionary[packet.Destination].RemoveHead();
 89
 290        return GetForwardBuffer(packet.Source, packet.Destination, packet.Timestamp);
 291    }
 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)
 2102    {
 2103        return _destinationToTimestampBufferDictionary.TryGetValue(destination, out var packetBuffer)
 2104            ? packetBuffer.GetCountInRange(startTime, endTime)
 2105            : 0;
 2106    }
 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)
 2117    {
 2118        ForwardBuffer[0] = source;
 2119        ForwardBuffer[1] = destination;
 2120        ForwardBuffer[2] = timestamp;
 121
 2122        return ForwardBuffer;
 2123    }
 124
 125    private class TimestampBuffer
 126    {
 4127        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)
 7136        {
 7137            _timestamps.Add(packet);
 7138        }
 139
 140        /// <summary>
 141        ///     Time complexity - O(1)
 142        ///     Space complexity - O(1)
 143        /// </summary>
 144        public void RemoveHead()
 2145        {
 2146            _head++;
 2147        }
 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)
 2157        {
 2158            if (_timestamps.Count - _head == 0)
 0159            {
 0160                return 0;
 161            }
 162
 2163            var packetsCount = _timestamps.Count;
 164
 2165            var left = FindLowerBound(startTime);
 2166            var right = FindLowerBound(endTime + 1);
 167
 2168            if (left > right || left >= packetsCount)
 0169            {
 0170                return 0;
 171            }
 172
 2173            return right - left;
 2174        }
 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)
 4183        {
 4184            var low = _head;
 4185            var high = _timestamps.Count;
 186
 10187            while (low < high)
 6188            {
 6189                var mid = low + ((high - low) / 2);
 190
 6191                if (_timestamps[mid] < target)
 3192                {
 3193                    low = mid + 1;
 3194                }
 195                else
 3196                {
 3197                    high = mid;
 3198                }
 6199            }
 200
 4201            return high;
 4202        }
 203    }
 204}
Generated by: ReportGenerator 5.5.4.0
4/1/2026 - 8:25:10 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)