[Summary view]

   1  <?php
   2  
   3  namespace PhpOffice\PhpSpreadsheet\Calculation\LookupRef;
   4  
   5  use PhpOffice\PhpSpreadsheet\Calculation\Calculation;
   6  use PhpOffice\PhpSpreadsheet\Calculation\Exception;
   7  use PhpOffice\PhpSpreadsheet\Calculation\Functions;
   8  use PhpOffice\PhpSpreadsheet\Calculation\Information\ExcelError;
   9  use PhpOffice\PhpSpreadsheet\Cell\Coordinate;
  10  use PhpOffice\PhpSpreadsheet\Shared\StringHelper;
  11  
  12  class Sort extends LookupRefValidations
  13  {
  14      public const ORDER_ASCENDING = 1;
  15      public const ORDER_DESCENDING = -1;
  16  
  17      /**
  18       * SORT
  19       * The SORT function returns a sorted array of the elements in an array.
  20       * The returned array is the same shape as the provided array argument.
  21       * Both $sortIndex and $sortOrder can be arrays, to provide multi-level sorting.
  22       *
  23       * @param mixed $sortArray The range of cells being sorted
  24       * @param mixed $sortIndex The column or row number within the sortArray to sort on
  25       * @param mixed $sortOrder Flag indicating whether to sort ascending or descending
  26       *                          Ascending = 1 (self::ORDER_ASCENDING)
  27       *                          Descending = -1 (self::ORDER_DESCENDING)
  28       * @param mixed $byColumn Whether the sort should be determined by row (the default) or by column
  29       *
  30       * @return mixed The sorted values from the sort range
  31       */
  32      public static function sort($sortArray, $sortIndex = 1, $sortOrder = self::ORDER_ASCENDING, $byColumn = false)
  33      {
  34          if (!is_array($sortArray)) {
  35              // Scalars are always returned "as is"
  36              return $sortArray;
  37          }
  38  
  39          $sortArray = self::enumerateArrayKeys($sortArray);
  40  
  41          $byColumn = (bool) $byColumn;
  42          $lookupIndexSize = $byColumn ? count($sortArray) : count($sortArray[0]);
  43  
  44          try {
  45              // If $sortIndex and $sortOrder are scalars, then convert them into arrays
  46              if (is_scalar($sortIndex)) {
  47                  $sortIndex = [$sortIndex];
  48                  $sortOrder = is_scalar($sortOrder) ? [$sortOrder] : $sortOrder;
  49              }
  50              // but the values of those array arguments still need validation
  51              $sortOrder = (empty($sortOrder) ? [self::ORDER_ASCENDING] : $sortOrder);
  52              self::validateArrayArgumentsForSort($sortIndex, $sortOrder, $lookupIndexSize);
  53          } catch (Exception $e) {
  54              return $e->getMessage();
  55          }
  56  
  57          // We want a simple, enumrated array of arrays where we can reference column by its index number.
  58          $sortArray = array_values(array_map('array_values', $sortArray));
  59  
  60          return ($byColumn === true)
  61              ? self::sortByColumn($sortArray, $sortIndex, $sortOrder)
  62              : self::sortByRow($sortArray, $sortIndex, $sortOrder);
  63      }
  64  
  65      /**
  66       * SORTBY
  67       * The SORTBY function sorts the contents of a range or array based on the values in a corresponding range or array.
  68       * The returned array is the same shape as the provided array argument.
  69       * Both $sortIndex and $sortOrder can be arrays, to provide multi-level sorting.
  70       *
  71       * @param mixed $sortArray The range of cells being sorted
  72       * @param mixed $args
  73       *              At least one additional argument must be provided, The vector or range to sort on
  74       *              After that, arguments are passed as pairs:
  75       *                    sort order: ascending or descending
  76       *                         Ascending = 1 (self::ORDER_ASCENDING)
  77       *                         Descending = -1 (self::ORDER_DESCENDING)
  78       *                    additional arrays or ranges for multi-level sorting
  79       *
  80       * @return mixed The sorted values from the sort range
  81       */
  82      public static function sortBy($sortArray, ...$args)
  83      {
  84          if (!is_array($sortArray)) {
  85              // Scalars are always returned "as is"
  86              return $sortArray;
  87          }
  88  
  89          $sortArray = self::enumerateArrayKeys($sortArray);
  90  
  91          $lookupArraySize = count($sortArray);
  92          $argumentCount = count($args);
  93  
  94          try {
  95              $sortBy = $sortOrder = [];
  96              for ($i = 0; $i < $argumentCount; $i += 2) {
  97                  $sortBy[] = self::validateSortVector($args[$i], $lookupArraySize);
  98                  $sortOrder[] = self::validateSortOrder($args[$i + 1] ?? self::ORDER_ASCENDING);
  99              }
 100          } catch (Exception $e) {
 101              return $e->getMessage();
 102          }
 103  
 104          return self::processSortBy($sortArray, $sortBy, $sortOrder);
 105      }
 106  
 107      private static function enumerateArrayKeys(array $sortArray): array
 108      {
 109          array_walk(
 110              $sortArray,
 111              function (&$columns): void {
 112                  if (is_array($columns)) {
 113                      $columns = array_values($columns);
 114                  }
 115              }
 116          );
 117  
 118          return array_values($sortArray);
 119      }
 120  
 121      /**
 122       * @param mixed $sortIndex
 123       * @param mixed $sortOrder
 124       */
 125      private static function validateScalarArgumentsForSort(&$sortIndex, &$sortOrder, int $sortArraySize): void
 126      {
 127          if (is_array($sortIndex) || is_array($sortOrder)) {
 128              throw new Exception(ExcelError::VALUE());
 129          }
 130  
 131          $sortIndex = self::validatePositiveInt($sortIndex, false);
 132  
 133          if ($sortIndex > $sortArraySize) {
 134              throw new Exception(ExcelError::VALUE());
 135          }
 136  
 137          $sortOrder = self::validateSortOrder($sortOrder);
 138      }
 139  
 140      /**
 141       * @param mixed $sortVector
 142       */
 143      private static function validateSortVector($sortVector, int $sortArraySize): array
 144      {
 145          if (!is_array($sortVector)) {
 146              throw new Exception(ExcelError::VALUE());
 147          }
 148  
 149          // It doesn't matter if it's a row or a column vectors, it works either way
 150          $sortVector = Functions::flattenArray($sortVector);
 151          if (count($sortVector) !== $sortArraySize) {
 152              throw new Exception(ExcelError::VALUE());
 153          }
 154  
 155          return $sortVector;
 156      }
 157  
 158      /**
 159       * @param mixed $sortOrder
 160       */
 161      private static function validateSortOrder($sortOrder): int
 162      {
 163          $sortOrder = self::validateInt($sortOrder);
 164          if (($sortOrder == self::ORDER_ASCENDING || $sortOrder === self::ORDER_DESCENDING) === false) {
 165              throw new Exception(ExcelError::VALUE());
 166          }
 167  
 168          return $sortOrder;
 169      }
 170  
 171      /**
 172       * @param array $sortIndex
 173       * @param mixed $sortOrder
 174       */
 175      private static function validateArrayArgumentsForSort(&$sortIndex, &$sortOrder, int $sortArraySize): void
 176      {
 177          // It doesn't matter if they're row or column vectors, it works either way
 178          $sortIndex = Functions::flattenArray($sortIndex);
 179          $sortOrder = Functions::flattenArray($sortOrder);
 180  
 181          if (
 182              count($sortOrder) === 0 || count($sortOrder) > $sortArraySize ||
 183              (count($sortOrder) > count($sortIndex))
 184          ) {
 185              throw new Exception(ExcelError::VALUE());
 186          }
 187  
 188          if (count($sortIndex) > count($sortOrder)) {
 189              // If $sortOrder has fewer elements than $sortIndex, then the last order element is repeated.
 190              $sortOrder = array_merge(
 191                  $sortOrder,
 192                  array_fill(0, count($sortIndex) - count($sortOrder), array_pop($sortOrder))
 193              );
 194          }
 195  
 196          foreach ($sortIndex as $key => &$value) {
 197              self::validateScalarArgumentsForSort($value, $sortOrder[$key], $sortArraySize);
 198          }
 199      }
 200  
 201      private static function prepareSortVectorValues(array $sortVector): array
 202      {
 203          // Strings should be sorted case-insensitive; with booleans converted to locale-strings
 204          return array_map(
 205              function ($value) {
 206                  if (is_bool($value)) {
 207                      return ($value) ? Calculation::getTRUE() : Calculation::getFALSE();
 208                  } elseif (is_string($value)) {
 209                      return StringHelper::strToLower($value);
 210                  }
 211  
 212                  return $value;
 213              },
 214              $sortVector
 215          );
 216      }
 217  
 218      /**
 219       * @param array[] $sortIndex
 220       * @param int[] $sortOrder
 221       */
 222      private static function processSortBy(array $sortArray, array $sortIndex, $sortOrder): array
 223      {
 224          $sortArguments = [];
 225          $sortData = [];
 226          foreach ($sortIndex as $index => $sortValues) {
 227              $sortData[] = $sortValues;
 228              $sortArguments[] = self::prepareSortVectorValues($sortValues);
 229              $sortArguments[] = $sortOrder[$index] === self::ORDER_ASCENDING ? SORT_ASC : SORT_DESC;
 230          }
 231          $sortArguments = self::applyPHP7Patch($sortArray, $sortArguments);
 232  
 233          $sortVector = self::executeVectorSortQuery($sortData, $sortArguments);
 234  
 235          return self::sortLookupArrayFromVector($sortArray, $sortVector);
 236      }
 237  
 238      /**
 239       * @param int[] $sortIndex
 240       * @param int[] $sortOrder
 241       */
 242      private static function sortByRow(array $sortArray, array $sortIndex, array $sortOrder): array
 243      {
 244          $sortVector = self::buildVectorForSort($sortArray, $sortIndex, $sortOrder);
 245  
 246          return self::sortLookupArrayFromVector($sortArray, $sortVector);
 247      }
 248  
 249      /**
 250       * @param int[] $sortIndex
 251       * @param int[] $sortOrder
 252       */
 253      private static function sortByColumn(array $sortArray, array $sortIndex, array $sortOrder): array
 254      {
 255          $sortArray = Matrix::transpose($sortArray);
 256          $result = self::sortByRow($sortArray, $sortIndex, $sortOrder);
 257  
 258          return Matrix::transpose($result);
 259      }
 260  
 261      /**
 262       * @param int[] $sortIndex
 263       * @param int[] $sortOrder
 264       */
 265      private static function buildVectorForSort(array $sortArray, array $sortIndex, array $sortOrder): array
 266      {
 267          $sortArguments = [];
 268          $sortData = [];
 269          foreach ($sortIndex as $index => $sortIndexValue) {
 270              $sortValues = array_column($sortArray, $sortIndexValue - 1);
 271              $sortData[] = $sortValues;
 272              $sortArguments[] = self::prepareSortVectorValues($sortValues);
 273              $sortArguments[] = $sortOrder[$index] === self::ORDER_ASCENDING ? SORT_ASC : SORT_DESC;
 274          }
 275          $sortArguments = self::applyPHP7Patch($sortArray, $sortArguments);
 276  
 277          $sortData = self::executeVectorSortQuery($sortData, $sortArguments);
 278  
 279          return $sortData;
 280      }
 281  
 282      private static function executeVectorSortQuery(array $sortData, array $sortArguments): array
 283      {
 284          $sortData = Matrix::transpose($sortData);
 285  
 286          // We need to set an index that can be retained, as array_multisort doesn't maintain numeric keys.
 287          $sortDataIndexed = [];
 288          foreach ($sortData as $key => $value) {
 289              $sortDataIndexed[Coordinate::stringFromColumnIndex($key + 1)] = $value;
 290          }
 291          unset($sortData);
 292  
 293          $sortArguments[] = &$sortDataIndexed;
 294  
 295          array_multisort(...$sortArguments);
 296  
 297          // After the sort, we restore the numeric keys that will now be in the correct, sorted order
 298          $sortedData = [];
 299          foreach (array_keys($sortDataIndexed) as $key) {
 300              $sortedData[] = Coordinate::columnIndexFromString($key) - 1;
 301          }
 302  
 303          return $sortedData;
 304      }
 305  
 306      private static function sortLookupArrayFromVector(array $sortArray, array $sortVector): array
 307      {
 308          // Building a new array in the correct (sorted) order works; but may be memory heavy for larger arrays
 309          $sortedArray = [];
 310          foreach ($sortVector as $index) {
 311              $sortedArray[] = $sortArray[$index];
 312          }
 313  
 314          return $sortedArray;
 315  
 316  //        uksort(
 317  //            $lookupArray,
 318  //            function (int $a, int $b) use (array $sortVector) {
 319  //                return $sortVector[$a] <=> $sortVector[$b];
 320  //            }
 321  //        );
 322  //
 323  //        return $lookupArray;
 324      }
 325  
 326      /**
 327       * Hack to handle PHP 7:
 328       * From PHP 8.0.0, If two members compare as equal in a sort, they retain their original order;
 329       *      but prior to PHP 8.0.0, their relative order in the sorted array was undefined.
 330       * MS Excel replicates the PHP 8.0.0 behaviour, retaining the original order of matching elements.
 331       * To replicate that behaviour with PHP 7, we add an extra sort based on the row index.
 332       */
 333      private static function applyPHP7Patch(array $sortArray, array $sortArguments): array
 334      {
 335          if (PHP_VERSION_ID < 80000) {
 336              $sortArguments[] = range(1, count($sortArray));
 337              $sortArguments[] = SORT_ASC;
 338          }
 339  
 340          return $sortArguments;
 341      }
 342  }