function [bins, edges] = discretize(x, edges, varargin)
%DISCRETIZE   Group numeric data into bins or categories.
%   BINS = DISCRETIZE(X,EDGES) returns the indices of the bins that the 
%   elements of X fall into.  EDGES is a numeric vector that contains bin 
%   edges in monotonically increasing order. An element X(i) falls into 
%   the j-th bin if EDGES(j) <= X(i) < EDGES(j+1), for 1 <= j < N where 
%   N is the number of bins and length(EDGES) = N+1. The last bin includes 
%   the right edge such that it contains EDGES(N) <= X(i) <= EDGES(N+1). For 
%   out-of-range values where X(i) < EDGES(1) or X(i) > EDGES(N+1) or 
%   isnan(X(i)), BINS(i) returns NaN.
%
%   [BINS, EDGES] = DISCRETIZE(X,N) where N is a scalar integer, divides the
%   range of X into N uniform bins, and also returns the bin edges.
%
%   [BINS, EDGES] = DISCRETIZE(...,VALUES) returns the corresponding 
%   element in VALUES, rather than the bin number. For example, if X(1) 
%   falls into bin 5 then BINS(1) would be VALUES(5) rather than 5. VALUES 
%   must be a vector with length equal to the number of bins. Out-of-range 
%   inputs return NaN. 
%
%   [C, EDGES] = DISCRETIZE(...,'categorical') creates a categorical array from 
%   the binned result of X. C will have the same number of categories 
%   as the number of bins. The category names will be in the form of 
%   "[A,B)", or "[A,B]" for the last bin, where A and B are consecutive 
%   values from EDGES. Out-of-range values will be undefined in C.
%
%   [C, EDGES] = DISCRETIZE(...,'categorical',CATEGORYNAMES) additionally 
%   specifies names for the categories in C using CATEGORYNAMES.  
%   CATEGORYNAMES is a cell array of character vectors and has
%   length equal to the number of bins.  
%
%   [...] = DISCRETIZE(...,'IncludedEdge',SIDE) specifies which bin edge is 
%   included in the bins. SIDE can be:
%       'left'    Each bin includes the left bin edge, except for the last bin
%                 which includes both bin edges. This is the default.
%       'right'   Each bin includes the right bin edge, except for the first 
%                 bin which includes both bin edges.
%   If SIDE is 'right', an element X(i) falls into the j-th bin if
%   EDGES(j) < X(i) <= EDGES(j+1), for 1 < j <= N where N is the number
%   of bins. The first bin includes the left edge such that it contains 
%   EDGES(1) <= X(i) <= EDGES(2).
%
%   Class support for inputs X, EDGES:
%      float: double, single
%      integers: uint8, int8, uint16, int16, uint32, int32, uint64, int64
%      logical
%
%   Example:
%      x = rand(10,1);
%      bins = discretize(x,0:0.25:1);  % group into 4 bins 
%
%   See also HISTCOUNTS, HISTOGRAM, CATEGORICAL

%   Copyright 1984-2019 The MathWorks, Inc.

nin = nargin;

if ~(isnumeric(x) || islogical(x)) || ~isreal(x)
    error(message('MATLAB:discretize:invalidType'));
end

if ~(isnumeric(edges) || islogical(edges)) || ~isvector(edges) || ~isreal(edges) ...
        || ~issorted(edges) || any(isnan(edges)) % nondecreasing check
    if isscalar(edges)
        error(message('MATLAB:discretize:InvalidN'));
    else
        error(message('MATLAB:discretize:InvalidSecondInput'));
    end
end

if isscalar(edges)
    numbins = double(edges);
    if floor(numbins) ~= numbins || numbins < 1 || ~isfinite(numbins) 
        error(message('MATLAB:discretize:InvalidN'));
    end
    xfinite = x(isfinite(x));
    xmin = min(xfinite);
    xmax = max(xfinite);
    xrange = xmax - xmin;
    edges = matlab.internal.math.binpicker(xmin,xmax,numbins,...
        xrange/numbins);
elseif isempty(edges)
    error(message('MATLAB:discretize:EmptyOrScalarEdges'));
end

% make sure edges are non-sparse, handle subclass of builtin class
if isobject(x)
    x = matlab.internal.language.castToBuiltinSuperclass(x);
