tab=jointable(tab1,tab2,keys1,keys2,fillval)

function tab=jointable(tab1,tab2,keys1,keys2,fillval)
% jointable: join two tables using lists of keys
%
% usage: jointable(tab1,tab2)
%        jointable(tab1,tab2,keys1,keys2)
%        jointable(tab1,tab2,keys1,keys2,fillval)
%
% JOINTABLE joins two tables much like an SQL join, using the list of keys,
% i.e. if TAB1 is N1xM1 and TAB2 is N2xM2, then the resulting table has
% M1+M2 columns with each row a pair of rows of TAB1 and TAB2 that have
% matching keys (or filled with FILLVAL if a key has no match).
%
% NOTE: requires LEXCMP (see below).
%
% The tables can be arrays or cell arrays or arrays of user-defined
% objects, provided they are of the same class.
%
% The key lists can be arrays or cell arrays of any class, provided the
% number of keys matches the number of rows of the corresponding table;
% also the key lists must be valid inputs to SORT and any pair of keys is
% valid input to LEXCMP.
%
% If the key lists are empty or not provided, the first column of the
% tables are used.
%
% If FILLVAL is not provided, either [] or NaN or 0 is used depending on
% the table's object class.
%
%
% Examples:
%   jointable([1;2;3],[4;5],{'a','b','c'},{'a','b'}) % join on string keys
%   jointable({'a';'b';'c'},{'d';'e'},[1,2,3],[1,2]) % join on numeric keys
%   jointable([1;2;3],[4;5],ones(1,3),ones(1,2)) % join on non-unique keys
%
% Example with user-defined object classes (requires fractions toolbox):
%   jointable(fr([1;2;3]),fr([4;5]),fr([1:3]),fr([1:2]))
%
%
% Further details:
%
% The keys should generally be unique within each list, but if non-unique
% keys are provided then at most one match will be returned for each copy
% (as opposed to an SQL full outer join, where all possible combinations of
% matches are returned).
%
% LEXCMP does not distinguish between string and equivalent numeric arrays,
% e.g. 'a' and 0+'a', so mixed alphabetic/numeric key lists may give
% unexpected results.
%
% Non-char cell array keys are currently not supported, unless you have an
% applicable implementation of SORT.  If you do, the results of SORT should
% be consistent with the ordering assumed by LEXCMP.
%
% The current version is not terribly efficient for large numeric arrays of
% keys mainly due to the use of LEXCMP, but I plan to remedy this in future
% versions.
%
%
% See also:
%  LEXCMP (http://www.mathworks.com/matlabcentral/fileexchange/23035)
%  Fractions Toolbox (http://www.mathworks.com/matlabcentral/fileexchange/24878)

% Author: Ben Petschel 15/9/2009
% Version history:
%   15/9/2009 - first release

% trivial case, empty tables
if isempty(tab1)
  tab=tab2;
  return;
elseif isempty(tab2)
  tab=tab1;
  return;
end;

[n1,m1] = size(tab1);
[n2,m2] = size(tab2);

if nargin<3 || isempty(keys1)
  keys1 = tab1(:,1);
end;
if nargin<4 || isempty(keys2)
  keys2 = tab2(:,2);
end;
if nargin<5
  % try to create fill value (the following rigmarole is to ensure correct class)
  if iscell(tab1)
    fillval=[];
  else
    try
      fillval=tab1(1);
      fillval(1)=nan; % ensures fillval is same class as tab
    catch %#ok
      fillval(1)=0;
    end;
  end;
end;


if numel(keys1)~=n1
  error('jointable:tab2size','length of keys1 must match number of rows of tab1');
end;
if numel(keys2)~=n2
  error('jointable:tab2size','length of keys2 must match number of rows of tab2');
end;
% check that classes agree
tabclass=class(tab1);
if ~isequal(tabclass,class(tab2))
  error('jointable:tabclass','tab1 and tab2 must be the same object class');
end;

[keys1,ind1]=sort(keys1(:));
[keys2,ind2]=sort(keys2(:));

if iscell(keys1)
  keyref1=@(n)keys1{n};
else
  keyref1=@(n)keys1(n);
end;
if iscell(keys2)
  keyref2=@(n)keys2{n};
else
  keyref2=@(n)keys2(n);
end;

% create an empty array of the same class as tab1 and tab2
if isequal(tabclass,'cell')
  tab=repmat({fillval},n1+n2,m1+m2);
else
  tab=repmat(fillval,n1+n2,m1+m2);
end;

% fill the table
i=1;
i1=1;
i2=1;
while i1<=n1 && i2<=n2
  switch lexcmp(keyref1(i1),keyref2(i2))
    case -1
      % key1(i1)<key2(i2): copy in row i1
      tab(i,1:m1) = tab1(ind1(i1),:);
      i1=i1+1;
      i=i+1;
    case 1
      % key1(i1)>key2(i2): copy in row i2
      tab(i,(m1+1):end) = tab2(ind2(i2),:);
      i2=i2+1;
      i=i+1;
    case 0
      % key1(i1)==key2(i2): copy in both rows
      tab(i,1:m1) = tab1(ind1(i1),:);
      tab(i,(m1+1):end) = tab2(ind2(i2),:);
      i1=i1+1;
      i2=i2+1;
      i=i+1;
    otherwise
      error('jointable:badcmp','unexpected comparison result');
  end;
end;
% trim table and copy in remaining rows, if any
tab=tab(1:(i+(n1-i1)+(n2-i2)+1),:);
if i1<=n1
  tab(i:end,1:m1)=tab1(i1:n1,:);
end;
if i2<=n2
  tab(i:end,m1+1:end)=tab2(i2:n2,:);
end;