string/detail/tst.hpp

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