Common/test/Trie_t.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 "Utilities/Testing/interface/CppUnit_testdriver.icpp"
0023 #include "cppunit/extensions/HelperMacros.h"
0024
0025 /**
0026    *
0027    * @brief Trie test suite
0028    *
0029    * <h2>Try to add/get string from trie</h2>
0030    *
0031    * @author Julien Lemoine <speedblue@happycoders.org>
0032    *
0033    */
0034
0035 class TestedmTrie : public CppUnit::TestFixture {
0036   CPPUNIT_TEST_SUITE(TestedmTrie);
0037   CPPUNIT_TEST(testString);
0038   CPPUNIT_TEST(testUnsigned);
0039   CPPUNIT_TEST(testSort);
0040   CPPUNIT_TEST_SUITE_END();
0041
0042 public:
0043   /// run all test tokenizer
0044   void testString();
0045   void testUnsigned();
0046   void testSort();
0047 };
0048
0049 CPPUNIT_TEST_SUITE_REGISTRATION(TestedmTrie);
0050
0051 #include <iostream>
0052 #include <sstream>
0053 #include <list>
0054
0055 #include "DataFormats/Common/interface/Trie.h"
0056
0057 void TestedmTrie::testString() {
0058   try {
0059     edm::Trie<std::string> strTrie(std::string(""));
0060     strTrie.insert("Premiere Chaine", 15, std::string("1er"));
0061     strTrie.insert("Deuxieme Chaine", std::string("2eme"));
0062     {
0063       const std::string &s = strTrie.find("unknown", 7);
0064       CPPUNIT_ASSERT_EQUAL(std::string(""), s);
0065     }
0066     {
0067       const std::string &s = strTrie.find("test");
0068       CPPUNIT_ASSERT_EQUAL(std::string(""), s);
0069     }
0070     {
0071       const std::string &s = strTrie.find("Premiere Chaine", 15);
0072       CPPUNIT_ASSERT_EQUAL(std::string("1er"), s);
0073     }
0074     {
0075       const std::string &s = strTrie.find("Premiere Chaine", 14);
0076       CPPUNIT_ASSERT_EQUAL(std::string(""), s);
0077     }
0078     {
0079       const std::string &s = strTrie.find("premiere Chaine", 15);
0080       CPPUNIT_ASSERT_EQUAL(std::string(""), s);
0081     }
0082     {
0083       const std::string &s = strTrie.find("Premiere Chaine ", 16);
0084       CPPUNIT_ASSERT_EQUAL(std::string(""), s);
0085     }
0086     {
0087       const std::string &s = strTrie.find("Deuxieme Chaine");
0088       CPPUNIT_ASSERT_EQUAL(std::string("2eme"), s);
0089     }
0090   } catch (const edm::Exception &e) {
0091     std::cerr << e.what() << std::endl;
0092     CPPUNIT_ASSERT(false);
0093   }
0094 }
0095
0096 void TestedmTrie::testUnsigned() {
0097   try {
0098     edm::Trie<unsigned> nbTrie(0);
0099     nbTrie.insert("un", 2, 1);
0100     nbTrie.insert("deux", 4, 2);
0101     nbTrie.insert("test", 4, 3);
0102     nbTrie.insert("tat", 4);
0103     nbTrie.insert("taa", 4);
0104     nbTrie.insert("tbp", 5);
0105     nbTrie.insert("tlp", 3, 6);
0106
0107     unsigned res = 0;
0108
0109     res = nbTrie.find("un", 2);
0110     CPPUNIT_ASSERT_EQUAL((unsigned)1, res);
0111
0112     res = nbTrie.find("Un", 2);
0113     CPPUNIT_ASSERT_EQUAL((unsigned)0, res);
0114
0115     res = nbTrie.find("UN", 2);
0116     CPPUNIT_ASSERT_EQUAL((unsigned)0, res);
0117
0118     res = nbTrie.find("", 0);
0119     CPPUNIT_ASSERT_EQUAL((unsigned)0, res);
0120
0121     res = nbTrie.find("deux");
0122     CPPUNIT_ASSERT_EQUAL((unsigned)2, res);
0123
0124     res = nbTrie.find(" deux ", 6);
0125     CPPUNIT_ASSERT_EQUAL((unsigned)0, res);
0126   } catch (const edm::Exception &e) {
0127     std::cerr << e.what() << std::endl;
0128     CPPUNIT_ASSERT(false);
0129   }
0130 }
0131
0132 void TestedmTrie::testSort() {
0133   try {
0134     //Test if trie is well sorted
0135     edm::Trie<unsigned> test(0);
0136     test.insert("acd", 3, 1);
0137     test.insert("ade", 3, 2);
0138     test.insert("abc", 3, 3);
0139     test.insert("ace", 3, 4);
0140     test.insert("adc", 3, 5);
0141     test.insert("abe", 3, 6);
0142     test.insert("acc", 3, 7);
0143     test.insert("add", 3, 8);
0144     test.insert("abd", 3, 9);
0145     const edm::TrieNode<unsigned> *first = test.initialNode(), *last = 0x0;
0146     CPPUNIT_ASSERT_EQUAL((unsigned)0, first->value());
0147     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)first->brother());
0148     CPPUNIT_ASSERT_EQUAL((unsigned char)'a', first->subNodeLabel());
0149     // Get one first sub node
0150     first = first->subNode();  //a*
0151     CPPUNIT_ASSERT_EQUAL((unsigned)0, first->value());
0152     CPPUNIT_ASSERT(first != 0x0);
0153
0154     // There is no other letter than a
0155     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)first->brother());
0156
0157     // Get first sub node of 'a'
0158     CPPUNIT_ASSERT(first->subNode() != 0x0);
0159     CPPUNIT_ASSERT_EQUAL((unsigned char)'b', first->subNodeLabel());
0160     first = first->subNode();  //ab*
0161     CPPUNIT_ASSERT_EQUAL((unsigned)0, first->value());
0162     CPPUNIT_ASSERT(first->subNode() != 0x0);
0163     CPPUNIT_ASSERT_EQUAL((unsigned char)'c', first->subNodeLabel());
0164     last = first->subNode();  //abc
0165     CPPUNIT_ASSERT_EQUAL((unsigned)3, last->value());
0166     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->subNode());
0167     CPPUNIT_ASSERT(last->brother() != 0x0);
0168     CPPUNIT_ASSERT_EQUAL((unsigned char)'d', last->brotherLabel());
0169     last = last->brother();  // abd
0170     CPPUNIT_ASSERT_EQUAL((unsigned)9, last->value());
0171     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->subNode());
0172     CPPUNIT_ASSERT(last->brother() != 0x0);
0173     CPPUNIT_ASSERT_EQUAL((unsigned char)'e', last->brotherLabel());
0174     last = last->brother();  // abe
0175     CPPUNIT_ASSERT_EQUAL((unsigned)6, last->value());
0176     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->subNode());
0177     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->brother());
0178
0179     CPPUNIT_ASSERT(first->brother() != 0x0);
0180     CPPUNIT_ASSERT_EQUAL((unsigned char)'c', first->brotherLabel());
0181     first = first->brother();  //ac*
0182     CPPUNIT_ASSERT_EQUAL((unsigned)0, first->value());
0183
0184     CPPUNIT_ASSERT(first->subNode() != 0x0);
0185     CPPUNIT_ASSERT_EQUAL((unsigned char)'c', first->subNodeLabel());
0186     last = first->subNode();  //acc
0187     CPPUNIT_ASSERT_EQUAL((unsigned)7, last->value());
0188     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->subNode());
0189     CPPUNIT_ASSERT(last->brother() != 0x0);
0190     CPPUNIT_ASSERT_EQUAL((unsigned char)'d', last->brotherLabel());
0191     last = last->brother();  // acd
0192     CPPUNIT_ASSERT_EQUAL((unsigned)1, last->value());
0193     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->subNode());
0194     CPPUNIT_ASSERT(last->brother() != 0x0);
0195     CPPUNIT_ASSERT_EQUAL((unsigned char)'e', last->brotherLabel());
0196     last = last->brother();  // ace
0197     CPPUNIT_ASSERT_EQUAL((unsigned)4, last->value());
0198     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->subNode());
0199     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->brother());
0200
0201     CPPUNIT_ASSERT(first->brother() != 0x0);
0202     CPPUNIT_ASSERT_EQUAL((unsigned char)'d', first->brotherLabel());
0203     first = first->brother();  //ad*
0204     CPPUNIT_ASSERT_EQUAL((unsigned)0, first->value());
0205
0206     CPPUNIT_ASSERT(first->subNode() != 0x0);
0207     CPPUNIT_ASSERT_EQUAL((unsigned char)'c', first->subNodeLabel());
0208     last = first->subNode();  //adc
0209     CPPUNIT_ASSERT_EQUAL((unsigned)5, last->value());
0210     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->subNode());
0211     CPPUNIT_ASSERT(last->brother() != 0x0);
0212     CPPUNIT_ASSERT_EQUAL((unsigned char)'d', last->brotherLabel());
0213     last = last->brother();  // add
0214     CPPUNIT_ASSERT_EQUAL((unsigned)8, last->value());
0215     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->subNode());
0216     CPPUNIT_ASSERT(last->brother() != 0x0);
0217     CPPUNIT_ASSERT_EQUAL((unsigned char)'e', last->brotherLabel());
0218     last = last->brother();  // ade
0219     CPPUNIT_ASSERT_EQUAL((unsigned)2, last->value());
0220     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->subNode());
0221     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)last->brother());
0222     CPPUNIT_ASSERT_EQUAL((void *)0x0, (void *)first->brother());
0223   } catch (const edm::Exception &e) {
0224     std::cerr << e.what() << std::endl;
0225     CPPUNIT_ASSERT(false);
0226   }
0227 }