1import java.util.HashMap;
2import java.util.HashSet;
3import java.util.Iterator;
4import java.util.Map;
5import java.util.Set;
6
7class AllOne {
8    private final Node root = new Node(); // Sentinel node to mark beginning and end of doubly linked list
9    private final Map<String, Node> nodes = new HashMap<>(); // Mapping from key to its corresponding Node
10
11    public AllOne() {
12        // Initialize the doubly linked list with root node pointing to itself
13        root.next = root;
14        root.prev = root;
15    }
16
17    public void inc(String key) {
18        // Increase the count for the key
19        if (!nodes.containsKey(key)) {
20            // If key is new, insert it appropriately
21            if (root.next == root || root.next.cnt > 1) {
22                nodes.put(key, root.insert(new Node(key, 1)));
23            } else {
24                root.next.keys.add(key);
25                nodes.put(key, root.next);
26            }
27        } else {
28            // If key already exists, move it to the next Node or create a new Node
29            Node current = nodes.get(key);
30            Node next = current.next;
31            if (next == root || next.cnt > current.cnt + 1) {
32                nodes.put(key, current.insert(new Node(key, current.cnt + 1)));
33            } else {
34                next.keys.add(key);
35                nodes.put(key, next);
36            }
37            // Remove key from current Node and check if it should be deleted
38            current.keys.remove(key);
39            if (current.keys.isEmpty()) {
40                current.remove();
41            }
42        }
43    }
44
45    public void dec(String key) {
46        // Decrease the count for the key
47        Node current = nodes.get(key);
48        if (current.cnt == 1) {
49            // If count goes to 0, remove key from system
50            nodes.remove(key);
51        } else {
52            // Move key to the previous Node or create a new Node
53            Node prev = current.prev;
54            if (prev == root || prev.cnt < current.cnt - 1) {
55                nodes.put(key, prev.insert(new Node(key, current.cnt - 1)));
56            } else {
57                prev.keys.add(key);
58                nodes.put(key, prev);
59            }
60        }
61      
62        // Remove key from current Node and remove Node if empty
63        current.keys.remove(key);
64        if (current.keys.isEmpty()) {
65            current.remove();
66        }
67    }
68
69    public String getMaxKey() {
70        // Get and return a key with the maximum count
71        if (root.prev == root) return ""; // Handle case with no keys
72        return root.prev.keys.iterator().next();
73    }
74
75    public String getMinKey() {
76        // Get and return a key with the minimum count
77        if (root.next == root) return ""; // Handle case with no keys
78        return root.next.keys.iterator().next();
79    }
80}
81
82class Node {
83    Node prev; // Previous node in doubly linked list
84    Node next; // Next node in doubly linked list
85    int cnt; // Count associated with node
86    Set<String> keys = new HashSet<>(); // Set of keys with this count
87
88    // Constructor for sentinel node
89    public Node() {
90        this("", 0);
91    }
92
93    // Constructor for actual nodes
94    public Node(String key, int cnt) {
95        this.cnt = cnt;
96        keys.add(key);
97    }
98
99    // Method to insert this node before the provided node
100    public Node insert(Node node) {
101        node.prev = this;
102        node.next = this.next;
103        node.prev.next = node;
104        node.next.prev = node;
105        return node;
106    }
107
108    // Method to remove this node from the linked list
109    public void remove() {
110        this.prev.next = this.next;
111        this.next.prev = this.prev;
112    }
113}
114

