function [assigned, unassignedrows, unassignedcols] = auction(A, cost)
% AUCTION  Auction assigmned algorithm
%
% [assigned, unassignedrows, unassignedcols] = auction(A, cost)
% A is the assignment matrix [A_ij], ie the cost associated to assigning
% item i to target j.  (Note, the handling of exogenos targets are
% automatic and handled by the cost parameter.)  The function minimizes the
% cost, assuming the cost cost to unassigned rows and columns.
%
% Based on (Blackman & Popoli, 1999)

% Copyright (2019) Gustaf Hendeby <gustaf.hendeby@liu.se>

% No claim of being efficient, but gets the job done in relatively few
% lines of code.  Many tricka would apply to speed up the implementation.

  [nI, nC] = size(A);
  extra = inf(nI);  for i=1:nI; extra(i, i) = cost;  end
  A = [A, extra]; nC = nC+nI;
  if nI > nC
    error('Number of columns in A must be greater or equal to the number of rows.');
  end
  A = -A;  % Minimize instead of max in the book.
  eps = 0.5*1/nC;
  I2C = zeros(1, nI, 'uint16');  % 0 indicates unassigned item
  C2I = zeros(1, nC, 'uint16');  % 0 indicates unassigned customer
  P = zeros(1, nC);

  while any(I2C==0)  % Any unassigned item
    i = find(I2C==0, 1);
    [m, j] = max(A(i, :) - P);
    if C2I(j) ~= 0;  I2C(C2I(j)) = 0;  end
    C2I(j) = i;  I2C(i) = j;
    pj = P(j);
    P(j) = inf;
    P(j) = pj + m - max(A(i, :) - P) + eps;
  end

  % Extract data in the same format as MATLABs assignauction.
  unassignedrows = I2C>nC-nI;
  assigned = uint32([find(~unassignedrows); I2C(~unassignedrows)]');
  unassignedrows = uint32(find(unassignedrows));
  unassignedcols = uint32(find(C2I==0));
  unassignedcols = unassignedcols(unassignedcols<=nC-nI);
end