Skip to content

Commit 1688a7b

Browse files
author
Yurii A.
committed
WIP: add suggested tests skeleton
* refactor extract_snippets.py to take arguments from command line * add logging to extract_snippets.py script * add suggested CMakeLists.txt * add google test library, add example refactoring for 2sat and aho korasick tests
1 parent 6eecd4a commit 1688a7b

File tree

6 files changed

+286
-41
lines changed

6 files changed

+286
-41
lines changed

‎test/.gitignore

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,2 @@
1-
/*.h
1+
include/snippets/
2+
build/

‎test/CMakeLists.txt

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
cmake_minimum_required(VERSION 3.30 FATAL_ERROR)
2+
3+
project(cp-algorithms LANGUAGES CXX)
4+
5+
# generating snippets
6+
set(SNIPPETS_DIR ${CMAKE_CURRENT_SOURCE_DIR}/include/snippets)
7+
find_package(Python3 3.10 REQUIRED COMPONENTS Interpreter)
8+
execute_process(
9+
COMMAND
10+
${Python3_EXECUTABLE}
11+
"${CMAKE_CURRENT_SOURCE_DIR}/scripts/extract_snippets.py"
12+
--src-dir=${CMAKE_CURRENT_SOURCE_DIR}/../src
13+
--target-dir=${SNIPPETS_DIR}
14+
--remove-prev-target-dir
15+
COMMAND_ERROR_IS_FATAL ANY
16+
)
17+
18+
# loading googletest
19+
include(FetchContent)
20+
FetchContent_Declare(
21+
googletest
22+
GIT_REPOSITORY https://github.com/google/googletest.git
23+
GIT_TAG v1.17.0
24+
)
25+
# For Windows: Prevent overriding the parent project's compiler/linker settings
26+
set(gtest_force_shared_crt ON CACHE BOOL "" FORCE)
27+
FetchContent_MakeAvailable(googletest)
28+
include(GoogleTest)
29+
30+
set(CMAKE_CXX_STANDARD 20)
31+
set(CMAKE_CXX_STANDARD_REQUIRED ON)
32+
set(CMAKE_CXX_EXTENSIONS OFF)
33+
34+
file(GLOB_RECURSE SNIPPETS_SOURCES CONFIGURE_DEPENDS ${SNIPPETS_DIR}/*.h)
35+
file(GLOB_RECURSE TEST_SOURCES CONFIGURE_DEPENDS src/test_*.cpp)
36+
37+
add_executable(main ${TEST_SOURCES} ${SNIPPETS_SOURCES})
38+
target_link_libraries(main PRIVATE GTest::gtest_main GTest::gtest GTest::gmock)
39+
target_include_directories(main PRIVATE ${CMAKE_CURRENT_SOURCE_DIR}/include)
40+
41+
enable_testing()
42+
gtest_discover_tests(main)

‎test/extract_snippets.py

Lines changed: 0 additions & 40 deletions
This file was deleted.

‎test/scripts/extract_snippets.py

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
import argparse
2+
import re
3+
import os
4+
import sys
5+
import shutil
6+
import logging
7+
from typing import List, Optional
8+
from dataclasses import dataclass
9+
10+
11+
@dataclass
12+
class Snippet:
13+
name: str
14+
lines: List[str]
15+
16+
17+
def write_snippet(target_dir: os.PathLike, snippet: Snippet):
18+
assert os.path.exists(target_dir) and os.path.isdir(target_dir)
19+
20+
file_name = f'{snippet.name}.h'
21+
with open(os.path.join(target_dir, file_name), 'w', encoding='utf-8') as f:
22+
f.writelines(snippet.lines)
23+
24+
25+
def extract_snippets(filepath: os.PathLike) -> List[Snippet]:
26+
with open(filepath, 'r', encoding='utf-8') as f:
27+
lines = f.readlines()
28+
29+
snippets = []
30+
31+
snippet_start = re.compile(r"^```\{.cpp\s+file=(\S+)\}$")
32+
snippet_end = re.compile(r"^```$")
33+
34+
snippet_start_line: Optional[int] = None
35+
snippet_name: Optional[str] = None
36+
37+
for line_idx, line in enumerate(lines):
38+
match_snippet_start = snippet_start.match(line)
39+
match_snippet_end = snippet_end.match(line)
40+
assert not (match_snippet_start and match_snippet_end)
41+
42+
if match_snippet_start:
43+
assert snippet_start_line is None
44+
assert snippet_name is None
45+
46+
snippet_start_line = line_idx
47+
snippet_name = match_snippet_start.group(1)
48+
elif match_snippet_end:
49+
if snippet_start_line is not None:
50+
assert snippet_start_line is not None
51+
assert snippet_name is not None
52+
53+
snippet = lines[snippet_start_line + 1: line_idx]
54+
55+
snippets.append(Snippet(name=snippet_name, lines=snippet))
56+
57+
snippet_start_line = None
58+
snippet_name = None
59+
60+
return snippets
61+
62+
63+
def main(args: argparse.Namespace) -> None:
64+
src_dir = args.src_dir
65+
target_dir = args.target_dir
66+
67+
logging.info(f'--src-dir="{src_dir}"')
68+
logging.info(f'--target-dir="{target_dir}"')
69+
70+
assert os.path.isdir(src_dir)
71+
72+
if args.remove_prev_target_dir and os.path.exists(target_dir):
73+
logging.info(f'Script launched with --remove-prev-target-dir flag')
74+
logging.info(f'Removing --target-dir="{target_dir}"')
75+
shutil.rmtree(target_dir)
76+
77+
if not os.path.exists(target_dir):
78+
logging.info(
79+
f'--target-dir="{target_dir}" does not exist, creating')
80+
os.makedirs(target_dir, exist_ok=False)
81+
assert os.path.isdir(
82+
target_dir), f'Failed to create --target-dir: "{target_dir}"'
83+
84+
snippets = []
85+
86+
for subdir, _, files in os.walk(src_dir):
87+
for filename in files:
88+
if filename.lower().endswith('.md'):
89+
filepath = os.path.join(subdir, filename)
90+
logging.debug(f'Extracting snippets from {filename}')
91+
snippets.extend(extract_snippets(filepath))
92+
93+
n_snippets = len(snippets)
94+
for snippet_idx, snippet in enumerate(snippets, start=1):
95+
logging.debug(
96+
f'({snippet_idx}/{n_snippets}) writing snippet {snippet.name} to "{target_dir}"')
97+
write_snippet(target_dir, snippet)
98+
99+
logging.info(
100+
f'All done, {n_snippets} snippets have been written to "{target_dir}"')
101+
102+
103+
if __name__ == '__main__':
104+
parser = argparse.ArgumentParser(
105+
description='Recursively extracts specially annotation cpp code snippets from src dir with .md files')
106+
107+
parser.add_argument('--src-dir', type=str, required=True,
108+
help='path to the directory with .md source to recursively look for cpp snippets with {.cpp file=...} annotation')
109+
parser.add_argument('--target-dir', type=str, required=True,
110+
help='path to the resulting directory with .h snippets extracted from src-dir')
111+
parser.add_argument('--remove-prev-target-dir', action='store_true',
112+
help='remove --target-dir prior to generating snippets')
113+
114+
logging_level_names = list(logging.getLevelNamesMapping().keys())
115+
assert 'INFO' in logging_level_names
116+
parser.add_argument('--logging-level', type=str, choices=logging_level_names,
117+
default='INFO', help='script logging level')
118+
119+
args = parser.parse_args()
120+
121+
logging.basicConfig(
122+
stream=sys.stdout,
123+
format='%(asctime)s %(module)-15s - [%(levelname)-6s] - %(message)s',
124+
datefmt='%H:%M:%S',
125+
level=args.logging_level
126+
)
127+
128+
main(args)

‎test/src/test_2sat_new.cpp

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
#include <gtest/gtest.h>
2+
#include <gmock/gmock.h>
3+
4+
#include <vector>
5+
using namespace std;
6+
7+
#include "snippets/2sat.h"
8+
9+
namespace
10+
{
11+
TEST(TwoSAT, ExampleUsage)
12+
{
13+
TwoSatSolver::example_usage();
14+
}
15+
16+
TEST(TwoSAT, ArticleExample)
17+
{
18+
TwoSatSolver solver(3); // a, b, c
19+
solver.add_disjunction(0, false, 1, true); // a v not b
20+
solver.add_disjunction(0, true, 1, false); // not a v b
21+
solver.add_disjunction(0, true, 1, true); // not a v not b
22+
solver.add_disjunction(0, false, 2, true); // a v not c
23+
EXPECT_TRUE(solver.solve_2SAT());
24+
auto expected = vector<bool>{{false, false, false}};
25+
EXPECT_EQ(solver.assignment, expected);
26+
}
27+
28+
TEST(TwoSAT, Unsatisfiable)
29+
{
30+
TwoSatSolver solver(2); // a, b
31+
solver.add_disjunction(0, false, 1, false); // a v b
32+
solver.add_disjunction(0, false, 1, true); // a v not b
33+
solver.add_disjunction(0, true, 1, false); // not a v b
34+
solver.add_disjunction(0, true, 1, true); // not a v not b
35+
EXPECT_FALSE(solver.solve_2SAT());
36+
}
37+
38+
TEST(TwoSAT, OtherSatisfiableExample)
39+
{
40+
TwoSatSolver solver(4); // a, b, c, d
41+
solver.add_disjunction(0, false, 1, true); // a v not b
42+
solver.add_disjunction(0, true, 2, true); // not a v not c
43+
solver.add_disjunction(0, false, 1, false); // a v b
44+
solver.add_disjunction(3, false, 2, true); // d v not c
45+
solver.add_disjunction(3, false, 0, true); // d v not a
46+
EXPECT_TRUE(solver.solve_2SAT());
47+
// two solutions
48+
auto expected_1 = vector<bool>{{true, true, false, true}};
49+
auto expected_2 = vector<bool>{{true, false, false, true}};
50+
EXPECT_THAT(solver.assignment, ::testing::AnyOf(expected_1, expected_2));
51+
}
52+
53+
} // namespace

‎test/src/test_aho_korasick_new.cpp

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
#include <gtest/gtest.h>
2+
3+
#include <vector>
4+
#include <string>
5+
#include <iostream>
6+
using namespace std;
7+
8+
namespace {
9+
10+
namespace Trie {
11+
#include "snippets/aho_corasick_trie_definition.h"
12+
#include "snippets/aho_corasick_trie_add.h"
13+
} // namespace Trie
14+
15+
namespace Automaton {
16+
#include "snippets/aho_corasick_automaton.h"
17+
} // namespace Automation
18+
19+
TEST(AhoKorasick, TrieAddString)
20+
{
21+
using namespace Trie;
22+
23+
vector<string> set = {"a", "to", "tea", "ted", "ten", "i", "in", "inn"};
24+
for (string s : set) {
25+
add_string(s);
26+
}
27+
28+
EXPECT_EQ(trie.size(), 11);
29+
}
30+
31+
TEST(AhoKorasick, TrieAutomation)
32+
{
33+
using namespace Automaton;
34+
35+
vector<string> set = {"a", "ab", "bab", "bc", "bca", "c", "caa"};
36+
for (string s : set) {
37+
add_string(s);
38+
}
39+
EXPECT_EQ(t.size(), 11);
40+
41+
int v = 0;
42+
v = go(v, 'a');
43+
EXPECT_TRUE(t[v].output);
44+
v = go(v, 'b');
45+
EXPECT_TRUE(t[v].output);
46+
v = go(v, 'c');
47+
EXPECT_TRUE(t[v].output);
48+
v = go(v, 'd');
49+
EXPECT_FALSE(t[v].output);
50+
EXPECT_EQ(v, 0);
51+
v = go(v, 'b');
52+
EXPECT_FALSE(t[v].output);
53+
v = go(v, 'a');
54+
EXPECT_FALSE(t[v].output);
55+
v = go(v, 'a');
56+
EXPECT_TRUE(t[v].output);
57+
v = go(v, 'b');
58+
EXPECT_TRUE(t[v].output);
59+
}
60+
61+
} // namespace

0 commit comments

Comments
 (0)