9. File System Intermediate → Advanced

interface NodeVisitor {
  void visitFile(File f);
  void visitDirectory(Directory d);
}

abstract class FileSystemNode {
  String name;
  Directory parent;
  abstract void accept(NodeVisitor v);
}

class FileSystem {
  void createFile(Path path);
  void createDirectory(Path path);
  void delete(Path path, boolean recursive);
  void move(Path source, Path destination);
  byte[] read(Path path);
  void write(Path path, byte[] data);
  List<String> list(Path directoryPath);
  List<Path> search(Path root, SearchCriteria criteria);
  long diskUsage(Path root);
}

interface NodeVisitor {
  void visitFile(File f);
  void visitDirectory(Directory d);
}

abstract class FileSystemNode {
  String name;
  Directory parent;
  abstract void accept(NodeVisitor v);
}

class FileSystem {
  void createFile(Path path);
  void createDirectory(Path path);
  void delete(Path path, boolean recursive);
  void move(Path source, Path destination);
  byte[] read(Path path);
  void write(Path path, byte[] data);
  List<String> list(Path directoryPath);
  List<Path> search(Path root, SearchCriteria criteria);
  long diskUsage(Path root);
}

class NodeVisitor {
public:
  virtual void visitFile(const File& f) = 0;
  virtual void visitDirectory(const Directory& d) = 0;
};

class FileSystemNode {
public:
  std::string name;
  std::shared_ptr<Directory> parent;
  virtual void accept(NodeVisitor& v) = 0;
};

class FileSystem {
public:
  void createFile(const Path& path);
  void createDirectory(const Path& path);
  void deleteNode(const Path& path, bool recursive);
  void move(const Path& source, const Path& destination);
  std::vector<uint8_t> read(const Path& path);
  void write(const Path& path, const std::vector<uint8_t>& data);
  std::vector<std::string> list(const Path& directoryPath);
  std::vector<Path> search(const Path& root, const SearchCriteria& criteria);
  long diskUsage(const Path& root);
};

class NodeVisitor {
  visitFile(f) { throw new Error('not implemented'); }
  visitDirectory(d) { throw new Error('not implemented'); }
}

class FileSystemNode {
  constructor() {
    this.name = null;
    this.parent = null;
  }
  accept(v) { throw new Error('not implemented'); }
}

class FileSystem {
  createFile(path) {}
  createDirectory(path) {}
  delete(path, recursive) {}
  move(source, destination) {}
  read(path) {}
  write(path, data) {}
  list(directoryPath) {}
  search(root, criteria) {}
  diskUsage(root) {}
}

interface NodeVisitor {
  visitFile(f: File): void;
  visitDirectory(d: Directory): void;
}

abstract class FileSystemNode {
  name: string;
  parent: Directory | null;
  abstract accept(v: NodeVisitor): void;
}

class FileSystem {
  createFile(path: Path): void {}
  createDirectory(path: Path): void {}
  delete(path: Path, recursive: boolean): void {}
  move(source: Path, destination: Path): void {}
  read(path: Path): Uint8Array { return new Uint8Array(); }
  write(path: Path, data: Uint8Array): void {}
  list(directoryPath: Path): string[] { return []; }
  search(root: Path, criteria: SearchCriteria): Path[] { return []; }
  diskUsage(root: Path): number { return 0; }
}

FileSystem.move(source, destination):
  srcParent = resolveParent(source)
  destParent = resolveParent(destination)
  node = srcParent.getChild(source.lastSegment)

  if node is Directory and destination.isDescendantOf(source):
    throw IllegalMoveException("cannot move a directory into its own subtree")

  // lock ordering: always acquire in canonical-path order to prevent
  // an ABBA deadlock against a concurrent move() going the other direction
  (first, second) = orderByCanonicalPath(srcParent, destParent)
  lock(first); lock(second)
  try:
    srcParent.removeChild(node.name)
    node.parent = destParent
    destParent.addChild(node)
  finally:
    unlock(second); unlock(first)

DiskUsageVisitor.visitDirectory(d):
  total = 0
  for child in d.children.values():
    child.accept(this)          // recurses; visitFile adds file.size directly
    total += this.lastSize
  this.lastSize = total

void move(Path source, Path destination) throws IllegalMoveException {
  Directory srcParent = resolveParent(source);
  Directory destParent = resolveParent(destination);
  FileSystemNode node = srcParent.getChild(source.lastSegment());

  if (node instanceof Directory && destination.isDescendantOf(source)) {
    throw new IllegalMoveException("cannot move a directory into its own subtree");
  }

  // lock ordering: always acquire in canonical-path order to prevent
  // an ABBA deadlock against a concurrent move() going the other direction
  Directory[] ordered = orderByCanonicalPath(srcParent, destParent);
  Directory first = ordered[0], second = ordered[1];
  lock(first); lock(second);
  try {
    srcParent.removeChild(node.getName());
    node.setParent(destParent);
    destParent.addChild(node);
  } finally {
    unlock(second); unlock(first);
  }
}

void visitDirectory(Directory d) {
  long total = 0;
  for (FileSystemNode child : d.getChildren().values()) {
    child.accept(this);              // recurses; visitFile adds file.size directly
    total += this.lastSize;
  }
  this.lastSize = total;
}

void FileSystem::move(const Path& source, const Path& destination) {
  auto srcParent = resolveParent(source);
  auto destParent = resolveParent(destination);
  auto node = srcParent->getChild(source.lastSegment());

  if (std::dynamic_pointer_cast<Directory>(node) && destination.isDescendantOf(source)) {
    throw IllegalMoveException("cannot move a directory into its own subtree");   // throws IllegalMoveException
  }

  // lock ordering: always acquire in canonical-path order to prevent
  // an ABBA deadlock against a concurrent move() going the other direction
  auto [first, second] = orderByCanonicalPath(srcParent, destParent);
  lock(first); lock(second);
  try {
    srcParent->removeChild(node->name);
    node->parent = destParent;
    destParent->addChild(node);
  } catch (...) {
    unlock(second); unlock(first);
    throw;
  }
  unlock(second); unlock(first);
}

void DiskUsageVisitor::visitDirectory(const Directory& d) {
  long total = 0;
  for (auto& [name, child] : d.children()) {
    child->accept(*this);              // recurses; visitFile adds file.size directly
    total += lastSize_;
  }
  lastSize_ = total;
}

