aalhour / C-Sharp-Algorithms

:books: :chart_with_upwards_trend: Plug-and-play class-library project of standard Data Structures and Algorithms in C#
MIT License
5.91k stars 1.4k forks source link

Items are not always added to a SkipList #137

Open Hoodedgull opened 4 years ago

Hoodedgull commented 4 years ago

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:

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[bot] commented 4 years ago

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