string/detail/tst.hpp

0001 /*=============================================================================
0002     Copyright (c) 2001-2014 Joel de Guzman
0003
0004     Distributed under the Boost Software License, Version 1.0. (See accompanying
0005     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 ==============================================================================*/
0007 #if !defined(BOOST_SPIRIT_X3_TST_MARCH_09_2007_0905AM)
0008 #define BOOST_SPIRIT_X3_TST_MARCH_09_2007_0905AM
0009
0010 #include <boost/call_traits.hpp>
0011 #include <boost/assert.hpp>
0012
0013 #include <string>
0014
0015 namespace boost { namespace spirit { namespace x3 { namespace detail
0016 {
0017     // This file contains low level TST routines, not for
0018     // public consumption.
0019
0020     template <typename Char, typename T>
0021     struct tst_node
0022     {
0023         tst_node(Char id)
0024           : id(id), data(0), lt(0), eq(0), gt(0)
0025         {
0026         }
0027
0028         template <typename Alloc>
0029         static void
0030         destruct_node(tst_node* p, Alloc* alloc)
0031         {
0032             if (p)
0033             {
0034                 if (p->data)
0035                     alloc->delete_data(p->data);
0036                 destruct_node(p->lt, alloc);
0037                 destruct_node(p->eq, alloc);
0038                 destruct_node(p->gt, alloc);
0039                 alloc->delete_node(p);
0040             }
0041         }
0042
0043         template <typename Alloc>
0044         static tst_node*
0045         clone_node(tst_node* p, Alloc* alloc)
0046         {
0047             if (p)
0048             {
0049                 tst_node* clone = alloc->new_node(p->id);
0050                 if (p->data)
0051                     clone->data = alloc->new_data(*p->data);
0052                 clone->lt = clone_node(p->lt, alloc);
0053                 clone->eq = clone_node(p->eq, alloc);
0054                 clone->gt = clone_node(p->gt, alloc);
0055                 return clone;
0056             }
0057             return 0;
0058         }
0059
0060         template <typename Iterator, typename CaseCompare>
0061         static T*
0062         find(tst_node* start, Iterator& first, Iterator last, CaseCompare comp)
0063         {
0064             if (first == last)
0065                 return 0;
0066
0067             Iterator i = first;
0068             Iterator latest = first;
0069             tst_node* p = start;
0070             T* found = 0;
0071
0072             while (p && i != last)
0073             {
0074                 int32_t c = comp(*i,p->id);
0075                 if (c == 0)
0076                 {
0077                     if (p->data)
0078                     {
0079                         found = p->data;
0080                         latest = i;
0081                     }
0082                     p = p->eq;
0083                     i++;
0084                 }
0085                 else if (c < 0)
0086                 {
0087                     p = p->lt;
0088                 }
0089                 else
0090                 {
0091                     p = p->gt;
0092                 }
0093             }
0094
0095             if (found)
0096                 first = ++latest; // one past the last matching char
0097             return found;
0098         }
0099
0100         template <typename Iterator, typename Alloc>
0101         static T*
0102         add(
0103             tst_node*& start
0104           , Iterator first
0105           , Iterator last
0106           , typename boost::call_traits<T>::param_type val
0107           , Alloc* alloc)
0108         {
0109             if (first == last)
0110                 return 0;
0111
0112             tst_node** pp = &start;
0113             for (;;)
0114             {
0115                 auto c = *first;
0116
0117                 if (*pp == 0)
0118                     *pp = alloc->new_node(c);
0119                 tst_node* p = *pp;
0120
0121                 if (c == p->id)
0122                 {
0123                     if (++first == last)
0124                     {
0125                         if (p->data == 0)
0126                             p->data = alloc->new_data(val);
0127                         return p->data;
0128                     }
0129                     pp = &p->eq;
0130                 }
0131                 else if (c < p->id)
0132                 {
0133                     pp = &p->lt;
0134                 }
0135                 else
0136                 {
0137                     pp = &p->gt;
0138                 }
0139             }
0140         }
0141
0142         template <typename Iterator, typename Alloc>
0143         static void
0144         remove(tst_node*& p, Iterator first, Iterator last, Alloc* alloc)
0145         {
0146             if (p == 0 || first == last)
0147                 return;
0148
0149             auto c = *first;
0150
0151             if (c == p->id)
0152             {
0153                 if (++first == last)
0154                 {
0155                     if (p->data)
0156                     {
0157                         alloc->delete_data(p->data);
0158                         p->data = 0;
0159                     }
0160                 }
0161                 remove(p->eq, first, last, alloc);
0162             }
0163             else if (c < p->id)
0164             {
0165                 remove(p->lt, first, last, alloc);
0166             }
0167             else
0168             {
0169                 remove(p->gt, first, last, alloc);
0170             }
0171
0172             if (p->data == 0 && p->lt == 0 && p->eq == 0 && p->gt == 0)
0173             {
0174                 alloc->delete_node(p);
0175                 p = 0;
0176             }
0177         }
0178
0179         template <typename F>
0180         static void
0181         for_each(tst_node* p, std::basic_string<Char> prefix, F f)
0182         {
0183             if (p)
0184             {
0185                 for_each(p->lt, prefix, f);
0186                 std::basic_string<Char> s = prefix + p->id;
0187                 for_each(p->eq, s, f);
0188                 if (p->data)
0189                     f(s, *p->data);
0190                 for_each(p->gt, prefix, f);
0191             }
0192         }
0193
0194         Char id;        // the node's identity character
0195         T* data;        // optional data
0196         tst_node* lt;   // left pointer
0197         tst_node* eq;   // middle pointer
0198         tst_node* gt;   // right pointer
0199     };
0200 }}}}
0201
0202 #endif