1 /* 2 3 Cadabra: a field-theory motivated computer algebra system. 4 Copyright (C) 2001-2011 Kasper Peeters <kasper.peeters@aei.mpg.de> 5 6 This program is free software: you can redistribute it and/or 7 modify it under the terms of the GNU General Public License as 8 published by the Free Software Foundation, either version 3 of the 9 License, or (at your option) any later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program. If not, see <http://www.gnu.org/licenses/>. 18 19 */ 20 21 /* 22 - TODO: has_nullifying trace is wrong, but needs to be merged with the 23 input_asym code in order to be more useful. 24 25 */ 26 27 #pragma once 28 29 #include <cstddef> 30 #include <iostream> 31 #include <iterator> 32 #include <vector> 33 #include <list> 34 #include <gmpxx.h> 35 #include "Combinatorics.hh" 36 #include <cstddef> 37 38 typedef mpz_class yngint_t; 39 typedef mpq_class yngrat_t; 40 41 /// Generic Young tableaux routines 42 namespace yngtab { 43 44 // The tableau_base is the abstract interface; does not depend on the 45 // actual storage format. 46 47 class tableau_base { 48 public: 49 tableau_base(); 50 virtual ~tableau_base(); 51 virtual unsigned int number_of_rows() const=0; 52 virtual unsigned int row_size(unsigned int row) const=0; 53 virtual unsigned int column_size(unsigned int col) const; // FIXME: maybe make pure virt too 54 virtual void add_box(unsigned int row)=0; 55 virtual void remove_box(unsigned int row)=0; 56 virtual void add_row(unsigned int row_size); 57 virtual void clear()=0; 58 59 yngrat_t multiplicity; // also keeps track of signs 60 int selfdual_column; // -n, 0, n for antiselfdual, no, selfdual (count from 1) 61 yngint_t dimension(unsigned int) const; 62 unsigned long hook_length(unsigned int row, unsigned int col) const; 63 yngint_t hook_length_prod() const; 64 }; 65 66 class tableau : public tableau_base { 67 public: 68 virtual ~tableau(); 69 virtual unsigned int number_of_rows() const; 70 virtual unsigned int row_size(unsigned int row) const; 71 virtual void add_box(unsigned int row); 72 virtual void remove_box(unsigned int row); 73 virtual void clear(); 74 75 tableau& operator=(const tableau&); 76 private: 77 std::vector<int> rows; 78 }; 79 80 template<class T> 81 class tableaux; 82 83 template<class T> 84 class filled_tableau : public tableau { 85 public: 86 typedef T value_type; 87 88 virtual ~filled_tableau(); 89 virtual unsigned int number_of_rows() const; 90 virtual unsigned int row_size(unsigned int row) const; 91 virtual void add_box(unsigned int row); 92 virtual void remove_box(unsigned int row); 93 std::pair<int, int> find(const T&) const; 94 virtual void clear(); 95 96 void copy_shape(const tableau&); 97 98 T& operator()(unsigned int row, unsigned int col); 99 const T& operator()(unsigned int row, unsigned int col) const; 100 const T& operator[](unsigned int boxnum) const; 101 void add_box(unsigned int rownum, T val); 102 void swap_columns(unsigned int c1, unsigned int c2); 103 104 bool compare_without_multiplicity(const filled_tableau<T>& other) const; 105 bool has_nullifying_trace() const; 106 void sort_within_columns(); 107 void sort_columns(); 108 /// Sort equal-length columns and sort within columns. 109 void canonicalise(); 110 std::pair<int, int> nonstandard_loc() const; 111 template<class StrictWeakOrdering> void sort_within_columns(StrictWeakOrdering comp); 112 template<class StrictWeakOrdering> void sort_columns(StrictWeakOrdering comp); 113 template<class StrictWeakOrdering> void canonicalise(StrictWeakOrdering comp, bool only_col_ex=false); 114 void projector(combin::symmetriser<T>&, bool modulo_monoterm=false) const; 115 void projector(combin::symmetriser<T>&, combin::range_vector_t&) const; 116 yngrat_t projector_normalisation() const; 117 118 filled_tableau<T>& operator=(const filled_tableau<T>&); 119 120 class iterator_base { 121 public: 122 typedef T value_type; 123 typedef T* pointer; 124 typedef T& reference; 125 typedef size_t size_type; 126 typedef ptrdiff_t difference_type; 127 typedef std::random_access_iterator_tag iterator_category; 128 }; 129 130 class const_iterator_base { 131 public: 132 typedef T value_type; 133 typedef const T* pointer; 134 typedef const T& reference; 135 typedef size_t size_type; 136 typedef ptrdiff_t difference_type; 137 typedef std::random_access_iterator_tag iterator_category; 138 }; 139 140 class const_iterator; 141 class in_column_iterator; 142 class in_column_const_iterator; 143 class in_row_iterator; 144 class in_row_const_iterator; 145 146 /// An iterator which stays inside a given column of a tableau. 147 class in_column_iterator : public iterator_base { 148 public: 149 in_column_iterator(unsigned int r, unsigned int c, filled_tableau<T> *); 150 T& operator*() const; 151 T* operator->() const; 152 in_column_iterator& operator++(); 153 in_column_iterator operator++(int); 154 in_column_iterator& operator--(); 155 in_column_iterator operator--(int); 156 in_column_iterator operator+(unsigned int); 157 in_column_iterator operator-(unsigned int); 158 in_column_iterator& operator+=(unsigned int); 159 in_column_iterator& operator-=(unsigned int); 160 T& operator[](int n) const; 161 bool operator<(const in_column_iterator& other) const; 162 bool operator>(const in_column_iterator& other) const; 163 bool operator<=(const in_column_iterator& other) const; 164 bool operator>=(const in_column_iterator& other) const; 165 ptrdiff_t operator-(const in_column_iterator&) const; 166 bool operator==(const in_column_iterator&) const; 167 bool operator!=(const in_column_iterator&) const; 168 169 friend class filled_tableau<T>; 170 friend class filled_tableau<T>::in_column_const_iterator; 171 private: 172 filled_tableau<T> *tab; 173 unsigned int column_number, row_number; 174 }; 175 176 /// A const iterator which stays inside a given column of a tableau. 177 class in_column_const_iterator : public const_iterator_base { 178 public: 179 in_column_const_iterator(unsigned int r, unsigned int c, const filled_tableau<T>*); 180 in_column_const_iterator(const in_column_iterator& other); 181 const T& operator*() const; 182 const T* operator->() const; 183 in_column_const_iterator& operator++(); 184 in_column_const_iterator operator++(int); 185 in_column_const_iterator& operator--(); 186 in_column_const_iterator operator--(int); 187 in_column_const_iterator operator+(unsigned int); 188 in_column_const_iterator operator-(unsigned int); 189 in_column_const_iterator& operator+=(unsigned int); 190 in_column_const_iterator& operator-=(unsigned int); 191 bool operator<(const in_column_const_iterator& other) const; 192 bool operator>(const in_column_const_iterator& other) const; 193 bool operator<=(const in_column_const_iterator& other) const; 194 bool operator>=(const in_column_const_iterator& other) const; 195 ptrdiff_t operator-(const in_column_const_iterator&) const; 196 bool operator==(const in_column_const_iterator&) const; 197 bool operator!=(const in_column_const_iterator&) const; 198 199 friend class filled_tableau<T>; 200 private: 201 const filled_tableau<T>* tab; 202 unsigned int column_number, row_number; 203 }; 204 205 /// An iterator which stays inside a given row of a tableau. 206 class in_row_iterator : public iterator_base { 207 public: 208 in_row_iterator(unsigned int r, unsigned int c, filled_tableau<T>*); 209 T& operator*() const; 210 T* operator->() const; 211 in_row_iterator& operator++(); 212 in_row_iterator operator++(int); 213 in_row_iterator& operator--(); 214 in_row_iterator operator--(int); 215 in_row_iterator operator+(unsigned int); 216 in_row_iterator operator-(unsigned int); 217 in_row_iterator& operator+=(unsigned int); 218 in_row_iterator& operator-=(unsigned int); 219 bool operator<(const in_row_iterator& other) const; 220 bool operator>(const in_row_iterator& other) const; 221 bool operator<=(const in_row_iterator& other) const; 222 bool operator>=(const in_row_iterator& other) const; 223 ptrdiff_t operator-(const in_row_iterator&) const; 224 bool operator==(const in_row_iterator&) const; 225 bool operator!=(const in_row_iterator&) const; 226 227 friend class filled_tableau<T>; 228 friend class filled_tableau<T>::in_row_const_iterator; 229 private: 230 filled_tableau<T>* tab; 231 unsigned int column_number, row_number; 232 }; 233 234 class in_row_const_iterator : public const_iterator_base { 235 public: 236 in_row_const_iterator(unsigned int r, unsigned int c, const filled_tableau<T>*); 237 in_row_const_iterator(const in_row_iterator& other); 238 const T& operator*() const; 239 const T* operator->() const; 240 in_row_const_iterator& operator++(); 241 in_row_const_iterator operator++(int); 242 in_row_const_iterator& operator--(); 243 in_row_const_iterator operator--(int); 244 in_row_const_iterator operator+(unsigned int); 245 in_row_const_iterator operator-(unsigned int); 246 in_row_const_iterator& operator+=(unsigned int); 247 in_row_const_iterator& operator-=(unsigned int); 248 bool operator<(const in_row_const_iterator& other) const; 249 bool operator>(const in_row_const_iterator& other) const; 250 bool operator<=(const in_row_const_iterator& other) const; 251 bool operator>=(const in_row_const_iterator& other) const; 252 ptrdiff_t operator-(const in_row_const_iterator&) const; 253 bool operator==(const in_row_const_iterator&) const; 254 bool operator!=(const in_row_const_iterator&) const; 255 256 friend class filled_tableau<T>; 257 private: 258 const filled_tableau<T>* tab; 259 unsigned int column_number, row_number; 260 }; 261 262 /// An iterator over all boxes of a tableau, left to right, top to bottom. 263 class iterator : public iterator_base { 264 public: 265 iterator(unsigned int r, unsigned int c, filled_tableau<T> *); 266 T& operator*() const; 267 T* operator->() const; 268 iterator& operator++(); 269 iterator operator++(int); 270 iterator& operator--(); 271 iterator operator--(int); 272 iterator operator+(unsigned int); 273 iterator operator-(unsigned int); 274 iterator& operator+=(unsigned int); 275 iterator& operator-=(unsigned int); 276 bool operator<(const iterator& other) const; 277 bool operator>(const iterator& other) const; 278 ptrdiff_t operator-(const iterator&) const; 279 bool operator==(const iterator&) const; 280 bool operator!=(const iterator&) const; 281 282 friend class filled_tableau<T>; 283 friend class filled_tableau<T>::const_iterator; 284 private: 285 filled_tableau<T> *tab; 286 unsigned int column_number, row_number; 287 }; 288 289 class const_iterator : public const_iterator_base { 290 public: 291 const_iterator(unsigned int r, unsigned int c, const filled_tableau<T>*); 292 const_iterator(const iterator& other); 293 const T& operator*() const; 294 const T* operator->() const; 295 const_iterator& operator++(); 296 const_iterator operator++(int); 297 const_iterator& operator--(); 298 const_iterator operator--(int); 299 const_iterator operator+(unsigned int); 300 const_iterator operator-(unsigned int); 301 const_iterator& operator+=(unsigned int); 302 const_iterator& operator-=(unsigned int); 303 bool operator<(const const_iterator& other) const; 304 bool operator>(const const_iterator& other) const; 305 ptrdiff_t operator-(const const_iterator&) const; 306 bool operator==(const const_iterator&) const; 307 bool operator!=(const const_iterator&) const; 308 309 friend class filled_tableau<T>; 310 private: 311 const filled_tableau<T>* tab; 312 unsigned int column_number, row_number; 313 }; 314 315 316 in_column_iterator begin_column(unsigned int column_number); 317 in_column_iterator end_column(unsigned int column_number); 318 in_column_const_iterator begin_column(unsigned int column_number) const; 319 in_column_const_iterator end_column(unsigned int column_number) const; 320 in_column_const_iterator cbegin_column(unsigned int column_number) const; 321 in_column_const_iterator cend_column(unsigned int column_number) const; 322 in_row_iterator begin_row(unsigned int row_number); 323 in_row_iterator end_row(unsigned int row_number); 324 in_row_const_iterator begin_row(unsigned int row_number) const; 325 in_row_const_iterator end_row(unsigned int row_number) const; 326 in_row_const_iterator cbegin_row(unsigned int row_number) const; 327 in_row_const_iterator cend_row(unsigned int row_number) const; 328 iterator begin(); 329 iterator end(); 330 const_iterator begin() const; 331 const_iterator end() const; 332 const_iterator cbegin() const; 333 const_iterator cend() const; 334 335 template<class OutputIterator> 336 OutputIterator Garnir_set(OutputIterator, unsigned int, unsigned int) const; 337 private: 338 typedef std::vector<T> box_row; 339 typedef std::vector<box_row> row_stack; 340 row_stack rows; 341 }; 342 343 template<class T> 344 class tableaux { 345 public: 346 yngint_t total_dimension(unsigned int dim); 347 void remove_nullifying_traces(); 348 /// Put the set of tableaux into standard form by using Garnir symmetries. 349 /// Return value indicates whether the tableaux were already all in standard form. 350 bool standard_form(); 351 void add_tableau(const T&); 352 void symmetrise(const T& tabsym); 353 354 typedef std::list<T> tableau_container_t; 355 tableau_container_t storage; 356 357 typedef std::back_insert_iterator<tableau_container_t> back_insert_iterator; 358 359 back_insert_iterator get_back_insert_iterator(); 360 }; 361 362 bool legal_box(const std::vector<std::pair<int,int> >& prev, 363 const std::vector<std::pair<int,int> >& ths, 364 int colpos, int trypos); 365 366 // -------------------------------------- 367 368 369 template<class T> get_back_insert_iterator()370 typename tableaux<T>::back_insert_iterator tableaux<T>::get_back_insert_iterator() 371 { 372 return back_insert_iterator(storage); 373 } 374 375 template<class T> remove_nullifying_traces()376 void tableaux<T>::remove_nullifying_traces() 377 { 378 typename tableau_container_t::iterator it=storage.begin(); 379 while(it!=storage.end()) { 380 if(it->has_nullifying_trace()) 381 it=storage.erase(it); 382 else ++it; 383 } 384 } 385 386 template<class T> symmetrise(const T &)387 void tableaux<T>::symmetrise(const T&) 388 { 389 // 390 // typename tableau_container_t::iterator thetab=storage.begin(); 391 // while(thetab!=storage.end()) { 392 // (*thetab).sort_columns(); 393 // std::pair<int,int> where=(*thetab).nonstandard_loc(); 394 // if(where.first!=-1) { 395 // combinations<typename T::value_type> com; 396 // 397 398 /* 399 FIXME: we should have two LR_tensor routines, because if you do 'alltabs', you should 400 keep track of which boxes came from tableau 2. So do a LR_tensor with numbered boxes, 401 and then after the LR_tensor apply the symmetries of the original tableaux, put back 402 the original index names, sort columns and determine whether the tableau is identically 403 non-zero. Then add to the product. 404 405 Another issue: adding to tableaux should have an option to not insert doubles. 406 407 There was something third, forgotten... 408 */ 409 } 410 411 template<class T> copy_shape(const tableau & other)412 void filled_tableau<T>::copy_shape(const tableau& other) 413 { 414 rows.clear(); 415 for(unsigned int r=0; r<other.number_of_rows(); ++r) { 416 rows.push_back(box_row(other.row_size(r))); 417 } 418 tableau::operator=(other); 419 } 420 421 template<class T> compare_without_multiplicity(const filled_tableau<T> & other) const422 bool filled_tableau<T>::compare_without_multiplicity(const filled_tableau<T>& other) const 423 { 424 return (rows==other.rows); 425 } 426 427 template<class T> has_nullifying_trace() const428 bool filled_tableau<T>::has_nullifying_trace() const 429 { 430 return false; 431 432 // Old, probably incorrect code: 433 // 434 // for(unsigned int r1=0; r1<number_of_rows(); ++r1) { 435 // for(unsigned c1=0; c1<row_size(r1); ++c1) { 436 // for(unsigned int c2=c1+1; c2<row_size(r1); ++c2) { 437 // // (r1,c1) and (r1,c2) 438 // for(unsigned int c3=0; c3<row_size(0); ++c3) { 439 // unsigned int r3=0; 440 // while(r3<number_of_rows()-1 && c3<row_size(r3)) { 441 // unsigned int r4=r3+1; 442 // while(r4<number_of_rows() && c3<row_size(r4)) { 443 // if((rows[r1][c1]==rows[r3][c3] && rows[r1][c2]==rows[r4][c3]) || 444 // (rows[r1][c1]==rows[r4][c3] && rows[r1][c2]==rows[r3][c3]) ) 445 // return true; 446 // ++r4; 447 // } 448 // ++r3; 449 // } 450 // } 451 // } 452 // } 453 // } 454 // return false; 455 } 456 457 template<class T> find(const T & obj) const458 std::pair<int, int> filled_tableau<T>::find(const T& obj) const 459 { 460 for(unsigned int ir=0; ir<rows.size(); ++ir) { 461 for(unsigned int ic=0; ic<rows[ir].size(); ++ic) { 462 if(rows[ir][ic]==obj) 463 return std::pair<int,int>(ir, ic); 464 } 465 } 466 return std::pair<int,int>(-1,-1); 467 } 468 469 template<class T> sort_within_columns()470 void filled_tableau<T>::sort_within_columns() 471 { 472 std::less<T> comp; 473 sort_within_columns(comp); 474 } 475 476 template<class T> sort_columns()477 void filled_tableau<T>::sort_columns() 478 { 479 std::less<T> comp; 480 sort_columns(comp); 481 } 482 483 template<class T> canonicalise()484 void filled_tableau<T>::canonicalise() 485 { 486 std::less<T> comp; 487 canonicalise(comp); 488 } 489 490 template<class T> 491 template<class StrictWeakOrdering> sort_within_columns(StrictWeakOrdering comp)492 void filled_tableau<T>::sort_within_columns(StrictWeakOrdering comp) 493 { 494 filled_tableau<T> tmp(*this); 495 if(number_of_rows()==0) return; 496 for(unsigned int c=0; c<row_size(0); ++c) { 497 std::sort(begin_column(c), end_column(c), comp); 498 multiplicity*=combin::ordersign(begin_column(c), end_column(c), tmp.begin_column(c), tmp.end_column(c)); 499 } 500 } 501 502 template<class T> 503 template<class StrictWeakOrdering> sort_columns(StrictWeakOrdering comp)504 void filled_tableau<T>::sort_columns(StrictWeakOrdering comp) 505 { 506 for(unsigned int c1=0; c1<row_size(0); ++c1) { 507 for(unsigned int c2=c1; c2<row_size(0); ++c2) { 508 if(column_size(c1)==column_size(c2)) { 509 if(comp((*this)(0,c2), (*this)(0,c1))) 510 swap_columns(c1,c2); 511 } 512 } 513 } 514 } 515 516 template<class T> 517 template<class StrictWeakOrdering> canonicalise(StrictWeakOrdering comp,bool only_col_ex)518 void filled_tableau<T>::canonicalise(StrictWeakOrdering comp, bool only_col_ex) 519 { 520 if(!only_col_ex) 521 sort_within_columns(comp); 522 sort_columns(comp); 523 } 524 525 //--------------------------------------------------------------------------- 526 // in_column_iterator 527 528 template<class T> in_column_iterator(unsigned int r,unsigned int c,filled_tableau<T> * t)529 filled_tableau<T>::in_column_iterator::in_column_iterator(unsigned int r, unsigned int c, filled_tableau<T> *t) 530 : tab(t), column_number(c), row_number(r) 531 { 532 } 533 534 template<class T> operator +(unsigned int n)535 typename filled_tableau<T>::in_column_iterator filled_tableau<T>::in_column_iterator::operator+(unsigned int n) 536 { 537 typename filled_tableau<T>::in_column_iterator it2(*this); 538 it2+=n; 539 return it2; 540 } 541 542 template<class T> operator -(unsigned int n)543 typename filled_tableau<T>::in_column_iterator filled_tableau<T>::in_column_iterator::operator-(unsigned int n) 544 { 545 typename filled_tableau<T>::in_column_iterator it2(*this); 546 it2-=n; 547 return it2; 548 } 549 550 template<class T> operator -(const in_column_iterator & other) const551 ptrdiff_t filled_tableau<T>::in_column_iterator::operator-(const in_column_iterator& other) const 552 { 553 return row_number-other.row_number; 554 } 555 556 template<class T> operator [](int n) const557 T& filled_tableau<T>::in_column_iterator::operator[](int n) const 558 { 559 return (*tab)(row_number + n, column_number); 560 } 561 562 template<class T> operator *() const563 T& filled_tableau<T>::in_column_iterator::operator*() const 564 { 565 return (*tab)(row_number,column_number); 566 } 567 568 template<class T> operator ->() const569 T* filled_tableau<T>::in_column_iterator::operator->() const 570 { 571 return &((*tab)(row_number,column_number)); 572 } 573 574 template<class T> operator ++()575 typename filled_tableau<T>::in_column_iterator& filled_tableau<T>::in_column_iterator::operator++() 576 { 577 ++row_number; 578 return (*this); 579 } 580 581 template<class T> operator +=(unsigned int n)582 typename filled_tableau<T>::in_column_iterator& filled_tableau<T>::in_column_iterator::operator+=(unsigned int n) 583 { 584 row_number+=n; 585 return (*this); 586 } 587 588 template<class T> operator --()589 typename filled_tableau<T>::in_column_iterator& filled_tableau<T>::in_column_iterator::operator--() 590 { 591 --row_number; 592 return (*this); 593 } 594 595 template<class T> operator --(int)596 typename filled_tableau<T>::in_column_iterator filled_tableau<T>::in_column_iterator::operator--(int) 597 { 598 in_column_iterator tmp(*this); 599 --row_number; 600 return tmp; 601 } 602 603 template<class T> operator ++(int)604 typename filled_tableau<T>::in_column_iterator filled_tableau<T>::in_column_iterator::operator++(int) 605 { 606 in_column_iterator tmp(*this); 607 ++row_number; 608 return tmp; 609 } 610 611 template<class T> operator -=(unsigned int n)612 typename filled_tableau<T>::in_column_iterator& filled_tableau<T>::in_column_iterator::operator-=(unsigned int n) 613 { 614 row_number-=n; 615 return (*this); 616 } 617 618 template<class T> operator ==(const in_column_iterator & other) const619 bool filled_tableau<T>::in_column_iterator::operator==(const in_column_iterator& other) const 620 { 621 if(tab==other.tab && row_number==other.row_number && column_number==other.column_number) 622 return true; 623 return false; 624 } 625 626 template<class T> operator <=(const in_column_iterator & other) const627 bool filled_tableau<T>::in_column_iterator::operator<=(const in_column_iterator& other) const 628 { 629 if(row_number<=other.row_number) return true; 630 return false; 631 } 632 633 template<class T> operator >=(const in_column_iterator & other) const634 bool filled_tableau<T>::in_column_iterator::operator>=(const in_column_iterator& other) const 635 { 636 if(row_number>=other.row_number) return true; 637 return false; 638 } 639 640 template<class T> operator <(const in_column_iterator & other) const641 bool filled_tableau<T>::in_column_iterator::operator<(const in_column_iterator& other) const 642 { 643 if(row_number<other.row_number) return true; 644 return false; 645 } 646 647 template<class T> operator >(const in_column_iterator & other) const648 bool filled_tableau<T>::in_column_iterator::operator>(const in_column_iterator& other) const 649 { 650 if(row_number>other.row_number) return true; 651 return false; 652 } 653 654 template<class T> operator !=(const in_column_iterator & other) const655 bool filled_tableau<T>::in_column_iterator::operator!=(const in_column_iterator& other) const 656 { 657 return !((*this)==other); 658 } 659 660 //--------------------------------------------------------------------------- 661 // in_column_const_iterator 662 663 template<class T> in_column_const_iterator(unsigned int r,unsigned int c,const filled_tableau<T> * t)664 filled_tableau<T>::in_column_const_iterator::in_column_const_iterator(unsigned int r, unsigned int c, const filled_tableau<T>* t) 665 : tab(t), column_number(c), row_number(r) 666 { 667 } 668 669 template<class T> in_column_const_iterator(const filled_tableau<T>::in_column_iterator & other)670 filled_tableau<T>::in_column_const_iterator::in_column_const_iterator(const filled_tableau<T>::in_column_iterator& other) 671 : tab(other.tab), column_number(other.column_number), row_number(other.row_number) 672 { 673 } 674 675 template<class T> operator +(unsigned int n)676 typename filled_tableau<T>::in_column_const_iterator filled_tableau<T>::in_column_const_iterator::operator+(unsigned int n) 677 { 678 typename filled_tableau<T>::in_column_const_iterator it2(*this); 679 it2 += n; 680 return it2; 681 } 682 683 template<class T> operator -(unsigned int n)684 typename filled_tableau<T>::in_column_const_iterator filled_tableau<T>::in_column_const_iterator::operator-(unsigned int n) 685 { 686 typename filled_tableau<T>::in_column_const_iterator it2(*this); 687 it2 -= n; 688 return it2; 689 } 690 691 template<class T> operator -(const in_column_const_iterator & other) const692 ptrdiff_t filled_tableau<T>::in_column_const_iterator::operator-(const in_column_const_iterator& other) const 693 { 694 return row_number - other.row_number; 695 } 696 697 template<class T> operator *() const698 const T& filled_tableau<T>::in_column_const_iterator::operator*() const 699 { 700 return (*tab)(row_number, column_number); 701 } 702 703 template<class T> operator ->() const704 const T* filled_tableau<T>::in_column_const_iterator::operator->() const 705 { 706 return &((*tab)(row_number, column_number)); 707 } 708 709 template<class T> operator ++()710 typename filled_tableau<T>::in_column_const_iterator& filled_tableau<T>::in_column_const_iterator::operator++() 711 { 712 ++row_number; 713 return (*this); 714 } 715 716 template<class T> operator +=(unsigned int n)717 typename filled_tableau<T>::in_column_const_iterator& filled_tableau<T>::in_column_const_iterator::operator+=(unsigned int n) 718 { 719 row_number += n; 720 return (*this); 721 } 722 723 template<class T> operator --()724 typename filled_tableau<T>::in_column_const_iterator& filled_tableau<T>::in_column_const_iterator::operator--() 725 { 726 --row_number; 727 return (*this); 728 } 729 730 template<class T> operator --(int)731 typename filled_tableau<T>::in_column_const_iterator filled_tableau<T>::in_column_const_iterator::operator--(int) 732 { 733 in_column_const_iterator tmp(*this); 734 --row_number; 735 return tmp; 736 } 737 738 template<class T> operator ++(int)739 typename filled_tableau<T>::in_column_const_iterator filled_tableau<T>::in_column_const_iterator::operator++(int) 740 { 741 in_column_const_iterator tmp(*this); 742 ++row_number; 743 return tmp; 744 } 745 746 template<class T> operator -=(unsigned int n)747 typename filled_tableau<T>::in_column_const_iterator& filled_tableau<T>::in_column_const_iterator::operator-=(unsigned int n) 748 { 749 row_number -= n; 750 return (*this); 751 } 752 753 template<class T> operator ==(const in_column_const_iterator & other) const754 bool filled_tableau<T>::in_column_const_iterator::operator==(const in_column_const_iterator& other) const 755 { 756 if (tab == other.tab && row_number == other.row_number && column_number == other.column_number) 757 return true; 758 return false; 759 } 760 761 template<class T> operator <=(const in_column_const_iterator & other) const762 bool filled_tableau<T>::in_column_const_iterator::operator<=(const in_column_const_iterator & other) const 763 { 764 if (row_number <= other.row_number) return true; 765 return false; 766 } 767 768 template<class T> operator >=(const in_column_const_iterator & other) const769 bool filled_tableau<T>::in_column_const_iterator::operator>=(const in_column_const_iterator & other) const 770 { 771 if (row_number >= other.row_number) return true; 772 return false; 773 } 774 775 template<class T> operator <(const in_column_const_iterator & other) const776 bool filled_tableau<T>::in_column_const_iterator::operator<(const in_column_const_iterator & other) const 777 { 778 if (row_number < other.row_number) return true; 779 return false; 780 } 781 782 template<class T> operator >(const in_column_const_iterator & other) const783 bool filled_tableau<T>::in_column_const_iterator::operator>(const in_column_const_iterator & other) const 784 { 785 if (row_number > other.row_number) return true; 786 return false; 787 } 788 789 template<class T> operator !=(const in_column_const_iterator & other) const790 bool filled_tableau<T>::in_column_const_iterator::operator!=(const in_column_const_iterator & other) const 791 { 792 return !((*this) == other); 793 } 794 795 796 //--------------------------------------------------------------------------- 797 // in_row_iterator 798 799 template<class T> in_row_iterator(unsigned int r,unsigned int c,filled_tableau<T> * t)800 filled_tableau<T>::in_row_iterator::in_row_iterator(unsigned int r, unsigned int c, filled_tableau<T>* t) 801 : tab(t), column_number(c), row_number(r) 802 { 803 } 804 805 template<class T> operator +(unsigned int n)806 typename filled_tableau<T>::in_row_iterator filled_tableau<T>::in_row_iterator::operator+(unsigned int n) 807 { 808 typename filled_tableau<T>::in_row_iterator it2(*this); 809 it2 += n; 810 return it2; 811 } 812 813 template<class T> operator -(unsigned int n)814 typename filled_tableau<T>::in_row_iterator filled_tableau<T>::in_row_iterator::operator-(unsigned int n) 815 { 816 typename filled_tableau<T>::in_row_iterator it2(*this); 817 it2 -= n; 818 return it2; 819 } 820 821 template<class T> operator -(const in_row_iterator & other) const822 ptrdiff_t filled_tableau<T>::in_row_iterator::operator-(const in_row_iterator& other) const 823 { 824 return column_number - other.column_number; 825 } 826 827 template<class T> operator *() const828 T& filled_tableau<T>::in_row_iterator::operator*() const 829 { 830 return (*tab)(row_number, column_number); 831 } 832 833 template<class T> operator ->() const834 T* filled_tableau<T>::in_row_iterator::operator->() const 835 { 836 return &((*tab)(row_number, column_number)); 837 } 838 839 template<class T> operator ++()840 typename filled_tableau<T>::in_row_iterator& filled_tableau<T>::in_row_iterator::operator++() 841 { 842 ++column_number; 843 return (*this); 844 } 845 846 template<class T> operator +=(unsigned int n)847 typename filled_tableau<T>::in_row_iterator& filled_tableau<T>::in_row_iterator::operator+=(unsigned int n) 848 { 849 column_number += n; 850 return (*this); 851 } 852 853 template<class T> operator --()854 typename filled_tableau<T>::in_row_iterator& filled_tableau<T>::in_row_iterator::operator--() 855 { 856 --column_number; 857 return (*this); 858 } 859 860 template<class T> operator --(int)861 typename filled_tableau<T>::in_row_iterator filled_tableau<T>::in_row_iterator::operator--(int) 862 { 863 in_row_iterator tmp(*this); 864 --column_number; 865 return tmp; 866 } 867 868 template<class T> operator ++(int)869 typename filled_tableau<T>::in_row_iterator filled_tableau<T>::in_row_iterator::operator++(int) 870 { 871 in_row_iterator tmp(*this); 872 ++column_number; 873 return tmp; 874 } 875 876 template<class T> operator -=(unsigned int n)877 typename filled_tableau<T>::in_row_iterator& filled_tableau<T>::in_row_iterator::operator-=(unsigned int n) 878 { 879 column_number -= n; 880 return (*this); 881 } 882 883 template<class T> operator ==(const in_row_iterator & other) const884 bool filled_tableau<T>::in_row_iterator::operator==(const in_row_iterator& other) const 885 { 886 if (tab == other.tab && row_number == other.row_number && column_number == other.column_number) 887 return true; 888 return false; 889 } 890 891 template<class T> operator <=(const in_row_iterator & other) const892 bool filled_tableau<T>::in_row_iterator::operator<=(const in_row_iterator & other) const 893 { 894 if (column_number <= other.column_number) return true; 895 return false; 896 } 897 898 template<class T> operator >=(const in_row_iterator & other) const899 bool filled_tableau<T>::in_row_iterator::operator>=(const in_row_iterator & other) const 900 { 901 if (column_number >= other.column_number) return true; 902 return false; 903 } 904 905 template<class T> operator <(const in_row_iterator & other) const906 bool filled_tableau<T>::in_row_iterator::operator<(const in_row_iterator & other) const 907 { 908 if (column_number < other.column_number) return true; 909 return false; 910 } 911 912 template<class T> operator >(const in_row_iterator & other) const913 bool filled_tableau<T>::in_row_iterator::operator>(const in_row_iterator & other) const 914 { 915 if (column_number > other.column_number) return true; 916 return false; 917 } 918 919 template<class T> operator !=(const in_row_iterator & other) const920 bool filled_tableau<T>::in_row_iterator::operator!=(const in_row_iterator & other) const 921 { 922 return !((*this) == other); 923 } 924 925 //--------------------------------------------------------------------------- 926 // in_row_const_iterator 927 928 template<class T> in_row_const_iterator(unsigned int r,unsigned int c,const filled_tableau<T> * t)929 filled_tableau<T>::in_row_const_iterator::in_row_const_iterator(unsigned int r, unsigned int c, const filled_tableau<T>* t) 930 : tab(t), column_number(c), row_number(r) 931 { 932 } 933 934 template<class T> in_row_const_iterator(const filled_tableau<T>::in_row_iterator & other)935 filled_tableau<T>::in_row_const_iterator::in_row_const_iterator(const filled_tableau<T>::in_row_iterator& other) 936 : tab(other.tab), column_number(other.column_number), row_number(other.row_number) 937 { 938 } 939 940 941 template<class T> operator +(unsigned int n)942 typename filled_tableau<T>::in_row_const_iterator filled_tableau<T>::in_row_const_iterator::operator+(unsigned int n) 943 { 944 typename filled_tableau<T>::in_row_const_iterator it2(*this); 945 it2 += n; 946 return it2; 947 } 948 949 template<class T> operator -(unsigned int n)950 typename filled_tableau<T>::in_row_const_iterator filled_tableau<T>::in_row_const_iterator::operator-(unsigned int n) 951 { 952 typename filled_tableau<T>::in_row_const_iterator it2(*this); 953 it2 -= n; 954 return it2; 955 } 956 957 template<class T> operator -(const in_row_const_iterator & other) const958 ptrdiff_t filled_tableau<T>::in_row_const_iterator::operator-(const in_row_const_iterator& other) const 959 { 960 return column_number - other.column_number; 961 } 962 963 template<class T> operator *() const964 const T& filled_tableau<T>::in_row_const_iterator::operator*() const 965 { 966 return (*tab)(row_number, column_number); 967 } 968 969 template<class T> operator ->() const970 const T* filled_tableau<T>::in_row_const_iterator::operator->() const 971 { 972 return &((*tab)(row_number, column_number)); 973 } 974 975 template<class T> operator ++()976 typename filled_tableau<T>::in_row_const_iterator& filled_tableau<T>::in_row_const_iterator::operator++() 977 { 978 ++column_number; 979 return (*this); 980 } 981 982 template<class T> operator +=(unsigned int n)983 typename filled_tableau<T>::in_row_const_iterator& filled_tableau<T>::in_row_const_iterator::operator+=(unsigned int n) 984 { 985 column_number += n; 986 return (*this); 987 } 988 989 template<class T> operator --()990 typename filled_tableau<T>::in_row_const_iterator& filled_tableau<T>::in_row_const_iterator::operator--() 991 { 992 --column_number; 993 return (*this); 994 } 995 996 template<class T> operator --(int)997 typename filled_tableau<T>::in_row_const_iterator filled_tableau<T>::in_row_const_iterator::operator--(int) 998 { 999 in_row_const_iterator tmp(*this); 1000 --column_number; 1001 return tmp; 1002 } 1003 1004 template<class T> operator ++(int)1005 typename filled_tableau<T>::in_row_const_iterator filled_tableau<T>::in_row_const_iterator::operator++(int) 1006 { 1007 in_row_const_iterator tmp(*this); 1008 ++column_number; 1009 return tmp; 1010 } 1011 1012 template<class T> operator -=(unsigned int n)1013 typename filled_tableau<T>::in_row_const_iterator& filled_tableau<T>::in_row_const_iterator::operator-=(unsigned int n) 1014 { 1015 column_number -= n; 1016 return (*this); 1017 } 1018 1019 template<class T> operator ==(const in_row_const_iterator & other) const1020 bool filled_tableau<T>::in_row_const_iterator::operator==(const in_row_const_iterator& other) const 1021 { 1022 if (tab == other.tab && row_number == other.row_number && column_number == other.column_number) 1023 return true; 1024 return false; 1025 } 1026 1027 template<class T> operator <=(const in_row_const_iterator & other) const1028 bool filled_tableau<T>::in_row_const_iterator::operator<=(const in_row_const_iterator & other) const 1029 { 1030 if (column_number <= other.column_number) return true; 1031 return false; 1032 } 1033 1034 template<class T> operator >=(const in_row_const_iterator & other) const1035 bool filled_tableau<T>::in_row_const_iterator::operator>=(const in_row_const_iterator & other) const 1036 { 1037 if (column_number >= other.column_number) return true; 1038 return false; 1039 } 1040 1041 template<class T> operator <(const in_row_const_iterator & other) const1042 bool filled_tableau<T>::in_row_const_iterator::operator<(const in_row_const_iterator & other) const 1043 { 1044 if (column_number < other.column_number) return true; 1045 return false; 1046 } 1047 1048 template<class T> operator >(const in_row_const_iterator & other) const1049 bool filled_tableau<T>::in_row_const_iterator::operator>(const in_row_const_iterator & other) const 1050 { 1051 if (column_number > other.column_number) return true; 1052 return false; 1053 } 1054 1055 template<class T> operator !=(const in_row_const_iterator & other) const1056 bool filled_tableau<T>::in_row_const_iterator::operator!=(const in_row_const_iterator & other) const 1057 { 1058 return !((*this) == other); 1059 } 1060 1061 1062 1063 //--------------------------------------------------------------------------- 1064 // iterator 1065 1066 template<class T> iterator(unsigned int r,unsigned int c,filled_tableau<T> * t)1067 filled_tableau<T>::iterator::iterator(unsigned int r, unsigned int c, filled_tableau<T> *t) 1068 : tab(t), column_number(c), row_number(r) 1069 { 1070 } 1071 1072 template<class T> operator +(unsigned int n)1073 typename filled_tableau<T>::iterator filled_tableau<T>::iterator::operator+(unsigned int n) 1074 { 1075 typename filled_tableau<T>::iterator it2(*this); 1076 it2+=n; 1077 return it2; 1078 } 1079 1080 template<class T> operator -(unsigned int n)1081 typename filled_tableau<T>::iterator filled_tableau<T>::iterator::operator-(unsigned int n) 1082 { 1083 typename filled_tableau<T>::iterator it2(*this); 1084 it2-=n; 1085 return it2; 1086 } 1087 1088 template<class T> operator -(const iterator & other) const1089 ptrdiff_t filled_tableau<T>::iterator::operator-(const iterator& other) const 1090 { 1091 return row_number-other.row_number; 1092 } 1093 1094 template<class T> operator *() const1095 T& filled_tableau<T>::iterator::operator*() const 1096 { 1097 return (*tab)(row_number,column_number); 1098 } 1099 1100 template<class T> operator ->() const1101 T* filled_tableau<T>::iterator::operator->() const 1102 { 1103 return &((*tab)(row_number,column_number)); 1104 } 1105 1106 template<class T> operator ++()1107 typename filled_tableau<T>::iterator& filled_tableau<T>::iterator::operator++() 1108 { 1109 if(++column_number==tab->rows[row_number].size()) { 1110 column_number=0; 1111 ++row_number; 1112 } 1113 return (*this); 1114 } 1115 1116 template<class T> operator +=(unsigned int n)1117 typename filled_tableau<T>::iterator& filled_tableau<T>::iterator::operator+=(unsigned int n) 1118 { 1119 while(n>0) { 1120 if(++column_number==tab->rows[row_number]) { 1121 column_number=0; 1122 ++row_number; 1123 } 1124 --n; 1125 } 1126 return (*this); 1127 } 1128 1129 template<class T> operator --()1130 typename filled_tableau<T>::iterator& filled_tableau<T>::iterator::operator--() 1131 { 1132 if(column_number==0) { 1133 --row_number; 1134 column_number=tab->rows[row_number].size()-1; 1135 } 1136 else --column_number; 1137 return (*this); 1138 } 1139 1140 template<class T> operator --(int)1141 typename filled_tableau<T>::iterator filled_tableau<T>::iterator::operator--(int) 1142 { 1143 iterator tmp(*this); 1144 if(column_number==0) { 1145 --row_number; 1146 column_number=tab->rows[row_number].size()-1; 1147 } 1148 else --column_number; 1149 return tmp; 1150 } 1151 1152 template<class T> operator ++(int)1153 typename filled_tableau<T>::iterator filled_tableau<T>::iterator::operator++(int) 1154 { 1155 iterator tmp(*this); 1156 while(this->n>0) { 1157 if(++column_number==tab->rows[row_number]) { 1158 column_number=0; 1159 ++row_number; 1160 } 1161 --this->n; 1162 } 1163 return tmp; 1164 } 1165 1166 template<class T> operator -=(unsigned int n)1167 typename filled_tableau<T>::iterator& filled_tableau<T>::iterator::operator-=(unsigned int n) 1168 { 1169 while(n>0) { 1170 if(column_number==0) { 1171 --row_number; 1172 column_number=tab->rows[row_number].size()-1; 1173 } 1174 else --column_number; 1175 --n; 1176 } 1177 return (*this); 1178 } 1179 1180 template<class T> operator ==(const iterator & other) const1181 bool filled_tableau<T>::iterator::operator==(const iterator& other) const 1182 { 1183 if(tab==other.tab && row_number==other.row_number && column_number==other.column_number) 1184 return true; 1185 return false; 1186 } 1187 1188 template<class T> operator <(const iterator & other) const1189 bool filled_tableau<T>::iterator::operator<(const iterator& other) const 1190 { 1191 if(row_number<other.row_number) return true; 1192 return false; 1193 } 1194 1195 template<class T> operator >(const iterator & other) const1196 bool filled_tableau<T>::iterator::operator>(const iterator& other) const 1197 { 1198 if(row_number>other.row_number) return true; 1199 return false; 1200 } 1201 1202 template<class T> operator !=(const iterator & other) const1203 bool filled_tableau<T>::iterator::operator!=(const iterator& other) const 1204 { 1205 return !((*this)==other); 1206 } 1207 1208 1209 1210 //--------------------------------------------------------------------------- 1211 // const_iterator 1212 1213 template<class T> const_iterator(unsigned int r,unsigned int c,const filled_tableau<T> * t)1214 filled_tableau<T>::const_iterator::const_iterator(unsigned int r, unsigned int c, const filled_tableau<T>* t) 1215 : tab(t), column_number(c), row_number(r) 1216 { 1217 } 1218 1219 template<class T> const_iterator(const filled_tableau<T>::iterator & other)1220 filled_tableau<T>::const_iterator::const_iterator(const filled_tableau<T>::iterator& other) 1221 : tab(other.tab), column_number(other.column_number), row_number(other.row_number) 1222 { 1223 } 1224 1225 template<class T> operator +(unsigned int n)1226 typename filled_tableau<T>::const_iterator filled_tableau<T>::const_iterator::operator+(unsigned int n) 1227 { 1228 typename filled_tableau<T>::const_iterator it2(*this); 1229 it2 += n; 1230 return it2; 1231 } 1232 1233 template<class T> operator -(unsigned int n)1234 typename filled_tableau<T>::const_iterator filled_tableau<T>::const_iterator::operator-(unsigned int n) 1235 { 1236 typename filled_tableau<T>::const_iterator it2(*this); 1237 it2 -= n; 1238 return it2; 1239 } 1240 1241 template<class T> operator -(const const_iterator & other) const1242 ptrdiff_t filled_tableau<T>::const_iterator::operator-(const const_iterator& other) const 1243 { 1244 return row_number - other.row_number; 1245 } 1246 1247 template<class T> operator *() const1248 const T& filled_tableau<T>::const_iterator::operator*() const 1249 { 1250 return (*tab)(row_number, column_number); 1251 } 1252 1253 template<class T> operator ->() const1254 const T* filled_tableau<T>::const_iterator::operator->() const 1255 { 1256 return &((*tab)(row_number, column_number)); 1257 } 1258 1259 template<class T> operator ++()1260 typename filled_tableau<T>::const_iterator& filled_tableau<T>::const_iterator::operator++() 1261 { 1262 if (++column_number == tab->rows[row_number].size()) { 1263 column_number = 0; 1264 ++row_number; 1265 } 1266 return (*this); 1267 } 1268 1269 template<class T> operator +=(unsigned int n)1270 typename filled_tableau<T>::const_iterator& filled_tableau<T>::const_iterator::operator+=(unsigned int n) 1271 { 1272 while (n > 0) { 1273 if (++column_number == tab->rows[row_number]) { 1274 column_number = 0; 1275 ++row_number; 1276 } 1277 --n; 1278 } 1279 return (*this); 1280 } 1281 1282 template<class T> operator --()1283 typename filled_tableau<T>::const_iterator& filled_tableau<T>::const_iterator::operator--() 1284 { 1285 if (column_number == 0) { 1286 --row_number; 1287 column_number = tab->rows[row_number].size() - 1; 1288 } 1289 else --column_number; 1290 return (*this); 1291 } 1292 1293 template<class T> operator --(int)1294 typename filled_tableau<T>::const_iterator filled_tableau<T>::const_iterator::operator--(int) 1295 { 1296 const_iterator tmp(*this); 1297 if (column_number == 0) { 1298 --row_number; 1299 column_number = tab->rows[row_number].size() - 1; 1300 } 1301 else --column_number; 1302 return tmp; 1303 } 1304 1305 template<class T> operator ++(int)1306 typename filled_tableau<T>::const_iterator filled_tableau<T>::const_iterator::operator++(int) 1307 { 1308 const_iterator tmp(*this); 1309 while (this->n > 0) { 1310 if (++column_number == tab->rows[row_number]) { 1311 column_number = 0; 1312 ++row_number; 1313 } 1314 --this->n; 1315 } 1316 return tmp; 1317 } 1318 1319 template<class T> operator -=(unsigned int n)1320 typename filled_tableau<T>::const_iterator& filled_tableau<T>::const_iterator::operator-=(unsigned int n) 1321 { 1322 while (n > 0) { 1323 if (column_number == 0) { 1324 --row_number; 1325 column_number = tab->rows[row_number].size() - 1; 1326 } 1327 else --column_number; 1328 --n; 1329 } 1330 return (*this); 1331 } 1332 1333 template<class T> operator ==(const const_iterator & other) const1334 bool filled_tableau<T>::const_iterator::operator==(const const_iterator& other) const 1335 { 1336 if (tab == other.tab && row_number == other.row_number && column_number == other.column_number) 1337 return true; 1338 return false; 1339 } 1340 1341 template<class T> operator <(const const_iterator & other) const1342 bool filled_tableau<T>::const_iterator::operator<(const const_iterator & other) const 1343 { 1344 if (row_number < other.row_number) return true; 1345 return false; 1346 } 1347 1348 template<class T> operator >(const const_iterator & other) const1349 bool filled_tableau<T>::const_iterator::operator>(const const_iterator & other) const 1350 { 1351 if (row_number > other.row_number) return true; 1352 return false; 1353 } 1354 1355 template<class T> operator !=(const const_iterator & other) const1356 bool filled_tableau<T>::const_iterator::operator!=(const const_iterator & other) const 1357 { 1358 return !((*this) == other); 1359 } 1360 1361 1362 //--- 1363 // other 1364 1365 template<class T> begin()1366 typename filled_tableau<T>::iterator filled_tableau<T>::begin() 1367 { 1368 return iterator(0, 0, this); 1369 } 1370 1371 template<class T> end()1372 typename filled_tableau<T>::iterator filled_tableau<T>::end() 1373 { 1374 return iterator(rows.size(), 0, this); 1375 } 1376 1377 1378 template<class T> cbegin() const1379 typename filled_tableau<T>::const_iterator filled_tableau<T>::cbegin() const 1380 { 1381 return const_iterator(0,0,this); 1382 } 1383 1384 template<class T> cend() const1385 typename filled_tableau<T>::const_iterator filled_tableau<T>::cend() const 1386 { 1387 return const_iterator(rows.size(), 0, this); 1388 } 1389 1390 template<class T> begin() const1391 typename filled_tableau<T>::const_iterator filled_tableau<T>::begin() const 1392 { 1393 return cbegin(); 1394 } 1395 1396 template<class T> end() const1397 typename filled_tableau<T>::const_iterator filled_tableau<T>::end() const 1398 { 1399 return cend(); 1400 } 1401 1402 template<class T> begin_column(unsigned int column)1403 typename filled_tableau<T>::in_column_iterator filled_tableau<T>::begin_column(unsigned int column) 1404 { 1405 typename filled_tableau<T>::in_column_iterator it(0,column,this); 1406 assert(number_of_rows()>0); 1407 assert(column<row_size(0)); 1408 return it; 1409 } 1410 1411 template<class T> end_column(unsigned int column)1412 typename filled_tableau<T>::in_column_iterator filled_tableau<T>::end_column(unsigned int column) 1413 { 1414 unsigned int r=0; 1415 while(r<number_of_rows()) { 1416 if(row_size(r)<=column) 1417 break; 1418 ++r; 1419 } 1420 typename filled_tableau<T>::in_column_iterator it(r,column,this); 1421 return it; 1422 } 1423 1424 template<class T> cbegin_column(unsigned int column) const1425 typename filled_tableau<T>::in_column_const_iterator filled_tableau<T>::cbegin_column(unsigned int column) const 1426 { 1427 typename filled_tableau<T>::in_column_const_iterator it(0, column, this); 1428 assert(number_of_rows() > 0); 1429 assert(column < row_size(0)); 1430 return it; 1431 } 1432 1433 template<class T> cend_column(unsigned int column) const1434 typename filled_tableau<T>::in_column_const_iterator filled_tableau<T>::cend_column(unsigned int column) const 1435 { 1436 unsigned int r = 0; 1437 while (r < number_of_rows()) { 1438 if (row_size(r) <= column) 1439 break; 1440 ++r; 1441 } 1442 typename filled_tableau<T>::in_column_const_iterator it(r, column, this); 1443 return it; 1444 } 1445 1446 template<class T> begin_column(unsigned int column) const1447 typename filled_tableau<T>::in_column_const_iterator filled_tableau<T>::begin_column(unsigned int column) const 1448 { 1449 return cbegin_column(column); 1450 } 1451 1452 template<class T> end_column(unsigned int column) const1453 typename filled_tableau<T>::in_column_const_iterator filled_tableau<T>::end_column(unsigned int column) const 1454 { 1455 return cend_column(column); 1456 } 1457 1458 template<class T> begin_row(unsigned int row)1459 typename filled_tableau<T>::in_row_iterator filled_tableau<T>::begin_row(unsigned int row) 1460 { 1461 return in_row_iterator{ row, 0, this }; 1462 } 1463 1464 template<class T> end_row(unsigned int row)1465 typename filled_tableau<T>::in_row_iterator filled_tableau<T>::end_row(unsigned int row) 1466 { 1467 return in_row_iterator{ row, row_size(row), this }; 1468 } 1469 1470 template<class T> cbegin_row(unsigned int row) const1471 typename filled_tableau<T>::in_row_const_iterator filled_tableau<T>::cbegin_row(unsigned int row) const 1472 { 1473 return in_row_const_iterator{ row, 0, this }; 1474 } 1475 1476 template<class T> cend_row(unsigned int row) const1477 typename filled_tableau<T>::in_row_const_iterator filled_tableau<T>::cend_row(unsigned int row) const 1478 { 1479 return in_row_const_iterator{ row, row_size(row), this }; 1480 } 1481 1482 template<class T> begin_row(unsigned int row) const1483 typename filled_tableau<T>::in_row_const_iterator filled_tableau<T>::begin_row(unsigned int row) const 1484 { 1485 return cbegin_row(row); 1486 } 1487 1488 template<class T> end_row(unsigned int row) const1489 typename filled_tableau<T>::in_row_const_iterator filled_tableau<T>::end_row(unsigned int row) const 1490 { 1491 return cend_row(row); 1492 } 1493 1494 1495 1496 1497 template<class T> 1498 template<class OutputIterator> Garnir_set(OutputIterator it,unsigned int row,unsigned int col) const1499 OutputIterator filled_tableau<T>::Garnir_set(OutputIterator it, unsigned int row, unsigned int col) const 1500 { 1501 assert(col>0); 1502 unsigned int r=row, c=col; 1503 *it=(*this)(r,c); 1504 ++it; 1505 while(r>0) { 1506 --r; 1507 *it=(*this)(r,c); 1508 ++it; 1509 } 1510 r=row; 1511 --c; 1512 *it=(*this)(r,c); 1513 ++it; 1514 while(r+1<column_size(c)) { 1515 ++r; 1516 *it=(*this)(r,c); 1517 ++it; 1518 } 1519 return it; 1520 } 1521 1522 template<class T> nonstandard_loc() const1523 std::pair<int, int> filled_tableau<T>::nonstandard_loc() const 1524 { 1525 unsigned int r=number_of_rows(); 1526 assert(r>0); 1527 do { 1528 --r; 1529 for(unsigned int c=0; c<row_size(r)-1; ++c) { 1530 if((*this)(r,c) > (*this)(r,c+1) ) 1531 return std::pair<int, int>(r,c); 1532 } 1533 } 1534 while(r>0); 1535 return std::pair<int,int>(-1,-1); 1536 } 1537 1538 template<class T> standard_form()1539 bool tableaux<T>::standard_form() 1540 { 1541 bool already_standard=true; 1542 1543 typename tableau_container_t::iterator thetab=storage.begin(); 1544 while(thetab!=storage.end()) { 1545 (*thetab).sort_within_columns(); 1546 std::pair<int,int> where=(*thetab).nonstandard_loc(); 1547 if(where.first!=-1) { 1548 already_standard=false; 1549 combin::combinations<typename T::value_type> com; 1550 for(unsigned int i1=where.first; i1<(*thetab).column_size(where.second); ++i1) 1551 com.original.push_back((*thetab)(i1,where.second)); 1552 for(unsigned int i1=0; i1<=(unsigned int)(where.first); ++i1) 1553 com.original.push_back((*thetab)(i1,where.second+1)); 1554 com.sublengths.push_back((*thetab).column_size(where.second)-where.first); 1555 com.sublengths.push_back(where.first+1); 1556 com.permute(); 1557 for(unsigned int tabi=1; tabi<com.size(); ++tabi) { 1558 T ntab((*thetab)); 1559 unsigned int offset=0; 1560 for(unsigned int i1=where.first; i1<(*thetab).column_size(where.second); ++i1, ++offset) 1561 ntab(i1,where.second)=com[tabi][offset]; 1562 for(unsigned int i1=0; i1<=(unsigned int)(where.first); ++i1, ++offset) 1563 ntab(i1,where.second+1)=com[tabi][offset]; 1564 ntab.multiplicity*=-1*com.ordersign(tabi); 1565 add_tableau(ntab); 1566 } 1567 thetab=storage.erase(thetab); 1568 } 1569 else ++thetab; 1570 } 1571 return already_standard; 1572 } 1573 1574 template<class T> add_tableau(const T & ntab)1575 void tableaux<T>::add_tableau(const T& ntab) 1576 { 1577 typename tableau_container_t::iterator it=storage.begin(); 1578 while(it!=storage.end()) { 1579 if((*it).compare_without_multiplicity(ntab)) { 1580 (*it).multiplicity+=ntab.multiplicity; 1581 if((*it).multiplicity==0) 1582 storage.erase(it); 1583 return; 1584 } 1585 ++it; 1586 } 1587 storage.push_back(ntab); 1588 } 1589 1590 1591 template<class T> projector_normalisation() const1592 yngrat_t filled_tableau<T>::projector_normalisation() const 1593 { 1594 yngrat_t norm=1; 1595 norm/=hook_length_prod(); 1596 return norm; 1597 } 1598 1599 template<class T> projector(combin::symmetriser<T> & sym,bool modulo_monoterm) const1600 void filled_tableau<T>::projector(combin::symmetriser<T>& sym, bool modulo_monoterm) const 1601 { 1602 for(unsigned int r=0; r<number_of_rows(); ++r) 1603 for(unsigned int c=0; c<row_size(r); ++c) 1604 sym.original.push_back(rows[r][c]); 1605 1606 unsigned int offset=0; 1607 // symmetrise over boxes in rows 1608 for(unsigned int r=0; r<number_of_rows(); ++r) { 1609 sym.permutation_sign=1; 1610 sym.permute_blocks.clear(); 1611 sym.block_length=1; 1612 sym.input_asym.clear(); 1613 for(unsigned int c=0; c<row_size(r); ++c) 1614 sym.permute_blocks.push_back(offset++); 1615 sym.apply_symmetry(); 1616 } 1617 // sym.collect(); 1618 // anti-symmetrise over boxes in columns 1619 if(modulo_monoterm) { 1620 int newmult=1; 1621 for(unsigned int c=0; c<row_size(0); ++c) 1622 newmult*=combin::factorial(column_size(c)); 1623 for(unsigned int i=0; i<sym.size(); ++i) 1624 sym.set_multiplicity(i, sym.signature(i)*newmult); 1625 } 1626 else { 1627 sym.permute_blocks.clear(); 1628 for(unsigned int c=0; c<row_size(0); ++c) { 1629 unsigned int r=0; 1630 sym.value_permute.clear(); 1631 sym.permutation_sign=-1; 1632 sym.input_asym.clear(); 1633 while(r<number_of_rows() && c<row_size(r)) 1634 sym.value_permute.push_back(rows[r++][c]); 1635 if(sym.value_permute.size()>1) 1636 sym.apply_symmetry(); 1637 } 1638 } 1639 // sym.collect(); 1640 } 1641 1642 template<class T> projector(combin::symmetriser<T> & sym,combin::range_vector_t & sublengths_scattered) const1643 void filled_tableau<T>::projector(combin::symmetriser<T>& sym, 1644 combin::range_vector_t& sublengths_scattered) const 1645 { 1646 for(unsigned int r=0; r<number_of_rows(); ++r) 1647 for(unsigned int c=0; c<row_size(r); ++c) 1648 sym.original.push_back(rows[r][c]); 1649 1650 unsigned int offset=0; 1651 // symmetrise over boxes in rows 1652 for(unsigned int r=0; r<number_of_rows(); ++r) { 1653 sym.permutation_sign=1; 1654 sym.permute_blocks.clear(); 1655 sym.block_length=1; 1656 sym.input_asym.clear(); 1657 for(unsigned int c=0; c<row_size(r); ++c) 1658 sym.permute_blocks.push_back(offset++); 1659 sym.apply_symmetry(); 1660 } 1661 /// anti-symmetrise over boxes in columns 1662 sym.permute_blocks.clear(); 1663 for(unsigned int c=0; c<row_size(0); ++c) { 1664 unsigned int r=0; 1665 sym.value_permute.clear(); 1666 sym.permutation_sign=-1; 1667 while(r<number_of_rows() && c<row_size(r)) 1668 sym.value_permute.push_back(rows[r++][c]); 1669 1670 sym.sublengths_scattered=sublengths_scattered; 1671 1672 // // Now setup sublengths_scattered to take into account 1673 // // asym_ranges. These asym_ranges refer to values stored in the 1674 // // boxes of the full tableau. We need to find the locations of 1675 // // these values inside the full original, as that is what goes 1676 // // into sublengths_scattered. 1677 // 1678 // sym.input_asym.clear(); 1679 // sym.sublengths.clear(); 1680 // sym.sublengths_scattered.clear(); 1681 // for(unsigned int m=0; m<sym.value_permute.size(); ++m) { 1682 // // Try to find this value in an asym range. 1683 // unsigned int overlap=0; 1684 // for(unsigned int n=0; n<asym_ranges.size(); ++n) { 1685 // for(unsigned int nn=0; nn<asym_ranges[n].size(); ++nn) { 1686 // if(sym.value_permute[m]==asym_ranges[n][nn]) { 1687 // std::cout << "found " << sym.value_permute[m] << " in range" << std::endl; 1688 // // FIXME: this assumes that even though asym_ranges[n] is a superset 1689 // // of the current part of value_permute, elements are in the same order. 1690 // ++m; ++nn; 1691 // while(nn<asym_ranges[n].size()) { 1692 // if(sym.value_permute[m]==asym_ranges[n][nn]) { 1693 // std::cout << "same range: " << sym.value_permute[m] << std::endl; 1694 // ++m; 1695 // ++overlap; 1696 // } 1697 // ++nn; 1698 // } 1699 // break; 1700 // } 1701 // } 1702 // } 1703 // if(overlap>0) --m; 1704 // sym.sublengths.push_back(overlap+1); 1705 // } 1706 // unsigned int sum=0; 1707 // for(unsigned int m=0; m<sym.sublengths.size(); ++m) 1708 // sum+=sym.sublengths[m]; 1709 // 1710 // std::cout << sum << " " << sym.value_permute.size() << std::endl; 1711 // assert(sum==sym.value_permute.size()); 1712 1713 // All set to run... 1714 if(sym.value_permute.size()>1) 1715 sym.apply_symmetry(); 1716 } 1717 } 1718 1719 template<class T> operator =(const filled_tableau<T> & other)1720 filled_tableau<T>& filled_tableau<T>::operator=(const filled_tableau<T>& other) 1721 { 1722 rows=other.rows; 1723 tableau::operator=(other); 1724 return (*this); 1725 } 1726 1727 template<class T> total_dimension(unsigned int dim)1728 yngint_t tableaux<T>::total_dimension(unsigned int dim) 1729 { 1730 yngint_t totdim=0; 1731 typename tableau_container_t::const_iterator it=storage.begin(); 1732 while(it!=storage.end()) { 1733 totdim+=(*it).dimension(dim); 1734 ++it; 1735 } 1736 return totdim; 1737 } 1738 1739 template<class T, class OutputIterator> LR_tensor(const tableaux<T> & tabs1,const T & tab2,unsigned int maxrows,OutputIterator out,bool alltabs=false)1740 void LR_tensor(const tableaux<T>& tabs1, const T& tab2, unsigned int maxrows, 1741 OutputIterator out, bool alltabs=false) 1742 { 1743 typename tableaux<T>::tableau_container_t::const_iterator it=tabs1.storage.begin(); 1744 while(it!=tabs1.storage.end()) { 1745 LR_tensor((*it), tab2, maxrows, out, alltabs); 1746 ++it; 1747 } 1748 } 1749 1750 template<class T1, class T2> add_box(T1 & tab1,unsigned int row1,const T2 & tab2,unsigned int row2,unsigned int col2)1751 void add_box(T1& tab1, unsigned int row1, 1752 const T2& tab2, unsigned int row2, unsigned int col2) 1753 { 1754 tab1.add_box(row1, tab2(row2,col2)); 1755 } 1756 1757 template<class T1> add_box(T1 & tab1,unsigned int row1,const tableau &,unsigned int,unsigned int)1758 void add_box(T1& tab1, unsigned int row1, 1759 const tableau&, unsigned int, unsigned int) 1760 { 1761 tab1.add_box(row1); 1762 } 1763 1764 typedef filled_tableau<std::pair<int, int> > keeptrack_tab_t; 1765 1766 template<class Tab, class OutputIterator> LR_add_box(const Tab & tab2,Tab & newtab,unsigned int currow2,unsigned int curcol2,unsigned int startrow,unsigned int maxrows,OutputIterator outit,keeptrack_tab_t & Ycurrent,bool alltabs)1767 void LR_add_box(const Tab& tab2, Tab& newtab, 1768 unsigned int currow2, unsigned int curcol2, unsigned int startrow, 1769 unsigned int maxrows, 1770 OutputIterator outit, 1771 keeptrack_tab_t& Ycurrent, 1772 bool alltabs) 1773 { 1774 // Are we at the end of the current row of boxes in tab2 ? 1775 if((++curcol2)==tab2.row_size(currow2)) { 1776 // Are we at the end of tab2 altogether? 1777 if((++currow2)==tab2.number_of_rows()) { 1778 *outit=newtab; // Store the product tableau just created. 1779 return; 1780 } 1781 curcol2=0; 1782 startrow=0; 1783 } 1784 1785 // Rule "row_by_row". 1786 for(unsigned int rowpos=startrow; rowpos<std::min(newtab.number_of_rows()+1,maxrows); ++rowpos) { 1787 // Rule "always_young". 1788 if(rowpos>0 && rowpos<newtab.number_of_rows()) 1789 if(newtab.row_size(rowpos-1)==newtab.row_size(rowpos)) 1790 continue; // No, would lead to non-Young tableau shape. 1791 1792 // The column where the box will be added. 1793 unsigned int colpos=(rowpos==newtab.number_of_rows())?0:newtab.row_size(rowpos); 1794 1795 // Rule "avoid_sym2asym". 1796 for(unsigned int rr=0; rr<rowpos; ++rr) 1797 if(Ycurrent(rr,colpos).first==(int)(currow2)) 1798 goto rule_violated; 1799 1800 // Rule "avoid_asym2sym". 1801 if(alltabs) // if not generating all tabs, ordered will take care of this already. 1802 for(unsigned int cc=0; cc<colpos; ++cc) 1803 if(Ycurrent(rowpos,cc).second==(int)(curcol2)) 1804 goto rule_violated; 1805 1806 // Rule "ordered". 1807 if(!alltabs && currow2>0) { 1808 int numi=0, numimin1=0; 1809 if(rowpos>0) { 1810 for(unsigned int sr=0; sr<rowpos; ++sr) // top to bottom 1811 for(unsigned int sc=0; sc<Ycurrent.row_size(sr); ++sc) { // right to left 1812 // Count all boxes from currow2 and from currow2-1. 1813 if(Ycurrent(sr,sc).first==(int)(currow2)) ++numi; 1814 if(Ycurrent(sr,sc).first==(int)(currow2)-1) ++numimin1; 1815 } 1816 } 1817 ++numi; // the box to be added 1818 if(numi>numimin1) 1819 goto rule_violated; 1820 1821 // continue counting to see whether a previously valid box is now invalid 1822 for(unsigned int sr=rowpos; sr<Ycurrent.number_of_rows(); ++sr) // top to bottom 1823 for(int sc=Ycurrent.row_size(sr)-1; sc>=0; --sc) { // right to left 1824 if(Ycurrent(sr,sc).first==(int)(currow2)) ++numi; 1825 if(Ycurrent(sr,sc).first==(int)(currow2)-1) ++numimin1; 1826 if(numi>numimin1) 1827 goto rule_violated; 1828 } 1829 } 1830 1831 // Put the box at row 'rowpos' and call LR_add_box recursively 1832 // to add the other boxes. 1833 Ycurrent.add_box(rowpos, std::pair<int,int>(currow2, curcol2)); 1834 add_box(newtab, rowpos, tab2, currow2, curcol2); 1835 LR_add_box(tab2, newtab, currow2, curcol2, alltabs?0:rowpos, maxrows, 1836 outit, Ycurrent, alltabs); 1837 1838 // Remove the box again in preparation for trying to add it to other rows. 1839 newtab.remove_box(rowpos); 1840 Ycurrent.remove_box(rowpos); 1841 1842 rule_violated: 1843 ; 1844 } 1845 } 1846 1847 template<class Tab, class OutputIterator> LR_tensor(const Tab & tab1,const Tab & tab2,unsigned int maxrows,OutputIterator outit,bool alltabs=false)1848 void LR_tensor(const Tab& tab1, const Tab& tab2, unsigned int maxrows, 1849 OutputIterator outit, bool alltabs=false) 1850 { 1851 // Make a copy of tab1 because LR_add_box has to change it and 1852 // tab1 is const here. 1853 Tab newtab(tab1); 1854 1855 // Tableau which keeps track of the LR rules. It contains the 1856 // current (incomplete) shape of the tensor product, and for all boxes 1857 // which come from tab2 we store the row and column of tab2 1858 // from which they originated. Tab1 boxes have (-2,-2) stored. 1859 keeptrack_tab_t Ycurrent; 1860 Ycurrent.copy_shape(tab1); 1861 keeptrack_tab_t::iterator yi=Ycurrent.begin(); 1862 while(yi!=Ycurrent.end()) { 1863 (*yi)=std::pair<int,int>(-2,-2); 1864 ++yi; 1865 } 1866 1867 LR_add_box(tab2, newtab, 0, -1, 0, maxrows, outit, Ycurrent, alltabs); 1868 } 1869 1870 template<class T, class OutputIterator> LR_tensor(const tableaux<T> &,bool,unsigned int,OutputIterator)1871 void LR_tensor(const tableaux<T>&, bool, unsigned int, OutputIterator ) 1872 { 1873 assert(1==0); 1874 } 1875 1876 1877 1878 std::ostream& operator<<(std::ostream&, const tableau& ); 1879 1880 template<class T> 1881 std::ostream& operator<<(std::ostream&, const tableaux<T>& ); 1882 1883 template<class T> 1884 std::ostream& operator<<(std::ostream&, const filled_tableau<T>& ); 1885 1886 template<class T> number_of_rows() const1887 unsigned int filled_tableau<T>::number_of_rows() const 1888 { 1889 return rows.size(); 1890 } 1891 1892 template<class T> row_size(unsigned int num) const1893 unsigned int filled_tableau<T>::row_size(unsigned int num) const 1894 { 1895 assert(num<rows.size()); 1896 return rows[num].size(); 1897 } 1898 1899 template<class T> operator ()(unsigned int row,unsigned int col)1900 T& filled_tableau<T>::operator()(unsigned int row, unsigned int col) 1901 { 1902 assert(row<rows.size()); 1903 assert(col<rows[row].size()); 1904 return rows[row][col]; 1905 } 1906 1907 template<class T> operator ()(unsigned int row,unsigned int col) const1908 const T& filled_tableau<T>::operator()(unsigned int row, unsigned int col) const 1909 { 1910 assert(row<rows.size()); 1911 assert(col<rows[row].size()); 1912 return rows[row][col]; 1913 } 1914 1915 template<class T> operator [](unsigned int boxnum) const1916 const T& filled_tableau<T>::operator[](unsigned int boxnum) const 1917 { 1918 unsigned int row = 0; 1919 while (true) { 1920 if (boxnum < row_size(row)) 1921 break; 1922 boxnum -= row_size(row); 1923 ++row; 1924 } 1925 return rows[row][boxnum]; 1926 } 1927 1928 template<class T> ~filled_tableau()1929 filled_tableau<T>::~filled_tableau() 1930 { 1931 } 1932 1933 template<class T> add_box(unsigned int rownum)1934 void filled_tableau<T>::add_box(unsigned int rownum) 1935 { 1936 if(rownum>=rows.size()) 1937 rows.resize(rownum+1); 1938 assert(rownum<rows.size()); 1939 rows[rownum].push_back(T()); 1940 } 1941 1942 template<class T> add_box(unsigned int rownum,T val)1943 void filled_tableau<T>::add_box(unsigned int rownum, T val) 1944 { 1945 if(rownum>=rows.size()) 1946 rows.resize(rownum+1); 1947 assert(rownum<rows.size()); 1948 rows[rownum].push_back(val); 1949 } 1950 1951 template<class T> swap_columns(unsigned int c1,unsigned int c2)1952 void filled_tableau<T>::swap_columns(unsigned int c1, unsigned int c2) 1953 { 1954 assert(c1<row_size(0) && c2<row_size(0)); 1955 assert(column_size(c1)==column_size(c2)); 1956 for(unsigned int r=0; r<column_size(c1); ++r) { 1957 T tmp=(*this)(r,c1); 1958 (*this)(r,c1)=(*this)(r,c2); 1959 (*this)(r,c2)=tmp; 1960 } 1961 } 1962 1963 template<class T> remove_box(unsigned int rownum)1964 void filled_tableau<T>::remove_box(unsigned int rownum) 1965 { 1966 assert(rownum<rows.size()); 1967 assert(rows[rownum].size()>0); 1968 rows[rownum].pop_back(); 1969 if(rows[rownum].size()==0) 1970 rows.pop_back(); 1971 } 1972 1973 template<class T> clear()1974 void filled_tableau<T>::clear() 1975 { 1976 rows.clear(); 1977 tableau::clear(); 1978 } 1979 1980 template<class T> operator <<(std::ostream & str,const tableaux<T> & tabs)1981 std::ostream& operator<<(std::ostream& str, const tableaux<T>& tabs) 1982 { 1983 typename tableaux<T>::tableau_container_t::const_iterator it=tabs.storage.begin(); 1984 while(it!=tabs.storage.end()) { 1985 str << (*it) << std::endl << std::endl; 1986 ++it; 1987 } 1988 return str; 1989 } 1990 1991 template<class T> operator <<(std::ostream & str,const filled_tableau<T> & tab)1992 std::ostream& operator<<(std::ostream& str, const filled_tableau<T>& tab) 1993 { 1994 for(unsigned int i=0; i<tab.number_of_rows(); ++i) { 1995 for(unsigned int j=0; j<tab.row_size(i); ++j) { 1996 // str << "|" << tab(i,j) << "|"; 1997 str << tab(i,j); 1998 } 1999 if(i==0) { 2000 str << " " << tab.dimension(10); 2001 if(tab.has_nullifying_trace()) str << " null"; 2002 } 2003 if(i!=tab.number_of_rows()-1) 2004 str << std::endl; 2005 else 2006 str << " (" << tab.multiplicity << ")" << std::endl; 2007 } 2008 return str; 2009 } 2010 2011 }; 2012 2013 2014