insert_skiplist

template<class Value, class Key, int numLevels>
void SkipList<Value, Key, numLevels>::insert(const Value &val, const Key &key)
{
    Node* newNode = new Node(key, val);
    Node* prevNode;

    std::cout << "doing INS of key " << key << std::endl;
    if (this->_preHead->next == this->_preHead)
    {
        this->_preHead->next = newNode;
        newNode->next = this->_preHead;
    }
    else
    {
        prevNode = findLastLessThan(key);

        // move right a bit among equal nodes
        while (prevNode->next != this->_preHead && prevNode->next->key == key)
            prevNode = prevNode->next;

        newNode->next = prevNode->next;
        prevNode->next = newNode;
    }

    int currentLevel = -1;

    // std::rand() генерирует числа [0, RAND_MAX]. Превращаем их в отрезок от 0 до 1 и радуемся.
    // Высчитываем, на каком уровне у нас впервые встретится элемент
    float prob = (float) std::rand() / RAND_MAX;

//    std::cout << "Prob is " << prob << "\n";
    while (currentLevel < numLevels - 1 && prob < _probability)
    {
        ++currentLevel;
        prob = (float) std::rand() / RAND_MAX;
//        std::cout << "And now prob is " << prob << "\n";
    }

    // adding references on higher levels
    using namespace std;
    newNode->levelHighest = currentLevel;
    Node* currentNode = this->_preHead;

    while (currentLevel != -1)
    {
        // right in sparse levels!
        Node* right = currentNode->nextJump[currentLevel];

        // our new node is the last among all equal to it, (so <= )
        if (right != this->_preHead && right->key <= key)
        {
            // just go right
            currentNode = right;
        }
        else
        {
            // insert new reference in sparse level.
            currentNode->nextJump[currentLevel] = newNode;
            newNode->nextJump[currentLevel] = right;
            // go down
            --currentLevel;
        }
    }

}