Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Removing 0 from SkipList<int> breaks enumeration #138

Open
Mabar16 opened this issue May 14, 2020 · 1 comment · May be fixed by #147
Open

Removing 0 from SkipList<int> breaks enumeration #138

Mabar16 opened this issue May 14, 2020 · 1 comment · May be fixed by #147

Comments

@Mabar16
Copy link

Mabar16 commented May 14, 2020

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).

@github-actions
Copy link

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

Gutsonok added a commit to Gutsonok/C-Sharp-Algorithms that referenced this issue Aug 8, 2020
@Gutsonok Gutsonok linked a pull request Aug 8, 2020 that will close this issue
8 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant