monotone

monotone Mtn Source Tree

Root/src/boost/circular_buffer_adaptor.hpp

1// Implementation of the circular buffer adaptor.
2
3// Copyright (c) 2003
4// Jan Gaspar, Whitestein Technologies
5
6// Permission to use or copy this software for any purpose is hereby granted
7// without fee, provided the above notices are retained on all copies.
8// Permission to modify the code and to distribute modified code is granted,
9// provided the above notices are retained, and a notice that the code was
10// modified is included with the above copyright notice.
11
12// This material is provided "as is", with absolutely no warranty expressed
13// or implied. Any use is at your own risk.
14
15#if !defined(BOOST_CIRCULAR_BUFFER_ADAPTOR_HPP)
16#define BOOST_CIRCULAR_BUFFER_ADAPTOR_HPP
17
18namespace boost {
19
20/*!
21 \class circular_buffer_space_optimized
22 \brief Space optimized circular buffer container adaptor.
23 \param T The type of the elements stored in the space optimized circular buffer.
24 \param Alloc The allocator type used for all internal memory management.
25 \author <a href="mailto:jano_gaspar@yahoo.com">Jan Gaspar</a>
26 \version 1.0
27 \date 2003
28
29 For more information how to use the space optimized circular
30 buffer see the <a href="../circular_buffer_adaptor.html">
31 documentation</a>.
32*/
33template<class T, class Alloc>
34class circular_buffer_space_optimized : private circular_buffer<T, Alloc> {
35public:
36// Typedefs
37
38 typedef typename circular_buffer<T, Alloc>::value_type value_type;
39 typedef typename circular_buffer<T, Alloc>::pointer pointer;
40 typedef typename circular_buffer<T, Alloc>::const_pointer const_pointer;
41 typedef typename circular_buffer<T, Alloc>::reference reference;
42 typedef typename circular_buffer<T, Alloc>::const_reference const_reference;
43 typedef typename circular_buffer<T, Alloc>::size_type size_type;
44 typedef typename circular_buffer<T, Alloc>::difference_type difference_type;
45 typedef typename circular_buffer<T, Alloc>::allocator_type allocator_type;
46 typedef typename circular_buffer<T, Alloc>::param_value_type param_value_type;
47 typedef typename circular_buffer<T, Alloc>::const_iterator const_iterator;
48 typedef typename circular_buffer<T, Alloc>::iterator iterator;
49 typedef typename circular_buffer<T, Alloc>::const_reverse_iterator const_reverse_iterator;
50 typedef typename circular_buffer<T, Alloc>::reverse_iterator reverse_iterator;
51
52// Inherited
53
54 using circular_buffer<T, Alloc>::get_allocator;
55 using circular_buffer<T, Alloc>::begin;
56 using circular_buffer<T, Alloc>::end;
57 using circular_buffer<T, Alloc>::rbegin;
58 using circular_buffer<T, Alloc>::rend;
59 using circular_buffer<T, Alloc>::operator[];
60 using circular_buffer<T, Alloc>::at;
61 using circular_buffer<T, Alloc>::front;
62 using circular_buffer<T, Alloc>::back;
63 using circular_buffer<T, Alloc>::data;
64 using circular_buffer<T, Alloc>::size;
65 using circular_buffer<T, Alloc>::max_size;
66 using circular_buffer<T, Alloc>::empty;
67
68private:
69// Member variables
70
71 //! The capacity of the optimized circular buffer.
72 size_type m_final_capacity;
73
74public:
75// Overridden
76
77 //! See the circular_buffer source documentation.
78 bool full() const { return size() == capacity(); }
79
80 //! See the circular_buffer source documentation.
81 size_type capacity() const { return m_final_capacity; }
82
83 //! See the circular_buffer source documentation.
84 void set_capacity(size_type new_capacity) {
85 if (m_final_capacity > new_capacity)
86 circular_buffer<T, Alloc>::set_capacity(new_capacity);
87 m_final_capacity = new_capacity;
88 }
89
90 //! See the circular_buffer source documentation.
91 void resize(size_type new_size, param_value_type item = T()) {
92 if (new_size > size()) {
93 if (new_size > capacity())
94 m_final_capacity = new_size;
95 insert(end(), new_size - size(), item);
96 } else {
97 erase(begin(), end() - new_size);
98 }
99 }
100
101 //! See the circular_buffer source documentation.
102 explicit circular_buffer_space_optimized(
103 size_type capacity,
104 const allocator_type& a = allocator_type())
105 : circular_buffer<T, Alloc>(0, a), m_final_capacity(capacity) {}
106
107 //! See the circular_buffer source documentation.
108 circular_buffer_space_optimized(
109 size_type capacity,
110 param_value_type item,
111 const allocator_type& a = allocator_type())
112 : circular_buffer<T, Alloc>(capacity, item, a), m_final_capacity(capacity) {}
113
114 // Default copy constructor
115
116 //! See the circular_buffer source documentation.
117 template <class InputIterator>
118 circular_buffer_space_optimized(
119 size_type capacity,
120 InputIterator first,
121 InputIterator last,
122 const allocator_type& a = allocator_type())
123 : circular_buffer<T, Alloc>(init_capacity(capacity, first, last), first, last, a)
124 , m_final_capacity(capacity) {}
125
126 // Default destructor
127
128 // Default assign operator
129
130 //! See the circular_buffer source documentation.
131 void assign(size_type n, param_value_type item) {
132 if (n > m_final_capacity)
133 m_final_capacity = n;
134 circular_buffer<T, Alloc>::assign(n, item);
135 }
136
137 //! See the circular_buffer source documentation.
138 template <class InputIterator>
139 void assign(InputIterator first, InputIterator last) {
140 circular_buffer<T, Alloc>::assign(first, last);
141 size_type capacity = circular_buffer<T, Alloc>::capacity();
142 if (capacity > m_final_capacity)
143 m_final_capacity = capacity;
144 }
145
146 //! See the circular_buffer source documentation.
147 void swap(circular_buffer_space_optimized& cb) {
148 std::swap(m_final_capacity, cb.m_final_capacity);
149 circular_buffer<T, Alloc>::swap(cb);
150 }
151
152 //! See the circular_buffer source documentation.
153 void push_back(param_value_type item) {
154 check_low_capacity();
155 circular_buffer<T, Alloc>::push_back(item);
156 }
157
158 //! See the circular_buffer source documentation.
159 void push_back() { push_back(value_type()); }
160
161 //! See the circular_buffer source documentation.
162 void push_front(param_value_type item) {
163 check_low_capacity();
164 circular_buffer<T, Alloc>::push_front(item);
165 }
166
167 //! See the circular_buffer source documentation.
168 void push_front() { push_front(value_type()); }
169
170 //! See the circular_buffer source documentation.
171 void pop_back() {
172 circular_buffer<T, Alloc>::pop_back();
173 check_high_capacity();
174 }
175
176 //! See the circular_buffer source documentation.
177 void pop_front() {
178 circular_buffer<T, Alloc>::pop_front();
179 check_high_capacity();
180 }
181
182 //! See the circular_buffer source documentation.
183 iterator insert(iterator pos, param_value_type item) {
184 size_type index = pos - begin();
185 check_low_capacity();
186 return circular_buffer<T, Alloc>::insert(begin() + index, item);
187 }
188
189 //! See the circular_buffer source documentation.
190 iterator insert(iterator pos) { return insert(pos, value_type()); }
191
192 //! See the circular_buffer source documentation.
193 void insert(iterator pos, size_type n, param_value_type item) {
194 size_type index = pos - begin();
195 check_low_capacity(n);
196 circular_buffer<T, Alloc>::insert(begin() + index, n, item);
197 }
198
199 //! See the circular_buffer source documentation.
200 template <class InputIterator>
201 void insert(iterator pos, InputIterator first, InputIterator last) {
202 insert(pos, first, last, cb_details::cb_iterator_category_traits<InputIterator>::tag());
203 }
204
205 //! See the circular_buffer source documentation.
206 iterator rinsert(iterator pos, param_value_type item) {
207 size_type index = pos - begin();
208 check_low_capacity();
209 return circular_buffer<T, Alloc>::rinsert(begin() + index, item);
210 }
211
212 //! See the circular_buffer source documentation.
213 iterator rinsert(iterator pos) { return rinsert(pos, value_type()); }
214
215 //! See the circular_buffer source documentation.
216 void rinsert(iterator pos, size_type n, param_value_type item) {
217 size_type index = pos - begin();
218 check_low_capacity(n);
219 circular_buffer<T, Alloc>::rinsert(begin() + index, n, item);
220 }
221
222 //! See the circular_buffer source documentation.
223 template <class InputIterator>
224 void rinsert(iterator pos, InputIterator first, InputIterator last) {
225 rinsert(pos, first, last, cb_details::cb_iterator_category_traits<InputIterator>::tag());
226 }
227
228 //! See the circular_buffer source documentation.
229 iterator erase(iterator pos) {
230 iterator it = circular_buffer<T, Alloc>::erase(pos);
231 size_type index = it - begin();
232 check_high_capacity();
233 return begin() + index;
234 }
235
236 //! See the circular_buffer source documentation.
237 iterator erase(iterator first, iterator last) {
238 iterator it = circular_buffer<T, Alloc>::erase(first, last);
239 size_type index = it - begin();
240 circular_buffer<T, Alloc>::set_capacity(size());
241 return begin() + index;
242 }
243
244 //! See the circular_buffer source documentation.
245 void clear() { circular_buffer<T, Alloc>::set_capacity(0); }
246
247private:
248// Helper methods
249
250 //! Check for low capacity.
251 /*
252 \post If the capacity is low it will be increased.
253 */
254 void check_low_capacity() {
255 if (circular_buffer<T, Alloc>::full() && size() < m_final_capacity) {
256 size_type new_capacity = empty() ? 1 : size() << 1; // (size * 2)
257 if (new_capacity > m_final_capacity)
258 new_capacity = m_final_capacity;
259 circular_buffer<T, Alloc>::set_capacity(new_capacity);
260 }
261 }
262
263 //! Check for low capacity.
264 /*
265 \post If the capacity is low it will be increased.
266 */
267 void check_low_capacity(size_type n) {
268 size_type new_capacity = size() + n;
269 if (new_capacity > m_final_capacity)
270 new_capacity = m_final_capacity;
271 if (new_capacity > circular_buffer<T, Alloc>::capacity())
272 circular_buffer<T, Alloc>::set_capacity(new_capacity);
273 }
274
275 //! Check for high capacity.
276 /*
277 \post If the capacity is high it will be decreased.
278 */
279 void check_high_capacity() {
280 size_type new_capacity = circular_buffer<T, Alloc>::capacity() >> 1; // (capacity / 2)
281 if (new_capacity >= size())
282 circular_buffer<T, Alloc>::set_capacity(new_capacity);
283 }
284
285 //! Determine the initial capacity.
286 template <class InputIterator>
287 static size_type init_capacity(size_type capacity, InputIterator first, InputIterator last) {
288 size_type diff = std::distance(first, last);
289 return diff > capacity ? capacity : diff;
290 }
291
292 //! Helper insert method.
293 template <class InputIterator>
294 void insert(iterator pos, InputIterator n, InputIterator item, cb_details::cb_int_iterator_tag) {
295 insert(pos, (size_type)n, item);
296 }
297
298 //! Helper insert method.
299 template <class InputIterator>
300 void insert(iterator pos, InputIterator first, InputIterator last, std::input_iterator_tag) {
301 size_type index = pos - begin();
302 check_low_capacity(std::distance(first, last));
303 circular_buffer<T, Alloc>::insert(begin() + index, first, last);
304 }
305
306 //! Helper rinsert method.
307 template <class InputIterator>
308 void rinsert(iterator pos, InputIterator n, InputIterator item, cb_details::cb_int_iterator_tag) {
309 rinsert(pos, (size_type)n, item);
310 }
311
312 //! Helper rinsert method.
313 template <class InputIterator>
314 void rinsert(iterator pos, InputIterator first, InputIterator last, std::input_iterator_tag) {
315 size_type index = pos - begin();
316 check_low_capacity(std::distance(first, last));
317 circular_buffer<T, Alloc>::rinsert(begin() + index, first, last);
318 }
319};
320
321// Non-member functions
322
323//! Test two space optimized circular buffers for equality.
324template <class T, class Alloc>
325inline bool operator == (const circular_buffer_space_optimized<T, Alloc>& lhs,
326 const circular_buffer_space_optimized<T, Alloc>& rhs) {
327 return lhs.size() == rhs.size() &&
328 std::equal(lhs.begin(), lhs.end(), rhs.begin());
329}
330
331//! Lexicographical comparison.
332template <class T, class Alloc>
333inline bool operator < (const circular_buffer_space_optimized<T, Alloc>& lhs,
334 const circular_buffer_space_optimized<T, Alloc>& rhs) {
335 return std::lexicographical_compare(
336 lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
337}
338
339#if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)
340
341//! Test two space optimized circular buffers for non-equality.
342template <class T, class Alloc>
343inline bool operator != (const circular_buffer_space_optimized<T, Alloc>& lhs,
344 const circular_buffer_space_optimized<T, Alloc>& rhs) {
345 return !(lhs == rhs);
346}
347
348//! Lexicographical comparison.
349template <class T, class Alloc>
350inline bool operator > (const circular_buffer_space_optimized<T, Alloc>& lhs,
351 const circular_buffer_space_optimized<T, Alloc>& rhs) {
352 return rhs < lhs;
353}
354
355//! Lexicographical comparison.
356template <class T, class Alloc>
357inline bool operator <= (const circular_buffer_space_optimized<T, Alloc>& lhs,
358 const circular_buffer_space_optimized<T, Alloc>& rhs) {
359 return !(rhs < lhs);
360}
361
362//! Lexicographical comparison.
363template <class T, class Alloc>
364inline bool operator >= (const circular_buffer_space_optimized<T, Alloc>& lhs,
365 const circular_buffer_space_optimized<T, Alloc>& rhs) {
366 return !(lhs < rhs);
367}
368
369//! Swap the contents of two space optimized circular buffers.
370template <class T, class Alloc>
371inline void swap(circular_buffer_space_optimized<T, Alloc>& lhs,
372 circular_buffer_space_optimized<T, Alloc>& rhs) {
373 lhs.swap(rhs);
374}
375
376#endif // #if !defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) || defined(BOOST_MSVC)
377
378} // namespace boost
379
380#endif // #if !defined(BOOST_CIRCULAR_BUFFER_ADAPTOR_HPP)

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status