Id Pool for Dart & Flutter

id_pool.dart

import 'dart:typed_data';

/// Пул объектов с целочисленными идентификаторами и переиспользованием ID.
///
/// Внутреннее устройство (sparse-set + recycle-stack):
///
///  ┌─────────┐        ┌─────────┐
///  │ sparse  │ id ──▶ │  dense  │  dense idx ──▶ data[idx]
///  │Uint32List│        │Uint32List│
///  └─────────┘        └─────────┘
///       ▲                  │
///       │    id = dense[i] │
///       └──────────────────┘
///
///  ┌─────────┐
///  │ recycle │  LIFO-стек освобождённых id
///  │Uint32List│
///  └─────────┘
///
/// - [sparse] : id  → dense-индекс  (или [_invalid])
/// - [dense]  : dense-индекс → id   (обратная ссылка, плотно упакован)
/// - [_data]  : dense-индекс → T    (объекты, плотно упакованы)
/// - [_recycle]: стек свободных id для повторного использования
///
/// Все мутирующие операции O(1). Итерация — линейная по количеству
/// *живых* объектов (dense-массив всегда плотный, без дыр).
class IdPool<T> {
  /// Значение-маркер «слот свободен» в sparse-массиве.
  static const int _invalid = 0xFFFFFFFF; // 2^32 − 1

  /// Начальная / минимальная вместимость.
  static const int _minCapacity = 16;

  // ── Хранилище ──────────────────────────────────────────────────────

  Uint32List _sparse;
  Uint32List _dense;
  Uint32List _recycle;
  List<T?> _data;

  // ── Счётчики ───────────────────────────────────────────────────────

  /// Количество живых (занятых) элементов.
  int _count = 0;

  /// Количество id в стеке переиспользования.
  int _recycleCount = 0;

  /// Следующий «свежий» id, который ещё ни разу не выдавался.
  int _nextFreshId = 0;

  // ── Конструктор ────────────────────────────────────────────────────

  /// Создаёт пул с начальной вместимостью [initialCapacity].
  IdPool([int initialCapacity = _minCapacity])
      : _sparse = _allocSparse(initialCapacity),
        _dense = Uint32List(initialCapacity),
        _recycle = Uint32List(initialCapacity),
        _data = List<T?>.filled(initialCapacity, null);

  // ── Публичный API ──────────────────────────────────────────────────

  /// Количество живых объектов в пуле.
  int get length => _count;

  /// `true`, если пул не содержит ни одного живого объекта.
  bool get isEmpty => _count == 0;

  /// `true`, если пул содержит хотя бы один живой объект.
  bool get isNotEmpty => _count != 0;

  /// Текущая вместимость (до очередного расширения массивов).
  int get capacity => _sparse.length;

  /// Количество id, ожидающих переиспользования.
  int get recycledCount => _recycleCount;

  // ── Acquire / Release ──────────────────────────────────────────────

  /// Выделяет новый (или переиспользованный) id и ассоциирует с ним [value].
  ///
  /// Возвращает присвоенный id.  Амортизированная сложность: O(1).
  int acquire(T value) {
    final int id = _allocateId();
    _ensureCapacity(id + 1);

    final int denseIdx = _count;
    _sparse[id] = denseIdx;
    _dense[denseIdx] = id;
    _data[denseIdx] = value;
    _count++;

    return id;
  }

  /// Освобождает [id] и возвращает ассоциированный объект.
  ///
  /// Использует swap-remove в dense-массиве, чтобы сохранить плотность.
  /// Бросает [StateError], если id не активен.
  T release(int id) {
    _assertAlive(id);

    final int denseIdx = _sparse[id];
    final T value = _data[denseIdx] as T;

    final int lastDense = _count - 1;

    // Swap-remove: перемещаем последний элемент на место удаляемого.
    if (denseIdx != lastDense) {
      final int movedId = _dense[lastDense];
      _dense[denseIdx] = movedId;
      _data[denseIdx] = _data[lastDense];
      _sparse[movedId] = denseIdx;
    }

    // Очистка хвоста.
    _data[lastDense] = null;
    _sparse[id] = _invalid;
    _count--;

    // Возврат id в стек переиспользования.
    _pushRecycled(id);

    return value;
  }

