Test the efficiency of skip lists. In addition to the functions given in this chapter, implement skipListDelete() and then compare the number of node accesses in searching, deleting, and inserting for large numbers of elements. Compare this efficiency with the efficiency of linked lists and ordered linked lists. Test your program on a randomly generated order of operations to be executed on the elements. These elements should be processed in random order. Then try your program on nonrandom samples.

Here is the header file for the skip lists.

//************************** genSkipL.h ***************************

// generic skip list class

const int maxLevel = 4;

template

class SkipListNode {

public:

SkipListNode() {

}

T key;

SkipListNode **next;

};

template

class SkipList {

public:

SkipList();

bool isEmpty() const;

void choosePowers();

int chooseLevel();

T* skipListSearch(const T&);

void skipListInsert(const T&);

private:

typedef SkipListNode *nodePtr;

nodePtr root[maxLevel];

int powers[maxLevel];

};

template

SkipList::SkipList() {

for (int i = 0; i < maxLevel; i++)

root[i] = 0;

}

template

bool SkipList::isEmpty() const {

return root[0] == 0;

}

template

void SkipList::choosePowers() {

powers[maxLevel-1] = (2 << (maxLevel-1)) - 1; // 2^maxLevel - 1

for (int i = maxLevel - 2, j = 0; i >= 0; i--, j++)

powers[i] = powers[i+1] - (2 << j); // 2^(j+1)

}

template

int SkipList::chooseLevel() {

int i, r = rand() % powers[maxLevel-1] + 1;

for (i = 1; i < maxLevel; i++)

if (r < powers[i])

return i-1; // return a level < the highest level;

return i-1; // return the highest level;

}

template

T* SkipList::skipListSearch(const T& key) {

if (isEmpty())

return 0;

nodePtr prev, curr;

int lvl; // find the highest non-null

for (lvl = maxLevel-1; lvl >= 0 && !root[lvl]; lvl--); // level;

prev = curr = root[lvl];

while (1) {

if (key == curr->key) // success if equal;

return &curr->key;

else if (key < curr->key) { // if smaller, go down

if (lvl == 0) // if possible,

return 0;

else if (curr == root[lvl]) // by one level

curr = root[--lvl]; // starting from the

else curr = *(prev->next + --lvl); // predecessor which

} // can be the root;

else { // if greater,

prev = curr; // go to the next

if (*(curr->next + lvl) != 0) // non-null node

curr = *(curr->next + lvl); // on the same level

else { // or to a list on a lower level;

for (lvl--; lvl >= 0 && *(curr->next + lvl) == 0; lvl--);

if (lvl >= 0)

curr = *(curr->next + lvl);

else return 0;

}

}

}

}

template

void SkipList::skipListInsert(const T& key) {

nodePtr curr[maxLevel], prev[maxLevel], newNode;

int lvl, i;

curr[maxLevel-1] = root[maxLevel-1];

prev[maxLevel-1] = 0;

for (lvl = maxLevel - 1; lvl >= 0; lvl--) {

while (curr[lvl] && curr[lvl]->key < key) {// go to the next

prev[lvl] = curr[lvl]; // if smaller;

curr[lvl] = *(curr[lvl]->next + lvl);

}

if (curr[lvl] && curr[lvl]->key == key) // don't include

return; // duplicates;

if (lvl > 0) // go one level down

if (prev[lvl] == 0) { // if not the lowest

curr[lvl-1] = root[lvl-1]; // level, using a link

prev[lvl-1] = 0; // either from the root

}

else { // or from the predecessor;

curr[lvl-1] = *(prev[lvl]->next + lvl-1);

prev[lvl-1] = prev[lvl];

}

}

lvl = chooseLevel(); // generate randomly level for newNode;

newNode = new SkipListNode;

newNode->next = new nodePtr[sizeof(nodePtr) * (lvl+1)];

newNode->key = key;

for (i = 0; i <= lvl; i++) { // initialize next fields of

*(newNode->next + i) = curr[i]; // newNode and reset to newNode

if (prev[i] == 0) // either fields of the root

root[i] = newNode; // or next fields of newNode's

else *(prev[i]->next + i) = newNode; // predecessors;

}

}