move(source, destination) {
  const srcParent = this.resolveParent(source);
  const destParent = this.resolveParent(destination);
  const node = srcParent.getChild(source.lastSegment);

  if (node instanceof Directory && destination.isDescendantOf(source)) {
    throw new Error("cannot move a directory into its own subtree");   // IllegalMoveException
  }

  // lock ordering: always acquire in canonical-path order to prevent
  // an ABBA deadlock against a concurrent move() going the other direction
  const [first, second] = orderByCanonicalPath(srcParent, destParent);
  lock(first); lock(second);
  try {
    srcParent.removeChild(node.name);
    node.parent = destParent;
    destParent.addChild(node);
  } finally {
    unlock(second); unlock(first);
  }
}

visitDirectory(d) {
  let total = 0;
  for (const child of d.children.values()) {
    child.accept(this);              // recurses; visitFile adds file.size directly
    total += this.lastSize;
  }
  this.lastSize = total;
}

move(source: Path, destination: Path): void {
  const srcParent: Directory = this.resolveParent(source);
  const destParent: Directory = this.resolveParent(destination);
  const node: FileSystemNode = srcParent.getChild(source.lastSegment);

  if (node instanceof Directory && destination.isDescendantOf(source)) {
    throw new Error("cannot move a directory into its own subtree");    // IllegalMoveException
  }

  // lock ordering: always acquire in canonical-path order to prevent
  // an ABBA deadlock against a concurrent move() going the other direction
  const [first, second] = orderByCanonicalPath(srcParent, destParent);
  lock(first); lock(second);
  try {
    srcParent.removeChild(node.name);
    node.parent = destParent;
    destParent.addChild(node);
  } finally {
    unlock(second); unlock(first);
  }
}

visitDirectory(d: Directory): void {
  let total = 0;
  for (const child of d.children.values()) {
    child.accept(this);               // recurses; visitFile adds file.size directly
    total += this.lastSize;
  }
  this.lastSize = total;
}

// File System -- full LLD implementation with demo.
// Single-file Java translation of the Mermaid class diagram in section J.
// No concurrency badge on this problem -- kept single-threaded; the lock-ordering idea in the
// move() pseudocode is preserved only as commentary, not as real mutexes.
import java.util.*;

public class p9 {

    // ---------- Path (value object) ----------
    /** Normalized location, independent of the live tree. Says nothing about whether it exists. */
    static final class Path {
        final List<String> segments;
        Path(List<String> segments) { this.segments = List.copyOf(segments); }
        static Path of(String slashSeparated) {
            List<String> parts = new ArrayList<>();
            for (String s : slashSeparated.split("/")) if (!s.isEmpty()) parts.add(s);
            return new Path(parts);
        }
        Path parent() { return new Path(segments.subList(0, Math.max(0, segments.size() - 1))); }
        String lastSegment() { return segments.get(segments.size() - 1); }
        Path resolve(String childName) {
            List<String> next = new ArrayList<>(segments);
            next.add(childName);
            return new Path(next);
        }
        boolean isDescendantOf(Path other) {
            if (other.segments.size() >= segments.size()) return false;
            for (int i = 0; i < other.segments.size(); i++) {
                if (!other.segments.get(i).equals(segments.get(i))) return false;
            }
            return true;
        }
        public String toString() { return "/" + String.join("/", segments); }
    }

    // ---------- NodeVisitor (interface) ----------
    interface NodeVisitor {
        void visitFile(File f);
        void visitDirectory(Directory d);
    }

    // ---------- FileSystemNode (abstract) ----------
    /** Common identity for anything in the tree. Aggregate ops are delegated to a NodeVisitor. */
    static abstract class FileSystemNode {
        String name;
        Directory parent;
        FileSystemNode(String name, Directory parent) { this.name = name; this.parent = parent; }
        abstract void accept(NodeVisitor visitor);
    }

    // ---------- File (leaf) ----------
    static final class File extends FileSystemNode {
        byte[] content = new byte[0];
        File(String name, Directory parent) { super(name, parent); }
        int size() { return content.length; }
        byte[] read() { return content; }
        void write(byte[] data) { content = data; }
        void accept(NodeVisitor visitor) { visitor.visitFile(this); }
    }

    // ---------- Directory (composite) ----------
    static final class Directory extends FileSystemNode {
        final Map<String, FileSystemNode> children = new LinkedHashMap<>();
        Directory(String name, Directory parent) { super(name, parent); }
        void addChild(FileSystemNode node) { children.put(node.name, node); }
        void removeChild(String name) { children.remove(name); }
        FileSystemNode getChild(String name) { return children.get(name); }
        void accept(NodeVisitor visitor) { visitor.visitDirectory(this); }
    }

    // ---------- DirectoryIterator ----------
    /**
     * Snapshot iterator: copies the child list at creation time, so a concurrent addChild/removeChild
     * on the underlying Directory during iteration cannot throw ConcurrentModificationException. This
     * is a deliberate policy choice (snapshot over fail-fast) since the directory is a live, mutable map.
     */
    static final class DirectoryIterator implements Iterator<FileSystemNode> {
        private final List<FileSystemNode> snapshot;
        private int index = 0;
        DirectoryIterator(Directory directory) { this.snapshot = new ArrayList<>(directory.children.values()); }
        public boolean hasNext() { return index < snapshot.size(); }
        public FileSystemNode next() {
            if (!hasNext()) throw new NoSuchElementException();
            return snapshot.get(index++);
        }
    }

    // ---------- NodeVisitor implementations ----------
    static final class DiskUsageVisitor implements NodeVisitor {
        private long lastSize;
        long compute(FileSystemNode node) { node.accept(this); return lastSize; }
        public void visitFile(File f) { lastSize = f.size(); }
        public void visitDirectory(Directory d) {
            long total = 0;
            DirectoryIterator it = new DirectoryIterator(d);
            while (it.hasNext()) {
                FileSystemNode child = it.next();
                child.accept(this); // recurses; visitFile sets lastSize directly for leaves
                total += lastSize;
            }
            lastSize = total;
        }
    }

    interface SearchCriteria { boolean matches(FileSystemNode node); }

    static final class SearchVisitor implements NodeVisitor {
        private final SearchCriteria criteria;
        private final Path currentBase;
        private final List<Path> matches = new ArrayList<>();
        SearchVisitor(SearchCriteria criteria, Path base) { this.criteria = criteria; this.currentBase = base; }

