// **************** Coxeter group functions ****************
forward GetWord;
// Input C, g; C is a Coxeter group, g is a group element. Output a reduced expression for g 
// as a sequence of integers where i corresponds to s_i
forward PushPiRight;
// Input g, We; g an extended affine Weyl group element of the form <k,h>, where pi^k in Pi and h in W_a, 
// We a structure for the extended affine Weyl group. Output h' as a list, where h'pi^k = g = pi^k h.
forward YesPi;
// Input h, We or <k,h>, We; h an element of We`AG, k an integer.
// Output <0,h> or <k,h> if <k,h> is input.
forward WeLeftDescentSet;
// Input e, We; e an extended affine Weyl group element.
// Output the left descent set of e as a set of integers.
forward WeRightDescentSet;
// Similar to WeLeftDescentSet.
forward MinCosetFactorRight;
// Input g, J, We; g an element of We`AG, J a subset of 1..We`n.
// Output a tuple <g1,g2> such that g2 is a minimal right coset rep and g1*g2 = g.
forward MinCosetFactorLeft;
// Input g, J, We; g an element of We`AG, J a subset of 1..We`n.
// Output a tuple <g1,g2> such that g1 is a minimal left coset rep and g1*g2 = g.
forward MinCosetFactorShort;
// Input s, g, J, We; s an integer corresponding to a simple reflection, g in We`AG and g is a minimal left coset representative -- an element of We`AG^J, J a subset of 1..We`n.
// Output g1,T such that g1 is a minimal left coset rep and s*g = g1*t, and t is the identity in which case
// T is the empty set or t is a simple reflection in which case T is a one-element set containing the
// integer corresponding to t.
forward LeftShuffle;
// Input e, IndType, We; e an element of an iterated product of Coxeter groups, 
// IndType a structure for an iterated product of Coxeter groups.
// Output an element of the same form as e, factored so that as large as possible
// an element is on the left.
// WARNING : currently assumes that all groups in Indtype equal We
forward WeIndLeftDescentSet;
// Input e, IndType, We; e an element of an iterated product of Coxeter groups, 
// IndType a structure for an iterated product of Coxeter groups.
// Output the left descent set of e as a list of integers.
forward WeMult;
// Input e1, e2, We; e1, e2 are extended affine Weyl group elements.
// Output e1*e2 (in the form <length 0 element, element of W_a>).
forward WeIndMult;
// Input i, e2, IndType, We; i an integer corresponding to a simple reflection, e2 an IndType element.
// Output s_i*e2.
forward WeListMult;
// Input elist, We; elist a list of extended affine Weyl group elements.
// Output the product of the elements in elist.
forward LengthDownOne;
// Input e, We; e an extended affine Weyl group element.
// Output the set of elements less than e in Bruhat order and of length 1 less than e. 
//   If the option descent := true, then only returns those elements with right descent set
//   contained in {We`n}.
forward AllDown;
// Input e, We; e an extended affine Weyl group element.
// Output the set of elements less than e in Bruhat order.
forward CycleType;
//returns the cycle type of a permutation group element g, in the  form of a partition
forward ListPerm;
// Input g, We where g is an element of a symmetric group We or a more general group structure and output g as a permutation of 1 to n in the form of a list
forward InverseZ;
// Input a word w of an affine permutation in window notation, and output its inverse in window notation
forward ListZPerm;
// Input n, g or n, g, We where n is an integer and g is an element of W_a of type \tilde{A_n} expressed as a reduced word. Output g in window notation
// **************** End Coxeter group functions ****************
// *************** Permutation / Word functions *****************
forward Inverse;
// Input a permutation w as a list. Output the inverse of w as a list.
forward Relabel;
// Input a list of integers w. Output the word obtained by relabeling so that entries are 1..n with the same relative order; entries further right are treated as being larger
forward CochargeLabel;
// Input w; w a list of integers. Output the cocharge labeling of Relabel(w).
forward RotateWord;
// Input w, r; w the cocharge labeling of a permutation, r an integer. Output the cocharge labeling resulting from rotating the word r times (one rotation removes the rightmost letter and brings it to the beginning of the word and adds 1 to the letter)
forward ParenSwap;
// Input w, i; w a semistandard word, i an integer. Output the result of the crystal reflection coming from looking at i and i+1 as right and left parentheses.
// For example, 
// > ParenSwap([1,1,2,2,2,2],1);
// [ 1, 1, 1, 1, 2, 2 ]
// > ParenSwap([2,2,2,2,1,1],1);
// [ 1, 1, 2, 2, 1, 1 ]
forward RollIn;
// Helper function for Standardize and UnStandardize
forward RollOut;
// Helper function for Standardize and UnStandardize
forward Standardize;
// Input w; w semistandard word. Output the standard word obtained by applying the standardization map of Lascoux and Schutzenberger
forward UnStandardize;
// Input w, mu; w a standard word, mu a partition. Output the semistandard word of content mu that is the inverse of the standardization map
forward MyCatabolism;
// Input w; w a standard word. Output the partition equal to catabolizability of the insertion tableau of w
// ***************** End Permutation / Word functions ************
// *************** Tableau combinatorics *************************
forward MyRowInsert;
// Input ~T, x. Update T to be the tableau obtained from T by row inserting the integer x
forward PTab;
// Input w. Output the insertion tableau of w as a list of lists
forward QTab;
// Input w. Output the recording tableau of w as a list of lists
forward MyShape;
// Input tableau T as a list of lists. Output the shape of T
forward ToPartition;
// Same as MyShape.
forward EnsureTabNotMagma;
// Input a tableau T as a list of lists or in Magma's format. Output this tableau as a list of lists
forward EnsureTabMagma;
// Input a tableau T as a list of lists or in Magma's format. Output this tableau in Magma's format
forward SuperStandard;
// Input mu, k; mu a partition, k an integer. Output the superstandard tableau of shape mu whose first row consists of only k, next row consists of k+1, etc.
forward EasyUnStandardize;
// Input w, mu; w a permutation as a list, mu a partition. Output the semistandard order with content mu and the same relative order as w (elements to the right considered larger)

