from typing import Dict, List, Set, Tuple, Optional
from dataclasses import dataclass
import re

@dataclass
class Package:
name: str
version: str

@dataclass
class ResolutionResult:
success: bool
packages: List[Package]
error: Optional[str] = None

def parse_version(version_str: str) -> Tuple[int, int, int]:
"""Parse semantic version string to tuple of integers."""
match = re.match(r'^(\d+).(\d+).(\d+)$', version_str)
if not match:
raise ValueError(f"Invalid version format: {version_str}")
return tuple(map(int, match.groups()))

def version_satisfies(version: str, constraint: str) -> bool:
"""Check if a version satisfies a constraint."""
v = parse_version(version)

if constraint.startswith('^'):
    spec = constraint[1:]
    spec_v = parse_version(spec)
    major = spec_v[0]
    return v >= spec_v and v[0] == major
elif constraint.startswith('~'):
    spec = constraint[1:]
    spec_v = parse_version(spec)
    major, minor = spec_v[0], spec_v[1]
    return v >= spec_v and v[0] == major and v[1] == minor
else:
    spec_v = parse_version(constraint)
    return v == spec_v

def find_best_version(package_name: str, constraint: str, available_packages: Dict) -> Optional[str]:
"""Find the highest version that satisfies the constraint."""
if package_name not in available_packages:
return None

versions = [pkg['version'] for pkg in available_packages[package_name]]
matching = [v for v in versions if version_satisfies(v, constraint)]

if not matching:
    return None

return max(matching, key=parse_version)

def resolve_dependencies(available_packages: Dict, target_package: str, version_constraint: str) -> ResolutionResult:
"""Resolve dependencies for a package with semantic versioning support."""

# Check if target package exists
if target_package not in available_packages:
    return ResolutionResult(False, [], f"Package '{target_package}' not found")

# Find best version for target
best_version = find_best_version(target_package, version_constraint, available_packages)
if best_version is None:
    return ResolutionResult(False, [], f"No version of '{target_package}' satisfies '{version_constraint}'")

# Track resolved packages and constraints
resolved: Dict[str, str] = {}  # package_name -> version
constraints: Dict[str, Set[str]] = {}  # package_name -> set of constraints
visiting: Set[str] = set()  # For cycle detection
visited: Set[str] = set()

def get_package_info(name: str, version: str) -> Optional[Dict]:
    """Get package info for a specific version."""
    if name not in available_packages:
        return None
    for pkg in available_packages[name]:
        if pkg['version'] == version:
            return pkg
    return None

def dfs(package_name: str, constraint: str) -> bool:
    """DFS to resolve dependencies. Returns True if successful."""
    
    # Check for circular dependency
    if package_name in visiting:
        return False
    
    if package_name in visited:
        # Already resolved, check if current constraint is satisfied
        if package_name in resolved:
            if not version_satisfies(resolved[package_name], constraint):
                return False
        return True
    
    visiting.add(package_name)
    
    # Track constraint
    if package_name not in constraints:
        constraints[package_name] = set()
    constraints[package_name].add(constraint)
    
    # Find best version satisfying all constraints
    all_constraints = constraints[package_name]
    best_version = None
    
    if package_name not in available_packages:
        visiting.remove(package_name)
        return False
    
    versions = [pkg['version'] for pkg in available_packages[package_name]]
    for v in sorted(versions, key=parse_version, reverse=True):
        if all(version_satisfies(v, c) for c in all_constraints):
            best_version = v
            break
    
    if best_version is None:
        visiting.remove(package_name)
        return False
    
    resolved[package_name] = best_version
    
    # Get dependencies
    pkg_info = get_package_info(package_name, best_version)
    if pkg_info is None:
        visiting.remove(package_name)
        return False
    
    dependencies = pkg_info.get('dependencies', {})
    
    # Resolve dependencies
    for dep_name, dep_constraint in dependencies.items():
        if not dfs(dep_name, dep_constraint):
            visiting.remove(package_name)
            return False
    
    visiting.remove(package_name)
    visited.add(package_name)
    return True

# Start resolution
if not dfs(target_package, version_constraint):
    if target_package in visiting:
        return ResolutionResult(False, [], f"Circular dependency detected involving '{target_package}'")
    return ResolutionResult(False, [], f"Unable to resolve dependencies for '{target_package}@{version_constraint}'")

# Topological sort
def topological_sort() -> List[Package]:
    in_degree = {pkg: 0 for pkg in resolved}
    graph = {pkg: [] for pkg in resolved}
    
    for pkg_name, version in resolved.items():
        pkg_info = get_package_info(pkg_name, version)
        if pkg_info:
            for dep_name in pkg_info.get('dependencies', {}):
                if dep_name in resolved:
                    graph[dep_name].append(pkg_name)
                    in_degree[pkg_name] += 1
    
    queue = [pkg for pkg in resolved if in_degree[pkg] == 0]
    result = []
    
    while queue:
        pkg = queue.pop(0)
        result.append(Package(pkg, resolved[pkg]))
        
        for neighbor in graph[pkg]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return result

sorted_packages = topological_sort()
return ResolutionResult(True, sorted_packages)

Example usage

if name == "main":
packages = {
"pkg-A": [
{"version": "1.0.0", "dependencies": {"pkg-B": "~1.0.0"}},
{"version": "1.1.0", "dependencies": {"pkg-B": "^1.1.0"}}
],
"pkg-B": [
{"version": "1.0.0", "dependencies": {}},
{"version": "1.0.5", "dependencies": {}},
{"version": "1.1.0", "dependencies": {}},
{"version": "2.0.0", "dependencies": {}}
],
"pkg-C": [
{"version": "1.0.0", "dependencies": {"pkg-A": "^1.0.0", "pkg-B": "^1.0.0"}}
],
"pkg-D": [
{"version": "1.0.0", "dependencies": {"pkg-D": "^1.0.0"}}
],
"pkg-E": [
{"version": "1.0.0", "dependencies": {"pkg-F": "^1.0.0"}}
],
"pkg-F": [
{"version": "1.0.0", "dependencies": {"pkg-E": "^1.0.0"}}
]
}

result = resolve_dependencies(packages, "pkg-C", "^1.0.0")
print(f"Success: {result.success}")
print(f"Packages: {[(p.name, p.version) for p in result.packages]}")
if result.error:
    print(f"Error: {result.error}")