File indexing completed on 2024-04-06 12:03:56
0001
0002
0003 #include "catch.hpp"
0004
0005 #include "DataFormats/Common/interface/Trie.h"
0006 #include "FWCore/Utilities/interface/Exception.h"
0007
0008 #include <iostream>
0009 #include <string>
0010 #include <sstream>
0011
0012 struct Print {
0013
0014
0015
0016
0017 void operator()(int v, std::string const& label) const { s_ << label << " " << v << std::endl; }
0018 mutable std::ostringstream s_;
0019 };
0020
0021 TEST_CASE("test Trie", "[Trie]") {
0022
0023
0024
0025 edm::Trie<int> trie(0);
0026 typedef edm::TrieNode<int> Node;
0027 typedef Node const* pointer;
0028 typedef edm::TrieNodeIter<int> node_iterator;
0029
0030 char tre[] = {'a', 'a', 'a'};
0031 char quattro[] = {'c', 'a', 'a', 'a'};
0032
0033 for (int j = 0; j < 3; j++) {
0034 tre[2] = 'a';
0035 quattro[3] = 'a';
0036 for (int i = 0; i < 10; i++) {
0037 trie.insert(tre, 3, i);
0038 trie.insert(quattro, 4, i);
0039 tre[2]++;
0040 quattro[3]++;
0041 }
0042 tre[1]++;
0043 quattro[2]++;
0044 }
0045
0046 SECTION("get") {
0047 CHECK(trie.find("aac", 3) == 2);
0048 CHECK(trie.find("caae", 4) == 4);
0049
0050 trie.setEntry("caag", 4, -2);
0051 CHECK(trie.find("caag", 4) == -2);
0052
0053 SECTION("no match") {
0054 CHECK(trie.find("abcd", 4) == 0);
0055 CHECK(trie.find("ca", 2) == 0);
0056 }
0057 }
0058 SECTION("display") {
0059 trie.setEntry("caag", 4, -2);
0060
0061 std::ostringstream s;
0062 trie.display(s);
0063 std::string output = R"(value[0]
0064 label[a] value[0]
0065 label[a] value[0]
0066 label[a] value[0]
0067 label[b] value[1]
0068 label[c] value[2]
0069 label[d] value[3]
0070 label[e] value[4]
0071 label[f] value[5]
0072 label[g] value[6]
0073 label[h] value[7]
0074 label[i] value[8]
0075 label[j] value[9]
0076 label[b] value[0]
0077 label[a] value[0]
0078 label[b] value[1]
0079 label[c] value[2]
0080 label[d] value[3]
0081 label[e] value[4]
0082 label[f] value[5]
0083 label[g] value[6]
0084 label[h] value[7]
0085 label[i] value[8]
0086 label[j] value[9]
0087 label[c] value[0]
0088 label[a] value[0]
0089 label[b] value[1]
0090 label[c] value[2]
0091 label[d] value[3]
0092 label[e] value[4]
0093 label[f] value[5]
0094 label[g] value[6]
0095 label[h] value[7]
0096 label[i] value[8]
0097 label[j] value[9]
0098 label[c] value[0]
0099 label[a] value[0]
0100 label[a] value[0]
0101 label[a] value[0]
0102 label[b] value[1]
0103 label[c] value[2]
0104 label[d] value[3]
0105 label[e] value[4]
0106 label[f] value[5]
0107 label[g] value[-2]
0108 label[h] value[7]
0109 label[i] value[8]
0110 label[j] value[9]
0111 label[b] value[0]
0112 label[a] value[0]
0113 label[b] value[1]
0114 label[c] value[2]
0115 label[d] value[3]
0116 label[e] value[4]
0117 label[f] value[5]
0118 label[g] value[6]
0119 label[h] value[7]
0120 label[i] value[8]
0121 label[j] value[9]
0122 label[c] value[0]
0123 label[a] value[0]
0124 label[b] value[1]
0125 label[c] value[2]
0126 label[d] value[3]
0127 label[e] value[4]
0128 label[f] value[5]
0129 label[g] value[6]
0130 label[h] value[7]
0131 label[i] value[8]
0132 label[j] value[9]
0133 )";
0134 REQUIRE_THAT(s.str(), Catch::Equals(output));
0135
0136 SECTION("ab display") {
0137 pointer pn = trie.node("ab", 2);
0138 REQUIRE(pn != nullptr);
0139 std::string output = R"(label[ ] value[0]
0140 label[a] value[0]
0141 label[b] value[1]
0142 label[c] value[2]
0143 label[d] value[3]
0144 label[e] value[4]
0145 label[f] value[5]
0146 label[g] value[6]
0147 label[h] value[7]
0148 label[i] value[8]
0149 label[j] value[9]
0150 label[c] value[0]
0151 label[a] value[0]
0152 label[b] value[1]
0153 label[c] value[2]
0154 label[d] value[3]
0155 label[e] value[4]
0156 label[f] value[5]
0157 label[g] value[6]
0158 label[h] value[7]
0159 label[i] value[8]
0160 label[j] value[9]
0161 )";
0162 std::ostringstream s;
0163 pn->display(s, 0, ' ');
0164 CHECK(s.str() == output);
0165 }
0166 }
0167 SECTION("iteration") {
0168 const std::vector<char> labels = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};
0169
0170 SECTION("ab") {
0171 node_iterator e;
0172 int value = 0;
0173 int index = 0;
0174 for (node_iterator p(trie.node("ab", 2)); p != e; p++) {
0175 CHECK(labels[index] == p.label());
0176 CHECK(value == p->value());
0177 ++value;
0178 ++index;
0179 }
0180 }
0181 SECTION("ab: string") {
0182 auto pn = trie.node("ab");
0183 auto e = pn->end();
0184 int value = 0;
0185 int index = 0;
0186 for (Node::const_iterator p = pn->begin(); p != e; p++) {
0187 CHECK(p.label() == labels[index]);
0188 CHECK(value == p->value());
0189 ++value;
0190 ++index;
0191 }
0192 }
0193 SECTION("top") {
0194 std::vector<char> labels = {'a', 'c'};
0195 int index = 0;
0196 auto e = trie.initialNode()->end();
0197 for (node_iterator p(trie.initialNode()); p != e; p++) {
0198 CHECK(p.label() == labels[index]);
0199 CHECK(p->value() == 0);
0200 ++index;
0201 }
0202 }
0203 }
0204
0205 SECTION("full walk") {
0206 trie.setEntry("caag", 4, -2);
0207 Print pr;
0208 edm::walkTrie(pr, *trie.initialNode());
0209 std::string const output = R"(a 0
0210 aa 0
0211 aaa 0
0212 aab 1
0213 aac 2
0214 aad 3
0215 aae 4
0216 aaf 5
0217 aag 6
0218 aah 7
0219 aai 8
0220 aaj 9
0221 ab 0
0222 aba 0
0223 abb 1
0224 abc 2
0225 abd 3
0226 abe 4
0227 abf 5
0228 abg 6
0229 abh 7
0230 abi 8
0231 abj 9
0232 ac 0
0233 aca 0
0234 acb 1
0235 acc 2
0236 acd 3
0237 ace 4
0238 acf 5
0239 acg 6
0240 ach 7
0241 aci 8
0242 acj 9
0243 c 0
0244 ca 0
0245 caa 0
0246 caaa 0
0247 caab 1
0248 caac 2
0249 caad 3
0250 caae 4
0251 caaf 5
0252 caag -2
0253 caah 7
0254 caai 8
0255 caaj 9
0256 cab 0
0257 caba 0
0258 cabb 1
0259 cabc 2
0260 cabd 3
0261 cabe 4
0262 cabf 5
0263 cabg 6
0264 cabh 7
0265 cabi 8
0266 cabj 9
0267 cac 0
0268 caca 0
0269 cacb 1
0270 cacc 2
0271 cacd 3
0272 cace 4
0273 cacf 5
0274 cacg 6
0275 cach 7
0276 caci 8
0277 cacj 9
0278 )";
0279 CHECK(output == pr.s_.str());
0280 }
0281
0282 SECTION("leaves iteration") {
0283 trie.setEntry("caag", 4, -2);
0284 Print pr;
0285 const std::string output = R"(aaa 0
0286 aab 1
0287 aac 2
0288 aad 3
0289 aae 4
0290 aaf 5
0291 aag 6
0292 aah 7
0293 aai 8
0294 aaj 9
0295 aba 0
0296 abb 1
0297 abc 2
0298 abd 3
0299 abe 4
0300 abf 5
0301 abg 6
0302 abh 7
0303 abi 8
0304 abj 9
0305 aca 0
0306 acb 1
0307 acc 2
0308 acd 3
0309 ace 4
0310 acf 5
0311 acg 6
0312 ach 7
0313 aci 8
0314 acj 9
0315 caaa 0
0316 caab 1
0317 caac 2
0318 caad 3
0319 caae 4
0320 caaf 5
0321 caag -2
0322 caah 7
0323 caai 8
0324 caaj 9
0325 caba 0
0326 cabb 1
0327 cabc 2
0328 cabd 3
0329 cabe 4
0330 cabf 5
0331 cabg 6
0332 cabh 7
0333 cabi 8
0334 cabj 9
0335 caca 0
0336 cacb 1
0337 cacc 2
0338 cacd 3
0339 cace 4
0340 cacf 5
0341 cacg 6
0342 cach 7
0343 caci 8
0344 cacj 9
0345 )";
0346 edm::iterateTrieLeaves(pr, *trie.initialNode());
0347 }
0348 }