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.
const T * const_iterator
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
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.
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.
size_t size() const
Return the current number of entries.
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.
iterator start
Iterator pointing to the beginning of the memory array where the vector is stored.
iterator finish
Iterator pointing to right after the last entry in the vector.
iterator begin()
Return an iterator to the beginning of the object.
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
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.