Versioned Key-Value Store with Nested Transactions (Begin, Commit, Rollback)

Implement an in-memory versioned key-value database that supports transactional writes with three transaction-control operations: begin (start a transaction), commit, and rollback. Transactions may be nested: a begin issued while another transaction is open starts a new inner transaction layered on top of it.

Implement the class VersionedKVStore:

• VersionedKVStore() — initializes an empty store with no open transactions.
• void set(String key, int value) — sets key to value in the current context: the innermost open transaction if one exists, otherwise the permanent store.
• int get(String key) — returns the value of key as currently visible: the innermost open transaction is consulted first, then each enclosing transaction from inner to outer, then the permanent store. Returns -1 if the key is absent, or if the most recent visible operation on it is a deletion.
• void delete(String key) — deletes key in the current context. Inside a transaction, the deletion shadows any value from outer transactions or the permanent store (so get returns -1), but takes permanent effect only if committed. Deleting a key that is not visible is a no-op in effect (subsequent get still returns -1).
• void begin() — opens a new transaction, nested inside the current innermost transaction if one is open.
• boolean commit() — if no transaction is open, returns false. Otherwise merges all changes (sets and deletions) of the innermost open transaction into its parent transaction — or into the permanent store if it is the outermost — closes that transaction, and returns true.
• boolean rollback() — if no transaction is open, returns false. Otherwise discards all changes made in the innermost open transaction, closes it, and returns true.

Reads and writes issued outside any transaction apply directly and permanently to the store.

Example

Input:
["VersionedKVStore", "set", "get", "begin", "set", "get", "begin", "delete", "get", "rollback", "get", "commit", "get", "rollback", "get"]
[[], ["a", 1], ["a"], [], ["a", 2], ["a"], [], ["a"], ["a"], [], ["a"], [], ["a"], [], ["a"]]

Output:
[null, null, 1, null, null, 2, null, null, -1, true, 2, true, 2, false, 2]

Explanation:

1. set("a", 1) — no transaction open, written permanently. get("a") returns 1.
2. begin() opens transaction T1; set("a", 2) inside T1; get("a") returns 2.
3. begin() opens nested transaction T2; delete("a") inside T2; get("a") returns -1 (the deletion in T2 shadows the outer value).
4. rollback() discards T2 and returns true; get("a") returns 2 again (T1's write is intact).
5. commit() merges T1 into the permanent store and returns true; get("a") returns 2.
6. rollback() returns false — no transaction is open; get("a") still returns 2.

Constraints

• At most 10^5 operations in total.
• Keys are non-empty lowercase strings of length at most 20.
• 0 <= value <= 10^9
• Transaction nesting depth will not exceed 10^3.

Performance requirement

set and delete should run in O(1) average time. get may be O(d) in the worst case, where d is the current nesting depth (an O(1)-average get is possible with a more advanced design and is a nice discussion point). commit and rollback should cost time proportional to the number of keys modified in the innermost transaction — not the size of the whole store.