##
##
##
##              gray code package
##
##copyright D. Joyner and J. McShea, 5-97
##
##
##########################################################

convert2binary:=proc(n::integer)
##
##decimal to binary 
##
 local i,L0,M;
 L0:=binary2list(convert(n,binary));
 for i from 1 to nops(L0) do
  if L0[i]=`0` then M[i]:=0; else M[i]:=1; fi; 
 od; 
 M:=[seq(M[i],i=1..nops(L0))];
 RETURN(M);
end: 

convert2gray:=proc(n::integer)
##
##decimal to binary reflected Gray code
##
 local i,M0,L0;
 L0:=convert2binary(n);
 M0[1]:=L0[1]:
 for i from 2 to nops(L0) do
  M0[i]:=`mod`(L0[i-1]+L0[i],2);
 od:
 M0:=[seq(M0[i],i=1..nops(L0))];
 RETURN(M0);
end:

nextcodeodd:=proc(a::list,n::integer,Size::integer)
 #return a_2n+1, given a_n
 local i,j,a0;
 if n=floor(n/2)*2 then
  a0:=[1,seq(a[i],i=1..(Size-1))];
 else
  a0:=[0,seq(a[i],i=1..(Size-1))];
 fi;
 RETURN(a0);
end:

lastcode:=proc(a::list,Size::integer)
 #returns a_n, given a_2n or a_2n+1
 local i,j,a0;
 a0:=[seq(a[i],i=2..(Size)),0];
 RETURN(a0);
end:

nextcodeeven:=proc(a::list,n::integer,Size::integer)
 #return a_2n, given a_n
 local i,j,a0;
 a0:=nextcodeodd(a,n,Size);
 a0:=`mod`(a0+[1,seq(0,i=1..(Size-1))],2);
 RETURN(a0);
end:

gray:=proc(n::integer,Size::integer)
 option remember;
 if n=0 then RETURN([0,seq(0,i=1..(Size-1))]); fi;
 if n=1 then RETURN([1,seq(0,i=1..(Size-1))]); fi;
 if n=floor(n/2)*2 then
  RETURN(nextcodeeven(gray(n/2,Size),n/2,Size));
 fi;
 if n<>floor(n/2)*2 then
  RETURN(nextcodeodd(gray((n-1)/2,Size),(n-1)/2,Size));
 fi;
end:

plot_gray:=proc(n::integer,Size::integer)
 local i,L;
 L:=[seq(sumlist(gray(i,Size)),i=0..n)];
 plots[listplot](L);
end:

wtd_plot_gray:=proc(n::integer,Size::integer,a)
 local i,L;
 L:=[seq(wtd_sumlist(gray(i,Size),a),i=0..n)];
 plots[listplot](L);
end:

gray_coord:=proc(n::integer,Size::integer)
 local i,j,w;
 w:=[seq(`mod`(floor((j+2^(n-1)-1)/2^n),2),j=1..Size)];
 RETURN(w);
end:

gray_2adic:=proc(n::integer,Size::integer)
 local w,i,j;
 w:=[seq(`mod`(floor((Size+2^(j-1)-1)/2^j),2),j=1..n)];
 RETURN(w);
end:

inv_normp:=proc(n::integer,p::integer)
 RETURN(p^(padic[ordp](n,p)));
end:

plot_tri:=proc(L0::list)
 local i,j,A;
 plots[polygonplot]([L0[1],L0[2],L0[3],L0[2]]);
end:

picture:=proc(n::integer)
local t,u,v,w,x,y,z,A,B;
w:=1; x:=1; y:=2; z:=3;
while z<2^n do
 A[w]:=[[x,1],[y,2],[z,1]];
 B[w]:=plot_tri(A[w]);
 x:=x+4; 
 w:=w+1;
 y:=y+4;
 z:=z+4;
