import logging
from typing import Dict, Any, Optional

# Configure logging
logging.basicConfig(level=logging.INFO, format='%(asctime)s - %(levelname)s - %(message)s')


class LRUCacheOptimizer:
    """
    A Least Recently Used (LRU) cache optimizer.

    This class provides methods for optimizing a cache by evicting the least recently used items.
    """

    def __init__(self, cache_size: int):
        """
        Initializes the LRUCacheOptimizer with a maximum cache size.

        Args:
            cache_size: The maximum number of items the cache can hold.
        """
        self.cache_size = cache_size
        self.cache: Dict[Any, Any] = {}
        self.access_history: Dict[Any, int] = {}  # Key: item, Value: access timestamp
        self.timestamp = 0
        logging.info(f"LRUCacheOptimizer initialized with cache size: {cache_size}")

    def optimize(self, cache: Dict[Any, Any]) -> Dict[Any, Any]:
        """
        Optimizes the given cache by evicting the least recently used items if the cache exceeds the maximum size.

        Args:
            cache: The cache to optimize.

        Returns:
            The optimized cache.
        """
        self.cache = cache
        if len(self.cache) > self.cache_size:
            logging.info("Cache is full, optimizing...")
            self._evict_lru_item()
        return self.cache

    def _evict_lru_item(self) -> None:
        """
        Evicts the least recently used item from the cache.
        """
        if not self.cache:
            logging.warning("Cache is already empty, cannot evict.")
            return

        lru_key: Optional[Any] = None
        min_timestamp = float('inf')

        for key, timestamp in self.access_history.items():
            if key in self.cache and timestamp < min_timestamp:  # Ensure the key is still in the cache
                min_timestamp = timestamp
                lru_key = key

        if lru_key is not None:
            try:
                del self.cache[lru_key]
                del self.access_history[lru_key]
                logging.info(f"Evicted LRU item: {lru_key}")
            except KeyError as e:
                logging.error(f"KeyError while evicting LRU item: {e}")
        else:
            logging.warning("No LRU item found in cache.")

    def update_access(self, key: Any) -> None:
        """
        Updates the access timestamp for a given key.

        Args:
            key: The key that was accessed.
        """
        self.timestamp += 1
        self.access_history[key] = self.timestamp
        logging.debug(f"Updated access timestamp for key: {key} to {self.timestamp}")


def main():
    """
    Main function to demonstrate the LRUCacheOptimizer.
    """
    optimizer = LRUCacheOptimizer(cache_size=3)
    cache = {
        'a': 1,
        'b': 2,
        'c': 3
    }

    optimizer.update_access('a')
    optimizer.update_access('b')
    optimizer.update_access('c')

    print(f"Initial Cache: {cache}")
    cache = optimizer.optimize(cache)
    print(f"Cache after first optimization: {cache}")

    optimizer.update_access('a')
    optimizer.update_access('d')
    cache['d'] = 4
    cache = optimizer.optimize(cache)
    print(f"Cache after second optimization: {cache}")



if __name__ == "__main__":
    main()