#include "stdafx.h"
#include <Windows.h>
#include <time.h>
#include <vector>
#include <algorithm>
#include <set>

struct STreeLeaf
{
    int m_nData;
    size_t m_nLeftIdx;
    size_t m_nRightIdx;

    STreeLeaf(int nData = 0) : m_nData(nData), m_nLeftIdx(0), m_nRightIdx(0) {}
};

int main()
{

    int nAddCnt = 10000000;

    std::vector<STreeLeaf> vecIdx1;
    vecIdx1.reserve(nAddCnt);
    std::vector<int> vecIdx2;
    vecIdx2.reserve(nAddCnt);
    std::set<int> setIdx;

    int nMinIterCnt = 0, nMaxIterCnt = 0, nTotalIterCnt = 0;
    srand(0);
    unsigned t0 = GetTickCount();
    for (int i = 0; i < nAddCnt; i++)
    {
        int nData = (rand() << 15) | rand();
        int nIterCnt = 1;
        STreeLeaf sLeaf(nData);
        if (vecIdx1.empty())
        {
            vecIdx1.push_back(sLeaf);
        }
        else
        {
            size_t nCurIdx = 0;
            size_t nIdxMax = vecIdx1.size() - 1;
            for(;;)
            {
                STreeLeaf& sCurLeaf = vecIdx1[nCurIdx];
                size_t nNextLeafIdx = nData < sCurLeaf.m_nData ? sCurLeaf.m_nLeftIdx : sCurLeaf.m_nRightIdx;
                if (!nNextLeafIdx)
                {
                    vecIdx1.push_back(sLeaf);
                    STreeLeaf& sCurLeaf = vecIdx1[nCurIdx];
                    size_t& nNextLeafIdx = nData < sCurLeaf.m_nData ? sCurLeaf.m_nLeftIdx : sCurLeaf.m_nRightIdx;
                    nNextLeafIdx = nIdxMax + 1;
                    break;
                }
                nCurIdx = nNextLeafIdx;
                nIterCnt++;
            }
        }
        if (!i || nMinIterCnt > nIterCnt) nMinIterCnt = nIterCnt;
        if (!i || nMaxIterCnt < nIterCnt) nMaxIterCnt = nIterCnt;
        nTotalIterCnt += nIterCnt;
    }
    unsigned t1 = GetTickCount();

    printf("B-Tree insert. Index size: %d, min iter cnt: %d, max iter cnt: %d, total iter cnt: %d, time estimated: %d ms\r\n", nAddCnt, nMinIterCnt, nMaxIterCnt, nTotalIterCnt, t1 - t0);

    srand(0);
    t0 = GetTickCount();
    for (int i = 0; i < nAddCnt; i++)
    {
        int nData = (rand() << 15) | rand();
        vecIdx2.push_back(nData);
    }
    std::stable_sort(vecIdx2.begin(), vecIdx2.end());
    t1 = GetTickCount();

    printf("Array insert+final sort. Index size: %d, time estimated: %d ms\r\n", nAddCnt, t1 - t0);

    srand(0);
    t0 = GetTickCount();
    int nAddCnt2 = 10;
    for (int i = 0; i < nAddCnt2; i++)
    {
        int nData = (rand() << 15) | rand();
        vecIdx2.push_back(nData);
        std::stable_sort(vecIdx2.begin(), vecIdx2.end());
    }
    t1 = GetTickCount();

    printf("Array insert+sort. Index size: %d, intem inserted: %d, time estimated: %d ms\r\n", nAddCnt, nAddCnt2, t1 - t0);

    srand(0);
    t0 = GetTickCount();
    for (int i = 0; i < nAddCnt; i++)
    {
        int nData = (rand() << 15) | rand();
        setIdx.insert(nData);
    }
    t1 = GetTickCount();

    printf("std::set insert. Index size: %d, time estimated: %d ms\r\n", nAddCnt, t1 - t0);

    nMinIterCnt = 0, nMaxIterCnt = 0, nTotalIterCnt = 0;
    srand(1000);
    t0 = GetTickCount();
    for (int i = 0; i < nAddCnt; i++)
    {
        int nData = (rand() << 15) | rand();
        int nIterCnt = 1;
        STreeLeaf sLeaf(nData);
        if (vecIdx1.empty())
        {
            vecIdx1.push_back(sLeaf);
        }
        else
        {
            size_t nCurIdx = 0;
            size_t nIdxMax = vecIdx1.size();
            for (;;)
            {
                STreeLeaf& sCurLeaf = vecIdx1[nCurIdx];
                if (sCurLeaf.m_nData == nData) break;
                size_t& nNextLeafIdx = nData < sCurLeaf.m_nData ? sCurLeaf.m_nLeftIdx : sCurLeaf.m_nRightIdx;
                if (!nNextLeafIdx) break;
                nCurIdx = nNextLeafIdx;
                nIterCnt++;
            }
        }
        if (!i || nMinIterCnt > nIterCnt) nMinIterCnt = nIterCnt;
        if (!i || nMaxIterCnt < nIterCnt) nMaxIterCnt = nIterCnt;
        nTotalIterCnt += nIterCnt;
    }
    t1 = GetTickCount();

    printf("B-Tree search. Values searched: %d, min iter cnt: %d, max iter cnt: %d, total iter cnt: %d, time estimated: %d ms\r\n", nAddCnt, nMinIterCnt, nMaxIterCnt, nTotalIterCnt, t1 - t0);

    nMinIterCnt = 0, nMaxIterCnt = 0, nTotalIterCnt = 0;
    srand(1000);
    t0 = GetTickCount();
    for (int i = 0; i < nAddCnt; i++)
    {
        int nData = (rand() << 15) | rand();

        int nIterCnt = 1;

        size_t nIdxMin = 0;
        size_t nIdxMax = vecIdx2.size() - 1;
        if (nData < vecIdx2[nIdxMin] || nData > vecIdx2[nIdxMax]) continue;

        while (nIdxMin != nIdxMax)
        {
            size_t nIdx = nIdxMin + (nIdxMax - nIdxMin) / 2;
            int nCurData = vecIdx2[nIdx];
            if (nCurData == nData) break;
            if (nIdx == nIdxMin)
            {
                nIdx++;
                // Или нашли или нет, в любом случае выход из поиска
                break;
            }
            if (nCurData > nData) nIdxMax = nIdx;
            else nIdxMin = nIdx;
            nIterCnt++;
        }
        if (!i || nMinIterCnt > nIterCnt) nMinIterCnt = nIterCnt;
        if (!i || nMaxIterCnt < nIterCnt) nMaxIterCnt = nIterCnt;
        nTotalIterCnt += nIterCnt;
    }
    t1 = GetTickCount();

    printf("Interval search. Values searched: %d, min iter cnt: %d, max iter cnt: %d, total iter cnt: %d, time estimated: %d ms\r\n", nAddCnt, nMinIterCnt, nMaxIterCnt, nTotalIterCnt, t1 - t0);

    nMinIterCnt = 0, nMaxIterCnt = 0, nTotalIterCnt = 0;
    srand(1000);
    t0 = GetTickCount();
    for (int i = 0; i < nAddCnt; i++)
    {
        int nData = (rand() << 15) | rand();
        auto ix = setIdx.find(nData);
        if (ix == setIdx.end()) continue;
        else continue; // vecIdx1[i] = *ix;
    }
    t1 = GetTickCount();

    printf("std::set search. Values searched: %d, time estimated: %d ms\r\n", nAddCnt, t1 - t0);

    getchar();

    return 0;
}