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.");
405 if(data_ <= rhs.data())
407 std::copy(rhs.begin(), rhs.end(), begin());
411 std::copy_backward(rhs.begin(), rhs.end(), end());
418 ArrayVectorView <T>::copyImpl(
const ArrayVectorView <U>& rhs)
420 vigra_precondition (size() == rhs.size(),
421 "ArrayVectorView::copy(): shape mismatch.");
422 std::copy(rhs.begin(), rhs.end(), begin());
428 ArrayVectorView <T>::swapDataImpl(
const ArrayVectorView <U>& rhs)
430 vigra_precondition (size () == rhs.size() (),
431 "ArrayVectorView::swapData(): size mismatch.");
434 if(data_ + size_ <= rhs.data_ || rhs.data_ + size_ <= data_)
436 for(
unsigned int k=0; k<size_; ++k)
437 std::swap(data_[k], rhs.data_[k]);
441 ArrayVector<T> t(*
this);
483 template <
class T,
class Alloc >
485 :
public ArrayVectorView<T>
487 typedef ArrayVector<T, Alloc> this_type;
488 enum { minimumCapacity = 2, resizeFactor = 2 };
491 typedef ArrayVectorView<T> view_type;
493 typedef typename view_type::reference reference;
494 typedef typename view_type::const_reference const_reference;
495 typedef typename view_type::pointer pointer;
496 typedef typename view_type::const_pointer const_pointer;
497 typedef typename view_type::iterator iterator;
498 typedef typename view_type::const_iterator const_iterator;
499 typedef typename view_type::size_type size_type;
500 typedef typename view_type::difference_type difference_type;
501 typedef typename view_type::reverse_iterator reverse_iterator;
502 typedef typename view_type::const_reverse_iterator const_reverse_iterator;
503 typedef Alloc allocator_type;
508 capacity_(minimumCapacity),
511 this->data_ = reserve_raw(capacity_);
514 explicit ArrayVector(Alloc
const & alloc)
516 capacity_(minimumCapacity),
519 this->data_ = reserve_raw(capacity_);
522 explicit ArrayVector( size_type
size, Alloc
const & alloc = Alloc())
526 initImpl(size, value_type(), VigraTrueType());
529 ArrayVector( size_type size, value_type
const & initial, Alloc
const & alloc = Alloc())
533 initImpl(size, initial, VigraTrueType());
537 ArrayVector( this_type
const & rhs )
541 initImpl(rhs.begin(), rhs.end(), VigraFalseType());
545 explicit ArrayVector( ArrayVectorView<U>
const & rhs, Alloc
const & alloc = Alloc() )
549 initImpl(rhs.begin(), rhs.end(), VigraFalseType());
552 template <
class InputIterator>
553 ArrayVector(InputIterator i, InputIterator
end)
555 initImpl(i, end,
typename NumericTraits<InputIterator>::isIntegral());
558 template <
class InputIterator>
559 ArrayVector(InputIterator i, InputIterator end, Alloc
const & alloc)
562 initImpl(i, end,
typename NumericTraits<InputIterator>::isIntegral());
565 this_type & operator=( this_type
const & rhs )
569 if(this->size_ == rhs.size_)
580 this_type & operator=( ArrayVectorView<U>
const & rhs);
584 deallocate(this->data_, this->size_);
589 void push_back( value_type
const & t );
591 iterator insert(iterator p, value_type
const & v);
593 iterator insert(iterator p, size_type n, value_type
const & v);
595 template <
class InputIterator>
596 iterator insert(iterator p, InputIterator i, InputIterator iend);
598 iterator erase(iterator p);
600 iterator erase(iterator p, iterator q);
604 void reserve( size_type new_capacity );
608 void resize( size_type new_size, value_type
const & initial );
610 void resize( size_type new_size )
612 resize(new_size, value_type());
615 size_type capacity()
const
620 void swap(this_type & rhs);
624 void deallocate(pointer
data, size_type size);
626 pointer reserve_raw(size_type capacity);
628 void initImpl( size_type size, value_type
const & initial, VigraTrueType );
630 template <
class Iter>
631 void initImpl( Iter i, Iter end, VigraFalseType );
633 template <
class Iter>
634 void initImpl( Iter i, Iter end, Error_NumericTraits_not_specialized_for_this_case)
636 initImpl(i, end, VigraFalseType());
643 template <
class T,
class Alloc>
645 ArrayVector<T, Alloc> & ArrayVector<T, Alloc>::operator=( ArrayVectorView<U>
const & rhs )
647 if(this->size_ == rhs.size())
657 template <
class T,
class Alloc>
658 inline void ArrayVector<T, Alloc>::pop_back()
661 alloc_.destroy(this->data_ + this->size_);
664 template <
class T,
class Alloc>
665 inline void ArrayVector<T, Alloc>::push_back( value_type
const & t )
668 alloc_.construct(this->data_ + this->size_, t);
672 template <
class T,
class Alloc>
673 inline void ArrayVector<T, Alloc>::clear()
675 detail::destroy_n(this->data_, (
int)this->size_);
679 template <
class T,
class Alloc>
680 typename ArrayVector<T, Alloc>::iterator
681 ArrayVector<T, Alloc>::insert(iterator p, value_type
const & v)
683 difference_type pos = p - this->begin();
687 p = this->begin() + pos;
691 T lastElement = this->back();
692 push_back(lastElement);
693 p = this->begin() + pos;
694 std::copy_backward(p, this->end() - 2, this->end() - 1);
700 template <
class T,
class Alloc>
701 typename ArrayVector<T, Alloc>::iterator
702 ArrayVector<T, Alloc>::insert(iterator p, size_type n, value_type
const & v)
704 difference_type pos = p - this->begin();
705 size_type new_size = this->size() + n;
706 if(new_size > capacity_)
708 size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
709 pointer new_data = reserve_raw(new_capacity);
712 std::uninitialized_copy(this->begin(), p, new_data);
713 std::uninitialized_fill(new_data + pos, new_data + pos + n, v);
714 std::uninitialized_copy(p, this->end(), new_data + pos + n);
718 alloc_.deallocate(new_data, new_capacity);
721 deallocate(this->data_, this->size_);
722 capacity_ = new_capacity;
723 this->data_ = new_data;
725 else if(pos + n > this->size_)
727 size_type diff = pos + n - this->size_;
728 std::uninitialized_copy(p, this->end(), this->end() + diff);
729 std::uninitialized_fill(this->end(), this->end() + diff, v);
730 std::fill(p, this->end(), v);
734 size_type diff = this->size_ - (pos + n);
735 std::uninitialized_copy(this->end() - n, this->end(), this->end());
736 std::copy_backward(p, p + diff, this->end());
737 std::fill(p, p + n, v);
739 this->size_ = new_size;
740 return this->begin() + pos;
743 template <
class T,
class Alloc>
744 template <
class InputIterator>
745 typename ArrayVector<T, Alloc>::iterator
746 ArrayVector<T, Alloc>::insert(iterator p, InputIterator i, InputIterator iend)
748 size_type n = std::distance(i, iend);
749 size_type pos = p - this->begin();
750 size_type new_size = this->size() + n;
751 if(new_size > capacity_)
753 size_type new_capacity = std::max(new_size, resizeFactor*capacity_);
754 pointer new_data = reserve_raw(new_capacity);
757 std::uninitialized_copy(this->begin(), p, new_data);
758 std::uninitialized_copy(i, iend, new_data + pos);
759 std::uninitialized_copy(p, this->end(), new_data + pos + n);
763 alloc_.deallocate(new_data, new_capacity);
766 deallocate(this->data_, this->size_);
767 capacity_ = new_capacity;
768 this->data_ = new_data;
770 else if(pos + n > this->size_)
772 size_type diff = pos + n - this->size_;
773 std::uninitialized_copy(p, this->end(), this->end() + diff);
774 InputIterator split = i;
775 std::advance(split, n - diff);
776 std::uninitialized_copy(split, iend, this->end());
777 std::copy(i, split, p);
781 size_type diff = this->size_ - (pos + n);
782 std::uninitialized_copy(this->end() - n, this->end(), this->end());
783 std::copy_backward(p, p + diff, this->end());
784 std::copy(i, iend, p);
786 this->size_ = new_size;
787 return this->begin() + pos;
790 template <
class T,
class Alloc>
791 typename ArrayVector<T, Alloc>::iterator
792 ArrayVector<T, Alloc>::erase(iterator p)
794 std::copy(p+1, this->end(), p);
799 template <
class T,
class Alloc>
800 typename ArrayVector<T, Alloc>::iterator
801 ArrayVector<T, Alloc>::erase(iterator p, iterator q)
803 std::copy(q, this->end(), p);
804 difference_type eraseCount = q - p;
805 detail::destroy_n(this->end() - eraseCount, eraseCount);
806 this->size_ -= eraseCount;
810 template <
class T,
class Alloc>
812 ArrayVector<T, Alloc>::reserve( size_type new_capacity )
814 if(new_capacity <= capacity_)
816 pointer new_data = reserve_raw(new_capacity);
818 std::uninitialized_copy(this->data_, this->data_+this->size_, new_data);
819 deallocate(this->data_, this->size_);
820 this->data_ = new_data;
821 capacity_ = new_capacity;
824 template <
class T,
class Alloc>
826 ArrayVector<T, Alloc>::reserve()
829 reserve(minimumCapacity);
830 else if(this->size_ == capacity_)
831 reserve(resizeFactor*capacity_);
834 template <
class T,
class Alloc>
836 ArrayVector<T, Alloc>::resize( size_type new_size, value_type
const & initial)
838 if(new_size < this->size_)
839 erase(this->begin() + new_size, this->end());
840 else if(this->size_ < new_size)
842 insert(this->end(), new_size - this->size(), initial);
846 template <
class T,
class Alloc>
848 ArrayVector<T, Alloc>::initImpl( size_type size, value_type
const & initial, VigraTrueType )
852 this->data_ = reserve_raw(capacity_);
854 std::uninitialized_fill(this->data_, this->data_+this->size_, initial);
857 template <
class T,
class Alloc>
858 template <
class Iter>
860 ArrayVector<T, Alloc>::initImpl( Iter i, Iter end, VigraFalseType )
862 this->size_ = std::distance(i, end);
863 capacity_ = this->size_;
864 this->data_ = reserve_raw(capacity_);
866 detail::uninitializedCopy(i, end, this->data_);
869 template <
class T,
class Alloc>
871 ArrayVector<T, Alloc>::swap(this_type & rhs)
873 std::swap(this->size_, rhs.size_);
874 std::swap(capacity_, rhs.capacity_);
875 std::swap(this->data_, rhs.data_);
878 template <
class T,
class Alloc>
880 ArrayVector<T, Alloc>::deallocate(pointer data, size_type size)
884 detail::destroy_n(data, (
int)size);
885 alloc_.deallocate(data, size);
889 template <
class T,
class Alloc>
890 inline typename ArrayVector<T, Alloc>::pointer
891 ArrayVector<T, Alloc>::reserve_raw(size_type capacity)
896 data = alloc_.allocate(capacity);
906 ostream & operator<<(ostream & s, vigra::ArrayVectorView<T>
const & a)
908 for(
int k=0; k<(int)a.size()-1; ++k)
917 #undef VIGRA_ASSERT_INSIDE