forward OuterCorners;
// Input mu; mu a partition. Output the outer corners of mu as a list of <r, c>, for r, c the row and column of the outer corner.
forward CoCyclage;
// Input T, i, j; T a tableau in Magma's format, i, j the position of an outer corner. Output the result of cocyclaging T at this outer corner
forward Cyclage;
// Input T, i, j; T a tableau in Magma's format, i, j the position of an outer corner. Output the result of cyclaging T at this outer corner
forward Catabolism;
// Helper function for RowCatable
forward InitBlock;
// Helper function for RowCatable
forward RowCatable;
// Input T; T a tableau in Magma's format. Output the row catabolizability of T as a partition.

// ******************* End Tableau combinatorics *******************
// ****************** Miscellaneous *****************************
forward DKEGraph;
// Input SH; SH a partition. Output a list of two things: First a list of permutations all with the same recording tableau T where T is of shape SH, second a list of |SH|-2 matrices that encode which permutations are related by a dual Knuth equivalence, i.e., the first matrix corresponds to DKEs on 1, 2, 3.
forward Restrict;
// Input w, n; w a permutation of length n in the form of a list.
// Output the result of deleting the letter n from w.
forward Induce;
// Input w, k; w a permutation as a list, k an element of 1..#w.
// Output the result of adding a k to the end of the word w and increasing
//   all letters greater than or equal to k by 1.
forward RMult;
// Input w, i; w a permutation as a list, i an integer corresponding to a simple reflection.
// Output the result of right multiplying by s_i.
//   If the option nodescentR := true, then only multiply if length increases.
forward LMult;
// Similar to RMult.
forward Subsequences;
// Input an array x, returns a list of the subsequences of x
forward modd;
// Input k, n; k, n integers. Output the integer in 1..n congruent to k mod n
// ************************ End Miscellaneous ***********************



// ****************************************************************************************************************

//P := Partitions(n);
O := OrderedIntegerMonoid();
TabM := TableauMonoid(O);



//Type for the extended Weyl group, pi generates the subgroup of length 0 elements. 
WeType := recformat<name, S, AG, pi, n:Integers(), G, GfAG, RG, f>;

