# node.py
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# circular_linked_list.py
from node import Node

class CircularLinkedList:
    def __init__(self):
        """
        Initializes an empty Circular Linked List.
        The 'last' pointer will point to the last node in the list.
        If the list is empty, 'last' is None.
        If not empty, 'last.next' always points to the first node.
        """
        self.last = None

    def is_empty(self):
        """
        Checks if the circular linked list is empty.
        Returns True if empty, False otherwise.
        """
        return self.last is None

    def append(self, data):
        """
        Adds a new node with the given data to the end of the list.
        """
        new_node = Node(data)
        if self.is_empty():
            self.last = new_node
            self.last.next = self.last # Point to itself for a single-node circular list
        else:
            new_node.next = self.last.next # New node points to the current head
            self.last.next = new_node      # Current last node points to the new node
            self.last = new_node           # New node becomes the new last node
        print(f"Appended: {data}")

    def prepend(self, data):
        """
        Adds a new node with the given data to the beginning of the list.
        """
        new_node = Node(data)
        if self.is_empty():
            self.last = new_node
            self.last.next = self.last # Point to itself
        else:
            new_node.next = self.last.next # New node points to the current head
            self.last.next = new_node      # Current last node points to the new node (which is now the head)
        print(f"Prepended: {data}")

    def delete_node(self, key):
        """
        Deletes the first occurrence of a node with the given key from the list.
        Handles deletion of head, last, and intermediate nodes.
        """
        if self.is_empty():
            print(f"Cannot delete {key}: List is empty.")
            return

        current = self.last.next # Start from the head
        prev = self.last         # Previous node, starting from the last (since it points to head)
        
        found = False
        # Special case: Deleting the only node
        if self.last.data == key and self.last.next == self.last:
            self.last = None
            print(f"Deleted: {key} (last remaining node)")
            return

        # Traverse to find the node or complete one full cycle
        while True:
            if current.data == key:
                found = True
                break
            prev = current
            current = current.next
            if current == self.last.next: # Completed one full cycle
                break

        if found:
            # Case 1: Deleting the head node (current is last.next)
            if current == self.last.next:
                self.last.next = current.next
            # Case 2: Deleting the last node (current is self.last)
            elif current == self.last:
                prev.next = self.last.next # Prev of last now points to head
                self.last = prev           # Prev becomes the new last node
            # Case 3: Deleting an intermediate node
            else:
                prev.next = current.next
            print(f"Deleted: {key}")
        else:
            print(f"Node with data '{key}' not found.")

    def traverse(self):
        """
        Traverses and prints the data of each node in the list.
        Starts from the head and prints until it loops back to the head.
        """
        if self.is_empty():
            print("List is empty.")
            return

        nodes = []
        current = self.last.next # Start from the head
        while True:
            nodes.append(str(current.data))
            current = current.next
            if current == self.last.next: # Stop when we loop back to the head
                break
        print("Circular List:", " -> ".join(nodes))

    def split_list(self):
        """
        Splits the circular list into two halves.
        Returns two new CircularLinkedList objects.
        If the number of nodes is odd, the first list gets the extra node.
        Uses the fast/slow pointer approach.
        """
        if self.is_empty():
            return CircularLinkedList(), CircularLinkedList()
        if self.last.next == self.last: # Only one node
            first_half = CircularLinkedList()
            first_half.append(self.last.data)
            self.last = None # Original list becomes empty
            return first_half, CircularLinkedList()

        slow_ptr = self.last.next # Starts at head
        fast_ptr = self.last.next # Starts at head

        # Move fast_ptr twice as fast as slow_ptr
        # When fast_ptr reaches the 'last' node or the node before 'last',
        # slow_ptr will be at the middle or just before it.
        while fast_ptr.next != self.last.next and fast_ptr.next.next != self.last.next:
            slow_ptr = slow_ptr.next
            fast_ptr = fast_ptr.next.next
        
        # Now slow_ptr is at the end of the first half
        
        first_half = CircularLinkedList()
        current = self.last.next # Start of original list
        while current != slow_ptr.next: # Iterate up to (but not including) the split point
            first_half.append(current.data)
            current = current.next
        
        second_half = CircularLinkedList()
        # Handle the split for the second half
        second_half_start = slow_ptr.next

        # If fast_ptr ended up on the last node, the slow_ptr.next is where the second half starts.
        # Otherwise, fast_ptr.next is the last node and fast_ptr.next.next is the head.
        # This condition handles both even/odd cases correctly for fast_ptr termination.
        while second_half_start != self.last.next: # Iterate from split point to original head
            second_half.append(second_half_start.data)
            second_half_start = second_half_start.next
        
        # The original list is now effectively empty after splitting.
        # Note: A more efficient split would re-wire pointers directly
        # rather than creating new lists and appending. This example
        # simplifies the re-wiring logic by showing creation.
        self.last = None # Clear original list

        print("\n--- Splitting List ---")
        first_half.traverse()
        second_half.traverse()
        return first_half, second_half


    def josephus_problem(self, k):
        """
        Solves the Josephus Problem: N people in a circle, every K-th person is eliminated.
        Finds the last person remaining.
        k: The elimination step (e.g., every 3rd person).
        """
        if self.is_empty():
            print("Cannot solve Josephus Problem: List is empty.")
            return None
        
        if self.last.next == self.last: # Only one person left
            survivor = self.last.data
            self.last = None # List becomes empty
            print(f"Josephus Problem (k={k}): The survivor is {survivor}")
            return survivor

        current = self.last.next # Start from the head (person 1)
        prev = self.last # Points to the person before the head

        # Keep eliminating until only one node remains
        while current.next != current: # While there's more than one node
            # Move k-1 steps to find the person to eliminate
            for _ in range(k - 1):
                prev = current
                current = current.next
            
            # Eliminate the 'current' person
            print(f"Eliminating: {current.data}")
            prev.next = current.next # Skip current node
            
            if current == self.last: # If we eliminated the last node, update last
                self.last = prev
            
            current = prev.next # Move to the next person after elimination
        
        survivor = current.data
        self.last = None # List becomes empty
        print(f"Josephus Problem (k={k}): The survivor is {survivor}")
        return survivor

