function [cycles]=addcombination(cycles);
% [ cycles ] = addcombination( cycles );
% Constructs short products whose product is the identity from long products whos product is the identity.
% Longer explanation:   Assume the product of matrices AB and BAB have the same eigenvector v1 to the eigenvalue 1.
%                       Then ABv = v and ABAv=v. This implies that Bv=v, thus Av=v, thus BAv=v. 
%                       The function thus returns: A, B, AB, ABA, BA.
% Input:
%   cycles      (cell array of vectors) vectors of numbers which define cycles for the same eigenvector
%
% Output:
%   cycles      longer list of numbers which define a cycle
%
% E.g.: addcombination({[1 1 2],[1]})
%
% See also: removecombination
%
% Written by: tommsch, 2018


    if(length(cycles)==1); return; end; %trivial case %length_m

    testelement=2;
    while(true)
        oo=cycles{testelement};
        for j=1:testelement-1;

            [o, or] = comparebegin(oo,cycles{j});
            if(isempty(o)); continue; end;
            if(searchincellarray(or,cycles,1)); 
                continue; 
            else
                cycles{end+1}=or; %#ok<AGROW>          
            end;

        end
        testelement=testelement+1;
        if(testelement>length(cycles)); break; end; %length_m
    end

end

function [o, or] = comparebegin(o1,o2)
%  compares if one of the orderings is the same as the beginning of the other ordering
%   o       the part at the beginning which is the same (thus equals either o1 or o2)
%           o is empty, if o1 and o2 are not compareable.
%   or      the rest of the ordering, where o is removed.
% Eg [o, or] = comparebegin([1 2 3],[1 2]) % o = [1 2]; or = [ 3 ];
if(length(o1)>length(o2));  %length_m
    [o1,o2]=swap(o1,o2); 
end;
if(isequal(o1,o2(1:length(o1)))); %length_m
    o = o1;
    or = o2(length(o1)+1:end); %length_m
else
    o=[];
    or=[];
end
end

function cycles=addcombination_old(varargin); %#ok<DEFNU>
% Is much slower and has no progress bar.
% oclass=addcombination(cycles, [options]);
% Tries to find shorter cycles which lead back to the starting point.
% Longer explanation:   Assume the product of matrices AB and BAB have the same eigenvector v1 to the eigenvalue 1.
%                       Then ABv = v and ABAv=v. This implies that Bv=v, thus Av=v, thus BAv=v. 
%                       The function thus returns: A, B, AB, ABA, BA.
% Input:
%   cycles      (cell array of vectors) vectors of numbers which define cycles for the same eigenvector
% 
% Options
%   'verbose',val       Verbose level
%
% Output:
%   cycles      longer list of numbers which define a cycle
%
% Eg: addcombination({[1 1 2],[1]})



cycles=varargin{1};
verbose=parsem('verbose',varargin,0);

sizeoclass=size(cycles,2);
for j=1:sizeoclass;
    if(verbose>=1); fprintf('|'); end;
    for k=1:sizeoclass;
        if(k==j); continue; end;
        if(length(cycles{j})>length(cycles{k})); kk=j; jj=k; else; kk=k; jj=j; end; %swap indices if oo is longer then ooo

        oo=cycles{jj}; %orderings to be compared for
        ooo=cycles{kk}; %ooo is the longer ordering of the two

        ll=length(oo);
        lll=length(ooo);
        if(ll==lll); continue; end;

        newo=cycles{kk}(ll+1:end); %the ordering which shall be added
        found=isequal(oo,ooo(1:ll));
        contained=searchincellarray(newo,cycles,1);
        if(found && contained && ll<lll);
            if(verbose>=2); fprintf('Remove %i:\n',kk); disp(cycles); end;
            cycles{kk}=newo;
            if(~searchincellarray(ooo,cycles,1)); 
                cycles{end+1}=ooo;  %#ok<AGROW>
            end; %if the old ordering is not present anymore, add it to the end
            
        elseif(found && ~contained);
            if(verbose>=2); fprintf('Add %i:\n',kk); disp(cycles); end;
            cycles{kk}=newo;
            cycles{end+1}=ooo;  %#ok<AGROW> %add the new ordering
            if(verbose>=2); fprintf('%i:\n',size(cycles,2)); disp(cycles); end;
            cycles=addcombination(cycles,'verbose',verbose);  %and start the algorithm again
            return;
        end
    end
end

if(verbose>=1); fprintf(' Simplify output.\n'); end;
cycles=uniquecell(cycles);
if(verbose>=2); cycles, end; %#ok<NOPRT>

end

function [y,x]=swap(x,y)
end

function dummy; end %#ok<DEFNU> %Generates an error, if the 'end' of a function is missing.   