---
title: "How a5R stores cell IDs without strings"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{How a5R stores cell IDs without strings}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)
```

## The problem

An A5 cell ID is a 64-bit unsigned integer (`u64`).
R has no native `u64` type: its integers are 32-bit signed (`-2^31` to
`2^31 - 1`), and its doubles are 64-bit floating point. A `double`
can only represent integers exactly up to 2^53, while a `u64` can go up to
2^64 - 1.

The obvious workaround is to store cell IDs as hex strings
(`"0800000000000006"`). This works, but every trip across the R-Rust
boundary requires hex parsing and formatting: O(n) string allocation that
dominates the cost of lightweight operations like `a5_get_resolution()` or
`a5_cell_to_parent()`.

## The solution: eight raw-byte fields

A `u64` is exactly 8 bytes. We store each byte of the little-endian
representation as a separate `raw` vector field in a vctrs record type, with
one twist: the most significant byte, `b8`, is stored XOR `0xFC` (see
[NA handling](#na-handling) for why).

```
cell_id (u64):  0x0800000000000006

little-endian bytes:
  0x06, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x08

stored fields:
  b1 = 0x06, b2 = 0x00, b3 = 0x00, b4 = 0x00,
  b5 = 0x00, b6 = 0x00, b7 = 0x00, b8 = 0x08 XOR 0xFC = 0xF4
```

This is lossless: XOR with a constant is its own inverse, so the eight
stored bytes map one-to-one onto the original `u64`. On the Rust side,
reconstructing the id from the eight byte slices is one XOR and a single
`u64::from_le_bytes()` call. There are no pointers, so an `a5_cell` can be
saved with `saveRDS()` like any other R object. Objects saved by a5R 0.6.0
or earlier use the plain byte layout and the pre-1.0 index. Flip the top
byte, then migrate:

```{r, eval = FALSE}
vctrs::field(old, "b8") <- xor(vctrs::field(old, "b8"), as.raw(0xFC))
old <- a5_migrate(old)
```

## R-side: a vctrs record type

On the R side, `a5_cell` is a **vctrs record** (`vctrs::new_rcrd()`) with
eight fields (`b1` through `b8`):

```{r}
library(a5R)
cell <- a5_lonlat_to_cell(-3.19, 55.95, resolution = 10)
vctrs::field(cell, "b1")
vctrs::field(cell, "b8") # stored XOR 0xFC
```

Each field is a plain `raw` vector: a contiguous block of memory with
no per-element overhead. Subsetting, combining, and NA propagation are all
handled automatically by vctrs.

Hex strings are only produced on demand:

```{r}
# Display calls format(), which converts to hex for readability
cell

# Explicit conversion
a5_u64_to_hex(cell)

# Round-trip from hex; unpadded ids and a 0x prefix are read too
a5_cell(c("0800000000000006", "800000000000006", "0x0800000000000006"))
```

## Why this matters

Compare memory for one million cells:

```{r}
set.seed(42)
cells <- a5_lonlat_to_cell(
  runif(1e6, -180, 180),
  runif(1e6, -80, 80),
  resolution = 10
)

# rcrd: eight contiguous raw vectors (8 × 1 byte × 1M ≈ 7.6 MB)
format(object.size(cells), units = "MB")

