1/*============================================================================= 2 Copyright (c) 2001-2003 Joel de Guzman 3 http://spirit.sourceforge.net/ 4 5 Use, modification and distribution is subject to the Boost Software 6 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8=============================================================================*/ 9#ifndef BOOST_SPIRIT_RANGE_RUN_IPP 10#define BOOST_SPIRIT_RANGE_RUN_IPP 11 12/////////////////////////////////////////////////////////////////////////////// 13#include <algorithm> // for std::lower_bound 14#include <boost/spirit/home/classic/core/assert.hpp> // for BOOST_SPIRIT_ASSERT 15#include <boost/spirit/home/classic/utility/impl/chset/range_run.hpp> 16#include <boost/spirit/home/classic/debug.hpp> 17#include <boost/limits.hpp> 18 19/////////////////////////////////////////////////////////////////////////////// 20namespace boost { namespace spirit { 21 22BOOST_SPIRIT_CLASSIC_NAMESPACE_BEGIN 23 24 namespace utility { namespace impl { 25 26 /////////////////////////////////////////////////////////////////////// 27 // 28 // range class implementation 29 // 30 /////////////////////////////////////////////////////////////////////// 31 template <typename CharT> 32 inline range<CharT>::range(CharT first_, CharT last_) 33 : first(first_), last(last_) {} 34 35 ////////////////////////////////// 36 template <typename CharT> 37 inline bool 38 range<CharT>::is_valid() const 39 { return first <= last; } 40 41 ////////////////////////////////// 42 template <typename CharT> 43 inline bool 44 range<CharT>::includes(range const& r) const 45 { return (first <= r.first) && (last >= r.last); } 46 47 ////////////////////////////////// 48 template <typename CharT> 49 inline bool 50 range<CharT>::includes(CharT v) const 51 { return (first <= v) && (last >= v); } 52 53 ////////////////////////////////// 54 template <typename CharT> 55 inline bool 56 range<CharT>::overlaps(range const& r) const 57 { 58 CharT decr_first = 59 first == (std::numeric_limits<CharT>::min)() ? first : first-1; 60 CharT incr_last = 61 last == (std::numeric_limits<CharT>::max)() ? last : last+1; 62 63 return (decr_first <= r.last) && (incr_last >= r.first); 64 } 65 66 ////////////////////////////////// 67 template <typename CharT> 68 inline void 69 range<CharT>::merge(range const& r) 70 { 71 first = (std::min)(first, r.first); 72 last = (std::max)(last, r.last); 73 } 74 75 /////////////////////////////////////////////////////////////////////// 76 // 77 // range_run class implementation 78 // 79 /////////////////////////////////////////////////////////////////////// 80 template <typename CharT> 81 inline bool 82 range_run<CharT>::test(CharT v) const 83 { 84 if (!run.empty()) 85 { 86 const_iterator iter = 87 std::lower_bound( 88 run.begin(), run.end(), v, 89 range_char_compare<CharT>() 90 ); 91 92 if (iter != run.end() && iter->includes(v)) 93 return true; 94 if (iter != run.begin()) 95 return (--iter)->includes(v); 96 } 97 return false; 98 } 99 100 ////////////////////////////////// 101 template <typename CharT> 102 inline void 103 range_run<CharT>::swap(range_run& rr) 104 { run.swap(rr.run); } 105 106 ////////////////////////////////// 107 template <typename CharT> 108 void 109 range_run<CharT>::merge(iterator iter, range<CharT> const& r) 110 { 111 iter->merge(r); 112 iterator i = iter + 1; 113 114 while (i != run.end() && iter->overlaps(*i)) 115 iter->merge(*i++); 116 117 run.erase(iter+1, i); 118 } 119 120 ////////////////////////////////// 121 template <typename CharT> 122 void 123 range_run<CharT>::set(range<CharT> const& r) 124 { 125 BOOST_SPIRIT_ASSERT(r.is_valid()); 126 if (!run.empty()) 127 { 128 iterator iter = 129 std::lower_bound( 130 run.begin(), run.end(), r, 131 range_compare<CharT>() 132 ); 133 134 if ((iter != run.end() && iter->includes(r)) || 135 ((iter != run.begin()) && (iter - 1)->includes(r))) 136 return; 137 138 if (iter != run.begin() && (iter - 1)->overlaps(r)) 139 merge(--iter, r); 140 141 else if (iter != run.end() && iter->overlaps(r)) 142 merge(iter, r); 143 144 else 145 run.insert(iter, r); 146 } 147 else 148 { 149 run.push_back(r); 150 } 151 } 152 153 ////////////////////////////////// 154 template <typename CharT> 155 void 156 range_run<CharT>::clear(range<CharT> const& r) 157 { 158 BOOST_SPIRIT_ASSERT(r.is_valid()); 159 if (!run.empty()) 160 { 161 iterator iter = 162 std::lower_bound( 163 run.begin(), run.end(), r, 164 range_compare<CharT>() 165 ); 166 167 iterator left_iter; 168 169 if ((iter != run.begin()) && 170 (left_iter = (iter - 1))->includes(r.first)) 171 { 172 if (left_iter->last > r.last) 173 { 174 CharT save_last = left_iter->last; 175 left_iter->last = r.first-1; 176 run.insert(iter, range<CharT>(r.last+1, save_last)); 177 return; 178 } 179 else 180 { 181 left_iter->last = r.first-1; 182 } 183 } 184 185 iterator i = iter; 186 while (i != run.end() && r.includes(*i)) 187 i++; 188 if (i != run.end() && i->includes(r.last)) 189 i->first = r.last+1; 190 run.erase(iter, i); 191 } 192 } 193 194 ////////////////////////////////// 195 template <typename CharT> 196 inline void 197 range_run<CharT>::clear() 198 { run.clear(); } 199 200 ////////////////////////////////// 201 template <typename CharT> 202 inline typename range_run<CharT>::const_iterator 203 range_run<CharT>::begin() const 204 { return run.begin(); } 205 206 ////////////////////////////////// 207 template <typename CharT> 208 inline typename range_run<CharT>::const_iterator 209 range_run<CharT>::end() const 210 { return run.end(); } 211 212 }} // namespace utility::impl 213 214BOOST_SPIRIT_CLASSIC_NAMESPACE_END 215 216}} // namespace boost::spirit 217 218#endif 219