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((unsigned int)diff < size_, "Index out of bounds");
51 #define VIGRA_ASSERT_INSIDE(diff)
57 template <
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;
158 if(data_ != rhs.data_)
180 if(data_ != rhs.data_)
202 vigra_precondition(begin <= end && end <= size_,
203 "ArrayVectorView::subarray(): Limits out of range.");
204 return this_type(end-begin, data_ + begin);
209 inline const_pointer
data()
const
237 inline const_iterator
end()
const
253 return (reverse_iterator(
end()));
258 inline const_reverse_iterator
rbegin()
const
260 return (const_reverse_iterator(
end()));
267 return (reverse_iterator(
begin()));
272 inline const_reverse_iterator
rend()
const
274 return (const_reverse_iterator(
begin()));
295 return data_[size_-1];
302 return data_[size_-1];
309 VIGRA_ASSERT_INSIDE(i);
317 VIGRA_ASSERT_INSIDE(i);
354 return p >= 0 && p < size_;
379 else if(data_ != rhs.data_)
388 if(size() != rhs.
size())
390 for(
unsigned int k=0; k<size(); ++k)
391 if(data_[k] != rhs[k])
400 vigra_precondition (size() == rhs.size(),
401 "ArrayVectorView::copy(): shape mismatch.");
403 if(data_ <= rhs.data())
405 std::copy(rhs.begin(), rhs.end(), begin());
409 std::copy_backward(rhs.begin(), rhs.end(), end());
416 ArrayVectorView <T>::copyImpl(
const ArrayVectorView <U>& rhs)
418 vigra_precondition (size() == rhs.size(),
419 "ArrayVectorView::copy(): shape mismatch.");
420 std::copy(rhs.begin(), rhs.end(), begin());
426 ArrayVectorView <T>::swapDataImpl(
const ArrayVectorView <U>& rhs)
428 vigra_precondition (size () == rhs.size() (),
429 "ArrayVectorView::swapData(): size mismatch.");
432 if(data_ + size_ <= rhs.data_ || rhs.data_ + size_ <= data_)
434 for(
unsigned int k=0; k<size_; ++k)
435 std::swap(data_[k], rhs.data_[k]);
439 ArrayVector<T> t(*
this);
481 template <
class T,
class Alloc >
483 :
public ArrayVectorView<T>
485 typedef ArrayVector<T, Alloc> this_type;
486 enum { minimumCapacity = 2, resizeFactor = 2 };
489 typedef ArrayVectorView<T> view_type;
491 typedef typename view_type::reference reference;
492 typedef typename view_type::const_reference const_reference;
493 typedef typename view_type::pointer pointer;
494 typedef typename view_type::const_pointer const_pointer;
495 typedef typename view_type::iterator iterator;
496 typedef typename view_type::const_iterator const_iterator;
497 typedef typename view_type::size_type size_type;
498 typedef typename view_type::difference_type difference_type;
499 typedef typename view_type::reverse_iterator reverse_iterator;
500 typedef typename view_type::const_reverse_iterator const_reverse_iterator;
501 typedef Alloc allocator_type;
506 capacity_(minimumCapacity),
509 this->data_ = reserve_raw(capacity_);
512 explicit ArrayVector(Alloc
const & alloc)
514 capacity_(minimumCapacity),
517 this->data_ = reserve_raw(capacity_);
520 explicit ArrayVector( size_type
size, Alloc
const & alloc = Alloc())
524 initImpl(size, value_type(), VigraTrueType());
527 ArrayVector( size_type size, value_type
const & initial, Alloc
const & alloc = Alloc())
531 initImpl(size, initial, VigraTrueType());
535 ArrayVector( this_type
const & rhs )
539 initImpl(rhs.begin(), rhs.end(), VigraFalseType());
543 explicit ArrayVector( ArrayVectorView<U>
const & rhs, Alloc
const & alloc = Alloc() )
547 initImpl(rhs.begin(), rhs.end(), VigraFalseType());
550 template <
class InputIterator>
551 ArrayVector(InputIterator i, InputIterator
end)
553 initImpl(i, end,
typename NumericTraits<InputIterator>::isIntegral());
556 template <
class InputIterator>
557 ArrayVector(InputIterator i, InputIterator end, Alloc
const & alloc)
560 initImpl(i, end,
typename NumericTraits<InputIterator>::isIntegral());
563 this_type & operator=( this_type
const & rhs )
567 if(this->size_ == rhs.size_)
578 this_type & operator=( ArrayVectorView<U>
const & rhs);
582 deallocate(this->data_, this->size_);
587 void push_back( value_type
const & t );
589 iterator insert(iterator p, value_type
const & v);
591 iterator insert(iterator p, size_type n, value_type
const & v);
593 template <
class InputIterator>
594 iterator insert(iterator p, InputIterator i, InputIterator iend);
596 iterator erase(iterator p);
598 iterator erase(iterator p, iterator q);
602 void reserve( size_type new_capacity );
606 void resize( size_type new_size, value_type
const & initial );
608 void resize( size_type new_size )
610 resize(new_size, value_type());
613 size_type capacity()
const
618 void swap(this_type & rhs);
622 void deallocate(pointer
data, size_type size);
624 pointer reserve_raw(size_type capacity);
626 void initImpl( size_type size, value_type
const & initial, VigraTrueType );
628 template <
class Iter>
629 void initImpl( Iter i, Iter end, VigraFalseType );
631 template <
class Iter>
632 void initImpl( Iter i, Iter end, Error_NumericTraits_not_specialized_for_this_case)
634 initImpl(i, end, VigraFalseType());
641 template <
class T,
class Alloc>
643 ArrayVector<T, Alloc> & ArrayVector<T, Alloc>::operator=( ArrayVectorView<U>
const & rhs )
645 if(this->size_ == rhs.size())
655 template <
class T,
class Alloc>
656 inline void ArrayVector<T, Alloc>::pop_back()
659 alloc_.destroy(this->data_ + this->size_);
662 template <
class T,
class Alloc>
663 inline void ArrayVector<T, Alloc>::push_back( value_type
const & t )
666 alloc_.construct(this->data_ + this->size_, t);
670 template <
class T,
class Alloc>
671 inline void ArrayVector<T, Alloc>::clear()
673 detail::destroy_n(this->data_, (
int)this->size_);
677 template <
class T,
class Alloc>
678 typename ArrayVector<T, Alloc>::iterator
679 ArrayVector<T, Alloc>::insert(iterator p, value_type
const & v)
681 difference_type pos = p - this->begin();
685 p = this->begin() + pos;
689 push_back(this->back());
690 p = this->begin() + pos;
691 std::copy_backward(p, this->end() - 2, this->end() - 1);
697 template <
class T,
class Alloc>
698 typename ArrayVector<T, Alloc>::iterator
699 ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type
const & v)
701 difference_type pos = p - this->begin();
702 size_type new_size = this->size() + n;
703 if(new_size > capacity_)
705 size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
706 pointer new_data = reserve_raw(new_capacity);
709 std::uninitialized_copy(this->begin(), p, new_data);
710 std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
711 std::uninitialized_copy(p, this->end(), new_data + pos + n);
715 alloc_.deallocate(new_data, new_capacity);
718 deallocate(this->data_, this->size_);
719 capacity_ = new_capacity;
720 this->data_ = new_data;
722 else if(pos + n > this->size_)
724 size_type diff = pos + n - this->size_;
725 std::uninitialized_copy(p, this->end(), this->end() + diff);
726 std::uninitialized_fill(this->end(), this->end() + diff, v);
727 std::fill(p, this->end(), v);
731 size_type diff = this->size_ - (pos + n);
732 std::uninitialized_copy(this->end() - n, this->end(), this->end());
733 std::copy_backward(p, p + diff, this->end());
734 std::fill(p, p + n, v);
736 this->size_ = new_size;
737 return this->begin() + pos;
740 template <
class T,
class Alloc>
741 template <
class InputIterator>
742 typename ArrayVector<T, Alloc>::iterator
743 ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend)
745 size_type n = std::distance(i, iend);
746 size_type pos = p - this->begin();
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_copy(i, iend, new_data + pos);
756 std::uninitialized_copy(p, this->end(), new_data + pos + n);
760 alloc_.deallocate(new_data, new_capacity);
763 deallocate(this->data_, this->size_);
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 InputIterator split = i;
772 std::advance(split, n - diff);
773 std::uninitialized_copy(split, iend, this->end());
774 std::copy(i, split, p);
778 size_type diff = this->size_ - (pos + n);
779 std::uninitialized_copy(this->end() - n, this->end(), this->end());
780 std::copy_backward(p, p + diff, this->end());
781 std::copy(i, iend, p);
783 this->size_ = new_size;
784 return this->begin() + pos;
787 template <
class T,
class Alloc>
788 typename ArrayVector<T, Alloc>::iterator
789 ArrayVector<T, Alloc>::erase(iterator p)
791 std::copy(p+1, this->end(), p);
796 template <
class T,
class Alloc>
797 typename ArrayVector<T, Alloc>::iterator
798 ArrayVector<T, Alloc>::erase(iterator p, iterator q)
800 std::copy(q, this->end(), p);
801 difference_type eraseCount = q - p;
802 detail::destroy_n(this->end() - eraseCount, eraseCount);
803 this->size_ -= eraseCount;
807 template <
class T,
class Alloc>
809 ArrayVector<T, Alloc>::reserve( size_type new_capacity )
811 if(new_capacity <= capacity_)
813 pointer new_data = reserve_raw(new_capacity);
815 std::uninitialized_copy(this->data_, this->data_+this->size_, new_data);
816 deallocate(this->data_, this->size_);
817 this->data_ = new_data;
818 capacity_ = new_capacity;
821 template <
class T,
class Alloc>
823 ArrayVector<T, Alloc>::reserve()
826 reserve(minimumCapacity);
827 else if(this->size_ == capacity_)
828 reserve(resizeFactor*capacity_);
831 template <
class T,
class Alloc>
833 ArrayVector<T, Alloc>::resize( size_type new_size, value_type
const & initial)
835 if(new_size < this->size_)
836 erase(this->begin() + new_size, this->end());
837 else if(this->size_ < new_size)
839 insert(this->end(), new_size - this->size(), initial);
843 template <
class T,
class Alloc>
845 ArrayVector<T, Alloc>::initImpl( size_type size, value_type
const & initial, VigraTrueType )
849 this->data_ = reserve_raw(capacity_);
851 std::uninitialized_fill(this->data_, this->data_+this->size_, initial);
854 template <
class T,
class Alloc>
855 template <
class Iter>
857 ArrayVector<T, Alloc>::initImpl( Iter i, Iter end, VigraFalseType )
859 this->size_ = std::distance(i, end);
860 capacity_ = this->size_;
861 this->data_ = reserve_raw(capacity_);
863 detail::uninitializedCopy(i, end, this->data_);
866 template <
class T,
class Alloc>
868 ArrayVector<T, Alloc>::swap(this_type & rhs)
870 std::swap(this->size_, rhs.size_);
871 std::swap(capacity_, rhs.capacity_);
872 std::swap(this->data_, rhs.data_);
875 template <
class T,
class Alloc>
877 ArrayVector<T, Alloc>::deallocate(pointer data, size_type size)
881 detail::destroy_n(data, (
int)size);
882 alloc_.deallocate(data, size);
886 template <
class T,
class Alloc>
887 inline typename ArrayVector<T, Alloc>::pointer
888 ArrayVector<T, Alloc>::reserve_raw(size_type capacity)
893 data = alloc_.allocate(capacity);
903 ostream & operator<<(ostream & s, vigra::ArrayVectorView<T>
const & a)
905 for(
int k=0; k<(int)a.size()-1; ++k)
914 #undef VIGRA_ASSERT_INSIDE
iterator end()
Definition: array_vector.hxx:244
reference back()
Definition: array_vector.hxx:293
void swapData(this_type rhs)
Definition: array_vector.hxx:178
this_type & operator=(ArrayVectorView< U > const &rhs)
Definition: array_vector.hxx:137
ArrayVectorView(size_type size, pointer const &data)
Definition: array_vector.hxx:107
bool empty() const
Definition: array_vector.hxx:323
Definition: array_vector.hxx:76
const_iterator begin() const
Definition: array_vector.hxx:223
reverse_iterator rend()
Definition: array_vector.hxx:265
bool isInside(difference_type const &p) const
Definition: array_vector.hxx:352
const_reverse_iterator rbegin() const
Definition: array_vector.hxx:258
const_reference back() const
Definition: array_vector.hxx:300
ArrayVectorView & operator=(ArrayVectorView const &rhs)
void copy(ArrayVectorView< U > const &rhs)
Definition: array_vector.hxx:168
reference operator[](difference_type i)
Definition: array_vector.hxx:307
Definition: array_vector.hxx:58
reference front()
Definition: array_vector.hxx:279
ArrayVectorView()
Definition: array_vector.hxx:99
bool operator!=(ArrayVectorView< U > const &rhs) const
Definition: array_vector.hxx:345
void init(U const &initial)
Definition: array_vector.hxx:146
pointer data()
Definition: array_vector.hxx:216
const_reference front() const
Definition: array_vector.hxx:286
this_type subarray(size_type begin, size_type end) const
Definition: array_vector.hxx:200
iterator begin()
Definition: array_vector.hxx:230
T value_type
Definition: array_vector.hxx:83
void copy(this_type const &rhs)
Definition: array_vector.hxx:156
reverse_iterator rbegin()
Definition: array_vector.hxx:251
const_iterator end() const
Definition: array_vector.hxx:237
const_pointer data() const
Definition: array_vector.hxx:209
size_type size() const
Definition: array_vector.hxx:330
ArrayVectorView(this_type const &rhs)
Definition: array_vector.hxx:114
void swapData(ArrayVectorView< U > rhs)
Definition: array_vector.hxx:190
bool operator==(ArrayVectorView< U > const &rhs) const
Definition: array_vector.hxx:386
const_reference operator[](difference_type i) const
Definition: array_vector.hxx:315
const_reverse_iterator rend() const
Definition: array_vector.hxx:272