//Type for sequence of extended Weyl groups, producted over parabolic subgroups.
IndElementType:= recformat<ng,groups,parabolics>;

procedure InitWe(myname, ~We)
	We`AG := CoxeterGroup(myname);
	We`name := myname;
	We`n := #(Generators(We`AG));
	We`S := [1..We`n]; 
	We`pi := map<We`S -> We`S | [<i,modd(i-1,We`n)>:i in [1..#(We`S)]]>;	
	We`G := StandardParabolicSubgroup(We`AG, {1..(We`n)-1});	
	We`GfAG := hom<We`G->We`AG | [We`AG.i : i in [1..(We`n)-1]]>;
	We`RG, We`f := ReflectionGroup(We`G);
end procedure;

procedure InitInd(groups,parabolics,~IT);
	  IT`groups := groups;
	  IT`parabolics := parabolics;
	  IT`ng := #groups;
end procedure;

procedure ShrinkIndType(~IndType,k)
	
	if k ne IndType`ng then
		Remove(~(IndType`groups),k);	
		Remove(~(IndType`parabolics),k);
	else
		Remove(~(IndType`parabolics),k-1);
		Remove(~(IndType`groups),k);
	end if;
	IndType`ng:=IndType`ng-1;
end procedure;

//name := "A~" cat IntegerToString(n-1);
//We := rec<WeType|>;
//InitWe(name, ~We);


// ****************************************************************************************************************
// ****************************************************************************************************************

// **************** Coxeter group functions ****************
function GetWord(C,g)
	return ElementToSequence(g);
end function;

//Given an element g of We, return an element x of W_a such that g=x*pi,
//where pi is of length zero
function PushPiRight(g,We)
	try 
		x := GetWord(We`AG,g[2]);
	catch e
		x := g[2];
	end try;
	Inv := map<We`S -> We`S | [<We`pi(i), i>:i in [1..#(We`S)]]>;
	pifun := map<We`S -> We`S | [<i,i>:i in [1..#(We`S)]]>;	//initialize to ID	
	for j in [1..g[1]] do
		pifun := Inv * pifun; 
	end for;	
	
	return [pifun(s):s in x];
end function;

function YesPi(e1, We)
	try 
		temp := e1[2] in We`AG;
	catch e
		e1 := <0, e1>;
	end try;	

	return e1;
end function;

function WeLeftDescentSet(e, We)
	//try 
//		kemp :=	e[2] in We`AG;
//	catch e
//		return WeIndLeftDescentSet(e,We);
//	end try;	
	temp := SetToIndexedSet(LeftDescentSet(We`AG,e[2]));
	Inv := map<We`S -> We`S | [<We`pi(i), i>:i in [1..#(We`S)]]>;
	pifun := map<We`S -> We`S | [<i,i>:i in [1..#(We`S)]]>;	//initialize to ID	
	for j in [1..e[1]] do
		pifun := Inv * pifun; 
	end for;	
	return {pifun(i):i in temp};
end function;

//This differs from WeLeftDescentSet because we're taking the convention of factoring
//the length zero element on the left.
function WeRightDescentSet(e, We)
	temp := SetToIndexedSet(RightDescentSet(We`AG,e[2]));
	return temp;
end function;

//returns a tuple <g1,g2> such that g2 is a minimal right coset rep and g1*g2 = g
//g assumed to be in We`AG
function MinCosetFactorRight(g,J,We)
	g2 := g;
	g1 := Id(We`AG);
	while WeLeftDescentSet(g2,We) meet J ne {} do
		s := SetToIndexedSet(WeLeftDescentSet(g2,We) meet J)[1];
		g2 := WeMult(We`AG.s,g2,We);
		g1 := WeMult(g1,We`AG.s,We);
	end while;
	return g1, g2;
end function;

//returns a tuple <g1,g2> such that g1 is a minimal left coset rep and g1*g2 = g
//g assumed to be in We`AG
function MinCosetFactorLeft(g,J,We)
	g1 := g;
	g2 := Id(We`AG);
	while WeRightDescentSet(g1,We) meet J ne {} do
		s := SetToIndexedSet(WeRightDescentSet(g1,We) meet J)[1];
		g1 := WeMult(g1,We`AG.s,We);
		g2 := WeMult(We`AG.s,g2,We);
	end while;
	return g1, g2;
end function;

//given s, g returns g1,t such that g1 is a minimal left coset rep and s*g = g1*t
//g assumed to be in We`AG and mincoset of W_J, s is an integers corresponding to simple reflection
//t is the empty set of contains one element that is a simple reflection
function MinCosetFactorShort(s,g,J,We)
	t := SetToIndexedSet(WeRightDescentSet(WeMult(We`AG.s,g,We),We) meet J);
	if #t gt 1 then 
		print "I proved this should never print!";
	end if;
	if #t eq 0 then
		return WeMult(We`AG.s,g,We),t;
	end if;
	return WeMult(WeMult(We`AG.s,g,We),We`AG.(t[1]),We),t;
end function;

//Given e an IndType element, factor as large as possible an element on the left
//return the factored form of such an element
//WARNING : currently assumes that all groups in Indtype equal We
function LeftShuffle(e,IndType,We)
	if IndType`ng eq 1 then
		return e;
	end if;
	J := IndType`parabolics[IndType`ng-1];
	g1,g2 := MinCosetFactorRight(e[#e],J,We);
	//print "printing g1,g2", g1,g2;
	e[#e-1] := WeMult(e[#e-1],g1,We);
	ShrinkIndType(~IndType,IndType`ng);
	return LeftShuffle([e[i]:i in [1..#e-1]],IndType,We) cat [g2];
end function;

function WeIndLeftDescentSet(e,IndType,We)
	return WeLeftDescentSet(LeftShuffle(e,IndType,We)[1],We);
end function; 



//return e1*e2 where ei is in W_e of the form <length 0 element, element of W_a>
function WeMult(e1, e2, We)
	e1 := YesPi(e1, We);
	e2 := YesPi(e2, We);
	
	//print "e1, e2, We`AG:", e1, e2, We`AG;
	
	w1 := GetWord(We`AG, e1[2]);	

	//pifun is We`pi composed with itself e2[1] times
	pifun := map<We`S -> We`S | [<i,i>:i in [1..#(We`S)]]>;	//initialize to ID	
	for j in [1..e2[1]] do
		pifun := We`pi * pifun; 
	end for;		
	
	//push e1[2] through the length 0 element of e2
	l1 := #w1 eq 0 select Id(We`AG) else (&*[We`AG.pifun(i):i in w1]);
	//print "answer:", <e1[1]+e2[1],l1*e2[2]>;
	return <e1[1]+e2[1], (l1)*e2[2]>;
end function;

			
function WeIndMult(s, e2,IndType,We)
	if IndType`ng gt 1 then
		J := IndType`parabolics[1];
	else
		J := {};
	end if;
	gg,t:=MinCosetFactorShort(s,e2[1],J,We);
	if #t eq 0 then 
		e2[1] := gg;
		return e2;
	else	  
		ShrinkIndType(~IndType,1);
		return [gg] cat WeIndMult(t[1],[e2[i]:i in [2..#e2]],IndType,We);
	end if;
end function;


function WeListMult(elist, We)
	if #elist eq 0 then
		return Id(We`AG);
	else
		e := elist[1];
		elist := [elist[i]:i in [2..#elist]];
		return WeMult(e, WeListMult(elist, We), We);
	end if;
end function;

//
function LengthDownOne(ine,We:descents:=false)
	singleelem := false;
	try 
		mye:=ine[1];
		temp := ine[2][2] in We`AG;
	catch e
		mye := ine;
		singleelem := true;
	end try;	

	w:=GetWord(We`AG,mye[2]);
	out:={};
	for i in [1..#w] do
		x:=Remove(w,i);
		nw:=&*([Id(We`AG)]cat[We`AG.k:k in x]);
		if Length(nw) eq #w-1 and (not descents or RightDescentSet(We`AG,nw) subset {We`n})  then
			g:=ine;
			if singleelem then
				g[2] := nw;
			else
				g[1][2]:=nw;		
			end if;
			out:=out join {g};	
		end if;
	end for;
	return out;
end function;

function AllDown(ine,We)
	e:=ine[1];
	w:=GetWord(We`AG,e[2]);
	out:={};
	subs:=Subsequences(w);
	for x in subs do
		nw:=&*([Id(We`AG)]cat[We`AG.k:k in x]);
		g:=ine;
		g[1][2]:=nw;		
		out:=out join {g};	
	end for;
	return out;
end function;

//returns the cycle type of a permutation group element g, in the form of a partition
function CycleType(g)
	CS := CycleStructure(g);
	p := [];
	for c in CS do
		p:= p cat [c[1] : i in [1..c[2]]];
	end for;
	return p;
end function;

//given an element of g, return g as a list of numbers from 1 to n
function ListPerm(g,We)
	try 
		G := We`G;
	catch e
		G := We;
	end try;
	L := GetWord(G,g);
	w := [1..We`n];
	for s in L do
		nw := w;
		nw[s] := w[s+1];
		nw[s+1] := w[s];
		w := nw;
	end for;
	return Inverse(w);
end function;

function InverseZ(w)
ww := [(w[i]-1) mod #w +1: i in [1..#w]];
	pos := [Position(ww,k) : k in [1..#w]];
	return [pos[i] + ww[pos[i]] - w[pos[i]]: i in [1..#w] ];
end function; 

//return a Z-permutation corresponding g in W_a of type A
function ListZPerm(n,g,...)
	//if We`name[1] ne "A" then 
	//	return 0;
	//end if;
	if #g eq 2 then
		We:=g[2];
		L := GetWord(We`AG,g[1]);	
	else 
		L:=g[1];
	end if;
	
	w := [1..n];
	for s in L do
		nw := w;
		if n gt s then 
			nw[s] := w[s+1];
			nw[s+1] := w[s];
		else
			nw[n] := w[1] + n;
			nw[1] := w[n] - n;
		end if;
		w := nw;
	end for;
	return w;
end function;

// **************** End Coxeter group functions ****************
// *************** Permutation / Word functions *****************

function Inverse(w)
	return [Position(w,k) : k in [1..#w]];
end function;

//Given a word with integer entries, relabel so that entries are 1..n
//with the same relative order
//entries further right are treated as being larger
function Relabel(w:inverse:=false)
	nw := w;
	for i in [1..#w] do
		x, p := Min(w);
		nw[p] := i;
		w[p] := 9999999;
	end for;
	if inverse then
		return Inverse(nw);
	else
		return nw;
	end if;
end function;

function CochargeLabel(w:tab := false,start:=0)
	if tab then
		w:=EnsureTabNotMagma(w);
		w := &cat(Reverse(w));
	end if;
	w:=Relabel(w:inverse:=true);
	nw:=[0:i in [1..#w]];
	c:=start;
	for i in [1..(#w-1)] do
		nw[w[i]]:=c;
		if w[i] gt w[i+1] then
			c:=c+1;
		end if;
	end for;
	nw[w[#w]]:=c;
	if tab then 
		return PTab(nw);
	else
		return nw;
	end if;
end function;

function RotateWord(w,r)
	for i in [1..r] do
		Insert(~w,1,w[#w]+1);
		Remove(~w,#w);
	end for;
	return w;
end function;

// Looks at only i and i+1 as right and left parentheses, matches parentheses and then swaps the leftover
function ParenSwap(w,i)
	savew:=w;
	w:=[x eq i or x eq i + 1 select x else -99:x in w];
	change:=true;
	while change do
		change:=false;
		posi1:=0;
		for k in [1..#w] do
			if w[k] eq i+1 then
				posi1:=k;
			end if;
			if w[k] eq i and posi1 ne 0 then
				w[k]:=-99;
				w[posi1]:=-99;
				change:=true;
				posi1:=0;
			end if;
		end for;
	end while;
	ni1:=#[x:x in w|x eq i+1];
	count:=1;
	for k in [1..#w] do
		if w[k] ne -99 then
			if count gt ni1 then
				savew[k]:=i+1;
			else
				savew[k]:=i;
			end if;
			count+:=1;
		end if;
	end for;
	return savew;
end function;

function RollIn(w,m)
	for i in [m-1..1 by -1] do
		w:=ParenSwap(w,i);
	end for;
	return w;
end function;

function RollOut(w)
	m:=Min(w);
	M:=Max(w);
	for i in [m..M-1] do
		w:=ParenSwap(w,i);
	end for;
	return w;
end function;

function Standardize(w)
	while #w ne #{x:x in w} do
		m:=#[x:x in w|x eq 1];
		count:=1;
		for i in [1..#w] do
			if w[i] eq 1 then
				w[i]:=count;
				count+:=1;
			else
				w[i]+:=m-1;
			end if;
		end for;
		content:=[#[x:x in w|x eq i]:i in [-100..100]];
		x,y:=Max(content);
		w:=RollIn(w,y-101);
	end while;
	return w;
end function;

function UnStandardize(w,mu:maxmu:=false)
	if maxmu then
		mu:=[0:i in [1..#w]];
	end if;
	r:=1;
	while &+([0]cat[mu[i]:i in [1..r-1]]) lt #w do
		T:=RSKCorrespondence(O!w);
		m:=InitBlock(T);
		content:=[#[x:x in w|x eq i]:i in [1..m]];
		m:=Position([x eq 1:x in content],false);
		if m eq 0 then
			newm:=#content;
		else
			newm:=m-1;
		end if;
		if maxmu then
			mu[r]:=Min(newm,#w-&+([0]cat[mu[i]:i in [1..r-1]]));
		end if;
		if newm lt mu[r] then
			print "Not mu catabolizable";
			return 0;
		end if;
		count:=1;
		for i in [1..#w] do
			if w[i] le mu[r] then
				w[i]:=1;
			else
				w[i]-:=mu[r]-1;
			end if;
		end for;
		print "before rollout w",w;
		w:=RollOut(w);
		print "after rollout w",w;
		r+:=1;
	end while;
	return w;
end function;

function MyCatabolism(w)
	mu:=[0:i in [1..#w]];
	w:=CochargeLabel(w);
	while #w ne 0 do
		x:=w[#w];
		k:=Position(mu,x);
		Remove(~w,#w);
		if k eq 0 then
			Insert(~w,1,x+1);
		else
			mu[k]:=mu[k]+1;
		end if;
	end while;
	return ConjugatePartition(mu);
end function;
// ***************** End Permutation / Word functions ************

// *************** Tableau combinatorics *************************

procedure MyRowInsert(~T, x)
	r := 1;
	while r in [1..#T] do 
		c := 1;
		while c in [1..#(T[r])] do 
			if T[r][c] gt x then 
				y := T[r][c];
				T[r][c] := x;
				x:= y;
				c:= 999998;
			end if;
			c +:= 1;
		end while;
		if c ne 999999 then 
			Append(~T[r],x);
			r := 999998;
		end if;
		r+:=1;
	end while;
	if r ne 999999 then 
		Append(~T,[x]);
	end if;
end procedure;

function PTab(w)
	T := [];
	for x in w do
		MyRowInsert(~T,x);	
	end for;
	return T;
end function;

function QTab(w)
	return PTab(Relabel(w:inverse:=true));	
end function;

function MyShape(T)
	return [#x : x in T];
end function;

function ToPartition(T)
	return [#x : x in T];
end function;

function EnsureTabNotMagma(T)
	try 
	    temp := T in TabM;
	    catch e
	    temp:= false;
	end try;
	
	if temp then
		T:=PTab(ElementToSequence(RowWord(T)));
	 end if;
	
	
	return T;
end function;

function EnsureTabMagma(T)
	try
		temp:= T in TabM;
		catch e
			try 
				T:=Tableau([O! arow : arow in T]);
				catch e	
				T := Tableau([O![99999]]);
			end try;		
	end try;
	
	return T;	
end function;

function SuperStandard(mu, k)
	return [[i+k-1: x in [1..mu[i]] ]: i in [1..#mu]];
end function;

function EasyUnStandardize(w,mu)
	nn := &+mu;
	nw := [0:i in [1..nn]];
	iw := Inverse(w);
	s := &cat(SuperStandard(mu,0));
	for i in [1..nn] do
		nw[iw[i]] := s[i];
	end for;
	return nw;
end function;

function OuterCorners(S)
	x:=[S[i] ne S[i+1]:i in [1..((#S)-1)]]cat [true];
	return [<r,S[r]> : r in [1..#S] | x[r]];
end function;

function CoCyclage(T,i,j)
	T,k:=InverseRowInsert(T,i,j);	
	tT:=Conjugate(T);
	return Conjugate(RowInsert(tT,k));
end function;

function Cyclage(T,i,j:whatelement:=false)
	tT:=Conjugate(T);
	T,k:=InverseRowInsert(tT,j,i);	
	T:=Conjugate(T);
	if whatelement then
		return <RowInsert(T,k),k>;
	else
		return RowInsert(T,k);
	end if;
end function;

function Catabolism(T,mu)
	w:=ElementToSequence(RowWord(T));
	c:=#mu;
	r:=&+[Shape(T)[i]:i in [c+1..(#Shape(T))]];
	w:=[w[modd(i,#w)]:i in [r+1..(r+#w)]];
	//print "w",w;
	P,Q := RSKCorrespondence(O!w);
	return P;
end function;

function InitBlock(T)
	r:=ElementToSequence(Row(T,1));
	k:=Position([r[i] eq i:i in [1..#r]],false);
	if k eq 0 then
		return #r;
	else
		return k-1;
	end if;
end function;

function RowCatable(T)
	mu:=[];
	Append(~mu,InitBlock(T));
	t:=Weight(T);
	while mu[#mu] ne t do
		T:=Catabolism(T,[Shape(T)[1]]);
		Append(~mu,InitBlock(T));
	end while;
	nmu:=[mu[1]] cat [mu[i+1]-mu[i]:i in [1..((#mu)-1)]];
	return nmu;
end function;

// ******************* End Tableau combinatorics *******************
// ****************** Miscellaneous *****************************

function DKEGraph(SH)
	nn := &+SH;
	Qs := StandardTableaux(SH);
	Rw := [ElementToSequence(RowWord(x)) : x in Qs];
	Rwi := [Inverse(x) : x in Rw];
	des := [{k : k in [1..(#x-1)] | x[k] gt x[k+1]} : x in Rwi];
	out := [];
	for s in [2..(nn-1)] do
		M := Matrix([[0 : x in [1..#Qs]] : y in [1..#Qs]]);
		for r,c in [1..#Qs] do
			if #({s-1,s} meet des[r]) eq 1 then
				x1 := Rwi[r];
				if Rwi[r][s+1] eq Sort([Rwi[r][j] : j in [s-1..s+1]])[2] then 
					x1[s-1] := x1[s];
					x1[s] := Rwi[r][s-1];
				else
					x1[s] := x1[s+1];
					x1[s+1] := Rwi[r][s];
				end if;
				M[r][Position(Rwi,x1)] := 1;
			end if;
		end for;
		Append(~out,M);
	end for;
	return <Rw,out>;
end function;
		

//removes the nth letter of the word w
function Restrict(w,n)
	w:=[w[i]:i in [1..#w]];
	return Remove(w,Position(w,n));
end function;

//adds a k to the end of the word w and increases all letters greater than or equal
//to k by one
function Induce (w,k)
for i in [1..#w] do
	if w[i] ge k then
	w[i]:=w[i]+1;
	end if;
end for;
Append(~w,k);
return w;
end function;

//right multiplies by the simple reflection s
//if nodescentR is true then only multiply if length increases
function RMult (w,s:nodescentR:=true)
	if nodescentR and w[s] gt w[s+1] then
		return w;
	else
		nw:=w;
		nw[s]:=w[s+1];
		nw[s+1]:=w[s];
		return nw;
	end if;
end function;

//left multiplies by the simple reflection s
//if nodescentL is true then only multiply if length increases
function LMult (w,s:nodescentL:=true)
	return Inverse(RMult(Inverse(w),s:nodescentR:=nodescentL));
end function;

//returns a list of all subsequences of a sequence
function Subsequences(list)
	subsets := [v: v in KSpace(GF(2),#list)];
	return [ [list[i] : i in [1..#list]| s[i] eq 1] : s in subsets];
end function;

function modd(k,n)
	 return ((k-1) mod n) +1; 
end function;

// ************************ End Miscellaneous ***********************