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 root directory 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.
  24  *
  25  * To check the order of other types or mixtures of the
  26  * aforementioned types, see C\is_sorted_by.
  27  *
  28  * If the comparison operator `<=>` is not useful on Tv
  29  * and no $comparator is provided, the result of is_sorted
  30  * will not be useful.
  31  *
  32  * Time complexity: O((n * c), where c is the complexity of the
  33  * comparator function (which is O(1) if not provided explicitly)
  34  * Space complexity: O(n)
  35  */
  36 function is_sorted<Tv>(
  37   Traversable<Tv> $traversable,
  38   ?(function(Tv, Tv)[_]: num) $comparator = null,
  39 )[ctx $comparator]: bool {
  40   $vec = Vec\cast_clear_legacy_array_mark($traversable);
  41   if (is_empty($vec)) {
  42     return true;
  43   }
  44
  45   $comparator ??= (Tv $a, Tv $b) ==>
  46     /*HH_FIXME[4240] Comparison may not be useful on Tv*/$a <=> $b;
  47
  48   $previous = firstx($vec);
  49   foreach ($vec as $next) {
  50     if ($comparator($next, $previous) < 0) {
  51       return false;
  52     }
  53     $previous = $next;
  54   }
  55
  56   return true;
  57 }
  58
  59 /**
  60  * Returns true if the given Traversable<Tv> would be sorted in ascending order
  61  * after having been `Vec\map`ed with $scalar_func sorted in ascending order.
  62  * If two neighbouring elements compare equal, this will be considered sorted.
  63  *
  64  * If no $comparator is provided, the `<=>` operator will be used.
  65  * This will sort numbers by value, strings by alphabetical order
  66  * or by the numeric value, if the strings are well-formed numbers,
  67  * and DateTime/DateTimeImmutable by their unixtime.
  68  *
  69  * To check the order without a mapping function,
  70  * see `C\is_sorted`.
  71  *
  72  * If the comparison operator `<=>` is not useful on Ts
  73  * and no $comparator is provided, the result of is_sorted_by
  74  * will not be useful.
  75  *
  76  * Time complexity: O((n * c), where c is the complexity of the
  77  * comparator function (which is O(1) if not provided explicitly)
  78  * Space complexity: O(n)
  79  */
  80 function is_sorted_by<Tv, Ts>(
  81   Traversable<Tv> $traversable,
  82   (function(Tv)[_]: Ts) $scalar_func,
  83   ?(function(Ts, Ts)[_]: num) $comparator = null,
  84 )[ctx $scalar_func, ctx $comparator]: bool {
  85   $vec = Vec\cast_clear_legacy_array_mark($traversable);
  86   if (is_empty($vec)) {
  87     return true;
  88   }
  89
  90   $comparator ??= (Ts $a, Ts $b) ==>
  91     /*HH_FIXME[4240] Comparison may not be useful on Ts*/$a <=> $b;
  92
  93   $previous = $scalar_func(firstx($vec));
  94   foreach ($vec as $next) {
  95     $next = $scalar_func($next);
  96     if ($comparator($next, $previous) < 0) {
  97       return false;
  98     }
  99     $previous = $next;
 100   }
 101
 102   return true;
 103 }