od;
for t from 1 to n-2 do
 v:=1;
 u:=A[v][3][1]*2^t;
 while u<2^n do
  A[w]:=[A[v][1]*2^t,A[v][2]*2^t,A[v][3]*2^t];
  B[w]:=plot_tri(A[w]);
  w:=w+1;
  v:=v+1;
  u:=A[v][3][1]*2^t;
 od;
od;
plots[display]([seq(B[i],i=1..(w-1))],view=[0..2^n,0..2^n]);
end:

gray0:=proc(n::integer, k::integer, b::integer)
local i, j, L, w;
  if k = 1 then
      L := [seq(vec(1, n, i), i = 0 .. b - 1)]; RETURN(L)
  fi;
  L := gray0(n, k - 1, b);
  for j from 0 to b - 1 do
      for i to nops(L) do
          w[i, j] := (L[i] + vec(k, n, j)) mod b
      od
  od;
  L := [seq(seq(w[i, j], j = 0 .. b - 1), i = 1 .. nops(L))];
  RETURN(L)
end:

convert2base:=proc(n::integer,b::integer,m::integer)
 local i,M0,L0;
 L0:=gray0(n,n,b)[m];
 M0[1]:=L0[1]:
 for i from 2 to nops(L0) do
  M0[i]:=`mod`(L0[i-1]+L0[i],b);
 od:
 M0:=[seq(M0[i],i=1..nops(L0))];
 RETURN(M0);
end:

wtd_sumlist0:=proc(L::list,a) 
local i,S,n; 
 S:=0;
 n:=nops(L); 
 for i from 1 to n do   
 S:=S+L[n-i+1]*a^(i-1);  
 od; 
RETURN(S);
end:

graycode:=proc(n::integer,m::integer)
 local i,j,L0,L1,L2,L,N;
 if n=1 then RETURN([seq([i],i=0..m-1)]); fi;
 L:=graycode(n-1,m);
 for i from 0 to m-1 do L.i:=op(i+1,L); od;
 N:=nops(L);
 for j from 0 to m-1 do
  M.j:=seq([op(L[i]),j],i=1..N);
 od;
 for j from 0 to m-1 do
  if type(j,odd) then Mreverse.j:=op(reverse([M.j])); 
   else Mreverse.j:=M.j;
  fi;
 od;
 RETURN([seq(Mreverse.i,i=0..(m-1))]);
end:

##################################################
#    list commands, not all of which are used
##################################################

string2list:=proc(s::string)
 local i,L;
 L:=[];
 for i from 1 to length(s) do
  L:=[op(L),substring(s,i)];
 od;
 RETURN(L);
end:

binary2list:=proc(b::integer)
 local i,L,s;
 L:=[];
 s:=convert(b,string);
 L:=string2list(s);
 RETURN(L);
end:

concatenate:=proc(L::list)
 local i,j,L0;
 L0:=[];
 for i from 1 to nops(L) do
  L0:=[op(L0),op(L[i])];
 od;
 RETURN(L0);
end:

sumlist:=proc(L::list)
 local i,S;
 S:=0;
 for i from 1 to nops(L) do
  S:=S+L[i];
 od;
 RETURN(S);
end:

wtd_sumlist:=proc(L::list,a)
 local i,S;
 S:=0;
 for i from 1 to nops(L) do
  S:=S+L[i]*a^i;
 od;
 RETURN(S);
end:

permcyclic:=proc(L::list,p::integer)
 local L0,i,N;
 N:=nops(L);
 if p=0 then RETURN(L); fi;
 if p=1 then 
  for i from 2 to N do
   L0[i]:=L[i-1];
  od;
 L0[1]:=L[N];
 L0:=[seq(L0[i],i=1..N)];
 RETURN(L0);
 fi;
 L0:=permcyclic(permcyclic(L,p-1),1);
 if p>1 then RETURN(L0); fi;
end:

reverse:=proc(L::list)
 local i,n,L0;
 if L=[] then RETURN([]); fi;
 n:=nops(L);
 L0:=[seq(L[n-i+1],i=1..n)];
 RETURN(L0);
end: