#include <library/cpp/actors/util/rope.h>
#include <library/cpp/testing/unittest/registar.h>
#include <util/random/random.h>

#include "shared_data_rope_backend.h"

namespace NActors {

    namespace {

        TRope CreateRope(TString s, size_t sliceSize) {
            TRope res;
            for (size_t i = 0; i < s.size(); ) {
                size_t len = std::min(sliceSize, s.size() - i);
                if (i % 2) {
                    auto str = s.substr(i, len);
                    res.Insert(res.End(), TRope(MakeIntrusive<TRopeSharedDataBackend>(
                        TSharedData::Copy(str.data(), str.size()))));
                } else {
                    res.Insert(res.End(), TRope(s.substr(i, len)));
                }
                i += len;
            }
            return res;
        }

        TString RopeToString(const TRope& rope) {
            TString res;
            auto iter = rope.Begin();
            while (iter != rope.End()) {
                res.append(iter.ContiguousData(), iter.ContiguousSize());
                iter.AdvanceToNextContiguousBlock();
            }

            UNIT_ASSERT_VALUES_EQUAL(rope.GetSize(), res.size());

            TString temp = TString::Uninitialized(rope.GetSize());
            rope.Begin().ExtractPlainDataAndAdvance(temp.Detach(), temp.size());
            UNIT_ASSERT_VALUES_EQUAL(temp, res);

            return res;
        }

        TString Text = "No elements are copied or moved, only the internal pointers of the list nodes are re-pointed.";

    }

    Y_UNIT_TEST_SUITE(TRopeSharedDataBackend) {

        // Same tests as in TRope but with new CreateRope using TSharedData backend

        Y_UNIT_TEST(Leak) {
            const size_t begin = 10, end = 20;
            TRope rope = CreateRope(Text, 10);
            rope.Erase(rope.Begin() + begin, rope.Begin() + end);
        }

        Y_UNIT_TEST(BasicRange) {
            TRope rope = CreateRope(Text, 10);
            for (size_t begin = 0; begin < Text.size(); ++begin) {
                for (size_t end = begin; end <= Text.size(); ++end) {
                    TRope::TIterator rBegin = rope.Begin() + begin;
                    TRope::TIterator rEnd = rope.Begin() + end;
                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(TRope(rBegin, rEnd)), Text.substr(begin, end - begin));
                }
            }
        }

