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