R/altrep_backend-sort.R

In charr: String Processing Reimagined for 'ALTREP' Strings

# Copied from stringi; stri_* renamed to ci_*.
# kate: default-dictionary en_US

## This file is part of the 'stringi' package for R.
## Copyright (c) 2013-2025, Marek Gagolewski <https://www.gagolewski.com/>
## All rights reserved.
##
## Redistribution and use in source and binary forms, with or without
## modification, are permitted provided that the following conditions are met:
##
## 1. Redistributions of source code must retain the above copyright notice,
## this list of conditions and the following disclaimer.
##
## 2. Redistributions in binary form must reproduce the above copyright notice,
## this list of conditions and the following disclaimer in the documentation
## and/or other materials provided with the distribution.
##
## 3. Neither the name of the copyright holder nor the names of its
## contributors may be used to endorse or promote products derived from
## this software without specific prior written permission.
##
## THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
## 'AS IS' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
## BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
## FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
## HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
## SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
## PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
## OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
## WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
## OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
## EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


# @title String Sorting
#
# @description
# This function sorts a character vector according to a locale-dependent
# lexicographic order.
#
# @details
# For more information on \pkg{ICU}'s Collator and how to tune it up
# in \pkg{stringi}, refer to \code{\link{ci_opts_collator}}.
#
# As usual in \pkg{stringi}, non-character inputs are coerced to strings,
# see an example below for a somewhat non-intuitive behavior of lexicographic
# sorting on numeric inputs.
#
# This function uses a stable sort algorithm (\pkg{STL}'s \code{stable_sort}),
# which performs up to \eqn{N*log^2(N)} element comparisons,
# where \eqn{N} is the length of \code{str}.
#
# @param str a character vector
# @param decreasing a single logical value; should the sort order
#    be nondecreasing (\code{FALSE}, default, i.e., weakly increasing)
#    or nonincreasing (\code{TRUE})?
# @param na_last a single logical value; controls the treatment of \code{NA}s
#    in \code{str}. If \code{TRUE}, then missing values in \code{str} are put
#    at the end; if \code{FALSE}, they are put at the beginning;
#    if \code{NA}, then they are removed from the output
# @param opts_collator a named list with \pkg{ICU} Collator's options,
# see \code{\link{ci_opts_collator}}, \code{NULL}
# for default collation options
# @param ... additional settings for \code{opts_collator}
#
# @return
# The result is a sorted version of \code{str},
# i.e., a character vector.
#
# @references
# \emph{Collation} - ICU User Guide,
# \url{https://unicode-org.github.io/icu/userguide/collation/}
#
# @family locale_sensitive
# @export
# @rdname ci_sort
#
# @examples
# ci_sort(c('hladny', 'chladny'), locale='pl_PL')
# ci_sort(c('hladny', 'chladny'), locale='sk_SK')
# ci_sort(sample(LETTERS))
# ci_sort(c(1, 100, 2, 101, 11, 10))  # lexicographic order
# ci_sort(c(1, 100, 2, 101, 11, 10), numeric=TRUE)  # OK for integers
# ci_sort(c(0.25, 0.5, 1, -1, -2, -3), numeric=TRUE)  # incorrect


# @title Ordering Permutation
#
# @description
# This function finds a permutation which rearranges the
# strings in a given character vector into the ascending or descending
# locale-dependent lexicographic order.
#
# @details
# For more information on \pkg{ICU}'s Collator and how to tune it up
# in \pkg{stringi}, refer to \code{\link{ci_opts_collator}}.
#
# As usual in \pkg{stringi}, non-character inputs are coerced to strings,
# see an example below for a somewhat non-intuitive behavior of lexicographic
# sorting on numeric inputs.
#
# This function uses a stable sort algorithm (\pkg{STL}'s \code{stable_sort}),
# which performs up to \eqn{N*log^2(N)} element comparisons,
# where \eqn{N} is the length of \code{str}.
#
# For ordering with regards to multiple criteria (such as sorting
# data frames by more than 1 column), see \code{\link{ci_rank}}.
#
# @param str a character vector
# @param decreasing a single logical value; should the sort order
#    be nondecreasing (\code{FALSE}, default)
#    or nonincreasing (\code{TRUE})?
# @param na_last a single logical value; controls the treatment of \code{NA}s
#    in \code{str}. If \code{TRUE}, then missing values in \code{str} are put
#    at the end; if \code{FALSE}, they are put at the beginning;
#    if \code{NA}, then they are removed from the output
# @param opts_collator a named list with \pkg{ICU} Collator's options,
# see \code{\link{ci_opts_collator}}, \code{NULL}
# for default collation options
# @param ... additional settings for \code{opts_collator}
#
# @return The function yields an integer vector that gives the sort order.
#
# @references
# \emph{Collation} - ICU User Guide,
# \url{https://unicode-org.github.io/icu/userguide/collation/}
#
# @family locale_sensitive
# @export
# @rdname ci_order
#
# @examples
# ci_order(c('hladny', 'chladny'), locale='pl_PL')
# ci_order(c('hladny', 'chladny'), locale='sk_SK')
#
# ci_order(c(1, 100, 2, 101, 11, 10))  # lexicographic order
# ci_order(c(1, 100, 2, 101, 11, 10), numeric=TRUE)  # OK for integers
# ci_order(c(0.25, 0.5, 1, -1, -2, -3), numeric=TRUE)  # incorrect
ci_order <- function(str, decreasing = FALSE, na_last = TRUE, ..., opts_collator = NULL)
{
    if (!missing(...))
        opts_collator <- do.call(ci_opts_collator, as.list(c(opts_collator, ...)))
    .Call(C_ci_order, str, decreasing, na_last, opts_collator)
}


