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 >
486 enum { minimumCapacity = 2, resizeFactor = 2 };
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_);
514 capacity_(minimumCapacity),
517 this->data_ = reserve_raw(capacity_);
524 initImpl(size,
value_type(), VigraTrueType());
531 initImpl(size, initial, VigraTrueType());
539 initImpl(rhs.
begin(), rhs.
end(), VigraFalseType());
547 initImpl(rhs.
begin(), rhs.
end(), VigraFalseType());
550 template <
class InputIterator>
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());
567 if(this->size_ == rhs.size_)
582 deallocate(this->data_, this->size_);
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 )
613 size_type capacity()
const
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>
645 if(this->size_ == rhs.
size())
655 template <
class T,
class Alloc>
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 std::uninitialized_copy(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