Created
May 31, 2011 12:47
-
-
Save Pet3ris/1000446 to your computer and use it in GitHub Desktop.
Old skip list implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <cstdlib> | |
#include <set> | |
using namespace std; | |
const int N = 10000000; | |
const int maxLevel = 20; | |
struct skip_list | |
{ | |
// Node record for each element in the skip list including head and tail | |
struct node | |
{ | |
node **next; | |
int data, levels; | |
node(int ndata, int nlevels) : data(ndata), levels(nlevels) | |
{ | |
next = new node *[nlevels]; | |
} | |
}; | |
node *head, *tail, *trd[maxLevel+1]; | |
int nTrd; | |
// Constructor | |
skip_list() | |
{ | |
head = new node(INT_MIN, maxLevel+1); | |
tail = new node(INT_MAX, maxLevel+1); | |
for (int i = 0; i <= maxLevel; ++i) head->next[i] = tail; | |
} | |
// Checks if the container is empty | |
bool empty() { return head->next[0] == tail; } | |
// Helper function. Traverses the list looking for an element and | |
// maintains a stack of elements (trd) that point to or over the element | |
// at each level | |
void findprev(int query) | |
{ | |
nTrd = 0; | |
node *it = head; | |
for (int l = maxLevel; l >= 0; --l) | |
{ | |
while (query > it->next[l]->data) it = it->next[l]; | |
trd[nTrd++] = it; | |
} | |
} | |
// Determines whether a particular element is in the skip list | |
bool find(int query) | |
{ | |
findprev(query); | |
return query == trd[nTrd - 1]->next[0]->data; | |
} | |
// Inserts an element into the skip list | |
void insert(int ndata) | |
{ | |
findprev(ndata); | |
if (ndata != trd[nTrd - 1]->next[0]->data) | |
{ | |
int randomLevel = 0; | |
while (randomLevel < maxLevel && rand() & 1) | |
++randomLevel; | |
node *newNode = new node(ndata, randomLevel + 1); | |
for (int i = 0; i <= randomLevel; ++i) | |
{ | |
newNode->next[i] = trd[nTrd - i - 1]->next[i]; | |
trd[nTrd - i - 1]->next[i] = newNode; | |
} | |
} | |
} | |
// Removes an element from the skip list | |
void remove(int query) | |
{ | |
findprev(query); | |
if (query == trd[nTrd - 1]->next[0]->data) | |
{ | |
node *deletee = trd[nTrd - 1]->next[0]; | |
for (int i = 0; i < deletee->levels; ++i) | |
trd[nTrd - 1 - i]->next[i] = deletee->next[i]; | |
delete deletee; | |
} | |
} | |
}; | |
int main(int argc, char **argv) | |
{ | |
srand(1111); | |
if (argc > 1) | |
{ | |
skip_list SL; | |
for (int i = 0; i < N; ++i) | |
SL.insert(rand() % 1000000); | |
for (int i = 0; i < N; ++i) | |
SL.find(rand () % 1000000); | |
} | |
else | |
{ | |
set<int> S; | |
for (int i = 0; i < N; ++i) | |
S.insert(rand() % 1000000); | |
for (int i = 0; i < N; ++i) | |
S.find(rand () % 1000000) != S.end(); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment