#include "pch.h"
#include <iostream>
using namespace std;
struct skipnode {
    skipnode**next;
    int val;
    int max_ava_lvl;
};
struct skiplist {
    skipnode*first;
    int max_level = 9;
};
int getlvl(int max) {
    int i = 1;
    for (i; i <= max; i++) {
        if (rand() % 2 == 1)break;
    }
    return i;
}
void insert(int key, skiplist*& a) {

    skipnode* to_insert = new skipnode;

    int lvl = getlvl(a->max_level);
    to_insert->max_ava_lvl = lvl;
    to_insert->val = key;
    skipnode*temp = a->first;
    if (a->first == NULL) {
        lvl = a->max_level;
        to_insert->max_ava_lvl = lvl;
        to_insert->next = new skipnode*[lvl];
        a->first = to_insert;
        for (int i = to_insert->max_ava_lvl - 1; i >= 0; i--) {
            a->first->next[i] = NULL;
        }
        return;
    }
    to_insert->next = new skipnode*[lvl];
    if (temp->val > key) {
        to_insert->max_ava_lvl = a->max_level;
        to_insert->next = new skipnode*[a->max_level];
        for (int i = to_insert->max_ava_lvl - 1; i >= 0; i--) {
            to_insert->next[i] = a->first;
        }
        a->first = to_insert;
        return;
    }
    to_insert->next = new skipnode*[lvl];
    for (int i = a->max_level - 1; i >= 0; i--) {
        while ((temp->next[i]!=NULL) && key > temp->next[i]->val) {
            temp = temp->next[i];
        }
        if (lvl >= i) {
            to_insert->next[i] = temp->next[i];
            temp->next[i]= to_insert;
        }
    }

}
void print(skiplist* start) {
    skipnode*temp = start->first;
    while (temp != NULL) {
        cout << temp->val<<" ";
        temp = temp->next[0];
    }
    cout << endl;
}