1 /*=============================================================================
2     Copyright (c) 2001-2011 Joel de Guzman
3 
4     Distributed under the Boost Software License, Version 1.0. (See accompanying
5     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 ==============================================================================*/
7 #if !defined(BOOST_SPIRIT_TST_MARCH_09_2007_0905AM)
8 #define BOOST_SPIRIT_TST_MARCH_09_2007_0905AM
9 
10 #if defined(_MSC_VER)
11 #pragma once
12 #endif
13 
14 #include <boost/call_traits.hpp>
15 #include <iterator> // for std::iterator_traits
16 
17 namespace boost { namespace spirit { namespace qi { namespace detail
18 {
19     // This file contains low level TST routines, not for
20     // public consumption.
21 
22     template <typename Char, typename T>
23     struct tst_node
24     {
tst_nodeboost::spirit::qi::detail::tst_node25         tst_node(Char id_)
26           : id(id_), data(0), lt(0), eq(0), gt(0)
27         {
28         }
29 
30         template <typename Alloc>
31         static void
destruct_nodeboost::spirit::qi::detail::tst_node32         destruct_node(tst_node* p, Alloc* alloc)
33         {
34             if (p)
35             {
36                 if (p->data)
37                     alloc->delete_data(p->data);
38                 destruct_node(p->lt, alloc);
39                 destruct_node(p->eq, alloc);
40                 destruct_node(p->gt, alloc);
41                 alloc->delete_node(p);
42             }
43         }
44 
45         template <typename Alloc>
46         static tst_node*
clone_nodeboost::spirit::qi::detail::tst_node47         clone_node(tst_node* p, Alloc* alloc)
48         {
49             if (p)
50             {
51                 tst_node* clone = alloc->new_node(p->id);
52                 if (p->data)
53                     clone->data = alloc->new_data(*p->data);
54                 clone->lt = clone_node(p->lt, alloc);
55                 clone->eq = clone_node(p->eq, alloc);
56                 clone->gt = clone_node(p->gt, alloc);
57                 return clone;
58             }
59             return 0;
60         }
61 
62         template <typename Iterator, typename Filter>
63         static T*
findboost::spirit::qi::detail::tst_node64         find(tst_node* start, Iterator& first, Iterator last, Filter filter)
65         {
66             if (first == last)
67                 return 0;
68 
69             Iterator i = first;
70             Iterator latest = first;
71             tst_node* p = start;
72             T* found = 0;
73 
74             while (p && i != last)
75             {
76                 typename
77                     std::iterator_traits<Iterator>::value_type
78                 c = filter(*i); // filter only the input
79 
80                 if (c == p->id)
81                 {
82                     if (p->data)
83                     {
84                         found = p->data;
85                         latest = i;
86                     }
87                     p = p->eq;
88                     i++;
89                 }
90                 else if (c < p->id)
91                 {
92                     p = p->lt;
93                 }
94                 else
95                 {
96                     p = p->gt;
97                 }
98             }
99 
100             if (found)
101                 first = ++latest; // one past the last matching char
102             return found;
103         }
104 
105         template <typename Iterator, typename Alloc>
106         static T*
addboost::spirit::qi::detail::tst_node107         add(
108             tst_node*& start
109           , Iterator first
110           , Iterator last
111           , typename boost::call_traits<T>::param_type val
112           , Alloc* alloc)
113         {
114             if (first == last)
115                 return 0;
116 
117             tst_node** pp = &start;
118             for(;;)
119             {
120                 typename
121                     std::iterator_traits<Iterator>::value_type
122                 c = *first;
123 
124                 if (*pp == 0)
125                     *pp = alloc->new_node(c);
126                 tst_node* p = *pp;
127 
128                 if (c == p->id)
129                 {
130                     if (++first == last)
131                     {
132                         if (p->data == 0)
133                             p->data = alloc->new_data(val);
134                         return p->data;
135                     }
136                     pp = &p->eq;
137                 }
138                 else if (c < p->id)
139                 {
140                     pp = &p->lt;
141                 }
142                 else
143                 {
144                     pp = &p->gt;
145                 }
146             }
147         }
148 
149         template <typename Iterator, typename Alloc>
150         static void
removeboost::spirit::qi::detail::tst_node151         remove(tst_node*& p, Iterator first, Iterator last, Alloc* alloc)
152         {
153             if (p == 0 || first == last)
154                 return;
155 
156             typename
157                 std::iterator_traits<Iterator>::value_type
158             c = *first;
159 
160             if (c == p->id)
161             {
162                 if (++first == last)
163                 {
164                     if (p->data)
165                     {
166                         alloc->delete_data(p->data);
167                         p->data = 0;
168                     }
169                 }
170                 remove(p->eq, first, last, alloc);
171             }
172             else if (c < p->id)
173             {
174                 remove(p->lt, first, last, alloc);
175             }
176             else
177             {
178                 remove(p->gt, first, last, alloc);
179             }
180 
181             if (p->data == 0 && p->lt == 0 && p->eq == 0 && p->gt == 0)
182             {
183                 alloc->delete_node(p);
184                 p = 0;
185             }
186         }
187 
188         template <typename F>
189         static void
for_eachboost::spirit::qi::detail::tst_node190         for_each(tst_node* p, std::basic_string<Char> prefix, F f)
191         {
192             if (p)
193             {
194                 for_each(p->lt, prefix, f);
195                 std::basic_string<Char> s = prefix + p->id;
196                 for_each(p->eq, s, f);
197                 if (p->data)
198                     f(s, *p->data);
199                 for_each(p->gt, prefix, f);
200             }
201         }
202 
203         Char id;        // the node's identity character
204         T* data;        // optional data
205         tst_node* lt;   // left pointer
206         tst_node* eq;   // middle pointer
207         tst_node* gt;   // right pointer
208     };
209 }}}}
210 
211 #endif
212