hphp/hsl/src/keyset/select.php

   1 <?hh
   2 /*
   3  *  Copyright (c) 2004-present, Facebook, Inc.
   4  *  All rights reserved.
   5  *
   6  *  This source code is licensed under the MIT license found in the
   7  *  LICENSE file in the root directory of this source tree.
   8  *
   9  */
  10
  11 namespace HH\Lib\Keyset;
  12
  13 use namespace HH\Lib\C;
  14
  15 /**
  16  * Returns a new keyset containing only the elements of the first Traversable
  17  * that do not appear in any of the other ones.
  18  *
  19  * Time complexity: O(n + m), where n is size of `$first` and m is the combined
  20  * size of `$second` plus all the `...$rest`
  21  * Space complexity: O(n + m), where n is size of `$first` and m is the combined
  22  * size of `$second` plus all the `...$rest` -- note that this is bigger than
  23  * O(n)
  24  */
  25 function diff<Tv1 as arraykey, Tv2 as arraykey>(
  26   Traversable<Tv1> $first,
  27   Traversable<Tv2> $second,
  28   Container<Tv2> ...$rest
  29 )[]: keyset<Tv1> {
  30   if (!$first) {
  31     return keyset[];
  32   }
  33   if (!$second && !$rest) {
  34     return keyset($first);
  35   }
  36   $union = !$rest ? keyset($second) : union($second, ...$rest);
  37   return filter($first, $value ==> !C\contains_key($union, $value));
  38 }
  39 /**
  40  * Returns a new keyset containing all except the first `$n` elements of
  41  * the given Traversable.
  42  *
  43  * To take only the first `$n` elements, see `Keyset\take()`.
  44  *
  45  * Time complexity: O(n), where n is the size of `$traversable`
  46  * Space complexity: O(n), where n is the size of `$traversable`
  47  */
  48 function drop<Tv as arraykey>(
  49   Traversable<Tv> $traversable,
  50   int $n,
  51 )[]: keyset<Tv> {
  52   invariant($n >= 0, 'Expected non-negative N, got %d.', $n);
  53   $result = keyset[];
  54   $ii = -1;
  55   foreach ($traversable as $value) {
  56     $ii++;
  57     if ($ii < $n) {
  58       continue;
  59     }
  60     $result[] = $value;
  61   }
  62   return $result;
  63 }
  64
  65 /**
  66  * Returns a new keyset containing only the values for which the given predicate
  67  * returns `true`. The default predicate is casting the value to boolean.
  68  *
  69  * To remove null values in a typechecker-visible way, see `Keyset\filter_nulls()`.
  70  *
  71  * Time complexity: O(n * p), where p is the complexity of `$value_predicate`
  72  * Space complexity: O(n)
  73  */
  74 function filter<Tv as arraykey>(
  75   Traversable<Tv> $traversable,
  76   ?(function(Tv)[_]: bool) $value_predicate = null,
  77 )[ctx $value_predicate]: keyset<Tv> {
  78   $value_predicate ??= \HH\Lib\_Private\boolval<>;
  79   $result = keyset[];
  80   foreach ($traversable as $value) {
  81     if ($value_predicate($value)) {
  82       $result[] = $value;
  83     }
  84   }
  85   return $result;
  86 }
  87
  88 /**
  89  * Returns a new keyset containing only non-null values of the given
  90  * Traversable.
  91  *
  92  * Time complexity: O(n)
  93  * Space complexity: O(n)
  94  */
  95 function filter_nulls<Tv as arraykey>(
  96   Traversable<?Tv> $traversable,
  97 )[]: keyset<Tv> {
  98   $result = keyset[];
  99   foreach ($traversable as $value) {
 100     if ($value !== null) {
 101       $result[] = $value;
 102     }
 103   }
 104   return $result;
 105 }
 106
 107 /**
 108  * Returns a new keyset containing only the values for which the given predicate
 109  * returns `true`.
 110  *
 111  * If you don't need access to the key, see `Keyset\filter()`.
 112  *
 113  * Time complexity: O(n * p), where p is the complexity of `$predicate`
 114  * Space complexity: O(n)
 115  */
 116 function filter_with_key<Tk, Tv as arraykey>(
 117   KeyedTraversable<Tk, Tv> $traversable,
 118   (function(Tk, Tv)[_]: bool) $predicate,
 119 )[ctx $predicate]: keyset<Tv> {
 120   $result = keyset[];
 121   foreach ($traversable as $key => $value) {
 122     if ($predicate($key, $value)) {
 123       $result[] = $value;
 124     }
 125   }
 126   return $result;
 127 }
 128
 129 /**
 130  * Returns a new keyset containing the keys of the given KeyedTraversable,
 131  * maintaining the iteration order.
 132  */
 133 function keys<Tk as arraykey, Tv>(
 134   KeyedTraversable<Tk, Tv> $traversable,
 135 )[]: keyset<Tk> {
 136   $result = keyset[];
 137   foreach ($traversable as $key => $_) {
 138     $result[] = $key;
 139   }
 140   return $result;
 141 }
 142
 143 /**
 144  * Returns a new keyset containing only the elements of the first Traversable
 145  * that appear in all the other ones.
 146  *
 147  * Time complexity: O(n + m), where n is size of `$first` and m is the combined
 148  * size of `$second` plus all the `...$rest`
 149  * Space complexity: O(n), where n is size of `$first`
 150  */
 151 function intersect<Tv as arraykey>(
 152   Traversable<Tv> $first,
 153   Traversable<Tv> $second,
 154   Container<Tv> ...$rest
 155 )[]: keyset<Tv> {
 156   if (!$first || !$second) {
 157     return keyset[];
 158   }
 159   $intersection = keyset($first);
 160   $rest[] = $second;
 161   foreach ($rest as $traversable) {
 162     $next_intersection = keyset[];
 163     $keyed_traversable = keyset($traversable);
 164     foreach ($intersection as $value) {
 165       if (C\contains_key($keyed_traversable, $value)) {
 166         $next_intersection[] = $value;
 167       }
 168     }
 169     if (!$next_intersection) {
 170       return keyset[];
 171     }
 172     $intersection = $next_intersection;
 173   }
 174   return $intersection;
 175 }
 176
 177 /**
 178  * Returns a new keyset containing the first `$n` elements of the given
 179  * Traversable.
 180  *
 181  * If there are duplicate values in the Traversable, the keyset may be shorter
 182  * than the specified length.
 183  *
 184  * To drop the first `$n` elements, see `Keyset\drop()`.
 185  *
 186  * Time complexity: O(n), where n is `$n`
 187  * Space complexity: O(n), where n is `$n`
 188  */
 189 function take<Tv as arraykey>(
 190   Traversable<Tv> $traversable,
 191   int $n,
 192 )[]: keyset<Tv> {
 193   if ($n === 0) {
 194     return keyset[];
 195   }
 196   invariant($n > 0, 'Expected non-negative N, got %d.', $n);
 197   $result = keyset[];
 198   $ii = 0;
 199   foreach ($traversable as $value) {
 200     $result[] = $value;
 201     $ii++;
 202     if ($ii === $n) {
 203       break;
 204     }
 205   }
 206   return $result;
 207 }