  // ── Доступ ─────────────────────────────────────────────────────────

  /// Возвращает `true`, если [id] в данный момент активен.
  bool contains(int id) {
    if (id < 0 || id >= _sparse.length) return false;
    final int d = _sparse[id];
    return d < _count && _dense[d] == id;
  }

  /// Возвращает объект по [id].
  ///
  /// Бросает [StateError], если id не активен.
  T operator [](int id) {
    _assertAlive(id);
    return _data[_sparse[id]] as T;
  }

  /// Заменяет объект, ассоциированный с [id].
  ///
  /// Бросает [StateError], если id не активен.
  void operator []=(int id, T value) {
    _assertAlive(id);
    _data[_sparse[id]] = value;
  }

  /// Возвращает объект по [id] или `null`, если id не активен.
  T? tryGet(int id) {
    if (!contains(id)) return null;
    return _data[_sparse[id]] as T;
  }

  // ── Итерация ───────────────────────────────────────────────────────

  /// Итерация по всем живым id.
  ///
  /// Dense-массив плотный → итерация без пропусков.
  Iterable<int> get ids => _DenseIterable(_dense, _count);

  /// Итерация по всем живым объектам.
  Iterable<T> get values => _DataIterable<T>(_data, _count);

  /// Итерация по парам (id, value).
  Iterable<IdEntry<T>> get entries => _EntryIterable<T>(_dense, _data, _count);

  /// Применяет [action] к каждому живому (id, value).
  ///
  /// Безопасен для чтения; **не** вызывайте [release]/[acquire] внутри callback.
  void forEach(void Function(int id, T value) action) {
    for (int i = 0; i < _count; i++) {
      action(_dense[i], _data[i] as T);
    }
  }

  // ── Очистка ────────────────────────────────────────────────────────

  /// Удаляет все объекты. Массивы сохраняют текущую вместимость.
  void clear() {
    for (int i = 0; i < _count; i++) {
      _sparse[_dense[i]] = _invalid;
      _data[i] = null;
    }
    _count = 0;
    _recycleCount = 0;
    _nextFreshId = 0;
  }

  /// Сбрасывает пул и освобождает все внутренние буферы.
  void reset([int initialCapacity = _minCapacity]) {
    _sparse = _allocSparse(initialCapacity);
    _dense = Uint32List(initialCapacity);
    _recycle = Uint32List(initialCapacity);
    _data = List<T?>.filled(initialCapacity, null);
    _count = 0;
    _recycleCount = 0;
    _nextFreshId = 0;
  }

  // ── Отладка ────────────────────────────────────────────────────────

  @override
  String toString() =>
      'IdPool<$T>(length: $_count, capacity: $capacity, '
      'recycled: $_recycleCount)';

  /// Полный дамп внутреннего состояния (для отладки).
  String dump() {
    final sb = StringBuffer()
      ..writeln('IdPool<$T> {')
      ..writeln('  count     : $_count')
      ..writeln('  capacity  : $capacity')
      ..writeln('  nextFresh : $_nextFreshId')
      ..writeln('  recycled  : $_recycleCount')
      ..writeln('  sparse    : ${_sparse.sublist(0, _nextFreshId)}')
      ..writeln('  dense     : ${_dense.sublist(0, _count)}')
      ..writeln('  recycle   : ${_recycle.sublist(0, _recycleCount)}')
      ..writeln('  data      : ${_data.sublist(0, _count)}')
      ..writeln('}');
    return sb.toString();
  }

  // ══════════════════════════════════════════════════════════════════
  //  Приватные методы
  // ══════════════════════════════════════════════════════════════════

  /// Выделяет id: сначала из стека recycle, затем свежий.
  int _allocateId() {
    if (_recycleCount > 0) {
      return _recycle[--_recycleCount];
    }
    return _nextFreshId++;
  }

  /// Помещает id в стек переиспользования, расширяя его при необходимости.
  void _pushRecycled(int id) {
    if (_recycleCount == _recycle.length) {
      _recycle = _grow(_recycle, _recycle.length * 2);
    }
    _recycle[_recycleCount++] = id;
  }