        List<Path> search(FileSystemNode node) { walk(node, currentBase); return matches; }

        private void walk(FileSystemNode node, Path path) {
            if (criteria.matches(node)) matches.add(path);
            if (node instanceof Directory) {
                Directory d = (Directory) node;
                DirectoryIterator it = new DirectoryIterator(d);
                while (it.hasNext()) {
                    FileSystemNode child = it.next();
                    walk(child, path.resolve(child.name));
                }
            }
        }
        public void visitFile(File f) { /* traversal handled by walk(); visitor methods unused here */ }
        public void visitDirectory(Directory d) { /* see walk() */ }
    }

    // ---------- FileSystem (facade) ----------
    static final class FileSystem {
        final Directory root = new Directory("", null);

        private Directory resolveParent(Path path) {
            Directory current = root;
            for (int i = 0; i < path.segments.size() - 1; i++) {
                FileSystemNode next = current.getChild(path.segments.get(i));
                if (!(next instanceof Directory)) throw new IllegalArgumentException("No such directory: " + path);
                current = (Directory) next;
            }
            return current;
        }

        private FileSystemNode resolve(Path path) {
            if (path.segments.isEmpty()) return root;
            Directory parentDir = resolveParent(path);
            FileSystemNode node = parentDir.getChild(path.lastSegment());
            if (node == null) throw new IllegalArgumentException("No such path: " + path);
            return node;
        }

        void createFile(Path path) {
            Directory parentDir = resolveParent(path);
            parentDir.addChild(new File(path.lastSegment(), parentDir));
        }

        void createDirectory(Path path) {
            Directory parentDir = resolveParent(path);
            parentDir.addChild(new Directory(path.lastSegment(), parentDir));
        }

        void delete(Path path, boolean recursive) {
            Directory parentDir = resolveParent(path);
            FileSystemNode node = parentDir.getChild(path.lastSegment());
            if (node instanceof Directory && !((Directory) node).children.isEmpty() && !recursive) {
                throw new IllegalStateException("Directory not empty; pass recursive=true to delete: " + path);
            }
            parentDir.removeChild(path.lastSegment());
        }

        byte[] read(Path path) {
            FileSystemNode node = resolve(path);
            if (!(node instanceof File)) throw new IllegalArgumentException("Not a file: " + path);
            return ((File) node).read();
        }

        void write(Path path, byte[] data) {
            FileSystemNode node = resolve(path);
            if (!(node instanceof File)) throw new IllegalArgumentException("Not a file: " + path);
            ((File) node).write(data);
        }

        List<String> list(Path directoryPath) {
            FileSystemNode node = resolve(directoryPath);
            if (!(node instanceof Directory)) throw new IllegalArgumentException("Not a directory: " + directoryPath);
            List<String> names = new ArrayList<>();
            DirectoryIterator it = new DirectoryIterator((Directory) node);
            while (it.hasNext()) names.add(it.next().name);
            return names;
        }

        /**
         * Move source under destination's parent. Guards against moving a directory into its own
         * subtree (would create a cycle). No real threads exist in this single-threaded translation,
         * so the "lock in canonical-path order" step from the pseudocode is left as a comment only --
         * this is where a two-mutex ABBA-safe acquisition would go under a concurrent implementation.
         */
        void move(Path source, Path destination) {
            Directory srcParent = resolveParent(source);
            Directory destParent = resolveParent(destination);
            FileSystemNode node = srcParent.getChild(source.lastSegment());
            if (node == null) throw new IllegalArgumentException("No such path: " + source);

            if (node instanceof Directory && destination.isDescendantOf(source)) {
                throw new IllegalArgumentException("cannot move a directory into its own subtree");
            }

            // lock ordering would be established here by canonical path in a concurrent version
            srcParent.removeChild(node.name);
            node.name = destination.lastSegment();
            node.parent = destParent;
            destParent.addChild(node);
        }

        List<Path> search(Path root, SearchCriteria criteria) {
            FileSystemNode startNode = resolve(root);
            return new SearchVisitor(criteria, root).search(startNode);
        }

        long diskUsage(Path root) {
            FileSystemNode startNode = resolve(root);
            return new DiskUsageVisitor().compute(startNode);
        }
    }

    // ---------- Demo ----------
    public static void main(String[] args) {
        FileSystem fs = new FileSystem();
        fs.createDirectory(Path.of("/docs"));
        fs.createDirectory(Path.of("/docs/reports"));
        fs.createFile(Path.of("/docs/readme.txt"));
        fs.createFile(Path.of("/docs/reports/q1.csv"));
        fs.createFile(Path.of("/docs/reports/q2.csv"));
        fs.createDirectory(Path.of("/media"));

        fs.write(Path.of("/docs/readme.txt"), "hello world".getBytes());
        fs.write(Path.of("/docs/reports/q1.csv"), "a,b,c\n1,2,3".getBytes());
        fs.write(Path.of("/docs/reports/q2.csv"), "x,y,z\n4,5,6\n7,8,9".getBytes());

        System.out.println("Listing /docs: " + fs.list(Path.of("/docs")));
        System.out.println("Listing /docs/reports: " + fs.list(Path.of("/docs/reports")));

        System.out.println("Read /docs/readme.txt: " + new String(fs.read(Path.of("/docs/readme.txt"))));

        System.out.println("Disk usage of /docs: " + fs.diskUsage(Path.of("/docs")) + " bytes");

        List<Path> csvFiles = fs.search(Path.of("/docs"), node -> node instanceof File && node.name.endsWith(".csv"));
        System.out.println("Search *.csv under /docs: " + csvFiles);

        System.out.println("\nMoving /docs/reports -> /media/reports");
        fs.move(Path.of("/docs/reports"), Path.of("/media/reports"));
        System.out.println("Listing /media: " + fs.list(Path.of("/media")));
        System.out.println("Listing /docs after move: " + fs.list(Path.of("/docs")));

        try {
            fs.move(Path.of("/media"), Path.of("/media/reports/media"));
        } catch (IllegalArgumentException e) {
            System.out.println("\nExpected rejection moving a directory into its own subtree: " + e.getMessage());
        }

        try {
            fs.delete(Path.of("/media"), false);
        } catch (IllegalStateException e) {
            System.out.println("Expected rejection deleting non-empty dir without recursive: " + e.getMessage());
        }
        fs.delete(Path.of("/media"), true);
        System.out.println("Root listing after recursive delete of /media: " + fs.list(Path.of("")));
    }
}