# @title Extract Unique Elements
#
# @description
# This function returns a character vector like \code{str},
# but with duplicate elements removed.
#
# @details
# As usual in \pkg{stringi}, no attributes are copied.
# Unlike \code{\link{unique}}, this function
# tests for canonical equivalence of strings (and not
# whether the strings are just bytewise equal). Such an operation
# is locale-dependent. Hence, \code{ci_unique} is significantly
# slower (but much better suited for natural language processing)
# than its base R counterpart.
#
# See also \code{\link{ci_duplicated}} for indicating non-unique elements.
#
# @param str a character vector
# @param opts_collator a named list with \pkg{ICU} Collator's options,
# see \code{\link{ci_opts_collator}}, \code{NULL}
# for default collation options
# @param ... additional settings for \code{opts_collator}
#
# @return Returns a character vector.
#
# @examples
# # normalized and non-Unicode-normalized version of the same code point:
# ci_unique(c('\u0105', ci_trans_nfkd('\u0105')))
# unique(c('\u0105', ci_trans_nfkd('\u0105')))
#
# ci_unique(c('gro\u00df', 'GROSS', 'Gro\u00df', 'Gross'), strength=1)
#
# @references
# \emph{Collation} - ICU User Guide,
# \url{https://unicode-org.github.io/icu/userguide/collation/}
#
# @family locale_sensitive
# @export


# @title
# Determine Duplicated Elements
#
# @description
# \code{ci_duplicated()} determines which strings in a character vector
# are duplicates of other elements.
#
# \code{ci_duplicated_any()} determines if there are any duplicated
# strings in a character vector.
#
# @details
# Missing values are regarded as equal.
#
# Unlike \code{\link{duplicated}} and \code{\link{anyDuplicated}},
# these functions test for canonical equivalence of strings
# (and not whether the strings are just bytewise equal)
# Such operations are locale-dependent.
# Hence, \code{ci_duplicated} and \code{ci_duplicated_any}
# are significantly slower (but much better suited for natural language
# processing) than their base R counterparts.
#
# See also \code{\link{ci_unique}} for extracting unique elements.
#
# @param str a character vector
# @param from_last a single logical value;
#    indicates whether search should be performed from the last to the
#    first string
# @param fromLast [DEPRECATED] alias of \code{from_last}
# @param opts_collator a named list with \pkg{ICU} Collator's options,
# see \code{\link{ci_opts_collator}}, \code{NULL}
# for default collation options
# @param ... additional settings for \code{opts_collator}
#
# @return
# \code{ci_duplicated()} returns a logical vector of the same length
# as \code{str}. Each of its elements indicates whether a canonically
# equivalent string was already found in \code{str}.
#
# \code{ci_duplicated_any()} returns a single non-negative integer.
# Value of 0 indicates that all the elements in \code{str} are unique.
# Otherwise, it gives the index of the first non-unique element.
#
# @references
# \emph{Collation} - ICU User Guide,
# \url{https://unicode-org.github.io/icu/userguide/collation/}
#
# @examples
# # In the following examples, we have 3 duplicated values,
# # 'a' - 2 times, NA - 1 time
# ci_duplicated(c('a', 'b', 'a', NA, 'a', NA))
# ci_duplicated(c('a', 'b', 'a', NA, 'a', NA), from_last=TRUE)
# ci_duplicated_any(c('a', 'b', 'a', NA, 'a', NA))
#
# # compare the results:
# ci_duplicated(c('\u0105', ci_trans_nfkd('\u0105')))
# duplicated(c('\u0105', ci_trans_nfkd('\u0105')))
#
# ci_duplicated(c('gro\u00df', 'GROSS', 'Gro\u00df', 'Gross'), strength=1)
# duplicated(c('gro\u00df', 'GROSS', 'Gro\u00df', 'Gross'))
#
# @rdname ci_duplicated
# @family locale_sensitive
# @export
ci_duplicated <- function(str, from_last = FALSE,
    fromLast = from_last, ..., opts_collator = NULL) {
    if (!missing(fromLast)) {
        warning("The 'fromLast' argument in ci_duplicated is a deprecated alias of 'from_last' and will be removed in a future release of 'stringi'.")
        from_last <- fromLast
    }
    if (!missing(...))
        opts_collator <- do.call(ci_opts_collator, as.list(c(opts_collator, ...)))
    .Call(C_ci_duplicated, str, from_last, opts_collator)
}


