Bcp 1.4.4
Loading...
Searching...
No Matches
BCP_vector_general.hpp
Go to the documentation of this file.
1// Copyright (C) 2000, International Business Machines
2// Corporation and others. All Rights Reserved.
3
4//##############################################################################
5
6template <class T> inline void BCP_vec<T>::destroy(iterator pos)
7{
8 pos->~T();
9}
10//------------------------------------------------------------------------------
11template <class T> inline void BCP_vec<T>::destroy_range(iterator first, iterator last)
12{
13 while (first != last) {
14 (--last)->~T();
15 }
16}
17//------------------------------------------------------------------------------
18template <class T> inline void BCP_vec<T>::construct(iterator pos)
19{
20 ::new(static_cast<void*>(pos)) T();
21}
22//------------------------------------------------------------------------------
23template <class T> inline void BCP_vec<T>::construct(iterator pos, const_reference x)
24{
25 ::new(static_cast<void*>(pos)) T(x);
26}
27
28//##############################################################################
29template <class T> inline typename BCP_vec<T>::iterator
31{
32 return static_cast<iterator>(::operator new(len * sizeof(T)));
33}
34//------------------------------------------------------------------------------
35template <class T> inline void BCP_vec<T>::deallocate()
36{
37 if (start) {
38 destroy_range(start, finish);
39 ::operator delete(start);
40 }
41}
42//------------------------------------------------------------------------------
43template <class T> void BCP_vec<T>::insert_aux(iterator position, const_reference x)
44{
45 if (finish != end_of_storage) {
46 construct(finish);
47 std::copy_backward(position, finish - 1, finish);
48 *position = x;
49 ++finish;
50 } else {
51 const size_t len = (2*size() + 0x100);
52 iterator tmp = allocate(len);
53 iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
54 construct(tmp_finish++, x);
55 tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
56 deallocate();
57 start = tmp;
58 finish = tmp_finish;
59 end_of_storage = tmp + len;
60 }
61}
62
63//##############################################################################
64
65template <class T> BCP_vec<T>::BCP_vec() :
66 start(0), finish(0), end_of_storage(0) {}
67//------------------------------------------------------------------------------
68template <class T> BCP_vec<T>::BCP_vec(const BCP_vec<T>& x) :
69 start(0), finish(0), end_of_storage(0)
70{
71 *this = x;
72}
73//------------------------------------------------------------------------------
74template <class T>
75BCP_vec<T>::BCP_vec(const size_t n, const_reference value) :
76 start(0), finish(0), end_of_storage(0)
77{
78 if (n > 0) {
79 start = allocate(n);
81 std::uninitialized_fill_n(start, n, value);
82 }
83}
84//------------------------------------------------------------------------------
85template <class T>
87 start(0), finish(0), end_of_storage(0)
88{
89 const size_t len = last - first;
90 if (len > 0) {
91 start = allocate(len);
92 end_of_storage = finish = std::uninitialized_copy(first, last, start);
93 }
94}
95//------------------------------------------------------------------------------
96template <class T>
97BCP_vec<T>::BCP_vec(const T* x, const size_t num) :
98 start(0), finish(0), end_of_storage(0)
99{
100 if (num > 0) {
101 finish = start = allocate(num);
102 const T* const lastx = x + num;
103 while (x != lastx) {
104 construct(finish++, *x++);
105 }
107 }
108}
109
110//##############################################################################
111
112template <class T> void BCP_vec<T>::reserve(const size_t n)
113{
114 if (capacity() < n) {
115 iterator tmp = allocate(n);
116 iterator tmp_finish = std::uninitialized_copy(start, finish, tmp);
117 deallocate();
118 start = tmp;
119 finish = tmp_finish;
120 end_of_storage = start + n;
121 }
122}
123//------------------------------------------------------------------------------
124template <class T> inline void BCP_vec<T>::swap(BCP_vec<T>& x)
125{
126 std::swap(start, x.start);
127 std::swap(finish, x.finish);
128 std::swap(end_of_storage, x.end_of_storage);
129}
130//------------------------------------------------------------------------------
131template <class T> BCP_vec<T>& BCP_vec<T>::operator=(const BCP_vec<T>& x)
132{
133 if (&x != this) {
134 const size_t x_size = x.size();
135 if (x_size > capacity()) {
136 deallocate();
137 start = allocate(x_size);
138 end_of_storage = start + x_size;
139 finish = std::uninitialized_copy(x.begin(), x.end(), start);
140 } else {
141 if (x_size < size()) {
142 iterator oldfinish = finish;
143 finish = std::copy(x.begin(), x.end(), start);
144 destroy_range(finish, oldfinish);
145 } else {
146 std::copy(x.begin(), x.entry(size()), start);
147 finish = std::uninitialized_copy(x.entry(size()), x.end(), finish);
148 }
149 }
150 }
151 return *this;
152}
154//##############################################################################
155// need the void* here, since we occasionally want to copy out of a buffer
157template <class T> void BCP_vec<T>::assign(const void* x, const size_t num)
158{
159 if (num > capacity()){
160 deallocate();
161 start = allocate(num);
162 end_of_storage = start + num;
163 } else {
164 destroy_range(start, finish);
165 }
166 T entry;
167 finish = start;
168 const char* charx = static_cast<const char*>(x);
169 for (int i = num; i > 0; --i) {
170 memcpy(&entry, charx, sizeof(T));
171 construct(finish++, entry);
172 charx += sizeof(T);
173 }
174}
175//------------------------------------------------------------------------------
176template <class T> void BCP_vec<T>::insert(iterator position,
177 const void* first, const size_t n)
179 if (n == 0) return;
180 T entry;
181 const char* charx = static_cast<const char*>(first);
182 if ((size_t) (end_of_storage - finish) >= n) {
183 const size_t to_move = finish - position;
184 if (to_move <= n) {
185 std::uninitialized_copy(position, finish, position + n);
186 finish += n;
187 size_t i = n;
188 for ( ; i > to_move; --i) {
189 memcpy(&entry, charx, sizeof(T));
190 construct(position++, entry);
191 charx += sizeof(T);
192 }
193 for ( ; i > 0; --i) {
194 memcpy(&entry, charx, sizeof(T));
195 *position++ = entry;
196 charx += sizeof(T);
197 }
198 } else {
199 std::uninitialized_copy(finish - n, finish, finish);
200 std::copy_backward(position, finish - n, finish);
201 finish += n;
202 for (int i = n; i > 0; --i) {
203 memcpy(&entry, charx, sizeof(T));
204 *position++ = entry;
205 charx += sizeof(T);
207 }
208 } else {
209 const size_t new_size = (2*size() + n);
210 iterator tmp = allocate(new_size);
211 iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
212 for (int i = n; i > 0; --i) {
213 memcpy(&entry, charx, sizeof(T));
214 construct(tmp_finish++, entry);
215 charx += sizeof(T);
216 }
217 tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
218 deallocate();
219 start = tmp;
220 finish = tmp_finish;
221 end_of_storage = tmp + new_size;
222 }
223}
224//------------------------------------------------------------------------------
225template <class T> void BCP_vec<T>::insert(iterator position,
226 const_iterator first,
228{
229 if (first == last) return;
230 const size_t n = last - first;
231 if ((size_t) (end_of_storage - finish) >= n) {
232 const size_t to_move = finish - position;
233 if (to_move <= n) {
234 std::uninitialized_copy(position, finish, position + n);
235 std::copy(first, first + to_move, position);
236 std::uninitialized_copy(first + to_move, last, finish);
237 } else {
238 std::uninitialized_copy(finish - n, finish, finish);
239 std::copy_backward(position, finish - n, finish);
240 std::copy(first, last, position);
241 }
242 finish += n;
243 } else {
244 const size_t new_size = (2*size() + n);
245 iterator tmp = allocate(new_size);
246 iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
247 tmp_finish = std::uninitialized_copy(first, last, tmp_finish);
248 tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
249 deallocate();
250 start = tmp;
251 finish = tmp_finish;
252 end_of_storage = tmp + new_size;
253 }
254}
255//------------------------------------------------------------------------------
256template <class T> void BCP_vec<T>::insert(iterator position, const size_t n,
258{
259 if (n == 0) return;
260 if ((size_t) (end_of_storage - finish) >= n) {
261 const size_t to_move = finish - position;
262 if (to_move <= n) {
263 std::uninitialized_copy(position, finish, position + n);
264 std::fill_n(position, to_move, x);
265 std::uninitialized_fill_n(finish, n - to_move, x);
266 } else {
267 std::uninitialized_copy(finish - n, finish, finish);
268 std::copy_backward(position, finish - n, finish);
269 std::fill_n(position, n, x);
270 }
271 finish += n;
272 } else {
273 const size_t new_size = (2*size() + n);
274 iterator tmp = allocate(new_size);
275 iterator tmp_finish = std::uninitialized_copy(start, position, tmp);
276 std::uninitialized_fill_n(tmp_finish, n, x);
277 tmp_finish += n;
278 tmp_finish = std::uninitialized_copy(position, finish, tmp_finish);
279 deallocate();
280 start = tmp;
281 finish = tmp_finish;
282 end_of_storage = tmp + new_size;
283 }
284}
285//------------------------------------------------------------------------------
286template <class T> inline typename BCP_vec<T>::iterator
288{
289 const size_t n = position - start;
290 if (finish != end_of_storage && position == finish) {
291 construct(finish++, x);
292 } else {
293 insert_aux(position, x);
294 }
295 return start + n;
296}
297
298
299//##############################################################################
300template <class T> inline void BCP_vec<T>::push_back(const_reference x)
301{
302 if (finish != end_of_storage) {
303 construct(finish++, x);
304 } else
305 insert_aux(finish, x);
306}
307//------------------------------------------------------------------------------
308template <class T> inline void BCP_vec<T>::unchecked_push_back(const_reference x)
309{
310 construct(finish++, x);
311}
312//------------------------------------------------------------------------------
313template <class T> inline void BCP_vec<T>::pop_back()
314{
315 destroy(--finish);
316}
317//------------------------------------------------------------------------------
318template <class T> inline void BCP_vec<T>::clear()
319{
320 if (start) erase(start, finish);
321}
322//------------------------------------------------------------------------------
323template <class T> void
325 const BCP_vec<T>& values)
326{
327 if (positions.size() == 0)
328 return;
329 const_iterator val = values.begin();
330 BCP_vec<int>::const_iterator pos = positions.begin();
331 const BCP_vec<int>::const_iterator lastpos = positions.end();
332 while (pos != lastpos)
333 operator[](*pos++) = *val++;
334}
335//------------------------------------------------------------------------------
336template <class T> inline void BCP_vec<T>::update(const BCP_vec<int>& positions,
337 const BCP_vec<T>& values)
338{
339 if (positions.size() != values.size())
340 throw BCP_fatal_error("BCP_vec::update() called with unequal sizes.\n");
341 BCP_vec_sanity_check(positions.begin(), positions.end(), size());
342 unchecked_update(positions, values);
343}
344
345//##############################################################################
346
347template <class T> inline void BCP_vec<T>::keep(iterator pos)
348{
349 iterator oldfinish = finish;
350 finish = std::copy(pos, pos + 1, start);
351 destroy_range(finish, oldfinish);
352}
353//------------------------------------------------------------------------------
354template <class T> inline void BCP_vec<T>::keep(iterator first, iterator last)
355{
356 iterator oldfinish = finish;
357 finish = std::copy(first, last, start);
358 destroy_range(finish, oldfinish);
359}
360//------------------------------------------------------------------------------
361template <class T> inline void
363{
364 BCP_vec_sanity_check(positions.begin(), positions.end(), size());
365 unchecked_keep_by_index(positions.begin(), positions.end());
366}
367//------------------------------------------------------------------------------
368template <class T> inline void
370{
371 unchecked_keep_by_index(positions.begin(), positions.end());
372}
373//------------------------------------------------------------------------------
374template <class T> inline void
377{
378 BCP_vec_sanity_check(firstpos, lastpos, size());
379 unchecked_keep_by_index(firstpos, lastpos);
380}
381//------------------------------------------------------------------------------
382template <class T> void
385{
386 if (firstpos == lastpos) {
387 clear();
388 } else {
389 iterator target = start;
390 while ( firstpos != lastpos )
391 *target++ = operator[](*firstpos++);
392 destroy_range(target, finish);
393 finish = target;
394 }
395}
396
397//##############################################################################
398
399template <class T> inline void BCP_vec<T>::erase(iterator position)
400{
401 if (position + 1 != finish)
402 std::copy(position + 1, finish, position);
403 destroy(--finish);
404}
405//------------------------------------------------------------------------------
406template <class T> inline void BCP_vec<T>::erase(iterator first, iterator last)
407{
408 iterator oldfinish = finish;
409 finish = std::copy(last, finish, first);
410 destroy_range(finish, oldfinish);
411}
412//------------------------------------------------------------------------------
413template <class T> inline void
415{
416 BCP_vec_sanity_check(positions.begin(), positions.end(), size());
417 unchecked_erase_by_index(positions.begin(), positions.end());
418}
419//-----------------------------------------------------------------------------
420template <class T> inline void
422{
423 unchecked_erase_by_index(positions.begin(), positions.end());
424}
425//------------------------------------------------------------------------------
426template <class T> inline void
429{
430 BCP_vec_sanity_check(firstpos, lastpos, size());
431 unchecked_erase_by_index(firstpos, lastpos);
432}
433//------------------------------------------------------------------------------
434template <class T> void
437{
438 if (firstpos == lastpos)
439 return;
440 --lastpos;
441 int source;
442 iterator target = entry(*firstpos);
443 while (firstpos != lastpos){
444 source = *firstpos + 1;
445 ++firstpos;
446 if (*firstpos > source)
447 target = std::copy( entry(source), entry(*firstpos), target );
448 }
449 iterator oldfinish = finish;
450 finish = std::copy( entry(*firstpos + 1), end(), target );
451 destroy_range(finish, oldfinish);
452}
453
454//##############################################################################
void BCP_vec_sanity_check(BCP_vec< int >::const_iterator firstpos, BCP_vec< int >::const_iterator lastpos, const int maxsize)
A helper function to test whether a set positions is sane for a vector.
Abstract base class that defines members common to all types of cuts.
Definition: BCP_cut.hpp:29
Currently there isn't any error handling in BCP.
Definition: BCP_error.hpp:20
Abstract base class that defines members common to all types of variables.
Definition: BCP_var.hpp:28
The class BCP_vec serves the same purpose as the vector class in the standard template library.
Definition: BCP_vector.hpp:24
const T * const_iterator
Definition: BCP_vector.hpp:35
void deallocate()
Destroy the entries in the vector and free the memory allocated for the vector.
void clear()
Delete every entry.
void unchecked_keep_by_index(const BCP_vec< int > &positions)
Same as the previous method but without the sanity checks.
void pop_back()
Delete the last entry.
const T & const_reference
Definition: BCP_vector.hpp:39
void push_back(const_reference x)
Append x to the end of the vector.
iterator end_of_storage
Iterator pointing to right after the last memory location usable by the vector without reallocation.
Definition: BCP_vector.hpp:71
void keep_by_index(const BCP_vec< int > &positions)
Keep the entries indexed by indices.
void unchecked_push_back(const_reference x)
Append x to the end of the vector.
void erase_by_index(const BCP_vec< int > &positions)
Erase the entries indexed by indices.
iterator end()
Return an iterator to the end of the object.
Definition: BCP_vector.hpp:104
size_t size() const
Return the current number of entries.
Definition: BCP_vector.hpp:116
void keep(iterator pos)
Keep only the entry pointed to by pos.
BCP_vec< T > & operator=(const BCP_vec< T > &x)
Copy the contents of x into the object and return a reference the the object itself.
void erase(iterator pos)
Erase the entry pointed to by pos.
iterator entry(const int i)
Return an iterator to the i-th entry.
Definition: BCP_vector.hpp:109
iterator start
Iterator pointing to the beginning of the memory array where the vector is stored.
Definition: BCP_vector.hpp:66
iterator finish
Iterator pointing to right after the last entry in the vector.
Definition: BCP_vector.hpp:68
iterator begin()
Return an iterator to the beginning of the object.
Definition: BCP_vector.hpp:99
void update(const BCP_vec< int > &positions, const BCP_vec< T > &values)
Update those entries listed in positions to the given values.
void unchecked_update(const BCP_vec< int > &positions, const BCP_vec< T > &values)
Same as the previous method but without sanity checks.
BCP_vec()
The default constructor initializes the data members as 0 pointers.
void reserve(const size_t n)
Reallocate the object to make space for n entries.
void swap(BCP_vec< T > &x)
Exchange the contents of the object with that of x.
iterator allocate(size_t len)
allocate raw, uninitialized memory for len entries.
void unchecked_erase_by_index(const BCP_vec< int > &positions)
Same as the previous method but without the sanity check.
void insert(iterator position, const void *first, const size_t num)
Insert num entries starting from memory location first into the vector from position pos.
T * iterator
Definition: BCP_vector.hpp:33
void assign(const void *x, const size_t num)
Copy num entries of type T starting at the memory location x into the object.
void insert_aux(iterator position, const_reference x)
insert x into the given position in the vector.