/*============================================================================= | |
Copyright (c) 2001-2011 Joel de Guzman | |
Distributed under the Boost Software License, Version 1.0. (See accompanying | |
file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
==============================================================================*/ | |
#if !defined(BOOST_SPIRIT_TST_MARCH_09_2007_0905AM) | |
#define BOOST_SPIRIT_TST_MARCH_09_2007_0905AM | |
#if defined(_MSC_VER) | |
#pragma once | |
#endif | |
#include <boost/call_traits.hpp> | |
#include <boost/detail/iterator.hpp> | |
#include <boost/foreach.hpp> | |
#include <boost/assert.hpp> | |
namespace boost { namespace spirit { namespace qi { namespace detail | |
{ | |
// This file contains low level TST routines, not for | |
// public consumption. | |
template <typename Char, typename T> | |
struct tst_node | |
{ | |
tst_node(Char id) | |
: id(id), data(0), lt(0), eq(0), gt(0) | |
{ | |
} | |
template <typename Alloc> | |
static void | |
destruct_node(tst_node* p, Alloc* alloc) | |
{ | |
if (p) | |
{ | |
if (p->data) | |
alloc->delete_data(p->data); | |
destruct_node(p->lt, alloc); | |
destruct_node(p->eq, alloc); | |
destruct_node(p->gt, alloc); | |
alloc->delete_node(p); | |
} | |
} | |
template <typename Alloc> | |
static tst_node* | |
clone_node(tst_node* p, Alloc* alloc) | |
{ | |
if (p) | |
{ | |
tst_node* clone = alloc->new_node(p->id); | |
if (p->data) | |
clone->data = alloc->new_data(*p->data); | |
clone->lt = clone_node(p->lt, alloc); | |
clone->eq = clone_node(p->eq, alloc); | |
clone->gt = clone_node(p->gt, alloc); | |
return clone; | |
} | |
return 0; | |
} | |
template <typename Iterator, typename Filter> | |
static T* | |
find(tst_node* start, Iterator& first, Iterator last, Filter filter) | |
{ | |
if (first == last) | |
return 0; | |
Iterator i = first; | |
Iterator latest = first; | |
tst_node* p = start; | |
T* found = 0; | |
while (p && i != last) | |
{ | |
typename | |
boost::detail::iterator_traits<Iterator>::value_type | |
c = filter(*i); // filter only the input | |
if (c == p->id) | |
{ | |
if (p->data) | |
{ | |
found = p->data; | |
latest = i; | |
} | |
p = p->eq; | |
i++; | |
} | |
else if (c < p->id) | |
{ | |
p = p->lt; | |
} | |
else | |
{ | |
p = p->gt; | |
} | |
} | |
if (found) | |
first = ++latest; // one past the last matching char | |
return found; | |
} | |
template <typename Iterator, typename Alloc> | |
static T* | |
add( | |
tst_node*& start | |
, Iterator first | |
, Iterator last | |
, typename boost::call_traits<T>::param_type val | |
, Alloc* alloc) | |
{ | |
if (first == last) | |
return 0; | |
tst_node** pp = &start; | |
for(;;) | |
{ | |
typename | |
boost::detail::iterator_traits<Iterator>::value_type | |
c = *first; | |
if (*pp == 0) | |
*pp = alloc->new_node(c); | |
tst_node* p = *pp; | |
if (c == p->id) | |
{ | |
if (++first == last) | |
{ | |
if (p->data == 0) | |
p->data = alloc->new_data(val); | |
return p->data; | |
} | |
pp = &p->eq; | |
} | |
else if (c < p->id) | |
{ | |
pp = &p->lt; | |
} | |
else | |
{ | |
pp = &p->gt; | |
} | |
} | |
} | |
template <typename Iterator, typename Alloc> | |
static void | |
remove(tst_node*& p, Iterator first, Iterator last, Alloc* alloc) | |
{ | |
if (p == 0 || first == last) | |
return; | |
typename | |
boost::detail::iterator_traits<Iterator>::value_type | |
c = *first; | |
if (c == p->id) | |
{ | |
if (++first == last) | |
{ | |
if (p->data) | |
{ | |
alloc->delete_data(p->data); | |
p->data = 0; | |
} | |
} | |
remove(p->eq, first, last, alloc); | |
} | |
else if (c < p->id) | |
{ | |
remove(p->lt, first, last, alloc); | |
} | |
else | |
{ | |
remove(p->gt, first, last, alloc); | |
} | |
if (p->data == 0 && p->lt == 0 && p->eq == 0 && p->gt == 0) | |
{ | |
alloc->delete_node(p); | |
p = 0; | |
} | |
} | |
template <typename F> | |
static void | |
for_each(tst_node* p, std::basic_string<Char> prefix, F f) | |
{ | |
if (p) | |
{ | |
for_each(p->lt, prefix, f); | |
std::basic_string<Char> s = prefix + p->id; | |
for_each(p->eq, s, f); | |
if (p->data) | |
f(s, *p->data); | |
for_each(p->gt, prefix, f); | |
} | |
} | |
Char id; // the node's identity character | |
T* data; // optional data | |
tst_node* lt; // left pointer | |
tst_node* eq; // middle pointer | |
tst_node* gt; // right pointer | |
}; | |
}}}} | |
#endif |