ginac/utils_multi_iterator.h

   1 /** @file utils_multi_iterator.h
   2  *
   3  *  Utilities for summing over multiple indices */
   4
   5 /*
   6  *  GiNaC Copyright (C) 1999-2020 Johannes Gutenberg University Mainz, Germany
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software
  20  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  21  */
  22
  23 #ifndef GINAC_UTILS_MULTI_ITERATOR_H
  24 #define GINAC_UTILS_MULTI_ITERATOR_H
  25
  26 #include <cstddef>
  27 #include <vector>
  28 #include <ostream>
  29 #include <iterator>
  30
  31 namespace GiNaC {
  32
  33 /**
  34  *
  35  * SFINAE test for distance
  36  *
  37  */
  38 template <typename T> class has_distance {
  39 private:
  40         typedef char yes_type[1];
  41         typedef char no_type[2];
  42
  43         template <typename C> static yes_type & test( decltype(std::distance<C>) ) ;
  44         template <typename C> static no_type & test(...);
  45
  46 public:
  47         enum { value = sizeof(test<T>(0)) == sizeof(yes_type) };
  48 };
  49
  50 /**
  51  *
  52  * For printing a multi-index:
  53  * If the templates are used, where T is an iterator, printing the address where the iterator points to is not meaningful.
  54  * However, we may print the difference to the starting point.
  55  *
  56  */
  57 template<typename T> typename std::enable_if<has_distance<T>::value, typename std::iterator_traits<T>::difference_type>::type format_index_value(const T & a, const T & b) {
  58                 return std::distance(a,b);
  59 }
  60
  61 /**
  62  *
  63  * For all other cases we simply print the value.
  64  *
  65  */
  66 template<typename T> typename std::enable_if<!has_distance<T>::value, T>::type format_index_value(const T & a, const T & b) {
  67         return b;
  68 }
  69
  70 /**
  71  *
  72  * basic_multi_iterator is a base class.
  73  *
  74  * The base class itself does not do anything useful.
  75  * A typical use of a class derived from basic_multi_iterator is
  76  *
  77  *    multi_iterator_ordered<int> k(0,4,2);
  78  *
  79  *    for( k.init(); !k.overflow(); k++) {
  80  *      std::cout << k << std::endl;
  81  *    }
  82  *
  83  * which prints out
  84  *
  85  *   multi_iterator_ordered(0,1)
  86  *   multi_iterator_ordered(0,2)
  87  *   multi_iterator_ordered(0,3)
  88  *   multi_iterator_ordered(1,2)
  89  *   multi_iterator_ordered(1,3)
  90  *   multi_iterator_ordered(2,3)
  91  *
  92  * Individual components of k can be accessed with k[i] or k(i).
  93  *
  94  * All classes derived from basic_multi_iterator follow the same syntax.
  95  *
  96  */
  97 template<class T> class basic_multi_iterator {
  98
  99         // ctors
 100 public :
 101         basic_multi_iterator(void);
 102         explicit basic_multi_iterator(T B, T N, size_t k);
 103         explicit basic_multi_iterator(T B, T N, const std::vector<T> & vv);
 104
 105         // dtor
 106         virtual ~basic_multi_iterator();
 107
 108         // functions
 109 public :
 110         size_t size(void) const;
 111         bool overflow(void) const;
 112         const std::vector<T> & get_vector(void) const;
 113
 114         // subscripting
 115 public :
 116         T operator[](size_t i) const;
 117         T & operator[](size_t i);
 118
 119         T operator()(size_t i) const;
 120         T & operator()(size_t i);
 121
 122         // virtual functions
 123 public :
 124         // initialization
 125         virtual basic_multi_iterator<T> & init(void);
 126         // postfix increment
 127         virtual basic_multi_iterator<T> & operator++ (int);
 128
 129         // I/O operators
 130         template <class TT> friend std::ostream & operator<< (std::ostream & os, const basic_multi_iterator<TT> & v);
 131
 132         // member variables :
 133 protected :
 134         T N;
 135         T B;
 136         std::vector<T> v;
 137         bool flag_overflow;
 138
 139 };
 140
 141 /**
 142  *
 143  * The class multi_iterator_ordered defines a multi_iterator
 144  * \f$(i_1,i_2,...,i_k)\f$, such that
 145  * \f[
 146  *     B \le i_j < N
 147  * \f]
 148  * and
 149  * \f[
 150  *     i_j < i_{j+1}.
 151  * \f]
 152  * It is assumed that \f$k>0\f$ and \f$ N-B \ge k \f$.
 153  *
 154  */
 155 template<class T> class multi_iterator_ordered : public basic_multi_iterator<T> {
 156
 157         // ctors
 158 public :
 159         multi_iterator_ordered(void);
 160         explicit multi_iterator_ordered(T B, T N, size_t k);
 161         explicit multi_iterator_ordered(T B, T N, const std::vector<T> & vv);
 162
 163         // overriding virtual functions from base class
 164 public :
 165         // initialization
 166         basic_multi_iterator<T> & init(void);
 167         // postfix increment
 168         basic_multi_iterator<T> & operator++ (int);
 169
 170         // I/O operators
 171         template <class TT> friend std::ostream & operator<< (std::ostream & os, const multi_iterator_ordered<TT> & v);
 172
 173 };
 174
 175 /**
 176  *
 177  * The class multi_iterator_ordered_eq defines a multi_iterator
 178  * \f$(i_1,i_2,...,i_k)\f$, such that
 179  * \f[
 180  *     B \le i_j < N
 181  * \f]
 182  * and
 183  * \f[
 184  *     i_j \le i_{j+1}.
 185  * \f]
 186  * It is assumed that \f$k>0\f$.
 187  *
 188  */
 189 template<class T> class multi_iterator_ordered_eq : public basic_multi_iterator<T> {
 190
 191         // ctors
 192 public :
 193         multi_iterator_ordered_eq(void);
 194         explicit multi_iterator_ordered_eq(T B, T N, size_t k);
 195         explicit multi_iterator_ordered_eq(T B, T N, const std::vector<T> & vv);
 196
 197         // overriding virtual functions from base class
 198 public :
 199         // initialization
 200         basic_multi_iterator<T> & init(void);
 201         // postfix increment
 202         basic_multi_iterator<T> & operator++ (int);
 203
 204         // I/O operators
 205         template <class TT> friend std::ostream & operator<< (std::ostream & os, const multi_iterator_ordered_eq<TT> & v);
 206
 207 };
 208
 209 /**
 210  *
 211  * The class multi_iterator_ordered_eq_indv defines a multi_iterator
 212  * \f$(i_1,i_2,...,i_k)\f$, such that
 213  * \f[
 214  *     B \le i_j < N_j
 215  * \f]
 216  * and
 217  * \f[
 218  *     i_j \le i_{j+1}.
 219  * \f]
 220  *
 221  */
 222 template<class T> class multi_iterator_ordered_eq_indv : public basic_multi_iterator<T> {
 223
 224         // ctors
 225 public :
 226         multi_iterator_ordered_eq_indv(void);
 227         explicit multi_iterator_ordered_eq_indv(T B, const std::vector<T> & Nv, size_t k);
 228         explicit multi_iterator_ordered_eq_indv(T B, const std::vector<T> & Nv, const std::vector<T> & vv);
 229
 230         // overriding virtual functions from base class
 231 public :
 232         // initialization
 233         basic_multi_iterator<T> & init(void);
 234         // postfix increment
 235         basic_multi_iterator<T> & operator++ (int);
 236
 237         // I/O operators
 238         template <class TT> friend std::ostream & operator<< (std::ostream & os, const multi_iterator_ordered_eq_indv<TT> & v);
 239
 240         // member variables :
 241 protected :
 242         std::vector<T> Nv;
 243 };
 244
 245 /**
 246  *
 247  * The class multi_iterator_counter defines a multi_iterator
 248  * \f$(i_1,i_2,...,i_k)\f$, such that
 249  * \f[
 250  *     B \le i_j < N
 251  * \f]
 252  *
 253  */
 254 template<class T> class multi_iterator_counter : public basic_multi_iterator<T> {
 255
 256         // ctors
 257 public :
 258         multi_iterator_counter(void);
 259         explicit multi_iterator_counter(T B, T N, size_t k);
 260         explicit multi_iterator_counter(T B, T N, const std::vector<T> & vv);
 261
 262         // overriding virtual functions from base class
 263 public :
 264         // initialization
 265         basic_multi_iterator<T> & init(void);
 266         // postfix increment
 267         basic_multi_iterator<T> & operator++ (int);
 268
 269         // I/O operators
 270         template <class TT> friend std::ostream & operator<< (std::ostream & os, const multi_iterator_counter<TT> & v);
 271
 272 };
 273
 274 /**
 275  *
 276  * The class multi_iterator_counter_indv defines a multi_iterator
 277  * \f$(i_1,i_2,...,i_k)\f$, such that
 278  * \f[
 279  *     B \le i_j < N_j
 280  * \f]
 281  *
 282  */
 283 template<class T> class multi_iterator_counter_indv : public basic_multi_iterator<T> {
 284
 285         // ctors
 286 public :
 287         multi_iterator_counter_indv(void);
 288         explicit multi_iterator_counter_indv(T B, const std::vector<T> & Nv, size_t k);
 289         explicit multi_iterator_counter_indv(T B, const std::vector<T> & Nv, const std::vector<T> & vv);
 290
 291         // overriding virtual functions from base class
 292 public :
 293         // initialization
 294         basic_multi_iterator<T> & init(void);
 295         // postfix increment
 296         basic_multi_iterator<T> & operator++ (int);
 297
 298         // I/O operators
 299         template <class TT> friend std::ostream & operator<< (std::ostream & os, const multi_iterator_counter_indv<TT> & v);
 300
 301         // member variables :
 302 protected :
 303         std::vector<T> Nv;
 304 };
 305
 306 /**
 307  *
 308  * The class multi_iterator_permutation defines a multi_iterator
 309  * \f$(i_1,i_2,...,i_k)\f$, for which
 310  * \f[
 311  *    B \le i_j < N
 312  * \f]
 313  * and
 314  * \f[
 315  *     i_i \neq i_j
 316  * \f]
 317  * In particular, if \f$N-B=k\f$, multi_iterator_permutation loops over all
 318  * permutations of \f$k\f$ elements.
 319  *
 320  */
 321 template<class T> class multi_iterator_permutation : public basic_multi_iterator<T> {
 322
 323         // ctors
 324 public :
 325         multi_iterator_permutation(void);
 326         explicit multi_iterator_permutation(T B, T N, size_t k);
 327         explicit multi_iterator_permutation(T B, T N, const std::vector<T> & vv);
 328
 329         // overriding virtual functions from base class
 330 public :
 331         // initialization
 332         basic_multi_iterator<T> & init(void);
 333         // postfix increment
 334         basic_multi_iterator<T> & operator++ (int);
 335
 336         // new functions in this class
 337         int get_sign(void) const;
 338
 339         // I/O operators
 340         template <class TT> friend std::ostream & operator<< (std::ostream & os, const multi_iterator_permutation<TT> & v);
 341
 342 };
 343
 344 /**
 345  *
 346  * The class multi_iterator_shuffle defines a multi_iterator,
 347  * which runs over all shuffles of a and b.
 348  *
 349  */
 350 template<class T> class multi_iterator_shuffle : public basic_multi_iterator<T> {
 351
 352         // ctors
 353 public :
 354         multi_iterator_shuffle(void);
 355         explicit multi_iterator_shuffle(const std::vector<T> & a, const std::vector<T> & b);
 356
 357         // overriding virtual functions from base class
 358 public :
 359         // initialization
 360         basic_multi_iterator<T> & init(void);
 361         // postfix increment
 362         basic_multi_iterator<T> & operator++ (int);
 363
 364         // I/O operators
 365         template <class TT> friend std::ostream & operator<< (std::ostream & os, const multi_iterator_shuffle<TT> & v);
 366
 367         // member variables :
 368 protected :
 369         size_t N_internal;
 370         std::vector<size_t> v_internal;
 371         std::vector<T> v_orig;
 372 };
 373
 374 /**
 375  *
 376  * The class multi_iterator_shuffle_prime defines a multi_iterator,
 377  * which runs over all shuffles of a and b, excluding the first one (a,b).
 378  *
 379  */
 380 template<class T> class multi_iterator_shuffle_prime : public multi_iterator_shuffle<T> {
 381
 382         // ctors
 383 public :
 384         multi_iterator_shuffle_prime(void);
 385         explicit multi_iterator_shuffle_prime(const std::vector<T> & a, const std::vector<T> & b);
 386
 387         // overriding virtual functions from base class
 388 public :
 389         // initialization
 390         basic_multi_iterator<T> & init(void);
 391
 392         // I/O operators
 393         template <class TT> friend std::ostream & operator<< (std::ostream & os, const multi_iterator_shuffle_prime<TT> & v);
 394 };
 395
 396 // ----------------------------------------------------------------------------------------------------------------
 397
 398 // ctors
 399
 400 /**
 401  *
 402  * Default constructor
 403  *
 404  */
 405 template<class T> inline basic_multi_iterator<T>::basic_multi_iterator(void) : N(), B(), v(), flag_overflow(false)
 406 {}
 407
 408 /**
 409  *
 410  * Construct a multi_iterator with upper limit N, lower limit B and size k .
 411  *
 412  */
 413 template<class T> inline basic_multi_iterator<T>::basic_multi_iterator(T BB, T NN, size_t k) : N(NN), B(BB), v(k), flag_overflow(false)
 414 {}
 415
 416 /**
 417  *
 418  * Construct from a vector.
 419  *
 420  */
 421 template<class T> inline basic_multi_iterator<T>::basic_multi_iterator(T BB, T NN, const std::vector<T> & vv) : N(NN), B(BB), v(vv), flag_overflow(false)
 422 {}
 423
 424 /**
 425  *
 426  * Destructor
 427  *
 428  */
 429 template<class T> inline basic_multi_iterator<T>::~basic_multi_iterator()
 430 {}
 431
 432 // functions
 433
 434 /**
 435  *
 436  * Returns the size of a multi_iterator.
 437  *
 438  */
 439 template<class T> inline size_t basic_multi_iterator<T>::size(void) const
 440 {
 441         return v.size();
 442 }
 443
 444 /**
 445  *
 446  * Initialize the multi-index to
 447  * \f[
 448  *    (n_1,n_2,n_3,...,n_k) = (B,B,...,B)
 449  * \f]
 450  *
 451  */
 452 template<class T> inline basic_multi_iterator<T> & basic_multi_iterator<T>::init(void)
 453 {
 454         flag_overflow = false;
 455
 456         for ( size_t i=0; i<v.size(); i++) {
 457                 v[i] = B;
 458         }
 459         return *this;
 460 }
 461
 462 /**
 463  *
 464  * Return the overflow flag.
 465  *
 466  */
 467 template<class T> inline bool basic_multi_iterator<T>::overflow(void) const
 468 {
 469         return flag_overflow;
 470 }
 471
 472 /**
 473  *
 474  * Returns a reference to the vector v.
 475  *
 476  */
 477 template<class T> inline const std::vector<T> & basic_multi_iterator<T>::get_vector(void) const
 478 {
 479         return v;
 480 }
 481
 482 // subscripting
 483
 484 /**
 485  *
 486  * Subscription via []
 487  *
 488  */
 489 template<class T> inline T basic_multi_iterator<T>::operator[](size_t i) const
 490 {
 491         return v[i];
 492 }
 493
 494 /**
 495  *
 496  * Subscription via []
 497  *
 498  */
 499 template<class T> inline T & basic_multi_iterator<T>::operator[](size_t i)
 500 {
 501         return v[i];
 502 }
 503
 504 /**
 505  *
 506  * Subscription via ()
 507  *
 508  */
 509 template<class T> inline T basic_multi_iterator<T>::operator()(size_t i) const
 510 {
 511         return v[i];
 512 }
 513
 514 /**
 515  *
 516  * Subscription via ()
 517  *
 518  */
 519 template<class T> inline T & basic_multi_iterator<T>::operator()(size_t i)
 520 {
 521         return v[i];
 522 }
 523
 524
 525 /**
 526  *
 527  * No effect for basic_multi_iterator
 528  *
 529  */
 530 template<class T> inline basic_multi_iterator<T> & basic_multi_iterator<T>::operator++ (int)
 531 {
 532         return *this;
 533 }
 534
 535 // I/O operators
 536
 537 /**
 538  *
 539  * Output operator. A multi_iterator prints out as
 540  * basic_multi_iterator(\f$n_0,n_1,...\f$).
 541  *
 542  */
 543 template<class T> inline std::ostream & operator<< (std::ostream & os, const basic_multi_iterator<T> & v)
 544 {
 545         os << "basic_multi_iterator(";
 546         for ( size_t i=0; i<v.size(); i++) {
 547                 if (i>0) {
 548                         os << ",";
 549                 }
 550                 os << format_index_value(v.B,v(i));
 551         }
 552
 553         return os << ")";
 554 }
 555
 556
 557
 558 // ctors
 559
 560 /**
 561  *
 562  * Default constructor
 563  *
 564  */
 565 template<class T> inline multi_iterator_ordered<T>::multi_iterator_ordered(void) : basic_multi_iterator<T>()
 566 {}
 567
 568 /**
 569  *
 570  * Construct a multi_iterator with upper limit N and size k .
 571  *
 572  */
 573 template<class T> inline multi_iterator_ordered<T>::multi_iterator_ordered(T B, T N, size_t k) : basic_multi_iterator<T>(B,N,k)
 574 {}
 575
 576 /**
 577  *
 578  * Construct from a vector.
 579  *
 580  */
 581 template<class T> inline multi_iterator_ordered<T>::multi_iterator_ordered(T B, T N, const std::vector<T> & v) : basic_multi_iterator<T>(B,N,v)
 582 {}
 583
 584 // functions
 585
 586 /**
 587  *
 588  * Initialize the multi-index to
 589  * \f[
 590  *    (n_1,n_2,n_3,...,n_k) = (B+0,B+1,B+2,...,B+k-1)
 591  * \f]
 592  *
 593  */
 594 template<class T> inline basic_multi_iterator<T> & multi_iterator_ordered<T>::init(void)
 595 {
 596         this->flag_overflow = false;
 597         T it = this->B;
 598
 599         for ( size_t i=0; i < this->v.size(); i++) {
 600                 this->v[i] = it;
 601                 it++;
 602         }
 603         return *this;
 604 }
 605
 606 /**
 607  *
 608  * The postfix increment operator allows to
 609  * write for a multi-index n++, which will
 610  * update n to the next configuration.
 611  *
 612  * If n is in the last configuration and the
 613  * increment operator ++ is applied to n,
 614  * the overflow flag will be raised.
 615  *
 616  */
 617 template<class T> inline basic_multi_iterator<T> & multi_iterator_ordered<T>::operator++ (int)
 618 {
 619         int k = this->size();
 620         int j = k - 1;
 621         T Upper_limit = this->N;
 622
 623         while ( j>0 ) {
 624                 this->v[j]++;
 625                 if ( this->v[j] == Upper_limit ) {
 626                         j--;
 627                         Upper_limit--;
 628                 }
 629                 else {
 630                         break;
 631                 }
 632         }
 633
 634         if (j==0) {
 635                 this->v[j]++;
 636                 if (this->v[j] == Upper_limit) this->flag_overflow=true;
 637         }
 638
 639         if ( j>= 0) {
 640                 for (int jj=j+1;jj<k;jj++) {
 641                         this->v[jj] = this->v[jj-1];
 642                         this->v[jj]++;
 643                 }
 644         }
 645
 646         return *this;
 647 }
 648
 649 // I/O operators
 650
 651 /**
 652  *
 653  * Output operator. A multi_iterator_ordered prints out as
 654  * multi_iterator_ordered(\f$n_0,n_1,...\f$).
 655  *
 656  */
 657 template<class T> inline std::ostream & operator<< (std::ostream & os, const multi_iterator_ordered<T> & v)
 658 {
 659         os << "multi_iterator_ordered(";
 660         for ( size_t i=0; i<v.size(); i++) {
 661                 if (i>0) {
 662                         os << ",";
 663                 }
 664                 os << format_index_value(v.B,v(i));
 665         }
 666
 667         return os << ")";
 668 }
 669
 670
 671
 672 // ctors
 673
 674 /**
 675  *
 676  * Default constructor
 677  *
 678  */
 679 template<class T> inline multi_iterator_ordered_eq<T>::multi_iterator_ordered_eq(void) : basic_multi_iterator<T>()
 680 {}
 681
 682 /**
 683  *
 684  * Construct a multi_iterator with upper limit N and size k .
 685  *
 686  */
 687 template<class T> inline multi_iterator_ordered_eq<T>::multi_iterator_ordered_eq(T B, T N, size_t k) : basic_multi_iterator<T>(B,N,k)
 688 {}
 689
 690 /**
 691  *
 692  * Construct from a vector.
 693  *
 694  */
 695 template<class T> inline multi_iterator_ordered_eq<T>::multi_iterator_ordered_eq(T B, T N, const std::vector<T> & v) : basic_multi_iterator<T>(B,N,v)
 696 {}
 697
 698 // functions
 699
 700 /**
 701  *
 702  * Initialize the multi-index to
 703  * \f[
 704  *    (n_1,n_2,...,n_k) = (B,B,...,B)
 705  * \f]
 706  *
 707  */
 708 template<class T> inline basic_multi_iterator<T> & multi_iterator_ordered_eq<T>::init(void)
 709 {
 710         this->flag_overflow = false;
 711
 712         for ( size_t i=0; i < this->v.size(); i++) {
 713                 this->v[i] = this->B;
 714         }
 715         return *this;
 716 }
 717
 718 /**
 719  *
 720  * The postfix increment operator allows to
 721  * write for a multi-index n++, which will
 722  * update n to the next configuration.
 723  *
 724  * If n is in the last configuration and the
 725  * increment operator ++ is applied to n,
 726  * the overflow flag will be raised.
 727  *
 728  */
 729 template<class T> inline basic_multi_iterator<T> & multi_iterator_ordered_eq<T>::operator++ (int)
 730 {
 731         int k = this->size();
 732         int j = k - 1;
 733
 734         while ( j>0 ) {
 735                 this->v[j]++;
 736                 if ( this->v[j] == this->N ) {
 737                         j--;
 738                 }
 739                 else {
 740                         break;
 741                 }
 742         }
 743
 744         if (j==0) {
 745                 this->v[j]++;
 746                 if (this->v[j] == this->N) {
 747                         this->flag_overflow=true;
 748                 }
 749         }
 750
 751         if ( j>= 0) {
 752                 for (int jj=j+1;jj<k;jj++) {
 753                         this->v[jj] = this->v[jj-1];
 754                 }
 755         }
 756
 757         return *this;
 758 }
 759
 760 // I/O operators
 761
 762 /**
 763  *
 764  * Output operator. A multi_iterator_ordered_eq prints out as
 765  * multi_iterator_ordered_eq(\f$n_0,n_1,...\f$).
 766  *
 767  */
 768 template<class T> inline std::ostream & operator<< (std::ostream & os, const multi_iterator_ordered_eq<T> & v)
 769 {
 770         os << "multi_iterator_ordered_eq(";
 771         for ( size_t i=0; i<v.size(); i++) {
 772                 if (i>0) {
 773                         os << ",";
 774                 }
 775                 os << format_index_value(v.B,v(i));
 776         }
 777
 778         return os << ")";
 779 }
 780
 781
 782
 783
 784 // ctors
 785
 786 /**
 787  *
 788  * Default constructor
 789  *
 790  */
 791 template<class T> inline multi_iterator_ordered_eq_indv<T>::multi_iterator_ordered_eq_indv(void) : basic_multi_iterator<T>(), Nv()
 792 {}
 793
 794 /**
 795  *
 796  * Construct a multi_iterator with upper limit N and size k .
 797  *
 798  */
 799 template<class T> inline multi_iterator_ordered_eq_indv<T>::multi_iterator_ordered_eq_indv(T B, const std::vector<T> & Nvv, size_t k) : basic_multi_iterator<T>(B,B,k), Nv(Nvv)
 800 {}
 801
 802 /**
 803  *
 804  * Construct from a vector.
 805  *
 806  */
 807 template<class T> inline multi_iterator_ordered_eq_indv<T>::multi_iterator_ordered_eq_indv(T B, const std::vector<T> & Nvv, const std::vector<T> & v) : basic_multi_iterator<T>(B,B,v), Nv(Nvv)
 808 {}
 809
 810 // functions
 811
 812 /**
 813  *
 814  * Initialize the multi-index to
 815  * \f[
 816  *    (n_1,n_2,n_3,...,n_k) = (B,B,B,...,B)
 817  * \f]
 818  *
 819  */
 820 template<class T> inline basic_multi_iterator<T> & multi_iterator_ordered_eq_indv<T>::init(void)
 821 {
 822         this->flag_overflow = false;
 823
 824         for ( size_t i=0; i < this->v.size(); i++) {
 825                 this->v[i] = this->B;
 826         }
 827         return *this;
 828 }
 829
 830 /**
 831  *
 832  * The postfix increment operator allows to
 833  * write for a multi-index n++, which will
 834  * update n to the next configuration.
 835  *
 836  * If n is in the last configuration and the
 837  * increment operator ++ is applied to n,
 838  * the overflow flag will be raised.
 839  *
 840  */
 841 template<class T> inline basic_multi_iterator<T> & multi_iterator_ordered_eq_indv<T>::operator++ (int)
 842 {
 843         int k = this->size();
 844         int j = k - 1;
 845
 846         while ( j>0 ) {
 847                 this->v[j]++;
 848                 if ( this->v[j] == Nv[j] ) {
 849                         j--;
 850                 }
 851                 else {
 852                         break;
 853                 }
 854         }
 855
 856         if (j==0) {
 857                 this->v[j]++;
 858                 if (this->v[j] == Nv[j]) {
 859                         this->flag_overflow=true;
 860                 }
 861         }
 862
 863         if ( j>= 0) {
 864                 for (int jj=j+1;jj<k;jj++) {
 865                         this->v[jj] = this->v[jj-1];
 866                 }
 867         }
 868
 869         return *this;
 870 }
 871
 872 // I/O operators
 873
 874 /**
 875  *
 876  * Output operator. A multi_iterator_ordered_eq_indv prints out as
 877  * multi_iterator_ordered_eq_indv(\f$n_0,n_1,...\f$).
 878  *
 879  */
 880 template<class T> inline std::ostream & operator<< (std::ostream & os, const multi_iterator_ordered_eq_indv<T> & v)
 881 {
 882         os << "multi_iterator_ordered_eq_indv(";
 883         for ( size_t i=0; i<v.size(); i++) {
 884                 if (i>0) {
 885                         os << ",";
 886                 }
 887                 os << format_index_value(v.B,v(i));
 888         }
 889
 890         return os << ")";
 891 }
 892
 893
 894
 895
 896 // ctors
 897
 898 /**
 899  *
 900  * Default constructor
 901  *
 902  */
 903 template<class T> inline multi_iterator_counter<T>::multi_iterator_counter(void) : basic_multi_iterator<T>()
 904 {}
 905
 906 /**
 907  *
 908  * Construct a multi_iterator with upper limit N and size k .
 909  *
 910  */
 911 template<class T> inline multi_iterator_counter<T>::multi_iterator_counter(T B, T N, size_t k) : basic_multi_iterator<T>(B,N,k)
 912 {}
 913
 914 /**
 915  *
 916  * Construct from a vector.
 917  *
 918  */
 919 template<class T> inline multi_iterator_counter<T>::multi_iterator_counter(T B, T N, const std::vector<T> & v) : basic_multi_iterator<T>(B,N,v)
 920 {}
 921
 922 // functions
 923
 924 /**
 925  *
 926  * Initialize the multi-index to
 927  * \f[
 928  *    (n_1,n_2,n_3,...,n_k) = (B,B,...,B)
 929  * \f]
 930  *
 931  */
 932 template<class T> inline basic_multi_iterator<T> & multi_iterator_counter<T>::init(void)
 933 {
 934         this->flag_overflow = false;
 935
 936         for ( size_t i=0; i < this->v.size(); i++) {
 937                 this->v[i] = this->B;
 938         }
 939         return *this;
 940 }
 941
 942 /**
 943  *
 944  * The postfix increment operator allows to
 945  * write for a multi-index n++, which will
 946  * update n to the next configuration.
 947  *
 948  * If n is in the last configuration and the
 949  * increment operator ++ is applied to n,
 950  * the overflow flag will be raised.
 951  *
 952  */
 953 template<class T> inline basic_multi_iterator<T> & multi_iterator_counter<T>::operator++ (int)
 954 {
 955         int k = this->size();
 956         int j = k - 1;
 957
 958         while ( j>0 ) {
 959                 this->v[j]++;
 960                 if ( this->v[j] == this->N ) {
 961                         this->v[j] = this->B;
 962                         j--;
 963                 }
 964                 else {
 965                         break;
 966                 }
 967         }
 968
 969         if (j==0) {
 970                 this->v[j]++;
 971                 if (this->v[j] == this->N) {
 972                         this->v[j] = this->B;
 973                         this->flag_overflow=true;
 974                 }
 975         }
 976
 977         return *this;
 978 }
 979
 980 // I/O operators
 981
 982 /**
 983  *
 984  * Output operator. A multi_iterator_counter prints out as
 985  * multi_iterator_counter(\f$n_0,n_1,...\f$).
 986  *
 987  */
 988 template<class T> inline std::ostream & operator<< (std::ostream & os, const multi_iterator_counter<T> & v)
 989 {
 990         os << "multi_iterator_counter(";
 991         for ( size_t i=0; i<v.size(); i++) {
 992                 if (i>0) {
 993                         os << ",";
 994                 }
 995                 os << format_index_value(v.B,v(i));
 996         }
 997
 998         return os << ")";
 999 }
1000
1001
1002
1003
1004 // ctors
1005
1006 /**
1007  *
1008  * Default constructor
1009  *
1010  */
1011 template<class T> inline multi_iterator_counter_indv<T>::multi_iterator_counter_indv(void) : basic_multi_iterator<T>(), Nv()
1012 {}
1013
1014 /**
1015  *
1016  * Construct a multi_iterator with upper limit N and size k .
1017  *
1018  */
1019 template<class T> inline multi_iterator_counter_indv<T>::multi_iterator_counter_indv(T B, const std::vector<T> & Nvv, size_t k) : basic_multi_iterator<T>(B,B,k), Nv(Nvv)
1020 {}
1021
1022 /**
1023  *
1024  * Construct from a vector.
1025  *
1026  */
1027 template<class T> inline multi_iterator_counter_indv<T>::multi_iterator_counter_indv(T B, const std::vector<T> & Nvv, const std::vector<T> & v) : basic_multi_iterator<T>(B,B,v), Nv(Nvv)
1028 {}
1029
1030 // functions
1031
1032 /**
1033  *
1034  * Initialize the multi-index to
1035  * \f[
1036  *    (n_1,n_2,n_3,...,n_k) = (B,B,...,B)
1037  * \f]
1038  *
1039  */
1040 template<class T> inline basic_multi_iterator<T> & multi_iterator_counter_indv<T>::init(void)
1041 {
1042         this->flag_overflow = false;
1043
1044         for ( size_t i=0; i < this->v.size(); i++) {
1045                 this->v[i] = this->B;
1046         }
1047         return *this;
1048 }
1049
1050 /**
1051  *
1052  * The postfix increment operator allows to
1053  * write for a multi-index n++, which will
1054  * update n to the next configuration.
1055  *
1056  * If n is in the last configuration and the
1057  * increment operator ++ is applied to n,
1058  * the overflow flag will be raised.
1059  *
1060  */
1061 template<class T> inline basic_multi_iterator<T> & multi_iterator_counter_indv<T>::operator++ (int)
1062 {
1063         int k = this->size();
1064         int j = k - 1;
1065
1066         while ( j>0 ) {
1067                 this->v[j]++;
1068                 if ( this->v[j] == Nv[j] ) {
1069                         this->v[j] = this->B;
1070                         j--;
1071                 }
1072                 else {
1073                         break;
1074                 }
1075         }
1076
1077         if (j==0) {
1078                 this->v[j]++;
1079                 if (this->v[j] == Nv[j]) {
1080                         this->v[j] = this->B;
1081                         this->flag_overflow=true;
1082                 }
1083         }
1084
1085         return *this;
1086 }
1087
1088 // I/O operators
1089
1090 /**
1091  *
1092  * Output operator. A multi_iterator_counter_indv prints out as
1093  * multi_iterator_counter_indv(\f$n_0,n_1,...\f$).
1094  *
1095  */
1096 template<class T> inline std::ostream & operator<< (std::ostream & os, const multi_iterator_counter_indv<T> & v)
1097 {
1098         os << "multi_iterator_counter_indv(";
1099         for ( size_t i=0; i<v.size(); i++) {
1100                 if (i>0) {
1101                         os << ",";
1102                 }
1103                 os << format_index_value(v.B,v(i));
1104         }
1105
1106         return os << ")";
1107 }
1108
1109
1110
1111
1112 // ctors
1113
1114 /**
1115  *
1116  * Default constructor
1117  *
1118  */
1119 template<class T> inline multi_iterator_permutation<T>::multi_iterator_permutation(void) : basic_multi_iterator<T>()
1120 {}
1121
1122 /**
1123  *
1124  * Construct a multi_iterator with upper limit N and size k .
1125  *
1126  */
1127 template<class T> inline multi_iterator_permutation<T>::multi_iterator_permutation(T B, T N, size_t k) : basic_multi_iterator<T>(B,N,k)
1128 {}
1129
1130 /**
1131  *
1132  * Construct from a vector.
1133  *
1134  */
1135 template<class T> inline multi_iterator_permutation<T>::multi_iterator_permutation(T B, T N, const std::vector<T> & v) : basic_multi_iterator<T>(B,N,v)
1136 {}
1137
1138 // functions
1139
1140 /**
1141  *
1142  * Initialize the multi-index to
1143  * \f[
1144  *    (n_1,n_2,n_3,...,n_k) = (B+0,B+1,B+2,...,B+k-1)
1145  * \f]
1146  *
1147  */
1148 template<class T> inline basic_multi_iterator<T> & multi_iterator_permutation<T>::init(void)
1149 {
1150         this->flag_overflow = false;
1151         T it = this->B;
1152
1153         for ( size_t i=0; i < this->v.size(); i++) {
1154                 this->v[i] = it;
1155                 it++;
1156         }
1157         return *this;
1158 }
1159
1160 /**
1161  *
1162  * The postfix increment operator allows to
1163  * write for a multi-index n++, which will
1164  * update n to the next configuration.
1165  *
1166  * If n is in the last configuration and the
1167  * increment operator ++ is applied to n,
1168  * the overflow flag will be raised.
1169  *
1170  */
1171 template<class T> inline basic_multi_iterator<T> & multi_iterator_permutation<T>::operator++ (int)
1172 {
1173         int k = this->size();
1174         int j = k - 1;
1175
1176         while ( j>=0 ) {
1177                 bool flag_have_already = true;
1178                 while ( flag_have_already ) {
1179                         this->v[j]++;
1180
1181                         // update flag_have_already
1182                         flag_have_already = false;
1183                         for (int ii=0; ii<j; ii++) {
1184                                 if (this->v[j] == this->v[ii]) {
1185                                         flag_have_already = true;
1186                                 }
1187                         }
1188                 }
1189
1190                 if ( this->v[j] == this->N ) {
1191                         j--;
1192                 }
1193                 else {
1194                         break;
1195                 }
1196         }
1197
1198         for (int l=j+1; l<k; l++) {
1199                 this->v[l] = this->B;
1200
1201                 bool flag_have_already;
1202                 do {
1203                         flag_have_already = false;
1204                         for (int ii=0; ii<l; ii++) {
1205                                 if (this->v[l] == this->v[ii]) {
1206                                         flag_have_already = true;
1207                                 }
1208                         }
1209                         if (flag_have_already) {
1210                                 this->v[l]++;
1211                         }
1212                 }
1213                 while (flag_have_already);
1214         }
1215
1216         // check for overflow
1217         this->flag_overflow = true;
1218         T it = this->B;
1219         for (int ii=0; ii<k; ii++) {
1220                 if (this->v[ii] != it) {
1221                         this->flag_overflow = false;
1222                 }
1223                 it++;
1224         }
1225
1226         return *this;
1227 }
1228
1229 /**
1230  *
1231  * Returns the sign of the permutation, defined by
1232  * \f[
1233  *     \left(-1\right)^{n_{inv}},
1234  * \f]
1235  * where \f$ n_{inv} \f$ is the number of inversions, e.g. the
1236  * number of pairs \f$ i < j \f$ for which
1237  * \f[
1238  *     n_i > n_j.
1239  * \f]
1240  *
1241  */
1242 template<class T> inline int multi_iterator_permutation<T>::get_sign() const
1243 {
1244         int sign = 1;
1245         int k = this->size();
1246
1247         for ( int i=0; i<k; i++) {
1248                 for ( int j=i+1; j<k; j++) {
1249                         // works only for random-access iterators
1250                         if ( this->v[i] > this->v[j] ) {
1251                                 sign = -sign;
1252                         }
1253                 }
1254         }
1255
1256         return sign;
1257 }
1258
1259
1260 // I/O operators
1261
1262 /**
1263  *
1264  * Output operator. A multi_iterator_permutation prints out as
1265  * multi_iterator_permutation(\f$n_0,n_1,...\f$).
1266  *
1267  */
1268 template<class T> inline std::ostream & operator<< (std::ostream & os, const multi_iterator_permutation<T> & v)
1269 {
1270         os << "multi_iterator_permutation(";
1271         for ( size_t i=0; i<v.size(); i++) {
1272                 if (i>0) {
1273                         os << ",";
1274                 }
1275                 os << format_index_value(v.B,v(i));
1276         }
1277
1278         return os << ")";
1279 }
1280
1281
1282
1283 // ctors
1284
1285 /**
1286  *
1287  * Default constructor
1288  *
1289  */
1290 template<class T> inline multi_iterator_shuffle<T>::multi_iterator_shuffle(void) : basic_multi_iterator<T>(), N_internal(), v_internal(), v_orig()
1291 {}
1292
1293 /**
1294  *
1295  * Construct from a vector.
1296  *
1297  */
1298 template<class T> inline multi_iterator_shuffle<T>::multi_iterator_shuffle(const std::vector<T> & a, const std::vector<T> & b) : basic_multi_iterator<T>(), N_internal(), v_internal(), v_orig()
1299 {
1300         this->B = a[0];
1301
1302         for (size_t i=0; i<a.size(); i++) {
1303                 this->v.push_back( a[i] );
1304                 this->v_orig.push_back( a[i] );
1305                 this->v_internal.push_back( i );
1306         }
1307         for (size_t i=0; i<b.size(); i++) {
1308                 this->v.push_back( b[i] );
1309                 this->v_orig.push_back( b[i] );
1310         }
1311         this->N_internal = this->v.size();
1312 }
1313
1314 // functions
1315
1316 /**
1317  *
1318  * Initialize the multi-index to the first shuffle.
1319  *
1320  */
1321 template<class T> inline basic_multi_iterator<T> & multi_iterator_shuffle<T>::init(void)
1322 {
1323         this->flag_overflow = false;
1324
1325         for ( size_t i=0; i < this->v_internal.size(); i++) {
1326                 this->v_internal[i] = i;
1327         }
1328         for ( size_t i=0; i < this->v.size(); i++) {
1329                 this->v[i] = this->v_orig[i];
1330         }
1331         return *this;
1332 }
1333
1334 /**
1335  *
1336  * The postfix increment operator allows to
1337  * write for a multi-index n++, which will
1338  * update n to the next configuration.
1339  *
1340  * If n is in the last configuration and the
1341  * increment operator ++ is applied to n,
1342  * the overflow flag will be raised.
1343  *
1344  */
1345 template<class T> inline basic_multi_iterator<T> & multi_iterator_shuffle<T>::operator++ (int)
1346 {
1347         int k = this->v_internal.size();
1348         int j = k - 1;
1349         size_t Upper_limit = this->N_internal;
1350
1351         while ( j>0 ) {
1352                 this->v_internal[j]++;
1353                 if ( this->v_internal[j] == Upper_limit ) {
1354                         j--;
1355                         Upper_limit--;
1356                 }
1357                 else {
1358                         break;
1359                 }
1360         }
1361
1362         if (j==0) {
1363                 this->v_internal[j]++;
1364                 if (this->v_internal[j] == Upper_limit) {
1365                         this->flag_overflow=true;
1366                 }
1367         }
1368
1369         if ( j>= 0) {
1370                 for (int jj=j+1;jj<k;jj++) {
1371                         this->v_internal[jj] = this->v_internal[jj-1];
1372                         this->v_internal[jj]++;
1373                 }
1374         }
1375
1376         // update v
1377         if ( !(this->flag_overflow) ) {
1378                 size_t i_a = 0;
1379                 size_t i_b = 0;
1380                 size_t i_all = 0;
1381                 for (size_t j=0; j<k; j++) {
1382                         for (size_t i=i_all; i < this->v_internal[j]; i++) {
1383                                 this->v[i_all] = this->v_orig[k+i_b];
1384                                 i_b++;
1385                                 i_all++;
1386                         }
1387                         this->v[i_all] = this->v_orig[i_a];
1388                         i_a++;
1389                         i_all++;
1390                 }
1391                 for (size_t i = this->v_internal[k-1]+1; i < this->v.size(); i++) {
1392                         this->v[i_all] = this->v_orig[k+i_b];
1393                         i_b++;
1394                         i_all++;
1395                 }
1396         }
1397
1398         return *this;
1399 }
1400
1401 // I/O operators
1402
1403 /**
1404  *
1405  * Output operator. A multi_iterator_shuffle prints out as
1406  * multi_iterator_shuffle(\f$n_0,n_1,...\f$).
1407  *
1408  */
1409 template<class T> inline std::ostream & operator<< (std::ostream & os, const multi_iterator_shuffle<T> & v)
1410 {
1411         os << "multi_iterator_shuffle(";
1412         for ( size_t i=0; i<v.size(); i++) {
1413                 if (i>0) {
1414                         os << ",";
1415                 }
1416                 os << format_index_value(v.B,v(i));
1417         }
1418
1419         return os << ")";
1420 }
1421
1422
1423
1424 // ctors
1425
1426 /**
1427  *
1428  * Default constructor
1429  *
1430  */
1431 template<class T> inline multi_iterator_shuffle_prime<T>::multi_iterator_shuffle_prime(void) : multi_iterator_shuffle<T>()
1432 {}
1433
1434 /**
1435  *
1436  * Construct from a vector.
1437  *
1438  */
1439 template<class T> inline multi_iterator_shuffle_prime<T>::multi_iterator_shuffle_prime(const std::vector<T> & a, const std::vector<T> & b) : multi_iterator_shuffle<T>(a,b)
1440 {}
1441
1442 // functions
1443
1444 /**
1445  *
1446  * Initialize the multi-index to the first shuffle.
1447  *
1448  */
1449 template<class T> inline basic_multi_iterator<T> & multi_iterator_shuffle_prime<T>::init(void)
1450 {
1451         this->flag_overflow = false;
1452
1453         for ( size_t i=0; i < this->v_internal.size(); i++) {
1454                 this->v_internal[i] = i;
1455         }
1456         for ( size_t i=0; i < this->v.size(); i++) {
1457                 this->v[i] = this->v_orig[i];
1458         }
1459
1460         (*this)++;
1461
1462         return *this;
1463 }
1464
1465 // I/O operators
1466
1467 /**
1468  *
1469  * Output operator. A multi_iterator_shuffle_prime prints out as
1470  * multi_iterator_shuffle_prime(\f$n_0,n_1,...\f$).
1471  *
1472  */
1473 template<class T> inline std::ostream & operator<< (std::ostream & os, const multi_iterator_shuffle_prime<T> & v)
1474 {
1475         os << "multi_iterator_shuffle_prime(";
1476         for ( size_t i=0; i<v.size(); i++) {
1477                 if (i>0) {
1478                         os << ",";
1479                 }
1480                 os << format_index_value(v.B,v(i));
1481         }
1482
1483         return os << ")";
1484 }
1485
1486 } // namespace GiNaC
1487
1488 #endif // ndef GINAC_UTILS_MULTI_ITERATOR_H