"""
p100 — Design In-Memory File System (LC 588)

INVARIANT (one node type): a Node is either a directory (content == "" and
  children may be nonempty) or a file (content != "" and children is empty).

INVARIANT (path parsing): split on "/" and drop empty strings. The root path
  "/" yields the empty list; operating on the root is "no parts to walk".

INVARIANT (single helper): all four ops route through _walk(parts, create);
  files and directories are distinguished only at the leaf.
"""
from __future__ import annotations

import random
from typing import Dict, List, Optional


class Node:
    __slots__ = ("children", "content")

    def __init__(self) -> None:
        self.children: Dict[str, "Node"] = {}
        self.content: str = ""


class FileSystem:
    """Trie of nodes with a unified _walk helper."""

    def __init__(self) -> None:
        self.root = Node()

    def _parts(self, path: str) -> List[str]:
        return [p for p in path.split("/") if p]

    def _walk(self, parts: List[str], create: bool = False) -> Optional[Node]:
        node = self.root
        for p in parts:
            if p not in node.children:
                if not create:
                    return None
                node.children[p] = Node()
            node = node.children[p]
        return node

    def ls(self, path: str) -> List[str]:
        parts = self._parts(path)
        node = self._walk(parts)
        if node is None:
            return []
        # If file, return [basename].
        if node.content != "":
            return [parts[-1]]
        return sorted(node.children.keys())

    def mkdir(self, path: str) -> None:
        self._walk(self._parts(path), create=True)

    def addContentToFile(self, path: str, content: str) -> None:
        node = self._walk(self._parts(path), create=True)
        assert node is not None
        node.content += content

    def readContentFromFile(self, path: str) -> str:
        node = self._walk(self._parts(path))
        assert node is not None
        return node.content


class FileSystemBrute:
    """Flat-dicts oracle. Tracks every existing path as either dir or file."""

    def __init__(self) -> None:
        # path -> ("dir", None) or ("file", content)
        self.entries: Dict[str, tuple] = {"/": ("dir", None)}

    def _ensure_dirs(self, path: str) -> None:
        parts = [p for p in path.split("/") if p]
        cur = ""
        for p in parts:
            cur += "/" + p
            if cur not in self.entries:
                self.entries[cur] = ("dir", None)

    def ls(self, path: str) -> List[str]:
        if path not in self.entries:
            return []
        kind, content = self.entries[path]
        if kind == "file":
            return [path.rsplit("/", 1)[1]]
        # Directory: gather direct children.
        prefix = path.rstrip("/") + "/"
        if path == "/":
            prefix = "/"
        out = set()
        for k in self.entries:
            if k == path:
                continue
            if k.startswith(prefix):
                rest = k[len(prefix):]
                if "/" in rest:
                    out.add(rest.split("/", 1)[0])
                else:
                    out.add(rest)
        return sorted(out)

    def mkdir(self, path: str) -> None:
        self._ensure_dirs(path)

    def addContentToFile(self, path: str, content: str) -> None:
        parent = path.rsplit("/", 1)[0]
        if parent == "":
            parent = "/"
        if parent != "/":
            self._ensure_dirs(parent)
        if path in self.entries:
            _, old = self.entries[path]
            self.entries[path] = ("file", (old or "") + content)
        else:
            self.entries[path] = ("file", content)

    def readContentFromFile(self, path: str) -> str:
        return self.entries[path][1]


def edge_cases() -> None:
    fs = FileSystem()
    assert fs.ls("/") == []
    fs.mkdir("/a/b/c")
    assert fs.ls("/") == ["a"]
    assert fs.ls("/a") == ["b"]
    assert fs.ls("/a/b") == ["c"]
    fs.addContentToFile("/a/b/c/d", "hello")
    assert fs.ls("/a/b/c") == ["d"]
    # ls on a file returns [filename].
    assert fs.ls("/a/b/c/d") == ["d"]
    assert fs.readContentFromFile("/a/b/c/d") == "hello"
    # Append.
    fs.addContentToFile("/a/b/c/d", " world")
    assert fs.readContentFromFile("/a/b/c/d") == "hello world"
    # Create file without mkdir first.
    fs.addContentToFile("/x/y/z", "data")
    assert fs.ls("/x/y") == ["z"]
    assert fs.readContentFromFile("/x/y/z") == "data"


def _random_path(rng: random.Random, max_depth: int = 3) -> str:
    depth = rng.randint(1, max_depth)
    parts = [rng.choice(["a", "b", "c", "d"]) for _ in range(depth)]
    return "/" + "/".join(parts)


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(100):
        a = FileSystem()
        b = FileSystemBrute()
        # Track which paths are files vs dirs so we don't violate fs semantics
        # (avoid e.g. mkdir on an existing file path).
        committed: Dict[str, str] = {}  # path -> "dir" | "file"
        n_ops = rng.randint(1, 25)
        for _ in range(n_ops):
            op = rng.choice(["mkdir", "add", "ls", "read"])
            if op == "mkdir":
                p = _random_path(rng)
                # Skip if any path on the chain is a file.
                parts = [x for x in p.split("/") if x]
                bad = False
                cur = ""
                for x in parts:
                    cur += "/" + x
                    if committed.get(cur) == "file":
                        bad = True
                        break
                if bad:
                    continue
                cur = ""
                for x in parts:
                    cur += "/" + x
                    committed.setdefault(cur, "dir")
                a.mkdir(p)
                b.mkdir(p)
            elif op == "add":
                p = _random_path(rng)
                parts = [x for x in p.split("/") if x]
                # Parent path components must not be files.
                bad = False
                cur = ""
                for x in parts[:-1]:
                    cur += "/" + x
                    if committed.get(cur) == "file":
                        bad = True
                        break
                if bad or committed.get(p) == "dir":
                    continue
                cur = ""
                for x in parts[:-1]:
                    cur += "/" + x
                    committed.setdefault(cur, "dir")
                committed[p] = "file"
                content = rng.choice(["x", "y", "ab"])
                a.addContentToFile(p, content)
                b.addContentToFile(p, content)
            elif op == "ls":
                # Pick a known path or root.
                if committed and rng.random() < 0.7:
                    p = rng.choice(list(committed.keys()))
                else:
                    p = "/"
                ra = a.ls(p)
                rb = b.ls(p)
                assert ra == rb, (p, ra, rb, committed)
            elif op == "read":
                files = [k for k, v in committed.items() if v == "file"]
                if not files:
                    continue
                p = rng.choice(files)
                assert a.readContentFromFile(p) == b.readContentFromFile(p)


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")