36#ifndef VIGRA_ARRAY_VECTOR_HXX
37#define VIGRA_ARRAY_VECTOR_HXX
41#include "numerictraits.hxx"
46#ifdef VIGRA_CHECK_BOUNDS
47#define VIGRA_ASSERT_INSIDE(diff) \
48 vigra_precondition(diff >= 0, "Index out of bounds");\
49 vigra_precondition(diff < (difference_type)size_, "Index out of bounds");
51#define VIGRA_ASSERT_INSIDE(diff)
57template <
class T,
class Alloc = std::allocator<T> >
90 typedef std::size_t size_type;
91 typedef std::ptrdiff_t difference_type;
92 typedef std::reverse_iterator<iterator> reverse_iterator;
93 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
156 void copy( this_type
const & rhs )
158 if(data_ != rhs.data_)
180 if(data_ != rhs.data_)
203 "ArrayVectorView::subarray(): Limits out of range.");
209 inline const_pointer
data()
const
237 inline const_iterator
end()
const
258 inline const_iterator
cend()
const
267 return (reverse_iterator(
end()));
272 inline const_reverse_iterator
rbegin()
const
274 return (const_reverse_iterator(
end()));
281 return (reverse_iterator(
begin()));
286 inline const_reverse_iterator
rend()
const
288 return (const_reverse_iterator(
begin()));
295 return (const_reverse_iterator(
end()));
300 inline const_reverse_iterator
crend()
const
302 return (const_reverse_iterator(
begin()));
323 return data_[size_-1];
330 return data_[size_-1];
337 VIGRA_ASSERT_INSIDE(i);
345 VIGRA_ASSERT_INSIDE(i);
382 return p >= 0 && p < size_;
407 else if(data_ != rhs.data_)
418 for(size_type k=0; k<
size(); ++k)
419 if(data_[k] != rhs[k])
428 vigra_precondition (size() == rhs.size(),
429 "ArrayVectorView::copy(): shape mismatch.");
433 if(data_ <= rhs.data())
435 std::copy(rhs.begin(), rhs.end(), begin());
439 std::copy_backward(rhs.begin(), rhs.end(), end());
446ArrayVectorView <T>::copyImpl(
const ArrayVectorView <U>& rhs)
448 vigra_precondition (size() == rhs.size(),
449 "ArrayVectorView::copy(): shape mismatch.");
450 std::copy(rhs.begin(), rhs.end(), begin());
456ArrayVectorView <T>::swapDataImpl(
const ArrayVectorView <U>& rhs)
458 vigra_precondition (size () == rhs.size() (),
459 "ArrayVectorView::swapData(): size mismatch.");
462 if(data_ + size_ <= rhs.data_ || rhs.data_ + size_ <= data_)
464 for(size_type k=0; k<size_; ++k)
465 std::swap(data_[k], rhs.data_[k]);
511template <
class T,
class Alloc >
515 typedef ArrayVector<T, Alloc> this_type;
516 enum { minimumCapacity = 2, resizeFactor = 2 };
521 typedef typename view_type::reference reference;
522 typedef typename view_type::const_reference const_reference;
523 typedef typename view_type::pointer pointer;
524 typedef typename view_type::const_pointer const_pointer;
525 typedef typename view_type::iterator iterator;
526 typedef typename view_type::const_iterator const_iterator;
527 typedef typename view_type::size_type size_type;
528 typedef typename view_type::difference_type difference_type;
529 typedef typename view_type::reverse_iterator reverse_iterator;
530 typedef typename view_type::const_reverse_iterator const_reverse_iterator;
531 typedef Alloc allocator_type;
536 capacity_(minimumCapacity),
539 this->data_ = reserve_raw(capacity_);
542 explicit ArrayVector(Alloc
const & alloc)
544 capacity_(minimumCapacity),
547 this->data_ = reserve_raw(capacity_);
550 explicit ArrayVector( size_type
size, Alloc
const & alloc = Alloc())
554 initImpl(
size, value_type(), VigraTrueType());
557 ArrayVector( size_type
size, value_type
const & initial, Alloc
const & alloc = Alloc())
561 initImpl(
size, initial, VigraTrueType());
565 ArrayVector( this_type
const & rhs )
569 initImpl(rhs.
begin(), rhs.
end(), VigraFalseType());
577 initImpl(rhs.
begin(), rhs.
end(), VigraFalseType());
580 template <
class InputIterator>
581 ArrayVector(InputIterator i, InputIterator
end)
583 initImpl(i,
end,
typename NumericTraits<InputIterator>::isIntegral());
586 template <
class InputIterator>
587 ArrayVector(InputIterator i, InputIterator
end, Alloc
const & alloc)
590 initImpl(i,
end,
typename NumericTraits<InputIterator>::isIntegral());
593 this_type & operator=( this_type
const & rhs )
597 if(this->size_ == rhs.size_)
612 deallocate(this->data_, this->size_, this->capacity_);
617 void push_back( value_type
const & t );
619 iterator insert(iterator p, value_type
const & v);
621 iterator insert(iterator p, size_type n, value_type
const & v);
623 template <
class InputIterator>
624 iterator insert(iterator p, InputIterator i, InputIterator iend);
626 iterator erase(iterator p);
628 iterator erase(iterator p, iterator q);
632 pointer reserveImpl(
bool dealloc, size_type new_capacity );
634 pointer reserveImpl(
bool dealloc);
641 void reserve( size_type new_capacity )
643 reserveImpl(
true, new_capacity);
646 void resize( size_type new_size, value_type
const & initial );
648 void resize( size_type new_size )
650 resize(new_size, value_type());
653 size_type capacity()
const
658 void swap(this_type & rhs);
662 void deallocate(pointer
data, size_type
size, size_type capacity);
664 pointer reserve_raw(size_type capacity);
666 void initImpl( size_type
size, value_type
const & initial, VigraTrueType );
668 template <
class Iter>
669 void initImpl( Iter i, Iter
end, VigraFalseType );
671 template <
class Iter>
672 void initImpl( Iter i, Iter
end, Error_NumericTraits_not_specialized_for_this_case)
674 initImpl(i,
end, VigraFalseType());
681template <
class T,
class Alloc>
685 if(this->size_ == rhs.
size())
695template <
class T,
class Alloc>
696inline void ArrayVector<T, Alloc>::pop_back()
699 std::allocator_traits<Alloc>::destroy(alloc_, this->data_ + this->size_);
702template <
class T,
class Alloc>
703inline void ArrayVector<T, Alloc>::push_back( value_type
const & t )
705 size_type old_capacity = this->capacity_;
706 pointer old_data = reserveImpl(
false);
707 std::allocator_traits<Alloc>::construct(alloc_, this->data_ + this->size_, t);
710 deallocate(old_data, this->size_, old_capacity);
714template <
class T,
class Alloc>
715inline void ArrayVector<T, Alloc>::clear()
717 detail::destroy_n(this->data_, this->size_);
721template <
class T,
class Alloc>
722typename ArrayVector<T, Alloc>::iterator
723ArrayVector<T, Alloc>::insert(iterator p, value_type
const & v)
729 p = this->begin() + pos;
733 T lastElement = this->back();
734 push_back(lastElement);
735 p = this->begin() + pos;
736 std::copy_backward(p, this->end() - 2, this->end() - 1);
742template <
class T,
class Alloc>
743typename ArrayVector<T, Alloc>::iterator
744ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type
const & v)
747 size_type new_size = this->size() + n;
748 if(new_size > capacity_)
750 size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
751 pointer new_data = reserve_raw(new_capacity);
754 std::uninitialized_copy(this->begin(), p, new_data);
755 std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
756 std::uninitialized_copy(p, this->end(), new_data + pos + n);
760 alloc_.deallocate(new_data, new_capacity);
763 deallocate(this->data_, this->size_, this->capacity_);
764 capacity_ = new_capacity;
765 this->data_ = new_data;
767 else if(pos + n > this->size_)
769 size_type diff = pos + n - this->size_;
770 std::uninitialized_copy(p, this->end(), this->end() + diff);
771 std::uninitialized_fill(this->end(), this->end() + diff, v);
772 std::fill(p, this->end(), v);
776 size_type diff = this->size_ - (pos + n);
777 std::uninitialized_copy(this->end() - n, this->end(), this->end());
778 std::copy_backward(p, p + diff, this->end());
779 std::fill(p, p + n, v);
781 this->size_ = new_size;
782 return this->begin() + pos;
785template <
class T,
class Alloc>
786template <
class InputIterator>
787typename ArrayVector<T, Alloc>::iterator
788ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend)
790 size_type n = std::distance(i, iend);
791 size_type pos = p - this->begin();
792 size_type new_size = this->size() + n;
793 if(new_size > capacity_)
795 size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
796 pointer new_data = reserve_raw(new_capacity);
799 std::uninitialized_copy(this->begin(), p, new_data);
800 std::uninitialized_copy(i, iend, new_data + pos);
801 std::uninitialized_copy(p, this->end(), new_data + pos + n);
805 alloc_.deallocate(new_data, new_capacity);
808 deallocate(this->data_, this->size_, this->capacity_);
809 capacity_ = new_capacity;
810 this->data_ = new_data;
812 else if(pos + n > this->size_)
814 size_type diff = pos + n - this->size_;
815 std::uninitialized_copy(p, this->end(), this->end() + diff);
816 InputIterator split = i;
817 std::advance(split, n - diff);
818 std::uninitialized_copy(split, iend, this->end());
819 std::copy(i, split, p);
823 size_type diff = this->size_ - (pos + n);
824 std::uninitialized_copy(this->end() - n, this->end(), this->end());
825 std::copy_backward(p, p + diff, this->end());
826 std::copy(i, iend, p);
828 this->size_ = new_size;
829 return this->begin() + pos;
832template <
class T,
class Alloc>
833typename ArrayVector<T, Alloc>::iterator
834ArrayVector<T, Alloc>::erase(iterator p)
836 std::copy(p+1, this->end(), p);
841template <
class T,
class Alloc>
842typename ArrayVector<T, Alloc>::iterator
843ArrayVector<T, Alloc>::erase(iterator p, iterator q)
845 std::copy(q, this->end(), p);
847 detail::destroy_n(this->end() - eraseCount, eraseCount);
848 this->size_ -= eraseCount;
852template <
class T,
class Alloc>
853typename ArrayVector<T, Alloc>::pointer
854ArrayVector<T, Alloc>::reserveImpl(
bool dealloc, size_type new_capacity)
856 if(new_capacity <= capacity_)
858 pointer new_data = reserve_raw(new_capacity),
859 old_data = this->data_;
861 std::uninitialized_copy(old_data, old_data+this->size_, new_data);
862 this->data_ = new_data;
865 this->capacity_ = new_capacity;
868 deallocate(old_data, this->size_, this->capacity_);
869 this->capacity_ = new_capacity;
873template <
class T,
class Alloc>
874inline typename ArrayVector<T, Alloc>::pointer
875ArrayVector<T, Alloc>::reserveImpl(
bool dealloc)
878 return reserveImpl(dealloc, minimumCapacity);
879 else if(this->size_ == capacity_)
880 return reserveImpl(dealloc, resizeFactor*capacity_);
885template <
class T,
class Alloc>
887ArrayVector<T, Alloc>::resize( size_type new_size, value_type
const & initial)
889 if(new_size < this->size_)
890 erase(this->begin() + new_size, this->end());
891 else if(this->size_ < new_size)
893 insert(this->end(), new_size - this->size(), initial);
897template <
class T,
class Alloc>
899ArrayVector<T, Alloc>::initImpl( size_type size, value_type
const & initial, VigraTrueType )
903 this->data_ = reserve_raw(capacity_);
905 std::uninitialized_fill(this->data_, this->data_+this->size_, initial);
908template <
class T,
class Alloc>
911ArrayVector<T, Alloc>::initImpl( Iter i, Iter end, VigraFalseType )
913 this->size_ = std::distance(i, end);
914 capacity_ = this->size_;
915 this->data_ = reserve_raw(capacity_);
917 detail::uninitializedCopy(i, end, this->data_);
920template <
class T,
class Alloc>
922ArrayVector<T, Alloc>::swap(this_type & rhs)
924 std::swap(this->size_, rhs.size_);
925 std::swap(capacity_, rhs.capacity_);
926 std::swap(this->data_, rhs.data_);
929template <
class T,
class Alloc>
931ArrayVector<T, Alloc>::deallocate(
pointer data, size_type size, size_type capacity)
935 detail::destroy_n(data, size);
936 alloc_.deallocate(data, capacity);
940template <
class T,
class Alloc>
941inline typename ArrayVector<T, Alloc>::pointer
942ArrayVector<T, Alloc>::reserve_raw(size_type capacity)
947 data = alloc_.allocate(capacity);
957ostream & operator<<(ostream & s, vigra::ArrayVectorView<T>
const & a)
959 for(std::ptrdiff_t k=0; k<(std::ptrdiff_t)a.
size()-1; ++k)
968#undef VIGRA_ASSERT_INSIDE
Definition array_vector.hxx:77
bool operator!=(ArrayVectorView< U > const &rhs) const
Definition array_vector.hxx:373
const_reverse_iterator rend() const
Definition array_vector.hxx:286
const_reference front() const
Definition array_vector.hxx:314
void copy(ArrayVectorView< U > const &rhs)
Definition array_vector.hxx:168
void copy(this_type const &rhs)
Definition array_vector.hxx:156
T value_type
Definition array_vector.hxx:83
const_iterator begin() const
Definition array_vector.hxx:223
const_pointer data() const
Definition array_vector.hxx:209
pointer data()
Definition array_vector.hxx:216
const_iterator cbegin() const
Definition array_vector.hxx:251
ArrayVectorView & operator=(ArrayVectorView const &rhs)
bool isInside(difference_type const &p) const
Definition array_vector.hxx:380
size_type size() const
Definition array_vector.hxx:358
const_reference back() const
Definition array_vector.hxx:328
bool empty() const
Definition array_vector.hxx:351
reverse_iterator rend()
Definition array_vector.hxx:279
reference front()
Definition array_vector.hxx:307
ArrayVectorView()
Definition array_vector.hxx:99
void swapData(ArrayVectorView< U > rhs)
Definition array_vector.hxx:190
void init(U const &initial)
Definition array_vector.hxx:146
const_reverse_iterator crbegin() const
Definition array_vector.hxx:293
bool operator==(ArrayVectorView< U > const &rhs) const
Definition array_vector.hxx:414
const_iterator cend() const
Definition array_vector.hxx:258
reference operator[](difference_type i)
Definition array_vector.hxx:335
this_type & operator=(ArrayVectorView< U > const &rhs)
Definition array_vector.hxx:137
const_reverse_iterator crend() const
Definition array_vector.hxx:300
iterator end()
Definition array_vector.hxx:244
const_iterator end() const
Definition array_vector.hxx:237
this_type subarray(size_type begin, size_type end) const
Definition array_vector.hxx:200
reverse_iterator rbegin()
Definition array_vector.hxx:265
void swapData(this_type rhs)
Definition array_vector.hxx:178
iterator begin()
Definition array_vector.hxx:230
const_reference operator[](difference_type i) const
Definition array_vector.hxx:343
ArrayVectorView(size_type size, pointer const &data)
Definition array_vector.hxx:107
ArrayVectorView(this_type const &rhs)
Definition array_vector.hxx:114
const_reverse_iterator rbegin() const
Definition array_vector.hxx:272
reference back()
Definition array_vector.hxx:321
Definition array_vector.hxx:514