%For Max Margin Training model(Kdd07 paper algorithm)
function [A,D,D1,L,dA,x,count,third,flagr]=MMTrain(rel,mA,mD,mD1,mL,mdA,mx,constant,mthird,mthird_value,dim,turn)  

%=========================================================================
%rel:the relation matrix between VReps and word, [rel]_(ij) is 1 if word i
%occurs in VRep j. [rel]_(i)(VRepno+1)=\sum_{j=1}^{VRepno} [rel]_(ij)

%count: the number of newly added variables

%mthird,mthird_value: the variable moved from B to N whose value is nonzero

%third: output variable to record the newly added constraints  

%dim:the dimension of feature vector, in our experiments, the value is 4.

%This script can be run as the follows:
%[A,D,D1,L,dA,x,count,third,flag]=MMTrain(rel,[],[],[],[],[1],[],constant,[],[],dim,0);
%weight=D1*x;

%After the weight vector is computed, the classification can be done. This
%code does not include the part of computing VRep and the part of testing
%since they are specific to the data set used.
%==========================================================================
format long

[wordno, imageno]=size(rel);
imageno=imageno-1;
%dim=4;

A=mA;
D=mD;
D1=mD1;
L=mL;
dA=mdA;

weight=zeros(dim,1);

[range,rangetemp]=size(mx);

flag=0;


LB=zeros(size(mx));
UB=zeros(size(mx));
[rows_A,cols_A]=size(A);


if(rows_A==0)
    C=[];
else
    C=zeros(rows_A,1);
    for i=1:rows_A
        C(i)=constant;
    end
end

if(range~=0)
    for i=1:range
        UB(i)=Inf;
    end
end

x0=mx;
options=optimset('MaxIter', 10000);
count=0; %added variable at each iteration
third=[];
flagr=1;

for index=1:imageno
    disp(index);
    count=0;    
    temp=sum(rel(:,index)); % index-th column
    selection=zeros(wordno,1);
    for i=1:temp
        selection(i,1)=i;
    end
    %compute the feature vector
    feature=zeros(dim,wordno);
    for i=1:wordno
        if(rel(i,(imageno+1))==0)
            continue;
        end
        if(dim==4)
            feature(1,i)= rel(i,index)/rel(i,(imageno+1));
            feature(2,i) = rel(i,(imageno+1))/imageno;
            feature(3,i) = rel(i,index)/temp;
            feature(4,i) = temp/wordno;
        end
        if(dim==2)
            if(turn==0)
                feature(1,i)= rel(i,index)/rel(i,(imageno+1));
                feature(2,i) = rel(i,index)/temp;
            else
                feature(1,i) = rel(i,(imageno+1))/imageno;
                feature(2,i) = temp/wordno;
            end
        end
    end

    if(selection==rel(:,index))
        selection(temp,1)=0;
        selection(temp+1,1)=temp;
    end   
    
    
    while true
        %test if the sum()<C
        [rows_x,cols_x]=size(x0);
        if(count==0)
            sum_index=0;
        else
            sum_index=sum(x(rows_x-count+1:rows_x,1));
        end
        
        sum_index=sum_index+sum(mthird_value);
        
        if(sum_index<constant)            
            indices=find(selection>0);
            indices1=find(rel(:,index)>0);
            diff=0;            
            diffv=zeros(dim,1);
            for k=1:temp
                if(indices(k)~=indices1(k))
                    diff=diff+1;
                end
                diffv=diffv+feature(:,indices1(k))-feature(:,indices(k));                                                
            end
            diff1=weight'*diffv;            
            if(diff1<diff)               
               L=[L;diff]; 
               count=count+1;
               
               if(rows_x==0)
                   x0=[0];
                   D1=[diffv];
                   D=[(diffv'*diffv)];
               else
                   [rows_third, cols_third]=size(mthird);
                   newvalue=0;
                   if(cols_third~=0)
                       for k=1:cols_third
                            if(selection==mthird(:,k))
                                newvalue=mthird_value(k);
                                mthird_value(k)=0;                                
                                mthird(:,k)=0;
                                break;
                            end
                       end
                   end
                   if(imageno==1)
                       third=[third,selection];
                   end
                   D2=diffv'*D1;
                   D=[D;D2];
                   D2=[D2,diffv'*diffv];
                   D=[D,D2'];
                   D1=[D1,diffv];
                   x0=[x0;newvalue];
               end
               if(count==1)
                   C=[C;constant];
                   if(rows_x>0)
                        [rows_A,cols_A]=size(A);
                        A=[A;zeros(1,cols_A)];
                        dA=[0;dA];
                   end
               end
               A=[A,dA];
               LB=[LB;0];
               UB=[UB;Inf];
               [x,fval,exitflag,output,lambda]=quadprog(D,-L,A,C,[],[],LB,UB,x0,options);
               x0=x;
               weight=D1*x;               
            end            
        else            
            break;
        end
        %select next variable               
        while true
            flag=0;
            for j=temp:-1:1
                permute = find(selection==j);
                if(permute<(wordno-temp+j))
                    selection(permute,1)=0;
                    for k=j:1:temp
                        selection(permute+1+k-j,1)=k;
                    end
                    if((permute+1+temp-j)<wordno)
                        for k=(permute+2+temp-j):wordno
                            selection(k,1)=0;
                        end
                    end
                    flag=1;
                    break;
                end
            end
            if(flag==0)
                flagr=0;
                break;
            end
            if(selection==rel(:,index))
                continue;            
            end
            break;
        end
        if(flag==0)
            break;
        end           
    end
%    disp(count);
end
%dlmwrite('resultx.txt',x);