Skip to content

Commit 84d83bf

Browse files
mbuckombucko
committed
Add support for TreeNode problems to cpp.
1 parent e615b47 commit 84d83bf

File tree

8 files changed

+198
-22
lines changed

8 files changed

+198
-22
lines changed

‎data/languages/cpp/CMakeLists.txt‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -46,12 +46,14 @@ set(HEADER_FILES
4646
problemtest.h
4747
solutionwrapper.h
4848
stlincludes.h
49+
treenode.h
4950
typetraits.h
5051
)
5152

5253
set(SOURCE_FILES
5354
main.cpp
5455
problemtest.cpp
56+
treenode.cpp
5557
)
5658

5759
target_sources(solution_cpp PRIVATE

‎data/languages/cpp/parser.h‎

Lines changed: 80 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,11 @@
77
#include <string>
88
#include <type_traits>
99
#include <vector>
10+
#include <queue>
1011

12+
#include "treenode.h"
13+
#include "singletreenode.h"
14+
#include "treenode.h"
1115
#include "typetraits.h"
1216

1317
void removeOuterSpaces(std::string& value) {
@@ -50,7 +54,7 @@ std::string removeQuotes(const std::string& str) {
5054
return removeEncapsulatedTokens(str);
5155
}
5256

53-
std::vector<std::string> splitIgnoreBrackets(const std::string& str,
57+
std::vector<std::string> splitIgnoreBrackets(const std::string str,
5458
char delimiter) {
5559
std::vector<std::string> result;
5660
std::string token;
@@ -77,7 +81,19 @@ std::vector<std::string> splitIgnoreBrackets(const std::string& str,
7781
}
7882

7983
template <typename T>
80-
std::enable_if_t<std::is_same_v<char, T>, T> parse(std::string& value) {
84+
std::enable_if_t<std::is_same_v<bool, T>, T> parse(std::string value) {
85+
removeOuterSpaces(value);
86+
if (value != "true" && value != "false") {
87+
std::stringstream ss;
88+
ss << "Error: Invalid boolean format. Must be either \"true\" or "
89+
"\"false\". String: " << value;
90+
throw std::runtime_error(ss.str());
91+
}
92+
return value == "true" ? true : false;
93+
}
94+
95+
template <typename T>
96+
std::enable_if_t<std::is_same_v<char, T>, T> parse(std::string value) {
8197
removeOuterSpaces(value);
8298
if (value.size() != 3 || !isCharFormatOk(value)) {
8399
std::stringstream ss;
@@ -89,7 +105,7 @@ std::enable_if_t<std::is_same_v<char, T>, T> parse(std::string& value) {
89105
}
90106

91107
template <typename T>
92-
std::enable_if_t<std::is_same_v<std::string, T>, T> parse(std::string& value) {
108+
std::enable_if_t<std::is_same_v<std::string, T>, T> parse(std::string value) {
93109
removeOuterSpaces(value);
94110
if (!isStringFormatOk(value)) {
95111
std::stringstream ss;
@@ -101,17 +117,34 @@ std::enable_if_t<std::is_same_v<std::string, T>, T> parse(std::string& value) {
101117
}
102118

103119
template <typename T>
104-
std::enable_if_t<std::is_integral_v<T>, T> parse(const std::string& value) {
105-
std::string valueCopy = value;
106-
removeOuterSpaces(valueCopy);
120+
std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<bool, T>, T>
121+
parse(std::string value) {
122+
removeOuterSpaces(value);
107123
T ret{};
108-
std::stringstream ss(valueCopy);
124+
std::stringstream ss(value);
109125
ss >> ret;
110126
return ret;
111127
}
112128

113129
template <typename T>
114-
std::enable_if_t<is_vector_type<T>::value, T> parse(auto&& value) {
130+
std::enable_if_t<std::is_same_v<SingleTreeNode*, T>, T> parse(
131+
std::string value) {
132+
if (value.empty()) {
133+
std::stringstream ss;
134+
ss << "Error: Invalid TreeNode value. Value: " << value;
135+
throw std::runtime_error(ss.str());
136+
}
137+
138+
if (value == "null") {
139+
return nullptr;
140+
}
141+
142+
return new SingleTreeNode(parse<int>(std::move(value)));
143+
144+
}
145+
146+
template <typename T>
147+
std::enable_if_t<is_vector_type<T>::value, T> parse(std::string value) {
115148
using element_type = typename T::value_type;
116149
removeOuterSpaces(value);
117150
T vec;
@@ -123,10 +156,47 @@ std::enable_if_t<is_vector_type<T>::value, T> parse(auto&& value) {
123156

124157
std::vector<std::string> tokens =
125158
splitIgnoreBrackets(removeBrackets(value), ',');
126-
for (std::string& token : tokens) {
127-
vec.push_back(parse<element_type>(token));
159+
for (auto&& token : tokens) {
160+
vec.push_back(parse<element_type>(std::move(token)));
128161
}
129162
return vec;
130163
}
131164

165+
TreeNode* convertToTree(const std::vector<SingleTreeNode*>& nodes) {
166+
if (nodes.empty() || nodes[0] == nullptr) {
167+
return nullptr;
168+
}
169+
170+
SingleTreeNode* root = static_cast<SingleTreeNode*>(nodes[0]);
171+
std::queue<TreeNode*> queue;
172+
queue.push(root);
173+
174+
size_t i = 1;
175+
while (!queue.empty() && i < nodes.size()) {
176+
TreeNode* current = queue.front();
177+
queue.pop();
178+
179+
if (i < nodes.size() && nodes[i] != nullptr) {
180+
current->left = static_cast<SingleTreeNode*>(nodes[i]);
181+
queue.push(static_cast<SingleTreeNode*>(nodes[i]));
182+
}
183+
++i;
184+
185+
if (i < nodes.size() && nodes[i] != nullptr) {
186+
current->right = static_cast<SingleTreeNode*>(nodes[i]);
187+
queue.push(static_cast<SingleTreeNode*>(nodes[i]));
188+
}
189+
++i;
190+
}
191+
192+
return root;
193+
}
194+
195+
template <typename T>
196+
std::enable_if_t<std::is_same_v<TreeNode*, T>, T> parse(std::string value) {
197+
const auto vec = parse<std::vector<SingleTreeNode*>>(std::move(value));
198+
199+
return convertToTree(vec);
200+
}
201+
132202
#endif // PARSER_H

‎data/languages/cpp/printer.h‎

Lines changed: 65 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,42 +1,97 @@
11
#ifndef PRINTER_H
22
#define PRINTER_H
33

4+
#include <algorithm>
5+
46
#include <type_traits>
7+
#include <stdexcept>
58
#include <sstream>
69
#include <string>
10+
#include <vector>
11+
#include <queue>
12+
#include <iostream>
13+
#include <unordered_set>
714

15+
#include "singletreenode.h"
16+
#include "treenode.h"
817
#include "typetraits.h"
918

1019
struct Printer {
11-
template <typename T,
12-
typename std::enable_if_t<std::is_integral_v<T>, int> = 0>
20+
template <typename T>
1321
static std::string toString(const T& value) {
1422
std::stringstream ss;
1523
ss << value;
1624
return ss.str();
1725
}
1826

19-
template <typename T,
20-
typename std::enable_if_t<std::is_same_v<std::string, T>,
21-
int> = 0>
22-
static std::string toString(const T& value) {
27+
static std::string toString(const std::string& value) {
2328
return value;
2429
}
2530

26-
template <typename T,
27-
typename std::enable_if_t<is_vector_type<T>::value, int> = 0>
28-
static std::string toString(const T& value) {
31+
template <typename T>
32+
static std::string toString(const std::vector<T>& value) {
2933
std::stringstream ss;
3034
ss << "[";
3135
for (size_t i = 0; i < value.size(); ++i) {
3236
if (i != 0) {
3337
ss << ", ";
3438
}
35-
ss << value[i];
39+
ss << Printer::toString(value[i]);
3640
}
3741
ss << "]";
3842
return ss.str();
3943
}
44+
45+
static std::string toString(const SingleTreeNode* value) {
46+
if (value == nullptr) {
47+
return "null";
48+
}
49+
return Printer::toString(value->val);
50+
}
51+
52+
static std::string toString(const TreeNode* value) {
53+
const std::vector<const SingleTreeNode*> nodes = toVector(value);
54+
if (nodes.empty()) {
55+
return "[null]";
56+
}
57+
58+
return Printer::toString(nodes);
59+
}
60+
61+
private:
62+
static std::vector<const SingleTreeNode*> toVector(const TreeNode* value) {
63+
std::vector<const SingleTreeNode*> nodes;
64+
if (value == nullptr) {
65+
return nodes;
66+
}
67+
68+
std::queue<const TreeNode*> queue;
69+
std::unordered_set<const TreeNode*> visited;
70+
queue.push(value);
71+
72+
while (!queue.empty()) {
73+
const TreeNode* current = queue.front();
74+
queue.pop();
75+
76+
if (visited.count(current) > 0) {
77+
throw std::runtime_error("Circular dependency detected");
78+
}
79+
visited.insert(current);
80+
81+
if (current != nullptr) {
82+
nodes.push_back(static_cast<const SingleTreeNode*>(current));
83+
queue.push(current->left);
84+
queue.push(current->right);
85+
} else {
86+
nodes.push_back(nullptr);
87+
}
88+
}
89+
90+
nodes.erase(std::find(nodes.rbegin(), nodes.rend(), nullptr).base(),
91+
nodes.end());
92+
93+
return nodes;
94+
}
4095
};
4196

4297
#endif // PRINTER_H

‎data/languages/cpp/singletreenode.h‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
#ifndef SINGLETREENODE_H
2+
#define SINGLETREENODE_H
3+
4+
#include "treenode.h"
5+
6+
struct SingleTreeNode : public TreeNode { };
7+
8+
static_assert(sizeof(SingleTreeNode) == sizeof(TreeNode),
9+
"SingleTreeNode is not the same size as TreeNode");
10+
11+
#endif // SINGLETREENODE_H

‎data/languages/cpp/solutionwrapper.h‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22
#define SOLUTIONWRAPPER_H
33

44
#include "stlincludes.h"
5+
#include "treenode.h"
56

67
using namespace std;
78

‎data/languages/cpp/treenode.cpp‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
#include "treenode.h"
2+
3+
#include "printer.h"
4+
5+
std::string TreeNode::toString() const {
6+
return Printer::toString(this);
7+
}

‎data/languages/cpp/treenode.h‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
#ifndef TREENODE_H
2+
#define TREENODE_H
3+
4+
#include <ostream>
5+
6+
struct TreeNode {
7+
int val;
8+
TreeNode *left;
9+
TreeNode *right;
10+
11+
TreeNode() : val(0), left(nullptr), right(nullptr) {}
12+
13+
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
14+
15+
TreeNode(int x, TreeNode *left, TreeNode *right)
16+
: val(x), left(left), right(right) {}
17+
18+
private:
19+
friend std::ostream& operator<< (std::ostream& os, TreeNode node);
20+
21+
std::string toString() const;
22+
};
23+
24+
inline std::ostream& operator<< (std::ostream& os, TreeNode node) {
25+
return os << node.toString();
26+
}
27+
28+
#endif // TREENODE_H

‎src/schema/results_validation_schema.json‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -22,14 +22,16 @@
2222
"anyOf": [
2323
{"type": "string"},
2424
{"type": "integer"},
25-
{"type": "array"}
25+
{"type": "array"},
26+
{"type": "boolean"}
2627
]
2728
},
2829
"expected": {
2930
"anyOf": [
3031
{"type": "string"},
3132
{"type": "integer"},
32-
{"type": "array"}
33+
{"type": "array"},
34+
{"type": "boolean"}
3335
]
3436
},
3537
"reason": {

0 commit comments

Comments
 (0)