Design: Multi-Tab Browser History

Extend an existing single-tab browser history component to manage multiple tabs. The system should support opening and closing tabs, switching the active tab, and performing navigation actions (visit, back, forward) on the currently active tab.

APIs to Design

1. int openTab(string homepage): Opens a new tab initialized with the given homepage URL and returns a stable, unique identifier for the new tab.
2. void closeTab(int tabId): Closes the tab identified by tabId and disposes of its associated history.
3. void switchTab(int tabId): Sets the tab identified by tabId as the active tab for subsequent navigation operations.
4. void visit(string url): Navigates the active tab to the specified URL. This operation clears any existing forward history for that tab.
5. string back(int steps): Moves the active tab's history backward by the specified number of steps. The movement is clamped by the available history. Returns the URL of the page after the navigation.
6. string forward(int steps): Moves the active tab's history forward by the specified number of steps. The movement is clamped by the available history. Returns the URL of the page after the navigation.
7. Optional: bool haveVisited(string url): Determines if a given URL has been visited. The candidate should define whether this applies per-tab, globally across all tabs, or both, and discuss the implications.

Functional Requirements

• Each tab must maintain its own independent navigational history, encompassing back, current, and forward states.
• The visit(url) operation for the active tab must clear its forward history before navigating to the new URL.
• back(steps) and forward(steps) operations apply only to the active tab, moving within its specific history. The number of steps moved will be clamped by the actual available history in either direction. Both operations must return the URL of the page that becomes current after the navigation.
• openTab must return a stable, unique tab identifier. switchTab is responsible for changing which tab is considered active for subsequent operations.
• closeTab must correctly dispose of all history and resources associated with the specified tab.

Design Discussion Requirements

The design discussion should cover:

• Data Structures: Propose and justify data structures for managing:
  • The navigational history for each individual tab.
  • A registry of all open tabs, potentially including their order (e.g., Most Recently Used).
• Trade-offs: Compare different design choices (e.g., using a map versus a list for tab management or history) considering factors such as memory footprint and operational complexity.
• Complexity Targets: Define and justify the expected time complexity for each API operation.
• Thread-Safety: Discuss considerations for thread-safety if multiple tabs or browser instances could operate concurrently. Propose appropriate mechanisms such as locking strategies or immutable data structures.
• History Capping/Eviction: Detail policies for capping the history size per tab and/or globally, and explain how these policies would affect the semantics and implementation of the haveVisited function.

Assumptions

• The system should be able to handle up to 10^5 (100,000) open tabs.
• Each individual tab's history can be capped at H entries (e.g., 1000).
• The concept of an "active tab" is maintained per browser instance or session.
• URLs are treated as arbitrary strings.