function [F,NoC,NoF] = ENS_SS (Population)
% Efficient non-dominated sort on sequential search strategy, TEVC, 2014,
% Xingyi Zhang, Ye Tian, Ran Cheng and Yaochu Jin
% Copyright 2014 BCMA Group, Written by Ye Tian
%
% Input: 
%        Population: a N-by-M matrix, which stands for the population on
%                    objective space, each row of Y stands for one solution, 
%                    and each column stands for one dimension
% Output:         
%                 F: the set of fronts, each vector F{i} contains all the
%                    NO. of solutions belonging to front i
%               NoC: number of total comparisons
%               NoF: number of total fronts

    NoC = 0;                    % Number of Comparisons
    [N,M] = size(Population);   % N = population size, M = number of objectives
    F = cell(N,1);              % the set of fronts
    NoF = 0;                    % Number of fronts
    % sort the population in ascending order according to the first
    % objective value, if two solutions have the same value on the first
    % objective value, sort them according to the second objective value
    [~,rank] = sortrows(Population);
    % assign the first solution to the first front
    F{1} = rank(1);
    NoF = NoF + 1;
    % for each solution in the sorted population, do sequential search
    for i = 2:N
        k = 1;	% the front now checked
        while 1
            % compare Population(rank(i)) with the solutions in F{k}
            % starting from the last one and ending with the first one
            for j = size(F{k},2):-1:1
                % do non-dominated comparison
                % x = 0 means the two solutions are non-dominated
                % x = 1 means the former one dominating the latter one (but this won't happen)
                % x = 2 means the latter one dominating the former one
                x=2;
                for j2 = 2:M
                    if Population(rank(i),j2) < Population(F{k}(j),j2)
                        x = 0;
                        break;
                    end
                end
                NoC = NoC + 1;
                if x == 2 || M == 2
                    break;
                end
            end
            if x ~= 2   % if F{k} has no solution dominating Population(rank(i))
                F{k} = [F{k},rank(i)];	% move Population(rank(i)) to F{k}
                break;
            else        % if F{k} has at least one soultion dominating Population(rank(i))
                if k < NoF
                    k = k + 1;
                else
                    NoF = NoF + 1;
                    F{NoF} = rank(i);	% move Population(rank(i)) to F{NoF+1}
                    break;
                end
            end
        end
    end
end

