search

emirpasic / gods

GoDS (Go Data Structures) - Sets, Lists, Stacks, Maps, Trees, Queues, and much more
Other
16.18k stars 1.76k forks source link

Add Skip Lists #60

Open sean-public opened 7 years ago

sean-public commented 7 years ago

I think it would be useful to have skip lists included in the GoDS collection.

I previously studied the publicly available Go skip list implementations and found some issues with each. I then created a very fast, threadsafe skip list of my own (under MIT license). I believe it is one of the best foundations to work from for this data structure and can easily be integrated into GoDS.

If you like, I can work on a pull request to include my skip list implementation with the appropriate interface. First, I wanted to make sure this would be useful and to ask what specific details I should watch for / include to ensure smooth compatibility.

emirpasic commented 6 years ago

Any new data structure is a good addition to GoDS, so I might use parts of your code as inspiration to create SkipLists.

Regarding thread-safety, GoDS tries to keep its hands clean from that problem and that should be handled on another abstaction level with mutex or whichever... repeat #68 #84 (also noted in the documentation and comments)

emirpasic commented 6 years ago

@sean-public i took a brief look at your implementation and testing various implementations. i think you have done a good job and would like to move from there.

however, two things i would change due to nature of GoDS which despite trying to stay un-opinionated, things took a path.

  1. i would remove the locking mechanisms as pointed in the documentation and frequently answered questions, it is something i believe that should be easily handled on a higher level with rw/mutexes.
  2. it is under the MIT license. although MIT and BSD are somewhat compatible, would it be possible to convert your MIT to BSD. i am honestly really not dogmatic about any of the two, but would not like to confuse others with having two licences in GoDS. note that i am also not a legal expert on the issue. in that case i would simply attach your BSD licence to https://github.com/emirpasic/gods/blob/master/LICENSE as done with the AVL tree implementation.

do these two suggestions sound reasonable?

tooooolong commented 4 years ago

@sean-public May I help with this

sean-public commented 4 years ago

It has been a few years, let me review everything and get back to you.