Method MeasureSubtrie

library/cpp/containers/comptrie/make_fast_layout.cpp:251–281

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.

        // 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;
        }

        //--------------------------------------------------------------------------------------