Common/test/test_catch2_Trie.cpp

0001 /*
0002 **
0003 ** Copyright (C) 2006 Julien Lemoine
0004 ** This program is free software; you can redistribute it and/or modify
0005 ** it under the terms of the GNU Lesser General Public License as published by
0006 ** the Free Software Foundation; either version 2 of the License, or
0007 ** (at your option) any later version.
0008 **
0009 ** This program is distributed in the hope that it will be useful,
0010 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
0011 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0012 ** GNU Lesser General Public License for more details.
0013 **
0014 ** You should have received a copy of the GNU Lesser General Public License
0015 ** along with this program; if not, write to the Free Software
0016 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
0017 **
0018 **
0019 **   modified by Vincenzo Innocente on 15/08/2007
0020 */
0021
0022 #include "catch.hpp"
0023 #include <iostream>
0024 #include <sstream>
0025 #include <list>
0026 #include <string>
0027 #include "DataFormats/Common/interface/Trie.h"
0028
0029 TEST_CASE("edm::Trie", "[Trie]") {
0030   SECTION("string") {
0031     try {
0032       edm::Trie<std::string> strTrie(std::string(""));
0033       strTrie.insert("Premiere Chaine", 15, std::string("1er"));
0034       strTrie.insert("Deuxieme Chaine", std::string("2eme"));
0035       {
0036         const std::string &s = strTrie.find("unknown", 7);
0037         REQUIRE(s == "");
0038       }
0039       {
0040         const std::string &s = strTrie.find("test");
0041         REQUIRE(s == "");
0042       }
0043       {
0044         const std::string &s = strTrie.find("Premiere Chaine", 15);
0045         REQUIRE(s == "1er");
0046       }
0047       {
0048         const std::string &s = strTrie.find("Premiere Chaine", 14);
0049         REQUIRE(s == "");
0050       }
0051       {
0052         const std::string &s = strTrie.find("premiere Chaine", 15);
0053         REQUIRE(s == "");
0054       }
0055       {
0056         const std::string &s = strTrie.find("Premiere Chaine ", 16);
0057         REQUIRE(s == "");
0058       }
0059       {
0060         const std::string &s = strTrie.find("Deuxieme Chaine");
0061         REQUIRE(s == "2eme");
0062       }
0063     } catch (const edm::Exception &e) {
0064       std::cerr << e.what() << std::endl;
0065       REQUIRE(false);
0066     }
0067   }
0068
0069   SECTION("unsigned") {
0070     try {
0071       edm::Trie<unsigned> nbTrie(0);
0072       nbTrie.insert("un", 2, 1);
0073       nbTrie.insert("deux", 4, 2);
0074       nbTrie.insert("test", 4, 3);
0075       nbTrie.insert("tat", 4);
0076       nbTrie.insert("taa", 4);
0077       nbTrie.insert("tbp", 5);
0078       nbTrie.insert("tlp", 3, 6);
0079
0080       unsigned res = 0;
0081
0082       res = nbTrie.find("un", 2);
0083       REQUIRE(res == 1u);
0084
0085       res = nbTrie.find("Un", 2);
0086       REQUIRE(res == 0u);
0087
0088       res = nbTrie.find("UN", 2);
0089       REQUIRE(res == 0u);
0090
0091       res = nbTrie.find("", 0);
0092       REQUIRE(res == 0u);
0093
0094       res = nbTrie.find("deux");
0095       REQUIRE(res == 2u);
0096
0097       res = nbTrie.find(" deux ", 6);
0098       REQUIRE(res == 0u);
0099     } catch (const edm::Exception &e) {
0100       std::cerr << e.what() << std::endl;
0101       REQUIRE(false);
0102     }
0103   }
0104
0105   SECTION("sort") {
0106     try {
0107       //Test if trie is well sorted
0108       edm::Trie<unsigned> test(0);
0109       test.insert("acd", 3, 1);
0110       test.insert("ade", 3, 2);
0111       test.insert("abc", 3, 3);
0112       test.insert("ace", 3, 4);
0113       test.insert("adc", 3, 5);
0114       test.insert("abe", 3, 6);
0115       test.insert("acc", 3, 7);
0116       test.insert("add", 3, 8);
0117       test.insert("abd", 3, 9);
0118       const edm::TrieNode<unsigned> *first = test.initialNode(), *last = 0x0;
0119       REQUIRE(first->value() == 0u);
0120       REQUIRE(first->brother() == nullptr);
0121       REQUIRE(first->subNodeLabel() == (unsigned char)'a');
0122       // Get one first sub node
0123       first = first->subNode();  //a*
0124       REQUIRE(first->value() == 0u);
0125       REQUIRE(first != nullptr);
0126       // There is no other letter than a
0127       REQUIRE(first->brother() == nullptr);
0128       // Get first sub node of 'a'
0129       REQUIRE(first->subNode() != nullptr);
0130       REQUIRE(first->subNodeLabel() == (unsigned char)'b');
0131       first = first->subNode();  //ab*
0132       REQUIRE(first->value() == 0u);
0133       REQUIRE(first->subNode() != nullptr);
0134       REQUIRE(first->subNodeLabel() == (unsigned char)'c');
0135       last = first->subNode();  //abc
0136       REQUIRE(last->value() == 3u);
0137       REQUIRE(last->subNode() == nullptr);
0138       REQUIRE(last->brother() != nullptr);
0139       REQUIRE(last->brotherLabel() == (unsigned char)'d');
0140       last = last->brother();  // abd
0141       REQUIRE(last->value() == 9u);
0142       REQUIRE(last->subNode() == nullptr);
0143       REQUIRE(last->brother() != nullptr);
0144       REQUIRE(last->brotherLabel() == (unsigned char)'e');
0145       last = last->brother();  // abe
0146       REQUIRE(last->value() == 6u);
0147       REQUIRE(last->subNode() == nullptr);
0148       REQUIRE(last->brother() == nullptr);
0149       REQUIRE(first->brother() != nullptr);
0150       REQUIRE(first->brotherLabel() == (unsigned char)'c');
0151       first = first->brother();  //ac*
0152       REQUIRE(first->value() == 0u);
0153       REQUIRE(first->subNode() != nullptr);
0154       REQUIRE(first->subNodeLabel() == (unsigned char)'c');
0155       last = first->subNode();  //acc
0156       REQUIRE(last->value() == 7u);
0157       REQUIRE(last->subNode() == nullptr);
0158       REQUIRE(last->brother() != nullptr);
0159       REQUIRE(last->brotherLabel() == (unsigned char)'d');
0160       last = last->brother();  // acd
0161       REQUIRE(last->value() == 1u);
0162       REQUIRE(last->subNode() == nullptr);
0163       REQUIRE(last->brother() != nullptr);
0164       REQUIRE(last->brotherLabel() == (unsigned char)'e');
0165       last = last->brother();  // ace
0166       REQUIRE(last->value() == 4u);
0167       REQUIRE(last->subNode() == nullptr);
0168       REQUIRE(last->brother() == nullptr);
0169       REQUIRE(first->brother() != nullptr);
0170       REQUIRE(first->brotherLabel() == (unsigned char)'d');
0171       first = first->brother();  //ad*
0172       REQUIRE(first->value() == 0u);
0173       REQUIRE(first->subNode() != nullptr);
0174       REQUIRE(first->subNodeLabel() == (unsigned char)'c');
0175       last = first->subNode();  //adc
0176       REQUIRE(last->value() == 5u);
0177       REQUIRE(last->subNode() == nullptr);
0178       REQUIRE(last->brother() != nullptr);
0179       REQUIRE(last->brotherLabel() == (unsigned char)'d');
0180       last = last->brother();  // add
0181       REQUIRE(last->value() == 8u);
0182       REQUIRE(last->subNode() == nullptr);
0183       REQUIRE(last->brother() != nullptr);
0184       REQUIRE(last->brotherLabel() == (unsigned char)'e');
0185       last = last->brother();  // ade
0186       REQUIRE(last->value() == 2u);
0187       REQUIRE(last->subNode() == nullptr);
0188       REQUIRE(last->brother() == nullptr);
0189       REQUIRE(first->brother() == nullptr);
0190     } catch (const edm::Exception &e) {
0191       std::cerr << e.what() << std::endl;
0192       REQUIRE(false);
0193     }
0194   }
0195 }