The Wayback Machine - https://web.archive.org/web/20201016025017/https://github.com/aalhour/C-Sharp-Algorithms/issues/137
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

Items are not always added to a SkipList #137

Open
Hoodedgull opened this issue May 13, 2020 · 1 comment · May be fixed by #147
Open

Items are not always added to a SkipList #137

Hoodedgull opened this issue May 13, 2020 · 1 comment · May be fixed by #147

Comments

@Hoodedgull
Copy link

@Hoodedgull Hoodedgull commented May 13, 2020

Describe the bug
When attempting to add an item to the SkipList, it is not always added. This seems to be caused by the fact that the _getNextLevel() method may return 0, in which case the for loop on line 138 that adds elements to the SkipList is not entered because lvl is 0.

To Reproduce
It is a bit difficult to reproduce, since a SkipList is a probabilistic data structure, so the behaviour will not be the same every time it is used. However, the following should work:

  1. Create a unit test
  2. Create a SkipList in that test
  3. Add a random number to the list and call list.Contains(number)
  4. Assert that this is true because you just added the number
  5. Run that test 1000 times

Expected behavior
I expect that after adding a number to a list of integers, the list will contain that number

Environmnet:

  • OS: Windows 10
  • .NET Version: .NET Core v3.1.101
  • IDE: Visual Studio Enterprise 2019

Additional context
If the Random object in the SkipList is initialized with seed 123, the first call to Add will not insert the element

@github-actions
Copy link

@github-actions github-actions bot commented May 13, 2020

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 5, 2020
@Gutsonok Gutsonok linked a pull request that will close this issue Aug 5, 2020
8 of 8 tasks complete
Gutsonok added a commit to Gutsonok/C-Sharp-Algorithms that referenced this issue Aug 8, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

1 participant
You can’t perform that action at this time.