Restoring authorship annotation for Anton Samokhvalov <[email protected]>. Commit 1 of 2.

1 files changed, 426 insertions, 426 deletions

diff --git a/library/cpp/containers/comptrie/make_fast_layout.cpp b/library/cpp/containers/comptrie/make_fast_layout.cpp
index ade78d78994..693384ee7f6 100644
--- a/library/cpp/containers/comptrie/make_fast_layout.cpp
+++ b/library/cpp/containers/comptrie/make_fast_layout.cpp
@@ -24,444 +24,444 @@
 // (there is not much difference between these papers, actually).
 //
 namespace NCompactTrie {
-    static size_t FindSupportingPowerOf2(size_t n) {
-        size_t result = 1ull << (8 * sizeof(size_t) - 1);
-        while (result > n) {
-            result >>= 1;
-        }
-        return result;
+    static size_t FindSupportingPowerOf2(size_t n) { 
+        size_t result = 1ull << (8 * sizeof(size_t) - 1); 
+        while (result > n) { 
+            result >>= 1; 
+        } 
+        return result; 
     }
 
-    namespace {
-        class TTrieNodeSet {
-        public:
+    namespace { 
+        class TTrieNodeSet { 
+        public: 
             TTrieNodeSet() = default;
 
-            explicit TTrieNodeSet(const TOpaqueTrie& trie)
-                : Body(trie.Length / (8 * MinNodeSize) + 1, 0)
-            {
-            }
-
-            bool Has(size_t offset) const {
-                const size_t reducedOffset = ReducedOffset(offset);
-                return OffsetCell(reducedOffset) & OffsetMask(reducedOffset);
-            }
-
-            void Add(size_t offset) {
-                const size_t reducedOffset = ReducedOffset(offset);
-                OffsetCell(reducedOffset) |= OffsetMask(reducedOffset);
-            }
-
-            void Remove(size_t offset) {
-                const size_t reducedOffset = ReducedOffset(offset);
-                OffsetCell(reducedOffset) &= ~OffsetMask(reducedOffset);
-            }
-
-            void Swap(TTrieNodeSet& other) {
-                Body.swap(other.Body);
-            }
-
-        private:
-            static const size_t MinNodeSize = 2;
-            TVector<ui8> Body;
-
-            static size_t ReducedOffset(size_t offset) {
-                return offset / MinNodeSize;
-            }
-            static ui8 OffsetMask(size_t reducedOffset) {
-                return 1 << (reducedOffset % 8);
-            }
-            ui8& OffsetCell(size_t reducedOffset) {
-                return Body.at(reducedOffset / 8);
-            }
-            const ui8& OffsetCell(size_t reducedOffset) const {
-                return Body.at(reducedOffset / 8);
-            }
-        };
-
-        //---------------------------------------------------------------------
-
-        class TTrieNodeCounts {
-        public:
+            explicit TTrieNodeSet(const TOpaqueTrie& trie) 
+                : Body(trie.Length / (8 * MinNodeSize) + 1, 0) 
+            { 
+            } 
+
+            bool Has(size_t offset) const { 
+                const size_t reducedOffset = ReducedOffset(offset); 
+                return OffsetCell(reducedOffset) & OffsetMask(reducedOffset); 
+            } 
+
+            void Add(size_t offset) { 
+                const size_t reducedOffset = ReducedOffset(offset); 
+                OffsetCell(reducedOffset) |= OffsetMask(reducedOffset); 
+            } 
+
+            void Remove(size_t offset) { 
+                const size_t reducedOffset = ReducedOffset(offset); 
+                OffsetCell(reducedOffset) &= ~OffsetMask(reducedOffset); 
+            } 
+
+            void Swap(TTrieNodeSet& other) { 
+                Body.swap(other.Body); 
+            } 
+
+        private: 
+            static const size_t MinNodeSize = 2; 
+            TVector<ui8> Body; 
+
+            static size_t ReducedOffset(size_t offset) { 
+                return offset / MinNodeSize; 
+            } 
+            static ui8 OffsetMask(size_t reducedOffset) { 
+                return 1 << (reducedOffset % 8); 
+            } 
+            ui8& OffsetCell(size_t reducedOffset) { 
+                return Body.at(reducedOffset / 8); 
+            } 
+            const ui8& OffsetCell(size_t reducedOffset) const { 
+                return Body.at(reducedOffset / 8); 
+            } 
+        }; 
+
+        //--------------------------------------------------------------------- 
+
+        class TTrieNodeCounts { 
+        public: 
             TTrieNodeCounts() = default;
 
-            explicit TTrieNodeCounts(const TOpaqueTrie& trie)
-                : Body(trie.Length / MinNodeSize, 0)
-                , IsTree(false)
-            {
-            }
-
-            size_t Get(size_t offset) const {
-                return IsTree ? 1 : Body.at(offset / MinNodeSize);
-            }
-
-            void Inc(size_t offset) {
-                if (IsTree) {
-                    return;
-                }
-                ui8& count = Body.at(offset / MinNodeSize);
-                if (count != MaxCount) {
-                    ++count;
-                }
-            }
-
-            size_t Dec(size_t offset) {
-                if (IsTree) {
-                    return 0;
-                }
-                ui8& count = Body.at(offset / MinNodeSize);
-                Y_ASSERT(count > 0);
-                if (count != MaxCount) {
-                    --count;
-                }
-                return count;
-            }
-
-            void Swap(TTrieNodeCounts& other) {
-                Body.swap(other.Body);
-                ::DoSwap(IsTree, other.IsTree);
-            }
-
-            void SetTreeMode() {
-                IsTree = true;
-                Body = TVector<ui8>();
-            }
-
-        private:
-            static const size_t MinNodeSize = 2;
-            static const ui8 MaxCount = 255;
-
-            TVector<ui8> Body;
-            bool IsTree = false;
-        };
-
-        //----------------------------------------------------------
-
-        class TOffsetIndex {
-        public:
-            // In all methods:
-            // Key --- offset from the beginning of the old trie.
-            // Value --- offset from the end of the new trie.
-
-            explicit TOffsetIndex(TTrieNodeCounts& counts) {
-                ParentCounts.Swap(counts);
-            }
-
-            void Add(size_t key, size_t value) {
-                Data[key] = value;
-            }
-
-            size_t Size() const {
-                return Data.size();
-            }
-
-            size_t Get(size_t key) {
-                auto pos = Data.find(key);
-                if (pos == Data.end()) {
-                    ythrow yexception() << "Bad node walking order: trying to get node offset too early or too many times!";
-                }
-                size_t result = pos->second;
-                if (ParentCounts.Dec(key) == 0) {
-                    // We don't need this offset any more.
-                    Data.erase(pos);
-                }
-                return result;
-            }
-
-        private:
-            TTrieNodeCounts ParentCounts;
-            THashMap<size_t, size_t> Data;
-        };
-
-        //---------------------------------------------------------------------------------------
-
-        class TTrieMeasurer {
-        public:
-            TTrieMeasurer(const TOpaqueTrie& trie, bool verbose);
-            void Measure();
-
-            size_t GetDepth() const {
-                return Depth;
-            }
-
-            size_t GetNodeCount() const {
-                return NodeCount;
-            }
-
-            size_t GetUnminimizedNodeCount() const {
-                return UnminimizedNodeCount;
-            }
-
-            bool IsTree() const {
-                return NodeCount == UnminimizedNodeCount;
-            }
-
-            TTrieNodeCounts& GetParentCounts() {
-                return ParentCounts;
-            }
-
-            const TOpaqueTrie& GetTrie() const {
-                return Trie;
-            }
-
-        private:
-            const TOpaqueTrie& Trie;
-            size_t Depth;
-            TTrieNodeCounts ParentCounts;
-            size_t NodeCount;
-            size_t UnminimizedNodeCount;
-            const bool Verbose;
-
-            // returns depth, increments NodeCount.
-            size_t MeasureSubtrie(size_t rootOffset, bool isNewPath);
-        };
-
-        TTrieMeasurer::TTrieMeasurer(const TOpaqueTrie& trie, bool verbose)
-            : Trie(trie)
-            , Depth(0)
-            , ParentCounts(trie)
-            , NodeCount(0)
-            , UnminimizedNodeCount(0)
-            , Verbose(verbose)
-        {
-            Y_ASSERT(Trie.Data);
+            explicit TTrieNodeCounts(const TOpaqueTrie& trie) 
+                : Body(trie.Length / MinNodeSize, 0) 
+                , IsTree(false) 
+            { 
+            } 
+
+            size_t Get(size_t offset) const { 
+                return IsTree ? 1 : Body.at(offset / MinNodeSize); 
+            } 
+
+            void Inc(size_t offset) { 
+                if (IsTree) { 
+                    return; 
+                } 
+                ui8& count = Body.at(offset / MinNodeSize); 
+                if (count != MaxCount) { 
+                    ++count; 
+                } 
+            } 
+
+            size_t Dec(size_t offset) { 
+                if (IsTree) { 
+                    return 0; 
+                } 
+                ui8& count = Body.at(offset / MinNodeSize); 
+                Y_ASSERT(count > 0); 
+                if (count != MaxCount) { 
+                    --count; 
+                } 
+                return count; 
+            } 
+
+            void Swap(TTrieNodeCounts& other) { 
+                Body.swap(other.Body); 
+                ::DoSwap(IsTree, other.IsTree); 
+            } 
+
+            void SetTreeMode() { 
+                IsTree = true; 
+                Body = TVector<ui8>(); 
+            } 
+
+        private: 
+            static const size_t MinNodeSize = 2; 
+            static const ui8 MaxCount = 255; 
+
+            TVector<ui8> Body; 
+            bool IsTree = false; 
+        }; 
+
+        //---------------------------------------------------------- 
+
+        class TOffsetIndex { 
+        public: 
+            // In all methods: 
+            // Key --- offset from the beginning of the old trie. 
+            // Value --- offset from the end of the new trie. 
+
+            explicit TOffsetIndex(TTrieNodeCounts& counts) { 
+                ParentCounts.Swap(counts); 
+            } 
+
+            void Add(size_t key, size_t value) { 
+                Data[key] = value; 
+            } 
+
+            size_t Size() const { 
+                return Data.size(); 
+            } 
+
+            size_t Get(size_t key) { 
+                auto pos = Data.find(key); 
+                if (pos == Data.end()) { 
+                    ythrow yexception() << "Bad node walking order: trying to get node offset too early or too many times!"; 
+                } 
+                size_t result = pos->second; 
+                if (ParentCounts.Dec(key) == 0) { 
+                    // We don't need this offset any more. 
+                    Data.erase(pos); 
+                } 
+                return result; 
+            } 
+
+        private: 
+            TTrieNodeCounts ParentCounts; 
+            THashMap<size_t, size_t> Data; 
+        }; 
+
+        //--------------------------------------------------------------------------------------- 
+
+        class TTrieMeasurer { 
+        public: 
+            TTrieMeasurer(const TOpaqueTrie& trie, bool verbose); 
+            void Measure(); 
+
+            size_t GetDepth() const { 
+                return Depth; 
+            } 
+
+            size_t GetNodeCount() const { 
+                return NodeCount; 
+            } 
+
+            size_t GetUnminimizedNodeCount() const { 
+                return UnminimizedNodeCount; 
+            } 
+
+            bool IsTree() const { 
+                return NodeCount == UnminimizedNodeCount; 
+            } 
+
+            TTrieNodeCounts& GetParentCounts() { 
+                return ParentCounts; 
+            } 
+
+            const TOpaqueTrie& GetTrie() const { 
+                return Trie; 
+            } 
+
+        private: 
+            const TOpaqueTrie& Trie; 
+            size_t Depth; 
+            TTrieNodeCounts ParentCounts; 
+            size_t NodeCount; 
+            size_t UnminimizedNodeCount; 
+            const bool Verbose; 
+
+            // returns depth, increments NodeCount. 
+            size_t MeasureSubtrie(size_t rootOffset, bool isNewPath); 
+        }; 
+
+        TTrieMeasurer::TTrieMeasurer(const TOpaqueTrie& trie, bool verbose) 
+            : Trie(trie) 
+            , Depth(0) 
+            , ParentCounts(trie) 
+            , NodeCount(0) 
+            , UnminimizedNodeCount(0) 
+            , Verbose(verbose) 
+        { 
+            Y_ASSERT(Trie.Data); 
+        } 
+
+        void TTrieMeasurer::Measure() { 
+            if (Verbose) { 
+                Cerr << "Measuring the trie..." << Endl; 
+            } 
+            NodeCount = 0; 
+            UnminimizedNodeCount = 0; 
+            Depth = MeasureSubtrie(0, true); 
+            if (IsTree()) { 
+                ParentCounts.SetTreeMode(); 
+            } 
+            if (Verbose) { 
+                Cerr << "Unminimized node count: " << UnminimizedNodeCount << Endl; 
+                Cerr << "Trie depth: " << Depth << Endl; 
+                Cerr << "Node count: " << NodeCount << Endl; 
+            } 
+        } 
+
+        // A chain of nodes linked by forward links 
+        // is considered one node with many left and right children 
+        // for depth measuring here and in 
+        // TVanEmdeBoasReverseNodeEnumerator::FindDescendants. 
+        size_t TTrieMeasurer::MeasureSubtrie(size_t rootOffset, bool isNewPath) { 
+            Y_ASSERT(rootOffset < Trie.Length); 
+            TNode node(Trie.Data, rootOffset, Trie.SkipFunction); 
+            size_t depth = 0; 
+            for (;;) { 
+                ++UnminimizedNodeCount; 
+                if (Verbose) { 
+                    ShowProgress(UnminimizedNodeCount); 
+                } 
+                if (isNewPath) { 
+                    if (ParentCounts.Get(node.GetOffset()) > 0) { 
+                        isNewPath = false; 
+                    } else { 
+                        ++NodeCount; 
+                    } 
+                    ParentCounts.Inc(node.GetOffset()); 
+                } 
+                if (node.GetLeftOffset()) { 
+                    depth = Max(depth, 1 + MeasureSubtrie(node.GetLeftOffset(), isNewPath)); 
+                } 
+                if (node.GetRightOffset()) { 
+                    depth = Max(depth, 1 + MeasureSubtrie(node.GetRightOffset(), isNewPath)); 
+                } 
+                if (node.GetForwardOffset()) { 
+                    node = TNode(Trie.Data, node.GetForwardOffset(), Trie.SkipFunction); 
+                } else { 
+                    break; 
+                } 
+            }
+            return depth; 
         }
-
-        void TTrieMeasurer::Measure() {
-            if (Verbose) {
-                Cerr << "Measuring the trie..." << Endl;
-            }
-            NodeCount = 0;
-            UnminimizedNodeCount = 0;
-            Depth = MeasureSubtrie(0, true);
-            if (IsTree()) {
-                ParentCounts.SetTreeMode();
-            }
-            if (Verbose) {
-                Cerr << "Unminimized node count: " << UnminimizedNodeCount << Endl;
-                Cerr << "Trie depth: " << Depth << Endl;
-                Cerr << "Node count: " << NodeCount << Endl;
-            }
-        }
-
-        // A chain of nodes linked by forward links
-        // is considered one node with many left and right children
-        // for depth measuring here and in
-        // TVanEmdeBoasReverseNodeEnumerator::FindDescendants.
-        size_t TTrieMeasurer::MeasureSubtrie(size_t rootOffset, bool isNewPath) {
-            Y_ASSERT(rootOffset < Trie.Length);
-            TNode node(Trie.Data, rootOffset, Trie.SkipFunction);
-            size_t depth = 0;
-            for (;;) {
-                ++UnminimizedNodeCount;
-                if (Verbose) {
-                    ShowProgress(UnminimizedNodeCount);
-                }
-                if (isNewPath) {
-                    if (ParentCounts.Get(node.GetOffset()) > 0) {
-                        isNewPath = false;
-                    } else {
-                        ++NodeCount;
-                    }
-                    ParentCounts.Inc(node.GetOffset());
-                }
-                if (node.GetLeftOffset()) {
-                    depth = Max(depth, 1 + MeasureSubtrie(node.GetLeftOffset(), isNewPath));
-                }
-                if (node.GetRightOffset()) {
-                    depth = Max(depth, 1 + MeasureSubtrie(node.GetRightOffset(), isNewPath));
-                }
-                if (node.GetForwardOffset()) {
-                    node = TNode(Trie.Data, node.GetForwardOffset(), Trie.SkipFunction);
-                } else {
-                    break;
-                }
-            }
-            return depth;
-        }
-
-        //--------------------------------------------------------------------------------------
-
-        using TLevelNodes = TVector<size_t>;
-
-        struct TLevel {
-            size_t Depth;
-            TLevelNodes Nodes;
-
-            explicit TLevel(size_t depth)
-                : Depth(depth)
-            {
-            }
-        };
-
-        //----------------------------------------------------------------------------------------
-
-        class TVanEmdeBoasReverseNodeEnumerator: public TReverseNodeEnumerator {
-        public:
-            TVanEmdeBoasReverseNodeEnumerator(TTrieMeasurer& measurer, bool verbose)
-                : Fresh(true)
-                , Trie(measurer.GetTrie())
-                , Depth(measurer.GetDepth())
-                , MaxIndexSize(0)
-                , BackIndex(measurer.GetParentCounts())
-                , ProcessedNodes(measurer.GetTrie())
-                , Verbose(verbose)
-            {
-            }
-
-            bool Move() override {
-                if (!Fresh) {
-                    CentralWord.pop_back();
-                }
-                if (CentralWord.empty()) {
-                    return MoveCentralWordStart();
-                }
-                return true;
-            }
-
-            const TNode& Get() const {
-                return CentralWord.back();
-            }
-
-            size_t GetLeafLength() const override {
-                return Get().GetLeafLength();
-            }
-
-            // Returns recalculated offset from the end of the current node.
-            size_t PrepareOffset(size_t absoffset, size_t resultLength) {
-                if (!absoffset)
-                    return NPOS;
-                return resultLength - BackIndex.Get(absoffset);
-            }
-
-            size_t RecreateNode(char* buffer, size_t resultLength) override {
-                TWriteableNode newNode(Get(), Trie.Data);
-                newNode.ForwardOffset = PrepareOffset(Get().GetForwardOffset(), resultLength);
-                newNode.LeftOffset = PrepareOffset(Get().GetLeftOffset(), resultLength);
-                newNode.RightOffset = PrepareOffset(Get().GetRightOffset(), resultLength);
-
-                const size_t len = newNode.Pack(buffer);
-                ProcessedNodes.Add(Get().GetOffset());
-                BackIndex.Add(Get().GetOffset(), resultLength + len);
-                MaxIndexSize = Max(MaxIndexSize, BackIndex.Size());
-                return len;
-            }
-
-        private:
-            bool Fresh;
-            TOpaqueTrie Trie;
-            size_t Depth;
-            size_t MaxIndexSize;
-
-            TVector<TLevel> Trace;
-            TOffsetIndex BackIndex;
-            TVector<TNode> CentralWord;
-            TTrieNodeSet ProcessedNodes;
-
-            const bool Verbose;
-
-        private:
-            bool IsVisited(size_t offset) const {
-                return ProcessedNodes.Has(offset);
-            }
-
-            void AddCascade(size_t step) {
-                Y_ASSERT(!(step & (step - 1))); // Should be a power of 2.
-                while (step > 0) {
-                    size_t root = Trace.back().Nodes.back();
-                    TLevel level(Trace.back().Depth + step);
-                    Trace.push_back(level);
-                    size_t actualStep = FindSupportingPowerOf2(FindDescendants(root, step, Trace.back().Nodes));
-                    if (actualStep != step) {
-                        // Retry with a smaller step.
-                        Y_ASSERT(actualStep < step);
-                        step = actualStep;
-                        Trace.pop_back();
-                    } else {
-                        step /= 2;
+ 
+        //-------------------------------------------------------------------------------------- 
+
+        using TLevelNodes = TVector<size_t>; 
+
+        struct TLevel { 
+            size_t Depth; 
+            TLevelNodes Nodes; 
+ 
+            explicit TLevel(size_t depth) 
+                : Depth(depth) 
+            { 
+            } 
+        }; 
+ 
+        //---------------------------------------------------------------------------------------- 
+
+        class TVanEmdeBoasReverseNodeEnumerator: public TReverseNodeEnumerator { 
+        public: 
+            TVanEmdeBoasReverseNodeEnumerator(TTrieMeasurer& measurer, bool verbose) 
+                : Fresh(true) 
+                , Trie(measurer.GetTrie()) 
+                , Depth(measurer.GetDepth()) 
+                , MaxIndexSize(0) 
+                , BackIndex(measurer.GetParentCounts()) 
+                , ProcessedNodes(measurer.GetTrie()) 
+                , Verbose(verbose) 
+            { 
+            } 
+
+            bool Move() override { 
+                if (!Fresh) { 
+                    CentralWord.pop_back(); 
+                } 
+                if (CentralWord.empty()) { 
+                    return MoveCentralWordStart(); 
+                } 
+                return true; 
+            } 
+
+            const TNode& Get() const { 
+                return CentralWord.back(); 
+            } 
+
+            size_t GetLeafLength() const override { 
+                return Get().GetLeafLength(); 
+            } 
+
+            // Returns recalculated offset from the end of the current node. 
+            size_t PrepareOffset(size_t absoffset, size_t resultLength) { 
+                if (!absoffset) 
+                    return NPOS; 
+                return resultLength - BackIndex.Get(absoffset); 
+            } 
+
+            size_t RecreateNode(char* buffer, size_t resultLength) override { 
+                TWriteableNode newNode(Get(), Trie.Data); 
+                newNode.ForwardOffset = PrepareOffset(Get().GetForwardOffset(), resultLength); 
+                newNode.LeftOffset = PrepareOffset(Get().GetLeftOffset(), resultLength); 
+                newNode.RightOffset = PrepareOffset(Get().GetRightOffset(), resultLength); 
+ 
+                const size_t len = newNode.Pack(buffer); 
+                ProcessedNodes.Add(Get().GetOffset()); 
+                BackIndex.Add(Get().GetOffset(), resultLength + len); 
+                MaxIndexSize = Max(MaxIndexSize, BackIndex.Size()); 
+                return len; 
+            } 
+
+        private: 
+            bool Fresh; 
+            TOpaqueTrie Trie; 
+            size_t Depth; 
+            size_t MaxIndexSize; 
+
+            TVector<TLevel> Trace; 
+            TOffsetIndex BackIndex; 
+            TVector<TNode> CentralWord; 
+            TTrieNodeSet ProcessedNodes; 
+
+            const bool Verbose; 
+
+        private: 
+            bool IsVisited(size_t offset) const { 
+                return ProcessedNodes.Has(offset); 
+            } 
+
+            void AddCascade(size_t step) { 
+                Y_ASSERT(!(step & (step - 1))); // Should be a power of 2. 
+                while (step > 0) { 
+                    size_t root = Trace.back().Nodes.back(); 
+                    TLevel level(Trace.back().Depth + step); 
+                    Trace.push_back(level); 
+                    size_t actualStep = FindSupportingPowerOf2(FindDescendants(root, step, Trace.back().Nodes)); 
+                    if (actualStep != step) { 
+                        // Retry with a smaller step. 
+                        Y_ASSERT(actualStep < step); 
+                        step = actualStep; 
+                        Trace.pop_back(); 
+                    } else { 
+                        step /= 2; 
+                    } 
+                } 
+            }
+
+            void FillCentralWord() { 
+                CentralWord.clear(); 
+                CentralWord.push_back(TNode(Trie.Data, Trace.back().Nodes.back(), Trie.SkipFunction)); 
+                // Do not check for epsilon links, as the traversal order now is different. 
+                while (CentralWord.back().GetForwardOffset() && !IsVisited(CentralWord.back().GetForwardOffset())) { 
+                    CentralWord.push_back(TNode(Trie.Data, CentralWord.back().GetForwardOffset(), Trie.SkipFunction)); 
+                } 
+            } 
+
+            bool MoveCentralWordStart() { 
+                do { 
+                    if (Fresh) { 
+                        TLevel root(0); 
+                        Trace.push_back(root); 
+                        Trace.back().Nodes.push_back(0); 
+                        const size_t sectionDepth = FindSupportingPowerOf2(Depth); 
+                        AddCascade(sectionDepth); 
+                        Fresh = false; 
+                    } else { 
+                        Trace.back().Nodes.pop_back(); 
+                        if (Trace.back().Nodes.empty() && Trace.size() == 1) { 
+                            if (Verbose) { 
+                                Cerr << "Max index size: " << MaxIndexSize << Endl; 
+                                Cerr << "Current index size: " << BackIndex.Size() << Endl; 
+                            } 
+                            // We just popped the root. 
+                            return false; 
+                        } 
+                        size_t lastStep = Trace.back().Depth - Trace[Trace.size() - 2].Depth; 
+                        if (Trace.back().Nodes.empty()) { 
+                            Trace.pop_back(); 
+                        } 
+                        AddCascade(lastStep / 2); 
+                    } 
+                } while (IsVisited(Trace.back().Nodes.back())); 
+                FillCentralWord(); 
+                return true; 
+            }
+ 
+            // Returns the maximal depth it has reached while searching. 
+            // This is a method because it needs OffsetIndex to skip processed nodes. 
+            size_t FindDescendants(size_t rootOffset, size_t depth, TLevelNodes& result) const { 
+                if (depth == 0) { 
+                    result.push_back(rootOffset); 
+                    return 0; 
+                } 
+                size_t actualDepth = 0; 
+                TNode node(Trie.Data, rootOffset, Trie.SkipFunction); 
+                for (;;) { 
+                    if (node.GetLeftOffset() && !IsVisited(node.GetLeftOffset())) { 
+                        actualDepth = Max(actualDepth, 
+                                          1 + FindDescendants(node.GetLeftOffset(), depth - 1, result)); 
                     }
+                    if (node.GetRightOffset() && !IsVisited(node.GetRightOffset())) { 
+                        actualDepth = Max(actualDepth, 
+                                          1 + FindDescendants(node.GetRightOffset(), depth - 1, result)); 
+                    } 
+                    if (node.GetForwardOffset() && !IsVisited(node.GetForwardOffset())) { 
+                        node = TNode(Trie.Data, node.GetForwardOffset(), Trie.SkipFunction); 
+                    } else { 
+                        break; 
+                    } 
                 }
+                return actualDepth; 
             }
+        }; 
 
-            void FillCentralWord() {
-                CentralWord.clear();
-                CentralWord.push_back(TNode(Trie.Data, Trace.back().Nodes.back(), Trie.SkipFunction));
-                // Do not check for epsilon links, as the traversal order now is different.
-                while (CentralWord.back().GetForwardOffset() && !IsVisited(CentralWord.back().GetForwardOffset())) {
-                    CentralWord.push_back(TNode(Trie.Data, CentralWord.back().GetForwardOffset(), Trie.SkipFunction));
-                }
-            }
-
-            bool MoveCentralWordStart() {
-                do {
-                    if (Fresh) {
-                        TLevel root(0);
-                        Trace.push_back(root);
-                        Trace.back().Nodes.push_back(0);
-                        const size_t sectionDepth = FindSupportingPowerOf2(Depth);
-                        AddCascade(sectionDepth);
-                        Fresh = false;
-                    } else {
-                        Trace.back().Nodes.pop_back();
-                        if (Trace.back().Nodes.empty() && Trace.size() == 1) {
-                            if (Verbose) {
-                                Cerr << "Max index size: " << MaxIndexSize << Endl;
-                                Cerr << "Current index size: " << BackIndex.Size() << Endl;
-                            }
-                            // We just popped the root.
-                            return false;
-                        }
-                        size_t lastStep = Trace.back().Depth - Trace[Trace.size() - 2].Depth;
-                        if (Trace.back().Nodes.empty()) {
-                            Trace.pop_back();
-                        }
-                        AddCascade(lastStep / 2);
-                    }
-                } while (IsVisited(Trace.back().Nodes.back()));
-                FillCentralWord();
-                return true;
-            }
-
-            // Returns the maximal depth it has reached while searching.
-            // This is a method because it needs OffsetIndex to skip processed nodes.
-            size_t FindDescendants(size_t rootOffset, size_t depth, TLevelNodes& result) const {
-                if (depth == 0) {
-                    result.push_back(rootOffset);
-                    return 0;
-                }
-                size_t actualDepth = 0;
-                TNode node(Trie.Data, rootOffset, Trie.SkipFunction);
-                for (;;) {
-                    if (node.GetLeftOffset() && !IsVisited(node.GetLeftOffset())) {
-                        actualDepth = Max(actualDepth,
-                                          1 + FindDescendants(node.GetLeftOffset(), depth - 1, result));
-                    }
-                    if (node.GetRightOffset() && !IsVisited(node.GetRightOffset())) {
-                        actualDepth = Max(actualDepth,
-                                          1 + FindDescendants(node.GetRightOffset(), depth - 1, result));
-                    }
-                    if (node.GetForwardOffset() && !IsVisited(node.GetForwardOffset())) {
-                        node = TNode(Trie.Data, node.GetForwardOffset(), Trie.SkipFunction);
-                    } else {
-                        break;
-                    }
-                }
-                return actualDepth;
-            }
-        };
-
-    } // Anonymous namespace.
-
-    //-----------------------------------------------------------------------------------
-
-    size_t RawCompactTrieFastLayoutImpl(IOutputStream& os, const TOpaqueTrie& trie, bool verbose) {
-        if (!trie.Data || !trie.Length) {
+    } // Anonymous namespace. 
+ 
+    //----------------------------------------------------------------------------------- 
+ 
+    size_t RawCompactTrieFastLayoutImpl(IOutputStream& os, const TOpaqueTrie& trie, bool verbose) { 
+        if (!trie.Data || !trie.Length) { 
             return 0;
         }
-        TTrieMeasurer mes(trie, verbose);
-        mes.Measure();
-        TVanEmdeBoasReverseNodeEnumerator enumerator(mes, verbose);
-        return WriteTrieBackwards(os, enumerator, verbose);
+        TTrieMeasurer mes(trie, verbose); 
+        mes.Measure(); 
+        TVanEmdeBoasReverseNodeEnumerator enumerator(mes, verbose); 
+        return WriteTrieBackwards(os, enumerator, verbose); 
     }
-
+ 
 }