hphp/hsl/src/c/order.php

   1 <?hh
   2
   3 /*
   4  *  Copyright (c) 2004-present, Facebook, Inc.
   5  *  All rights reserved.
   6  *
   7  *  This source code is licensed under the MIT license found in the
   8  *  LICENSE file in the hphp/hsl/ subdirectory of this source tree.
   9  *
  10  */
  11
  12 namespace HH\Lib\C;
  13
  14 use namespace HH\Lib\Vec;
  15
  16 /**
  17  * Returns true if the given Traversable<Tv> is sorted in ascending order.
  18  * If two neighbouring elements compare equal, this will be considered sorted.
  19  *
  20  * If no $comparator is provided, the `<=>` operator will be used.
  21  * This will sort numbers by value, strings by alphabetical order
  22  * or by the numeric value, if the strings are well-formed numbers,
  23  * and DateTime/DateTimeImmutable by their unixtime. If the comparison
  24  * operator `<=>` is not useful on Tv and no $comparator is provided,
  25  * the result of is_sorted will not be useful.
  26  *
  27  * When specified, a comparator should exhibit the same behavior as the `<=>`
  28  * operator: a negative value when the left operand compares less than the
  29  * right operand, 0 when the operands compare equal, and a positive value when
  30  * the left operand compares greater than the right operand.
  31  *
  32  * To check the order of other types or mixtures of the
  33  * aforementioned types, see C\is_sorted_by.
  34  *
  35  * Time complexity: O((n * c), where c is the complexity of the
  36  * comparator function (which is O(1) if not provided explicitly)
  37  * Space complexity: O(n)
  38  */
  39 function is_sorted<Tv>(
  40   Traversable<Tv> $traversable,
  41   ?(function(Tv, Tv)[_]: num) $comparator = null,
  42 )[ctx $comparator]: bool {
  43   $vec = Vec\cast_clear_legacy_array_mark($traversable);
  44   if (is_empty($vec)) {
  45     return true;
  46   }
  47
  48   $comparator ??= (Tv $a, Tv $b) ==>
  49     /*HH_FIXME[4240] Comparison may not be useful on Tv*/$a <=> $b;
  50
  51   $previous = firstx($vec);
  52   foreach ($vec as $next) {
  53     if ($comparator($next, $previous) < 0) {
  54       return false;
  55     }
  56     $previous = $next;
  57   }
  58
  59   return true;
  60 }
  61
  62 /**
  63  * Returns true if the given Traversable<Tv> would be sorted in ascending order
  64  * after having been `Vec\map`ed with $scalar_func sorted in ascending order.
  65  * If two neighbouring elements compare equal, this will be considered sorted.
  66  *
  67  * If no $comparator is provided, the `<=>` operator will be used.
  68  * This will sort numbers by value, strings by alphabetical order
  69  * or by the numeric value, if the strings are well-formed numbers,
  70  * and DateTime/DateTimeImmutable by their unixtime. If the comparison
  71  * operator `<=>` is not useful on Ts and no $comparator is provided, the
  72  * result of is_sorted_by will not be useful.
  73  *
  74  * When specified, a comparator should exhibit the same behavior as the `<=>`
  75  * operator: a negative value when the left operand compares less than the
  76  * right operand, 0 when the operands compare equal, and a positive value when
  77  * the left operand compares greater than the right operand.
  78  *
  79  * To check the order without a mapping function,
  80  * see `C\is_sorted`.
  81  *
  82  * Time complexity: O((n * c), where c is the complexity of the
  83  * comparator function (which is O(1) if not provided explicitly)
  84  * Space complexity: O(n)
  85  */
  86 function is_sorted_by<Tv, Ts>(
  87   Traversable<Tv> $traversable,
  88   (function(Tv)[_]: Ts) $scalar_func,
  89   ?(function(Ts, Ts)[_]: num) $comparator = null,
  90 )[ctx $scalar_func, ctx $comparator]: bool {
  91   $vec = Vec\cast_clear_legacy_array_mark($traversable);
  92   if (is_empty($vec)) {
  93     return true;
  94   }
  95
  96   $comparator ??= (Ts $a, Ts $b) ==>
  97     /*HH_FIXME[4240] Comparison may not be useful on Ts*/$a <=> $b;
  98
  99   $previous = $scalar_func(firstx($vec));
 100   foreach ($vec as $next) {
 101     $next = $scalar_func($next);
 102     if ($comparator($next, $previous) < 0) {
 103       return false;
 104     }
 105     $previous = $next;
 106   }
 107
 108   return true;
 109 }