Line data    Source code

       1             : /*=============================================================================
       2             :     Copyright (c) 2001-2003 Joel de Guzman
       3             :     http://spirit.sourceforge.net/
       4             : 
       5             :     Use, modification and distribution is subject to the Boost Software
       6             :     License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
       7             :     http://www.boost.org/LICENSE_1_0.txt)
       8             : =============================================================================*/
       9             : #ifndef BOOST_SPIRIT_TST_IPP
      10             : #define BOOST_SPIRIT_TST_IPP
      11             : 
      12             : ///////////////////////////////////////////////////////////////////////////////
      13             : #include <boost/move/unique_ptr.hpp>
      14             : #include <boost/spirit/home/classic/core/assert.hpp>
      15             : 
      16             : ///////////////////////////////////////////////////////////////////////////////
      17             : namespace boost { namespace spirit {
      18             : 
      19             : BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN
      20             : 
      21             :     namespace impl
      22             :     {
      23             : 
      24             : ///////////////////////////////////////////////////////////////////////////////
      25             : //
      26             : //  tst class
      27             : //
      28             : //      Ternary Search Tree implementation. The data structure is faster than
      29             : //      hashing for many typical search problems especially when the search
      30             : //      interface is iterator based. Searching for a string of length k in a
      31             : //      ternary search tree with n strings will require at most O(log n+k)
      32             : //      character comparisons. TSTs are many times faster than hash tables
      33             : //      for unsuccessful searches since mismatches are discovered earlier
      34             : //      after examining only a few characters. Hash tables always examine an
      35             : //      entire key when searching.
      36             : //
      37             : //      For details see http://www.cs.princeton.edu/~rs/strings/.
      38             : //
      39             : //      *** This is a low level class and is
      40             : //          not meant for public consumption ***
      41             : //
      42             : ///////////////////////////////////////////////////////////////////////////////
      43             :     template <typename T, typename CharT>
      44             :     struct tst_node
      45             :     {
      46           0 :         tst_node(CharT value_)
      47             :         : value(value_)
      48             :         , left(0)
      49           0 :         , right(0)
      50           0 :         { middle.link = 0; }
      51             : 
      52           0 :         ~tst_node()
      53             :         {
      54           0 :             delete left;
      55           0 :             delete right;
      56           0 :             if (value)
      57           0 :                 delete middle.link;
      58             :             else
      59           0 :                 delete middle.data;
      60           0 :         }
      61             : 
      62             :         tst_node*
      63             :         clone() const
      64             :         {
      65             :             boost::movelib::unique_ptr<tst_node> copy(new tst_node(value));
      66             : 
      67             :             if (left)
      68             :                 copy->left = left->clone();
      69             :             if (right)
      70             :                 copy->right = right->clone();
      71             : 
      72             :             if (value && middle.link)
      73             :             {
      74             :                 copy->middle.link = middle.link->clone();
      75             :             }
      76             :             else
      77             :             {
      78             :                 boost::movelib::unique_ptr<T> mid_data(new T(*middle.data));
      79             :                 copy->middle.data = mid_data.release();
      80             :             }
      81             : 
      82             :             return copy.release();
      83             :         }
      84             : 
      85             :         union center {
      86             : 
      87             :             tst_node*   link;
      88             :             T*          data;
      89             :         };
      90             : 
      91             :         CharT       value;
      92             :         tst_node*   left;
      93             :         center      middle;
      94             :         tst_node*   right;
      95             :     };
      96             : 
      97             :     ///////////////////////////////////////////////////////////////////////////
      98             :     template <typename T, typename CharT>
      99             :     class tst
     100             :     {
     101             :     public:
     102             : 
     103             :         struct search_info
     104             :         {
     105             :             T*          data;
     106             :             std::size_t length;
     107             :         };
     108             : 
     109           0 :         tst()
     110           0 :         : root(0) {}
     111             : 
     112             :         tst(tst const& other)
     113             :         : root(other.root ? other.root->clone() : 0) {}
     114             : 
     115           0 :         ~tst()
     116           0 :         { delete root; }
     117             : 
     118             :         tst&
     119             :         operator=(tst const& other)
     120             :         {
     121             :             if (this != &other)
     122             :             {
     123             :                 node_t* new_root = other.root ? other.root->clone() : 0;
     124             :                 delete root;
     125             :                 root = new_root;
     126             :             }
     127             :             return *this;
     128             :         }
     129             : 
     130             :         template <typename IteratorT>
     131           0 :         T* add(IteratorT first, IteratorT const& last, T const& data)
     132             :         {
     133           0 :             if (first == last)
     134             :                 return 0;
     135             : 
     136           0 :             node_t**  np = &root;
     137           0 :             CharT   ch = *first;
     138             : 
     139           0 :             BOOST_SPIRIT_ASSERT((first == last || ch != 0)
     140             :                 && "Won't add string containing null character");
     141             : 
     142             :             for (;;)
     143             :             {
     144           0 :                 if (*np == 0 || ch == 0)
     145             :                 {
     146             :                     node_t* right = 0;
     147             :                     if (np != 0)
     148             :                         right = *np;
     149           0 :                     *np = new node_t(ch);
     150           0 :                     if (right)
     151           0 :                         (**np).right = right;
     152             :                 }
     153             : 
     154           0 :                 if (ch < (**np).value)
     155             :                 {
     156           0 :                     np = &(**np).left;
     157             :                 }
     158             :                 else
     159             :                 {
     160           0 :                     if (ch == (**np).value)
     161             :                     {
     162           0 :                         if (ch == 0)
     163             :                         {
     164           0 :                             if ((**np).middle.data == 0)
     165             :                             {
     166           0 :                                 (**np).middle.data = new T(data);
     167           0 :                                 return (**np).middle.data;
     168             :                             }
     169             :                             else
     170             :                             {
     171             :                                 //  re-addition is disallowed
     172             :                                 return 0;
     173             :                             }
     174             :                        }
     175           0 :                         ++first;
     176           0 :                         ch = (first == last) ? CharT(0) : *first;
     177           0 :                         BOOST_SPIRIT_ASSERT((first == last || ch != 0)
     178             :                             && "Won't add string containing null character");
     179           0 :                         np = &(**np).middle.link;
     180             :                     }
     181             :                     else
     182             :                     {
     183           0 :                         np = &(**np).right;
     184             :                     }
     185             :                 }
     186             :             }
     187             :         }
     188             : 
     189             :         template <typename ScannerT>
     190           0 :         search_info find(ScannerT const& scan) const
     191             :         {
     192           0 :             search_info result = { 0, 0 };
     193           0 :             if (scan.at_end()) {
     194           0 :                 return result;
     195             :             }
     196             : 
     197             :             typedef typename ScannerT::iterator_t iterator_t;
     198           0 :             node_t*     np = root;
     199           0 :             CharT       ch = *scan;
     200           0 :             iterator_t  save = scan.first;
     201           0 :             iterator_t  latest = scan.first;
     202           0 :             std::size_t latest_len = 0;
     203             : 
     204           0 :             while (np)
     205             :             {
     206             : 
     207           0 :                 if (ch < np->value) // => go left!
     208             :                 {
     209           0 :                     if (np->value == 0)
     210             :                     {
     211           0 :                         result.data = np->middle.data;
     212           0 :                         if (result.data)
     213             :                         {
     214           0 :                             latest = scan.first;
     215           0 :                             latest_len = result.length;
     216             :                         }
     217             :                     }
     218             : 
     219           0 :                     np = np->left;
     220             :                 }
     221           0 :                 else if (ch == np->value) // => go middle!
     222             :                 {
     223             :                     // Matching the null character is not allowed.
     224           0 :                     if (np->value == 0)
     225             :                     {
     226           0 :                         result.data = np->middle.data;
     227           0 :                         if (result.data)
     228             :                         {
     229           0 :                             latest = scan.first;
     230           0 :                             latest_len = result.length;
     231             :                         }
     232             :                         break;
     233             :                     }
     234             : 
     235           0 :                     ++scan;
     236           0 :                     ch = scan.at_end() ? CharT(0) : *scan;
     237           0 :                     np = np->middle.link;
     238           0 :                     ++result.length;
     239             :                 }
     240             :                 else // (ch > np->value) => go right!
     241             :                 {
     242           0 :                     if (np->value == 0)
     243             :                     {
     244           0 :                         result.data = np->middle.data;
     245           0 :                         if (result.data)
     246             :                         {
     247           0 :                             latest = scan.first;
     248           0 :                             latest_len = result.length;
     249             :                         }
     250             :                     }
     251             : 
     252           0 :                     np = np->right;
     253             :                 }
     254             :             }
     255             : 
     256           0 :             if (result.data == 0)
     257             :             {
     258           0 :                 scan.first = save;
     259             :             }
     260             :             else
     261             :             {
     262           0 :                 scan.first = latest;
     263           0 :                 result.length = latest_len;
     264             :             }
     265           0 :             return result;
     266             :         }
     267             : 
     268             :     private:
     269             : 
     270             :         typedef tst_node<T, CharT> node_t;
     271             :         node_t* root;
     272             :     };
     273             : 
     274             : ///////////////////////////////////////////////////////////////////////////////
     275             :     } // namespace impl
     276             : 
     277             : BOOST_SPIRIT_CLASSIC_NAMESPACE_END
     278             : 
     279             : }} // namespace boost::spirit
     280             : 
     281             : #endif