Implement vec_identify_runs() and vec_rle()

[DavisVaughan]

Inspired by the adjacency grouping idea in tidyverse/dplyr#5184

We could do much better than this in terms of performance with a C implementation. vec_group_rle() does a lot more work than is necessary here because it uses a dictionary to keep track of what it has already seen.

I've added this to the vec-prefixes google sheet

library(vctrs)
library(dplyr, warn.conflicts = FALSE)

vec_runs <- function(x) {
  rle <- vec_group_rle(x)
  lengths <- field(rle, "length")
  rep(seq_along(lengths), times = lengths)
}

mtcars <- as_tibble(mtcars)

mtcars %>%
  select(vs, am) %>%
  mutate(runs = vec_runs(across()))
#> # A tibble: 32 x 3
#>       vs    am  runs
#>    <dbl> <dbl> <int>
#>  1     0     1     1
#>  2     0     1     1
#>  3     1     1     2
#>  4     1     0     3
#>  5     0     0     4
#>  6     1     0     5
#>  7     0     0     6
#>  8     1     0     7
#>  9     1     0     7
#> 10     1     0     7
#> # … with 22 more rows

^{Created on 2020-05-05 by the reprex package (v0.3.0)}

[DavisVaughan]

Also consider vec_rle(), which would be different from vec_group_rle() since that uses a dictionary to track the first time we saw an individual value. vec_rle() would be much simpler, and would just track changes in x, like vec_runs(). It would return a two column data frame with val and len, very much like rle().

Also, why doesn't vec_group_rle() return a data frame rather than a rcrd? It seems like that would've been simpler for such a low level function.

library(vctrs)

vec_group_rle2 <- function(x) {
  rle <- vec_group_rle(x)
  data.frame(
    grp = field(rle, "group"),
    len = field(rle, "length") 
  )
}

head(vec_group_rle2(mtcars$cyl))
#>   grp len
#> 1   1   2
#> 2   2   1
#> 3   1   1
#> 4   3   1
#> 5   1   1
#> 6   3   1

---

For vec_runs() and vec_rle() to work efficiently, we need to extract out the equality comparison caching utilities from the dictionary code (i.e. d->equal and d->vec_p). That will allow us to extremely efficiently compare values of x for equality.

[DavisVaughan]

vec_identify_runs() might be a better name, since it returns an id. This is inline with other vec-prefixes changes