function list = genStructs(N)
%GEN_STRUCTS Generate cell array of structures enumerating all
%  associative-rule combinations for the chain multiplication
%  of N multiplicands.
%
% See also genFwdStruct.

% Author: D. Orofino
% Copyright 1984-2000 The MathWorks, Inc. 
% $Revision: 1.3 $ $Date: 2000/06/01 03:16:19 $

list={};
if N==0, return; end

TreeStack('reset');
TreeStack('push',char('A'+(0:N-1)));

[v,ok]=TreeStack('pop');
while ok,
   [y,stop]=SplitOneLevel(v,[],0);
   if stop==-1,
      % Done with this entry:
      list{end+1}=y;
   end
   %if stop==0,
   %   error('Should not have stop=0 at top level.');
   %end
   
   [v,ok]=TreeStack('pop');
end


% ----------------------------------------------------
function field = convertIdxToField(idx)

field={};
for i=length(idx):-1:1,
   if idx(i)==1,
      f='Lvar';
   else
      f='Rvar';
   end
   field{i}=f;
end


% ----------------------------------------------------
function [y,stop]=SplitOneLevel(node,idx,stop)
% Recursive associative-rule decomposition:

persistent orig

if stop,
   y=node;
   return
end

if isempty(idx),
   orig=node;
end

if ~isstruct(node),
   N=length(node);
   if N==1,
      y=node;
      stop=-1; % xxx
   else
      field=convertIdxToField(idx);
      for i=1:N-1,
         q.Lvar=node(1:i);
         q.Rvar=node(i+1:end);
         if ~isempty(field),
            y=orig;
            y=setfield(y,field{:},q);
         else
            y=q;
         end
         TreeStack('push',y);
      end
      stop=1; % forked new trees on stack
   end
   
else
   y=node;
   [y.Lvar,stop]=SplitOneLevel(node.Lvar,[idx 1],stop);
   if (stop~=1),
      stop=0; % Must reset to 0, since it could be -1 at this point
      [y.Rvar,stop]=SplitOneLevel(node.Rvar,[idx 2],stop);
      if (stop~=1),
         stop=-1;
         y=node; % we're done with this tree
      end
   end
end

% [EOF] genStructs.m