# equivalent hex strings would be ~81 MB
# (16 chars + 56-byte SEXP header per string)
hex <- a5_u64_to_hex(cells)
format(object.size(hex), units = "MB")
```

## NA handling

`NA` is the id `0xFC00000000000000`. It is never a valid cell: at
resolutions 1 to 29 the top 6 bits hold the quintant (one of the 60 fifths
of the dodecahedron's 12 faces, numbered 0 to 59), and at resolution 0 the
face (0 to 11), so 63 (binary `111111`) never occurs; the id does not decode as a resolution-30 cell
either. Only the full id is the sentinel. Resolution 30 keeps just 5, 3 or 1
quintant bits at the top to make room for position bits, so valid
resolution-30 cells can have a top byte of `0xFC`.

Storing `b8` XOR `0xFC` makes the sentinel's stored form eight `00` bytes.
That matters because vctrs fills gaps field by field, and a missing `raw`
value is `00`. Combining with `NA`, subsetting with an `NA` index, assigning
`NA`, and unmatched rows in joins all produce eight `00` bytes, which decode
to `NA`. With plain bytes they would decode to id 0, the world cell, a valid
id.

On the Rust side, the sentinel is detected and mapped to `None`. Standard
R idioms work as expected:

```{r}
cells_with_na <- a5_cell(c("0800000000000006", NA))
is.na(cells_with_na)
is.na(c(cell, NA))
```

## Working with base R

Because an `a5_cell` is a list of eight raw fields underneath, base
functions that look at that structure directly rather than dispatching on
the class need some care. a5R covers the common cases; the rest have a
vctrs form that is both correct and fast.

**Works as expected.** Subsetting, `c()`, `rev()`, `unique()`,
`duplicated()`, `sort()`, `order()`, `is.na()`, `sample()`, `==`,
comparison operators, `split(cells, f)` with a factor `f`, data frame and
tibble columns, and `rbind()` of data frames with `a5_cell` columns.
Assigning past the end (`x[length(x) + 1] <- cell`) and `length(x) <- n`
grow the vector with `NA`, as they do for base vectors.

**Fast.** `match()` and `%in%` use an exact `mtfrm()` key rather than hex
strings, so they cost about the same as `vctrs::vec_match()` and
`vctrs::vec_in()`.

**Use the vctrs form instead.** Three base cases cannot be intercepted by a
method:

- `c()` dispatches on its first argument only, so `c(NA, cells)` with a
  bare `NA` first never reaches the `a5_cell` method and returns a list.
  Base classes behave the same way: `c(NA, Sys.Date())` loses the `Date`
  class. Start with a cell, as in `c(a5_cell(NA), cells)`, or use
  `vctrs::vec_c(NA, cells)`, which combines by every argument's type. An
  `NA` anywhere after the first argument is fine.
- `split(x, cells)` and `tapply(x, cells, f)` with an `a5_cell` *grouping*
  vector see a list of eight raw vectors and group on their interaction,
  giving one group or an error. Use `vctrs::vec_split(x, cells)` or
  `vctrs::vec_group_id(cells)`, or group with `factor(cells)`.
- `unlist()` on a plain list of `a5_cell` vectors, such as `lapply()`
  output, descends into the fields and returns a meaningless `raw` vector.
  Use `vctrs::list_unchop()`, `do.call(c, x)`, or wrap the list with
  `as_a5_cell_list()`, after which `unlist()` works. Lists returned by
  `a5_cell_to_children()` and friends with `simplify = FALSE` are already
  `a5_cell_list` objects.

Adding rows to a data frame by index (`df[nrow(df) + 1, ] <- ...`) is not
supported for any record-backed column, because base R strips the class
before growing the column. Use `rbind()` or `vctrs::vec_rbind()`.

```{r base-r}
cells <- a5_lonlat_to_cell(c(0, 10, 0), c(0, 10, 0), resolution = 5)

# A leading NA: start with a cell, or use vctrs
c(a5_cell(NA), cells)
vctrs::vec_c(NA, cells)

# Grouping by cell: use vctrs
vctrs::vec_split(1:3, cells)$val

# Flattening lapply() output
parts <- lapply(1:3, function(i) a5_cell_to_children(cells[i]))
unlist(as_a5_cell_list(parts))
```

## Coverings

An `a5_covering` holds one compacted set of cells per element, so it uses a
different layout. Each element is a single `raw` vector of the covering's
64-bit values, little-endian and unmasked: its cells sorted in curve order,
then the compaction marker, exactly as the A5 libraries return them. Rust
reads an element as one slice, and Arrow export is one `list<uint64>` value
per covering.

The compaction marker is a value no cell can take: quintant 60 (only 0 to 59
exist) in the top 6 bits, the resolution in bits 55 to 48, and the tag
`1000000` in the low 7 bits, which no resolution uses. The marker for
resolution 12 is `0xf00c000000000040`:

```{r}
covering <- a5_compact(a5_cell_to_children(cell, child_resolution = 12))
covering
bytes <- unclass(covering)[[1]]
length(bytes) / 8                 # one stored cell, then the marker
rev(bytes[9:16])                  # the marker, most significant byte first
```

A covering never holds `NA`, so no byte is masked. A missing covering is a
`NULL` element, which is what vctrs fills in for a list, so joins and
`vec_init()` produce `NA` coverings with no extra work.

## From compiled code

The byte layout is internal and may change. Packages that build or read
`a5_cell` vectors in C, C++ or Rust should use a5R's C API (`?a5_c_api`):
add `LinkingTo: a5R` and `Imports: a5R`, include `<a5R.h>`, and call
`a5R_cells_from_u64()` and `a5R_cells_to_u64()`. These take plain
`uint64_t` ids with `NA` flagged in a separate `int` array, so callers never
see the mask or the sentinel. `a5R_api_version()`, also given by
`a5_info()$c_api`, reports the API version.

## Summary

| Aspect | Hex strings | Raw bytes |
|--------|------------|-----------|
| R type | `character` vector | `vctrs_rcrd` (eight `raw` fields) |
| Memory (1M cells) | ~81 MB | ~7.6 MB |
| R-Rust crossing | O(n) hex parse/format | Zero-copy byte access |
| Human-readable | Always | On `format()` / `print()` |
| Lossless | Yes | Yes (one-to-one byte encoding) |