symbols/impl/tst.ipp

0001 /*=============================================================================
0002     Copyright (c) 2001-2003 Joel de Guzman
0003     http://spirit.sourceforge.net/
0004
0005     Use, modification and distribution is subject to the Boost Software
0006     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007     http://www.boost.org/LICENSE_1_0.txt)
0008 =============================================================================*/
0009 #ifndef BOOST_SPIRIT_TST_IPP
0010 #define BOOST_SPIRIT_TST_IPP
0011
0012 ///////////////////////////////////////////////////////////////////////////////
0013 #include <boost/move/unique_ptr.hpp>
0014 #include <boost/spirit/home/classic/core/assert.hpp>
0015
0016 ///////////////////////////////////////////////////////////////////////////////
0017 namespace boost { namespace spirit {
0018
0019 BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
0020
0021     namespace impl
0022     {
0023
0024 ///////////////////////////////////////////////////////////////////////////////
0025 //
0026 //  tst class
0027 //
0028 //      Ternary Search Tree implementation. The data structure is faster than
0029 //      hashing for many typical search problems especially when the search
0030 //      interface is iterator based. Searching for a string of length k in a
0031 //      ternary search tree with n strings will require at most O(log n+k)
0032 //      character comparisons. TSTs are many times faster than hash tables
0033 //      for unsuccessful searches since mismatches are discovered earlier
0034 //      after examining only a few characters. Hash tables always examine an
0035 //      entire key when searching.
0036 //
0037 //      For details see http://www.cs.princeton.edu/~rs/strings/.
0038 //
0039 //      *** This is a low level class and is
0040 //          not meant for public consumption ***
0041 //
0042 ///////////////////////////////////////////////////////////////////////////////
0043     template <typename T, typename CharT>
0044     struct tst_node
0045     {
0046         tst_node(CharT value_)
0047         : value(value_)
0048         , left(0)
0049         , right(0)
0050         { middle.link = 0; }
0051
0052         ~tst_node()
0053         {
0054             delete left;
0055             delete right;
0056             if (value)
0057                 delete middle.link;
0058             else
0059                 delete middle.data;
0060         }
0061
0062         tst_node*
0063         clone() const
0064         {
0065             boost::movelib::unique_ptr<tst_node> copy(new tst_node(value));
0066
0067             if (left)
0068                 copy->left = left->clone();
0069             if (right)
0070                 copy->right = right->clone();
0071
0072             if (value && middle.link)
0073             {
0074                 copy->middle.link = middle.link->clone();
0075             }
0076             else
0077             {
0078                 boost::movelib::unique_ptr<T> mid_data(new T(*middle.data));
0079                 copy->middle.data = mid_data.release();
0080             }
0081
0082             return copy.release();
0083         }
0084
0085         union center {
0086
0087             tst_node*   link;
0088             T*          data;
0089         };
0090
0091         CharT       value;
0092         tst_node*   left;
0093         center      middle;
0094         tst_node*   right;
0095     };
0096
0097     ///////////////////////////////////////////////////////////////////////////
0098     template <typename T, typename CharT>
0099     class tst
0100     {
0101     public:
0102
0103         struct search_info
0104         {
0105             T*          data;
0106             std::size_t length;
0107         };
0108
0109         tst()
0110         : root(0) {}
0111
0112         tst(tst const& other)
0113         : root(other.root ? other.root->clone() : 0) {}
0114
0115         ~tst()
0116         { delete root; }
0117
0118         tst&
0119         operator=(tst const& other)
0120         {
0121             if (this != &other)
0122             {
0123                 node_t* new_root = other.root ? other.root->clone() : 0;
0124                 delete root;
0125                 root = new_root;
0126             }
0127             return *this;
0128         }
0129
0130         template <typename IteratorT>
0131         T* add(IteratorT first, IteratorT const& last, T const& data)
0132         {
0133             if (first == last)
0134                 return 0;
0135
0136             node_t**  np = &root;
0137             CharT   ch = *first;
0138
0139             BOOST_SPIRIT_ASSERT((first == last || ch != 0)
0140                 && "Won't add string containing null character");
0141
0142             for (;;)
0143             {
0144                 if (*np == 0 || ch == 0)
0145                 {
0146                     node_t* right = 0;
0147                     if (np != 0)
0148                         right = *np;
0149                     *np = new node_t(ch);
0150                     if (right)
0151                         (**np).right = right;
0152                 }
0153
0154                 if (ch < (**np).value)
0155                 {
0156                     np = &(**np).left;
0157                 }
0158                 else
0159                 {
0160                     if (ch == (**np).value)
0161                     {
0162                         if (ch == 0)
0163                         {
0164                             if ((**np).middle.data == 0)
0165                             {
0166                                 (**np).middle.data = new T(data);
0167                                 return (**np).middle.data;
0168                             }
0169                             else
0170                             {
0171                                 //  re-addition is disallowed
0172                                 return 0;
0173                             }
0174                        }
0175                         ++first;
0176                         ch = (first == last) ? CharT(0) : *first;
0177                         BOOST_SPIRIT_ASSERT((first == last || ch != 0)
0178                             && "Won't add string containing null character");
0179                         np = &(**np).middle.link;
0180                     }
0181                     else
0182                     {
0183                         np = &(**np).right;
0184                     }
0185                 }
0186             }
0187         }
0188
0189         template <typename ScannerT>
0190         search_info find(ScannerT const& scan) const
0191         {
0192             search_info result = { 0, 0 };
0193             if (scan.at_end()) {
0194                 return result;
0195             }
0196
0197             typedef typename ScannerT::iterator_t iterator_t;
0198             node_t*     np = root;
0199             CharT       ch = *scan;
0200             iterator_t  save = scan.first;
0201             iterator_t  latest = scan.first;
0202             std::size_t latest_len = 0;
0203
0204             while (np)
0205             {
0206
0207                 if (ch < np->value) // => go left!
0208                 {
0209                     if (np->value == 0)
0210                     {
0211                         result.data = np->middle.data;
0212                         if (result.data)
0213                         {
0214                             latest = scan.first;
0215                             latest_len = result.length;
0216                         }
0217                     }
0218
0219                     np = np->left;
0220                 }
0221                 else if (ch == np->value) // => go middle!
0222                 {
0223                     // Matching the null character is not allowed.
0224                     if (np->value == 0)
0225                     {
0226                         result.data = np->middle.data;
0227                         if (result.data)
0228                         {
0229                             latest = scan.first;
0230                             latest_len = result.length;
0231                         }
0232                         break;
0233                     }
0234
0235                     ++scan;
0236                     ch = scan.at_end() ? CharT(0) : *scan;
0237                     np = np->middle.link;
0238                     ++result.length;
0239                 }
0240                 else // (ch > np->value) => go right!
0241                 {
0242                     if (np->value == 0)
0243                     {
0244                         result.data = np->middle.data;
0245                         if (result.data)
0246                         {
0247                             latest = scan.first;
0248                             latest_len = result.length;
0249                         }
0250                     }
0251
0252                     np = np->right;
0253                 }
0254             }
0255
0256             if (result.data == 0)
0257             {
0258                 scan.first = save;
0259             }
0260             else
0261             {
0262                 scan.first = latest;
0263                 result.length = latest_len;
0264             }
0265             return result;
0266         }
0267
0268     private:
0269
0270         typedef tst_node<T, CharT> node_t;
0271         node_t* root;
0272     };
0273
0274 ///////////////////////////////////////////////////////////////////////////////
0275     } // namespace impl
0276
0277 BOOST_SPIRIT_CLASSIC_NAMESPACE_END
0278
0279 }} // namespace boost::spirit
0280
0281 #endif