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_RANGE_RUN_MAY_16_2006_0807_PM) 8 #define BOOST_SPIRIT_RANGE_RUN_MAY_16_2006_0807_PM 9 10 #if defined(_MSC_VER) 11 #pragma once 12 #endif 13 14 #include <boost/spirit/home/support/char_set/range_functions.hpp> 15 #include <boost/assert.hpp> 16 #include <algorithm> 17 18 namespace boost { namespace spirit { namespace support { namespace detail 19 { 20 template <typename Run, typename Iterator, typename Range> 21 inline bool try_merge(Run & run,Iterator iter,Range const & range)22 try_merge(Run& run, Iterator iter, Range const& range) 23 { 24 // if *iter intersects with, or is adjacent to, 'range'... 25 if (can_merge(*iter, range)) 26 { 27 // merge range and *iter 28 merge(*iter, range); 29 30 // collapse all subsequent ranges that can merge with *iter: 31 Iterator i = iter+1; 32 // 1. skip subsequent ranges completely included in *iter 33 while (i != run.end() && i->last <= iter->last) 34 ++i; 35 // 2. collapse next range if adjacent or overlapping with *iter 36 if (i != run.end() && i->first-1 <= iter->last) 37 { 38 iter->last = i->last; 39 ++i; 40 } 41 42 // erase all ranges that were collapsed 43 run.erase(iter+1, i); 44 return true; 45 } 46 return false; 47 } 48 49 template <typename Char> 50 inline bool test(Char val) const51 range_run<Char>::test(Char val) const 52 { 53 if (run.empty()) 54 return false; 55 56 // search the ranges for one that potentially includes val 57 typename storage_type::const_iterator iter = 58 std::upper_bound( 59 run.begin(), run.end(), val, 60 range_compare<range_type>() 61 ); 62 63 // return true if *(iter-1) includes val 64 return iter != run.begin() && includes(*(--iter), val); 65 } 66 67 template <typename Char> 68 inline void swap(range_run & other)69 range_run<Char>::swap(range_run& other) 70 { 71 run.swap(other.run); 72 } 73 74 template <typename Char> 75 void set(range_type const & range)76 range_run<Char>::set(range_type const& range) 77 { 78 BOOST_ASSERT(is_valid(range)); 79 if (run.empty()) 80 { 81 // the vector is empty, insert 'range' 82 run.push_back(range); 83 return; 84 } 85 86 // search the ranges for one that potentially includes 'range' 87 typename storage_type::iterator iter = 88 std::upper_bound( 89 run.begin(), run.end(), range, 90 range_compare<range_type>() 91 ); 92 93 if (iter != run.begin()) 94 { 95 // if *(iter-1) includes 'range', return early 96 if (includes(*(iter-1), range)) 97 { 98 return; 99 } 100 101 // if *(iter-1) can merge with 'range', merge them and return 102 if (try_merge(run, iter-1, range)) 103 { 104 return; 105 } 106 } 107 108 // if *iter can merge with with 'range', merge them 109 if (iter == run.end() || !try_merge(run, iter, range)) 110 { 111 // no overlap, insert 'range' 112 run.insert(iter, range); 113 } 114 } 115 116 template <typename Char> 117 void clear(range_type const & range)118 range_run<Char>::clear(range_type const& range) 119 { 120 BOOST_ASSERT(is_valid(range)); 121 if (!run.empty()) 122 { 123 // search the ranges for one that potentially includes 'range' 124 typename storage_type::iterator iter = 125 std::upper_bound( 126 run.begin(), run.end(), range, 127 range_compare<range_type>() 128 ); 129 130 // 'range' starts with or after another range: 131 if (iter != run.begin()) 132 { 133 typename storage_type::iterator const left_iter = iter-1; 134 135 // 'range' starts after '*left_iter': 136 if (left_iter->first < range.first) 137 { 138 // if 'range' is completely included inside '*left_iter': 139 // need to break it apart into two ranges (punch a hole), 140 if (left_iter->last > range.last) 141 { 142 Char save_last = left_iter->last; 143 left_iter->last = range.first-1; 144 run.insert(iter, range_type(range.last+1, save_last)); 145 return; 146 } 147 // if 'range' contains 'left_iter->last': 148 // truncate '*left_iter' (clip its right) 149 else if (left_iter->last >= range.first) 150 { 151 left_iter->last = range.first-1; 152 } 153 } 154 155 // 'range' has the same left bound as '*left_iter': it 156 // must be removed or truncated by the code below 157 else 158 { 159 iter = left_iter; 160 } 161 } 162 163 // remove or truncate subsequent ranges that overlap with 'range': 164 typename storage_type::iterator i = iter; 165 // 1. skip subsequent ranges completely included in 'range' 166 while (i != run.end() && i->last <= range.last) 167 ++i; 168 // 2. clip left of next range if overlapping with 'range' 169 if (i != run.end() && i->first <= range.last) 170 i->first = range.last+1; 171 172 // erase all ranges that 'range' contained 173 run.erase(iter, i); 174 } 175 } 176 177 template <typename Char> 178 inline void clear()179 range_run<Char>::clear() 180 { 181 run.clear(); 182 } 183 }}}} 184 185 #endif 186