// File System -- full class-diagram implementation, single-threaded.
// No concurrency badge on this problem -- kept single-threaded; the lock-ordering idea in the
// move() pseudocode is preserved only as commentary, not as real mutexes.
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <memory>
#include <sstream>
#include <stdexcept>
#include <functional>

// ---------- Path (value object) ----------
class Path {
public:
    std::vector<std::string> segments;
    explicit Path(std::vector<std::string> segs = {}) : segments(std::move(segs)) {}

    static Path of(const std::string& slashSeparated) {
        std::vector<std::string> parts;
        std::stringstream ss(slashSeparated);
        std::string part;
        while (std::getline(ss, part, '/')) if (!part.empty()) parts.push_back(part);
        return Path(parts);
    }
    Path parentPath() const {
        if (segments.empty()) return Path();
        return Path(std::vector<std::string>(segments.begin(), segments.end() - 1));
    }
    std::string lastSegment() const { return segments.back(); }
    Path resolveChild(const std::string& childName) const {
        std::vector<std::string> next = segments;
        next.push_back(childName);
        return Path(next);
    }
    bool isDescendantOf(const Path& other) const {
        if (other.segments.size() >= segments.size()) return false;
        for (size_t i = 0; i < other.segments.size(); i++) {
            if (other.segments[i] != segments[i]) return false;
        }
        return true;
    }
    std::string toString() const {
        std::string out = "/";
        for (size_t i = 0; i < segments.size(); i++) { out += segments[i]; if (i + 1 < segments.size()) out += "/"; }
        return out;
    }
};

class File;
class Directory;

// ---------- NodeVisitor (interface) ----------
struct NodeVisitor {
    virtual ~NodeVisitor() = default;
    virtual void visitFile(File& f) = 0;
    virtual void visitDirectory(Directory& d) = 0;
};

// ---------- FileSystemNode (abstract) ----------
// Common identity for anything in the tree. Aggregate ops are delegated to a NodeVisitor.
class FileSystemNode {
public:
    std::string name;
    Directory* parent;
    FileSystemNode(std::string name_, Directory* parent_) : name(std::move(name_)), parent(parent_) {}
    virtual ~FileSystemNode() = default;
    virtual void accept(NodeVisitor& visitor) = 0;
};

// ---------- File (leaf) ----------
class File : public FileSystemNode {
public:
    std::string content;
    File(std::string name_, Directory* parent_) : FileSystemNode(std::move(name_), parent_) {}
    size_t size() const { return content.size(); }
    std::string read() const { return content; }
    void write(const std::string& data) { content = data; }
    void accept(NodeVisitor& visitor) override;
};

// ---------- Directory (composite) ----------
class Directory : public FileSystemNode {
public:
    std::map<std::string, std::shared_ptr<FileSystemNode>> children; // ordered by name
    Directory(std::string name_, Directory* parent_) : FileSystemNode(std::move(name_), parent_) {}
    void addChild(std::shared_ptr<FileSystemNode> node) { children[node->name] = node; }
    void removeChild(const std::string& name) { children.erase(name); }
    std::shared_ptr<FileSystemNode> getChild(const std::string& name) const {
        auto it = children.find(name);
        return it == children.end() ? nullptr : it->second;
    }
    void accept(NodeVisitor& visitor) override;
};

void File::accept(NodeVisitor& visitor) { visitor.visitFile(*this); }
void Directory::accept(NodeVisitor& visitor) { visitor.visitDirectory(*this); }

// ---------- DirectoryIterator ----------
// Snapshot iterator: copies the child list at creation time so a concurrent mutation of the
// underlying Directory during iteration can't invalidate iterators mid-walk (policy choice: snapshot).
class DirectoryIterator {
public:
    explicit DirectoryIterator(const Directory& dir) {
        for (auto& kv : dir.children) snapshot_.push_back(kv.second);
    }
    bool hasNext() const { return index_ < snapshot_.size(); }
    std::shared_ptr<FileSystemNode> next() { return snapshot_[index_++]; }
private:
    std::vector<std::shared_ptr<FileSystemNode>> snapshot_;
    size_t index_ = 0;
};

// ---------- NodeVisitor implementations ----------
class DiskUsageVisitor : public NodeVisitor {
public:
    long long compute(std::shared_ptr<FileSystemNode> node) { node->accept(*this); return lastSize_; }
    void visitFile(File& f) override { lastSize_ = (long long)f.size(); }
    void visitDirectory(Directory& d) override {
        long long total = 0;
        DirectoryIterator it(d);
        while (it.hasNext()) {
            auto child = it.next();
            child->accept(*this); // recurses; visitFile sets lastSize_ directly for leaves
            total += lastSize_;
        }
        lastSize_ = total;
    }
private:
    long long lastSize_ = 0;
};

using SearchCriteria = std::function<bool(const FileSystemNode&)>;

class SearchVisitor : public NodeVisitor {
public:
    SearchVisitor(SearchCriteria criteria, Path base) : criteria_(std::move(criteria)), base_(std::move(base)) {}

    std::vector<Path> search(std::shared_ptr<FileSystemNode> node) {
        walk(node, base_);
        return matches_;
    }
    void visitFile(File&) override {}      // traversal is driven by walk(), not the visitor dispatch
    void visitDirectory(Directory&) override {}
private:
    SearchCriteria criteria_;
    Path base_;
    std::vector<Path> matches_;

    void walk(std::shared_ptr<FileSystemNode> node, const Path& path) {
        if (criteria_(*node)) matches_.push_back(path);
        auto dir = std::dynamic_pointer_cast<Directory>(node);
        if (dir) {
            DirectoryIterator it(*dir);
            while (it.hasNext()) {
                auto child = it.next();
                walk(child, path.resolveChild(child->name));
            }
        }
    }
};

// ---------- FileSystem (facade) ----------
class FileSystem {
public:
    std::shared_ptr<Directory> root = std::make_shared<Directory>("", nullptr);

    void createFile(const Path& path) {
        auto parentDir = resolveParent(path);
        parentDir->addChild(std::make_shared<File>(path.lastSegment(), parentDir.get()));
    }

    void createDirectory(const Path& path) {
        auto parentDir = resolveParent(path);
        parentDir->addChild(std::make_shared<Directory>(path.lastSegment(), parentDir.get()));
    }

