# Итераторы коллекций armdb

## Обзор

Итерация доступна только для **Tree-типов** (SkipList-индекс): ConstTree, VarTree, TypedTree, ZeroTree.
**Map-типы** (HashMap-индекс) итерацию не поддерживают.

| Метод | Описание | Семантика диапазона |
|-------|----------|---------------------|
| `iter()` | Все записи | полный обход |
| `range(start, end)` | Диапазон `[start, end)` | включая start, исключая end |
| `range_bounds(start, end)` | Диапазон с произвольными `Bound` | `Included`, `Excluded`, `Unbounded` |
| `prefix_iter(prefix)` | Ключи с заданным префиксом | автоматические границы |

Все методы возвращают итератор, реализующий `Iterator` + `DoubleEndedIterator`.

---

## Типы итераторов

| Tree | Итератор | Item | Disk I/O |
|------|----------|------|----------|
| ConstTree | `ConstIter<'a, K, V>` | `(K, [u8; V])` — копия | нет |
| VarTree | `VarIter<'a, K, H>` | `(K, ByteView)` — RC | возможен (cache miss) |
| TypedTree | `TypedIter<'a, K, T>` | `(K, &'a T)` — ссылка | нет |
| ZeroTree | `ZeroIter<'a, K, V, T>` | `(K, T)` — копия | нет |

### Возврат значений

- **ConstTree** — `[u8; V]` копируется из inline SeqLock (`node.read_value()`)
- **VarTree** — `ByteView` читается через `read_value_cached(&disk)`, при промахе block cache — pread с диска
- **TypedTree** — `&'a T` ссылка на значение в `TypedData`, защищённая seize guard
- **ZeroTree** — обёртка над `ConstIter`, `[u8; V]` → `T` через zerocopy (`from_value_bytes`)

---

## Структура итератора

Все итераторы (кроме ZeroIter) имеют одинаковую структуру:

```rust,ignore
pub struct ConstIter<'a, K: Key, const V: usize> {
    list: &'a SkipList<ConstNode<K, V>>,
    front: *mut ConstNode<K, V>,     // указатель вперёд
    back: *mut ConstNode<K, V>,      // указатель назад
    end: Bound<K>,                   // верхняя граница (forward)
    start: Bound<K>,                 // нижняя граница (backward)
    reversed: bool,                  // флаг обратного порядка
    done: bool,                      // front == back — итерация завершена
    _guard: seize::LocalGuard<'a>,   // предотвращает reclamation нод
}
```

`ZeroIter` — тонкая обёртка:

```rust,ignore
pub struct ZeroIter<'a, K: Key, const V: usize, T> {
    inner: ConstIter<'a, K, V>,
    _marker: PhantomData<T>,
}
```

`VarIter` отличается тем, что хранит `tree: &'a VarTree<K, H>` вместо `list`,
чтобы читать значения через block cache.

---

## Алгоритм обхода

### next() — прямой обход

```text
loop:
  if done || front == null → None
  node = *front
  converged = (front == back)
  front = node.tower[0].next()     // двигаем front вперёд
  if converged → done = true
  if node.is_marked() → skip       // удалённая нода
  if !check_end(node.key) → None   // вышли за границу
  return Some((key, value))
```

### next_back() — обратный обход

```text
loop:
  if done || back == null → None
  node = *back
  converged = (front == back)
  back = list.find_last_lt(key)    // двигаем back назад
  if converged → done = true
  if node.is_marked() → skip
  if !check_start(node.key) → None
  return Some((key, value))
```

Асимметрия: `next()` использует `tower[0].next()` (O(1)), а `next_back()` — `find_last_lt()` (O(log n)).

### Конвергенция

Когда `front == back`, итератор устанавливает `done = true`. После этого и `next()`, и `next_back()` возвращают `None`. Это предотвращает повторную выдачу элемента.

---

## Reversed ordering

По умолчанию `Config::reversed = true` — SkipList хранит ключи в обратном порядке (компаратор `b.cmp(a)`).

| reversed | iter() | iter().rev() |
|----------|--------|-------------|
| true (default) | descending | ascending |
| false | ascending | descending |

Проверка границ учитывает `reversed`:

```rust,ignore
// check_end (forward direction)
fn check_end(&self, key: &K) -> bool {
    match &self.end {
        Bound::Unbounded => true,
        Bound::Excluded(end) => {
            if self.reversed { key > end } else { key < end }
        }
        Bound::Included(end) => {
            if self.reversed { key >= end } else { key <= end }
        }
    }
}
```

---

## Prefix search

`prefix_iter(prefix)` вычисляет границы через `prefix_bounds()`:

**reversed = false:**
- `search_key` = prefix + `0x00` padding → первый ключ с этим префиксом
- `end` = `prefix + 1` (инкремент последнего байта) как `Excluded` bound; если overflow (все `0xFF`) — `Unbounded`

**reversed = true:**
- `search_key` = prefix + `0xFF` padding → последний ключ с этим префиксом
- `end` = prefix + `0x00` padding как `Included` bound

```rust
// Пример: prefix = [0x01]
// reversed=true:
//   search = [0x01, 0xFF, 0xFF, ...]  — ищем от конца группы
//   end    = [0x01, 0x00, 0x00, ...]  — до начала группы (Included)
// reversed=false:
//   search = [0x01, 0x00, 0x00, ...]  — ищем от начала группы
//   end    = [0x02, 0x00, 0x00, ...]  — до следующей группы (Excluded)
```

