For this problem, you will implement a simplified Version Tree in C/C++. Each node in the tree represents a "version" of a project. Every node stores a single character value (Node Value, representing project data for the version) and a pointer to its parent.
The version tree starts with a single Root node. The root node is special: it represents an empty state and does not store a value (it contains no character). Your program should also maintain a Current Pointer which points to the root node at the start.
Each node of this tree is also associated with a unique integer Version ID. The root node's ID is 0. IDs for additional nodes are assigned incrementally (1, 2, 3...) as new nodes are created via commit.
For each node, we can find its Version History: the sequence of characters collected from the root down to the target node. Note: The root (ID 0) does not contribute a character to this sequence. For example, if the path is 0 => 1('A') => 2('B'), the version history is A B.
Your program should support the following commands.
1. commit CHAR
- Create a new node as a child of the current(-pointed) node.
- Assign the next available ID to this node and store the alphanumerical character CHAR.
- Move the "Current Pointer" to this new node.
2. checkout ID
- Move the "Current Pointer" to the node with the specified ID.
- (You can assume ID always exists.)
3. log
- Display the version history of the current node, with each node character value separated by a single space.
- If the current node is the Root, print an empty line.
4. diff ID
- Compare the version history of the current node with the history of the Target Node (the node with ID ID).
- To do so, first find the Lowest Common Ancestor (LCA): identify the most recent version that both nodes share. This is the "Split Point" where the two versions diverged. Then output:
+ First line: lenA v1c v2c ..., where v1c v2c ... is the sequence of characters in the current node's version history after the LCA, and lenA is the total number of characters in v1c v2c ....
+ Second line: lenB u1c u2c ..., where u1c u2c ... is the sequence of characters in the target node's version history after the LCA, and lenB is the total number of characters in u1c u2c ....
+ If v1c v2c ... (and likewise for u1c u2c ...) has no characters, output its line to contain only 0.
Your program MAY use C/C++ standard library headers.
- The first line contains an integer N (1 <= N <= 5000), the number of commands.
- The next N lines each contains one command.
- CHAR is a single visible character (non-space).
- For each log command, print the version history on one line ('\n'-terminated).
- For each diff command, print the two lines ('\n'-terminated) describing the branch differences.