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