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