---

## Weakly-consistent семантика

Итераторы **не** создают snapshot. Они являются weakly-consistent:

- Конкурентные вставки/обновления **могут быть видны** во время итерации
- Удалённые записи (marked nodes) автоматически **пропускаются**
- `seize::LocalGuard` предотвращает reclamation памяти нод на время жизни итератора

---

## VarTree: disk I/O при итерации

`VarIter` — единственный итератор, который может выполнять disk I/O:

```rust,ignore
fn next(&mut self) -> Option<Self::Item> {
    // ... обход SkipList ...
    let disk = *node.load_disk();
    match self.tree.read_value_cached(&disk) {
        Some(value) => return Some((node.key, value)),
        None => continue,  // значение недоступно (compacted), пропускаем
    }
}
```

При промахе block cache выполняется `pread` с диска. Для предзагрузки кэша используйте `warmup()`.

---

## Helper-методы

| Итератор | Метод | Описание |
|----------|-------|----------|
| ConstIter | `collect_vec()` | `Vec<(K, [u8; V])>` |
| TypedIter | `collect_vec()` | `Vec<(K, &T)>` |
| VarIter | `collect_keys()` | `Vec<K>` — только ключи |
| VarIter | `collect_entries()` | `Vec<(K, ByteView)>` |

---

## Send safety

Все итераторы содержат raw pointers и реализуют `unsafe impl Send`:

```rust,ignore
// SAFETY: итератор держит seize guard, который предотвращает
// reclamation нод. Raw pointer разыменовывается только пока guard жив.
unsafe impl<K: Key, const V: usize> Send for ConstIter<'_, K, V> {}
unsafe impl<K: Key, H: WriteHook<K>> Send for VarIter<'_, K, H> {}
unsafe impl<K: Key, T: Send + Sync> Send for TypedIter<'_, K, T> {}
```

ZeroIter наследует Send от ConstIter (обёртка).

---

## Стоимость операций

| Операция | ConstTree | VarTree | TypedTree | ZeroTree |
|----------|-----------|---------|-----------|----------|
| `next()` | O(1), zero I/O | O(1) + возможен pread | O(1), zero I/O | O(1), zero I/O |
| `next_back()` | O(log n), zero I/O | O(log n) + возможен pread | O(log n), zero I/O | O(log n), zero I/O |
| `prefix_iter()` setup | O(log n) | O(log n) | O(log n) | O(log n) |
| `range()` setup | O(log n) | O(log n) | O(log n) | O(log n) |

---

## Примеры использования

### Полный обход

```rust,ignore
// ConstTree
for (key, value) in tree.iter() {
    // key: [u8; K], value: [u8; V]
}

// TypedTree
for (key, user) in tree.iter() {
    // key: [u8; K], user: &User
}

// ZeroTree
for (key, counters) in tree.iter() {
    // key: [u8; K], counters: Counters (Copy)
}
```

### Prefix search — "последние N записей"

```rust,ignore
// Составной ключ: [user_id:8][post_id:8]
// reversed=true (default) → prefix_iter возвращает от новых к старым

let latest_posts: Vec<_> = tree
    .prefix_iter(&user_id)
    .take(20)
    .collect();
```

### Range query

```rust,ignore
// Диапазон [start, end) — start включительно, end исключительно
let start = 5u64.to_be_bytes();
let end = 10u64.to_be_bytes();

for (key, value) in tree.range(&start, &end) {
    // reversed=true → ключи 9, 8, 7, 6, 5
}
```

### range_bounds — произвольные границы

`range_bounds(start: Bound<&K>, end: Bound<&K>)` — обобщение `range()`.
Каждая граница может быть `Included`, `Excluded` или `Unbounded`.

`range(start, end)` эквивалентен `range_bounds(Bound::Included(start), Bound::Excluded(end))`.

```rust,ignore
use std::ops::Bound;

// (5, 10] — исключить 5, включить 10
let entries: Vec<_> = tree.range_bounds(
    Bound::Excluded(&5u64.to_be_bytes()),
    Bound::Included(&10u64.to_be_bytes()),
).collect();
// reversed=true → 10, 9, 8, 7, 6

// [5, 10] — включить обе границы
let entries: Vec<_> = tree.range_bounds(
    Bound::Included(&5u64.to_be_bytes()),
    Bound::Included(&10u64.to_be_bytes()),
).collect();
// reversed=true → 10, 9, 8, 7, 6, 5

// (5, ..) — от 5 исключительно до конца
let entries: Vec<_> = tree.range_bounds(
    Bound::Excluded(&5u64.to_be_bytes()),
    Bound::Unbounded,
).collect();

// (.., 10) — от начала до 10 исключительно
let entries: Vec<_> = tree.range_bounds(
    Bound::Unbounded,
    Bound::Excluded(&10u64.to_be_bytes()),
).collect();
```

### DoubleEndedIterator

```rust,ignore
// .rev() — обратный порядок
let oldest: Vec<_> = tree.prefix_iter(&user_id).rev().take(10).collect();

// Смешанный обход: next() + next_back()
let mut iter = tree.iter();
let first = iter.next();       // первый в порядке итерации
let last = iter.next_back();   // последний в порядке итерации
// Итератор схлопывается к центру
```

### VarTree — предзагрузка кэша

```rust,ignore
// Предзагрузить все значения в block cache перед итерацией
tree.warmup()?;
for (key, value) in tree.iter() {
    // value: ByteView — без disk I/O после warmup
}
```
