]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | { | |
27 | 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 | |
34 | 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* | |
49 | 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* | |
66 | 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* | |
109 | 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 | |
153 | 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 | |
192 | 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 |