class Dictionary:
    """
    Dictionary ADT implementation using hashing with chaining.

    Attributes:
        capacity (int): The initial capacity of the hash table.
        table (list): The hash table, a list of lists (chains).
        size (int): The number of key-value pairs currently in the dictionary.
        use_replacement (bool): Flag to indicate whether to use chaining with replacement.
    """

    def __init__(self, capacity=10, use_replacement=False):
        """
        Initializes the Dictionary.

        Args:
            capacity (int): The initial capacity of the hash table (default: 10).
            use_replacement (bool): Whether to use chaining with replacement (default: False).
        """
        if not isinstance(capacity, int) or capacity <= 0:
            raise ValueError("Capacity must be a positive integer.")
        self.capacity = capacity
        self.table = [[] for _ in range(capacity)]  # Use a list comprehension
        self.size = 0
        self.use_replacement = use_replacement

    def _hash(self, key):
        """
        Hashes the key to an index in the hash table.

        This uses Python's built-in hash function, and then applies a modulo
        operation to ensure the index is within the table bounds.
        For demonstration, we'll use a simple modulo, but in a real-world
        scenario, a more robust hash function would be preferable.

        Args:
            key: The key to hash.  Must be hashable.

        Returns:
            int: The index in the hash table.

        Raises:
            TypeError: If the key is not hashable.
        """
        try:
            return hash(key) % self.capacity
        except TypeError:
            raise TypeError(f"Key {key} is not hashable.")

    def insert(self, key, value):
        """
        Inserts a key-value pair into the dictionary.

        Handles collisions using chaining (with or without replacement).

        Args:
            key: The key to insert.  Must be hashable and unique.
            value: The value to associate with the key.

        Raises:
            TypeError: If the key is not hashable.
            ValueError: If the key already exists in the dictionary.
        """
        if not self._is_valid_key(key):
            raise TypeError(f"Key {key} is not a valid key type.")

        index = self._hash(key)
        bucket = self.table[index]

        # Check for duplicate keys.  This needs to be done *before*
        # inserting the new key-value pair.
        for i, (k, v) in enumerate(bucket):
            if k == key:
                if self.use_replacement:
                    # Chaining with replacement
                    if self._hash(k) != index:
                        # Find the correct position for the new key
                        original_index = self._hash(k)
                        original_bucket = self.table[original_index]
                        original_bucket[i] = (key, value)  # update the value in the original index
                        # remove the key value pair from the new index
                        bucket.remove((k, v))
                        self.table[index].append((key, value))
                        return
                    else:
                        raise ValueError(f"Key {key} already exists in the dictionary.")
                else:
                    raise ValueError(f"Key {key} already exists in the dictionary.")

        # Key not found, insert the new key-value pair at the end of the chain.
        bucket.append((key, value))
        self.size += 1

        # Check if resizing is needed (simple load factor check).
        if self.size > self.capacity * 0.7:  # Load factor of 0.7
            self._resize()

    def find(self, key):
        """
        Finds the value associated with a key in the dictionary.

        Args:
            key: The key to search for.

        Returns:
            The value associated with the key, or None if the key is not found.

        Raises:
            TypeError: If the key is not hashable.
        """
        if not self._is_valid_key(key):
            raise TypeError(f"Key {key} is not a valid key type.")
        index = self._hash(key)
        bucket = self.table[index]

        for k, v in bucket:
            if k == key:
                return v
        return None  # Key not found

    def delete(self, key):
        """
        Deletes the key-value pair associated with the given key from the dictionary.

        Args:
            key: The key to delete.

        Raises:
            TypeError: If the key is not hashable.
            KeyError: If the key is not found in the dictionary.
        """
        if not self._is_valid_key(key):
            raise TypeError(f"Key {key} is not a valid key type.")

        index = self._hash(key)
        bucket = self.table[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return  # Exit after successful deletion
        raise KeyError(f"Key {key} not found in the dictionary.")

    def _resize(self):
        """
        Resizes the hash table to a new capacity (usually double the old).

        This is called when the load factor exceeds a certain threshold to maintain
        good performance.  All key-value pairs are rehashed and inserted into the
        new table.
        """
        new_capacity = self.capacity * 2
        new_table = [[] for _ in range(new_capacity)]  # Create new table
        old_table = self.table  # Keep a reference to the old table
        self.capacity = new_capacity  # Update capacity
        self.table = new_table
        self.size = 0  # Reset size, as we're re-inserting

        # Rehash and insert all key-value pairs from the old table
        for bucket in old_table:
            for key, value in bucket:
                self.insert(key, value)  # Use insert to handle rehashing

    def __len__(self):
        """
        Returns the number of key-value pairs in the dictionary.
        """
        return self.size

    def __contains__(self, key):
        """
        Checks if a key is in the dictionary.  Implements the 'in' operator.

        Args:
            key: The key to check for.

        Returns:
            bool: True if the key is in the dictionary, False otherwise.
        """
        return self.find(key) is not None

    def __getitem__(self, key):
        """
        Gets the value associated with a key.  Implements dict[key] syntax.

        Args:
            key: The key to look up.

        Returns:
            The value associated with the key.

        Raises:
            KeyError: If the key is not found.
            TypeError: If the key is not hashable.
        """
        value = self.find(key)
        if value is None:
            raise KeyError(key)
        return value

    def __setitem__(self, key, value):
        """
        Sets the value associated with a key.  Implements dict[key] = value syntax.
        If the key is already in the dictionary, the value is updated.
        Otherwise, the (key, value) pair is inserted.

        Args:
            key: The key to set.
            value: The value to associate with the key.
        """
        try:
            self.insert(key, value)  # Try inserting first
        except ValueError:  # Key already exists
            index = self._hash(key)
            bucket = self.table[index]
            for i, (k, v) in enumerate(bucket):
                if k == key:
                    bucket[i] = (key, value)  # update the value
                    return

    def __delitem__(self, key):
        """
        Deletes the key-value pair associated with a key. Implements del dict[key]

        Args:
            key: the key to delete
        Raises:
            KeyError: If the key is not found.
            TypeError: If the key is not hashable
        """
        self.delete(key)

    def _is_valid_key(self, key):
        """
        Checks if a key is valid.
        """
        return isinstance(key, (int, str, float, bool, tuple, frozenset))  # extendable

    def display(self):
        """
        Displays the contents of the dictionary (for debugging/testing).
        """
        print("Dictionary Contents:")
        for i, bucket in enumerate(self.table):
            print(f"Index {i}: ", end="")
            if not bucket:
                print("[]")
            else:
                print("[", ", ".join(f"({k}, {v})" for k, v in bucket), "]")
        print(f"Capacity: {self.capacity}, Size: {self.size}")


def get_user_input(prompt, expected_type):
    """
    Gets user input and validates the type.

    Args:
        prompt (str): The prompt to display to the user.
        expected_type (type): The expected data type of the input.

    Returns:
        The user's input, converted to the expected type, or None on error.
    """
    while True:
        try:
            user_input = input(prompt).strip()
            if user_input.lower() == 'null':  # Allow 'null' for None
                return None
            if expected_type == bool:
                if user_input.lower() == 'true':
                    return True
                elif user_input.lower() == 'false':
                    return False
                else:
                    raise ValueError("Invalid boolean value.  Use 'True' or 'False'.")
            else:
                return expected_type(user_input)
        except ValueError as e:
            print(f"Invalid input: {e}")
            print(f"Please enter a valid {expected_type.__name__}.")
        except TypeError:
            print("Invalid input type.")
            print(f"Please enter a valid {expected_type.__name__}.")
        except Exception as e:
            print(f"An unexpected error occurred: {e}")
            return None  # Return None on unexpected error

def main():
    """
    Main function to run the dictionary program with a user interface.
    """
    capacity = get_user_input("Enter the initial capacity of the dictionary: ", int)
    if capacity is None:
        print("Using default capacity of 10.")
        capacity = 10
    use_replacement = get_user_input("Use chaining with replacement? (True/False): ", bool)
    if use_replacement is None:
        print("Using default: False")
        use_replacement = False

    my_dict = Dictionary(capacity, use_replacement)

    while True:
        print("\nDictionary Menu:")
        print("1. Insert a key-value pair")
        print("2. Delete a key-value pair")
        print("3. Find a value by key")
        print("4. Display the dictionary")
        print("5. Get the size of the dictionary")
        print("6. Check if a key exists")
        print("7. Update a key's value")
        print("8. Exit")

        choice = get_user_input("Enter your choice: ", int)

        if choice is None:
            print("Invalid input. Please enter an integer.")
            continue  # Restart the loop

        if choice == 1:
            key = get_user_input("Enter the key (int, str, float, bool, tuple, frozenset): ", str)
            if key is None:
                print("No key entered")
                continue
            value = get_user_input("Enter the value: ", str)  # Can be any string
            if value is None:
                print("No value entered, using None")
                value = None
            # Convert key string back to original type
            if key.isdigit():
                key = int(key)
            elif key.lower() == "true" or key.lower() == "false":
                key = key.lower() == "true"
            elif '.' in key and key.replace('.', '', 1).isdigit():
                key = float(key)
            elif '(' in key and ')' in key:
                key = tuple(key[1:-1].split(','))
            try:
                my_dict.insert(key, value)
                print(f"Key-value pair ({key}, {value}) inserted.")
            except ValueError as e:
                print(f"Error: {e}")
            except TypeError as e:
                print(f"Error: {e}")

        elif choice == 2:
            key = get_user_input("Enter the key to delete: ", str)
            if key is None:
                print("No key entered.")
                continue
             # Convert key string back to original type
            if key.isdigit():
                key = int(key)
            elif key.lower() == "true" or key.lower() == "false":
                key = key.lower() == "true"
            elif '.' in key and key.replace('.', '', 1).isdigit():
                key = float(key)
            elif '(' in key and ')' in key:
                key = tuple(key[1:-1].split(','))
            try:
                my_dict.delete(key)
                print(f"Key-value pair with key '{key}' deleted.")
            except KeyError as e:
                print(f"Error: {e}")
            except TypeError as e:
                print(f"Error: {e}")

        elif choice == 3:
            key = get_user_input("Enter the key to find: ", str)
            if key is None:
                print("No key entered.")
                continue
             # Convert key string back to original type
            if key.isdigit():
                key = int(key)
            elif key.lower() == "true" or key.lower() == "false":
                key = key.lower() == "true"
            elif '.' in key and key.replace('.', '', 1).isdigit():
                key = float(key)
            elif '(' in key and ')' in key:
                key = tuple(key[1:-1].split(','))
            value = my_dict.find(key)
            if value is not None:
                print(f"Value associated with key '{key}': {value}")
            else:
                print(f"Key '{key}' not found in the dictionary.")

        elif choice == 4:
            my_dict.display()

        elif choice == 5:
            print(f"Size of the dictionary: {len(my_dict)}")

        elif choice == 6:
            key = get_user_input("Enter the key to check: ", str)
            if key is None:
                print("No key entered.")
                continue
             # Convert key string back to original type
            if key.isdigit():
                key = int(key)
            elif key.lower() == "true" or key.lower() == "false":
                key = key.lower() == "true"
            elif '.' in key and key.replace('.', '', 1).isdigit():
                key = float(key)
            elif '(' in key and ')' in key:
                key = tuple(key[1:-1].split(','))
            if key in my_dict:
                print(f"Key '{key}' exists in the dictionary.")
            else:
                print(f"Key '{key}' does not exist in the dictionary.")

        elif choice == 7:
            key = get_user_input("Enter the key to update: ", str)
            if key is None:
                print("No key entered.")
                continue
            value = get_user_input("Enter the new value: ", str)
            if value is None:
                print("No new value entered")
                continue
             # Convert key string back to original type
            if key.isdigit():
                key = int(key)
            elif key.lower() == "true" or key.lower() == "false":
                key = key.lower() == "true"
            elif '.' in key and key.replace('.', '', 1).isdigit():
                key = float(key)
            elif '(' in key and ')' in key:
                key = tuple(key[1:-1].split(','))
            try:
                my_dict[key] = value
                print(f"Value for key '{key}' updated to '{value}'.")
            except KeyError:
                print(f"Key '{key}' not found.")

        elif choice == 8:
            print("Exiting program.")
            break

        else:
            print("Invalid choice. Please enter a number between 1 and 8.")


if __name__ == "__main__":
    main()