INSERT METHOD

insert.cpp

int coin(double propability, int times) {
    std::srand((unsigned int) std::time(0));
    int sum = 0;
    for (int i = 0; i < times; ++i) {
        double gen = ((double) rand() / (RAND_MAX));
        if (gen < propability)
            sum += 1;
        else
            break;
    }
    return sum;
}


template<class Value, class Key, int numLevels>
void SkipList<Value, Key, numLevels>::insert(Value value, Key key) {


    // Determine how lucky coin
    int lvlcount = coin(this->m_probability, numLevels - 1) - 1;

    //init new elem
    NodeSkipList<Value, Key, numLevels> *new_element = new NodeSkipList<Value, Key, numLevels>(key, value);
    new_element->m_levelHighest = lvlcount;

    //start point
    NodeSkipList<Value, Key, numLevels> *res = this->getPreHead();

    int curlvl = numLevels - 1;
    //find place
    while (true) {
        if (curlvl != -1) {
            while (res->m_nextjump[curlvl] != this->getPreHead()
                   && res->m_nextjump[curlvl]->m_key <= key) {
                res = res->m_nextjump[curlvl];
            }
            if (curlvl <= lvlcount) {
                //insert on cur lvl
                NodeSkipList<Value, Key, numLevels> *tmp = res->m_nextjump[curlvl];
                res->m_nextjump[curlvl] = new_element;
                new_element->m_nextjump[curlvl] = tmp;
            }
            curlvl--;
        } else if (curlvl == -1) {
            while (res->m_next != this->getPreHead()
                   && res->m_next->m_key <= key) {
                res = res->m_next;
            }
            //insert on base lvl
            NodeSkipList<Value, Key, numLevels> *tmp = res->m_next;
            res->m_next = new_element;
            new_element->m_next = tmp;
            break;
        }

    }

}