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 <boost/detail/iterator.hpp>
16 #include <boost/foreach.hpp>
17 #include <boost/assert.hpp>
18 
19 namespace boost { namespace spirit { namespace qi { namespace detail
20 {
21     // This file contains low level TST routines, not for
22     // public consumption.
23 
24     template <typename Char, typename T>
25     struct tst_node
26     {
tst_nodeboost::spirit::qi::detail::tst_node27         tst_node(Char id_)
28           : id(id_), data(0), lt(0), eq(0), gt(0)
29         {
30         }
31 
32         template <typename Alloc>
33         static void
destruct_nodeboost::spirit::qi::detail::tst_node34         destruct_node(tst_node* p, Alloc* alloc)
35         {
36             if (p)
37             {
38                 if (p->data)
39                     alloc->delete_data(p->data);
40                 destruct_node(p->lt, alloc);
41                 destruct_node(p->eq, alloc);
42                 destruct_node(p->gt, alloc);
43                 alloc->delete_node(p);
44             }
45         }
46 
47         template <typename Alloc>
48         static tst_node*
clone_nodeboost::spirit::qi::detail::tst_node49         clone_node(tst_node* p, Alloc* alloc)
50         {
51             if (p)
52             {
53                 tst_node* clone = alloc->new_node(p->id);
54                 if (p->data)
55                     clone->data = alloc->new_data(*p->data);
56                 clone->lt = clone_node(p->lt, alloc);
57                 clone->eq = clone_node(p->eq, alloc);
58                 clone->gt = clone_node(p->gt, alloc);
59                 return clone;
60             }
61             return 0;
62         }
63 
64         template <typename Iterator, typename Filter>
65         static T*
findboost::spirit::qi::detail::tst_node66         find(tst_node* start, Iterator& first, Iterator last, Filter filter)
67         {
68             if (first == last)
69                 return 0;
70 
71             Iterator i = first;
72             Iterator latest = first;
73             tst_node* p = start;
74             T* found = 0;
75 
76             while (p && i != last)
77             {
78                 typename
79                     boost::detail::iterator_traits<Iterator>::value_type
80                 c = filter(*i); // filter only the input
81 
82                 if (c == p->id)
83                 {
84                     if (p->data)
85                     {
86                         found = p->data;
87                         latest = i;
88                     }
89                     p = p->eq;
90                     i++;
91                 }
92                 else if (c < p->id)
93                 {
94                     p = p->lt;
95                 }
96                 else
97                 {
98                     p = p->gt;
99                 }
100             }
101 
102             if (found)
103                 first = ++latest; // one past the last matching char
104             return found;
105         }
106 
107         template <typename Iterator, typename Alloc>
108         static T*
addboost::spirit::qi::detail::tst_node109         add(
110             tst_node*& start
111           , Iterator first
112           , Iterator last
113           , typename boost::call_traits<T>::param_type val
114           , Alloc* alloc)
115         {
116             if (first == last)
117                 return 0;
118 
119             tst_node** pp = &start;
120             for(;;)
121             {
122                 typename
123                     boost::detail::iterator_traits<Iterator>::value_type
124                 c = *first;
125 
126                 if (*pp == 0)
127                     *pp = alloc->new_node(c);
128                 tst_node* p = *pp;
129 
130                 if (c == p->id)
131                 {
132                     if (++first == last)
133                     {
134                         if (p->data == 0)
135                             p->data = alloc->new_data(val);
136                         return p->data;
137                     }
138                     pp = &p->eq;
139                 }
140                 else if (c < p->id)
141                 {
142                     pp = &p->lt;
143                 }
144                 else
145                 {
146                     pp = &p->gt;
147                 }
148             }
149         }
150 
151         template <typename Iterator, typename Alloc>
152         static void
removeboost::spirit::qi::detail::tst_node153         remove(tst_node*& p, Iterator first, Iterator last, Alloc* alloc)
154         {
155             if (p == 0 || first == last)
156                 return;
157 
158             typename
159                 boost::detail::iterator_traits<Iterator>::value_type
160             c = *first;
161 
162             if (c == p->id)
163             {
164                 if (++first == last)
165                 {
166                     if (p->data)
167                     {
168                         alloc->delete_data(p->data);
169                         p->data = 0;
170                     }
171                 }
172                 remove(p->eq, first, last, alloc);
173             }
174             else if (c < p->id)
175             {
176                 remove(p->lt, first, last, alloc);
177             }
178             else
179             {
180                 remove(p->gt, first, last, alloc);
181             }
182 
183             if (p->data == 0 && p->lt == 0 && p->eq == 0 && p->gt == 0)
184             {
185                 alloc->delete_node(p);
186                 p = 0;
187             }
188         }
189 
190         template <typename F>
191         static void
for_eachboost::spirit::qi::detail::tst_node192         for_each(tst_node* p, std::basic_string<Char> prefix, F f)
193         {
194             if (p)
195             {
196                 for_each(p->lt, prefix, f);
197                 std::basic_string<Char> s = prefix + p->id;
198                 for_each(p->eq, s, f);
199                 if (p->data)
200                     f(s, *p->data);
201                 for_each(p->gt, prefix, f);
202             }
203         }
204 
205         Char id;        // the node's identity character
206         T* data;        // optional data
207         tst_node* lt;   // left pointer
208         tst_node* eq;   // middle pointer
209         tst_node* gt;   // right pointer
210     };
211 }}}}
212 
213 #endif
214