%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%    Copyright (c) 2004.  Takayuki Osogami.  All Rights Reserved.   %
%                                                                   %
% Permission to use, copy, modify, and distribute this source code  %
% and its documentation for any purpose, without fee, and without   %
% a written agreement, is hereby granted, provided that the above   %
% copyright notice, this paragraph and the following two paragraphs %
% appear in all copies, modifications, and distributions.           %
% Created by Takayuki Osogami, Department of Computer Science,      %
% Carnegie Mellon University.                                       %
%                                                                   %
% IN NO EVENT SHALL THE AUTHOR BE LIABLE TO ANY PARTY FOR ANY       %
% DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS   %
% SOURCE CODE AND ITS DOCUMENTATION, EVEN IF THE AUTHOR HAS BEEN    %
% ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.                        %
%                                                                   %
% THE AUTHOR SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,      %
% BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY     %
% AND FITNESS FOR A PARTICULAR PURPOSE.  THE SOURCE CODE AND        %
% ACCOMPANYING DOCUMENTATION, IF ANY, PROVIDED HEREUNDER IS         %
% PROVIDED "AS IS."  THE AUTHOR HAS NO OBLIGATION TO PROVIDE        %
% MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Usage: [A0,A1,A2] = finiteforeground(F0,F1,F2,n,B0,B1,B2,kB)
%
% Given a (foreground) QBD process whose transitions depends on
% the level of a background QBD process, finiteforeground
% returns a single QBD process for the foreground QBD process
%
% There are kB generator matrices for the foreground QBD process.
% The i-th generator matrix is used when the background process is in level i.
%
% [ F1{i,1} F0{i,1}                                         ]
% [ F2{i,2} F1{i,2} F0{i,2}                                 ]
% [         F2{i,3} F1{i,3} F0{i,3}                         ]
% [                     :       :                           ]
% [                         F2{i,n} F1{i,n} F0{i,n}         ]
% [                                 F2{i,n} F1{i,n} F0{i,n} ]
% [                                             :       :   ]
%
% We define cells, F0, F1, and F2:
% F0 = {F0{1,1} F0{1,2} ... F0{n,n}}
% F1 = {F1{1,1} F1{1,2} ... F1{n,n}}
% F2 = {F2{1,1} F2{1,2} ... F2{n,n}},
% Note that the QBD process repeats after level n.
%
% The generator matrix of the background QBD process is
%
% [ B1{1} B0{1}                                 ]
% [ B2{2} B1{2} B0{2}                           ]
% [       B2{3} B1{3} B0{3}                     ]
% [              :     :                        ]
% [                        B2{kB} B1{kB} B0{kB} ]
%
% We define cells, B0, B1, and B2:
% B0 = {B0{1} B0{2} ... B0{n}}
% B1 = {B1{1} B1{2} ... B1{n}}
% B2 = {B2{1} B2{2} ... B2{n}},
%
% The generator matrix of the output QBD process is
%
% [ A1{1} A0{1}                                    ]
% [ A2{2} A1{2} A0{2}                              ]
% [       A2{3} A1{3} A0{3}                        ]
% [              :     :                           ]
% [                        A2{n} A1{n} A0{n}       ]
% [                              A2{n} A1{n} A0{n} ]
% [                                     :     :    ]
%
% INPUT: F0,F1,F2: cells for F0{i,j}, F1{i,j}, F2{i,j}
%        n: level that the QBD process starts repeating
%        B0,B1,B2: cells for B0{i}, B1{i}, B2{i}
%        kB: the number of levels in the output QBD process
%
% OUTPUT: A0,A1,A2: cells for A0{i}, A1{i}, A2{i}
%
% author: Takayuki Osogami
%         Department of Computer Science
%         Carnegie Mellon University
%         osogami@cs.cmu.edu
% date: August 15, 2004

function [A0,A1,A2] = finiteforeground(F0,F1,F2,n,B0,B1,B2,kB)

%%%%%%%%%%%%%%%%%%%%%%%%%
%% getting matrix size %%
%%%%%%%%%%%%%%%%%%%%%%%%%

for i = 1:kB
  dim = size(B1{i});
  SB(i) = dim(1);
end
  for i = 1:n
  dim = size(F1{1,i});
  SF(i) = dim(1);
end


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% aggregating B0,B1,B2 into single generator matrix, QB %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

base = [0,0];
for i = 1:kB

  dim = size(B1{i});
  QB(base(1)+1:base(1)+dim(1),base(2)+1:base(2)+dim(2)) = B1{i};

  if( i < kB )
    dim0 = size(B0{i});
    QB(base(1)+1:base(1)+dim(1),base(2)+dim(2)+1:base(2)+dim(2)+dim0(2)) = B0{i};
  end

  if( i > 1 )
    dim2 = size(B2{i});
    QB(base(1)+1:base(1)+dim(1),base(2)-dim2(2)+1:base(2)) = B2{i};
  end

  base = base + dim;

end


%%%%%%%%%%%%%%%%%%%%%%%%%  
%% specifying A0,A1,A2 %%
%%%%%%%%%%%%%%%%%%%%%%%%%  

for i = 1:n

  base = [0,0];
  for j = 1:kB
    M = kron(eye(SB(j)),F0{j,i});
    dim = size(M);
    A0{i}(base(1)+1:base(1)+dim(1),base(2)+1:base(2)+dim(2)) = M;
    base = base + dim;
  end

  base = [0,0];
  for j = 1:kB
    M = kron(eye(SB(j)),F2{j,i});
    dim = size(M);
    A2{i}(base(1)+1:base(1)+dim(1),base(2)+1:base(2)+dim(2)) = M;
    base = base + dim;
  end

  base = [0,0];
  for j = 1:kB
    M = kron(eye(SB(j)),F1{j,i});
    dim = size(M);
    A1{i}(base(1)+1:base(1)+dim(1),base(2)+1:base(2)+dim(2)) = M;
    base = base + dim;
  end

  A1{i} = A1{i} + kron(QB,eye(SF(i)));

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% normalizing diagonal elements of A1 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

for i = 1:n
 dim = size(A1{i});
 for j = 1:dim(1)
  if( i == 1 )
    A1{i}(j,j) = 0;
    A1{i}(j,j) = - (sum(A0{i}(j,:)) + sum(A1{i}(j,:)));
  else
    A1{i}(j,j) = 0;
    A1{i}(j,j) = - (sum(A0{i}(j,:)) + sum(A1{i}(j,:)) + sum(A2{i}(j,:)));
  end
 end
end