<?php
/*************************************************************
# 076 License

Copyright (c) テクニカル諏訪子

Permission is hereby granted to any person obtaining a copy of the software
Little Beast (the "Software") to use, modify, merge, copy, publish, distribute,
sublicense, and/or sell copies of the Software, subject to the following conditions:

    1. **Origin Attribution**:
       - You must not misrepresent the origin of the Software; you must not claim
         you created the original Software.
       - If the Software is used in a product, you must either:
         a. Provide clear attribution in the product's documentation, user interface,
            or other visible areas, **OR**
         b. Pay the original developers a fee they specify in writing.
    2. **Usage Restriction**:
       - The Software, or any derivative works, dependencies, or libraries
         incorporating it, must not be used for censorship or to suppress freedom of
         speech, expression, or creativity. Prohibited uses include, but are not
         limited to:
         - Censorship of so-called "hate speech", visuals, non-mainstream opinions,
           ideas, or objective reality.
         - Tools or systems designed to restrict access to information or
           artistic works.
    3. **Notice Preservation**:
       - This license and the above copyright notice must remain intact in all copies
         of the source code.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
namespace Std\Lib\Db\Sqlite;

use Std\Lib\Db\DbException;

/**
 * SQLiteのBツリー（テーブル：rowidがキー、インデックス：レコードがキー）
 *
 * ページはPageのオブジェクトとして持ち、flush()でPagerに書く。セルは毎回ページの最後に詰めて書き直すので、
 * フリーブロックは使わない。ページが溢れたり少なくなったりしたら、SQLiteと同じく最大3つの兄弟のページで分け直す。
 */
final class Btree {
  public const TABLE_LEAF = 13;
  public const TABLE_INTERIOR = 5;
  public const INDEX_LEAF = 10;
  public const INDEX_INTERIOR = 2;

  /** @var array<int, Page> */
  private array $pages = [];
  private array $dirty = [];
  private int $generation = -1;
  /** スナップショット（文・セーブポイント）：ページ番号 => [変更前のページ, 変更されていたか]、又はnull（無かった） */
  private array $snaps = [];

  public function __construct(private Pager $pager) {}

  ///////////////
  // ページ

  /** ページを読む（オブジェクトのキャッシュ） */
  public function page(int $pgno): Page {
    $this->sync();
    if ($this->snaps) $this->remember($pgno);
    if (isset($this->pages[$pgno])) return $this->pages[$pgno];
    if (count($this->pages) > 3000 && empty($this->dirty)) $this->pages = [];
    return $this->pages[$pgno] = $this->parse($pgno);
  }

  /** Pagerのキャッシュが捨てられたら、こちらも捨てる */
  private function sync(): void {
    if ($this->generation !== $this->pager->generation) {
      $this->pages = [];
      $this->dirty = [];
      $this->snaps = [];
      $this->generation = $this->pager->generation;
    }
  }

  /** キャッシュを捨てる（ロールバックの後） */
  public function reset(): void {
    $this->pages = [];
    $this->dirty = [];
    $this->snaps = [];
  }

  /** ページの変更前の状態を覚える（今のスナップショットで初めての場合） */
  private function remember(int $pgno): void {
    $k = array_key_last($this->snaps);
    if (array_key_exists($pgno, $this->snaps[$k])) return;
    $this->snaps[$k][$pgno] = isset($this->pages[$pgno]) ? [clone $this->pages[$pgno], isset($this->dirty[$pgno])] : null;
  }

  /**
   * スナップショット（Pagerと一緒に使う。変更されたページをPagerに書かなくても、文だけを元に戻せる）
   *
   * @return int
   */
  public function snapPush(): int {
    $this->sync();
    $this->snaps[] = [];
    return count($this->snaps) - 1;
  }

  /** スナップショットを捨てる（変更は残す） */
  public function snapPop(?int $n): void {
    if ($n === null) return;
    while (count($this->snaps) > $n) {
      $top = array_pop($this->snaps);
      if ($this->snaps) {
        $k = array_key_last($this->snaps);
        $this->snaps[$k] += $top;
      }
    }
  }

