Build a Progressive Cloud Storage System

Problem Statement

Implement an in-memory cloud storage service that manages files for multiple users under strict storage quotas. The system tracks both logical size (the uncompressed byte size) and charged size (the actual bytes counted against a user's quota).

You need to implement the CloudStorage class with the following methods:

1. User and File Management

• add_user(user_id: str, quota: int) -> bool: Creates a new user with a specified storage quota in bytes. Returns True if successfully created, or False if user_id already exists or quota bool: Uploads a new file at path for user_id with logical size size. The file starts uncompressed (charged size equals logical size). Returns True if successful. Returns False if user_id does not exist, path already exists for this user, size bool: Removes the file at path for user_id, freeing up its charged size from the user's quota. Returns True if deleted, or False if user_id does not exist or path does not exist for that user.

2. Compression & Restoration

• compress_file(user_id: str, path: str, factor: int) -> bool: Compresses an existing uncompressed file. factor is an integer >= 2. The new charged size becomes size // factor (integer division). The logical size remains unchanged. Returns True if successful. Returns False if user_id or path is not found, factor bool: Decompresses a compressed file. The charged size reverts back to the logical size. The user must have sufficient remaining quota to accommodate the difference (logical_size - charged_size). Returns True if successfully restored. Returns False if user_id or path is not found, the file is not compressed, or restoring would exceed the user's quota.

3. Copy and Search

• copy_file(from_user: str, from_path: str, to_user: str, to_path: str) -> bool: Copies a file from (from_user, from_path) to (to_user, to_path). The destination inherits the source file's logical size, charged size, and compression state. Returns True if successful. Returns False if either user does not exist, from_path does not exist, to_path already exists for to_user, or to_user has insufficient quota to hold the file's charged size.
• search(user_id: str, pattern: str) -> list[str]: Returns a lexicographically sorted list of file paths belonging to user_id that match the glob pattern. The glob pattern supports *, which matches zero or more arbitrary characters. Returns an empty list if user_id does not exist or no files match.

Example

storage = CloudStorage()
storage.add_user("alice", 100)        # True (alice: 0/100 used)
storage.add_file("alice", "/docs/a.txt", 60) # True (alice: 60/100 used)
storage.add_file("alice", "/docs/b.txt", 50) # False (exceeds quota: 60 + 50 > 100)

storage.compress_file("alice", "/docs/a.txt", 2) # True (charged size becomes 60 // 2 = 30; 30/100 used)
storage.add_file("alice", "/docs/b.txt", 50)     # True (now 30 + 50 = 80/100 used)

storage.restore_file("alice", "/docs/a.txt")     # False (needs +30, but only 20 remaining)

storage.search("alice", "/docs/*.txt")            # ["/docs/a.txt", "/docs/b.txt"]

Constraints

• 1 <= len(user_id), len(path) <= 256
• File sizes and quotas: 0 <= size, quota <= 10^9
• Up to 10^4 total calls across all methods.
• Operations that fail must leave the system state completely unchanged (atomic operations).