  /// Гарантирует, что sparse / dense / data вмещают минимум [needed] слотов.
  void _ensureCapacity(int needed) {
    if (needed <= _sparse.length) return;

    int newCap = _sparse.length;
    while (newCap < needed) {
      newCap = newCap * 2;
    }

    _sparse = _growSparse(_sparse, newCap);
    _dense = _grow(_dense, newCap);
    _data = _growData(_data, newCap);
  }

  void _assertAlive(int id) {
    if (!contains(id)) {
      throw StateError('IdPool: id $id is not alive');
    }
  }

  // ── Статические хелперы для массивов ───────────────────────────────

  /// Создаёт sparse-массив, заполненный [_invalid].
  static Uint32List _allocSparse(int size) {
    final list = Uint32List(size);
    for (int i = 0; i < size; i++) {
      list[i] = _invalid;
    }
    return list;
  }

  /// Расширяет sparse-массив, заполняя новые слоты [_invalid].
  static Uint32List _growSparse(Uint32List old, int newSize) {
    final list = Uint32List(newSize);
    list.setRange(0, old.length, old);
    for (int i = old.length; i < newSize; i++) {
      list[i] = _invalid;
    }
    return list;
  }

  /// Расширяет обычный Uint32List (dense / recycle).
  static Uint32List _grow(Uint32List old, int newSize) {
    final list = Uint32List(newSize);
    list.setRange(0, old.length, old);
    return list;
  }

  /// Расширяет List<T?>.
  static List<T?> _growData<T>(List<T?> old, int newSize) {
    final list = List<T?>.filled(newSize, null);
    for (int i = 0; i < old.length; i++) {
      list[i] = old[i];
    }
    return list;
  }
}

// ═══════════════════════════════════════════════════════════════════
//  Вспомогательные типы для итерации
// ═══════════════════════════════════════════════════════════════════

/// Пара (id, value) для итерации по [IdPool.entries].
class IdEntry<T> {
  final int id;
  final T value;

  const IdEntry(this.id, this.value);

  @override
  String toString() => 'IdEntry($id: $value)';
}

// ── id-итератор ──────────────────────────────────────────────────

class _DenseIterable extends Iterable<int> {
  final Uint32List _dense;
  final int _count;

  _DenseIterable(this._dense, this._count);

  @override
  Iterator<int> get iterator => _DenseIterator(_dense, _count);
}

class _DenseIterator implements Iterator<int> {
  final Uint32List _dense;
  final int _count;
  int _index = -1;

  _DenseIterator(this._dense, this._count);

  @override
  int get current => _dense[_index];

  @override
  bool moveNext() => ++_index < _count;
}

// ── value-итератор ───────────────────────────────────────────────

class _DataIterable<T> extends Iterable<T> {
  final List<T?> _data;
  final int _count;

  _DataIterable(this._data, this._count);

  @override
  Iterator<T> get iterator => _DataIterator<T>(_data, _count);
}

class _DataIterator<T> implements Iterator<T> {
  final List<T?> _data;
  final int _count;
  int _index = -1;

  _DataIterator(this._data, this._count);

  @override
  T get current => _data[_index] as T;

  @override
  bool moveNext() => ++_index < _count;
}

// ── entry-итератор ───────────────────────────────────────────────

class _EntryIterable<T> extends Iterable<IdEntry<T>> {
  final Uint32List _dense;
  final List<T?> _data;
  final int _count;

  _EntryIterable(this._dense, this._data, this._count);

  @override
  Iterator<IdEntry<T>> get iterator =>
      _EntryIterator<T>(_dense, _data, _count);
}

class _EntryIterator<T> implements Iterator<IdEntry<T>> {
  final Uint32List _dense;
  final List<T?> _data;
  final int _count;
  int _index = -1;

  _EntryIterator(this._dense, this._data, this._count);

  @override
  IdEntry<T> get current => IdEntry<T>(_dense[_index], _data[_index] as T);

  @override
  bool moveNext() => ++_index < _count;
}