TestSkipList

#include <vector>

using namespace std;

const int MAX_LEVELS = 10;

/** \brief СкипЛист на стероидах.
 * Умеет печатать себя с помощью PRINT_REFS, PRINT_VALUES, PRINT_KEYS.
 * Ещё умеет запрашивать нужную ноду через operator[], вычислять длину себя, и среднюю длину уровней.
 * Может создаваться по заданным значениям ключей и их уровней.
 */
class TestSkipList
        : public SkipList<std::string, int, MAX_LEVELS>
{
public:
    explicit TestSkipList(double prob = 0.5) : SkipList(prob)
    {}

    /// Constr with initial values and levels. Levels must be in [0..MAX_LEVELS]
    TestSkipList(const vector<int>& keys,
                 const vector<int>& levels,
                 const vector<string>& values = vector<string>()
    ) : SkipList()
    {
        if (keys.size() != levels.size())
            throw invalid_argument("keys.size != levels.size");

        if (!values.empty() && !levels.empty() && values.size() != levels.size())
            throw invalid_argument("values.size != levels.size");

        Node* last = _preHead;
        for (int i = 0; i < keys.size(); ++i)
        {
            string value = values.empty() ? "val" + to_string(i) : values[i];
            Node* newNode = new Node(keys[i], value);
            newNode->levelHighest = levels[i] - 1;
            if (levels[i] > MAX_LEVELS || levels[i] < 0)
                throw invalid_argument("some level is not in [0..MAX_LEVELS]");

            last->next = newNode;
            newNode->next = _preHead;

            last = newNode;
        }

        for (int i = 0; i < MAX_LEVELS; ++i)
        {
            Node* prev = _preHead;

            Node* curr = _preHead;
            while (curr->next != _preHead)
            {
                curr = curr->next;

                if (curr->levelHighest >= i)
                {
                    prev->nextJump[i] = curr;
                    prev = curr;
                }
            }
            prev->nextJump[i] = _preHead;
        }
    }

    double getProbability()
    {
        return _probability;
    }

    /// -1 returns _preHead.
    Node* operator[](int pos)
    {
        if (pos < -1)
            throw invalid_argument("pos < -1");
        Node* curr = _preHead;
        while (pos-- != -1)
            curr = curr->next;
        return curr;
    }

    int size()
    {
        int ans = 0;
        Node* curr = _preHead;
        while (curr->next != _preHead)
        {
            ans++;
            curr = curr->next;
        }
        return ans;
    }

    double meanHeight()
    {
        long hSum = 0;
        int size = 0;
        Node* curr = _preHead;
        while (curr->next != _preHead)
        {
            curr = curr->next;
            hSum += curr->levelHighest + 1;
            size++;
        }
        return (double) hSum / size;
    }

    /// Displays only heights of all nodes. If you need to validate references, use PRINT_REF.
    void PRINT_KEYS()
    {
        printf("\nPRINT_KEYS\n");
        for (int i = MAX_LEVELS - 1; i >= -1; --i)
        {
            printf("%2d pr ", i);
            Node* curr = _preHead;
            while (curr->next != _preHead)
            {
                curr = curr->next;
                if (curr->levelHighest < i)
                    printf("--- ");
                else
                    printf("%3d ", curr->key);
            }
            printf("pr\n");
        }
        cout << endl;
    }

    /// Works like PRINT_KEYS, but prints values instead of keys.
    /// size - max size of string value
    void PRINT_VALUES(unsigned int size = 5)
    {
        string pattern_val = "%" + to_string(size) + "s ";
        string pattern_sparse = string(size, '-') + " ";

        printf("\nPRINT_VALUES\n");
        for (int i = MAX_LEVELS - 1; i >= -1; --i)
        {
            printf("%2d pr ", i);
            Node* curr = _preHead;
            while (curr->next != _preHead)
            {
                curr = curr->next;
                if (curr->levelHighest < i)
                    printf(pattern_sparse.c_str());
                else
                    printf(pattern_val.c_str(), curr->value.c_str());
            }
            printf("pr\n");
        }
        cout << endl;
    }

    /// It is like PRINT_KEYS, but it iterates over references in sparse levels.
    void PRINT_REFS()
    {
        printf("\nPRINT_REFS\n");
        for (int i = MAX_LEVELS - 1; i >= 0; --i)
        {
            printf("%2d pr ", i);
            Node* sparse = _preHead;
            Node* full = _preHead->next;
            while (full != _preHead)
            {
                if (sparse->nextJump[i] == full->next)
                {
                    printf("--> ");
                } else if (sparse->nextJump[i] == full)
                {
                    printf("%3d ", full->key);
                    sparse = sparse->nextJump[i];
                } else
                {
                    printf("--- ");
                }
                full = full->next;
            }
            printf("pr\n");
        }
        printf("-1 pr ");
        Node* curr = _preHead->next;
        while (curr != _preHead)
        {
            printf("%3d ", curr->key);
            curr = curr->next;
        }
        printf("pr\n");
        cout << endl;
    }


    string joinKeysToString()
    {
        stringstream ss;
        Node* curr = _preHead;
        while (curr->next != _preHead)
        {
            curr = curr->next;
            ss << curr->key << " ";
        }
        return ss.str().substr(0, ss.str().size() - 1);
    }

    string joinValuesToString()
    {
        stringstream ss;
        Node* curr = _preHead;
        while (curr->next != _preHead)
        {
            curr = curr->next;
            ss << curr->value << " ";
        }
        return ss.str().substr(0, ss.str().size() - 1);
    }
};


TEST(SkipList, simple)
{
    TestSkipList list();

//    TestSkipList list1(0.3);
//    TestSkipList list2(0.6);
//    for (int i = 0; i < 20; ++i)
//    {
//        list1.insert("val", i);
//        list2.insert("val", i);
//    }
//    cout << "list1" << endl;
//    list1.PRINT_REFS();
//    cout << "list2" << endl;
//    list2.PRINT_REFS();
//    list2.PRINT_VALUES();
//    list2.PRINT_KEYS();

}