function [ envelopes, envelope_matrix ] = find_envelopes( A );
%
% FIND_ENVELOPES Find a set of envelopes for a matrix A as specified by m and n.
%
% This routine finds support envelopes by repreatedly calling find_envelope. 
%
% This routine uses the property that an envelope characterized by 
% m and n is a subset of the envelope characterized by m' and n' when m <= m' 
% and n = n'.  Also, note that the m and n that characterize a block may be 
% different than the m and n specified to find the block. This routine returns
% a unique set of envelopes and a matrix that indexes into this unique set of 
% envelopes for possible value of m and n. 
%
% See also: find_envelope
%
% [ envelopes, envelope_matrix  ] = find_envelopes( A );

% Copyright © Regents of the University of Minnesota. All rights reserved.

[ M N ] = size( A );

% Find the envelopes
envelope_matrix = sparse( [], [], [], M, N );
num_unique_envelopes = 0;

% Outer loop is over values of m
for m = 1 : M
    %disp( m );
    % Inner loop is over values of n
    for n = 1: N
        % Continue if this envelope for this value of m and n has been found
        if envelope_matrix( m, n ) ~= 0
            continue;
        end;
        %disp( n );
        
        % Set up a parent envelope for added efficiency
        if n == 1 
            if m > 1
                parent_env = envelopes( envelope_matrix( m - 1, 1 ) );
            else
                parent_env = [];
            end
        else 
            parent_env = envelopes( envelope_matrix( m, n - 1 ) );
        end
            
        % Find the envelope
        envelope = find_envelope( A, m, n, parent_env ); 
        
        % Break if we have an empty block
        if isempty( envelope )
            break;
        end

        % Update the envelope array and matrix
        if envelope_matrix( envelope.m, envelope.n ) == 0
            num_unique_envelopes = num_unique_envelopes + 1;
            envelopes( num_unique_envelopes ) = envelope;
            
            % Because envelopes can be larger than the initially specified
            % values, update all envelope entries in the envelope matrix 
            % that are subsumed by these values.
            envelope_matrix( m : envelope.m, n : envelope.n ) = num_unique_envelopes;
            
        else 
            envelope_matrix( m, n ) = envelope_matrix( envelope.m, envelope.n );
        end
        
    end;
        
    % Break if we have an empty block at the start of new value of m
    if n == 1 & isempty( envelope )
        break;
    end;
    
end;    


