38 #ifndef VIGRA_MULTI_ITERATOR_HXX
39 #define VIGRA_MULTI_ITERATOR_HXX
41 #include <sys/types.h>
42 #include "tinyvector.hxx"
43 #include "iteratortags.hxx"
48 template <
unsigned int N,
class T,
49 class REFERENCE = T &,
class POINTER = T *>
class MultiIterator;
50 template <
unsigned int N,
class T,
51 class REFERENCE = T &,
class POINTER = T *>
class StridedMultiIterator;
351 template <
unsigned int N>
373 template <
unsigned int N,
class T,
class REFERENCE,
class POINTER>
383 template <
class T,
class REFERENCE,
class POINTER>
395 typedef StridedMultiIterator<1, T, REFERENCE, POINTER>
iterator;
476 return (m_ptr - d.m_ptr);
500 return m_ptr [d[level]];
520 return m_ptr != rhs.m_ptr;
525 return m_ptr == rhs.m_ptr;
530 return m_ptr < rhs.m_ptr;
535 return m_ptr <= rhs.m_ptr;
540 return m_ptr > rhs.m_ptr;
545 return m_ptr >= rhs.m_ptr;
550 vigra_precondition(d == 0,
551 "MultiIterator<1>::iteratorForDimension(d): d == 0 required");
556 template <
unsigned int K>
557 MultiIterator<K+1, T, REFERENCE, POINTER> &
563 MultiIterator<1, T, REFERENCE, POINTER> &
564 dim0() {
return *
this; }
569 total_stride(
typename multi_difference_type::const_iterator d)
const
582 template <
class T,
class REFERENCE,
class POINTER>
583 class MultiIterator<2, T, REFERENCE, POINTER>
585 :
public MultiIterator<1, T, REFERENCE, POINTER>
590 typedef MultiIterator<1, T, REFERENCE, POINTER>
base_type;
600 typedef StridedMultiIterator<1, T, REFERENCE, POINTER>
iterator;
612 m_stride (0), m_shape (0)
619 m_stride (stride), m_shape (shape)
624 this->m_ptr += m_stride [level];
629 this->m_ptr -= m_stride [level];
648 this->m_ptr += n * m_stride [level];
654 this->m_ptr += total_stride(d.begin());
660 this->m_ptr -= n * m_stride [level];
666 this->m_ptr -= total_stride(d.begin());
686 return (this->m_ptr - d.m_ptr) / this->m_stride[level];
705 return this->m_ptr [n*m_stride [level]];
710 return this->m_ptr [total_stride(d.begin())];
721 ret += m_shape [level-1];
727 vigra_precondition(d <= level,
728 "MultiIterator<N>::iteratorForDimension(d): d < N required");
729 return iterator(this->m_ptr, &m_stride [d], 0);
732 template <
unsigned int K>
733 MultiIterator<K+1, T, REFERENCE, POINTER> &
739 MultiIterator<1, T, REFERENCE, POINTER> &
740 dim0() {
return *
this; }
741 MultiIterator<2, T, REFERENCE, POINTER> &
742 dim1() {
return *
this; }
747 total_stride(
typename multi_difference_type::const_iterator d)
const
749 return d[level]*m_stride[level] + base_type::total_stride(d);
768 template <
unsigned int N,
class T,
class REFERENCE,
class POINTER>
782 enum { level = N-1 };
847 this->m_ptr += this->m_stride [level];
854 this->m_ptr -= this->m_stride [level];
880 this->m_ptr += n * this->m_stride [level];
889 this->m_ptr += total_stride(d.
begin());
898 this->m_ptr -= n * this->m_stride [level];
907 this->m_ptr -= total_stride(d.
begin());
935 return (this->m_ptr - d.m_ptr) / this->m_stride[level];
999 return this->m_ptr [n* this->m_stride [level]];
1006 return this->m_ptr [total_stride(d.
begin())];
1042 ret += this->m_shape [level-1];
1064 vigra_precondition(d <= level,
1065 "MultiIterator<N>::iteratorForDimension(d): d < N required");
1066 return iterator(this->m_ptr, &this->m_stride [d], 0);
1090 template <
unsigned int K>
1098 dim0() {
return *
this; }
1099 MultiIterator<2, T, REFERENCE, POINTER> &
1100 dim1() {
return *
this; }
1101 MultiIterator<3, T, REFERENCE, POINTER> &
1102 dim2() {
return *
this; }
1103 MultiIterator<4, T, REFERENCE, POINTER> &
1104 dim3() {
return *
this; }
1105 MultiIterator<5, T, REFERENCE, POINTER> &
1106 dim4() {
return *
this; }
1111 total_stride(
typename multi_difference_type::const_iterator d)
const
1113 return d[level]*this->m_stride[level] + base_type::total_stride(d);
1124 template <
unsigned int N,
class T,
class REFERENCE,
class POINTER>
1125 class StridedMultiIterator;
1134 template <
class T,
class REFERENCE,
class POINTER>
1135 class StridedMultiIterator<1, T, REFERENCE, POINTER>
1146 typedef StridedMultiIterator<1, T, REFERENCE, POINTER>
iterator;
1157 : m_ptr (0), m_stride (0)
1163 : m_ptr (ptr), m_stride (stride [level])
1192 m_ptr += n * m_stride;
1198 m_ptr += d[level] * m_stride;
1204 m_ptr -= n * m_stride;
1210 m_ptr -= d[level] * m_stride;
1230 return (m_ptr - d.m_ptr) / m_stride;
1249 return m_ptr [n*m_stride];
1254 return m_ptr [d[level]*m_stride];
1274 return m_ptr != rhs.m_ptr;
1279 return m_ptr == rhs.m_ptr;
1284 return m_ptr < rhs.m_ptr;
1289 return m_ptr <= rhs.m_ptr;
1294 return m_ptr > rhs.m_ptr;
1299 return m_ptr >= rhs.m_ptr;
1304 vigra_precondition(d == 0,
1305 "StridedMultiIterator<1>::iteratorForDimension(d): d == 0 required");
1307 return iterator(m_ptr, &stride, 0);
1310 template <
unsigned int K>
1311 StridedMultiIterator<K+1, T, REFERENCE, POINTER> &
1317 StridedMultiIterator<1, T, REFERENCE, POINTER> &
1318 dim0() {
return *
this; }
1323 total_stride(
typename multi_difference_type::const_iterator d)
const
1325 return d[level] * m_stride;
1336 template <
class T,
class REFERENCE,
class POINTER>
1337 class StridedMultiIterator<2, T, REFERENCE, POINTER>
1339 :
public StridedMultiIterator<1, T, REFERENCE, POINTER>
1344 typedef StridedMultiIterator<1, T, REFERENCE, POINTER>
base_type;
1354 typedef StridedMultiIterator<1, T, REFERENCE, POINTER>
iterator;
1366 m_stride (0), m_shape (0)
1373 m_stride (stride), m_shape (shape)
1378 this->m_ptr += m_stride [level];
1383 this->m_ptr -= m_stride [level];
1402 this->m_ptr += n * m_stride [level];
1408 this->m_ptr += total_stride(d.begin());
1414 this->m_ptr -= n * m_stride [level];
1420 this->m_ptr -= total_stride(d.begin());
1440 return (this->m_ptr - d.m_ptr) / this->m_stride[level];
1459 return this->m_ptr [n*m_stride [level]];
1464 return this->m_ptr [total_stride(d.begin())];
1475 ret += m_shape [level-1];
1481 vigra_precondition(d <= level,
1482 "StridedMultiIterator<N>::iteratorForDimension(d): d < N required");
1483 return iterator(this->m_ptr, &m_stride [d], 0);
1486 template <
unsigned int K>
1487 StridedMultiIterator<K+1, T, REFERENCE, POINTER> &
1493 StridedMultiIterator<1, T, REFERENCE, POINTER> &
1494 dim0() {
return *
this; }
1495 StridedMultiIterator<2, T, REFERENCE, POINTER> &
1496 dim1() {
return *
this; }
1501 total_stride(
typename multi_difference_type::const_iterator d)
const
1503 return d[level]*m_stride[level] + base_type::total_stride(d);
1522 template <
unsigned int N,
class T,
class REFERENCE,
class POINTER>
1536 enum { level = N-1 };
1601 this->m_ptr += this->m_stride [level];
1608 this->m_ptr -= this->m_stride [level];
1634 this->m_ptr += n * this->m_stride [level];
1643 this->m_ptr += total_stride(d.
begin());
1652 this->m_ptr -= n * this->m_stride [level];
1661 this->m_ptr -= total_stride(d.
begin());
1689 return (this->m_ptr - d.m_ptr) / this->m_stride[level];
1753 return this->m_ptr [n* this->m_stride [level]];
1760 return this->m_ptr [total_stride(d.
begin())];
1796 ret += this->m_shape [level-1];
1818 vigra_precondition(d <= level,
1819 "StridedMultiIterator<N>::iteratorForDimension(d): d < N required");
1820 return iterator(this->m_ptr, &this->m_stride [d], 0);
1844 template <
unsigned int K>
1852 dim0() {
return *
this; }
1853 StridedMultiIterator<2, T, REFERENCE, POINTER> &
1854 dim1() {
return *
this; }
1855 StridedMultiIterator<3, T, REFERENCE, POINTER> &
1856 dim2() {
return *
this; }
1857 StridedMultiIterator<4, T, REFERENCE, POINTER> &
1858 dim3() {
return *
this; }
1859 StridedMultiIterator<5, T, REFERENCE, POINTER> &
1860 dim4() {
return *
this; }
1865 total_stride(
typename multi_difference_type::const_iterator d)
const
1867 return d[level]*this->m_stride[level] + base_type::total_stride(d);
1874 template <
unsigned int M>
1875 struct MoveToScanOrderIndex
1877 template <
class Shape,
class Ptr>
1880 Shape & point, Ptr & p, Shape
const & strides)
1882 enum { N = Shape::static_size };
1884 p += (newPos - point[N-1-M]) * strides[N-1-M];
1885 point[N-1-M] = newPos;
1886 MoveToScanOrderIndex<M-1>::exec(newIndex / shape[N-1-M], shape, point, p, strides);
1889 template <
class Shape,
class Ptr1,
class Ptr2>
1892 Ptr1 & p1, Shape
const & strides1, Ptr2 & p2, Shape
const & strides2)
1894 enum { N = Shape::static_size };
1896 p1 += (newPos - point[N-1-M]) * strides1[N-1-M];
1897 p2 += (newPos - point[N-1-M]) * strides2[N-1-M];
1898 point[N-1-M] = newPos;
1899 MoveToScanOrderIndex<M-1>::exec(newIndex / shape[N-1-M], shape, point,
1900 p1, strides1, p2, strides2);
1905 struct MoveToScanOrderIndex<0>
1907 template <
class Shape,
class Ptr>
1910 Shape & point, Ptr & p, Shape
const & strides)
1912 enum { N = Shape::static_size };
1914 p += (newPos - point[N-1]) * strides[N-1];
1915 point[N-1] = newPos;
1918 template <
class Shape,
class Ptr1,
class Ptr2>
1921 Ptr1 & p1, Shape
const & strides1, Ptr2 & p2, Shape
const & strides2)
1923 enum { N = Shape::static_size };
1925 p1 += (newPos - point[N-1]) * strides1[N-1];
1926 p2 += (newPos - point[N-1]) * strides2[N-1];
1927 point[N-1] = newPos;
1931 #if 0 // alternative implementation, may be faster on some machines
1932 template <
unsigned int M>
1933 struct MoveToScanOrderIndex
1935 template <
class Shape,
class Ptr>
1938 Shape & point, Ptr & p, Shape
const & strides,
MultiArrayIndex shapeStride = 1)
1940 enum { N = Shape::static_size };
1941 MoveToScanOrderIndex<M-1>::exec(newIndex, shape, point, p, strides, shapeStride*shape[N-1-M]);
1943 p += (newPos - point[N-1-M]) * strides[N-1-M];
1944 point[N-1-M] = newPos;
1945 newIndex %= shapeStride;
1948 template <
class Shape,
class Ptr1,
class Ptr2>
1951 Ptr1 & p1, Shape
const & strides1, Ptr2 & p2, Shape
const & strides2,
1954 enum { N = Shape::static_size };
1955 MoveToScanOrderIndex<M-1>::exec(newIndex, shape, point,
1956 p1, strides1, p2, strides2, shapeStride*shape[N-1-M]);
1958 p1 += (newPos - point[N-1-M]) * strides1[N-1-M];
1959 p2 += (newPos - point[N-1-M]) * strides2[N-1-M];
1960 point[N-1-M] = newPos;
1961 newIndex %= shapeStride;
1966 struct MoveToScanOrderIndex<0>
1968 template <
class Shape,
class Ptr>
1971 Shape & point, Ptr & p, Shape
const & strides,
MultiArrayIndex shapeStride)
1973 enum { N = Shape::static_size };
1975 p += (newPos - point[N-1]) * strides[N-1];
1976 point[N-1] = newPos;
1977 newIndex %= shapeStride;
1980 template <
class Shape,
class Ptr1,
class Ptr2>
1983 Ptr1 & p1, Shape
const & strides1, Ptr2 & p2, Shape
const & strides2,
1986 enum { N = Shape::static_size };
1988 p1 += (newPos - point[N-1]) * strides1[N-1];
1989 p2 += (newPos - point[N-1]) * strides2[N-1];
1990 point[N-1] = newPos;
1991 newIndex %= shapeStride;
2012 template <
unsigned int N,
class T,
class REFERENCE,
class POINTER,
unsigned int M = N>
2019 enum { level = M-1 };
2023 typedef typename base_type::value_type value_type;
2024 typedef typename base_type::pointer pointer;
2025 typedef typename base_type::reference reference;
2026 typedef typename base_type::const_reference const_reference;
2027 typedef typename base_type::shape_type shape_type;
2030 typedef std::random_access_iterator_tag iterator_category;
2036 shape_type
const & shape, shape_type
const & strides)
2042 base_type::operator++();
2043 if(this->point_[level-1] == this->shape_[level-1])
2046 this->i_ += this->strides_[level];
2047 ++this->point_[level];
2061 this->moveToScanOrderIndex(this->index_+i);
2067 base_type::operator--();
2068 if(this->point_[level-1] == -1)
2070 base_type::inverseReset();
2071 this->i_ -= this->strides_[level];
2072 --this->point_[level];
2086 return operator+=(-i);
2092 res.moveToScanOrderIndex(
prod(this->shape_));
2096 bool atBorder()
const
2098 return base_type::atBorder() ||
2099 this->point_[level] == 0 ||
2100 this->point_[level] == this->shape_[level] - 1;
2103 unsigned int neighborhoodType()
const
2105 unsigned int res = base_type::neighborhoodType();
2106 if(this->point_[level] == 0)
2107 res |= (1 << 2*level);
2108 if(this->point_[level] == this->shape_[level]-1)
2109 res |= (2 << 2*level);
2125 return base_type::operator-(r);
2130 return base_type::operator==(r);
2135 return base_type::operator!=(r);
2140 return base_type::operator<(r);
2145 return base_type::operator<=(r);
2150 return base_type::operator>(r);
2155 return base_type::operator>=(r);
2158 using base_type::point;
2159 using base_type::shape;
2160 using base_type::strides;
2161 using base_type::ptr;
2162 using base_type::index;
2163 using base_type::operator*;
2164 using base_type::operator->;
2165 using base_type::operator[];
2170 this->i_ -= this->shape_[level]*this->strides_[level];
2171 this->point_[level] = 0;
2176 this->i_ += this->shape_[level]*this->strides_[level];
2177 this->point_[level] = this->shape_[level]-1;
2180 template <
class Ptr>
2181 void increment(Ptr & p2, shape_type
const & strides2)
2183 base_type::increment(p2, strides2);
2184 if(this->point_[level-1] == this->shape_[level-1])
2187 this->i_ += this->strides_[level];
2188 p2 += strides2[level] - this->shape_[level-1]*strides2[level-1];
2189 ++this->point_[level];
2193 template <
class Ptr>
2194 void decrement(Ptr & p2, shape_type
const & strides2)
2196 base_type::decrement(p2, strides2);
2197 if(this->point_[level-1] == -1)
2199 base_type::inverseReset();
2200 this->i_ -= this->strides_[level];
2201 p2 -= strides2[level] - this->shape_[level-1]*strides2[level-1];
2202 --this->point_[level];
2207 template <
unsigned int N,
class T,
class REFERENCE,
class POINTER>
2214 typedef T value_type;
2215 typedef POINTER pointer;
2216 typedef T
const * const_pointer;
2217 typedef REFERENCE reference;
2218 typedef T
const & const_reference;
2219 typedef typename MultiArrayShape<N>::type shape_type;
2221 typedef StridedScanOrderIterator iterator;
2222 typedef std::random_access_iterator_tag iterator_category;
2224 StridedScanOrderIterator()
2229 StridedScanOrderIterator(pointer i,
2230 shape_type
const & shape, shape_type
const & strides)
2237 StridedScanOrderIterator & operator++()
2239 i_ += strides_[level];
2245 StridedScanOrderIterator operator++(
int)
2247 StridedScanOrderIterator res(*
this);
2254 this->moveToScanOrderIndex(index_+i);
2258 StridedScanOrderIterator & operator--()
2260 i_ -= strides_[level];
2266 StridedScanOrderIterator operator--(
int)
2268 StridedScanOrderIterator res(*
this);
2275 return operator+=(-i);
2278 reference operator*()
2283 const_reference operator*()
const
2288 pointer operator->()
2293 const_pointer operator->()
const
2303 const_pointer ptr()
const
2310 StridedScanOrderIterator t(*
this);
2311 t.moveToScanOrderIndex(index_+i);
2317 StridedScanOrderIterator t(*
this);
2318 t.moveToScanOrderIndex(index_+i);
2322 StridedScanOrderIterator
2325 return StridedScanOrderIterator(*
this) += d;
2328 StridedScanOrderIterator
2331 return StridedScanOrderIterator(*
this) -= d;
2335 operator-(StridedScanOrderIterator
const & r)
const
2337 return index() - r.index();
2341 operator==(StridedScanOrderIterator
const & r)
2343 return index() == r.index();
2347 operator!=(StridedScanOrderIterator
const & r)
const
2349 return index() != r.index();
2353 operator<(StridedScanOrderIterator
const & r)
const
2355 return index() < r.index();
2359 operator<=(StridedScanOrderIterator
const & r)
const
2361 return index() <= r.index();
2365 operator>(StridedScanOrderIterator
const & r)
const
2367 return index() > r.index();
2371 operator>=(StridedScanOrderIterator
const & r)
const
2373 return index() >= r.index();
2377 bool atBorder()
const
2379 return point_[level] == 0 || point_[level] == shape_[level] - 1;
2387 shape_type
const & point()
const
2392 shape_type
const & shape()
const
2397 shape_type
const & strides()
const
2402 StridedScanOrderIterator getEndIterator()
const
2404 StridedScanOrderIterator res(*
this);
2405 res.moveToScanOrderIndex(
prod(shape_));
2409 unsigned int neighborhoodType()
const
2411 unsigned int res = 0;
2412 if(this->point_[level] == 0)
2414 if(this->point_[level] == this->shape_[level]-1)
2422 i_ -= shape_[level]*strides_[level];
2428 i_ += shape_[level]*strides_[level];
2429 point_[level] = shape_[level] - 1;
2435 detail::MoveToScanOrderIndex<N-1>::exec(newIndex, shape_, point_, i_, strides_);
2438 template <
class Ptr>
2439 void increment(Ptr & p2, shape_type
const & strides2)
2442 p2 += strides2[level];
2445 template <
class Ptr>
2446 void decrement(Ptr & p2, shape_type
const & strides2)
2449 p2 -= strides2[level];
2452 template <
class Ptr>
2453 void moveToScanOrderIndex(
MultiArrayIndex newIndex, Ptr & p2, shape_type
const & strides2)
2456 detail::MoveToScanOrderIndex<N-1>::exec(newIndex, shape_, point_, i_, strides_, p2, strides2);
2460 shape_type point_, shape_, strides_;
2469 #endif // VIGRA_MULTI_ITERATOR_HXX