llvm/llvm/unittests/Support/SuffixTreeTest.cpp

//===- unittests/Support/SuffixTreeTest.cpp - suffix tree tests -----------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "llvm/Support/SuffixTree.h"
#include "gtest/gtest.h"
#include <vector>

usingnamespacellvm;

namespace {

// Each example vector has a unique element at the end to represent the end of
// the string

// Tests that The SuffixTree finds a simple repetition of the substring {1, 2}
// {1, 2} twice in the provided string.
TEST(SuffixTreeTest, TestSingleRepetition) { … }

// Tests that the SuffixTree is able to find the substrings {1, 2, 3} at
// at indices 0 and 3 as well as the substrings {2, 3} at indices 1 and 4.
// This test also serves as a flag for improvements to the suffix tree.
//
// FIXME: Right now, the longest repeated substring from a specific index is
// returned, this could be improved to return the longest repeated substring, as
// well as those that are smaller.
TEST(SuffixTreeTest, TestLongerRepetition) { … }

// Tests that the SuffixTree is able to find substring {1, 1, 1, 1, 1} at
// indices 0 and 1.
//
// FIXME: Add support for detecting {1, 1} and {1, 1, 1}
// See Test TestSingleCharacterRepeatWithLeafDescendants for the fix
TEST(SuffixTreeTest, TestSingleCharacterRepeat) { … }

// Tests that the SuffixTree is able to find the following substrings:
// {1, 1} at indices 0, 1, 2, 3, and 4;
// {1, 1, 1} at indices 0, 1, 2, and 3;
// {1, 1, 1, 1}  at indices 0, 1, and 2; and
// {1, 1, 1, 1, 1} at indices 0 and 1.
//
// This is the fix for TestSingleCharacterRepeat.
TEST(SuffixTreeTest, TestSingleCharacterRepeatWithLeafDescendants) { … }

// The suffix tree cannot currently find repeated substrings in strings of the
// form {1, 2, 3, 1, 2, 3}, because the two {1, 2, 3}s are adjacent ("tandem
// repeats")
//
// FIXME: Teach the SuffixTree to recognize these cases.
TEST(SuffixTreeTest, TestTandemRepeat) { … }

// Tests that the SuffixTree does not erroneously include values that are not
// in repeated substrings.  That is, only finds {1, 1} at indices 0 and 3 and
// does not include 2 and 3.
TEST(SuffixTreeTest, TestExclusion) { … }

// Tests that the SuffixTree is able to find three substrings
// {1, 2, 3} at indices 6 and 10;
// {2, 3} at indices 7 and 11; and
// {1, 2} at indicies 0 and 3.
//
// FIXME: {1, 2} has indices 6 and 10 missing as it is a substring of {1, 2, 3}
// See Test TestSubstringRepeatsWithLeafDescendants for the fix
TEST(SuffixTreeTest, TestSubstringRepeats) { … }

// Tests that the SuffixTree is able to find three substrings
// {1, 2, 3} at indices 6 and 10;
// {2, 3} at indices 7 and 11; and
// {1, 2} at indicies 0, 3, 6, and 10.
//
// This is the fix for TestSubstringRepeats
TEST(SuffixTreeTest, TestSubstringRepeatsWithLeafDescendants) { … }

} // namespace