Description
Introduction
In international trade, governments frequently adjust tariff policies for different countries. These policy changes need to be accurately recorded and tracked so that the tariff status for any specific country can be queried at any point in time. This assignment requires the design of a tariff policy tracking system, similar to a version control system.
Problem Description
In this assignment, we will design a simple tariff policy tracking system. We need to implement three main functions:
Announce (announce a new policy),
Switch (switch to the policy of a specific date),
Check (check the current tariff rate of a specific country),
The system starts with an empty root node, and all countries initially have no tariffs.
1. Announce (Announce a new policy)
Command format:
<country_name> <tariff_rate>
...
This command creates a new policy node containing tariff changes for <country_count> countries. Each country's tariff change includes the country name and the new tariff rate. The new policy node becomes a child of the current node, and the current node is updated to this new node.
The system should output:
New policy announced on <date>
2. Switch (Switch to a policy on a specific date)
Command format:
tariff switch <date>
This command switches the current node to the policy node of the specified date.
If a policy is found for the given date, output:
Switched to Policy on <date>
And the current node will change
If not found, output:
No policy found on <date>
And the current node will not change
After doing a switch, the current_node of the tree will change to the target of the switch, and if an announce is performed afterward, the new node should connect after the current_node. However, don't worry, the test cases ensure that after a switch, if an announce will be performed, it will first switch back to the leaf node of the tree.
3. Check (Check the tariff history of a specific country)
Command format:
This command queries the complete tariff history for the specified country. The system will list all tariff changes in chronological order according to the specified order parameter:
asc: Lists all tariff changes in ascending chronological order (from oldest to newest)
desc: Lists all tariff changes in descending chronological order (from newest to oldest)
If history is found, output in the format:
Tariff history for <country_name>:
<rate_1>
<rate_2>
…
If no tariff policy is found, output:
No tariff policy for <country_name>
System Structure
We provide the TradePolicy, TariffPolicy and PolicyNode classes. Each PolicyNode is designed to store information for a single policy announcement.
The TariffPolicy class uses a Trie data structure to optimize country name lookup performance.
Implementing the Trie is necessary to ensure efficient data retrieval, especially for the check command.
Test Cases
Case 1 : Announce & Check
Case 2 : Announce & Check
Case 3 : Announce & Switch & Check
Case 4 : Announce & Switch & Check
Case 5 : Announce & Switch & Check
Input
The input will contain N commands, each representing one of the three operations described above.
Input parameter ranges:
1. 1 ≤ N ≤ 5 * 10^5
2. Country names contain only lowercase letters, with 1 ≤ len(country_name) ≤ 20
3. Tariff rate format is a percentage, such as "25%" or "10.5%"
4. Date format is "YYYY-MM-DD"
5. Please submit your solution in C++11.
6. This is a partially graded assignment, so you do not need to worry about the exact input/output format.
7. You are required to implement the following functions:
|
// Clear the Trie tree |
Output
Print output required according to each command. Enter a newline after every output.