Restoring authorship annotation for Anton Samokhvalov <pg83@yandex.ru>. Commit 1 of 2.

1 files changed, 168 insertions, 168 deletions

diff --git a/library/cpp/lcs/lcs_via_lis.h b/library/cpp/lcs/lcs_via_lis.h
index d26733d94e..a227b01268 100644
--- a/library/cpp/lcs/lcs_via_lis.h
+++ b/library/cpp/lcs/lcs_via_lis.h
@@ -1,193 +1,193 @@
 #pragma once
 
 #include <library/cpp/containers/paged_vector/paged_vector.h>
-
+ 
 #include <util/generic/ptr.h>
 #include <util/generic/hash.h>
 #include <util/generic/vector.h>
-#include <util/generic/algorithm.h>
+#include <util/generic/algorithm.h> 
 #include <util/memory/pool.h>
 
 namespace NLCS {
-    template <typename TVal>
-    struct TLCSCtx {
+    template <typename TVal> 
+    struct TLCSCtx { 
         typedef TVector<ui32> TSubsequence;
         typedef THashMap<TVal, TSubsequence, THash<TVal>, TEqualTo<TVal>, ::TPoolAllocator> TEncounterIndex;
         typedef TVector<std::pair<ui32, ui32>> TLastIndex;
-        typedef NPagedVector::TPagedVector<TSubsequence, 4096> TCover;
-
-        TMemoryPool Pool;
-        THolder<TEncounterIndex> Encounters;
-        TLastIndex LastIndex;
-        TCover Cover;
-
-        TSubsequence ResultBuffer;
-
-        TLCSCtx()
-            : Pool(16 * 1024 - 64, TMemoryPool::TExpGrow::Instance())
-        {
-            Reset();
-        }
-
-        void Reset() {
-            Encounters.Reset(nullptr);
-            Pool.Clear();
-            Encounters.Reset(new TEncounterIndex(&Pool));
-            LastIndex.clear();
-            Cover.clear();
-            ResultBuffer.clear();
-        }
-    };
-
-    namespace NPrivate {
-        template <typename TIt, typename TVl>
-        struct TSequence {
-            typedef TIt TIter;
-            typedef TVl TVal;
-
-            const TIter Begin;
-            const TIter End;
-            const size_t Size;
-
-            TSequence(TIter beg, TIter end)
-                : Begin(beg)
-                , End(end)
-                , Size(end - beg)
-            {
-            }
-        };
-
-        template <typename TVal, typename TSequence, typename TResult>
-        size_t MakeLCS(TSequence s1, TSequence s2, TResult* res = nullptr, TLCSCtx<TVal>* ctx = nullptr) {
-            typedef TLCSCtx<TVal> TCtx;
-
-            THolder<TCtx> ctxhld;
-
-            if (!ctx) {
-                ctxhld.Reset(new TCtx());
-                ctx = ctxhld.Get();
-            } else {
-                ctx->Reset();
-            }
-
-            size_t maxsize = Max(s1.Size, s2.Size);
-            auto& index = *(ctx->Encounters);
-
-            for (auto it = s1.Begin; it != s1.End; ++it) {
-                index[*it];
-            }
-
-            for (auto it = s2.Begin; it != s2.End; ++it) {
-                auto hit = index.find(*it);
-
-                if (hit != index.end()) {
-                    hit->second.push_back(it - s2.Begin);
-                }
-            }
-
-            if (!res) {
-                auto& lastindex = ctx->ResultBuffer;
-                lastindex.reserve(maxsize);
-
-                for (auto it1 = s1.Begin; it1 != s1.End; ++it1) {
-                    const auto& sub2 = index[*it1];
-
-                    for (auto it2 = sub2.rbegin(); it2 != sub2.rend(); ++it2) {
-                        ui32 x = *it2;
-
-                        auto lit = LowerBound(lastindex.begin(), lastindex.end(), x);
-
-                        if (lit == lastindex.end()) {
-                            lastindex.push_back(x);
-                        } else {
-                            *lit = x;
-                        }
-                    }
+        typedef NPagedVector::TPagedVector<TSubsequence, 4096> TCover; 
+
+        TMemoryPool Pool; 
+        THolder<TEncounterIndex> Encounters; 
+        TLastIndex LastIndex; 
+        TCover Cover; 
+
+        TSubsequence ResultBuffer; 
+
+        TLCSCtx() 
+            : Pool(16 * 1024 - 64, TMemoryPool::TExpGrow::Instance()) 
+        { 
+            Reset(); 
+        } 
+
+        void Reset() { 
+            Encounters.Reset(nullptr); 
+            Pool.Clear(); 
+            Encounters.Reset(new TEncounterIndex(&Pool)); 
+            LastIndex.clear(); 
+            Cover.clear(); 
+            ResultBuffer.clear(); 
+        } 
+    }; 
+
+    namespace NPrivate { 
+        template <typename TIt, typename TVl> 
+        struct TSequence { 
+            typedef TIt TIter; 
+            typedef TVl TVal; 
+
+            const TIter Begin; 
+            const TIter End; 
+            const size_t Size; 
+
+            TSequence(TIter beg, TIter end) 
+                : Begin(beg) 
+                , End(end) 
+                , Size(end - beg) 
+            { 
+            } 
+        }; 
+
+        template <typename TVal, typename TSequence, typename TResult> 
+        size_t MakeLCS(TSequence s1, TSequence s2, TResult* res = nullptr, TLCSCtx<TVal>* ctx = nullptr) { 
+            typedef TLCSCtx<TVal> TCtx; 
+
+            THolder<TCtx> ctxhld; 
+
+            if (!ctx) { 
+                ctxhld.Reset(new TCtx()); 
+                ctx = ctxhld.Get(); 
+            } else { 
+                ctx->Reset(); 
+            } 
+
+            size_t maxsize = Max(s1.Size, s2.Size); 
+            auto& index = *(ctx->Encounters); 
+
+            for (auto it = s1.Begin; it != s1.End; ++it) { 
+                index[*it]; 
+            } 
+
+            for (auto it = s2.Begin; it != s2.End; ++it) { 
+                auto hit = index.find(*it); 
+
+                if (hit != index.end()) { 
+                    hit->second.push_back(it - s2.Begin); 
+                } 
+            } 
+
+            if (!res) { 
+                auto& lastindex = ctx->ResultBuffer; 
+                lastindex.reserve(maxsize); 
+ 
+                for (auto it1 = s1.Begin; it1 != s1.End; ++it1) { 
+                    const auto& sub2 = index[*it1]; 
+
+                    for (auto it2 = sub2.rbegin(); it2 != sub2.rend(); ++it2) { 
+                        ui32 x = *it2; 
+
+                        auto lit = LowerBound(lastindex.begin(), lastindex.end(), x); 
+ 
+                        if (lit == lastindex.end()) { 
+                            lastindex.push_back(x); 
+                        } else { 
+                            *lit = x; 
+                        } 
+                    } 
+                } 
+
+                return lastindex.size(); 
+            } else { 
+                auto& lastindex = ctx->LastIndex; 
+                auto& cover = ctx->Cover; 
+ 
+                lastindex.reserve(maxsize); 
+
+                for (auto it1 = s1.Begin; it1 != s1.End; ++it1) { 
+                    const auto& sub2 = index[*it1]; 
+
+                    for (auto it2 = sub2.rbegin(); it2 != sub2.rend(); ++it2) { 
+                        ui32 x = *it2; 
+
+                        auto lit = LowerBound(lastindex.begin(), lastindex.end(), std::make_pair(x, (ui32)0u)); 
+
+                        if (lit == lastindex.end()) { 
+                            lastindex.push_back(std::make_pair(x, cover.size())); 
+                            cover.emplace_back(); 
+                            cover.back().push_back(x); 
+                        } else { 
+                            *lit = std::make_pair(x, lit->second); 
+                            cover[lit->second].push_back(x); 
+                        } 
+                    } 
                 }
 
-                return lastindex.size();
-            } else {
-                auto& lastindex = ctx->LastIndex;
-                auto& cover = ctx->Cover;
-
-                lastindex.reserve(maxsize);
-
-                for (auto it1 = s1.Begin; it1 != s1.End; ++it1) {
-                    const auto& sub2 = index[*it1];
-
-                    for (auto it2 = sub2.rbegin(); it2 != sub2.rend(); ++it2) {
-                        ui32 x = *it2;
-
-                        auto lit = LowerBound(lastindex.begin(), lastindex.end(), std::make_pair(x, (ui32)0u));
-
-                        if (lit == lastindex.end()) {
-                            lastindex.push_back(std::make_pair(x, cover.size()));
-                            cover.emplace_back();
-                            cover.back().push_back(x);
-                        } else {
-                            *lit = std::make_pair(x, lit->second);
-                            cover[lit->second].push_back(x);
-                        }
-                    }
-                }
-
-                if (cover.empty()) {
-                    return 0;
-                }
-
-                std::reverse(cover.begin(), cover.end());
-
-                auto& resbuf = ctx->ResultBuffer;
-
-                resbuf.push_back(cover.front().front());
-
-                for (auto it = cover.begin() + 1; it != cover.end(); ++it) {
-                    auto pit = UpperBound(it->begin(), it->end(), resbuf.back(), std::greater<ui32>());
-
-                    Y_VERIFY(pit != it->end(), " ");
-
-                    resbuf.push_back(*pit);
-                }
-
-                std::reverse(resbuf.begin(), resbuf.end());
-
-                for (auto it = resbuf.begin(); it != resbuf.end(); ++it) {
-                    res->push_back(*(s2.Begin + *it));
-                }
-
-                return lastindex.size();
-            }
-        }
+                if (cover.empty()) { 
+                    return 0; 
+                } 
+
+                std::reverse(cover.begin(), cover.end()); 
+
+                auto& resbuf = ctx->ResultBuffer; 
+
+                resbuf.push_back(cover.front().front()); 
+ 
+                for (auto it = cover.begin() + 1; it != cover.end(); ++it) { 
+                    auto pit = UpperBound(it->begin(), it->end(), resbuf.back(), std::greater<ui32>()); 
+ 
+                    Y_VERIFY(pit != it->end(), " "); 
+ 
+                    resbuf.push_back(*pit); 
+                } 
+
+                std::reverse(resbuf.begin(), resbuf.end()); 
+
+                for (auto it = resbuf.begin(); it != resbuf.end(); ++it) { 
+                    res->push_back(*(s2.Begin + *it)); 
+                } 
+ 
+                return lastindex.size(); 
+            } 
+        } 
     }
 
-    template <typename TVal, typename TIter, typename TResult>
-    size_t MakeLCS(TIter beg1, TIter end1, TIter beg2, TIter end2, TResult* res = nullptr, TLCSCtx<TVal>* ctx = nullptr) {
-        typedef NPrivate::TSequence<TIter, TVal> TSeq;
+    template <typename TVal, typename TIter, typename TResult> 
+    size_t MakeLCS(TIter beg1, TIter end1, TIter beg2, TIter end2, TResult* res = nullptr, TLCSCtx<TVal>* ctx = nullptr) { 
+        typedef NPrivate::TSequence<TIter, TVal> TSeq; 
 
-        size_t sz1 = end1 - beg1;
-        size_t sz2 = end2 - beg2;
+        size_t sz1 = end1 - beg1; 
+        size_t sz2 = end2 - beg2; 
 
-        if (sz2 > sz1) {
-            DoSwap(beg1, beg2);
-            DoSwap(end1, end2);
-            DoSwap(sz1, sz2);
-        }
+        if (sz2 > sz1) { 
+            DoSwap(beg1, beg2); 
+            DoSwap(end1, end2); 
+            DoSwap(sz1, sz2); 
+        } 
 
-        return NPrivate::MakeLCS<TVal>(TSeq(beg1, end1), TSeq(beg2, end2), res, ctx);
+        return NPrivate::MakeLCS<TVal>(TSeq(beg1, end1), TSeq(beg2, end2), res, ctx); 
     }
 
-    template <typename TVal, typename TColl, typename TRes>
-    size_t MakeLCS(const TColl& coll1, const TColl& coll2, TRes* res = nullptr, TLCSCtx<TVal>* ctx = nullptr) {
-        return MakeLCS<TVal>(coll1.begin(), coll1.end(), coll2.begin(), coll2.end(), res, ctx);
-    }
+    template <typename TVal, typename TColl, typename TRes> 
+    size_t MakeLCS(const TColl& coll1, const TColl& coll2, TRes* res = nullptr, TLCSCtx<TVal>* ctx = nullptr) { 
+        return MakeLCS<TVal>(coll1.begin(), coll1.end(), coll2.begin(), coll2.end(), res, ctx); 
+    } 
 
-    template <typename TVal, typename TIter>
-    size_t MeasureLCS(TIter beg1, TIter end1, TIter beg2, TIter end2, TLCSCtx<TVal>* ctx = nullptr) {
+    template <typename TVal, typename TIter> 
+    size_t MeasureLCS(TIter beg1, TIter end1, TIter beg2, TIter end2, TLCSCtx<TVal>* ctx = nullptr) { 
         return MakeLCS<TVal>(beg1, end1, beg2, end2, (TVector<TVal>*)nullptr, ctx);
-    }
+    } 
 
-    template <typename TVal, typename TColl>
-    size_t MeasureLCS(const TColl& coll1, const TColl& coll2, TLCSCtx<TVal>* ctx = nullptr) {
-        return MeasureLCS<TVal>(coll1.begin(), coll1.end(), coll2.begin(), coll2.end(), ctx);
-    }
+    template <typename TVal, typename TColl> 
+    size_t MeasureLCS(const TColl& coll1, const TColl& coll2, TLCSCtx<TVal>* ctx = nullptr) { 
+        return MeasureLCS<TVal>(coll1.begin(), coll1.end(), coll2.begin(), coll2.end(), ctx); 
+    } 
 }