  /** スナップショットの時に戻す（スナップショットは残す） */
  public function snapRestore(?int $n): void {
    if ($n === null || !isset($this->snaps[$n])) return;
    $all = [];
    for ($k = $n; $k < count($this->snaps); $k++) $all += $this->snaps[$k];
    foreach ($all as $pgno => $e) {
      if ($e === null) {
        unset($this->pages[$pgno], $this->dirty[$pgno]);
      } else {
        $this->pages[$pgno] = $e[0];
        if ($e[1]) $this->dirty[$pgno] = true;
        else unset($this->dirty[$pgno]);
      }
    }
    $this->snaps = array_slice($this->snaps, 0, $n);
    $this->snaps[] = [];
  }

  private function parse(int $pgno): Page {
    if ($pgno === 1 && $this->pager->nPages === 0) {
      // 空のファイル：sqlite_schemaは空
      $p = new Page(1);
      $p->type = self::TABLE_LEAF;
      return $p;
    }
    $raw = $this->pager->read($pgno);
    $h = $pgno === 1 ? 100 : 0;
    $p = new Page($pgno);
    $p->type = ord($raw[$h]);
    if (!in_array($p->type, [2, 5, 10, 13], true)) throw new DbException("データベースが壊れています（ページ{$pgno}の種類：{$p->type}）", 11, 'HY000');
    $n = unpack('n', $raw, $h + 3)[1];
    $leaf = $p->isLeaf();
    $table = $p->isTable();
    if (!$leaf) $p->right = unpack('N', $raw, $h + 8)[1];
    $base = $h + ($leaf ? 8 : 12);
    $ptrs = $n > 0 ? array_values(unpack("n{$n}", $raw, $base)) : [];
    $size = 0;
    foreach ($ptrs as $off) {
      $pos = $off;
      if (!$leaf) {
        $p->left[] = unpack('N', $raw, $off)[1];
        $pos += 4;
      }
      $start = $pos;
      if ($table && !$leaf) {
        $p->keys[] = Record::getVarint($raw, $pos);
      } else {
        $len = Record::getVarint($raw, $pos);
        if ($table) $p->keys[] = Record::getVarint($raw, $pos);
        $local = $this->localSize($len, $table);
        $pos += $local + ($len > $local ? 4 : 0);
      }
      $p->cells[] = substr($raw, $start, $pos - $start);
      $size += $pos - $off + 2;
    }
    $p->size = $size;
    if (!$table) $p->dec = $n > 0 ? array_fill(0, $n, null) : [];
    return $p;
  }

  private function serialize(Page $p): string {
    $h = $p->pgno === 1 ? 100 : 0;
    $leaf = $p->isLeaf();
    $off = $this->pager->usable;
    $ptrs = '';
    $parts = [];
    foreach ($p->cells as $i => $c) {
      $cell = $leaf ? $c : pack('N', $p->left[$i]).$c;
      $off -= strlen($cell);
      $ptrs .= pack('n', $off);
      $parts[] = $cell;
    }
    $n = count($p->cells);
    $head = chr($p->type)."\0\0".pack('n', $n).pack('n', $off === 65536 ? 0 : $off)."\0".($leaf ? '' : pack('N', $p->right));
    $gap = $off - ($h + strlen($head) + strlen($ptrs));
    if ($gap < 0) throw new \LogicException("SQLite：ページ{$p->pgno}が溢れました");
    $prefix = $h ? $this->pager->header() : '';
    return $prefix.$head.$ptrs.str_repeat("\0", $gap).implode('', array_reverse($parts))
      .str_repeat("\0", $this->pager->pageSize - $this->pager->usable);
  }

  /** 変更されたページ */
  private function touch(Page $p): void {
    $this->dirty[$p->pgno] = true;
  }

