ceph/src/boost/boost/date_time/string_parse_tree.hpp

   1 #ifndef BOOST_DATE_TIME_STRING_PARSE_TREE___HPP__
   2 #define BOOST_DATE_TIME_STRING_PARSE_TREE___HPP__
   3
   4 /* Copyright (c) 2004-2005 CrystalClear Software, Inc.
   5  * Use, modification and distribution is subject to the
   6  * Boost Software License, Version 1.0. (See accompanying
   7  * file LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
   8  * Author: Jeff Garland, Bart Garst
   9  * $Date$
  10  */
  11
  12
  13 #include "boost/lexical_cast.hpp" //error without?
  14 #include "boost/algorithm/string/case_conv.hpp"
  15 #include <map>
  16 #include <string>
  17 #include <vector>
  18 #include <algorithm>
  19
  20 namespace boost { namespace date_time {
  21
  22
  23 template<typename charT>
  24 struct parse_match_result
  25 {
  26   parse_match_result() :
  27     match_depth(0),
  28     current_match(PARSE_ERROR)
  29   {}
  30   typedef std::basic_string<charT> string_type;
  31   string_type remaining() const
  32   {
  33     if (match_depth == cache.size()) {
  34       return string_type();
  35     }
  36     if (current_match == PARSE_ERROR) {
  37       return cache;
  38     }
  39     //some of the cache was used return the rest
  40     return string_type(cache, match_depth);
  41   }
  42   charT last_char() const
  43   {
  44     return cache[cache.size()-1];
  45   }
  46   //! Returns true if more characters were parsed than was necessary
  47   /*! Should be used in conjunction with last_char()
  48    *  to get the remaining character.
  49    */
  50   bool has_remaining() const
  51   {
  52     return (cache.size() > match_depth);
  53   }
  54
  55   // cache will hold characters that have been read from the stream
  56   string_type cache;
  57   unsigned short match_depth;
  58   short current_match;
  59   enum PARSE_STATE { PARSE_ERROR = -1 };
  60 };
  61
  62   //for debug -- really only char streams...
  63 template<typename charT>
  64 std::basic_ostream<charT>&
  65 operator<<(std::basic_ostream<charT>& os, parse_match_result<charT>& mr)
  66 {
  67   os << "cm: " << mr.current_match
  68      << " C: '" << mr.cache
  69      << "' md: " << mr.match_depth
  70      << " R: " << mr.remaining();
  71   return os;
  72 }
  73
  74
  75
  76 //! Recursive data structure to allow efficient parsing of various strings
  77 /*! This class provides a quick lookup by building what amounts to a
  78  *  tree data structure.  It also features a match function which can
  79  *  can handle nasty input interators by caching values as it recurses
  80  *  the tree so that it can backtrack as needed.
  81  */
  82 template<typename charT>
  83 struct string_parse_tree
  84 {
  85 #if BOOST_WORKAROUND( __BORLANDC__, BOOST_TESTED_AT(0x581) )
  86   typedef std::multimap<charT, string_parse_tree< charT> > ptree_coll;
  87 #else
  88   typedef std::multimap<charT, string_parse_tree > ptree_coll;
  89 #endif
  90   typedef typename ptree_coll::value_type value_type;
  91   typedef typename ptree_coll::iterator iterator;
  92   typedef typename ptree_coll::const_iterator const_iterator;
  93   typedef std::basic_string<charT> string_type;
  94   typedef std::vector<std::basic_string<charT> > collection_type;
  95   typedef parse_match_result<charT> parse_match_result_type;
  96
  97   /*! Parameter "starting_point" designates where the numbering begins.
  98    * A starting_point of zero will start the numbering at zero
  99    * (Sun=0, Mon=1, ...) were a starting_point of one starts the
 100    * numbering at one (Jan=1, Feb=2, ...). The default is zero,
 101    * negative vaules are not allowed */
 102   string_parse_tree(collection_type names, unsigned int starting_point=0) :
 103     m_value(parse_match_result_type::PARSE_ERROR)
 104   {
 105     // iterate thru all the elements and build the tree
 106     unsigned short index = 0;
 107     while (index != names.size() ) {
 108       string_type s = boost::algorithm::to_lower_copy(names[index]);
 109       insert(s, static_cast<unsigned short>(index + starting_point));
 110       index++;
 111     }
 112     //set the last tree node = index+1  indicating a value
 113     index++;
 114   }
 115
 116
 117   string_parse_tree(short value = parse_match_result_type::PARSE_ERROR) :
 118     m_value(value)
 119   {}
 120   ptree_coll m_next_chars;
 121   short m_value;
 122
 123   void insert(const string_type& s, unsigned short value)
 124   {
 125     unsigned int i = 0;
 126     iterator ti;
 127     while(i < s.size()) {
 128       if (i==0) {
 129         if (i == (s.size()-1)) {
 130           ti = m_next_chars.insert(value_type(s[i],
 131                                               string_parse_tree<charT>(value)));
 132         }
 133         else {
 134           ti = m_next_chars.insert(value_type(s[i],
 135                                               string_parse_tree<charT>()));
 136         }
 137       }
 138       else {
 139         if (i == (s.size()-1)) {
 140           ti = ti->second.m_next_chars.insert(value_type(s[i],
 141                                                          string_parse_tree<charT>(value)));
 142         }
 143
 144         else {
 145           ti = ti->second.m_next_chars.insert(value_type(s[i],
 146                                                          string_parse_tree<charT>()));
 147         }
 148
 149       }
 150       i++;
 151     }
 152   }
 153
 154
 155   //! Recursive function that finds a matching string in the tree.
 156   /*! Must check match_results::has_remaining() after match() is
 157    * called. This is required so the user can determine if
 158    * stream iterator is already pointing to the expected
 159    * character or not (match() might advance sitr to next char in stream).
 160    *
 161    * A parse_match_result that has been returned from a failed match
 162    * attempt can be sent in to the match function of a different
 163    * string_parse_tree to attempt a match there. Use the iterators
 164    * for the partially consumed stream, the parse_match_result object,
 165    * and '0' for the level parameter. */
 166   short
 167   match(std::istreambuf_iterator<charT>& sitr,
 168         std::istreambuf_iterator<charT>& stream_end,
 169         parse_match_result_type& result,
 170         unsigned int& level)  const
 171   {
 172
 173     level++;
 174     charT c;
 175     // if we conditionally advance sitr, we won't have
 176     // to consume the next character past the input
 177     bool adv_itr = true;
 178     if (level > result.cache.size()) {
 179       if (sitr == stream_end) return 0; //bail - input exhausted
 180       c = static_cast<charT>(std::tolower(*sitr));
 181       //result.cache += c;
 182       //sitr++;
 183     }
 184     else {
 185       // if we're looking for characters from the cache,
 186       // we don't want to increment sitr
 187       adv_itr = false;
 188       c = static_cast<charT>(std::tolower(result.cache[level-1]));
 189     }
 190     const_iterator litr = m_next_chars.lower_bound(c);
 191     const_iterator uitr = m_next_chars.upper_bound(c);
 192     while (litr != uitr) { // equal if not found
 193       if(adv_itr) {
 194         sitr++;
 195         result.cache += c;
 196       }
 197       if (litr->second.m_value != -1) { // -1 is default value
 198         if (result.match_depth < level) {
 199           result.current_match = litr->second.m_value;
 200           result.match_depth = static_cast<unsigned short>(level);
 201         }
 202         litr->second.match(sitr, stream_end,
 203                            result, level);
 204         level--;
 205       }
 206       else {
 207         litr->second.match(sitr, stream_end,
 208                            result, level);
 209         level--;
 210       }
 211
 212       if(level <= result.cache.size()) {
 213         adv_itr = false;
 214       }
 215
 216       litr++;
 217     }
 218     return result.current_match;
 219
 220   }
 221
 222   /*! Must check match_results::has_remaining() after match() is
 223    * called. This is required so the user can determine if
 224    * stream iterator is already pointing to the expected
 225    * character or not (match() might advance sitr to next char in stream).
 226    */
 227   parse_match_result_type
 228   match(std::istreambuf_iterator<charT>& sitr,
 229         std::istreambuf_iterator<charT>& stream_end) const
 230   {
 231     // lookup to_lower of char in tree.
 232     unsigned int level = 0;
 233     //    string_type cache;
 234     parse_match_result_type result;
 235     match(sitr, stream_end, result, level);
 236     return result;
 237   }
 238
 239   void printme(std::ostream& os, int& level)
 240   {
 241     level++;
 242     iterator itr = m_next_chars.begin();
 243     iterator end = m_next_chars.end();
 244     //    os << "starting level: " << level << std::endl;
 245     while (itr != end) {
 246       os << "level:  " << level
 247          << " node:  " << itr->first
 248          << " value: " << itr->second.m_value
 249          << std::endl;
 250       itr->second.printme(os, level);
 251       itr++;
 252     }
 253     level--;
 254   }
 255
 256   void print(std::ostream& os)
 257   {
 258     int level = 0;
 259     printme(os, level);
 260   }
 261
 262   void printmatch(std::ostream& os, charT c)
 263   {
 264     iterator litr = m_next_chars.lower_bound(c);
 265     iterator uitr = m_next_chars.upper_bound(c);
 266     os << "matches for: " << c << std::endl;
 267     while (litr != uitr) {
 268       os << " node:  " << litr->first
 269          << " value: " << litr->second.m_value
 270          << std::endl;
 271       litr++;
 272     }
 273   }
 274
 275 };
 276
 277
 278 } } //namespace
 279 #endif