end
if isobject(edges)
    edges = matlab.internal.language.castToBuiltinSuperclass(edges);
end
edges = full(edges);
nbins = length(edges)-1;
    
if nin > 2 && checkCharString(varargin{1}) && startsWith("categorical",varargin{1},'IgnoreCase',true)
    % create categorical output
    catnames_provided = false;
    right = false;
    if nin > 3
        idx = 2;
        % Convert scalar string to char in certain cases to distinguish
        % IncludedEdge NV pair from catnames
        if isstring(varargin{idx}) && isscalar(varargin{idx})
            if nbins ~= 1
                % catnames is not scalar, treat as NV-pair
                varargin{idx} = char(varargin{idx});
            elseif strcmpi("IncludedEdge",varargin{idx})
                % exact match, treat as NV-pair
                varargin{idx} = char(varargin{idx});
            end
        end
        
        % Parse catnames input
        if (iscellstr(varargin{idx}) || isstring(varargin{idx})) && isvector(varargin{idx})
            catnames_provided = true;
            catnames = varargin{idx};
            idx = idx+1;
            if length(catnames) ~= nbins
                error(message('MATLAB:discretize:CategoryNamesInvalidSize',nbins));
            end
        end
        
        % Parse NV pair
        if rem(nargin-idx+1,2) == 0
            right = parseNVpair(varargin, right, idx);
        elseif catnames_provided
            error(message('MATLAB:discretize:KeyWithoutValue'));
        else
            error(message('MATLAB:discretize:InvalidCatnames'));
        end
    end
    
    if ~catnames_provided
        catnames = matlab.internal.datatypes.numericBinEdgesToCategoryNames(edges,right);
    end
    
    bins = matlab.internal.math.discretize(x, edges, right);
    
    bins = categorical(bins, 1:nbins, catnames, 'Ordinal', true);
else
    % create numerical output
    values_provided = false;
    right = false;
    if nin > 2
        idx = 1;
        % Parse values
        if isvector(varargin{idx}) && ~isempty(varargin{idx}) && ...
                ~ischar(varargin{idx}) && ~(isstring(varargin{idx}) && isscalar(varargin{idx})) ...
                && ~isa(varargin{idx},'function_handle')
            values_provided = true;
            values = varargin{idx};
            idx = idx+1;
            if length(values) ~= nbins
                error(message('MATLAB:discretize:ValuesInvalidSize',nbins));
            end
        end
        
        % Parse NV pair
        if rem(nargin-idx+1,2) == 0
            right = parseNVpair(varargin, right, idx);
        elseif values_provided
            error(message('MATLAB:discretize:KeyWithoutValue'));
        else
            error(message('MATLAB:discretize:InvalidValues'));
        end
    end
    
    bins = matlab.internal.math.discretize(x, edges, right);
    if values_provided
        nanbins = isnan(bins);
        if any(nanbins(:))
            try
                values(end+1) = NaN;
            catch
                error(message('MATLAB:discretize:ValuesClassNoNaN',class(values)));
            end
            bins(nanbins) = length(values);
        end
        % reshape needed when x and values are vectors of different orientation
        bins = reshape(values(bins),size(x));
    end
    
end

end

function flag = checkCharString(inputName)
flag = (ischar(inputName) && isrow(inputName)) || (isstring(inputName) && isscalar(inputName) ...
    && strlength(inputName) ~= 0);
end

function right = parseNVpair(nvpairs, right, idx)
% Parse 'IncludedEdge'
for j = idx:2:length(nvpairs)
    name = nvpairs{j};
    if ~checkCharString(name)
        error(message('MATLAB:discretize:ParseFlags'));
    elseif startsWith("IncludedEdge",name,'IgnoreCase',true)
        if checkCharString(nvpairs{j+1})
            if startsWith("right",nvpairs{j+1},'IgnoreCase',true)
                right = true;
            elseif startsWith("left",nvpairs{j+1},'IgnoreCase',true)
                right = false;
            else
                error(message('MATLAB:discretize:InvalidIncludedEdgeValue'));
            end
        else
            error(message('MATLAB:discretize:InvalidIncludedEdgeValue'));
        end
    else
        error(message('MATLAB:discretize:ParseFlags'));
    end
end
end