  /** 変更されたページが多ければPagerに書く（操作の間だけ。途中のページは溢れているかもしれない） */
  private function spill(): void {
    if (count($this->dirty) > 500) $this->flush();
  }

  /** 変更されたページをPagerに書く */
  public function flush(): void {
    foreach (array_keys($this->dirty) as $pgno) {
      if (isset($this->pages[$pgno])) $this->pager->write($pgno, $this->serialize($this->pages[$pgno]));
    }
    $this->dirty = [];
  }

  private function newPage(int $type): Page {
    $this->sync();
    $pgno = $this->pager->allocate();
    if ($this->snaps) $this->remember($pgno);
    $p = new Page($pgno);
    $p->type = $type;
    $this->pages[$pgno] = $p;
    $this->touch($p);
    return $p;
  }

  private function freePage(int $pgno): void {
    if ($this->snaps) $this->remember($pgno);
    unset($this->pages[$pgno], $this->dirty[$pgno]);
    $this->pager->free($pgno);
  }

  /** ページに入るセルの大きさ */
  private function capacity(Page $p): int {
    return $this->pager->usable - ($p->pgno === 1 ? 100 : 0) - ($p->isLeaf() ? 8 : 12);
  }

  private function cellSize(Page $p, string $cell): int {
    return strlen($cell) + ($p->isLeaf() ? 2 : 6);
  }

  ///////////////
  // ペイロードとオーバーフロー

  /** ページに置くペイロードのバイト数（残りはオーバーフローのページ） */
  public function localSize(int $len, bool $table): int {
    $u = $this->pager->usable;
    $x = $table ? $u - 35 : intdiv(($u - 12) * 64, 255) - 23;
    if ($len <= $x) return $len;
    $m = intdiv(($u - 12) * 32, 255) - 23;
    $k = $m + (($len - $m) % ($u - 4));
    return $k <= $x ? $k : $m;
  }

  /** セルのペイロードの全部 */
  public function payload(Page $p, int $i): string {
    $c = $p->cells[$i];
    $pos = 0;
    $len = Record::getVarint($c, $pos);
    $table = $p->isTable();
    if ($table) Record::getVarint($c, $pos);
    $local = $this->localSize($len, $table);
    $data = substr($c, $pos, $local);
    if ($len > $local) {
      $next = unpack('N', $c, $pos + $local)[1];
      $rest = $len - $local;
      $chunk = $this->pager->usable - 4;
      while ($rest > 0) {
        if ($next < 1) throw new DbException('データベースが壊れています（オーバーフロー）', 11, 'HY000');
        $o = $this->pager->read($next);
        $take = min($rest, $chunk);
        $data .= substr($o, 4, $take);
        $rest -= $take;
        $next = unpack('N', $o)[1];
      }
    }
    return $data;
  }

  /** インデックスのセルのキー（デコードした物） */
  public function key(Page $p, int $i): array {
    return $p->dec[$i] ??= Record::decode($this->payload($p, $i));
  }

  private function makeCell(string $payload, ?int $rowid): string {
    $len = strlen($payload);
    $table = $rowid !== null;
    $head = Record::putVarint($len).($table ? Record::putVarint($rowid) : '');
    $local = $this->localSize($len, $table);
    if ($local >= $len) return $head.$payload;
    $chunk = $this->pager->usable - 4;
    $pieces = str_split(substr($payload, $local), $chunk);
    $pgnos = [];
    foreach ($pieces as $_) $pgnos[] = $this->pager->allocate();
    foreach ($pieces as $k => $piece) {
      $next = $pgnos[$k + 1] ?? 0;
      $this->pager->write($pgnos[$k], str_pad(pack('N', $next).$piece, $this->pager->pageSize, "\0"));
    }
    return $head.substr($payload, 0, $local).pack('N', $pgnos[0]);
  }

