C-Sharp-Algorithms

C-Sharp-Algorithms copied to clipboard

Describe the bug Attempting to enumerate a SkipList<int> whose head node has been removed leads to the program running indefinitely. The head can be removed by calling Remove(0), the defualt value for int, whilst the list contains a negative int.

To Reproduce Reproducing this bug can be done as follows:

1. Instantiate a new SkipList<int> var list = new SkipList<int>();
2. Add any negative integer to the list list.Add(-23);
3. Attempt to remove 0 (the head node) from the list list.Remove(0);
4. Perform (almost) any operation that enumerates the skip list list.Contains(2);

Expected behavior list.Remove(0); should not modify the list unless 0 has been added explicitly.

Environment OS: Windows 10 Home (Version 10.0.18362 Build 18362) .NET Version: .NET Core v3.1.101 IDE: Microsoft Visual Studio Community 2019 - Version 16.4.5

Additional context

• The bug can only be reproduced if the SkipList<int> contains at least one negative integer.

• The bug will not occur if the value 0 has been added to (and not removed from) the SkipList<int>.

• Step 4 in To Reproduce can be replaced by any function that iterates over the skip list: Contains, Find, Remove, for-each looping over the list, etc.

• NB: Contains and Find will function as intended if you search for an int that exists in the list (list.Contains(-23); in the case of the example would still work).

Thanks for supporting the development of C# Algorithms with your first issue! We look forward to handling it.