# main.py
from circular_linked_list import CircularLinkedList

print("--- Basic Circular Linked List Operations ---")
cll = CircularLinkedList()

# Check empty list
cll.traverse()

# Append elements
cll.append(10)
cll.traverse()

cll.append(20)
cll.traverse()

cll.append(30)
cll.traverse()

# Prepend an element
cll.prepend(5)
cll.traverse()

cll.prepend(0)
cll.traverse()

# Delete elements
cll.delete_node(20) # Delete an intermediate node
cll.traverse()

cll.delete_node(0)  # Delete the head node
cll.traverse()

cll.delete_node(30) # Delete the last node
cll.traverse()

cll.delete_node(100) # Not found
cll.traverse()

cll.delete_node(5)
cll.traverse()

cll.delete_node(10) # Delete the last remaining node
cll.traverse()

cll.delete_node(99) # Delete from empty list

# main.py (continued)
print("\n--- Splitting Circular Linked List ---")
cll_split = CircularLinkedList()
cll_split.append(1)
cll_split.append(2)
cll_split.append(3)
cll_split.append(4)
cll_split.append(5) # Odd number of elements
cll_split.append(6) # Even number of elements now

cll_split.traverse() # Original list

# Split the list
first_half, second_half = cll_split.split_list()

# Original list should be empty
cll_split.traverse()

# Test with an odd number of elements
print("\n--- Splitting Odd Length List ---")
cll_odd = CircularLinkedList()
cll_odd.append('A')
cll_odd.append('B')
cll_odd.append('C')
cll_odd.append('D')
cll_odd.append('E')
cll_odd.traverse()
first_half_odd, second_half_odd = cll_odd.split_list()

# main.py (continued)
print("\n--- Josephus Problem Simulation ---")

# Example 1: N=7, K=3
cll_josephus1 = CircularLinkedList()
for i in range(1, 8): # People 1 to 7
    cll_josephus1.append(i)
cll_josephus1.traverse()
cll_josephus1.josephus_problem(3) # Every 3rd person

# Example 2: N=5, K=2
print("\n--- Josephus Problem Simulation (N=5, K=2) ---")
cll_josephus2 = CircularLinkedList()
for i in ['Alice', 'Bob', 'Charlie', 'David', 'Eve']:
    cll_josephus2.append(i)
cll_josephus2.traverse()
cll_josephus2.josephus_problem(2) # Every 2nd person

# Example 3: Single person
print("\n--- Josephus Problem Simulation (N=1, K=Any) ---")
cll_josephus3 = CircularLinkedList()
cll_josephus3.append("Solo")
cll_josephus3.traverse()
cll_josephus3.josephus_problem(5)