1 //////////////////////////////////////////////////////////////////////// 2 // 3 // Copyright (C) 1993-2021 The Octave Project Developers 4 // 5 // See the file COPYRIGHT.md in the top-level directory of this 6 // distribution or <https://octave.org/copyright/>. 7 // 8 // This file is part of Octave. 9 // 10 // Octave is free software: you can redistribute it and/or modify it 11 // under the terms of the GNU General Public License as published by 12 // the Free Software Foundation, either version 3 of the License, or 13 // (at your option) any later version. 14 // 15 // Octave is distributed in the hope that it will be useful, but 16 // WITHOUT ANY WARRANTY; without even the implied warranty of 17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 // GNU General Public License for more details. 19 // 20 // You should have received a copy of the GNU General Public License 21 // along with Octave; see the file COPYING. If not, see 22 // <https://www.gnu.org/licenses/>. 23 // 24 //////////////////////////////////////////////////////////////////////// 25 26 #if ! defined (octave_idx_vector_h) 27 #define octave_idx_vector_h 1 28 29 #include "octave-config.h" 30 31 #include <cassert> 32 #include <cstring> 33 34 #include <algorithm> 35 #include <iosfwd> 36 #include <memory> 37 38 #include "dim-vector.h" 39 #include "oct-inttypes-fwd.h" 40 #include "oct-refcount.h" 41 42 template <typename T> class Array; 43 template <typename T> class Sparse; 44 class Range; 45 46 // Design rationale: 47 // idx_vector is a reference-counting, polymorphic pointer, that can contain 48 // 4 types of index objects: a magic colon, a range, a scalar, or an index vector. 49 // Polymorphic methods for single element access are provided, as well as 50 // templates implementing "early dispatch", i.e., hoisting the checks for index 51 // type out of loops. 52 53 class 54 OCTAVE_API 55 idx_vector 56 { 57 public: 58 59 enum idx_class_type 60 { 61 class_invalid = -1, 62 class_colon = 0, 63 class_range, 64 class_scalar, 65 class_vector, 66 class_mask 67 }; 68 69 template <typename T, typename D> friend class std::unique_ptr; 70 71 private: 72 73 class OCTAVE_API idx_base_rep 74 { 75 public: 76 idx_base_rep(void)77 idx_base_rep (void) : count (1), err (false) { } 78 79 // No copying! 80 81 idx_base_rep (const idx_base_rep&) = delete; 82 83 idx_base_rep& operator = (const idx_base_rep&) = delete; 84 85 virtual ~idx_base_rep (void) = default; 86 87 // Non-range-checking element query. 88 virtual octave_idx_type xelem (octave_idx_type i) const = 0; 89 90 // Range-checking element query. 91 virtual octave_idx_type checkelem (octave_idx_type i) const = 0; 92 93 // Length of the index vector. 94 virtual octave_idx_type length (octave_idx_type n) const = 0; 95 96 // The maximum index + 1. The actual dimension is passed in. 97 virtual octave_idx_type extent (octave_idx_type n) const = 0; 98 99 // Index class. idx_class(void)100 virtual idx_class_type idx_class (void) const { return class_invalid; } 101 102 // Sorts, maybe uniqifies, and returns a clone object pointer. 103 virtual idx_base_rep * sort_uniq_clone (bool uniq = false) = 0; 104 // Sorts, and returns a sorting permutation (aka Array::sort). 105 virtual idx_base_rep * sort_idx (Array<octave_idx_type>&) = 0; 106 107 // Checks whether the index is colon or a range equivalent to colon. is_colon_equiv(octave_idx_type)108 virtual bool is_colon_equiv (octave_idx_type) const { return false; } 109 110 // The original dimensions of object (used when subscribing by matrices). orig_dimensions(void)111 virtual dim_vector orig_dimensions (void) const { return dim_vector (); } 112 113 // i/o 114 virtual std::ostream& print (std::ostream& os) const = 0; 115 116 virtual Array<octave_idx_type> as_array (void); 117 118 octave::refcount<octave_idx_type> count; 119 120 bool err; 121 }; 122 123 // The magic colon index. 124 class OCTAVE_API idx_colon_rep : public idx_base_rep 125 { 126 public: 127 128 idx_colon_rep (void) = default; 129 130 idx_colon_rep (char c); 131 132 // No copying! 133 134 idx_colon_rep (const idx_colon_rep& idx) = delete; 135 136 idx_colon_rep& operator = (const idx_colon_rep& idx) = delete; 137 xelem(octave_idx_type i)138 octave_idx_type xelem (octave_idx_type i) const { return i; } 139 140 octave_idx_type checkelem (octave_idx_type i) const; 141 length(octave_idx_type n)142 octave_idx_type length (octave_idx_type n) const { return n; } 143 extent(octave_idx_type n)144 octave_idx_type extent (octave_idx_type n) const { return n; } 145 idx_class(void)146 idx_class_type idx_class (void) const { return class_colon; } 147 148 idx_base_rep * sort_uniq_clone (bool = false) 149 { count++; return this; } 150 151 OCTAVE_NORETURN idx_base_rep * sort_idx (Array<octave_idx_type>&); 152 is_colon_equiv(octave_idx_type)153 bool is_colon_equiv (octave_idx_type) const { return true; } 154 155 std::ostream& print (std::ostream& os) const; 156 }; 157 158 // To distinguish the "direct" constructors that blindly trust the data. 159 enum direct { DIRECT }; 160 161 // The integer range index. 162 class OCTAVE_API idx_range_rep : public idx_base_rep 163 { 164 public: 165 166 idx_range_rep (void) = delete; 167 idx_range_rep(octave_idx_type _start,octave_idx_type _len,octave_idx_type _step,direct)168 idx_range_rep (octave_idx_type _start, octave_idx_type _len, 169 octave_idx_type _step, direct) 170 : idx_base_rep (), start(_start), len(_len), step(_step) { } 171 172 // Zero-based constructor. 173 idx_range_rep (octave_idx_type _start, octave_idx_type _limit, 174 octave_idx_type _step); 175 176 idx_range_rep (const Range&); 177 178 // No copying! 179 180 idx_range_rep (const idx_range_rep& idx) = delete; 181 182 idx_range_rep& operator = (const idx_range_rep& idx) = delete; 183 xelem(octave_idx_type i)184 octave_idx_type xelem (octave_idx_type i) const 185 { return start + i * step; } 186 187 octave_idx_type checkelem (octave_idx_type i) const; 188 length(octave_idx_type)189 octave_idx_type length (octave_idx_type) const { return len; } 190 extent(octave_idx_type n)191 octave_idx_type extent (octave_idx_type n) const 192 { 193 return len ? std::max (n, start + 1 + (step < 0 ? 0 : step * (len - 1))) 194 : n; 195 } 196 idx_class(void)197 idx_class_type idx_class (void) const { return class_range; } 198 199 idx_base_rep * sort_uniq_clone (bool uniq = false); 200 201 idx_base_rep * sort_idx (Array<octave_idx_type>&); 202 is_colon_equiv(octave_idx_type n)203 bool is_colon_equiv (octave_idx_type n) const 204 { return start == 0 && step == 1 && len == n; } 205 orig_dimensions(void)206 dim_vector orig_dimensions (void) const 207 { return dim_vector (1, len); } 208 get_start(void)209 octave_idx_type get_start (void) const { return start; } 210 get_step(void)211 octave_idx_type get_step (void) const { return step; } 212 213 std::ostream& print (std::ostream& os) const; 214 215 Range unconvert (void) const; 216 217 Array<octave_idx_type> as_array (void); 218 219 private: 220 221 octave_idx_type start, len, step; 222 }; 223 224 // The integer scalar index. 225 class OCTAVE_API idx_scalar_rep : public idx_base_rep 226 { 227 public: 228 229 idx_scalar_rep (void) = delete; 230 idx_scalar_rep(octave_idx_type i,direct)231 idx_scalar_rep (octave_idx_type i, direct) 232 : idx_base_rep (), data (i) { } 233 234 // No copying! 235 236 idx_scalar_rep (const idx_scalar_rep& idx) = delete; 237 238 idx_scalar_rep& operator = (const idx_scalar_rep& idx) = delete; 239 240 // Zero-based constructor. 241 idx_scalar_rep (octave_idx_type i); 242 243 template <typename T> 244 idx_scalar_rep (T x); 245 xelem(octave_idx_type)246 octave_idx_type xelem (octave_idx_type) const { return data; } 247 248 octave_idx_type checkelem (octave_idx_type i) const; 249 length(octave_idx_type)250 octave_idx_type length (octave_idx_type) const { return 1; } 251 extent(octave_idx_type n)252 octave_idx_type extent (octave_idx_type n) const 253 { return std::max (n, data + 1); } 254 idx_class(void)255 idx_class_type idx_class (void) const { return class_scalar; } 256 257 idx_base_rep * sort_uniq_clone (bool = false) 258 { count++; return this; } 259 260 idx_base_rep * sort_idx (Array<octave_idx_type>&); 261 is_colon_equiv(octave_idx_type n)262 bool is_colon_equiv (octave_idx_type n) const 263 { return n == 1 && data == 0; } 264 orig_dimensions(void)265 dim_vector orig_dimensions (void) const { return dim_vector (1, 1); } 266 get_data(void)267 octave_idx_type get_data (void) const { return data; } 268 269 std::ostream& print (std::ostream& os) const; 270 271 double unconvert (void) const; 272 273 Array<octave_idx_type> as_array (void); 274 275 private: 276 277 octave_idx_type data; 278 }; 279 280 // The integer vector index. 281 class OCTAVE_API idx_vector_rep : public idx_base_rep 282 { 283 public: 284 idx_vector_rep(void)285 idx_vector_rep (void) 286 : data (nullptr), len (0), ext (0), aowner (nullptr), orig_dims () 287 { } 288 289 // Direct constructor. idx_vector_rep(octave_idx_type * _data,octave_idx_type _len,octave_idx_type _ext,const dim_vector & od,direct)290 idx_vector_rep (octave_idx_type *_data, octave_idx_type _len, 291 octave_idx_type _ext, const dim_vector& od, direct) 292 : idx_base_rep (), data (_data), len (_len), ext (_ext), 293 aowner (nullptr), orig_dims (od) 294 { } 295 296 // Zero-based constructor. 297 idx_vector_rep (const Array<octave_idx_type>& inda); 298 299 idx_vector_rep (const Array<octave_idx_type>& inda, 300 octave_idx_type _ext, direct); 301 302 template <typename T> 303 idx_vector_rep (const Array<T>&); 304 305 idx_vector_rep (bool); 306 307 idx_vector_rep (const Array<bool>&, octave_idx_type = -1); 308 309 idx_vector_rep (const Sparse<bool>&); 310 311 // No copying! 312 313 idx_vector_rep (const idx_vector_rep& idx) = delete; 314 315 idx_vector_rep& operator = (const idx_vector_rep& idx) = delete; 316 317 ~idx_vector_rep (void); 318 xelem(octave_idx_type i)319 octave_idx_type xelem (octave_idx_type i) const { return data[i]; } 320 321 octave_idx_type checkelem (octave_idx_type i) const; 322 length(octave_idx_type)323 octave_idx_type length (octave_idx_type) const { return len; } 324 extent(octave_idx_type n)325 octave_idx_type extent (octave_idx_type n) const 326 { return std::max (n, ext); } 327 idx_class(void)328 idx_class_type idx_class (void) const { return class_vector; } 329 330 idx_base_rep * sort_uniq_clone (bool uniq = false); 331 332 idx_base_rep * sort_idx (Array<octave_idx_type>&); 333 orig_dimensions(void)334 dim_vector orig_dimensions (void) const { return orig_dims; } 335 get_data(void)336 const octave_idx_type * get_data (void) const { return data; } 337 338 std::ostream& print (std::ostream& os) const; 339 340 Array<double> unconvert (void) const; 341 342 Array<octave_idx_type> as_array (void); 343 344 private: 345 346 const octave_idx_type *data; 347 octave_idx_type len; 348 octave_idx_type ext; 349 350 // This is a trick to allow user-given zero-based arrays to be used 351 // as indices without copying. If the following pointer is nonzero, 352 // we do not own the data, but rather have an Array<octave_idx_type> 353 // object that provides us the data. Note that we need a pointer 354 // because we deferred the Array<T> declaration and we do not want 355 // it yet to be defined. 356 357 Array<octave_idx_type> *aowner; 358 359 dim_vector orig_dims; 360 }; 361 362 // The logical mask index. 363 class OCTAVE_API idx_mask_rep : public idx_base_rep 364 { 365 public: 366 367 idx_mask_rep (void) = delete; 368 369 // Direct constructor. idx_mask_rep(bool * _data,octave_idx_type _len,octave_idx_type _ext,const dim_vector & od,direct)370 idx_mask_rep (bool *_data, octave_idx_type _len, 371 octave_idx_type _ext, const dim_vector& od, direct) 372 : idx_base_rep (), data (_data), len (_len), ext (_ext), 373 lsti (-1), lste (-1), aowner (nullptr), orig_dims (od) 374 { } 375 376 idx_mask_rep (bool); 377 378 idx_mask_rep (const Array<bool>&, octave_idx_type = -1); 379 380 // No copying! 381 382 idx_mask_rep (const idx_mask_rep& idx) = delete; 383 384 idx_mask_rep& operator = (const idx_mask_rep& idx) = delete; 385 386 ~idx_mask_rep (void); 387 388 octave_idx_type xelem (octave_idx_type i) const; 389 390 octave_idx_type checkelem (octave_idx_type i) const; 391 length(octave_idx_type)392 octave_idx_type length (octave_idx_type) const { return len; } 393 extent(octave_idx_type n)394 octave_idx_type extent (octave_idx_type n) const 395 { return std::max (n, ext); } 396 idx_class(void)397 idx_class_type idx_class (void) const { return class_mask; } 398 399 idx_base_rep * sort_uniq_clone (bool = false) 400 { count++; return this; } 401 402 idx_base_rep * sort_idx (Array<octave_idx_type>&); 403 orig_dimensions(void)404 dim_vector orig_dimensions (void) const { return orig_dims; } 405 is_colon_equiv(octave_idx_type n)406 bool is_colon_equiv (octave_idx_type n) const 407 { return len == n && ext == n; } 408 get_data(void)409 const bool * get_data (void) const { return data; } 410 411 std::ostream& print (std::ostream& os) const; 412 413 Array<bool> unconvert (void) const; 414 415 Array<octave_idx_type> as_array (void); 416 417 private: 418 419 const bool *data; 420 octave_idx_type len; 421 octave_idx_type ext; 422 423 // FIXME: I'm not sure if this is a good design. Maybe it would be 424 // better to employ some sort of generalized iteration scheme. 425 mutable octave_idx_type lsti; 426 mutable octave_idx_type lste; 427 428 // This is a trick to allow user-given mask arrays to be used as 429 // indices without copying. If the following pointer is nonzero, we 430 // do not own the data, but rather have an Array<bool> object that 431 // provides us the data. Note that we need a pointer because we 432 // deferred the Array<T> declaration and we do not want it yet to be 433 // defined. 434 435 Array<bool> *aowner; 436 437 dim_vector orig_dims; 438 }; 439 idx_vector(idx_base_rep * r)440 idx_vector (idx_base_rep *r) : rep (r) { } 441 442 // The shared empty vector representation (for fast default 443 // constructor). 444 static idx_vector_rep *nil_rep (void); 445 446 // The shared empty vector representation with the error flag set. 447 static idx_vector_rep *err_rep (void); 448 449 // If there was an error in constructing the rep, replace it with 450 // empty vector for safety. chkerr(void)451 void chkerr (void) 452 { 453 if (rep->err) 454 { 455 if (--rep->count == 0) 456 delete rep; 457 rep = err_rep (); 458 rep->count++; 459 } 460 } 461 462 public: 463 464 // Fast empty constructor. idx_vector(void)465 idx_vector (void) : rep (nil_rep ()) { rep->count++; } 466 467 // Zero-based constructors (for use from C++). idx_vector(octave_idx_type i)468 idx_vector (octave_idx_type i) : rep (new idx_scalar_rep (i)) 469 { chkerr (); } 470 471 #if OCTAVE_SIZEOF_F77_INT_TYPE != OCTAVE_SIZEOF_IDX_TYPE idx_vector(octave_f77_int_type i)472 idx_vector (octave_f77_int_type i) 473 : rep (new idx_scalar_rep (static_cast<octave_idx_type> (i))) 474 { chkerr (); } 475 #endif 476 477 idx_vector (octave_idx_type start, octave_idx_type limit, 478 octave_idx_type step = 1) rep(new idx_range_rep (start,limit,step))479 : rep (new idx_range_rep (start, limit, step)) 480 { chkerr (); } 481 482 static idx_vector make_range(octave_idx_type start,octave_idx_type step,octave_idx_type len)483 make_range (octave_idx_type start, octave_idx_type step, 484 octave_idx_type len) 485 { 486 return idx_vector (new idx_range_rep (start, len, step, DIRECT)); 487 } 488 idx_vector(const Array<octave_idx_type> & inda)489 idx_vector (const Array<octave_idx_type>& inda) 490 : rep (new idx_vector_rep (inda)) 491 { chkerr (); } 492 493 // Directly pass extent, no checking. idx_vector(const Array<octave_idx_type> & inda,octave_idx_type ext)494 idx_vector (const Array<octave_idx_type>& inda, octave_idx_type ext) 495 : rep (new idx_vector_rep (inda, ext, DIRECT)) 496 { } 497 498 // Colon is best constructed by simply copying (or referencing) this member. 499 static const idx_vector colon; 500 501 // or passing ':' here idx_vector(char c)502 idx_vector (char c) : rep (new idx_colon_rep (c)) { chkerr (); } 503 504 // Conversion constructors (used by interpreter). 505 506 template <typename T> idx_vector(octave_int<T> x)507 idx_vector (octave_int<T> x) : rep (new idx_scalar_rep (x)) { chkerr (); } 508 idx_vector(double x)509 idx_vector (double x) : rep (new idx_scalar_rep (x)) { chkerr (); } 510 idx_vector(float x)511 idx_vector (float x) : rep (new idx_scalar_rep (x)) { chkerr (); } 512 513 // A scalar bool does not necessarily map to scalar index. idx_vector(bool x)514 idx_vector (bool x) : rep (new idx_mask_rep (x)) { chkerr (); } 515 516 template <typename T> idx_vector(const Array<octave_int<T>> & nda)517 idx_vector (const Array<octave_int<T>>& nda) : rep (new idx_vector_rep (nda)) 518 { chkerr (); } 519 idx_vector(const Array<double> & nda)520 idx_vector (const Array<double>& nda) : rep (new idx_vector_rep (nda)) 521 { chkerr (); } 522 idx_vector(const Array<float> & nda)523 idx_vector (const Array<float>& nda) : rep (new idx_vector_rep (nda)) 524 { chkerr (); } 525 526 idx_vector (const Array<bool>& nda); 527 idx_vector(const Range & r)528 idx_vector (const Range& r) 529 : rep (new idx_range_rep (r)) 530 { chkerr (); } 531 idx_vector(const Sparse<bool> & nda)532 idx_vector (const Sparse<bool>& nda) : rep (new idx_vector_rep (nda)) 533 { chkerr (); } 534 idx_vector(const idx_vector & a)535 idx_vector (const idx_vector& a) : rep (a.rep) { rep->count++; } 536 ~idx_vector(void)537 ~idx_vector (void) 538 { 539 if (--rep->count == 0 && rep != nil_rep ()) 540 delete rep; 541 } 542 543 idx_vector& operator = (const idx_vector& a) 544 { 545 if (this != &a) 546 { 547 if (--rep->count == 0 && rep != nil_rep ()) 548 delete rep; 549 550 rep = a.rep; 551 rep->count++; 552 } 553 return *this; 554 } 555 idx_class(void)556 idx_class_type idx_class (void) const { return rep->idx_class (); } 557 558 octave_idx_type length (octave_idx_type n = 0) const 559 { return rep->length (n); } 560 extent(octave_idx_type n)561 octave_idx_type extent (octave_idx_type n) const 562 { return rep->extent (n); } 563 xelem(octave_idx_type n)564 octave_idx_type xelem (octave_idx_type n) const 565 { return rep->xelem (n); } 566 checkelem(octave_idx_type n)567 octave_idx_type checkelem (octave_idx_type n) const 568 { return rep->xelem (n); } 569 operator()570 octave_idx_type operator () (octave_idx_type n) const 571 { return rep->xelem (n); } 572 573 operator bool (void) const 574 { return ! rep->err; } 575 is_colon(void)576 bool is_colon (void) const 577 { return rep->idx_class () == class_colon; } 578 is_scalar(void)579 bool is_scalar (void) const 580 { return rep->idx_class () == class_scalar; } 581 is_range(void)582 bool is_range (void) const 583 { return rep->idx_class () == class_range; } 584 is_colon_equiv(octave_idx_type n)585 bool is_colon_equiv (octave_idx_type n) const 586 { return rep->is_colon_equiv (n); } 587 588 idx_vector sorted (bool uniq = false) const 589 { return idx_vector (rep->sort_uniq_clone (uniq)); } 590 sorted(Array<octave_idx_type> & sidx)591 idx_vector sorted (Array<octave_idx_type>& sidx) const 592 { return idx_vector (rep->sort_idx (sidx)); } 593 orig_dimensions(void)594 dim_vector orig_dimensions (void) const { return rep->orig_dimensions (); } 595 orig_rows(void)596 octave_idx_type orig_rows (void) const 597 { return orig_dimensions () (0); } 598 orig_columns(void)599 octave_idx_type orig_columns (void) const 600 { return orig_dimensions () (1); } 601 orig_empty(void)602 int orig_empty (void) const 603 { return (! is_colon () && orig_dimensions ().any_zero ()); } 604 605 // i/o 606 print(std::ostream & os)607 std::ostream& print (std::ostream& os) const { return rep->print (os); } 608 609 friend std::ostream& operator << (std::ostream& os, const idx_vector& a) 610 { return a.print (os); } 611 612 // Slice with specializations. No checking of bounds! 613 // 614 // This is equivalent to the following loop (but much faster): 615 // 616 // for (octave_idx_type i = 0; i < idx->length (n); i++) 617 // dest[i] = src[idx(i)]; 618 // return i; 619 // 620 template <typename T> 621 octave_idx_type index(const T * src,octave_idx_type n,T * dest)622 index (const T *src, octave_idx_type n, T *dest) const 623 { 624 octave_idx_type len = rep->length (n); 625 626 switch (rep->idx_class ()) 627 { 628 case class_colon: 629 std::copy_n (src, len, dest); 630 break; 631 632 case class_range: 633 { 634 idx_range_rep *r = dynamic_cast<idx_range_rep *> (rep); 635 octave_idx_type start = r->get_start (); 636 octave_idx_type step = r->get_step (); 637 const T *ssrc = src + start; 638 if (step == 1) 639 std::copy_n (ssrc, len, dest); 640 else if (step == -1) 641 std::reverse_copy (ssrc - len + 1, ssrc + 1, dest); 642 else if (step == 0) 643 std::fill_n (dest, len, *ssrc); 644 else 645 { 646 for (octave_idx_type i = 0, j = 0; i < len; i++, j += step) 647 dest[i] = ssrc[j]; 648 } 649 } 650 break; 651 652 case class_scalar: 653 { 654 idx_scalar_rep *r = dynamic_cast<idx_scalar_rep *> (rep); 655 dest[0] = src[r->get_data ()]; 656 } 657 break; 658 659 case class_vector: 660 { 661 idx_vector_rep *r = dynamic_cast<idx_vector_rep *> (rep); 662 const octave_idx_type *data = r->get_data (); 663 for (octave_idx_type i = 0; i < len; i++) 664 dest[i] = src[data[i]]; 665 } 666 break; 667 668 case class_mask: 669 { 670 idx_mask_rep *r = dynamic_cast<idx_mask_rep *> (rep); 671 const bool *data = r->get_data (); 672 octave_idx_type ext = r->extent (0); 673 for (octave_idx_type i = 0; i < ext; i++) 674 if (data[i]) *dest++ = src[i]; 675 } 676 break; 677 678 default: 679 assert (false); 680 break; 681 } 682 683 return len; 684 } 685 686 // Slice assignment with specializations. No checking of bounds! 687 // 688 // This is equivalent to the following loop (but much faster): 689 // 690 // for (octave_idx_type i = 0; i < idx->length (n); i++) 691 // dest[idx(i)] = src[i]; 692 // return i; 693 // 694 template <typename T> 695 octave_idx_type assign(const T * src,octave_idx_type n,T * dest)696 assign (const T *src, octave_idx_type n, T *dest) const 697 { 698 octave_idx_type len = rep->length (n); 699 700 switch (rep->idx_class ()) 701 { 702 case class_colon: 703 std::copy_n (src, len, dest); 704 break; 705 706 case class_range: 707 { 708 idx_range_rep *r = dynamic_cast<idx_range_rep *> (rep); 709 octave_idx_type start = r->get_start (); 710 octave_idx_type step = r->get_step (); 711 T *sdest = dest + start; 712 if (step == 1) 713 std::copy_n (src, len, sdest); 714 else if (step == -1) 715 std::reverse_copy (src, src + len, sdest - len + 1); 716 else 717 { 718 for (octave_idx_type i = 0, j = 0; i < len; i++, j += step) 719 sdest[j] = src[i]; 720 } 721 } 722 break; 723 724 case class_scalar: 725 { 726 idx_scalar_rep *r = dynamic_cast<idx_scalar_rep *> (rep); 727 dest[r->get_data ()] = src[0]; 728 } 729 break; 730 731 case class_vector: 732 { 733 idx_vector_rep *r = dynamic_cast<idx_vector_rep *> (rep); 734 const octave_idx_type *data = r->get_data (); 735 for (octave_idx_type i = 0; i < len; i++) 736 dest[data[i]] = src[i]; 737 } 738 break; 739 740 case class_mask: 741 { 742 idx_mask_rep *r = dynamic_cast<idx_mask_rep *> (rep); 743 const bool *data = r->get_data (); 744 octave_idx_type ext = r->extent (0); 745 for (octave_idx_type i = 0; i < ext; i++) 746 if (data[i]) dest[i] = *src++; 747 } 748 break; 749 750 default: 751 assert (false); 752 break; 753 } 754 755 return len; 756 } 757 758 // Slice fill with specializations. No checking of bounds! 759 // 760 // This is equivalent to the following loop (but much faster): 761 // 762 // for (octave_idx_type i = 0; i < idx->length (n); i++) 763 // dest[idx(i)] = val; 764 // return i; 765 // 766 template <typename T> 767 octave_idx_type fill(const T & val,octave_idx_type n,T * dest)768 fill (const T& val, octave_idx_type n, T *dest) const 769 { 770 octave_idx_type len = rep->length (n); 771 772 switch (rep->idx_class ()) 773 { 774 case class_colon: 775 std::fill_n (dest, len, val); 776 break; 777 778 case class_range: 779 { 780 idx_range_rep *r = dynamic_cast<idx_range_rep *> (rep); 781 octave_idx_type start = r->get_start (); 782 octave_idx_type step = r->get_step (); 783 T *sdest = dest + start; 784 if (step == 1) 785 std::fill_n (sdest, len, val); 786 else if (step == -1) 787 std::fill (sdest - len + 1, sdest + 1, val); 788 else 789 { 790 for (octave_idx_type i = 0, j = 0; i < len; i++, j += step) 791 sdest[j] = val; 792 } 793 } 794 break; 795 796 case class_scalar: 797 { 798 idx_scalar_rep *r = dynamic_cast<idx_scalar_rep *> (rep); 799 dest[r->get_data ()] = val; 800 } 801 break; 802 803 case class_vector: 804 { 805 idx_vector_rep *r = dynamic_cast<idx_vector_rep *> (rep); 806 const octave_idx_type *data = r->get_data (); 807 for (octave_idx_type i = 0; i < len; i++) 808 dest[data[i]] = val; 809 } 810 break; 811 812 case class_mask: 813 { 814 idx_mask_rep *r = dynamic_cast<idx_mask_rep *> (rep); 815 const bool *data = r->get_data (); 816 octave_idx_type ext = r->extent (0); 817 for (octave_idx_type i = 0; i < ext; i++) 818 if (data[i]) dest[i] = val; 819 } 820 break; 821 822 default: 823 assert (false); 824 break; 825 } 826 827 return len; 828 } 829 830 // Generic non-breakable indexed loop. The loop body should be 831 // encapsulated in a single functor body. This is equivalent to the 832 // following loop (but faster, at least for simple inlined bodies): 833 // 834 // for (octave_idx_type i = 0; i < idx->length (n); i++) body (idx(i)); 835 836 template <typename Functor> 837 void loop(octave_idx_type n,Functor body)838 loop (octave_idx_type n, Functor body) const 839 { 840 octave_idx_type len = rep->length (n); 841 842 switch (rep->idx_class ()) 843 { 844 case class_colon: 845 for (octave_idx_type i = 0; i < len; i++) body (i); 846 break; 847 848 case class_range: 849 { 850 idx_range_rep *r = dynamic_cast<idx_range_rep *> (rep); 851 octave_idx_type start = r->get_start (); 852 octave_idx_type step = r->get_step (); 853 octave_idx_type i, j; 854 if (step == 1) 855 for (i = start, j = start + len; i < j; i++) body (i); 856 else if (step == -1) 857 for (i = start, j = start - len; i > j; i--) body (i); 858 else 859 for (i = 0, j = start; i < len; i++, j += step) body (j); 860 } 861 break; 862 863 case class_scalar: 864 { 865 idx_scalar_rep *r = dynamic_cast<idx_scalar_rep *> (rep); 866 body (r->get_data ()); 867 } 868 break; 869 870 case class_vector: 871 { 872 idx_vector_rep *r = dynamic_cast<idx_vector_rep *> (rep); 873 const octave_idx_type *data = r->get_data (); 874 for (octave_idx_type i = 0; i < len; i++) body (data[i]); 875 } 876 break; 877 878 case class_mask: 879 { 880 idx_mask_rep *r = dynamic_cast<idx_mask_rep *> (rep); 881 const bool *data = r->get_data (); 882 octave_idx_type ext = r->extent (0); 883 for (octave_idx_type i = 0; i < ext; i++) 884 if (data[i]) body (i); 885 } 886 break; 887 888 default: 889 assert (false); 890 break; 891 } 892 893 } 894 895 // Generic breakable indexed loop. The loop body should be 896 // encapsulated in a single functor body. This is equivalent to the 897 // following loop (but faster, at least for simple inlined bodies): 898 // 899 // for (octave_idx_type i = 0; i < idx->length (n); i++) 900 // if (body (idx(i))) break; 901 // return i; 902 // 903 904 template <typename Functor> 905 octave_idx_type bloop(octave_idx_type n,Functor body)906 bloop (octave_idx_type n, Functor body) const 907 { 908 octave_idx_type len = rep->length (n), ret; 909 910 switch (rep->idx_class ()) 911 { 912 case class_colon: 913 { 914 octave_idx_type i; 915 for (i = 0; i < len && body (i); i++) ; 916 ret = i; 917 } 918 break; 919 920 case class_range: 921 { 922 idx_range_rep *r = dynamic_cast<idx_range_rep *> (rep); 923 octave_idx_type start = r->get_start (); 924 octave_idx_type step = r->get_step (); 925 octave_idx_type i, j; 926 if (step == 1) 927 for (i = start, j = start + len; i < j && body (i); i++) ; 928 else if (step == -1) 929 for (i = start, j = start - len; i > j && body (i); i--) ; 930 else 931 for (i = 0, j = start; i < len && body (j); i++, j += step) ; 932 ret = i; 933 } 934 break; 935 936 case class_scalar: 937 { 938 idx_scalar_rep *r = dynamic_cast<idx_scalar_rep *> (rep); 939 ret = (body (r->get_data ()) ? 1 : 0); 940 } 941 break; 942 943 case class_vector: 944 { 945 idx_vector_rep *r = dynamic_cast<idx_vector_rep *> (rep); 946 const octave_idx_type *data = r->get_data (); 947 octave_idx_type i; 948 for (i = 0; i < len && body (data[i]); i++) ; 949 ret = i; 950 } 951 break; 952 953 case class_mask: 954 { 955 idx_mask_rep *r = dynamic_cast<idx_mask_rep *> (rep); 956 const bool *data = r->get_data (); 957 octave_idx_type ext = r->extent (0); 958 octave_idx_type j = 0; 959 for (octave_idx_type i = 0; i < ext; i++) 960 { 961 if (data[i]) 962 { 963 if (body (i)) 964 break; 965 else 966 j++; 967 } 968 } 969 970 ret = j; 971 } 972 break; 973 974 default: 975 assert (false); 976 break; 977 } 978 979 return ret; 980 } 981 982 // Rationale: 983 // This method is the key to "smart indexing". When indexing cartesian 984 // arrays, sometimes consecutive index vectors can be reduced into a 985 // single index. If rows (A) = k and i.maybe_reduce (j) gives k, then 986 // A(i,j)(:) is equal to A(k)(:). 987 988 // If the next index can be reduced, returns true and updates this. 989 bool maybe_reduce (octave_idx_type n, const idx_vector& j, 990 octave_idx_type nj); 991 992 bool is_cont_range (octave_idx_type n, 993 octave_idx_type& l, octave_idx_type& u) const; 994 995 // Returns the increment for ranges and colon, 0 for scalars and empty 996 // vectors, 1st difference otherwise. 997 octave_idx_type increment (void) const; 998 999 idx_vector 1000 complement (octave_idx_type n) const; 1001 1002 bool is_permutation (octave_idx_type n) const; 1003 1004 // Returns the inverse permutation. If this is not a permutation on 1:n, the 1005 // result is undefined (but no error unless extent () != n). 1006 idx_vector inverse_permutation (octave_idx_type n) const; 1007 1008 // Copies all the indices to a given array. Not allowed for colons. 1009 void copy_data (octave_idx_type *data) const; 1010 1011 // If the index is a mask, convert it to index vector. 1012 idx_vector unmask (void) const; 1013 1014 // Unconverts the index to a scalar, Range, double array or a mask. 1015 void unconvert (idx_class_type& iclass, 1016 double& scalar, Range& range, 1017 Array<double>& array, Array<bool>& mask) const; 1018 1019 Array<octave_idx_type> as_array (void) const; 1020 1021 // Raw pointer to index array. This is non-const because it may be 1022 // necessary to mutate the index. 1023 const octave_idx_type * raw (void); 1024 1025 bool isvector (void) const; 1026 1027 // FIXME: these are here for compatibility. They should be removed 1028 // when no longer in use. 1029 elem(octave_idx_type n)1030 octave_idx_type elem (octave_idx_type n) const 1031 { return (*this) (n); } 1032 is_colon_equiv(octave_idx_type n,int)1033 bool is_colon_equiv (octave_idx_type n, int) const 1034 { return is_colon_equiv (n); } 1035 1036 octave_idx_type 1037 freeze (octave_idx_type z_len, const char *tag, bool resize_ok = false); 1038 1039 void sort (bool uniq = false) 1040 { *this = sorted (uniq); } 1041 1042 octave_idx_type ones_count (void) const; 1043 max(void)1044 octave_idx_type max (void) const { return extent (1) - 1; } 1045 1046 private: 1047 1048 idx_base_rep *rep; 1049 1050 }; 1051 1052 #endif 1053