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