---
title: "Flexible Sequences: Persistent Lists, Deques, and Slicing"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{Flexible Sequences: Persistent Lists, Deques, and Slicing}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---
```{r setup, include = FALSE}
knitr::opts_chunk$set(collapse = TRUE, comment = "#>")
if(requireNamespace("pkgload", quietly = TRUE)) {
  pkgload::load_all(".", quiet = TRUE)
} else if(requireNamespace("Immutables", quietly = TRUE)) {
  library(Immutables)
} else {
  stop("Need either installed 'Immutables' or the 'pkgload' package to render this vignette.")
}
```


## `flexseq` basics

`flexseq` is a persistent sequence type, with many of the same features as an R `list()`, including storing arbitrary items.
All updates return a new object and keep the original unchanged.

```{r}
x <- flexseq(1, 2, 3)
x

x2 <- as_flexseq(letters[1:5])
x2
```
## Names and indexing

Flexseqs may be named, but if any are named they must all have unique non-`NULL` names. Large named flexseqs are somewhat slower than unnamed ones; for efficient key/value stores consider using an `ordered_sequence()`.

```{r}
x <- flexseq(a = 1, b = 2, c = 3)
x
x[c("c", "b")]

x$b <- NULL # delete b
x
```

In general indexing and slicing works as it does with lists: `[]` returns a sublist indexed by integer (by position), character vector (by name if named), or logical vector (by inclusion). Note that these operations are $O(k\log n)$ where $k$ is the length of the indexing vector.

```{r}
x <- as_flexseq(letters[1:6])

x[[3]]

x[c(1, 3, 5)]
```

## End operations

Flexseqs support pushing new elements onto the front or back of the sequences, peeking at the front or back (i.e., getting a copy of the first or last item), and popping from the front or back, which returns the removed element and a copy of the flexseq input with that item removed. `pop_front()` and `pop_back()` both return a list with fields `$value` and `$remaining`; `peek_back()` is the symmetric counterpart to `peek_front()`.

```{r}
x <- as_flexseq(4:6)

x <- x |>
  push_back(100) |>
  push_front(50)

x

xpopped <- pop_front(x)

xpopped$value
xpopped$remaining
```
## Positional operations

Beyond the ends, flexseqs support arbitrary-position persistent operations. `peek_at()` is the non-throwing positional read (compare with `[[`, which errors when out of bounds); `pop_at()` removes an element at a given index and returns `$value`/`$remaining`; `insert_at()` inserts before a given index, or at `length(x) + 1` to append.

```{r}
x <- flexseq("a", "b", "c", "d")

peek_at(x, 10)  # NULL, no error

out <- pop_at(x, 2)
out$value
out$remaining

insert_at(x, 3, c("x", "y"))
```

## Transforming and combining

`c()` concatenates flexseqs, and `fapply()` applies a function to each element of one returning the result as a flexseq, analygous to `lapply()` for R lists.
```{r}
x <- as_flexseq(4:6)
x2 <- as_flexseq(8:10)

c(x, x2)

x <- as_flexseq(1:3)
fapply(x, function(el) el * 10)
```

`merge(x, y)` is provided as an alias for `c(x, y)` so that `merge()` works uniformly across the package's four structure types. For `flexseq`, `c()` and `merge()` are equivalent; the distinction matters for `ordered_sequence`, `interval_index`, and `priority_queue`, where `merge()` performs a proper sorted/priority-aware combine.

`loop()` (re-exported from the **coro** package) enables `for`-loop traversal, yielding elements left-to-right lazily without materializing a list.

```{r}
x <- flexseq("a", "b", "c", "d")

loop(for (el in x) {
  print(el)
})
```

For named flexseqs, `loop()` yields bare values (matching `peek_front()`); use `as.list()` when you need names alongside values.

```{r}
x <- flexseq(a = 1, b = 2, c = 3)
loop(for (el in x) print(el))
```

Plain `for (el in x)` (without `loop()`) does *not* dispatch to the iteration protocol — it walks the underlying finger-tree storage and yields internal nodes rather than sequence elements. Always wrap with `loop()`.

Flexseqs convert back to standard R structures with `as.list()` (preserves names and list semantics) and `unlist()` (atomic vector when possible). `length()` returns the element count in O(1), and `str()` gives a compact diagnostic display.

```{r}
x <- flexseq(a = 1, b = 2, c = 3)

as.list(x)
unlist(x)
length(x)
```

## Example: simulating complex queueing systems

Queueing systems represent one or more service queues, where arrival and service times are typically drawn from defined distributions such as the exponential. The dynamics of such systems are a common area of study, for example in computing average wait times. While in many cases closed-form solutions for these dynamics exist, simple policy choices such as "each request joins the currently shortest queue" can complicate analyses significantly. In this example we simulate such a system to generate an empirical wait-time distribution.

We simulate `steps` time steps; at each, a new request arrives with probability `p_arrival` and joins the shorter of two queues, `qa` or `qb`. We keep track of each server's next free time step, processing requests from the front of its queue. Each request's wait time is calculated and collected in a running `flexseq`, which we convert to a vector and summarize after.

```{r}
set.seed(100)
steps <- 1000
p_arrival <- 0.9
mean_service <- 1 # service times ~ rpois(1, mean_service) + 1 (real mean 2)

qa <- flexseq(); free_a <- 0
qb <- flexseq(); free_b <- 0
waits <- flexseq()

for(t in seq_len(steps)) {
  # process new arrivals into the shorter queue
  if(runif(1) < p_arrival) {
    request <- list(arrival = t)
    if(length(qa) <= length(qb)) qa <- push_back(qa, request)
    else                         qb <- push_back(qb, request)
  }

  # if qa is free, process the front request and record total wait time
  if(free_a <= t && length(qa) > 0) {
    nxt <- pop_front(qa)
    qa <- nxt$remaining    # overwrite queue with remaining portion
    request <- nxt$value
    waits <- push_back(waits, t - request$arrival)
    free_a <- t + rpois(1, mean_service) + 1
  }

  # if qb is free, process the front request and record total wait time
  if(free_b <= t && length(qb) > 0) {
    nxt <- pop_front(qb)
    qb <- nxt$remaining    # overwrite queue with remaining portion
    request <- nxt$value
    waits <- push_back(waits, t - request$arrival)
    free_b <- t + rpois(1, mean_service) + 1
  }
}

mean(unlist(waits))
```

This example may be extended in several ways, including tracking queue lengths, requests that migrate between queues (as in queueing networks), or other policies such as length-weighted random queue assignment.