    void deleteNode(const Path& path, bool recursive) {
        auto parentDir = resolveParent(path);
        auto node = parentDir->getChild(path.lastSegment());
        auto dir = std::dynamic_pointer_cast<Directory>(node);
        if (dir && !dir->children.empty() && !recursive) {
            throw std::runtime_error("Directory not empty; pass recursive=true to delete: " + path.toString());
        }
        parentDir->removeChild(path.lastSegment());
    }

    std::string read(const Path& path) {
        auto node = resolve(path);
        auto file = std::dynamic_pointer_cast<File>(node);
        if (!file) throw std::runtime_error("Not a file: " + path.toString());
        return file->read();
    }

    void write(const Path& path, const std::string& data) {
        auto node = resolve(path);
        auto file = std::dynamic_pointer_cast<File>(node);
        if (!file) throw std::runtime_error("Not a file: " + path.toString());
        file->write(data);
    }

    std::vector<std::string> list(const Path& directoryPath) {
        auto node = resolve(directoryPath);
        auto dir = std::dynamic_pointer_cast<Directory>(node);
        if (!dir) throw std::runtime_error("Not a directory: " + directoryPath.toString());
        std::vector<std::string> names;
        DirectoryIterator it(*dir);
        while (it.hasNext()) names.push_back(it.next()->name);
        return names;
    }

    // Move source under destination's parent (destination's last segment becomes the new name).
    // Guards against moving a directory into its own subtree. No real threads exist in this
    // single-threaded translation, so canonical-path lock ordering is left as commentary only --
    // this is where a two-mutex ABBA-safe acquisition would go under a concurrent implementation.
    void move(const Path& source, const Path& destination) {
        auto srcParent = resolveParent(source);
        auto destParent = resolveParent(destination);
        auto node = srcParent->getChild(source.lastSegment());
        if (!node) throw std::runtime_error("No such path: " + source.toString());

        auto asDir = std::dynamic_pointer_cast<Directory>(node);
        if (asDir && destination.isDescendantOf(source)) {
            throw std::runtime_error("cannot move a directory into its own subtree");
        }

        // lock ordering would be established here by canonical path in a concurrent version
        srcParent->removeChild(node->name);
        node->name = destination.lastSegment();
        node->parent = destParent.get();
        destParent->addChild(node);
    }

    std::vector<Path> search(const Path& startPath, const SearchCriteria& criteria) {
        auto startNode = resolve(startPath);
        return SearchVisitor(criteria, startPath).search(startNode);
    }

    long long diskUsage(const Path& startPath) {
        auto startNode = resolve(startPath);
        return DiskUsageVisitor().compute(startNode);
    }

private:
    std::shared_ptr<Directory> resolveParent(const Path& path) {
        std::shared_ptr<Directory> current = root;
        for (size_t i = 0; i + 1 < path.segments.size(); i++) {
            auto next = std::dynamic_pointer_cast<Directory>(current->getChild(path.segments[i]));
            if (!next) throw std::runtime_error("No such directory in path: " + path.toString());
            current = next;
        }
        return current;
    }

    std::shared_ptr<FileSystemNode> resolve(const Path& path) {
        if (path.segments.empty()) return root;
        auto parentDir = resolveParent(path);
        auto node = parentDir->getChild(path.lastSegment());
        if (!node) throw std::runtime_error("No such path: " + path.toString());
        return node;
    }
};

static void printVec(const std::string& label, const std::vector<std::string>& v) {
    std::cout << label << ": [";
    for (size_t i = 0; i < v.size(); i++) { std::cout << v[i]; if (i + 1 < v.size()) std::cout << ", "; }
    std::cout << "]\n";
}

int main() {
    FileSystem fs;
    fs.createDirectory(Path::of("/docs"));
    fs.createDirectory(Path::of("/docs/reports"));
    fs.createFile(Path::of("/docs/readme.txt"));
    fs.createFile(Path::of("/docs/reports/q1.csv"));
    fs.createFile(Path::of("/docs/reports/q2.csv"));
    fs.createDirectory(Path::of("/media"));

    fs.write(Path::of("/docs/readme.txt"), "hello world");
    fs.write(Path::of("/docs/reports/q1.csv"), "a,b,c\n1,2,3");
    fs.write(Path::of("/docs/reports/q2.csv"), "x,y,z\n4,5,6\n7,8,9");

    printVec("Listing /docs", fs.list(Path::of("/docs")));
    printVec("Listing /docs/reports", fs.list(Path::of("/docs/reports")));

    std::cout << "Read /docs/readme.txt: " << fs.read(Path::of("/docs/readme.txt")) << "\n";
    std::cout << "Disk usage of /docs: " << fs.diskUsage(Path::of("/docs")) << " bytes\n";

    auto csvFiles = fs.search(Path::of("/docs"), [](const FileSystemNode& n) {
        return dynamic_cast<const File*>(&n) != nullptr && n.name.size() > 4 && n.name.substr(n.name.size() - 4) == ".csv";
    });
    std::cout << "Search *.csv under /docs: [";
    for (size_t i = 0; i < csvFiles.size(); i++) { std::cout << csvFiles[i].toString(); if (i + 1 < csvFiles.size()) std::cout << ", "; }
    std::cout << "]\n";

    std::cout << "\nMoving /docs/reports -> /media/reports\n";
    fs.move(Path::of("/docs/reports"), Path::of("/media/reports"));
    printVec("Listing /media", fs.list(Path::of("/media")));
    printVec("Listing /docs after move", fs.list(Path::of("/docs")));

    try {
        fs.move(Path::of("/media"), Path::of("/media/reports/media"));
    } catch (const std::exception& e) {
        std::cout << "\nExpected rejection moving a directory into its own subtree: " << e.what() << "\n";
    }

    try {
        fs.deleteNode(Path::of("/media"), false);
    } catch (const std::exception& e) {
        std::cout << "Expected rejection deleting non-empty dir without recursive: " << e.what() << "\n";
    }
    fs.deleteNode(Path::of("/media"), true);
    printVec("Root listing after recursive delete of /media", fs.list(Path::of("")));

    return 0;
}

// File System -- full class-diagram implementation, single-threaded.
// No concurrency badge on this problem -- kept single-threaded; the lock-ordering idea in the
// move() pseudocode is preserved only as commentary, not as real mutexes.
// Node-style, plain classes, CommonJS.

