algorithms/greedy.py

"""
USSU Algorithm Analyzer v4.0 - Greedy Algorithms Suite
Activity Selection, Huffman, Fractional Knapsack, and more.
"""
import heapq
from typing import List, Dict, Tuple, Any
from utils.core import profile_algorithm, OperationCounter


class GreedyAlgorithms(OperationCounter):
    """Greedy algorithm collection for ADA"""

    def __init__(self):
        super().__init__()

    def reset(self):
        self.reset_counters()

    # ==================== ACTIVITY SELECTION ====================
    @profile_algorithm
    def activity_selection(self, activities: List[Tuple[int, int, str]]) -> Dict:
        """
        activities: list of (start, finish, name)
        Returns maximum set of non-conflicting activities.
        """
        self.reset()
        # Sort by finish time
        sorted_acts = sorted(activities, key=lambda x: x[1])
        selected = [sorted_acts[0]]
        last_finish = sorted_acts[0][1]

        for i in range(1, len(sorted_acts)):
            self.iterations += 1
            self.comparisons += 1
            if sorted_acts[i][0] >= last_finish:
                selected.append(sorted_acts[i])
                last_finish = sorted_acts[i][1]

        return {
            'algorithm': 'Activity Selection (Greedy)',
            'selected': selected,
            'count': len(selected),
            'time_complexity': 'O(n log n)',
            'space_complexity': 'O(n)',
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }

    # ==================== FRACTIONAL KNAPSACK ====================
    @profile_algorithm
    def fractional_knapsack(self, weights: List[int], values: List[int], capacity: int) -> Dict:
        self.reset()
        n = len(weights)
        items = [(values[i] / weights[i], weights[i], values[i], i) for i in range(n)]
        items.sort(reverse=True)  # Sort by value/weight ratio descending

        total_value = 0.0
        selected = []
        remaining = capacity

        for ratio, w, v, idx in items:
            self.iterations += 1
            self.comparisons += 1
            if remaining >= w:
                selected.append((idx, 1.0, v))
                total_value += v
                remaining -= w
            else:
                fraction = remaining / w
                selected.append((idx, fraction, v * fraction))
                total_value += v * fraction
                remaining = 0
                break

        return {
            'algorithm': 'Fractional Knapsack (Greedy)',
            'max_value': total_value,
            'selected_items': selected,
            'time_complexity': 'O(n log n)',
            'space_complexity': 'O(n)',
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }

    # ==================== HUFFMAN CODING ====================
    @profile_algorithm
    def huffman_coding(self, frequencies: Dict[str, int]) -> Dict:
        self.reset()
        if len(frequencies) == 0:
            return {'algorithm': 'Huffman Coding', 'codes': {}, 'time_complexity': 'O(n log n)', 'space_complexity': 'O(n)'}

        heap = [[weight, [symbol, ""]] for symbol, weight in frequencies.items()]
        heapq.heapify(heap)

        while len(heap) > 1:
            self.iterations += 1
            lo = heapq.heappop(heap)
            hi = heapq.heappop(heap)
            for pair in lo[1:]:
                pair[1] = '0' + pair[1]
            for pair in hi[1:]:
                pair[1] = '1' + pair[1]
            heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

        result = sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))
        codes = {symbol: code for symbol, code in result}

        # Calculate total bits
        total_bits = sum(frequencies[s] * len(codes[s]) for s in frequencies)

        return {
            'algorithm': 'Huffman Coding',
            'codes': codes,
            'total_bits': total_bits,
            'average_bits': total_bits / sum(frequencies.values()),
            'time_complexity': 'O(n log n)',
            'space_complexity': 'O(n)',
            'iterations': self.iterations,
        }

    # ==================== JOB SEQUENCING WITH DEADLINES ====================
    @profile_algorithm
    def job_sequencing(self, jobs: List[Tuple[str, int, int]]) -> Dict:
        """
        jobs: list of (job_id, deadline, profit)
        """
        self.reset()
        n = len(jobs)
        # Sort by profit descending
        jobs_sorted = sorted(jobs, key=lambda x: x[2], reverse=True)
        max_deadline = max(j[1] for j in jobs)
        slot = [-1] * (max_deadline + 1)

        scheduled = []
        total_profit = 0

        for job_id, deadline, profit in jobs_sorted:
            self.iterations += 1
            # Find latest available slot before deadline
            for t in range(min(deadline, max_deadline), 0, -1):
                self.comparisons += 1
                if slot[t] == -1:
                    slot[t] = job_id
                    scheduled.append((job_id, t))
                    total_profit += profit
                    break

        return {
            'algorithm': 'Job Sequencing with Deadlines',
            'scheduled_jobs': scheduled,
            'total_profit': total_profit,
            'time_complexity': 'O(n²)',
            'space_complexity': 'O(n)',
            'iterations': self.iterations,
            'comparisons': self.comparisons,
        }

    # ==================== MINIMUM COINS (GREEDY) ====================
    @profile_algorithm
    def minimum_coins_greedy(self, coins: List[int], amount: int) -> Dict:
        """Greedy coin change - works for canonical systems like US coins"""
        self.reset()
        coins_sorted = sorted(coins, reverse=True)
        count = 0
        used = []
        remaining = amount

        for coin in coins_sorted:
            self.iterations += 1
            if remaining >= coin:
                num = remaining // coin
                count += num
                used.extend([coin] * num)
                remaining -= num * coin

        optimal = remaining == 0
        return {
            'algorithm': 'Minimum Coins (Greedy)',
            'min_coins': count if optimal else -1,
            'coins_used': used if optimal else [],
            'optimal': optimal,
            'warning': None if optimal else 'Greedy may not be optimal for this coin system!',
            'time_complexity': 'O(|coins|)',
            'space_complexity': 'O(1)',
            'iterations': self.iterations,
        }