algorithms/search.py

"""
USSU Algorithm Analyzer v4.0 - Searching Algorithms Suite
Complete with complexity tracking, metrics, and step logging.
"""
import math
import time
import random
from typing import List, Dict, Any, Optional
from utils.core import profile_algorithm, OperationCounter


class SearchingAlgorithms(OperationCounter):
    """Complete suite of searching algorithms"""

    def __init__(self):
        super().__init__()
        self.steps: List[Dict] = []

    def reset(self):
        self.reset_counters()
        self.steps = []

    def _make_result(self, name: str, found: bool, index: int, time_c: str, space_c: str,
                     arr_size: int, target: Any) -> Dict:
        return {
            'algorithm': name,
            'found': found,
            'index': index,
            'time_complexity': time_c,
            'space_complexity': space_c,
            'array_size': arr_size,
            'target': target,
            'comparisons': self.comparisons,
            'accesses': self.accesses,
            'recursions': self.recursions,
        }

    @profile_algorithm
    def linear_search(self, arr: List[Any], target: Any) -> Dict:
        self.reset()
        for i, val in enumerate(arr):
            self.comparisons += 1
            self.accesses += 1
            if val == target:
                return self._make_result('Linear Search', True, i, 'O(n)', 'O(1)', len(arr), target)
        return self._make_result('Linear Search', False, -1, 'O(n)', 'O(1)', len(arr), target)

    @profile_algorithm
    def binary_search_iterative(self, arr: List[Any], target: Any) -> Dict:
        self.reset()
        left, right = 0, len(arr) - 1
        while left <= right:
            self.comparisons += 1
            mid = (left + right) // 2
            self.accesses += 1
            if arr[mid] == target:
                return self._make_result('Binary Search (Iterative)', True, mid, 'O(log n)', 'O(1)', len(arr), target)
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return self._make_result('Binary Search (Iterative)', False, -1, 'O(log n)', 'O(1)', len(arr), target)

    @profile_algorithm
    def binary_search_recursive(self, arr: List[Any], target: Any, left: int = 0, right: int = None, _is_outer: bool = True) -> Dict:
        if right is None:
            self.reset()
            right = len(arr) - 1
        if _is_outer:
            self.recursions += 1
        if left > right:
            return self._make_result('Binary Search (Recursive)', False, -1, 'O(log n)', 'O(log n)', len(arr), target)
        self.comparisons += 1
        mid = (left + right) // 2
        self.accesses += 1
        if arr[mid] == target:
            return self._make_result('Binary Search (Recursive)', True, mid, 'O(log n)', 'O(log n)', len(arr), target)
        elif arr[mid] < target:
            return self.binary_search_recursive(arr, target, mid + 1, right, _is_outer=False)
        else:
            return self.binary_search_recursive(arr, target, left, mid - 1, _is_outer=False)

    @profile_algorithm
    def jump_search(self, arr: List[Any], target: Any) -> Dict:
        self.reset()
        n = len(arr)
        step = int(math.sqrt(n))
        prev = 0
        while prev < n and arr[min(step, n) - 1] < target:
            self.comparisons += 1
            self.accesses += 1
            prev = step
            step += int(math.sqrt(n))
            if prev >= n:
                return self._make_result('Jump Search', False, -1, 'O(√n)', 'O(1)', n, target)
        while prev < min(step, n) and arr[prev] < target:
            self.comparisons += 1
            self.accesses += 1
            prev += 1
        self.accesses += 1
        if prev < n and arr[prev] == target:
            return self._make_result('Jump Search', True, prev, 'O(√n)', 'O(1)', n, target)
        return self._make_result('Jump Search', False, -1, 'O(√n)', 'O(1)', n, target)

    @profile_algorithm
    def interpolation_search(self, arr: List[Any], target: Any) -> Dict:
        self.reset()
        left, right = 0, len(arr) - 1
        while left <= right and target >= arr[left] and target <= arr[right]:
            self.comparisons += 1
            if left == right:
                self.accesses += 1
                if arr[left] == target:
                    return self._make_result('Interpolation Search', True, left, 'O(log log n) avg', 'O(1)', len(arr), target)
                break
            pos = left + int(((target - arr[left]) / (arr[right] - arr[left])) * (right - left))
            self.accesses += 1
            if arr[pos] == target:
                return self._make_result('Interpolation Search', True, pos, 'O(log log n) avg', 'O(1)', len(arr), target)
            elif arr[pos] < target:
                left = pos + 1
            else:
                right = pos - 1
        return self._make_result('Interpolation Search', False, -1, 'O(log log n) avg', 'O(1)', len(arr), target)

    @profile_algorithm
    def exponential_search(self, arr: List[Any], target: Any) -> Dict:
        self.reset()
        n = len(arr)
        if n == 0:
            return self._make_result('Exponential Search', False, -1, 'O(log n)', 'O(1)', 0, target)
        self.accesses += 1
        if arr[0] == target:
            return self._make_result('Exponential Search', True, 0, 'O(log n)', 'O(1)', n, target)
        bound = 1
        while bound < n and arr[bound] <= target:
            self.comparisons += 1
            self.accesses += 1
            bound *= 2
        left = bound // 2
        right = min(bound, n - 1)
        while left <= right:
            self.comparisons += 1
            mid = (left + right) // 2
            self.accesses += 1
            if arr[mid] == target:
                return self._make_result('Exponential Search', True, mid, 'O(log n)', 'O(1)', n, target)
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return self._make_result('Exponential Search', False, -1, 'O(log n)', 'O(1)', n, target)

    @profile_algorithm
    def ternary_search(self, arr: List[Any], target: Any) -> Dict:
        self.reset()
        left, right = 0, len(arr) - 1
        while left <= right:
            self.comparisons += 1
            third = (right - left) // 3
            mid1 = left + third
            mid2 = right - third
            self.accesses += 2
            if arr[mid1] == target:
                return self._make_result('Ternary Search', True, mid1, 'O(log₃ n)', 'O(1)', len(arr), target)
            if arr[mid2] == target:
                return self._make_result('Ternary Search', True, mid2, 'O(log₃ n)', 'O(1)', len(arr), target)
            if target < arr[mid1]:
                right = mid1 - 1
            elif target > arr[mid2]:
                left = mid2 + 1
            else:
                left = mid1 + 1
                right = mid2 - 1
        return self._make_result('Ternary Search', False, -1, 'O(log₃ n)', 'O(1)', len(arr), target)

    @profile_algorithm
    def fibonacci_search(self, arr: List[Any], target: Any) -> Dict:
        self.reset()
        n = len(arr)
        fib2, fib1 = 0, 1
        fib = fib1 + fib2
        while fib < n:
            fib2 = fib1
            fib1 = fib
            fib = fib1 + fib2
        offset = -1
        while fib > 1:
            i = min(offset + fib2, n - 1)
            self.accesses += 1
            self.comparisons += 1
            if arr[i] < target:
                fib = fib1
                fib1 = fib2
                fib2 = fib - fib1
                offset = i
            elif arr[i] > target:
                fib = fib2
                fib1 = fib1 - fib2
                fib2 = fib - fib1
            else:
                return self._make_result('Fibonacci Search', True, i, 'O(log n)', 'O(1)', n, target)
        self.accesses += 1
        if fib1 and offset + 1 < n and arr[offset + 1] == target:
            return self._make_result('Fibonacci Search', True, offset + 1, 'O(log n)', 'O(1)', n, target)
        return self._make_result('Fibonacci Search', False, -1, 'O(log n)', 'O(1)', n, target)

    def compare_all(self, arr: List[Any], target: Any) -> List[Dict]:
        """Benchmark all searching algorithms"""
        sorted_arr = sorted(arr)
        algorithms = [
            ('Linear Search', self.linear_search),
            ('Binary Search (Iter)', self.binary_search_iterative),
            ('Binary Search (Rec)', self.binary_search_recursive),
            ('Jump Search', self.jump_search),
            ('Interpolation Search', self.interpolation_search),
            ('Exponential Search', self.exponential_search),
            ('Ternary Search', self.ternary_search),
            ('Fibonacci Search', self.fibonacci_search),
        ]
        results = []
        for name, algo in algorithms:
            try:
                res = algo(sorted_arr if name != 'Linear Search' else arr, target)
                results.append({
                    'name': name,
                    'time_ms': res.get('execution_time_ms', 0),
                    'complexity': res.get('time_complexity', 'N/A'),
                    'found': res.get('found', False),
                    'index': res.get('index', -1),
                    'comparisons': res.get('comparisons', 0),
                })
            except Exception as e:
                results.append({'name': name, 'error': str(e)})
        return results