<?php

class TreeBuilder
{
  public function build(array $snapshot): array
  {
    $root = ['type' => 'dir', 'name' => '', 'children' => []];

    foreach ($snapshot as $path => $blobId) {
      $parts = explode('/', $path);
      $node = &$root;

      foreach ($parts as $i => $part) {
        $isLast = ($i === count($parts) - 1);

        if ($isLast) {
          $node['children'][$part] = ['type' => 'file', 'name' => $part, 'path' => $path, 'blob_id' => $blobId];
        } else {
          if (!isset($node['children'][$part])) {
            $node['children'][$part] = ['type' => 'dir', 'name' => $part, 'children' => []];
          }
          $node = &$node['children'][$part];
        }
      }
    }

    $this->sortTree($root);
    return $root;
  }

  private function sortTree(array &$node): void
  {
    if (($node['type'] ?? '') !== 'dir') return;
    $children = $node['children'] ?? [];

    uksort($children, function($a, $b) use ($children) {
      $ta = $children[$a]['type'];
      $tb = $children[$b]['type'];
      if ($ta !== $tb) return $ta === 'dir' ? -1 : 1;
      return strcmp($a, $b);
    });

    $node['children'] = $children;
    foreach ($node['children'] as &$child) $this->sortTree($child);
  }

  public function listDir(array $tree, string $dirPath): array
  {
    $dirPath = trim($dirPath, '/');
    if ($dirPath === '') return array_values($tree['children'] ?? []);

    $parts = explode('/', $dirPath);
    $node = $tree;
    foreach ($parts as $p) {
      if (!isset($node['children'][$p]) || $node['children'][$p]['type'] !== 'dir') return [];
      $node = $node['children'][$p];
    }
    return array_values($node['children'] ?? []);
  }
}