  /** セルのオーバーフローのページを解放する */
  private function freeOverflow(Page $p, string $c): void {
    if (!$p->isLeaf() && $p->isTable()) return;
    $pos = 0;
    $len = Record::getVarint($c, $pos);
    if ($p->isTable()) Record::getVarint($c, $pos);
    $local = $this->localSize($len, $p->isTable());
    if ($len <= $local) return;
    $next = unpack('N', $c, $pos + $local)[1];
    $n = intdiv($len - $local + $this->pager->usable - 5, $this->pager->usable - 4);
    for ($k = 0; $k < $n && $next > 0; $k++) {
      $o = $this->pager->read($next);
      $this->freePage($next);
      $next = unpack('N', $o)[1];
    }
  }

  ///////////////
  // テーブル

  /** 新しいテーブル（又はインデックス）のツリー */
  public function create(bool $table): int {
    return $this->newPage($table ? self::TABLE_LEAF : self::INDEX_LEAF)->pgno;
  }

  private static function lowerBound(array $keys, int $k): int {
    $lo = 0;
    $hi = count($keys);
    while ($lo < $hi) {
      $mid = ($lo + $hi) >> 1;
      if ($keys[$mid] < $k) $lo = $mid + 1;
      else $hi = $mid;
    }
    return $lo;
  }

  private function child(Page $p, int $i): int {
    return $i < count($p->cells) ? $p->left[$i] : $p->right;
  }

  /** @return array  [path, 葉, 位置, 有るか] */
  private function seek(int $root, int $rowid): array {
    $path = [];
    $p = $this->page($root);
    while (!$p->isLeaf()) {
      $i = self::lowerBound($p->keys, $rowid);
      $path[] = [$p, $i];
      $p = $this->page($this->child($p, $i));
    }
    $i = self::lowerBound($p->keys, $rowid);
    return [$path, $p, $i, $i < count($p->keys) && $p->keys[$i] === $rowid];
  }

  /**
   * 行を読む
   *
   * @return string|null  レコード（無ければnull）
   */
  public function get(int $root, int $rowid): ?string {
    [, $p, $i, $found] = $this->seek($root, $rowid);
    return $found ? $this->payload($p, $i) : null;
  }

  /** 行を入れる（同じrowidが有れば置き換える） */
  public function insert(int $root, int $rowid, string $record): void {
    $this->spill();
    [$path, $p, $i, $found] = $this->seek($root, $rowid);
    $cell = $this->makeCell($record, $rowid);
    if ($found) {
      $this->freeOverflow($p, $p->cells[$i]);
      $p->size += strlen($cell) - strlen($p->cells[$i]);
      $p->cells[$i] = $cell;
    } else {
      array_splice($p->cells, $i, 0, [$cell]);
      array_splice($p->keys, $i, 0, [$rowid]);
      $p->size += strlen($cell) + 2;
    }
    $this->touch($p);
    $this->fix($path, $p);
  }

  /** 行を消す */
  public function delete(int $root, int $rowid): bool {
    $this->spill();
    [$path, $p, $i, $found] = $this->seek($root, $rowid);
    if (!$found) return false;
    $this->freeOverflow($p, $p->cells[$i]);
    $p->size -= strlen($p->cells[$i]) + 2;
    array_splice($p->cells, $i, 1);
    array_splice($p->keys, $i, 1);
    $this->touch($p);
    $this->fix($path, $p);
    return true;
  }

  /** 一番大きいrowid（空なら0） */
  public function maxRowid(int $root): int {
    $p = $this->page($root);
    while (!$p->isLeaf()) $p = $this->page($p->right);
    return empty($p->keys) ? 0 : end($p->keys);
  }

  /**
   * テーブルの行を順番に
   *
   * @param int $root
   * @param int|null $from  最小のrowid
   * @param int|null $to  最大のrowid
   * @return \Generator  rowid => レコード
   */
  public function scan(int $root, ?int $from = null, ?int $to = null): \Generator {
    $stop = false;
    yield from $this->walkTable($root, $from, $to, $stop);
  }

