selfSTLDRAFT

#include <iostream>
#include <algorithm>

template <typename T> bool sortUp(T a, T b)
{
    return a < b;
}

template <typename T> bool sortDown(T a, T b)
{
    return a > b;
}


template <typename T> void sort(T* begin, T* end, bool(*sortCrit)(T, T), void(*print)(T*, T*) = nullptr)
{
    if (print) print(begin, end);
    T tmp;
    for (T* head{ begin }; head != end; ++head)
    {
        for (T* tail{ end - 1 }; tail != head; --tail)
        {
            if (sortCrit(*tail, *head))
            {
                tmp = *tail;
                *tail = *head;
                *head = tmp;
                if (print) print(begin, end);
            }
        }

    }
    if (print) print(begin, end);
}

template <typename T>
void print(T* begin, T* end)
{
    while (begin != end)
    {
        std::cout << *begin++ << ' ';
    }
    std::cout << '\n';
}

template <typename T>
T* unique(T* begin, T* end)
{
    T* insertPos{ begin + 1 };
    for (; (insertPos != end) and (*insertPos != *(insertPos - 1)); ++insertPos);
    if (insertPos == end) return end;

    begin = insertPos + 1;
    while (begin != end)
    {
        if (*(insertPos - 1) != *begin)
        {
            *insertPos++ = *begin;
        }
        ++begin;
    }
    return insertPos;
}

template <typename T>
T* uniqualize(T* begin, T* end)
{
    sort(begin, end, sortUp<int>);
    return unique(begin, end);
}

template <typename T>
T* binSearch(T* begin, T* end, const T& key)
{
    T* left{ begin };
    T* right{ end - 1 };
    T* mid;
    while (true)
    {
        mid = left + ((right - left) / 2);
        if (key == *mid) { return mid; };
        if (key < *mid) { right = mid - 1; }
        if (key > * mid) { left = mid + 1; }
        if (left > right) { return end; };
    }
}

template <typename T, typename PredFunction>
T* leave_if(T* begin, T* end, PredFunction pred)
{
    T* insertPos{ begin };
    for (; (insertPos != end) and pred(*insertPos); ++insertPos);
    if (insertPos == end) return end;

    begin = insertPos + 1;
    while (begin != end)
    {
        if (pred(*begin))
        {
            *insertPos++ = *begin;
        }
        ++begin;
    }
    return insertPos;
}

template <typename T>
T* leave_if_ref(T* begin, T* end, T* beginRef, T* endRef, bool(*pred)(T*, T*, const T&))
{
    T* insertPos{ begin };
    for (; (insertPos != end) and pred(beginRef, endRef, *insertPos); ++insertPos);
    if (insertPos == end) return end;

    begin = insertPos + 1;
    while (begin != end)
    {
        if (pred(beginRef, endRef, *begin))
        {
            *insertPos++ = *begin;
        }
        ++begin;
    }
    return insertPos;
}

template <typename T>
T* remove_if_ref(T* begin, T* end, T* beginRef, T* endRef, bool(*pred)(T*, T*, const T&))
{
    T* insertPos{ begin };
    for (; (insertPos != end) and !pred(beginRef, endRef, *insertPos); ++insertPos);
    if (insertPos == end) return end;

    begin = insertPos + 1;
    while (begin != end)
    {
        if (!pred(beginRef, endRef, *begin))
        {
            *insertPos++ = *begin;
        }
        ++begin;
    }
    return insertPos;
}

template <typename T>
T* merge(T* beginA, T* endA, T* beginB, T* endB, T* beginDest)
{
    while (beginA != endA and beginB != endB)
    {
        *beginDest++ = *beginA < *beginB ? *beginA++ : *beginB++;
    }
    while (beginA != endA)
    {
        *beginDest++ = *beginA++;
    }
    while (beginB != endB)
    {
        *beginDest++ = *beginB++;
    }
    return beginDest;
}

template <typename T>
bool notIn(T* begin, T* end, const T& el)
{
    return (binSearch(begin, end, el) == end);
}

template <typename T>
bool isIn(T* begin, T* end, const T& el)
{
    return (binSearch(begin, end, el) != end);
}

template <typename T>
size_t distance(T* begin, T* end)
{
    return end - begin;
}

template <typename T>
T* dedup(T* begin, T* end)
{
    T* next{ begin };
    ++next;
    T* out{ begin };

    while (begin != end)
    {
        if (*begin != *next)
        {
            *out++ = *begin++;
            ++next;
        }
        else
        {
            begin+=2;
            next+=2;
        }
    }
    return out;
}

int main()
{
    const int arrASize{ 15 };
    const int arrBSize{ 15 };
    int arrA[arrASize] = { 6,1,4,2,8,9,11,26,2,7,8,11,2,2,3 };
    int arrB[arrBSize] = { 1,8,29,2,2,9,11,1,2,5,8,34,12,9,8 };


    print(arrA, arrA + arrASize);
    print(arrB, arrB + arrBSize);
    int* uniqueAPos{ uniqualize(arrA, arrA + arrASize) };
    int* uniqueBPos{ uniqualize(arrB, arrB + arrBSize) };
    print(arrA, uniqueAPos);
    print(arrB, uniqueBPos);

    int* mergeAB{ new int[distance(arrA,uniqueAPos) + distance(arrB,uniqueBPos)] };
    int* mergePos{ merge(arrA, uniqueAPos,arrB, uniqueBPos, mergeAB) };
    print(mergeAB, mergePos);
    int* dedupPos{ dedup(mergeAB, mergePos)};
    print(mergeAB, dedupPos);

    //int* resAPos { leave_if(arrA, uniqueAPos, [arrB, uniqueBPos](int& el) {return (binSearch((int*)arrB, uniqueBPos, el) == uniqueBPos); }) };
    //int* resAPos{ remove_if_ref(arrA, uniqueAPos, arrB, uniqueBPos, isIn<int>) };
    //int* resAPos{ leave_if_ref(arrA, uniqueAPos, arrB, uniqueBPos, isIn<int>) };
    //print(arrA, resAPos);
    delete[] mergeAB;
}