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