Subversion Repositories RTK

Rev

Rev 348 | Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
319 gdshaw 1
// This file is part of the RISC OS Toolkit (RTK).
2
// Copyright  2004 Graham Shaw.
3
// Distribution and use are subject to the GNU Lesser General Public License,
4
// a copy of which may be found in the file !RTK.Copyright.
5
 
6
#ifndef _RTK_UTIL_CUMULATIVE_SUM
7
#define _RTK_UTIL_CUMULATIVE_SUM
8
 
9
#include <stdexcept>
10
#include <vector>
11
 
12
namespace rtk {
13
namespace util {
14
 
15
/** A class for quickly calculating cumulative sums.
16
 * Elements may be indexed using operator[].  It is also possible to
17
 * obtain the cumulative sum up to a given index.  Both of these
18
 * operations execute in O(log n) time.
19
 */
20
template<class value_type>
21
class cumulative_sum
22
{
23
public:
24
        /** The type of the index of an element. */
25
        typedef unsigned int index_type;
26
private:
27
        /** A vector of partial sums.
28
         * If a given index, written in binary, ends in m trailing ones,
29
         * then it is a sum of 2**m elements ending at the given index.
30
         */
31
        vector<value_type> _values;
32
 
33
        class reference_type;
34
public:
35
        /** Construct cumulative sum object. */
36
        cumulative_sum();
37
 
38
        /** Index into cumulative sum.
39
         * Note that the result is a helper object, as opposed to a
40
         * true reference.
41
         */
42
        reference_type operator[](index_type index);
43
 
44
        /** Get cumulative sum up to a given index.
45
         * A std::out_of_range exception is thrown if index>size().
46
         * @param index the index
47
         * @return the cumulative sum up to but excluding that index
48
         */
49
        value_type sum(index_type index) const;
50
 
51
        /** Erase elements.
52
         * @param first the first element to be erased
53
         * @param last the last element plus one to be erased
54
         */
55
        void erase(unsigned int first,unsigned int last);
56
 
57
        /** Insert elements.
58
         * @param pos the index at which to insert
59
         * @param count the number of elements to insert
60
         * @param value the value of the elements to insert
61
         */
62
        void insert(unsigned int pos,unsigned int count,value_type value);
63
 
64
        /** Find the index after which a given cumulative sum is exceeded.
65
         * @param value the cumulative sum
66
         * @return the index at which that cumulative sum is reached
67
         */
68
        index_type find(value_type value) const;
69
 
70
        /** Get number of elements.
71
         * @return the number of elements
72
         */
73
        index_type size() const
74
                { return _values.size(); }
75
 
76
        /** Set number of elements.
77
         * @param size the required number of elements
78
         */
79
        void resize(index_type size);
80
 
81
        /** Get capacity.
82
         * @return the capacity
83
         */
84
        index_type capacity() const
85
                { return _values.capacity(); }
86
 
87
        /** Set capacity.
88
         * @param capacity the required capacity
89
         */
90
        void reserve(index_type capacity)
91
                { _values.reserve(capacity); }
92
};
93
 
94
/** A helper class for use by cumulative_sum<>::operator[]. */
95
template<class value_type>
96
class cumulative_sum<value_type>::reference_type
97
{
98
private:
99
        /** A reference to the vector of partial sums. */
100
        vector<value_type>& _values;
101
 
102
        /** The index of the element to which this object refers. */
103
        index_type _index;
104
public:
105
        /** Create helper object.
106
         * @param values the vector of partial sums
107
         * @param idnex the index of the element to which this object refers
108
         */
109
        reference_type(vector<value_type>& values,index_type index);
110
 
111
        /** Set value of element.
112
         * @param value the required value of the element
113
         */
114
        reference_type& operator=(const value_type& value);
115
 
116
        /** Get value of element.
117
         * @return the value of the element
118
         */
119
        operator value_type() const;
120
};
121
 
122
template<class value_type>
123
cumulative_sum<value_type>::cumulative_sum()
124
{}
125
 
126
template<class value_type>
127
cumulative_sum<value_type>::reference_type
128
cumulative_sum<value_type>::operator[](index_type index)
129
{
130
        if (index>=_values.size())
131
        {
132
                throw std::out_of_range(
133
                        "index out of range in rtk::util::cumulative_sum");
134
        }
135
        return reference_type(_values,index);
136
}
137
 
138
template<class value_type>
139
value_type cumulative_sum<value_type>::sum(index_type index) const
140
{
141
        if (index>_values.size())
142
                throw out_of_range("index out of range in rtk::util::cumulative_sum");
143
        value_type value=0;
144
        index_type i=index;
145
        while (i)
146
        {
147
                value+=_values[i-1];
148
                i&=i-1;
149
        }
150
        return value;
151
}
152
 
153
template<class value_type>
154
void cumulative_sum<value_type>::erase(unsigned int first,unsigned int last)
155
{
156
        if ((first>last)||(last>_values.size()))
157
                throw out_of_range("index out of range in rtk::util::cumulative_sum");
158
 
159
        for (unsigned int i=first,j=last;j!=_values.size();++i,++j)
160
        {
161
                (*this)[i]=value_type((*this)[j]);
162
        }
163
 
164
        _values.resize(_values.size()-(last-first));
165
}
166
 
167
template<class value_type>
168
void cumulative_sum<value_type>::insert(unsigned int pos,unsigned int count,
169
        value_type value)
170
{
171
        _values.resize(_values.size()+count,0);
172
 
173
        for (unsigned int i=_values.size(),j=_values.size()-count;j!=pos;--i,--j)
174
        {
175
                (*this)[i-1]=value_type((*this)[j-1]);
176
        }
177
 
178
        for (unsigned int i=pos+count;i!=pos;--i)
179
        {
180
                (*this)[i-1]=value;
181
        }
182
}
183
 
184
template<class value_type>
185
cumulative_sum<value_type>::index_type
186
cumulative_sum<value_type>::find(value_type value) const
187
{
188
        index_type index=0;
189
 
190
        index_type i=1;
191
        while (i<=_values.size()) i<<=1;
192
        i>>=1;
193
 
194
        while (i)
195
        {
196
                unsigned int j=index+i-1;
197
                if ((j<_values.size())&&(_values[j]<=value))
198
                {
199
                        value-=_values[j];
200
                        index+=i;
201
                }
202
                i>>=1;
203
        }
204
 
205
        return index;
206
}
207
 
208
template<class value_type>
209
void cumulative_sum<value_type>::resize(index_type size)
210
{
211
        index_type old_size=size;
212
        _values.resize(size,0);
213
 
214
        for (unsigned int i=old_size;i!=size;++i)
215
        {
216
                (*this)[i]=0;
217
        }
218
}
219
 
220
template<class value_type>
221
cumulative_sum<value_type>::reference_type::reference_type(
222
        vector<value_type>& values,index_type index):
223
        _values(values),
224
        _index(index)
225
{}
226
 
227
template<class value_type>
228
cumulative_sum<value_type>::reference_type&
229
cumulative_sum<value_type>::reference_type::operator=(const value_type& value)
230
{
231
        value_type diff=value;
232
 
233
        index_type i=_index+1;
234
        while (i)
235
        {
236
                diff-=_values[i-1];
237
                i&=i-1;
238
        }
239
 
240
        index_type j=_index;
241
        while (j)
242
        {
243
                diff+=_values[j-1];
244
                j&=j-1;
245
        }
246
 
247
        index_type k=_index;
248
        while (k<_values.size())
249
        {
250
                _values[k]+=diff;
251
                k|=k+1;
252
        }
253
 
254
        return *this;
255
}
256
 
257
template<class value_type>
258
cumulative_sum<value_type>::reference_type::operator value_type() const
259
{
260
        value_type value=0;
261
 
262
        index_type i=_index+1;
263
        while (i)
264
        {
265
                value+=_values[i-1];
266
                i&=i-1;
267
        }
268
 
269
        index_type j=_index;
270
        while (j)
271
        {
272
                value-=_values[j-1];
273
                j&=j-1;
274
        }
275
 
276
        return value;
277
}
278
 
279
}; /* namespace util */
280
}; /* namespace rtk */
281
 
282
#endif