function y = KM(xPoint,wLower,wUpper,maxFlag)

%
% y = KM(xPoint,wLower,wUpper,maxFlag)
%
% function to implement the KM algorithms:
%
% N. N. Karnik and Jerry M. Mendel, "Centroid of a Type-2 Fuzzy Set,"
% Information Sciences, vol. 132, pp. 195-220, 2001.
%
% J. M. Mendel and Dongrui Wu, Perceptual Computing: Aiding People in Making Subjective Judgments, 
% Wiley-IEEE Press, 2010.
%
% Last modified by Dongrui WU (dongruiw@usc.edu), 7/29/2009
%
% xPoint: x_i
% [wLower, wUpper]: range of w_i
% maxFlag: 1, if to output the maximum; -1, if to output the minimum
% xPoint, wLower and wUpper must have the same length.

if max(wUpper)==0 | max(xPoint)==0
    y=0; return
end

if max(wLower)==0
    if maxFlag>0
        y=max(xPoint);
    else
        y=min(xPoint);
    end
    return;
end

if length(xPoint)==1
    y=xPoint;
    return;
end

% combine zero firing intervals
I=find(wUpper==0);
xPoint(I)=[];
wLower(I)=[];
wUpper(I)=[];

% combine zero xs
[xSort,xIndex] = sort(xPoint);
lowerSort = wLower(xIndex);
upperSort = wUpper(xIndex);
k=find(xSort==0,1,'last');
if k>1
    xSort(1)=0;
    xSort(2:k)=[];
    lowerSort(1)=sum(lowerSort(1:k));
    lowerSort(2:k)=[];
    upperSort(1)=sum(upperSort(1:k));
    upperSort(2:k)=[];
end

% initialization
ly=length(xSort);
hl = (lowerSort+upperSort)/2;
y = sum(xSort.*hl)/sum(hl);
yOld=y+0.1;

while y-yOld
    yOld = y;
    k = find(xSort > y,1)-1;

    if maxFlag < 0
        theta(1:k) = upperSort(1:k);
        theta(k+1:ly) = lowerSort(k+1:ly);
    else
        theta(1:k) = lowerSort(1:k);
        theta(k+1:ly)= upperSort(k+1:ly);
    end
    y = sum(xSort.*theta)/sum(theta);
end

