← Back to branch summary

~ubuntu-branches/ubuntu/warty/aqsis/warty

« back to all changes in this revision

Viewing changes to boost/boost/spirit/utility/impl/chset/range_run.ipp

  • Committer: Bazaar Package Importer
  • Author(s): LaMont Jones
  • Date: 2004-08-24 07:25:04 UTC
  • Revision ID: james.westby@ubuntu.com-20040824072504-zf993vnevvisdsvb
Tags: upstream-0.9.1
Import upstream version 0.9.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
boost/boost/spirit/utility/impl/chset/range_run.ipp
 
1
/*=============================================================================
 
2
    Spirit v1.6.1
 
3
    Copyright (c) 2001-2003 Joel de Guzman
 
4
    http://spirit.sourceforge.net/
 
5
 
 
6
    Permission to copy, use, modify, sell and distribute this software is
 
7
    granted provided this copyright notice appears in all copies. This
 
8
    software is provided "as is" without express or implied warranty, and
 
9
    with no claim as to its suitability for any purpose.
 
10
=============================================================================*/
 
11
#ifndef BOOST_SPIRIT_RANGE_RUN_IPP
 
12
#define BOOST_SPIRIT_RANGE_RUN_IPP
 
13
 
 
14
///////////////////////////////////////////////////////////////////////////////
 
15
#include <algorithm> // for std::lower_bound
 
16
#include <boost/spirit/core/assert.hpp> // for BOOST_SPIRIT_ASSERT
 
17
#include <boost/spirit/utility/impl/chset/range_run.hpp>
 
18
#include <boost/spirit/debug.hpp>
 
19
#include <boost/limits.hpp>
 
20
 
 
21
///////////////////////////////////////////////////////////////////////////////
 
22
namespace boost { namespace spirit {
 
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
                    if (left_iter->last > r.last)
 
172
                    {
 
173
                        CharT save_last = left_iter->last;
 
174
                        left_iter->last = r.first-1;
 
175
                        run.insert(iter, range<CharT>(r.last+1, save_last));
 
176
                        return;
 
177
                    }
 
178
                    else
 
179
                    {
 
180
                        left_iter->last = r.first-1;
 
181
                    }
 
182
 
 
183
                iterator i = iter;
 
184
                while (i != run.end() && r.includes(*i))
 
185
                    i++;
 
186
                if (i != run.end() && i->includes(r.last))
 
187
                    i->first = r.last+1;
 
188
                run.erase(iter, i);
 
189
            }
 
190
        }
 
191
 
 
192
        //////////////////////////////////
 
193
        template <typename CharT>
 
194
        inline void
 
195
        range_run<CharT>::clear()
 
196
        { run.clear(); }
 
197
 
 
198
        //////////////////////////////////
 
199
        template <typename CharT>
 
200
        inline typename range_run<CharT>::const_iterator
 
201
        range_run<CharT>::begin() const
 
202
        { return run.begin(); }
 
203
 
 
204
        //////////////////////////////////
 
205
        template <typename CharT>
 
206
        inline typename range_run<CharT>::const_iterator
 
207
        range_run<CharT>::end() const
 
208
        { return run.end(); }
 
209
 
 
210
    }} // namespace utility::impl
 
211
 
 
212
}} // namespace boost::spirit
 
213
 
 
214
#endif