# @rdname ci_duplicated
# @export


# @title
# Sort Keys
#
# @description
# This function computes a locale-dependent sort key, which is an alternative
# character representation of the string that, when ordered in the C locale
# (which orders using the underlying bytes directly), will give an equivalent
# ordering to the original string. It is useful for enhancing algorithms
# that sort only in the C locale (e.g., the \code{strcmp} function in libc)
# with the ability to be locale-aware.
#
# @details
# For more information on \pkg{ICU}'s Collator and how to tune it up
# in \pkg{stringi}, refer to \code{\link{ci_opts_collator}}.
#
# See also \code{\link{ci_rank}} for ranking strings with a single character
# vector, i.e., generating relative sort keys.
#
# @param str a character vector
# @param opts_collator a named list with \pkg{ICU} Collator's options,
# see \code{\link{ci_opts_collator}}, \code{NULL}
# for default collation options
# @param ... additional settings for \code{opts_collator}
#
# @return
# The result is a character vector with the same length as \code{str} that
# contains the sort keys. The output is marked as \code{bytes}-encoded.
#
# @references
# \emph{Collation} - ICU User Guide,
# \url{https://unicode-org.github.io/icu/userguide/collation/}
#
# @examples
# ci_sort_key(c('hladny', 'chladny'), locale='pl_PL')
# ci_sort_key(c('hladny', 'chladny'), locale='sk_SK')
#
# @family locale_sensitive
# @export
# @rdname ci_sort_key



# @title
# Ranking
#
# @description
# This function ranks each string in a character vector according to a
# locale-dependent lexicographic order.
# It is a portable replacement for the base \code{xtfrm} function.
#
# @details
# Missing values result in missing ranks and tied observations receive
# the same ranks (based on min).
#
# For more information on \pkg{ICU}'s Collator and how to tune it up
# in \pkg{stringi}, refer to \code{\link{ci_opts_collator}}.
#
# @param str a character vector
# @param opts_collator a named list with \pkg{ICU} Collator's options,
# see \code{\link{ci_opts_collator}}, \code{NULL}
# for default collation options
# @param ... additional settings for \code{opts_collator}
#
# @return
# The result is a vector of ranks corresponding to each
# string in \code{str}.
#
# @references
# \emph{Collation} -- ICU User Guide,
# \url{https://unicode-org.github.io/icu/userguide/collation/}
#
# @examples
# ci_rank(c('hladny', 'chladny'), locale='pl_PL')
# ci_rank(c('hladny', 'chladny'), locale='sk_SK')
#
# ci_rank("a" %s+% c(1, 100, 2, 101, 11, 10))  # lexicographic order
# ci_rank("a" %s+% c(1, 100, 2, 101, 11, 10), numeric=TRUE)  # OK
# ci_rank("a" %s+% c(0.25, 0.5, 1, -1, -2, -3), numeric=TRUE)  # incorrect
#
# # Ordering a data frame with respect to two criteria:
# X <- data.frame(a=c("b", NA, "b", "b", NA, "a", "a", "c"), b=runif(8))
# X[order(ci_rank(X$a), X$b), ]
#
# @family locale_sensitive
# @export
# @rdname ci_rank
ci_rank <- function(str, ..., opts_collator=NULL)
{
    if (!missing(...))
        opts_collator <- do.call(ci_opts_collator, as.list(c(opts_collator, ...)))

    .Call(C_ci_rank, str, opts_collator)
}