// ---------- Path (value object) ----------
class Path {
  constructor(segments = []) { this.segments = [...segments]; }
  static of(slashSeparated) {
    return new Path(slashSeparated.split('/').filter((s) => s.length > 0));
  }
  parentPath() { return new Path(this.segments.slice(0, -1)); }
  lastSegment() { return this.segments[this.segments.length - 1]; }
  resolveChild(childName) { return new Path([...this.segments, childName]); }
  isDescendantOf(other) {
    if (other.segments.length >= this.segments.length) return false;
    return other.segments.every((seg, i) => seg === this.segments[i]);
  }
  toString() { return '/' + this.segments.join('/'); }
}

// ---------- NodeVisitor (interface) ----------
class NodeVisitor {
  visitFile(_f) { throw new Error('not implemented'); }
  visitDirectory(_d) { throw new Error('not implemented'); }
}

// ---------- FileSystemNode (abstract) ----------
// Common identity for anything in the tree. Aggregate ops are delegated to a NodeVisitor.
class FileSystemNode {
  constructor(name, parent) {
    if (new.target === FileSystemNode) throw new Error('FileSystemNode is abstract');
    this.name = name;
    this.parent = parent;
  }
  accept(_visitor) { throw new Error('accept() not implemented'); }
}

// ---------- File (leaf) ----------
class File extends FileSystemNode {
  constructor(name, parent) { super(name, parent); this.content = Buffer.alloc(0); }
  size() { return this.content.length; }
  read() { return this.content; }
  write(data) { this.content = Buffer.isBuffer(data) ? data : Buffer.from(data); }
  accept(visitor) { visitor.visitFile(this); }
}

// ---------- Directory (composite) ----------
class Directory extends FileSystemNode {
  constructor(name, parent) { super(name, parent); this.children = new Map(); }
  addChild(node) { this.children.set(node.name, node); }
  removeChild(name) { this.children.delete(name); }
  getChild(name) { return this.children.get(name); }
  accept(visitor) { visitor.visitDirectory(this); }
}

// ---------- DirectoryIterator ----------
// Snapshot iterator: copies the child list at creation time so a concurrent mutation of the
// underlying Directory during iteration can't invalidate iteration mid-walk (policy: snapshot).
class DirectoryIterator {
  constructor(directory) {
    this.snapshot = Array.from(directory.children.values());
    this.index = 0;
  }
  hasNext() { return this.index < this.snapshot.length; }
  next() {
    if (!this.hasNext()) throw new Error('No more elements');
    return this.snapshot[this.index++];
  }
}

// ---------- NodeVisitor implementations ----------
class DiskUsageVisitor extends NodeVisitor {
  compute(node) { node.accept(this); return this.lastSize; }
  visitFile(f) { this.lastSize = f.size(); }
  visitDirectory(d) {
    let total = 0;
    const it = new DirectoryIterator(d);
    while (it.hasNext()) {
      const child = it.next();
      child.accept(this); // recurses; visitFile sets lastSize directly for leaves
      total += this.lastSize;
    }
    this.lastSize = total;
  }
}

class SearchVisitor extends NodeVisitor {
  constructor(criteria, base) { super(); this.criteria = criteria; this.base = base; this.matches = []; }
  search(node) { this._walk(node, this.base); return this.matches; }
  visitFile(_f) {}      // traversal is driven by _walk(), not the visitor dispatch
  visitDirectory(_d) {}
  _walk(node, path) {
    if (this.criteria(node)) this.matches.push(path);
    if (node instanceof Directory) {
      const it = new DirectoryIterator(node);
      while (it.hasNext()) {
        const child = it.next();
        this._walk(child, path.resolveChild(child.name));
      }
    }
  }
}

// ---------- FileSystem (facade) ----------
class FileSystem {
  constructor() { this.root = new Directory('', null); }

  _resolveParent(path) {
    let current = this.root;
    for (let i = 0; i < path.segments.length - 1; i++) {
      const next = current.getChild(path.segments[i]);
      if (!(next instanceof Directory)) throw new Error(`No such directory: ${path}`);
      current = next;
    }
    return current;
  }

  _resolve(path) {
    if (path.segments.length === 0) return this.root;
    const parentDir = this._resolveParent(path);
    const node = parentDir.getChild(path.lastSegment());
    if (!node) throw new Error(`No such path: ${path}`);
    return node;
  }

  createFile(path) {
    const parentDir = this._resolveParent(path);
    parentDir.addChild(new File(path.lastSegment(), parentDir));
  }

  createDirectory(path) {
    const parentDir = this._resolveParent(path);
    parentDir.addChild(new Directory(path.lastSegment(), parentDir));
  }

  delete(path, recursive) {
    const parentDir = this._resolveParent(path);
    const node = parentDir.getChild(path.lastSegment());
    if (node instanceof Directory && node.children.size > 0 && !recursive) {
      throw new Error(`Directory not empty; pass recursive=true to delete: ${path}`);
    }
    parentDir.removeChild(path.lastSegment());
  }

  read(path) {
    const node = this._resolve(path);
    if (!(node instanceof File)) throw new Error(`Not a file: ${path}`);
    return node.read();
  }

  write(path, data) {
    const node = this._resolve(path);
    if (!(node instanceof File)) throw new Error(`Not a file: ${path}`);
    node.write(data);
  }

  list(directoryPath) {
    const node = this._resolve(directoryPath);
    if (!(node instanceof Directory)) throw new Error(`Not a directory: ${directoryPath}`);
    const names = [];
    const it = new DirectoryIterator(node);
    while (it.hasNext()) names.push(it.next().name);
    return names;
  }

  // Move source under destination's parent (destination's last segment becomes the new name).
  // Guards against moving a directory into its own subtree. No real threads exist in this
  // single-threaded translation, so canonical-path lock ordering is left as commentary only --
  // this is where a two-mutex ABBA-safe acquisition would go under a concurrent implementation.
  move(source, destination) {
    const srcParent = this._resolveParent(source);
    const destParent = this._resolveParent(destination);
    const node = srcParent.getChild(source.lastSegment());
    if (!node) throw new Error(`No such path: ${source}`);

    if (node instanceof Directory && destination.isDescendantOf(source)) {
      throw new Error('cannot move a directory into its own subtree');
    }

    // lock ordering would be established here by canonical path in a concurrent version
    srcParent.removeChild(node.name);
    node.name = destination.lastSegment();
    node.parent = destParent;
    destParent.addChild(node);
  }

