function y=convertStruct2Cell(pc)
% convertStruct2Cell Converts cell-array of structures in P
%  (representing multiple enumerations of the chain
%   multiplication problem) into a cell-array of cell-arrays
%   of "program" vectors.

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

% If this is one structure, wrap it in a cell-array:
single_struct = ~iscell(pc);
if single_struct,
    pc={pc};
end

% Is this a single-variable problem?
if length(pc)==1,
    if ~isstruct(pc{1}),
        y={{[1 0]}};
        return
    end	
end	

for i=1:length(pc),
    p=pc{i};
    
    localRecursion(p,0);
    c=localRecursion(p,1);
    
    % Overwrite last result index with the output index (0):
    c{end}(3)=0;
    y{i}=c;
end

% Convert back from nested cells if needed:
if single_struct,
    y=y{1};
end


% ------------------------------------------------
function c=localRecursion(p,init)

persistent Gtemp chainResult;
if nargin>1,
   if init==0,
      Gtemp=[]; chainResult={};
   else
      c=chainResult;
      return
   end
end

freeList=[];

% Get depth order:
% [1 2] -> Left is deeper than Right
% [2 1] -> Right is deeper than Left
DepthOrder = getDepthOrder(p);
children = {p.Lvar p.Rvar};
children = children(DepthOrder);

for i=1:2,
   % Get "left" contribution
   % If .Lvar is a string, use it directly
   % If .Lvar is a struct, it's the child
   if isstruct(children{i}),
      % Get child computation's temp name
      c=localRecursion(children{i});
      % c(3) is the destination
      result{i}=c(3);  % numeric, neg. temp index
      % Consumed the temp variable
      % record index for free'ing after use
      freeList(end+1)=c(3);
   else
      result{i}=children{i};
   end
   % Convert to # if a character:
   if ischar(result{i}),
      result{i} = result{i}-'A'+1;
   end
end

[T,Gtemp]=allocTemp(Gtemp);
c = [result{DepthOrder} T];

chainResult{end+1}=c;
Gtemp=freeTemp(Gtemp,freeList);


% ----------------------------------------------------
function depthOrder= getDepthOrder(p)

% Determine ordering of depth of subtree p
% 
% [1 2] -> Left is deeper than Right
% [2 1] -> Right is deeper than Left

%depthOrder = [2 1];
%depthOrder = [1 2];

cntL=descendDepth(p.Lvar,0);
cntR=descendDepth(p.Rvar,0);

if cntL>=cntR,
	depthOrder = [1 2];
else
    depthOrder = [2 1];
end


% ----------------------------------------------------
function cnt = descendDepth(p,cnt)

if isstruct(p),
	cntL = descendDepth(p.Lvar,cnt+1);
	cntR = descendDepth(p.Rvar,cnt+1);
    cnt = max(cntL,cntR);
end

% ----------------------------------------------------
function Gtemp=freeTemp(Gtemp,idx)
% Return temp variable - no longer being used:

% Temp index is negative, and so are the entries
% in the global temp list:
if isempty(Gtemp),
   error('No temps in list - cannot free.');
end
for j=1:length(idx),
   i=find(Gtemp==idx(j));
   if isempty(i),
      error('Temp index not found - cannot free');
   end
   Gtemp(i)=[];
end


% ----------------------------------------------------
function [tnew,Gtemp]=allocTemp(Gtemp)
% Determine index of next temp to use
% Maintain cache of all active temp #'s in Gtemp

if ~isempty(Gtemp),
   
   % Get +ve # of all temps currently in use
   posTemp=-Gtemp;
   maxTemp=max(posTemp);
   
   % Determine all temps possible in this range
   tempList=1:maxTemp;
   
   % Find which ones were not used ("holes" in the temp list)
   unused = setdiff(tempList,posTemp);
   if ~isempty(unused),
      % Get lowest-numbered "hole" to use as a temp
      nextTemp=min(unused);
   else
      nextTemp=maxTemp+1;
   end
else
   nextTemp=1;  % no temps used yet
end

% Use -ve # for temp:
tnew=-nextTemp;

% Put into global list:
Gtemp(end+1)=tnew;


% [EOF] convertStruct2Cell.m
