Common/test/exTrie.cpp

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   //  typedef edm::TrieNode<int> const node;
0014   //void operator()(node& n, std::string const& label) const {
0015   //  std::cout << label << " " << n.value() << std::endl;
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   /// trie that associates a integer to strings
0023   /// 0 is the default value I want to receive when there is no match
0024   /// in trie
0025   edm::Trie<int> trie(0);
0026   typedef edm::TrieNode<int> Node;
0027   typedef Node const* pointer;  // sigh....
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 }