  private function walkTable(int $pgno, ?int $from, ?int $to, bool &$stop): \Generator {
    $p = $this->page($pgno);
    $n = count($p->cells);
    $i = $from === null ? 0 : self::lowerBound($p->keys, $from);
    if ($p->isLeaf()) {
      for (; $i < $n; $i++) {
        if ($to !== null && $p->keys[$i] > $to) {
          $stop = true;
          return;
        }
        yield $p->keys[$i] => $this->payload($p, $i);
      }
      return;
    }
    for (; $i <= $n; $i++) {
      yield from $this->walkTable($this->child($p, $i), $from, $to, $stop);
      if ($stop || ($to !== null && $i < $n && $p->keys[$i] >= $to)) {
        $stop = true;
        return;
      }
    }
  }

  /** 行の数 */
  public function count(int $root): int {
    $p = $this->page($root);
    if ($p->isLeaf()) return count($p->cells);
    $n = 0;
    for ($i = 0; $i <= count($p->cells); $i++) $n += $this->count($this->child($p, $i));
    return $n;
  }

  /**
   * ツリーを空にする（$dropならルートも解放する）
   */
  public function clear(int $root, bool $drop = false): void {
    $p = $this->page($root);
    $this->freeSubtree($p, false);
    if ($drop) {
      $this->freePage($root);
      return;
    }
    $p->type = $p->isTable() ? self::TABLE_LEAF : self::INDEX_LEAF;
    $p->cells = $p->left = $p->keys = $p->dec = [];
    $p->right = 0;
    $p->size = 0;
    $this->touch($p);
  }

  private function freeSubtree(Page $p, bool $self): void {
    foreach ($p->cells as $c) $this->freeOverflow($p, $c);
    if (!$p->isLeaf()) {
      for ($i = 0; $i <= count($p->cells); $i++) $this->freeSubtree($this->page($this->child($p, $i)), true);
    }
    if ($self) $this->freePage($p->pgno);
  }

  ///////////////
  // インデックス

  /**
   * 最初の位置（キーの前方一致で比べる）
   *
   * @param bool $strict  trueなら「＞」、falseなら「≧」
   */
  private function bound(Page $p, array $key, array $idx, bool $strict): int {
    $lo = 0;
    $hi = count($p->cells);
    while ($lo < $hi) {
      $mid = ($lo + $hi) >> 1;
      $c = Record::compareKeys($this->key($p, $mid), $key, $idx['colls'], $idx['desc']);
      if ($c < 0 || ($strict && $c === 0)) $lo = $mid + 1;
      else $hi = $mid;
    }
    return $lo;
  }

  /**
   * インデックスにキーを入れる
   *
   * @param array $idx  root、colls、desc（rowidの列も含む）
   * @param array $key  列の値…、rowid
   */
  public function indexInsert(array $idx, array $key): void {
    $this->spill();
    $path = [];
    $p = $this->page($idx['root']);
    while (true) {
      $i = $this->bound($p, $key, $idx, false);
      if ($i < count($p->cells) && count($this->key($p, $i)) === count($key)
          && Record::compareKeys($this->key($p, $i), $key, $idx['colls'], $idx['desc']) === 0) return;
      if ($p->isLeaf()) break;
      $path[] = [$p, $i];
      $p = $this->page($this->child($p, $i));
    }
    $cell = $this->makeCell(Record::encode($key), null);
    array_splice($p->cells, $i, 0, [$cell]);
    array_splice($p->dec, $i, 0, [$key]);
    $p->size += strlen($cell) + 2;
    $this->touch($p);
    $this->fix($path, $p);
  }

  /**
   * キーの前方一致の項目を探す（一意の制約の確認用）
   *
   * @param int|null $self  除くrowid
   * @return int|null  見つけた項目のrowid
   */
  public function indexFind(array $idx, array $prefix, ?int $self = null): ?int {
    $p = $this->page($idx['root']);
    while (true) {
      $i = $this->bound($p, $prefix, $idx, false);
      if ($i < count($p->cells)) {
        $k = $this->key($p, $i);
        if (Record::compareKeys($k, $prefix, $idx['colls'], $idx['desc']) === 0) {
          $id = end($k);
          if ($id !== $self) return $id;
          // 自分自身：他にも有るかもしれないので全部を見る
          foreach ($this->indexScan($idx, $prefix, true, $prefix, true) as $k2) {
            if (end($k2) !== $self) return end($k2);
          }
          return null;
        }
      }
      if ($p->isLeaf()) return null;
      $p = $this->page($this->child($p, $i));
    }
  }

