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