boost/spirit/home/qi/string/detail/tst.hpp

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