  /** インデックスからキーを消す */
  public function indexDelete(array $idx, array $key): bool {
    $this->spill();
    $path = [];
    $p = $this->page($idx['root']);
    while (true) {
      $i = $this->bound($p, $key, $idx, false);
      if ($i < count($p->cells) && Record::compareKeys($this->key($p, $i), $key, $idx['colls'], $idx['desc']) === 0) break;
      if ($p->isLeaf()) return false;
      $path[] = [$p, $i];
      $p = $this->page($this->child($p, $i));
    }
    $this->decAll($p);
    if ($p->isLeaf()) {
      $this->freeOverflow($p, $p->cells[$i]);
      $p->size -= strlen($p->cells[$i]) + 2;
      array_splice($p->cells, $i, 1);
      array_splice($p->dec, $i, 1);
      $this->touch($p);
      $this->fix($path, $p);
      return true;
    }

    // 内部のページ：左のツリーの一番大きいキーと置き換える
    $pathL = array_merge($path, [[$p, $i]]);
    $q = $this->page($p->left[$i]);
    while (!$q->isLeaf()) {
      $pathL[] = [$q, count($q->cells)];
      $q = $this->page($q->right);
    }
    $this->decAll($q);
    $last = count($q->cells) - 1;
    $cell = $q->cells[$last];
    $dec = $this->key($q, $last);
    $q->size -= strlen($cell) + 2;
    array_splice($q->cells, $last, 1);
    array_splice($q->dec, $last, 1);
    $this->freeOverflow($p, $p->cells[$i]);
    $p->size += strlen($cell) - strlen($p->cells[$i]);
    $p->cells[$i] = $cell;
    $p->dec[$i] = $dec;
    $this->touch($p);
    $this->touch($q);
    if ($this->fix($pathL, $q) > count($path)) $this->fix($path, $p);
    return true;
  }

  /** decの配列をセルと同じ長さにする（array_spliceの前に） */
  private function decAll(Page $p): void {
    for ($i = 0, $n = count($p->cells); $i < $n; $i++) $p->dec[$i] ??= null;
    ksort($p->dec);
  }

  /**
   * インデックスの範囲
   *
   * @param array $idx
   * @param array|null $lo  最小のキー（前方一致）
   * @param bool $loInc  最小を含む
   * @param array|null $hi  最大のキー（前方一致）
   * @param bool $hiInc  最大を含む
   * @return \Generator  キー（列の値…、rowid）
   */
  public function indexScan(array $idx, ?array $lo = null, bool $loInc = true, ?array $hi = null, bool $hiInc = true): \Generator {
    $stop = false;
    yield from $this->walkIndex($idx['root'], $idx, $lo, $loInc, $hi, $hiInc, $stop);
  }

  private function walkIndex(int $pgno, array $idx, ?array $lo, bool $loInc, ?array $hi, bool $hiInc, bool &$stop): \Generator {
    $p = $this->page($pgno);
    $n = count($p->cells);
    $i = $lo === null ? 0 : $this->bound($p, $lo, $idx, !$loInc);
    $leaf = $p->isLeaf();
    for (; $i <= $n; $i++) {
      if (!$leaf) {
        yield from $this->walkIndex($this->child($p, $i), $idx, $lo, $loInc, $hi, $hiInc, $stop);
        if ($stop) return;
      }
      if ($i === $n) return;
      $k = $this->key($p, $i);
      if ($hi !== null) {
        $c = Record::compareKeys($k, $hi, $idx['colls'], $idx['desc']);
        if ($c > 0 || (!$hiInc && $c === 0)) {
          $stop = true;
          return;
        }
      }
      yield $k;
    }
  }

