Bài 32.3. Hệ thống Quản lý Phiên làm việc Đa nhiệm - [Độ khó: Khó]

Trong một hệ điều hành đa nhiệm tưởng tượng, các phiên làm việc (user session) của người dùng được quản lý theo một danh sách vòng tròn. Mỗi phiên làm việc có một ID duy nhất và có thể được chuyển đổi giữa chúng. Để tối ưu hóa việc sử dụng, hệ thống muốn giữ các phiên làm việc được sử dụng gần đây nhất ở vị trí dễ truy cập (ví dụ, ngay sau phiên làm việc hiện tại). Đồng thời, hệ thống cần hỗ trợ chuyển đổi nhanh giữa các phiên và loại bỏ các phiên không còn hoạt động.

Bạn cần triển khai một hệ thống quản lý phiên làm việc sử dụng Danh sách liên kết đôi-vòng (Doubly Circular Linked List). Hệ thống sẽ có một "phiên làm việc hiện tại" (current session).

INPUT FORMAT

Dòng đầu tiên là một số nguyên N (1 <= N <= 10000), số lượng thao tác. Tiếp theo là N dòng, mỗi dòng mô tả một thao tác:

• ADD <session_ID>: Thêm một phiên làm việc mới có session_ID vào danh sách. Nếu danh sách rỗng, đây là phiên làm việc đầu tiên và trở thành "phiên làm việc hiện tại". Nếu không, nó được thêm vào ngay sau "phiên làm việc hiện tại".
• SWITCH <session_ID>: Chuyển "phiên làm việc hiện tại" sang session_ID. Nếu session_ID này không tồn tại, bỏ qua thao tác. Nếu tồn tại, phiên làm việc này trở thành "phiên làm việc hiện tại".
• REMOVE <session_ID>: Loại bỏ phiên làm việc có session_ID. Nếu session_ID là "phiên làm việc hiện tại", "phiên làm việc hiện tại" sẽ chuyển sang phiên kế tiếp (theo chiều thuận). Nếu không có phiên kế tiếp (danh sách trở nên rỗng), không có phiên làm việc hiện tại.
• MOVE_TO_FRONT <session_ID>: Di chuyển phiên làm việc có session_ID đến vị trí ngay sau "phiên làm việc hiện tại". Nếu session_ID là "phiên làm việc hiện tại", hoặc không tồn tại, hoặc danh sách rỗng, không làm gì cả. Thao tác này giúp các phiên được sử dụng thường xuyên hơn ở gần phiên hiện tại để dễ chuyển đổi.
• PRINT_STATUS: In ra ID của "phiên làm việc hiện tại", sau đó là danh sách các session_ID theo thứ tự tuần hoàn, bắt đầu từ "phiên làm việc hiện tại" (bao gồm chính nó) và đi theo chiều thuận.

Tất cả các session_ID đều là số nguyên dương và không trùng lặp (1 <= session_ID <= 10^9). Các thao tác SWITCH và REMOVE đảm bảo session_ID luôn tồn tại trong danh sách (trừ trường hợp xóa hoặc chuyển đổi đến một ID không tồn tại). Thao tác ADD đảm bảo session_ID chưa tồn tại.

OUTPUT FORMAT

Với mỗi thao tác PRINT_STATUS:

• Nếu danh sách rỗng, in ra "Empty".
• Nếu có phiên làm việc, in ra "Current: <current_session_ID>". Sau đó, trên một dòng mới, in ra chuỗi tuần hoàn các session_ID cách nhau bởi dấu cách, bắt đầu từ current_session_ID và đi theo chiều thuận.

Ví dụ:

Input:

9
ADD 10
ADD 20
ADD 30
PRINT_STATUS
SWITCH 10
MOVE_TO_FRONT 30
PRINT_STATUS
REMOVE 20
PRINT_STATUS

Output:

Current: 10
10 20 30
Current: 10
10 30 20
Current: 10
10 30

Giải thích:

• ADD 10: Danh sách: 10. Current: 10.
• ADD 20: Thêm 20 sau 10. List: 10 <-> 20. Current: 10.
• ADD 30: Thêm 30 sau 10. List: 10 <-> 30 <-> 20. Current: 10. (Lưu ý, thêm sau current).
• PRINT_STATUS: Current: 10. In ra: 10 30 20.
• SWITCH 10: Current vẫn là 10.
• MOVE_TO_FRONT 30: Di chuyển 30 đến sau 10. List: 10 <-> 30 <-> 20. Vị trí của 30 không thay đổi vì nó đã ở ngay sau 10. (Nếu 30 ở cuối thì nó sẽ được di chuyển). Correction: "Move to front" implies moving it to the position right after the current node. In this example, 30 is already after 10. Let's assume "front" means "immediately after current". If 30 was e.g. after 20, it would become 10 <-> 30 <-> 20. The list is 10 <-> 30 <-> 20 with current at 10. If we move 30 (which is already after 10) it might not change. Let's refine the "Move to Front" operation: "Di chuyển phiên làm việc có session_ID đến vị trí ngay sau phiên làm việc hiện tại, biến nó thành node kế tiếp trực tiếp của phiên hiện tại."
  • List: 10 <-> 30 <-> 20. Current: 10.
  • MOVE_TO_FRONT 30: 30 đã là kế tiếp của 10. Vậy không có gì thay đổi.
  • If MOVE_TO_FRONT 20: List was 10 <-> 30 <-> 20. Current: 10. 20 would move to become 10 <-> 20 <-> 30.
  • Example should reflect this. Let's fix the example to make MOVE_TO_FRONT more impactful.

Revised Example for 32.3: Input:

9
ADD 10
ADD 20
ADD 30
PRINT_STATUS
SWITCH 20
MOVE_TO_FRONT 10
PRINT_STATUS
REMOVE 30
PRINT_STATUS

Output:

Current: 10
10 20 30
Current: 20
20 10 30
Current: 20
20 10

Giải thích:

• ADD 10: Danh sách: 10. Current: 10.
• ADD 20: Thêm 20 sau 10. List: 10 <-> 20. Current: 10.
• ADD 30: Thêm 30 sau 10. List: 10 <-> 30 <-> 20. Current: 10. (Lưu ý: 30 được thêm giữa 10 và 20, vì 10 là current).
• PRINT_STATUS: Current: 10. In ra: 10 30 20.
• SWITCH 20: Current trở thành 20. List: 10 <-> 30 <-> 20.
• MOVE_TO_FRONT 10: Di chuyển 10 đến ngay sau current (là 20).
  • Ban đầu: 10 <-> 30 <-> 20. current trỏ đến 20. 20.next = 10, 20.prev = 30.
  • Thao tác: Lấy 10 ra khỏi vị trí hiện tại (20 và 30 sẽ nối với nhau).
  • Sau đó: Chèn 10 vào giữa 20 và 30.
  • Kết quả: 20 <-> 10 <-> 30. Current: 20.
• PRINT_STATUS: Current: 20. In ra: 20 10 30.
• REMOVE 30: Loại bỏ 30.
  • List: 20 <-> 10 <-> 30. Current: 20.
  • Sau khi xóa 30: 20 <-> 10.
• PRINT_STATUS: Current: 20. In ra: 20 10.