1 /* 2 * Scythe Statistical Library Copyright (C) 2000-2002 Andrew D. Martin 3 * and Kevin M. Quinn; 2002-present Andrew D. Martin, Kevin M. Quinn, 4 * and Daniel Pemstein. All Rights Reserved. 5 * 6 * This program is free software; you can redistribute it and/or 7 * modify under the terms of the GNU General Public License as 8 * published by Free Software Foundation; either version 2 of the 9 * License, or (at your option) any later version. See the text files 10 * COPYING and LICENSE, distributed with this source code, for further 11 * information. 12 * -------------------------------------------------------------------- 13 * scythestat/matrix_forward_iterator.h 14 * 15 * Forward iterators for the matrix class. 16 * 17 */ 18 19 /*! \file matrix_forward_iterator.h 20 * \brief Definitions of STL-compliant forward iterators for the 21 * Matrix class. 22 * 23 * Contains definitions of const_matrix_forward_iterator, 24 * matrix_forward_iterator, and related operators. See a Standard 25 * Template Library reference, such as Josuttis (1999), for a full 26 * description of the capabilities of forward iterators. 27 * 28 * These iterators are templated on the type, order and style of the 29 * Matrix they iterate over and their own order, which need not match 30 * the iterated-over matrix. Same-order iteration over concrete 31 * matrices is extremely fast. Cross-grain concrete and/or view 32 * iteration is slower. 33 */ 34 35 #ifndef SCYTHE_MATRIX_FORWARD_ITERATOR_H 36 #define SCYTHE_MATRIX_FORWARD_ITERATOR_H 37 38 #include <iterator> 39 40 #ifdef SCYTHE_COMPILE_DIRECT 41 #include "defs.h" 42 #include "error.h" 43 #include "matrix.h" 44 #else 45 #include "scythestat/defs.h" 46 #include "scythestat/error.h" 47 #include "scythestat/matrix.h" 48 #endif 49 50 namespace scythe { 51 /* convenience typedefs */ 52 namespace { // local to this file 53 typedef unsigned int uint; 54 } 55 56 /* forward declaration of the matrix class */ 57 template <typename T_type, matrix_order ORDER, matrix_style STYLE> 58 class Matrix; 59 60 /*! \brief An STL-compliant const forward iterator for Matrix. 61 * 62 * Provides forward iteration over const Matrix objects. See 63 * Josuttis (1999), or some other STL reference, for a full 64 * description of the forward iterator interface. 65 * 66 * \see Matrix 67 * \see matrix_forward_iterator 68 * \see const_matrix_random_access_iterator 69 * \see matrix_random_access_iterator 70 * \see const_matrix_bidirectional_iterator 71 * \see matrix_bidirectional_iterator 72 */ 73 74 template <typename T_type, matrix_order ORDER, matrix_order M_ORDER, 75 matrix_style M_STYLE> 76 class const_matrix_forward_iterator 77 : public std::iterator<std::forward_iterator_tag, T_type> 78 { 79 public: 80 /**** TYPEDEFS ***/ 81 typedef const_matrix_forward_iterator<T_type, ORDER, 82 M_ORDER, M_STYLE> self; 83 84 /* These are a little formal, but useful */ 85 typedef typename std::iterator_traits<self>::value_type 86 value_type; 87 typedef typename std::iterator_traits<self>::iterator_category 88 iterator_category; 89 typedef typename std::iterator_traits<self>::difference_type 90 difference_type; 91 typedef typename std::iterator_traits<self>::pointer pointer; 92 typedef typename std::iterator_traits<self>::reference reference; 93 94 95 /**** CONSTRUCTORS ****/ 96 97 /* Default constructor */ const_matrix_forward_iterator()98 const_matrix_forward_iterator () 99 {} 100 101 /* Standard constructor */ const_matrix_forward_iterator(const Matrix<value_type,M_ORDER,M_STYLE> & M)102 const_matrix_forward_iterator 103 (const Matrix<value_type, M_ORDER, M_STYLE> &M) 104 : pos_ (M.getArray()), 105 matrix_ (&M) 106 { 107 SCYTHE_CHECK_30 (pos_ == 0, scythe_null_error, 108 "Requesting iterator to NULL matrix"); 109 110 /* The basic story is: when M_STYLE == Concrete and ORDER == 111 * M_ORDER, we only need pos_ and iteration will be as fast as 112 * possible. All other types of iteration need more variables 113 * to keep track of things and are slower. 114 */ 115 116 117 if (M_STYLE != Concrete || M_ORDER != ORDER) { 118 offset_ = 0; 119 120 if (ORDER == Col) { 121 lead_length_ = M.rows(); 122 lead_inc_ = M.rowstride(); 123 trail_inc_ = M.colstride(); 124 } else { 125 lead_length_ = M.cols(); 126 lead_inc_ = M.colstride(); 127 trail_inc_ = M.rowstride(); 128 } 129 jump_ = trail_inc_ + (1 - lead_length_) * lead_inc_; 130 vend_ = pos_ + (lead_length_ - 1) * lead_inc_; 131 } 132 #if SCYTHE_DEBUG > 2 133 size_ = M.size(); 134 start_ = pos_; 135 #endif 136 } 137 138 /* Copy constructor */ const_matrix_forward_iterator(const self & mi)139 const_matrix_forward_iterator (const self &mi) 140 : pos_ (mi.pos_), 141 matrix_ (mi.matrix_) 142 { 143 if (M_STYLE != Concrete || M_ORDER != ORDER) { 144 offset_ = mi.offset_; 145 lead_length_ = mi.lead_length_; 146 lead_inc_ = mi.lead_inc_; 147 trail_inc_ = mi.trail_inc_; 148 vend_ = mi.vend_; 149 jump_ = mi.jump_; 150 } 151 #if SCYTHE_DEBUG > 2 152 size_ = mi.size_; 153 start_ = mi.start_; 154 #endif 155 } 156 157 /**** EXTRA MODIFIER ****/ 158 159 /* This function lets us grab an end iterator quickly, for both 160 * concrete and view matrices. The view code is a bit of a 161 * kludge, but it works. 162 */ set_end()163 inline self& set_end () 164 { 165 if (M_STYLE == Concrete && ORDER == M_ORDER) { 166 pos_ = matrix_->getArray() + matrix_->size(); 167 } else { 168 offset_ = matrix_->size(); 169 } 170 171 return *this; 172 } 173 174 /* Returns the current index (in logical matrix terms) of the 175 * iterator. 176 */ get_index()177 unsigned int get_index () const 178 { 179 return offset_; 180 } 181 182 /**** FORWARD ITERATOR FACILITIES ****/ 183 184 inline self& operator= (const self& mi) 185 { 186 pos_ = mi.pos_; 187 matrix_ = mi.matrix_; 188 189 if (M_STYLE != Concrete || M_ORDER != ORDER) { 190 offset_ = mi.offset_; 191 lead_length_ = mi.lead_length_; 192 lead_inc_ = mi.lead_inc_; 193 trail_inc_ = mi.trail_inc_; 194 vend_ = mi.vend_; 195 jump_ = mi.jump_; 196 } 197 #if SCYTHE_DEBUG > 2 198 size_ = mi.size_; 199 start_ = mi.start_; 200 #endif 201 202 return *this; 203 } 204 205 inline const reference operator* () const 206 { 207 SCYTHE_ITER_CHECK_BOUNDS(); 208 return *pos_; 209 } 210 211 inline const pointer operator-> () const 212 { 213 SCYTHE_ITER_CHECK_BOUNDS(); 214 return pos_; 215 } 216 217 inline self& operator++ () 218 { 219 if (M_STYLE == Concrete && ORDER == M_ORDER) 220 ++pos_; 221 else { 222 if (pos_ == vend_) { 223 vend_ += trail_inc_; 224 pos_ += jump_; 225 } else { 226 pos_ += lead_inc_; 227 } 228 ++offset_; 229 } 230 231 return *this; 232 } 233 234 inline self operator++ (int) 235 { 236 self tmp = *this; 237 ++(*this); 238 return tmp; 239 } 240 241 /* == is only defined for iterators of the same template type 242 * that point to the same matrix. Behavior for any other 243 * comparison is undefined. 244 * 245 * Note that we have to be careful about iterator comparisons 246 * when working with views and cross-grain iterators. 247 * Specifically, we always have to rely on the offset value. 248 * Obviously, with <> checks pos_ can jump all over the place in 249 * cross-grain iterators, but also end iterators point to the 250 * value after the last in the matrix. In some cases, the 251 * equation in += and -= will actually put pos_ inside the 252 * matrix (often in an early position) in this case. 253 */ 254 inline bool operator== (const self& x) const 255 { 256 if (M_STYLE == Concrete && ORDER == M_ORDER) { 257 return pos_ == x.pos_; 258 } else { 259 return offset_ == x.offset_; 260 } 261 } 262 263 /* Again, != is only officially defined for iterators over the 264 * same matrix although the test will be trivially true for 265 * matrices that don't view the same data, by implementation. 266 */ 267 inline bool operator!= (const self &x) const 268 { 269 return !(*this == x); 270 } 271 272 protected: 273 274 /**** INSTANCE VARIABLES ****/ 275 T_type* pos_; // pointer to current position in array 276 T_type *vend_; // pointer to end of current vector 277 278 uint offset_; // logical offset into matrix 279 280 // TODO Some of these can probably be uints 281 int lead_length_; // Logical length of leading dimension 282 int lead_inc_; // Memory distance between vectors in ldim 283 int trail_inc_; // Memory distance between vectors in tdim 284 int jump_; // Memory distance between end of one ldim vector and 285 // begin of next 286 // Pointer to the matrix we're iterating over. This is really 287 // only needed to get variables necessary to set the end. 288 // TODO Handle this more cleanly. 289 const Matrix<T_type, M_ORDER, M_STYLE>* matrix_; 290 // Size variable for range checking 291 #if SCYTHE_DEBUG > 2 292 uint size_; // Logical matrix size 293 T_type* start_; // Not normally needed, but used for bound check 294 #endif 295 }; 296 297 /*! \brief An STL-compliant forward iterator for Matrix. 298 * 299 * Provides forward iteration over Matrix objects. See 300 * Josuttis (1999), or some other STL reference, for a full 301 * description of the forward iterator interface. 302 * 303 * \see Matrix 304 * \see const_matrix_forward_iterator 305 * \see const_matrix_random_access_iterator 306 * \see matrix_random_access_iterator 307 * \see const_matrix_bidirectional_iterator 308 * \see matrix_bidirectional_iterator 309 */ 310 template <typename T_type, matrix_order ORDER, matrix_order M_ORDER, 311 matrix_style M_STYLE> 312 class matrix_forward_iterator 313 : public const_matrix_forward_iterator<T_type, ORDER, 314 M_ORDER, M_STYLE> 315 { 316 /**** TYPEDEFS ***/ 317 typedef matrix_forward_iterator<T_type, ORDER, M_ORDER, 318 M_STYLE> self; 319 typedef const_matrix_forward_iterator<T_type, ORDER, 320 M_ORDER, M_STYLE> Base; 321 322 public: 323 /* These are a little formal, but useful */ 324 typedef typename std::iterator_traits<Base>::value_type 325 value_type; 326 typedef typename std::iterator_traits<Base>::iterator_category 327 iterator_category; 328 typedef typename std::iterator_traits<Base>::difference_type 329 difference_type; 330 typedef typename std::iterator_traits<Base>::pointer pointer; 331 typedef typename std::iterator_traits<Base>::reference reference; 332 333 334 /**** CONSTRUCTORS ****/ 335 336 /* Default constructor */ matrix_forward_iterator()337 matrix_forward_iterator () 338 : Base () 339 {} 340 341 /* Standard constructor */ matrix_forward_iterator(const Matrix<value_type,M_ORDER,M_STYLE> & M)342 matrix_forward_iterator (const Matrix<value_type, M_ORDER, 343 M_STYLE> &M) 344 : Base(M) 345 {} 346 347 /* Copy constructor */ matrix_forward_iterator(const self & mi)348 matrix_forward_iterator (const self &mi) 349 : Base (mi) 350 {} 351 352 /**** EXTRA MODIFIER ****/ set_end()353 inline self& set_end () 354 { 355 Base::set_end(); 356 return *this; 357 } 358 359 /**** FORWARD ITERATOR FACILITIES ****/ 360 361 /* We have to override a lot of these to get return values 362 * right.*/ 363 inline self& operator= (const self& mi) 364 { 365 pos_ = mi.pos_; 366 matrix_ = mi.matrix_; 367 368 if (M_STYLE != Concrete || M_ORDER != ORDER) { 369 offset_ = mi.offset_; 370 lead_length_ = mi.lead_length_; 371 lead_inc_ = mi.lead_inc_; 372 trail_inc_ = mi.trail_inc_; 373 vend_ = mi.vend_; 374 jump_ = mi.jump_; 375 } 376 #if SCYTHE_DEBUG > 2 377 size_ = mi.size_; 378 start_ = mi.start_; 379 #endif 380 381 return *this; 382 } 383 384 inline reference operator* () const 385 { 386 SCYTHE_ITER_CHECK_BOUNDS(); 387 return *pos_; 388 } 389 390 inline pointer operator-> () const 391 { 392 SCYTHE_ITER_CHECK_BOUNDS(); 393 return pos_; 394 } 395 396 inline self& operator++ () 397 { 398 Base::operator++(); 399 return *this; 400 } 401 402 inline self operator++ (int) 403 { 404 self tmp = *this; 405 ++(*this); 406 return tmp; 407 } 408 409 private: 410 /* Get handles to base members. It boggles the mind */ 411 using Base::pos_; 412 using Base::vend_; 413 using Base::offset_; 414 using Base::lead_length_; 415 using Base::lead_inc_; 416 using Base::trail_inc_; 417 using Base::jump_; 418 using Base::matrix_; 419 #if SCYTHE_DEBUG > 2 420 using Base::size_; 421 using Base::start_; 422 #endif 423 }; 424 425 } // namespace scythe 426 427 #endif /* SCYTHE_MATRIX_ITERATOR_H */ 428