< Summary

Information
Class: LeetCode.Algorithms.AllOneDataStructure.AllOneDataStructureLinkedList
Assembly: LeetCode
File(s): D:\a\LeetCode-CS\LeetCode-CS\source\LeetCode\Algorithms\AllOneDataStructure\AllOneDataStructureLinkedList.cs
Line coverage
68%
Covered lines: 76
Uncovered lines: 35
Coverable lines: 111
Total lines: 203
Line coverage: 68.4%
Branch coverage
55%
Covered branches: 21
Total branches: 38
Branch coverage: 55.2%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity Line coverage
.ctor()100%11100%
Inc(...)80%101085.71%
Dec(...)0%110100%
GetMaxKey()50%5466.66%
GetMinKey()50%5466.66%
MoveKey(...)100%22100%
InsertNodeAfter(...)100%22100%
RemoveNode(...)100%44100%
GetFirstKey(...)50%22100%
.ctor(...)100%11100%
get_Count()100%11100%
get_KeysHashSet()100%11100%
get_PreviousNode()100%11100%
get_NextNode()100%11100%

File(s)

D:\a\LeetCode-CS\LeetCode-CS\source\LeetCode\Algorithms\AllOneDataStructure\AllOneDataStructureLinkedList.cs

#LineLine coverage
 1// --------------------------------------------------------------------------------
 2// Copyright (C) 2025 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.AllOneDataStructure;
 13
 14/// <inheritdoc />
 15public class AllOneDataStructureLinkedList : IAllOneDataStructure
 16{
 117    private readonly Node _headNode = new(int.MinValue);
 118    private readonly Dictionary<string, Node> _keyNodeDictionary = new();
 119    private readonly Node _tailNode = new(int.MaxValue);
 20
 121    public AllOneDataStructureLinkedList()
 122    {
 123        _headNode.NextNode = _tailNode;
 124        _tailNode.PreviousNode = _headNode;
 125    }
 26
 27    /// <summary>
 28    ///     Time complexity - O(1)
 29    ///     Space complexity - O(n)
 30    /// </summary>
 31    /// <param name="key"></param>
 32    public void Inc(string key)
 333    {
 334        if (_keyNodeDictionary.TryGetValue(key, out var currentNode))
 135        {
 136            var nextNode = currentNode.NextNode;
 37
 138            if (nextNode == null)
 039            {
 040                return;
 41            }
 42
 143            if (nextNode.Count != currentNode.Count + 1)
 144            {
 145                var newNode = new Node(currentNode.Count + 1);
 46
 147                InsertNodeAfter(currentNode, newNode);
 48
 149                nextNode = newNode;
 150            }
 51
 152            MoveKey(key, currentNode, nextNode);
 153        }
 54        else
 255        {
 256            if (_headNode.NextNode == null)
 057            {
 058                return;
 59            }
 60
 261            if (_headNode.NextNode.Count != 1)
 262            {
 263                var newNode = new Node(1);
 64
 265                InsertNodeAfter(_headNode, newNode);
 266            }
 67
 268            _headNode.NextNode.KeysHashSet.Add(key);
 269            _keyNodeDictionary[key] = _headNode.NextNode;
 270        }
 371    }
 72
 73    /// <summary>
 74    ///     Time complexity - O(1)
 75    ///     Space complexity - O(n)
 76    /// </summary>
 77    /// <param name="key"></param>
 78    public void Dec(string key)
 079    {
 080        if (!_keyNodeDictionary.TryGetValue(key, out var currentNode))
 081        {
 082            return;
 83        }
 84
 085        if (currentNode.Count == 1)
 086        {
 087            _keyNodeDictionary.Remove(key);
 88
 089            currentNode.KeysHashSet.Remove(key);
 90
 091            if (currentNode.KeysHashSet.Count == 0)
 092            {
 093                RemoveNode(currentNode);
 094            }
 095        }
 96        else
 097        {
 098            var prevNode = currentNode.PreviousNode;
 99
 0100            if (prevNode == null)
 0101            {
 0102                return;
 103            }
 104
 0105            if (prevNode.Count != currentNode.Count - 1)
 0106            {
 0107                var newNode = new Node(currentNode.Count - 1);
 108
 0109                InsertNodeAfter(prevNode, newNode);
 110
 0111                prevNode = newNode;
 0112            }
 113
 0114            MoveKey(key, currentNode, prevNode);
 0115        }
 0116    }
 117
 118    /// <summary>
 119    ///     Time complexity - O(1)
 120    ///     Space complexity - O(n)
 121    /// </summary>
 122    /// <returns></returns>
 123    public string GetMaxKey()
 2124    {
 2125        if (_tailNode.PreviousNode == null)
 0126        {
 0127            return string.Empty;
 128        }
 129
 2130        return _tailNode.PreviousNode == _headNode ? string.Empty : GetFirstKey(_tailNode.PreviousNode);
 2131    }
 132
 133    /// <summary>
 134    ///     Time complexity - O(1)
 135    ///     Space complexity - O(n)
 136    /// </summary>
 137    /// <returns></returns>
 138    public string GetMinKey()
 2139    {
 2140        if (_headNode.NextNode == null)
 0141        {
 0142            return string.Empty;
 143        }
 144
 2145        return _headNode.NextNode == _tailNode ? string.Empty : GetFirstKey(_headNode.NextNode);
 2146    }
 147
 148    private void MoveKey(string key, Node fromNode, Node toNode)
 1149    {
 1150        fromNode.KeysHashSet.Remove(key);
 151
 1152        if (fromNode.KeysHashSet.Count == 0)
 1153        {
 1154            RemoveNode(fromNode);
 1155        }
 156
 1157        toNode.KeysHashSet.Add(key);
 158
 1159        _keyNodeDictionary[key] = toNode;
 1160    }
 161
 162    private static void InsertNodeAfter(Node prevNode, Node newNode)
 3163    {
 3164        newNode.PreviousNode = prevNode;
 3165        newNode.NextNode = prevNode.NextNode;
 166
 3167        if (prevNode.NextNode != null)
 3168        {
 3169            prevNode.NextNode.PreviousNode = newNode;
 3170        }
 171
 3172        prevNode.NextNode = newNode;
 3173    }
 174
 175    private static void RemoveNode(Node node)
 1176    {
 1177        if (node.PreviousNode != null)
 1178        {
 1179            node.PreviousNode.NextNode = node.NextNode;
 1180        }
 181
 1182        if (node.NextNode != null)
 1183        {
 1184            node.NextNode.PreviousNode = node.PreviousNode;
 1185        }
 1186    }
 187
 188    private static string GetFirstKey(Node node)
 4189    {
 4190        return node.KeysHashSet.Count > 0 ? node.KeysHashSet.First() : string.Empty;
 4191    }
 192
 5193    private class Node(int count)
 194    {
 10195        public int Count { get; } = count;
 196
 18197        public HashSet<string> KeysHashSet { get; } = [];
 198
 17199        public Node? PreviousNode { get; set; }
 200
 35201        public Node? NextNode { get; set; }
 202    }
 203}
Generated by: ReportGenerator 5.4.9.0
7/17/2025 - 6:24:25 PM
GitHub | reportgenerator.io

Methods/Properties

.ctor()
Inc(System.String)
Dec(System.String)
GetMaxKey()
GetMinKey()
MoveKey(System.String,LeetCode.Algorithms.AllOneDataStructure.AllOneDataStructureLinkedList/Node,LeetCode.Algorithms.AllOneDataStructure.AllOneDataStructureLinkedList/Node)
InsertNodeAfter(LeetCode.Algorithms.AllOneDataStructure.AllOneDataStructureLinkedList/Node,LeetCode.Algorithms.AllOneDataStructure.AllOneDataStructureLinkedList/Node)
RemoveNode(LeetCode.Algorithms.AllOneDataStructure.AllOneDataStructureLinkedList/Node)
GetFirstKey(LeetCode.Algorithms.AllOneDataStructure.AllOneDataStructureLinkedList/Node)
.ctor(System.Int32)
get_Count()
get_KeysHashSet()
get_PreviousNode()
get_NextNode()