LLVM 24.0.0git
SuffixTreeNode.h
Go to the documentation of this file.
1//===- llvm/ADT/SuffixTreeNode.h - Nodes for SuffixTrees --------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines nodes for use within a SuffixTree.
10//
11// Each node has either no children or at least two children, with the root
12// being an exception in the empty tree. Pruning boundary leaves can leave
13// internal nodes with fewer children.
14//
15// Children are represented as a map between unsigned integers and nodes. If
16// a node N has a child M on unsigned integer k, then the mapping represented
17// by N is a proper prefix of the mapping represented by M. Note that this,
18// although similar to a trie is somewhat different: each node stores a full
19// substring of the full mapping rather than a single character state.
20//
21// Each internal node contains a pointer to the internal node representing
22// the same string, but with the first character chopped off. This is stored
23// in \p Link. Each leaf node stores the start index of its respective
24// suffix in \p SuffixIdx.
25//===----------------------------------------------------------------------===//
26
27#ifndef LLVM_SUPPORT_SUFFIXTREE_NODE_H
28#define LLVM_SUPPORT_SUFFIXTREE_NODE_H
29#include "llvm/ADT/DenseMap.h"
31
32namespace llvm {
33
34/// A node in a suffix tree which represents a substring or suffix.
36public:
37 /// Represents an undefined index in the suffix tree.
38 static const unsigned EmptyIdx = -1;
39 enum class NodeKind { ST_Leaf, ST_Internal };
40
41private:
42 const NodeKind Kind;
43
44 /// The start index of this node's substring in the main string.
45 unsigned StartIdx = EmptyIdx;
46
47 /// The length of the string formed by concatenating the edge labels from
48 /// the root to this node.
49 unsigned ConcatLen = 0;
50
51 /// These two indices give a range of indices for its leaf descendants.
52 /// Imagine drawing a tree on paper and assigning a unique index to each leaf
53 /// node in monotonically increasing order from left to right. This way of
54 /// numbering the leaf nodes allows us to associate a continuous range of
55 /// indices with each internal node. For example, if a node has leaf
56 /// descendants with indices i, i+1, ..., j, then its LeftLeafIdx is i and
57 /// its RightLeafIdx is j. These indices are for LeafNodes in the SuffixTree
58 /// class, which is constructed using post-order depth-first traversal.
59 unsigned LeftLeafIdx = EmptyIdx;
60 unsigned RightLeafIdx = EmptyIdx;
61
62public:
63 // LLVM RTTI boilerplate.
64 NodeKind getKind() const { return Kind; }
65
66 /// \return the start index of this node's substring in the entire string.
67 LLVM_ABI unsigned getStartIdx() const;
68
69 /// \returns the end index of this node.
70 virtual unsigned getEndIdx() const = 0;
71
72 /// \return the index of this node's left most leaf node.
73 LLVM_ABI unsigned getLeftLeafIdx() const;
74
75 /// \return the index of this node's right most leaf node.
76 LLVM_ABI unsigned getRightLeafIdx() const;
77
78 /// Set the index of the left most leaf node of this node to \p Idx.
79 LLVM_ABI void setLeftLeafIdx(unsigned Idx);
80
81 /// Set the index of the right most leaf node of this node to \p Idx.
82 LLVM_ABI void setRightLeafIdx(unsigned Idx);
83
84 /// Advance this node's StartIdx by \p Inc.
85 LLVM_ABI void incrementStartIdx(unsigned Inc);
86
87 /// Set the length of the string from the root to this node to \p Len.
88 LLVM_ABI void setConcatLen(unsigned Len);
89
90 /// \returns the length of the string from the root to this node.
91 LLVM_ABI unsigned getConcatLen() const;
92
93 SuffixTreeNode(NodeKind Kind, unsigned StartIdx)
94 : Kind(Kind), StartIdx(StartIdx) {}
95 virtual ~SuffixTreeNode() = default;
96};
97
98// A node with two or more children before pruning, or the root.
100private:
101 /// The end index of this node's substring in the main string.
102 ///
103 /// Every leaf node must have its \p EndIdx incremented at the end of every
104 /// step in the construction algorithm. To avoid having to update O(N)
105 /// nodes individually at the end of every step, the end index is stored
106 /// as a pointer.
107 unsigned EndIdx = EmptyIdx;
108
109 /// A pointer to the internal node representing the same sequence with the
110 /// first character chopped off.
111 ///
112 /// This acts as a shortcut in Ukkonen's algorithm. One of the things that
113 /// Ukkonen's algorithm does to achieve linear-time construction is
114 /// keep track of which node the next insert should be at. This makes each
115 /// insert O(1), and there are a total of O(N) inserts. The suffix link
116 /// helps with inserting children of internal nodes.
117 ///
118 /// Say we add a child to an internal node with associated mapping S. The
119 /// next insertion must be at the node representing S - its first character.
120 /// This is given by the way that we iteratively build the tree in Ukkonen's
121 /// algorithm. The main idea is to look at the suffixes of each prefix in the
122 /// string, starting with the longest suffix of the prefix, and ending with
123 /// the shortest. Therefore, if we keep pointers between such nodes, we can
124 /// move to the next insertion point in O(1) time. If we don't, then we'd
125 /// have to query from the root, which takes O(N) time. This would make the
126 /// construction algorithm O(N^2) rather than O(N).
127 SuffixTreeInternalNode *Link = nullptr;
128
129public:
130 // LLVM RTTI boilerplate.
131 static bool classof(const SuffixTreeNode *N) {
132 return N->getKind() == NodeKind::ST_Internal;
133 }
134
135 /// \returns true if this node is the root of its owning \p SuffixTree.
136 bool isRoot() const;
137
138 /// \returns the end index of this node's substring in the entire string.
139 unsigned getEndIdx() const override;
140
141 /// Sets \p Link to \p L. Assumes \p L is not null.
142 void setLink(SuffixTreeInternalNode *L);
143
144 /// \returns the pointer to the Link node.
145 SuffixTreeInternalNode *getLink() const;
146
147 /// The children of this node.
148 ///
149 /// A child existing on an unsigned integer implies that from the mapping
150 /// represented by the current node, there is a way to reach another
151 /// mapping by tacking that character on the end of the current string.
153
154 SuffixTreeInternalNode(unsigned StartIdx, unsigned EndIdx,
156 : SuffixTreeNode(NodeKind::ST_Internal, StartIdx), EndIdx(EndIdx),
157 Link(Link) {}
158
159 ~SuffixTreeInternalNode() override = default;
160};
161
162// A node representing a suffix.
164private:
165 /// The start index of the suffix represented by this leaf.
166 unsigned SuffixIdx = EmptyIdx;
167
168 /// The end index of this node's substring in the main string.
169 ///
170 /// Every leaf node must have its \p EndIdx incremented at the end of every
171 /// step in the construction algorithm. To avoid having to update O(N)
172 /// nodes individually at the end of every step, the end index is stored
173 /// as a pointer.
174 unsigned *EndIdx = nullptr;
175
176public:
177 // LLVM RTTI boilerplate.
178 static bool classof(const SuffixTreeNode *N) {
179 return N->getKind() == NodeKind::ST_Leaf;
180 }
181
182 /// \returns the end index of this node's substring in the entire string.
183 unsigned getEndIdx() const override;
184
185 /// \returns the start index of the suffix represented by this leaf.
186 unsigned getSuffixIdx() const;
187
188 /// Sets the start index of the suffix represented by this leaf to \p Idx.
189 void setSuffixIdx(unsigned Idx);
190 SuffixTreeLeafNode(unsigned StartIdx, unsigned *EndIdx)
191 : SuffixTreeNode(NodeKind::ST_Leaf, StartIdx), EndIdx(EndIdx) {}
192
193 ~SuffixTreeLeafNode() override = default;
194};
195} // namespace llvm
196#endif // LLVM_SUPPORT_SUFFIXTREE_NODE_H
#define LLVM_ABI
Definition Compiler.h:211
This file defines the DenseMap class.
This is an optimization pass for GlobalISel generic memory operations.
#define N
Determine the kind of a node from its type.
DenseMap< unsigned, SuffixTreeNode * > Children
The children of this node.
static bool classof(const SuffixTreeNode *N)
SuffixTreeInternalNode(unsigned StartIdx, unsigned EndIdx, SuffixTreeInternalNode *Link)
~SuffixTreeInternalNode() override=default
~SuffixTreeLeafNode() override=default
static bool classof(const SuffixTreeNode *N)
SuffixTreeLeafNode(unsigned StartIdx, unsigned *EndIdx)
LLVM_ABI void incrementStartIdx(unsigned Inc)
Advance this node's StartIdx by Inc.
NodeKind getKind() const
LLVM_ABI void setConcatLen(unsigned Len)
Set the length of the string from the root to this node to Len.
LLVM_ABI unsigned getLeftLeafIdx() const
virtual ~SuffixTreeNode()=default
LLVM_ABI unsigned getRightLeafIdx() const
LLVM_ABI void setRightLeafIdx(unsigned Idx)
Set the index of the right most leaf node of this node to Idx.
SuffixTreeNode(NodeKind Kind, unsigned StartIdx)
LLVM_ABI unsigned getConcatLen() const
static const unsigned EmptyIdx
Represents an undefined index in the suffix tree.
LLVM_ABI unsigned getStartIdx() const
LLVM_ABI void setLeftLeafIdx(unsigned Idx)
Set the index of the left most leaf node of this node to Idx.
virtual unsigned getEndIdx() const =0