  ///////////////
  // 釣り合い

  /**
   * 変更したページを直す（溢れた・少なくなったら兄弟と分け直す）
   *
   * @param array $path  親のページと位置の配列（ルートから）
   * @param Page $p  変更したページ
   * @return int  確認を終えた深さ（パスの長さ）
   */
  private function fix(array $path, Page $p): int {
    while (true) {
      $cap = $this->capacity($p);
      $over = $p->size > $cap;
      if (empty($path)) {
        if ($over) {
          $c = $this->deeper($p);
          $path = [[$p, 0]];
          $p = $c;
          continue;
        }
        if (!$p->isLeaf() && empty($p->cells)) $this->shallower($p);
        return 0;
      }
      $under = $p->size < intdiv($cap, 3);
      if (!$over && !$under) return count($path);
      [$parent, $idx] = array_pop($path);
      if (!$over && empty($parent->cells)) {
        // 兄弟が無い
        $p = $parent;
        continue;
      }
      $this->balance($parent, $idx);
      $p = $parent;
    }
  }

  /** ルートが溢れた：中身を新しいページに移して、ルートを1段上にする */
  private function deeper(Page $root): Page {
    $c = $this->newPage($root->type);
    $c->cells = $root->cells;
    $c->left = $root->left;
    $c->keys = $root->keys;
    $c->dec = $root->dec;
    $c->right = $root->right;
    $c->size = $root->size;
    $root->type = $root->isTable() ? self::TABLE_INTERIOR : self::INDEX_INTERIOR;
    $root->cells = $root->left = $root->keys = $root->dec = [];
    $root->size = 0;
    $root->right = $c->pgno;
    $this->touch($root);
    return $c;
  }

  /** ルートの子が1つだけ：子の中身をルートに入れる（入れば） */
  private function shallower(Page $root): void {
    $c = $this->page($root->right);
    $cap = $this->pager->usable - ($root->pgno === 1 ? 100 : 0) - ($c->isLeaf() ? 8 : 12);
    if ($c->size > $cap) return;
    $this->decAll($c);
    $root->type = $c->type;
    $root->cells = $c->cells;
    $root->left = $c->left;
    $root->keys = $c->keys;
    $root->dec = $c->dec;
    $root->right = $c->right;
    $root->size = $c->size;
    $this->freePage($c->pgno);
    $this->touch($root);
  }

