Lines Matching +full:active +full:-
1 //===- llvm/Support/SuffixTree.cpp - Implement Suffix Tree ------*- C++ -*-===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
24 if (Internal->isRoot()) in numElementsInSubstring()
26 return N->getEndIdx() - N->getStartIdx() + 1; in numElementsInSubstring()
33 Active.Node = Root; in SuffixTree()
73 "Non-root internal nodes must have parents!"); in insertInternalNode()
77 Parent->Children[Edge] = N; in insertInternalNode()
101 CurrNode->setConcatLen(CurrNodeLen); in setSuffixIndices()
103 for (auto &ChildPair : InternalNode->Children) { in setSuffixIndices()
111 LeafNode->setSuffixIdx(Str.size() - CurrNodeLen); in setSuffixIndices()
116 // A stack that keeps track of nodes to visit for post-order DFS traversal. in setLeafNodes()
130 // Traverse the tree in post-order. in setLeafNodes()
141 auto J = CurrInternalNode->Children.begin(); in setLeafNodes()
142 if (J != CurrInternalNode->Children.end()) { in setLeafNodes()
144 SuffixTreeNode *FirstChild = J->second; in setLeafNodes()
146 for (; J != CurrInternalNode->Children.end(); ++J) { in setLeafNodes()
147 LastChild = J->second; in setLeafNodes()
156 auto [FirstChild, LastChild] = I->second; in setLeafNodes()
161 CurrNode->setRightLeafIdx(FirstChild->getRightLeafIdx()); in setLeafNodes()
163 CurrNode->setLeftLeafIdx(LastChild->getLeftLeafIdx()); in setLeafNodes()
164 assert(CurrNode->getLeftLeafIdx() <= CurrNode->getRightLeafIdx() && in setLeafNodes()
170 CurrNode->setLeftLeafIdx(LeafCounter); in setLeafNodes()
171 CurrNode->setRightLeafIdx(LeafCounter); in setLeafNodes()
185 if (Active.Len == 0) { in extend()
186 // If not, then say the active index is the end index. in extend()
187 Active.Idx = EndIdx; in extend()
190 assert(Active.Idx <= EndIdx && "Start index can't be after end index!"); in extend()
193 unsigned FirstChar = Str[Active.Idx]; in extend()
196 if (Active.Node->Children.count(FirstChar) == 0) { in extend()
198 insertLeaf(*Active.Node, EndIdx, FirstChar); in extend()
200 // The active node is an internal node, and we visited it, so it must in extend()
203 NeedsLink->setLink(Active.Node); in extend()
209 SuffixTreeNode *NextNode = Active.Node->Children[FirstChar]; in extend()
215 if (Active.Len >= SubstringLen) { in extend()
220 Active.Idx += SubstringLen; in extend()
221 Active.Len -= SubstringLen; in extend()
222 Active.Node = cast<SuffixTreeInternalNode>(NextNode); in extend()
231 if (Str[NextNode->getStartIdx() + Active.Len] == LastChar) { in extend()
235 if (NeedsLink && !Active.Node->isRoot()) { in extend()
236 NeedsLink->setLink(Active.Node); in extend()
240 Active.Len++; in extend()
252 // | ABC ---split---> | AB in extend()
259 Active.Node, NextNode->getStartIdx(), in extend()
260 NextNode->getStartIdx() + Active.Len - 1, FirstChar); in extend()
268 NextNode->incrementStartIdx(Active.Len); in extend()
269 SplitNode->Children[Str[NextNode->getStartIdx()]] = NextNode; in extend()
273 NeedsLink->setLink(SplitNode); in extend()
280 SuffixesToAdd--; in extend()
282 if (Active.Node->isRoot()) { in extend()
283 if (Active.Len > 0) { in extend()
284 Active.Len--; in extend()
285 Active.Idx = EndIdx - SuffixesToAdd + 1; in extend()
289 Active.Node = Active.Node->getLink(); in extend()
313 unsigned Length = Curr->getConcatLen(); in advance()
317 for (auto &ChildPair : Curr->Children) in advance()
329 if (Curr->isRoot()) in advance()
334 for (unsigned I = Curr->getLeftLeafIdx(); I <= Curr->getRightLeafIdx(); in advance()
336 RepeatedSubstringStarts.push_back(LeafNodes[I]->getSuffixIdx()); in advance()
338 for (auto &ChildPair : Curr->Children) in advance()
340 RepeatedSubstringStarts.push_back(Leaf->getSuffixIdx()); in advance()