data_structures::SkipList Class Reference

Collaboration diagram for data_structures::SkipList:

Public Member Functions
	SkipList ()
int	randomLevel ()
void	insertElement (int key, void *value)
void	deleteElement (int key)
void *	searchElement (int key)
void	displayList ()

Private Attributes
int	level
	Maximum level of the skiplist.
std::shared_ptr< Node >	header
	Pointer to the header node.

Detailed Description

SkipList class implementation with basic methods

Definition at line 55 of file skip_list.cpp.

Constructor & Destructor Documentation

SkipList()

data_structures::SkipList::SkipList ( )

inline

Skip List constructor. Initializes header, start Node for searching in the list

Definition at line 64 of file skip_list.cpp.

               {
        level = 0;
        // Header initialization
        header = std::make_shared<Node>(-1, MAX_LEVEL);
    }

Member Function Documentation

deleteElement()

void data_structures::SkipList::deleteElement ( int key )

inline

Deletes an element by key and prints if has been removed successfully

Parameters

key	is number that is used for comparision.

Definition at line 133 of file skip_list.cpp.

                                {
        std::shared_ptr<Node> x = header;
 
        std::array<std::shared_ptr<Node>, MAX_LEVEL + 1> update;
        update.fill(nullptr);
 
        for (int i = level; i >= 0; i--) {
            while (x->forward[i] != nullptr && x->forward[i]->key < key) {
                x = x->forward[i];
            }
            update[i] = x;
        }
 
        x = x->forward[0];
 
        bool doesnt_exist = (x == nullptr || x->key != key);
 
        if (!doesnt_exist) {
            for (int i = 0; i <= level; i++) {
                if (update[i]->forward[i] != x) {
                    break;
                }
                update[i]->forward[i] = x->forward[i];
            }
            /* Remove empty levels*/
            while (level > 0 && header->forward[level] == nullptr) level--;
            std::cout << "Deleted" << std::endl;
        } else {
            std::cout << "Doesn't exist" << std::endl;
        }
    }

displayList()

void data_structures::SkipList::displayList ( )

inline

Display skip list level

Definition at line 191 of file skip_list.cpp.

                       {
        std::cout << "Displaying list:\n";
        for (int i = 0; i <= level; i++) {
            std::shared_ptr<Node> node = header->forward[i];
            std::cout << "Level " << (i) << ": ";
            while (node != nullptr) {
                std::cout << node->key << " ";
                node = node->forward[i];
            }
            std::cout << std::endl;
        }
    }

insertElement()

void data_structures::SkipList::insertElement ( int key, void * value )

inline

Inserts elements with given key and value; It's level is computed by randomLevel() function.

Parameters

key	is number that is used for comparision
value	pointer to a value, that can be any type

Definition at line 90 of file skip_list.cpp.

                                             {
        std::cout << "Inserting" << key << "...";
        std::shared_ptr<Node> x = header;
        std::array<std::shared_ptr<Node>, MAX_LEVEL + 1> update;
        update.fill(nullptr);
 
        for (int i = level; i >= 0; i--) {
            while (x->forward[i] != nullptr && x->forward[i]->key < key) {
                x = x->forward[i];
            }
            update[i] = x;
        }
 
        x = x->forward[0];
 
        bool doesnt_exist = (x == nullptr || x->key != key);
        if (doesnt_exist) {
            int rlevel = randomLevel();
 
            if (rlevel > level) {
                for (int i = level + 1; i < rlevel + 1; i++) update[i] = header;
 
                // Update current level
                level = rlevel;
            }
 
            std::shared_ptr<Node> n =
                std::make_shared<Node>(key, rlevel, value);
            for (int i = 0; i <= rlevel; i++) {
                n->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = n;
            }
            std::cout << "Inserted" << std::endl;
 
        } else {
            std::cout << "Exists" << std::endl;
        }
    }

randomLevel()

int data_structures::SkipList::randomLevel ( )

inline

Returns random level of the skip list. Every higher level is 2 times less likely.

Returns

random level for skip list

Definition at line 75 of file skip_list.cpp.

                      {
        int lvl = 0;
        while (static_cast<float>(std::rand()) / RAND_MAX < PROBABILITY &&
               lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

searchElement()

void * data_structures::SkipList::searchElement ( int key )

inline

Searching element in skip list structure

Parameters

key	is number that is used for comparision

Returns

pointer to the value of the node

Definition at line 170 of file skip_list.cpp.

                                 {
        std::shared_ptr<Node> x = header;
        std::cout << "Searching for " << key << std::endl;
 
        for (int i = level; i >= 0; i--) {
            while (x->forward[i] && x->forward[i]->key < key) x = x->forward[i];
        }
 
        x = x->forward[0];
        if (x && x->key == key) {
            std::cout << "Found" << std::endl;
            return x->value;
        } else {
            std::cout << "Not Found" << std::endl;
            return nullptr;
        }
    }

Member Data Documentation

header

std::shared_ptr<Node> data_structures::SkipList::header

private

Pointer to the header node.

Definition at line 57 of file skip_list.cpp.

level

int data_structures::SkipList::level

private

Maximum level of the skiplist.

Definition at line 56 of file skip_list.cpp.

---

The documentation for this class was generated from the following file:

• data_structures/skip_list.cpp