How To Create A Skip List in C++?
Posted on 2009-05-10
I'm working on an assignment for one of my classes that I'm having a lot of trouble with. Basically we have to implement a skip list that stores rectangle names and their coordinates. We also have to implement a couple of other functions, like:
insert name x y w h (where x y is the bottom coordinate of the rectangle, w is the width, h is the height, and name is the key that it will be sorted by in the skip list)
remove x y w h
rangesearch x y w h (report all rectangles in the skip list that intersect the query rectangle)
allintersections (report all rectangles that intersect with others)
search name (return parameters of rectangle name)
Also, when we implement the skip list, in order to receive full credit we need to implement it using node splicing, where basically you store within a node an array called forward that keeps a number of pointers equal to the number of lists in participates in.
We also need to maintain a header array that points to the beginning of the lists at each level. Since the number of levels can grow during insertion of successive nodes I also need to implement a procedure that allows the forward array to be extendible.
I cannot use existing STL C++ templates either. I pretty much understand the concept, but I'm having trouble translating it into code, so what I'm looking for in a good solution is a link to or example code that does what I have described.