#include "ordered_set.h"
#include <algorithm>

using namespace std;

OrderedSet::OrderedSet() : start_(0) {}

OrderedSet::OrderedSet(size_t size) : Set(size), start_(0) {}

OrderedSet::OrderedSet(const Set& other) : Set(other), start_(0)
{
    SortIntern();
}

OrderedSet::OrderedSet(Set&& other) : Set(move(other)), start_(0)
{
    SortIntern();
}

OrderedSet::OrderedSet(const OrderedSet& other) : Set(other), start_(other.start_){}

OrderedSet::OrderedSet(OrderedSet&& other) noexcept : Set(move(other))
{
    start_ = other.start_;
    other.start_ = 0;
}

OrderedSet::OrderedSet(const std::initializer_list<int>& list) : Set(list), start_(0)
{
    SortIntern();
}

void OrderedSet::SortIntern()
{
    sort(begin(), begin() + size_);
}

OrderedSet OrderedSet::GetSmaller(int x) const
{
    OrderedSet result(*this);
    size_t i = 0;
    while (i < size() && begin()[i] < x) ++i;
    result.size_ = i;
    return result;
}


OrderedSet OrderedSet::GetLarger(int x) const
{
    OrderedSet result(*this);
    size_t i = 0;
    while (i < size() && begin()[i] <= x) ++i;
    result.size_ = size_ - i;
    result.start_ = i;
    return result;
}

Set OrderedSet::Merge(const Set& other) const
{
    if (const auto* ordered = dynamic_cast<const OrderedSet*>(&other))
    {
        OrderedSet result(size() + ordered->size());
        auto* a = begin();
        auto* b = ordered->begin();
        auto* endA = a + size();
        auto* endB =b + other.size();
        while(a < endA && b < endB)
        {
            const int val1 = *a;
            const int val2 = *b;
            int val = 0;
            if (val1 <= val2)
            {
                ++a;
                val = val1;
            } else
            {
                ++b;
                val = val2;
            }
            if (!result.Contains(val)) {
                result.AddUnchecked(val);
            }
        }
        if (a < endA)
        {
            for (; a < endA; ++a) {
                if (!result.Contains(*a)) result.AddUnchecked(*a);
            }
        } else if (b < endB)
        {
            for (; b < endB; ++b) {
                if (!result.Contains(*b)) result.AddUnchecked(*b);
            }
        }
        return static_cast<Set>(result);
    }
    return Set::Merge(other);
}