  /** 親の$idx番目の子とその兄弟（最大3つ）のセルを分け直す */
  private function balance(Page $parent, int $idx): void {
    $n = count($parent->cells);
    $first = max(0, $idx - 1);
    $last = min($n, $first + 2);
    $first = max(0, $last - 2);
    $sibs = [];
    for ($j = $first; $j <= $last; $j++) $sibs[] = $this->page($this->child($parent, $j));
    $leaf = $sibs[0]->isLeaf();
    $table = $sibs[0]->isTable();
    $type = $sibs[0]->type;
    if (!$table) $this->decAll($parent);

    // 全部のセル（間の区切りも）
    $items = [];
    $lastRight = 0;
    $ns = count($sibs);
    foreach ($sibs as $j => $s) {
      if ($s->isLeaf() !== $leaf) throw new DbException('データベースが壊れています（ツリーの深さ）', 11, 'HY000');
      foreach ($s->cells as $i => $c) {
        $items[] = [$c, $leaf ? 0 : $s->left[$i], $table ? $s->keys[$i] : 0, $table ? null : ($s->dec[$i] ?? null)];
      }
      if (!$leaf) $lastRight = $s->right;
      if ($j < $ns - 1) {
        $pi = $first + $j;
        if ($table && $leaf) continue;
        if ($table) {
          $items[] = [Record::putVarint($parent->keys[$pi]), $s->right, $parent->keys[$pi], null];
        } else {
          $items[] = [$parent->cells[$pi], $leaf ? 0 : $s->right, 0, $parent->dec[$pi] ?? null];
        }
      }
    }

    $cap = $this->pager->usable - ($leaf ? 8 : 12);
    $extra = $leaf ? 2 : 6;
    [$groups, $divs] = $this->distribute($items, $cap, !($table && $leaf), $extra);
    $k = count($groups);

    $pgs = [];
    for ($j = 0; $j < $k; $j++) $pgs[] = $j < $ns ? $sibs[$j] : $this->newPage($type);
    for ($j = $k; $j < $ns; $j++) $this->freePage($sibs[$j]->pgno);

    foreach ($groups as $j => $g) {
      $pg = $pgs[$j];
      $pg->type = $type;
      $pg->cells = $pg->left = $pg->keys = $pg->dec = [];
      $pg->size = 0;
      foreach ($g as $it) {
        $pg->cells[] = $it[0];
        if (!$leaf) $pg->left[] = $it[1];
        if ($table) $pg->keys[] = $it[2];
        else $pg->dec[] = $it[3];
        $pg->size += strlen($it[0]) + $extra;
      }
      if (!$leaf) $pg->right = $j < $k - 1 ? $divs[$j][1] : $lastRight;
      $this->touch($pg);
    }

    // 親の区切り
    $cells = $left = $keys = $dec = [];
    for ($j = 0; $j < $k - 1; $j++) {
      if ($table) {
        $key = $leaf ? end($groups[$j])[2] : $divs[$j][2];
        $cells[] = Record::putVarint($key);
        $keys[] = $key;
      } else {
        $cells[] = $divs[$j][0];
        $dec[] = $divs[$j][3];
      }
      $left[] = $pgs[$j]->pgno;
    }
    array_splice($parent->cells, $first, $ns - 1, $cells);
    array_splice($parent->left, $first, $ns - 1, $left);
    if ($table) array_splice($parent->keys, $first, $ns - 1, $keys);
    else array_splice($parent->dec, $first, $ns - 1, $dec);
    $slot = $first + $k - 1;
    if ($slot < count($parent->cells)) $parent->left[$slot] = $pgs[$k - 1]->pgno;
    else $parent->right = $pgs[$k - 1]->pgno;
    $parent->size = 0;
    foreach ($parent->cells as $c) $parent->size += strlen($c) + 6;
    $this->touch($parent);
  }

  /**
   * セルをページに分ける
   *
   * @param bool $promote  グループの間のセルを親の区切りにする（テーブルの葉以外）
   * @return array  [グループの配列, 区切りの配列]
   */
  private function distribute(array $items, int $cap, bool $promote, int $extra): array {
    $sizes = [];
    $total = 0;
    $max = 0;
    foreach ($items as $it) {
      $s = strlen($it[0]) + $extra;
      $sizes[] = $s;
      $total += $s;
      $max = max($max, $s);
    }
    $pack = function(int $limit) use ($items, $sizes, $promote): array {
      $groups = $divs = $cur = [];
      $cs = 0;
      foreach ($items as $i => $it) {
        if ($cur && $cs + $sizes[$i] > $limit) {
          $groups[] = $cur;
          $cur = [];
          $cs = 0;
          if ($promote) {
            $divs[] = $it;
            continue;
          }
        }
        $cur[] = $it;
        $cs += $sizes[$i];
      }
      if ($cur || empty($groups)) {
        $groups[] = $cur;
      } else if ($promote) {
        $groups[] = [array_pop($divs)];
      }
      return [$groups, $divs];
    };
    $res = $pack($cap);
    $k = count($res[0]);
    if ($k > 1) {
      // なるべく同じ大きさに
      $target = max($max, intdiv($total, $k));
      $step = max(1, intdiv($cap - $target, 8));
      for ($limit = $target; $limit < $cap; $limit += $step) {
        $try = $pack($limit);
        if (count($try[0]) === $k) {
          $res = $try;
          break;
        }
      }
    }
    return $res;
  }
}