1#include <unordered_map>
2#include <unordered_set>
3#include <string>
4
5class Node {
6public:
7    Node *prev; // Pointer to the previous node in the doubly linked list
8    Node *next; // Pointer to the next node in the doubly linked list
9    int count; // Count of occurrences for this node
10    std::unordered_set<std::string> keys; // Set of keys with this occurrence count
11
12    // Constructor for sentinel node
13    Node() : prev(nullptr), next(nullptr), count(0) {}
14
15    // Constructor for actual nodes with a given key and count
16    Node(const std::string& key, int count) : prev(nullptr), next(nullptr), count(count) {
17        keys.insert(key);
18    }
19
20    // Method to insert a node after this node
21    Node* insert(Node* node) {
22        node->prev = this;
23        node->next = this->next;
24        this->next->prev = node;
25        this->next = node;
26        return node;
27    }
28
29    // Remove the node from the doubly linked list
30    void remove() {
31        this->prev->next = this->next;
32        this->next->prev = this->prev;
33    }
34};
35
36class AllOne {
37private:
38    Node root; // Sentinel node to mark the beginning and end of the doubly linked list
39    std::unordered_map<std::string, Node*> nodes; // Mapping from keys to their corresponding nodes
40
41public:
42    AllOne() {
43        // Initialize the doubly linked list with the sentinel node linking to itself
44        root.next = &root;
45        root.prev = &root;
46    }
47
48    void inc(const std::string& key) {
49        // Increase the count for the key
50        if (nodes.find(key) == nodes.end()) {
51            // If key is new, insert it into the list
52            if (root.next == &root || root.next->count > 1) {
53                nodes[key] = root.insert(new Node(key, 1));
54            } else {
55                root.next->keys.insert(key);
56                nodes[key] = root.next;
57            }
58        } else {
59            // If the key already exists, move it to a new or next existing Node
60            Node *current = nodes[key];
61            Node *next = current->next;
62            if (next == &root || next->count > current->count + 1) {
63                nodes[key] = current->insert(new Node(key, current->count + 1));
64            } else {
65                next->keys.insert(key);
66                nodes[key] = next;
67            }
68            // Remove the key from the current Node and delete the Node if it's empty
69            current->keys.erase(key);
70            if (current->keys.empty()) {
71                current->remove();
72                delete current; // C++ requires explicit deletion
73            }
74        }
75    }
76
77    void dec(const std::string& key) {
78        auto it = nodes.find(key);
79        if (it == nodes.end()) return;
80        Node *current = it->second;
81        if (current->count == 1) {
82            // Remove the key completely if the count is 1
83            nodes.erase(key);
84        } else {
85            // Move the key to previous Node or create a new Node
86            Node *prev = current->prev;
87            if (prev == &root || prev->count < current->count - 1) {
88                nodes[key] = prev->insert(new Node(key, current->count - 1));
89            } else {
90                prev->keys.insert(key);
91                nodes[key] = prev;
92            }
93        }
94        // Remove the key from the current Node and delete the Node if empty
95        current->keys.erase(key);
96        if (current->keys.empty()) {
97            current->remove();
98            delete current; // C++ requires explicit deletion
99        }
100    }
101
102    std::string getMaxKey() {
103        // Return a key with the maximum count
104        if (root.prev == &root) return ""; // Handle case with no keys
105        return *root.prev->keys.begin();
106    }
107
108    std::string getMinKey() {
109        // Return a key with the minimum count
110        if (root.next == &root) return ""; // Handle case with no keys
111        return *root.next->keys.begin();
112    }
113};
114

1// Define a Node class to represent each entry in our linked list
2class Node {
3    prev: Node | null; // Reference to the previous node in the list
4    next: Node | null; // Reference to the next node in the list
5    count: number; // Number of occurrences of keys
6    keys: Set<string>; // Set of keys with this occurrence count
7
8    // Constructor to initialize a new instance of Node
9    constructor(key: string = "", count: number = 0) {
10        this.prev = this.next = null;
11        this.count = count;
12        this.keys = new Set(key ? [key] : []);
13    }
14
15    // Method to insert a new node after the current node
16    insertAfter(newNode: Node): Node {
17        newNode.prev = this;
18        newNode.next = this.next;
19        if (this.next) {
20            this.next.prev = newNode;
21        }
22        this.next = newNode;
23        return newNode;
24    }
25
26    // Method to remove the current node from the list
27    removeFromList(): void {
28        if (this.prev) {
29            this.prev.next = this.next;
30        }
31        if (this.next) {
32            this.next.prev = this.prev;
33        }
34    }
35}
36
37// Create a sentinel node as the root node of our doubly linked list
38const root = new Node();
39
40// Initialize root to point to itself, creating an empty linked list
41root.prev = root;
42root.next = root;
43
44// Create a mapping from key to its corresponding node
45const nodes: Map<string, Node> = new Map();
46
47// Function to increment the occurrence count of a key
48function incrementKey(key: string): void {
49    if (!nodes.has(key)) {
50        // Handle new key
51        insertNewKey(key);
52    } else {
53        // Handle existing key
54        incrementExistingKey(key);
55    }
56}
57
58// Function to decrement the occurrence count of a key
59function decrementKey(key: string): void {
60    const current = nodes.get(key);
61    if (!current) return;
62
63    if (current.count === 1) {
64        // Remove the key if its count reaches zero
65        nodes.delete(key);
66        current.keys.delete(key);
67    } else {
68        // Move the key to a lower count or create a new node if necessary
69        moveToPreviousCount(key, current);
70    }
71    // Remove node if it's empty
72    if (current.keys.size === 0) {
73        current.removeFromList();
74    }
75}
76
77// Function to retrieve a key with the maximum count
78function getMaxKey(): string {
79    // If list is empty, return an empty string
80    if (root.prev === root) return "";
81    return root.prev.keys.values().next().value;
82}
83
84// Function to retrieve a key with the minimum count
85function getMinKey(): string {
86    // If list is empty, return an empty string
87    if (root.next === root) return "";
88    return root.next.keys.values().next().value;
89}
90
91// ... (additional helper functions such as `insertNewKey`, `incrementExistingKey`, `moveToPreviousCount` would be implemented here)
92
93// (The remaining helpers and logic can be implemented following the below pattern):
94// Implement helper methods such as `insertNewKey`, `incrementExistingKey`, and `moveToPreviousCount`
95// which follow the logic outlined in the provided Java code. These helpers manage the linked list
96// and the nodes map, ensuring that keys are correctly incremented or decremented in counts and
97// the corresponding nodes are inserted or removed as needed within the list structure.
98