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 
6 template <class T> inline void BCP_vec<T>::destroy(iterator pos)
7 {
8  pos->~T();
9 }
10 //------------------------------------------------------------------------------
11 template <class T> inline void BCP_vec<T>::destroy_range(iterator first, iterator last)
12 {
13  while (first != last) {
14  (--last)->~T();
15  }
16 }
17 //------------------------------------------------------------------------------
18 template <class T> inline void BCP_vec<T>::construct(iterator pos)
19 {
20  ::new(static_cast<void*>(pos)) T();
21 }
22 //------------------------------------------------------------------------------
23 template <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 //##############################################################################
29 template <class T> inline typename BCP_vec<T>::iterator
30 BCP_vec<T>::allocate(size_t len)
31 {
32  return static_cast<iterator>(::operator new(len * sizeof(T)));
33 }
34 //------------------------------------------------------------------------------
35 template <class T> inline void BCP_vec<T>::deallocate()
36 {
37  if (start) {
38  destroy_range(start, finish);
39  ::operator delete(start);
40  }
41 }
42 //------------------------------------------------------------------------------
43 template <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 
65 template <class T> BCP_vec<T>::BCP_vec() :
66  start(0), finish(0), end_of_storage(0) {}
67 //------------------------------------------------------------------------------
68 template <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 //------------------------------------------------------------------------------
74 template <class T>
75 BCP_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);
80  end_of_storage = finish = start + n;
81  std::uninitialized_fill_n(start, n, value);
82  }
83 }
84 //------------------------------------------------------------------------------
85 template <class T>
86 BCP_vec<T>::BCP_vec(const_iterator first, const_iterator last) :
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 //------------------------------------------------------------------------------
96 template <class T>
97 BCP_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  }
106  end_of_storage = finish;
107  }
108 }
109 
110 //##############################################################################
111 
112 template <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 //------------------------------------------------------------------------------
124 template <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 //------------------------------------------------------------------------------
131 template <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 }
153 
154 //##############################################################################
155 // need the void* here, since we occasionally want to copy out of a buffer
156 
157 template <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 //------------------------------------------------------------------------------
176 template <class T> void BCP_vec<T>::insert(iterator position,
177  const void* first, const size_t n)
178 {
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);
206  }
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 //------------------------------------------------------------------------------
225 template <class T> void BCP_vec<T>::insert(iterator position,
226  const_iterator first,
227  const_iterator last)
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 //------------------------------------------------------------------------------
256 template <class T> void BCP_vec<T>::insert(iterator position, const size_t n,
257  const_reference x)
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 //------------------------------------------------------------------------------
286 template <class T> inline typename BCP_vec<T>::iterator
287 BCP_vec<T>::insert(iterator position, const_reference x)
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 //##############################################################################
300 template <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 //------------------------------------------------------------------------------
308 template <class T> inline void BCP_vec<T>::unchecked_push_back(const_reference x)
309 {
310  construct(finish++, x);
311 }
312 //------------------------------------------------------------------------------
313 template <class T> inline void BCP_vec<T>::pop_back()
314 {
315  destroy(--finish);
316 }
317 //------------------------------------------------------------------------------
318 template <class T> inline void BCP_vec<T>::clear()
319 {
320  if (start) erase(start, finish);
321 }
322 //------------------------------------------------------------------------------
323 template <class T> void
324 BCP_vec<T>::unchecked_update(const BCP_vec<int>& positions,
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 //------------------------------------------------------------------------------
336 template <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 
347 template <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 //------------------------------------------------------------------------------
354 template <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 //------------------------------------------------------------------------------
361 template <class T> inline void
362 BCP_vec<T>::keep_by_index(const BCP_vec<int>& positions)
363 {
364  BCP_vec_sanity_check(positions.begin(), positions.end(), size());
365  unchecked_keep_by_index(positions.begin(), positions.end());
366 }
367 //------------------------------------------------------------------------------
368 template <class T> inline void
369 BCP_vec<T>::unchecked_keep_by_index(const BCP_vec<int>& positions)
370 {
371  unchecked_keep_by_index(positions.begin(), positions.end());
372 }
373 //------------------------------------------------------------------------------
374 template <class T> inline void
375 BCP_vec<T>::keep_by_index(BCP_vec<int>::const_iterator firstpos,
376  BCP_vec<int>::const_iterator lastpos)
377 {
378  BCP_vec_sanity_check(firstpos, lastpos, size());
379  unchecked_keep_by_index(firstpos, lastpos);
380 }
381 //------------------------------------------------------------------------------
382 template <class T> void
383 BCP_vec<T>::unchecked_keep_by_index(BCP_vec<int>::const_iterator firstpos,
384  BCP_vec<int>::const_iterator lastpos)
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 
399 template <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 //------------------------------------------------------------------------------
406 template <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 //------------------------------------------------------------------------------
413 template <class T> inline void
414 BCP_vec<T>::erase_by_index(const BCP_vec<int>& positions)
415 {
416  BCP_vec_sanity_check(positions.begin(), positions.end(), size());
417  unchecked_erase_by_index(positions.begin(), positions.end());
418 }
419 //-----------------------------------------------------------------------------
420 template <class T> inline void
421 BCP_vec<T>::unchecked_erase_by_index(const BCP_vec<int>& positions)
422 {
423  unchecked_erase_by_index(positions.begin(), positions.end());
424 }
425 //------------------------------------------------------------------------------
426 template <class T> inline void
427 BCP_vec<T>::erase_by_index(BCP_vec<int>::const_iterator firstpos,
428  BCP_vec<int>::const_iterator lastpos)
429 {
430  BCP_vec_sanity_check(firstpos, lastpos, size());
431  unchecked_erase_by_index(firstpos, lastpos);
432 }
433 //------------------------------------------------------------------------------
434 template <class T> void
435 BCP_vec<T>::unchecked_erase_by_index(BCP_vec<int>::const_iterator firstpos,
436  BCP_vec<int>::const_iterator lastpos)
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 //##############################################################################
values
double * values
Definition: BonFilterSolver.cpp:113
BCP_vec::deallocate
void deallocate()
Destroy the entries in the vector and free the memory allocated for the vector.
Definition: BCP_vector_general.hpp:35
BCP_vec::insert_aux
void insert_aux(iterator position, const_reference x)
insert x into the given position in the vector.
Definition: BCP_vector_general.hpp:43
Couenne::pos
pos
position where the operator should be printed when printing the expression
Definition: CouenneTypes.hpp:30
BCP_vec::clear
void clear()
Delete every entry.
Definition: BCP_vector_general.hpp:318
BCP_vec::finish
iterator finish
Iterator pointing to right after the last entry in the vector.
Definition: BCP_vector.hpp:68
BCP_vec::const_reference
const T & const_reference
Definition: BCP_vector.hpp:39
BCP_vec::begin
iterator begin()
Return an iterator to the beginning of the object.
Definition: BCP_vector.hpp:99
BCP_vec::unchecked_update
void unchecked_update(const BCP_vec< int > &positions, const BCP_vec< T > &values)
Same as the previous method but without sanity checks.
Definition: BCP_vector_general.hpp:324
BCP_vec::reserve
void reserve(const size_t n)
Reallocate the object to make space for n entries.
Definition: BCP_vector_general.hpp:112
BCP_vec::push_back
void push_back(const_reference x)
Append x to the end of the vector.
Definition: BCP_vector_general.hpp:300
BCP_vec::operator=
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.
Definition: BCP_vector_general.hpp:131
BCP_vec::construct
void construct(iterator pos)
Definition: BCP_vector_general.hpp:18
BCP_vec::iterator
T * iterator
Definition: BCP_vector.hpp:33
BCP_vec::keep_by_index
void keep_by_index(const BCP_vec< int > &positions)
Keep the entries indexed by indices.
Definition: BCP_vector_general.hpp:362
BCP_vec::erase
void erase(iterator pos)
Erase the entry pointed to by pos.
Definition: BCP_vector_general.hpp:399
BCP_vec::end_of_storage
iterator end_of_storage
Iterator pointing to right after the last memory location usable by the vector without reallocation...
Definition: BCP_vector.hpp:71
end
fint end
Definition: BonFilterSolver.cpp:135
BCP_vec::pop_back
void pop_back()
Delete the last entry.
Definition: BCP_vector_general.hpp:313
BCP_vec::start
iterator start
Iterator pointing to the beginning of the memory array where the vector is stored.
Definition: BCP_vector.hpp:66
BCP_vec::erase_by_index
void erase_by_index(const BCP_vec< int > &positions)
Erase the entries indexed by indices.
Definition: BCP_vector_general.hpp:414
BCP_vec::update
void update(const BCP_vec< int > &positions, const BCP_vec< T > &values)
Update those entries listed in positions to the given values.
Definition: BCP_vector_general.hpp:336
BCP_vec::destroy_range
void destroy_range(iterator first, iterator last)
Definition: BCP_vector_general.hpp:11
BCP_vec::BCP_vec
BCP_vec()
The default constructor initializes the data members as 0 pointers.
Definition: BCP_vector_general.hpp:65
BCP_vec::insert
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...
Definition: BCP_vector_general.hpp:176
BCP_vec_sanity_check
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.
Definition: BCP_vector_sanity.cpp:8
BCP_fatal_error
Currently there isn&#39;t any error handling in BCP.
Definition: BCP_error.hpp:20
BCP_vec::size
size_t size() const
Return the current number of entries.
Definition: BCP_vector.hpp:116
BCP_vec::end
iterator end()
Return an iterator to the end of the object.
Definition: BCP_vector.hpp:104
BCP_vec::unchecked_keep_by_index
void unchecked_keep_by_index(const BCP_vec< int > &positions)
Same as the previous method but without the sanity checks.
Definition: BCP_vector_general.hpp:369
BCP_vec
The class BCP_vec serves the same purpose as the vector class in the standard template library...
Definition: BCP_vector.hpp:24
BCP_vec::unchecked_push_back
void unchecked_push_back(const_reference x)
Append x to the end of the vector.
Definition: BCP_vector_general.hpp:308
BCP_vec::allocate
iterator allocate(size_t len)
allocate raw, uninitialized memory for len entries.
Definition: BCP_vector_general.hpp:30
BCP_vec::entry
iterator entry(const int i)
Return an iterator to the i-th entry.
Definition: BCP_vector.hpp:109
n
void fint * n
Definition: BonFilterSolver.cpp:96
BCP_vec::keep
void keep(iterator pos)
Keep only the entry pointed to by pos.
Definition: BCP_vector_general.hpp:347
BCP_vec::assign
void assign(const void *x, const size_t num)
Copy num entries of type T starting at the memory location x into the object.
Definition: BCP_vector_general.hpp:157
BCP_vec::swap
void swap(BCP_vec< T > &x)
Exchange the contents of the object with that of x.
Definition: BCP_vector_general.hpp:124
BCP_vec::unchecked_erase_by_index
void unchecked_erase_by_index(const BCP_vec< int > &positions)
Same as the previous method but without the sanity check.
Definition: BCP_vector_general.hpp:421
BCP_vec::const_iterator
const T * const_iterator
Definition: BCP_vector.hpp:35
x
void fint fint fint real fint real * x
Definition: BonBqpdSolver.cpp:27
BCP_vec::destroy
void destroy(iterator pos)
Definition: BCP_vector_general.hpp:6
Generated by   doxygen 1.8.5