function new_img = create_new_img(dist_matrix, objs, background, order, dist_vector)

% Create New Image, (Adam Meadows: ameadows@cs.ucr.edu)
% new_img = create_new_img(dist_matrix, objs, background, order, dist_vector)
% 
% DIST_MATRIX is a distance matrix formatted to pass to classicalmds()
% OBJS is a cell array containing the images for the individual objects
% BACKGROUND is the blank background image
% ORDER hold the order in which to place the objects (0 = choose randomly,
% 1 = left-right, 2 = right-left, 3 = top-down, 4 = bottom-up)
% DIST_VECTOR is an optional distance vector (OPTIONAL: if given, a dendogram is made)
%
% NEW_IMG returns the new, nicely formatted image
%


%use background as starter for new image
new_img = background;
dims = size(new_img);

%use MDS to find locations
loc =  dim_bound_mds(dims, dist_matrix);    

%how to sort the objects:
%left-right & up-down, left-right & down-up
%right-left & up-down, or right-left & down-up
if(order == 0)
    r = rand;
else
    r = order/4;
end

if r <= .25
    [S I] = sortrows(loc, [1]);
elseif r <= .50
    [S I] = sortrows(loc, [-1]);
elseif r <= .75
    [S I] = sortrows(loc, [2]);
else
    [S I] = sortrows(loc, [-2]);
end

%re-order objs
for i=1:length(objs) 
    objs2{i} = objs{I(i)};
end

%re-order locs
loc2 = loc(I,:);

for i=1 : length(objs2)
    
    %make sure objects aren't out of the picture frame
    objDims = size(objs2{i});
    
    dob = dist_out_of_bounds(loc2(i,:), objDims, dims);
    loc2(i,:) = loc2(i,:) - dob;
  
    
    %make sure there's no overlap
    loc2(i,:) = find_free_spot(loc2, objs2, dims, i);
    
    %reverse loc(i,:) to be valid for image
    loc_i = loc2(i,:);
    loc_i(2) = dims(1) - loc_i(2);

    %add the object to new_img
    l1 = ceil(loc_i(2)-objDims(1)+1);
    r1 = ceil(loc_i(2));
    l2 = ceil(loc_i(1));
    r2 = ceil(loc_i(1)+objDims(2)-1);
    
    %ensure that there are no 0s
    if l1 == 0 || r1 == 0 || l2 == 0 || r2 == 0
        l1 = l1+1;
        r1 = r1+1;
        l2 = l2+1;
        r2 = r2+1;
    end
    
    new_img(l1:r1,l2:r2,:) = objs2{i};
    
end %end of for each object

%imshow(new_img);

%if it was supplied, use dist_vector to create dendogram
if nargin == 5
    temp = [1:length(objs)];
    figure

    dist_vector = (dist_vector / max(dist_vector))*10;
    Z = linkage(dist_vector,'ward'); 
    [H, T,perm] = dendrogram(Z,0);
    hold on;
    set(gca,'Ylim',[-1.9 max(get(gca,'Ylim'))])

    for j = 1 : length(objs)
        i=perm(j); 
        i=temp(i);

        %Use object image passed in for display
        A = objs{i};
        image([0.6 1.4]+j-1,[-0.1 -0.8] , A)
    end;
    
    axis off
    axis equal
    orient landscape          

end %end of if dendogram

       
        
%end of create_new_image function

%==========================================================================
%==========================================================================
       
       
%function that creates an mds location matrix w/i dims of original image
function new_loc = dim_bound_mds(dims, dist_matrix)

%special case for if everything the same color/shape
if(dist_matrix == 0)
    loc = ones(length(dist_matrix), 2);
    loc(:,1) = loc(:,1) * dims(2)/2;
    loc(:,2) = loc(:,2) * dims(1)/2;
    new_loc = loc;
    return;
end

%loc = mdscale(dist_matrix,2);
loc = classicalmds(dist_matrix,2);
loc(:,1) = (loc(:,1) - min(loc(:,1)));
loc(:,1) = (loc(:,1) / max(loc(:,1)));
loc(:,1) = (loc(:,1) * dims(2));
loc(:,2) = (loc(:,2) - min(loc(:,2)));
loc(:,2) = (loc(:,2) / max(loc(:,2)));
loc(:,2) = (loc(:,2) * dims(1));

new_loc = loc;

% end of dim_bound_mds function

%==========================================================================
%==========================================================================

function varargout = imflipud(varargin)
%IMFLIPUD Flip an image upside down.
%
%   [Y, NEWMAP] = IMFLIPUD(X, MAP) flips the index image represented by the
%   index matrix X and the color map MAP in a up-down direction.  If MAP is
%   empty, X is assumed to be a bitmap, intensity image or RGB image.
%
%   NEWRGB = IMFLIPUD(RGB) flips the RGB represented by the 3-D image array
%   RGB in a up-down direction.
%
%   NEWI = IMFLIPUD(I) flips the intensity image represented by the 2-D
%   matrix I in a up-down direction.
%
%   NEWBM = IMFLIPUD(BM) flips the bitmap image represented by the logical
%   2-D matrix BW in a up-down direction.

%   Author:      Peter J. Acklam
%   Time-stamp:  2004-02-03 21:39:12 +0100
%   E-mail:      pjacklam@online.no
%   URL:         http://home.online.no/~pjacklam

   % Check number of input arguments.
   nargsin = nargin;
   error(nargchk(1, 2, nargsin));

   % Now do the actual flipping.
   varargout = varargin;
   varargout{1} = flipdim(x, 1);
   
%end of imflipud function

%==========================================================================
%==========================================================================

