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_bidirectional_iterator.h 14 * 15 * Bidirectional iterators for the matrix class. 16 * 17 */ 18 19 /*! \file matrix_bidirectional_iterator.h 20 * \brief Definitions of STL-compliant bidirectional iterators for the 21 * Matrix class. 22 * 23 * Contains definitions of const_matrix_bidirectional_iterator, 24 * matrix_bidirectional_iterator, and related operators. See a 25 * Standard Template Library reference, such as Josuttis (1999), for a 26 * full description of the capabilities of bidirectional 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_BIDIRECTIONAL_ITERATOR_H 36 #define SCYTHE_MATRIX_BIDIRECTIONAL_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 bidirectional iterator for Matrix. 61 * 62 * Provides bidirectional iteration over const Matrix objects. See 63 * Josuttis (1999), or some other STL reference, for a full 64 * description of the bidirectional iterator interface. 65 * 66 * \see Matrix 67 * \see matrix_bidirectional_iterator 68 * \see const_matrix_forward_iterator 69 * \see matrix_forward_iterator 70 * \see const_matrix_random_access_iterator 71 * \see matrix_random_access_iterator 72 */ 73 74 template <typename T_type, matrix_order ORDER, matrix_order M_ORDER, 75 matrix_style M_STYLE> 76 class const_matrix_bidirectional_iterator 77 : public std::iterator<std::bidirectional_iterator_tag, T_type> 78 { 79 public: 80 /**** TYPEDEFS ***/ 81 typedef const_matrix_bidirectional_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_bidirectional_iterator()98 const_matrix_bidirectional_iterator () 99 {} 100 101 /* Standard constructor */ const_matrix_bidirectional_iterator(const Matrix<value_type,M_ORDER,M_STYLE> & M)102 const_matrix_bidirectional_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 vbegin_ = pos_; 132 } 133 #if SCYTHE_DEBUG > 2 134 size_ = M.size(); 135 start_ = pos_; 136 #endif 137 138 } 139 140 /* Copy constructor */ const_matrix_bidirectional_iterator(const self & mi)141 const_matrix_bidirectional_iterator (const self &mi) 142 : pos_ (mi.pos_), 143 matrix_ (mi.matrix_) 144 { 145 if (M_STYLE != Concrete || M_ORDER != ORDER) { 146 offset_ = mi.offset_; 147 lead_length_ = mi.lead_length_; 148 lead_inc_ = mi.lead_inc_; 149 trail_inc_ = mi.trail_inc_; 150 vend_ = mi.vend_; 151 vbegin_ = mi.vbegin_; 152 jump_ = mi.jump_; 153 } 154 155 #if SCYTHE_DEBUG > 2 156 size_ = mi.size_; 157 start_ = mi.start_; 158 #endif 159 } 160 161 /**** EXTRA MODIFIER ****/ 162 163 /* This function lets us grab an end iterator. It is cheap for 164 * Concrete matrices but somewhat more costly for views. 165 */ set_end()166 inline self& set_end () 167 { 168 if (M_STYLE == Concrete && ORDER == M_ORDER) { 169 pos_ = matrix_->getArray() + matrix_->size(); 170 } else { 171 if (ORDER == Col) { 172 vbegin_ += trail_inc_ * matrix_->cols(); 173 vend_ += trail_inc_ * matrix_->cols(); 174 } else { // ORDER == Rows 175 vbegin_ += trail_inc_ * matrix_->rows(); 176 vend_ += trail_inc_ * matrix_->rows(); 177 } 178 179 pos_ = vbegin_; 180 offset_ = matrix_->size(); 181 } 182 183 return *this; 184 } 185 186 /**** FORWARD ITERATOR FACILITIES ****/ 187 188 inline self& operator= (const self& mi) 189 { 190 pos_ = mi.pos_; 191 matrix_ = mi.matrix_; 192 193 if (M_STYLE != Concrete || M_ORDER != ORDER) { 194 offset_ = mi.offset_; 195 lead_length_ = mi.lead_length_; 196 lead_inc_ = mi.lead_inc_; 197 trail_inc_ = mi.trail_inc_; 198 vend_ = mi.vend_; 199 vbegin_ = mi.vbegin_; 200 jump_ = mi.jump_; 201 } 202 #if SCYTHE_DEBUG > 2 203 size_ = mi.size_; 204 start_ = mi.start_; 205 #endif 206 207 return *this; 208 } 209 210 inline const reference operator* () const 211 { 212 SCYTHE_ITER_CHECK_BOUNDS(); 213 return *pos_; 214 } 215 216 inline const pointer operator-> () const 217 { 218 SCYTHE_ITER_CHECK_BOUNDS(); 219 return pos_; 220 } 221 222 inline self& operator++ () 223 { 224 if (M_STYLE == Concrete && ORDER == M_ORDER) 225 ++pos_; 226 else { 227 if (pos_ == vend_) { 228 vend_ += trail_inc_; 229 vbegin_ += trail_inc_; 230 pos_ += jump_; 231 } else { 232 pos_ += lead_inc_; 233 } 234 ++offset_; 235 } 236 237 return *this; 238 } 239 240 inline self operator++ (int) 241 { 242 self tmp = *this; 243 ++(*this); 244 return tmp; 245 } 246 247 /* == is only defined for iterators of the same template type 248 * that point to the same matrix. Behavior for any other 249 * comparison is undefined. 250 * 251 * Note that we have to be careful about iterator comparisons 252 * when working with views and cross-grain iterators. 253 * Specifically, we always have to rely on the offset value. 254 * Obviously, with <> checks pos_ can jump all over the place in 255 * cross-grain iterators, but also end iterators point to the 256 * value after the last in the matrix. In some cases, the 257 * equation in += and -= will actually put pos_ inside the 258 * matrix (often in an early position) in this case. 259 */ 260 inline bool operator== (const self& x) const 261 { 262 if (M_STYLE == Concrete && ORDER == M_ORDER) { 263 return pos_ == x.pos_; 264 } else { 265 return offset_ == x.offset_; 266 } 267 } 268 269 /* Again, != is only officially defined for iterators over the 270 * same matrix although the test will be trivially true for 271 * matrices that don't view the same data, by implementation. 272 */ 273 inline bool operator!= (const self &x) const 274 { 275 return !(*this == x); 276 } 277 278 /**** BIDIRECTIONAL ITERATOR FACILITES ****/ 279 inline self& operator-- () 280 { 281 if (M_STYLE == Concrete && ORDER == M_ORDER) 282 --pos_; 283 else { 284 if (pos_ == vbegin_) { 285 vend_ -= trail_inc_; 286 vbegin_ -= trail_inc_; 287 pos_ -= jump_; 288 } else { 289 pos_ -= lead_inc_; 290 } 291 --offset_; 292 } 293 294 return *this; 295 } 296 297 inline self operator-- (int) 298 { 299 self tmp = *this; 300 --(*this); 301 return tmp; 302 } 303 304 protected: 305 306 /**** INSTANCE VARIABLES ****/ 307 T_type* pos_; // pointer to current position in array 308 T_type *vend_; // pointer to end of current vector 309 T_type *vbegin_; // pointer to begin of current vector 310 311 uint offset_; // logical offset into matrix 312 313 // TODO Some of these can probably be uints 314 int lead_length_; // Logical length of leading dimension 315 int lead_inc_; // Memory distance between vectors in ldim 316 int trail_inc_; // Memory distance between vectors in tdim 317 int jump_; // Memory distance between end of one ldim vector and 318 // begin of next 319 // Pointer used only for set_end. TODO Cleaner impl. 320 const Matrix<T_type, M_ORDER, M_STYLE>* matrix_; 321 // Size variable for range checking 322 #if SCYTHE_DEBUG > 2 323 uint size_; // Logical matrix size 324 T_type* start_; // only needed for bounds checking 325 #endif 326 }; 327 328 /*! \brief An STL-compliant bidirectional iterator for Matrix. 329 * 330 * Provides bidirectional iteration over Matrix objects. See 331 * Josuttis (1999), or some other STL reference, for a full 332 * description of the bidirectional iterator interface. 333 * 334 * \see Matrix 335 * \see const_matrix_bidirectional_iterator 336 * \see const_matrix_forward_iterator 337 * \see matrix_forward_iterator 338 * \see const_matrix_random_access_iterator 339 * \see matrix_random_access_iterator 340 */ 341 342 template <typename T_type, matrix_order ORDER, matrix_order M_ORDER, 343 matrix_style M_STYLE> 344 class matrix_bidirectional_iterator 345 : public const_matrix_bidirectional_iterator<T_type, ORDER, 346 M_ORDER, M_STYLE> 347 { 348 /**** TYPEDEFS ***/ 349 typedef matrix_bidirectional_iterator<T_type, ORDER, M_ORDER, 350 M_STYLE> self; 351 typedef const_matrix_bidirectional_iterator<T_type, ORDER, 352 M_ORDER, M_STYLE> Base; 353 354 public: 355 /* These are a little formal, but useful */ 356 typedef typename std::iterator_traits<Base>::value_type 357 value_type; 358 typedef typename std::iterator_traits<Base>::iterator_category 359 iterator_category; 360 typedef typename std::iterator_traits<Base>::difference_type 361 difference_type; 362 typedef typename std::iterator_traits<Base>::pointer pointer; 363 typedef typename std::iterator_traits<Base>::reference reference; 364 365 366 /**** CONSTRUCTORS ****/ 367 368 /* Default constructor */ matrix_bidirectional_iterator()369 matrix_bidirectional_iterator () 370 : Base () 371 {} 372 373 /* Standard constructor */ matrix_bidirectional_iterator(const Matrix<value_type,M_ORDER,M_STYLE> & M)374 matrix_bidirectional_iterator (const Matrix<value_type, M_ORDER, 375 M_STYLE> &M) 376 : Base(M) 377 {} 378 379 /* Copy constructor */ matrix_bidirectional_iterator(const self & mi)380 matrix_bidirectional_iterator (const self &mi) 381 : Base (mi) 382 {} 383 384 /**** EXTRA MODIFIER ****/ set_end()385 inline self& set_end () 386 { 387 Base::set_end(); 388 return *this; 389 } 390 391 /**** FORWARD ITERATOR FACILITIES ****/ 392 393 /* We have to override a lot of these to get return values 394 * right.*/ 395 inline self& operator= (const self& mi) 396 { 397 pos_ = mi.pos_; 398 matrix_ = mi.matrix_; 399 400 if (M_STYLE != Concrete || M_ORDER != ORDER) { 401 offset_ = mi.offset_; 402 lead_length_ = mi.lead_length_; 403 lead_inc_ = mi.lead_inc_; 404 trail_inc_ = mi.trail_inc_; 405 vend_ = mi.vend_; 406 vbegin_ = mi.vbegin_; 407 jump_ = mi.jump_; 408 } 409 #if SCYTHE_DEBUG > 2 410 size_ = mi.size_; 411 start_ = mi.start_; 412 #endif 413 414 return *this; 415 } 416 417 inline reference operator* () const 418 { 419 SCYTHE_ITER_CHECK_BOUNDS(); 420 return *pos_; 421 } 422 423 inline pointer operator-> () const 424 { 425 SCYTHE_ITER_CHECK_BOUNDS(); 426 return pos_; 427 } 428 429 inline self& operator++ () 430 { 431 Base::operator++(); 432 return *this; 433 } 434 435 inline self operator++ (int) 436 { 437 self tmp = *this; 438 ++(*this); 439 return tmp; 440 } 441 442 inline self& operator-- () 443 { 444 Base::operator--(); 445 return *this; 446 } 447 448 inline self operator-- (int) 449 { 450 self tmp = *this; 451 --(*this); 452 return tmp; 453 } 454 455 private: 456 /* Get handles to base members. It boggles the mind */ 457 using Base::pos_; 458 using Base::vend_; 459 using Base::vbegin_; 460 using Base::offset_; 461 using Base::lead_length_; 462 using Base::lead_inc_; 463 using Base::trail_inc_; 464 using Base::jump_; 465 using Base::matrix_; 466 #if SCYTHE_DEBUG > 2 467 using Base::size_; 468 using Base::start_; 469 #endif 470 }; 471 472 } // namespace scythe 473 474 #endif /* SCYTHE_MATRIX_BIDIRECTIONAL_ITERATOR_H */ 475