        Y_UNIT_TEST(Erase) {
            for (size_t begin = 0; begin < Text.size(); ++begin) {
                for (size_t end = begin; end <= Text.size(); ++end) {
                    TRope rope = CreateRope(Text, 10);
                    rope.Erase(rope.Begin() + begin, rope.Begin() + end);
                    TString text = Text;
                    text.erase(text.begin() + begin, text.begin() + end);
                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), text);
                }
            }
        }

        Y_UNIT_TEST(Insert) {
            TRope rope = CreateRope(Text, 10);
            for (size_t begin = 0; begin < Text.size(); ++begin) {
                for (size_t end = begin; end <= Text.size(); ++end) {
                    TRope part = TRope(rope.Begin() + begin, rope.Begin() + end);
                    for (size_t where = 0; where <= Text.size(); ++where) {
                        TRope x(rope);
                        x.Insert(x.Begin() + where, TRope(part));
                        UNIT_ASSERT_VALUES_EQUAL(x.GetSize(), rope.GetSize() + part.GetSize());
                        TString text = Text;
                        text.insert(text.begin() + where, Text.begin() + begin, Text.begin() + end);
                        UNIT_ASSERT_VALUES_EQUAL(RopeToString(x), text);
                    }
                }
            }
        }

        Y_UNIT_TEST(Extract) {
            for (size_t begin = 0; begin < Text.size(); ++begin) {
                for (size_t end = begin; end <= Text.size(); ++end) {
                    TRope rope = CreateRope(Text, 10);
                    TRope part = rope.Extract(rope.Begin() + begin, rope.Begin() + end);
                    TString text = Text;
                    text.erase(text.begin() + begin, text.begin() + end);
                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), text);
                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(part), Text.substr(begin, end - begin));
                }
            }
        }

        Y_UNIT_TEST(EraseFront) {
            for (size_t pos = 0; pos <= Text.size(); ++pos) {
                TRope rope = CreateRope(Text, 10);
                rope.EraseFront(pos);
                UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text.substr(pos));
            }
        }

        Y_UNIT_TEST(EraseBack) {
            for (size_t pos = 0; pos <= Text.size(); ++pos) {
                TRope rope = CreateRope(Text, 10);
                rope.EraseBack(pos);
                UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text.substr(0, Text.size() - pos));
            }
        }

        Y_UNIT_TEST(ExtractFront) {
            for (size_t step = 1; step <= Text.size(); ++step) {
                TRope rope = CreateRope(Text, 10);
                TRope out;
                while (const size_t len = Min(step, rope.GetSize())) {
                    rope.ExtractFront(len, &out);
                    UNIT_ASSERT(rope.GetSize() + out.GetSize() == Text.size());
                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(out), Text.substr(0, out.GetSize()));
                }
            }
        }

        Y_UNIT_TEST(ExtractFrontPlain) {
            for (size_t step = 1; step <= Text.size(); ++step) {
                TRope rope = CreateRope(Text, 10);
                TString buffer = Text;
                auto it = rope.Begin();
                size_t remain = rope.GetSize();
                while (const size_t len = Min(step, remain)) {
                    TString data = TString::Uninitialized(len);
                    it.ExtractPlainDataAndAdvance(data.Detach(), data.size());
                    UNIT_ASSERT_VALUES_EQUAL(data, buffer.substr(0, len));
                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(TRope(it, rope.End())), buffer.substr(len));
                    buffer = buffer.substr(len);
                    remain -= len;
                }
            }
        }

        Y_UNIT_TEST(Glueing) {
            TRope rope = CreateRope(Text, 10);
            for (size_t begin = 0; begin <= Text.size(); ++begin) {
                for (size_t end = begin; end <= Text.size(); ++end) {
                    TString repr = rope.DebugString();
                    TRope temp = rope.Extract(rope.Position(begin), rope.Position(end));
                    rope.Insert(rope.Position(begin), std::move(temp));
                    UNIT_ASSERT_VALUES_EQUAL(repr, rope.DebugString());
                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text);
                }
            }
        }

        Y_UNIT_TEST(IterWalk) {
            TRope rope = CreateRope(Text, 10);
            for (size_t step1 = 0; step1 <= rope.GetSize(); ++step1) {
                for (size_t step2 = 0; step2 <= step1; ++step2) {
                    TRope::TConstIterator iter = rope.Begin();
                    iter += step1;
                    iter -= step2;
                    UNIT_ASSERT(iter == rope.Position(step1 - step2));
                }
            }
        }

        Y_UNIT_TEST(Compare) {
            auto check = [](const TString& x, const TString& y) {
                const TRope xRope = CreateRope(x, 7);
                const TRope yRope = CreateRope(y, 11);
                UNIT_ASSERT_VALUES_EQUAL(xRope == yRope, x == y);
                UNIT_ASSERT_VALUES_EQUAL(xRope != yRope, x != y);
                UNIT_ASSERT_VALUES_EQUAL(xRope <  yRope, x <  y);
                UNIT_ASSERT_VALUES_EQUAL(xRope <= yRope, x <= y);
                UNIT_ASSERT_VALUES_EQUAL(xRope >  yRope, x >  y);
                UNIT_ASSERT_VALUES_EQUAL(xRope >= yRope, x >= y);
            };

            TVector<TString> pool;
            for (size_t k = 0; k < 10; ++k) {
                size_t len = RandomNumber<size_t>(100) + 100;
                TString s = TString::Uninitialized(len);
                char *p = s.Detach();
                for (size_t j = 0; j < len; ++j) {
                    *p++ = RandomNumber<unsigned char>();
                }
                pool.push_back(std::move(s));
            }

            for (const TString& x : pool) {
                for (const TString& y : pool) {
                    check(x, y);
                }
            }
        }

        // Specific TSharedDataRopeBackend tests

        Y_UNIT_TEST(RopeOnlyBorrows) {
            TSharedData data = TSharedData::Copy(Text.data(), Text.size());
            {
                TRope rope;
                rope.Insert(rope.End(), TRope(MakeIntrusive<TRopeSharedDataBackend>(data)));
                UNIT_ASSERT(data.IsShared());
                TSharedData dataCopy = data;
                UNIT_ASSERT(dataCopy.IsShared());
                UNIT_ASSERT_EQUAL(dataCopy.data(), data.data());
                rope.Insert(rope.End(), TRope(MakeIntrusive<TRopeSharedDataBackend>(data)));
                rope.Insert(rope.End(), TRope(MakeIntrusive<TRopeSharedDataBackend>(data)));
                dataCopy.Trim(10);
                UNIT_ASSERT_EQUAL(rope.GetSize(), data.size() * 3);
            }
            UNIT_ASSERT(data.IsPrivate());
        }
    }

} // namespace NActors