%Finds a new location for the ith object in objs, that doesn't overlap with
% any object < i
function loc_i = find_free_spot(loc, objs, dims, i)

set(0, 'RecursionLimit', 1000);

%first we see if it's valid
[valid moves] = valid_locs(loc, objs, i);

if(valid)
    loc_i = loc(i,:);
    return;
end %end of if point was valid

%now we know what the possible moves are try them all, smallest first

%next loc to recurse on
try_locs = {};
objDims = size(objs{i});

%try the smallest moves first
[S I] = sort(moves);
for k = 1:length(moves)
    %get new location
    m = moves(I(k));
    
    %what we do depends on I(k)
    if(I(k) == 1)
        loc_i = loc(i,:) + [0 m];
    elseif(I(k) == 2)
        loc_i = loc(i,:) + [0 -m];
    elseif(I(k) == 3)
        loc_i = loc(i,:) + [-m 0];
    else
        loc_i = loc(i,:) + [m 0];
    end
    
    %test new location
    dob = dist_out_of_bounds(loc_i, objDims, dims);
    if(dob == 0)
        try_locs{length(try_locs)+1} = loc_i;
        
        new_locs = loc;
        new_locs(i,:) = loc_i;
        if valid_locs(new_locs, objs, i)
            return;
        end
        
    end %end of if it was in bounds
    
end %end of loop through each move

%try up, down, left, right (in that order) make sure to check for
% out of bounds

%now recurse on a random direction and return result
tryme = ceil(rand() * length(try_locs));
new_locs = loc;
new_locs(i,:) = try_locs{tryme};
loc_i = find_free_spot(new_locs, objs, dims, i);

%end of find_free_spot function

%==========================================================================
%==========================================================================



%function to find out by how much A resides INSIDE B
% where A and B are arrays w/ values [ x_min x_max y_min y_max ]
% flag indicates whether A was in B or not, while moves holds how to move
% it to fix the overlap and is in the format: [up down left right]
% holding the distances loc has to move in each direction to escape the
% overlap (all values positive)
function [flag moves] = AinB(A, B)
    
AinB_x = 0;
AinB_y = 0;
flag = 0;
up = 0;
down = 0;
left = 0;
right = 0;

%if A's x values fall within B's
if((B(1) <= A(1)) && (A(1) <= B(2))) || ((B(1) <= A(2)) && (A(2) <= B(2)))
    left = A(2) - B(1) + 1;
    right = B(2) - A(1) + 1;
    AinB_x = 1;
end %end of if there's an x overlap

%if I's y values fall within J's
if((B(3) <= A(3)) && (A(3) <= B(4))) || ((B(3) <= A(4)) && (A(4) <= B(4)))
    up = B(4) - A(3) + 1;
    down = A(4) - B(3) + 1;
    AinB_y = 1;
end %end of if there's a y overlap

flag = 0;
if (AinB_x == 1) && (AinB_y == 1)
    flag = 1;
end

moves = [ up down left right ];

%end of AinB function

%==========================================================================
%==========================================================================


%function to check if current locations (up to i) are valid, returns
%flag == 1 if valid, 0 if invalid, moves = minimum distance to move
%[up down left right] to avoid all overlaps
function [flag moves] = valid_locs(loc, objs, i)

all_moves = [];
moves = [];
flag = 1;

%set the appropriate top/bottom values for i
objDims_i = size(objs{i});
xBottom_i = loc(i,1);
xTop_i = xBottom_i + objDims_i(2);
yBottom_i = loc(i,2);
yTop_i = yBottom_i + objDims_i(1);

%loop through all objects
for j = 1:i-1
    
    %set the appropriate top/bottom values for j
    objDims_j = size(objs{j});
    xBottom_j = loc(j,1);
    xTop_j = xBottom_j + objDims_j(2);
    yBottom_j = loc(j,2);
    yTop_j = yBottom_j + objDims_j(1);

    %if I falls within J
    I = [xBottom_i xTop_i yBottom_i yTop_i];
    J = [xBottom_j xTop_j yBottom_j yTop_j];
    
    [mflag, m] = AinB(I,J);
    if(mflag)
        flag = 0;
        all_moves = [all_moves; m];
    end
    
    [mflag, m] = AinB(J,I);
    if(mflag)
        flag = 0;
        %in this case we need to swap the moves, I needs to move
        m2 = [m(2) m(1) m(4) m(3)];
        all_moves = [all_moves; m2];
    end
    
end %end of for all previous objects
    
if(flag == 1)
    return;
end

%now calculate minimum moves in each direction
up = max(all_moves(:,1));
down = max(all_moves(:,2));
left = max(all_moves(:,3));
right = max(all_moves(:,4));
moves = [up down left right];

% end of valid_locs function

%==========================================================================
%==========================================================================

%Calculates how far out of bounds the given object is
function dob = dist_out_of_bounds(loc_i, objDims, dims)

dx = 0;
dy = 0;

%set the dx value
if(loc_i(1) < 1)
    dx = loc_i(1) - 1; %TBD: might have to -1 from this
elseif(loc_i(1) + objDims(2) >= dims(2))
    dx = loc_i(1) + objDims(2) - dims(2);
end %end of check on x value

%set the dy value
if(loc_i(2) < 1)
    dy = loc_i(2) - 1; %TBD: might have to -1 from this
elseif(loc_i(2) + objDims(1) >= dims(1))
    dy = loc_i(2) + objDims(1) - dims(1);
end %end of check on y value

dob = [ dx dy ];

%end of dist_out_of_bounds function 

%=========================================================================
%=========================================================================