  search(startPath, criteria) {
    const startNode = this._resolve(startPath);
    return new SearchVisitor(criteria, startPath).search(startNode);
  }

  diskUsage(startPath) {
    const startNode = this._resolve(startPath);
    return new DiskUsageVisitor().compute(startNode);
  }
}

// ---------- Demo ----------
function main() {
  const fs = new FileSystem();
  fs.createDirectory(Path.of('/docs'));
  fs.createDirectory(Path.of('/docs/reports'));
  fs.createFile(Path.of('/docs/readme.txt'));
  fs.createFile(Path.of('/docs/reports/q1.csv'));
  fs.createFile(Path.of('/docs/reports/q2.csv'));
  fs.createDirectory(Path.of('/media'));

  fs.write(Path.of('/docs/readme.txt'), 'hello world');
  fs.write(Path.of('/docs/reports/q1.csv'), 'a,b,c\n1,2,3');
  fs.write(Path.of('/docs/reports/q2.csv'), 'x,y,z\n4,5,6\n7,8,9');

  console.log('Listing /docs:', fs.list(Path.of('/docs')));
  console.log('Listing /docs/reports:', fs.list(Path.of('/docs/reports')));

  console.log('Read /docs/readme.txt:', fs.read(Path.of('/docs/readme.txt')).toString());
  console.log('Disk usage of /docs:', fs.diskUsage(Path.of('/docs')), 'bytes');

  const csvFiles = fs.search(Path.of('/docs'), (node) => node instanceof File && node.name.endsWith('.csv'));
  console.log('Search *.csv under /docs:', csvFiles.map(String));

  console.log('\nMoving /docs/reports -> /media/reports');
  fs.move(Path.of('/docs/reports'), Path.of('/media/reports'));
  console.log('Listing /media:', fs.list(Path.of('/media')));
  console.log('Listing /docs after move:', fs.list(Path.of('/docs')));

  try {
    fs.move(Path.of('/media'), Path.of('/media/reports/media'));
  } catch (e) {
    console.log('\nExpected rejection moving a directory into its own subtree:', e.message);
  }

  try {
    fs.delete(Path.of('/media'), false);
  } catch (e) {
    console.log('Expected rejection deleting non-empty dir without recursive:', e.message);
  }
  fs.delete(Path.of('/media'), true);
  console.log('Root listing after recursive delete of /media:', fs.list(Path.of('')));
}

if (require.main === module) main();

module.exports = {
  Path, NodeVisitor, FileSystemNode, File, Directory, DirectoryIterator,
  DiskUsageVisitor, SearchVisitor, FileSystem,
};

// File System -- full class-diagram implementation, single-threaded.
// No concurrency badge on this problem -- kept single-threaded; the lock-ordering idea in the
// move() pseudocode is preserved only as commentary, not as real mutexes.
//
// Note: the diagram's `File` leaf class is named `FileNode`, and its `FileSystem` facade is
// named `VirtualFileSystem`, here because TypeScript's default lib set includes DOM, which
// declares global `File` and `FileSystem` types; this avoids those name collisions while
// keeping identical fields/behavior. `Directory` and the rest keep their diagram names.

// ---------- Path (value object) ----------
class Path {
  readonly segments: string[];
  constructor(segments: string[] = []) { this.segments = [...segments]; }
  static of(slashSeparated: string): Path {
    return new Path(slashSeparated.split('/').filter((s) => s.length > 0));
  }
  parentPath(): Path { return new Path(this.segments.slice(0, -1)); }
  lastSegment(): string { return this.segments[this.segments.length - 1]; }
  resolveChild(childName: string): Path { return new Path([...this.segments, childName]); }
  isDescendantOf(other: Path): boolean {
    if (other.segments.length >= this.segments.length) return false;
    return other.segments.every((seg, i) => seg === this.segments[i]);
  }
  toString(): string { return '/' + this.segments.join('/'); }
}

// ---------- NodeVisitor (interface) ----------
interface NodeVisitor {
  visitFile(f: FileNode): void;
  visitDirectory(d: Directory): void;
}

// ---------- FileSystemNode (abstract) ----------
// Common identity for anything in the tree. Aggregate ops are delegated to a NodeVisitor.
abstract class FileSystemNode {
  constructor(public name: string, public parent: Directory | null) {}
  abstract accept(visitor: NodeVisitor): void;
}

// ---------- FileNode (leaf) ----------
class FileNode extends FileSystemNode {
  content: string = '';
  constructor(name: string, parent: Directory | null) { super(name, parent); }
  size(): number { return this.content.length; }
  read(): string { return this.content; }
  write(data: string): void { this.content = data; }
  accept(visitor: NodeVisitor): void { visitor.visitFile(this); }
}

// ---------- Directory (composite) ----------
class Directory extends FileSystemNode {
  readonly children = new Map<string, FileSystemNode>();
  constructor(name: string, parent: Directory | null) { super(name, parent); }
  addChild(node: FileSystemNode): void { this.children.set(node.name, node); }
  removeChild(name: string): void { this.children.delete(name); }
  getChild(name: string): FileSystemNode | undefined { return this.children.get(name); }
  accept(visitor: NodeVisitor): void { visitor.visitDirectory(this); }
}

// ---------- DirectoryIterator ----------
// Snapshot iterator: copies the child list at creation time so a concurrent mutation of the
// underlying Directory during iteration can't invalidate iteration mid-walk (policy: snapshot).
class DirectoryIterator {
  private readonly snapshot: FileSystemNode[];
  private index = 0;
  constructor(directory: Directory) { this.snapshot = Array.from(directory.children.values()); }
  hasNext(): boolean { return this.index < this.snapshot.length; }
  next(): FileSystemNode {
    if (!this.hasNext()) throw new Error('No more elements');
    return this.snapshot[this.index++];
  }
}

// ---------- NodeVisitor implementations ----------
class DiskUsageVisitor implements NodeVisitor {
  private lastSize = 0;
  compute(node: FileSystemNode): number { node.accept(this); return this.lastSize; }
  visitFile(f: FileNode): void { this.lastSize = f.size(); }
  visitDirectory(d: Directory): void {
    let total = 0;
    const it = new DirectoryIterator(d);
    while (it.hasNext()) {
      const child = it.next();
      child.accept(this); // recurses; visitFile sets lastSize directly for leaves
      total += this.lastSize;
    }
    this.lastSize = total;
  }
}

