#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// simple skiplist implementation
// 1) do not consider duplicate data
// 2) no backward pointer in the node

class SkipList
{
private:
    struct skiplistNode {
        int data; // node's data
        vector<skiplistNode*> level; // level array

        skiplistNode(int d, int l) : data(d), level(l)
        {
        }
    };

    int m_maxlevel; // max level of skip list
    int m_curlevel; // current level of skip list
    int m_len; // number of nodes
    const double m_prob; // probability

    skiplistNode head; // dumb head

    // get random level for a node
    int RandomLevel()
    {
        int level = 1;
        // m_prob probability to reach to upper level
        while ((random() & 0xFFFF) < (m_prob * 0xFFFF))
            level += 1;

        return (level < m_maxlevel) ? level : m_maxlevel;
    }

public:

    SkipList(const int ml = 32, const double p = 0.25) :
        m_maxlevel(ml), m_prob(p), head(INT_MIN, m_maxlevel)
    {
        m_curlevel = 1; // only one level when initialization
        m_len = 0;
    }

    bool Insert(int data)
    {
        // Considering a single linked list, when inserting
        // an element, we need to get the previous pointer

        // As for skiplist, each level is a list, so we need
        // to keep a previous pointer for each level

        vector<skiplistNode*> prev(m_maxlevel);

        // traverse each level to get prev array
        skiplistNode *x = &head;
        for (int i = m_curlevel - 1; i >= 0; i--) {
            // minus i : move towards bottom
            // forward x : move towards right
            while (x->level[i] && x->level[i]->data < data) {
                x = x->level[i];
            }
            prev[i] = x; // update current level's previous pointer
        }

        // duplicate data
        if (x->level[0] && x->level[0]->data == data) return false;

        int level = RandomLevel();
        // increase skiplist's level
        if (level > m_curlevel) {
            for (int i = m_curlevel; i < level; i++) {
                prev[i] = &head; // update prev array
            }
            m_curlevel = level; // update level
        }

        // insert new node
        x = new skiplistNode(data, level);
        if (x == nullptr) return false; // no memory
        for (int i = 0; i < level; i++) {
            // insert x after pointer prev[i]
            x->level[i] = prev[i]->level[i];
            prev[i]->level[i] = x;
        }

        m_len++;
        return true;
    }

    bool Delete(int data)
    {
        // again, we need to keep previous pointer as
        // single linked list delete operation
        vector<skiplistNode*> prev(m_maxlevel);

        // traverse each level to get prev array
        skiplistNode *x = &head;
        for (int i = m_curlevel - 1; i >= 0; i--) {
            while (x->level[i] && x->level[i]->data < data) {
                x = x->level[i];
            }

            prev[i] = x; // update current level's previous pointer
        }

        x = x->level[0];
        if (x == nullptr || x->data != data) return false; // not exist

        // delete
        for (int i = 0; i < m_curlevel; i++) {
            if (prev[i]->level[i] == x) {
                prev[i]->level[i] = x->level[i]; // delete node
            }
        }
        delete x;
        x = nullptr;

        while(m_curlevel > 1 && head.level[m_curlevel - 1] == NULL)
            m_curlevel--; // delete null list on the top

        m_len--; // update length
        return true;
    }

    bool Find(int data)
    {
        skiplistNode *x = &head;
        for (int i = m_curlevel - 1; i >= 0; i--) {
            while (x->level[i] && x->level[i]->data < data) {
                x = x->level[i];
            }

            if (x->level[i] && x->level[i]->data == data) return true;
        }
        return false;
    }
};

struct Test {
    void orderedTest()
    {
        SkipList sl;

        cout << "*************Ordered Test*************" << endl;

        cout << "Insert Nodes:" << endl;
        for (int i = 0; i < 10; i++) {
            cout << "Insert: " << i << "  Result: " << sl.Insert(i);
            cout << endl;
        }

        cout << "Find Nodes:" << endl;
        for (int i = 0; i < 10; i++) {
            cout << "Find: " << i << "  Result: " << sl.Find(i);
            cout << endl;
        }

        cout << "Delete Node: 50  ";
        cout << "Reseult: " << sl.Delete(50) << endl;

        cout << "Find Node: 50  ";
        cout << "Result: " << sl.Find(50) << endl;

        cout << "Insert Node : 50  ";
        cout << "Result: " << sl.Insert(50) << endl;

        cout << "Find Node: 50  ";
        cout << "Result: " << sl.Find(50) << endl;
    }

    void randomTest()
    {
        SkipList sl;

        cout << "*************Random Test*************" << endl;

        cout << "Insert Nodes:" << endl;
        for (int i = 0; i < 10; i++) {
            int r = random() % 20;
            cout << "Insert: " << r << "  Result: " << sl.Insert(r);
            cout << endl;
        }

        cout << "Find Nodes:" << endl;
        for (int i = 0; i < 10; i++) {
            int r = random() % 20;
            cout << "Find: " << r << "  Result: " << sl.Find(r);
            cout << endl;
        }

        cout << "Delete Node: 50  ";
        cout << "Reseult: " << sl.Delete(50) << endl;

        cout << "Find Node: 50  ";
        cout << "Result: " << sl.Find(50) << endl;

        cout << "Insert Node : 50  ";
        cout << "Result: " << sl.Insert(50) << endl;

        cout << "Find Node: 50  ";
        cout << "Result: " << sl.Find(50) << endl;
    }
};

int main(int argc, const char *argv[])
{
    Test t;

    srand(time(nullptr));

    t.orderedTest();
    t.randomTest();

    return 0;
}