type SearchCriteria = (node: FileSystemNode) => boolean;

class SearchVisitor implements NodeVisitor {
  private readonly matches: Path[] = [];
  constructor(private readonly criteria: SearchCriteria, private readonly base: Path) {}

  search(node: FileSystemNode): Path[] { this.walk(node, this.base); return this.matches; }
  visitFile(_f: FileNode): void {}      // traversal is driven by walk(), not the visitor dispatch
  visitDirectory(_d: Directory): void {}

  private walk(node: FileSystemNode, path: Path): void {
    if (this.criteria(node)) this.matches.push(path);
    if (node instanceof Directory) {
      const it = new DirectoryIterator(node);
      while (it.hasNext()) {
        const child = it.next();
        this.walk(child, path.resolveChild(child.name));
      }
    }
  }
}

// ---------- VirtualFileSystem (facade) ----------
class VirtualFileSystem {
  readonly root = new Directory('', null);

  private resolveParent(path: Path): Directory {
    let current = this.root;
    for (let i = 0; i < path.segments.length - 1; i++) {
      const next = current.getChild(path.segments[i]);
      if (!(next instanceof Directory)) throw new Error(`No such directory: ${path}`);
      current = next;
    }
    return current;
  }

  private resolve(path: Path): FileSystemNode {
    if (path.segments.length === 0) return this.root;
    const parentDir = this.resolveParent(path);
    const node = parentDir.getChild(path.lastSegment());
    if (!node) throw new Error(`No such path: ${path}`);
    return node;
  }

  createFile(path: Path): void {
    const parentDir = this.resolveParent(path);
    parentDir.addChild(new FileNode(path.lastSegment(), parentDir));
  }

  createDirectory(path: Path): void {
    const parentDir = this.resolveParent(path);
    parentDir.addChild(new Directory(path.lastSegment(), parentDir));
  }

  delete(path: Path, recursive: boolean): void {
    const parentDir = this.resolveParent(path);
    const node = parentDir.getChild(path.lastSegment());
    if (node instanceof Directory && node.children.size > 0 && !recursive) {
      throw new Error(`Directory not empty; pass recursive=true to delete: ${path}`);
    }
    parentDir.removeChild(path.lastSegment());
  }

  read(path: Path): string {
    const node = this.resolve(path);
    if (!(node instanceof FileNode)) throw new Error(`Not a file: ${path}`);
    return node.read();
  }

  write(path: Path, data: string): void {
    const node = this.resolve(path);
    if (!(node instanceof FileNode)) throw new Error(`Not a file: ${path}`);
    node.write(data);
  }

  list(directoryPath: Path): string[] {
    const node = this.resolve(directoryPath);
    if (!(node instanceof Directory)) throw new Error(`Not a directory: ${directoryPath}`);
    const names: string[] = [];
    const it = new DirectoryIterator(node);
    while (it.hasNext()) names.push(it.next().name);
    return names;
  }

  // Move source under destination's parent (destination's last segment becomes the new name).
  // Guards against moving a directory into its own subtree. No real threads exist in this
  // single-threaded translation, so canonical-path lock ordering is left as commentary only --
  // this is where a two-mutex ABBA-safe acquisition would go under a concurrent implementation.
  move(source: Path, destination: Path): void {
    const srcParent = this.resolveParent(source);
    const destParent = this.resolveParent(destination);
    const node = srcParent.getChild(source.lastSegment());
    if (!node) throw new Error(`No such path: ${source}`);

    if (node instanceof Directory && destination.isDescendantOf(source)) {
      throw new Error('cannot move a directory into its own subtree');
    }

    // lock ordering would be established here by canonical path in a concurrent version
    srcParent.removeChild(node.name);
    node.name = destination.lastSegment();
    node.parent = destParent;
    destParent.addChild(node);
  }

  search(startPath: Path, criteria: SearchCriteria): Path[] {
    const startNode = this.resolve(startPath);
    return new SearchVisitor(criteria, startPath).search(startNode);
  }

  diskUsage(startPath: Path): number {
    const startNode = this.resolve(startPath);
    return new DiskUsageVisitor().compute(startNode);
  }
}

// ---------- Demo ----------
function main(): void {
  const fs = new VirtualFileSystem();
  fs.createDirectory(Path.of('/docs'));
  fs.createDirectory(Path.of('/docs/reports'));
  fs.createFile(Path.of('/docs/readme.txt'));
  fs.createFile(Path.of('/docs/reports/q1.csv'));
  fs.createFile(Path.of('/docs/reports/q2.csv'));
  fs.createDirectory(Path.of('/media'));

  fs.write(Path.of('/docs/readme.txt'), 'hello world');
  fs.write(Path.of('/docs/reports/q1.csv'), 'a,b,c\n1,2,3');
  fs.write(Path.of('/docs/reports/q2.csv'), 'x,y,z\n4,5,6\n7,8,9');

  console.log('Listing /docs:', fs.list(Path.of('/docs')));
  console.log('Listing /docs/reports:', fs.list(Path.of('/docs/reports')));

  console.log('Read /docs/readme.txt:', fs.read(Path.of('/docs/readme.txt')));
  console.log('Disk usage of /docs:', fs.diskUsage(Path.of('/docs')), 'bytes');

  const csvFiles = fs.search(Path.of('/docs'), (node) => node instanceof FileNode && node.name.endsWith('.csv'));
  console.log('Search *.csv under /docs:', csvFiles.map(String));

  console.log('\nMoving /docs/reports -> /media/reports');
  fs.move(Path.of('/docs/reports'), Path.of('/media/reports'));
  console.log('Listing /media:', fs.list(Path.of('/media')));
  console.log('Listing /docs after move:', fs.list(Path.of('/docs')));

  try {
    fs.move(Path.of('/media'), Path.of('/media/reports/media'));
  } catch (e) {
    console.log('\nExpected rejection moving a directory into its own subtree:', (e as Error).message);
  }

  try {
    fs.delete(Path.of('/media'), false);
  } catch (e) {
    console.log('Expected rejection deleting non-empty dir without recursive:', (e as Error).message);
  }
  fs.delete(Path.of('/media'), true);
  console.log('Root listing after recursive delete of /media:', fs.list(Path.of('')));
}

main();