RuslanKain/sorting-searching-recognized-gestures
0
1"""2Base classes for sorting and searching algorithms.3 4This module defines the abstract base classes (interfaces) that all5sorting and searching algorithms must implement.6 7OOP Concepts Demonstrated:8- Abstract Base Classes (ABC)9- Abstract methods (@abstractmethod)10- Properties (@property)11- Generator functions (yield)12- Type hints with Generator13"""14 15from abc import ABC, abstractmethod16from typing import List, Generator, Tuple, Optional17 18from ..models import GestureImage, Step, StepType19 20 21# ==============================================================================22# ABSTRACT CLASS: SortingAlgorithm (The Interface)23# ==============================================================================24 25class SortingAlgorithm(ABC):26 """27 Abstract base class (interface) for all sorting algorithms.28 29 This defines the CONTRACT that all sorting algorithms must follow:30 - They must have a name31 - They must indicate if they're stable32 - They must indicate if they sort in-place33 - They must implement a sort() method that yields steps34 35 ┌─────────────────────────────────────────────────────────────────────────┐36 │ 🔄 PROCEDURAL vs OOP: Algorithm Organization │37 │ │38 │ PROCEDURAL (scattered functions): │39 │ def bubble_sort(arr): ... │40 │ def merge_sort(arr): ... │41 │ def quick_sort(arr): ... │42 │ # No clear structure, hard to add new algorithms │43 │ │44 │ OOP (organized hierarchy): │45 │ class SortingAlgorithm(ABC): # The contract │46 │ def sort(self): ... │47 │ │48 │ class BubbleSort(SortingAlgorithm): # Implements contract │49 │ class MergeSort(SortingAlgorithm): # Implements contract │50 │ class QuickSort(SortingAlgorithm): # Implements contract │51 │ │52 │ # Easy to add new algorithms, all follow same pattern! │53 └─────────────────────────────────────────────────────────────────────────┘54 """55 56 # -------------------------------------------------------------------------57 # Abstract Properties (MUST be implemented by subclasses)58 # -------------------------------------------------------------------------59 60 @property61 @abstractmethod62 def name(self) -> str:63 """The display name of the algorithm (e.g., 'Bubble Sort')."""64 pass65 66 @property67 @abstractmethod68 def is_stable(self) -> bool:69 """70 Whether the algorithm is stable.71 72 A STABLE algorithm preserves the relative order of equal elements.73 74 Example with [✌️₁, ✌️₂, ✊]:75 - Stable: Always produces [✊, ✌️₁, ✌️₂] (original order of peace signs kept)76 - Unstable: Might produce [✊, ✌️₂, ✌️₁] (order can change)77 """78 pass79 80 @property81 @abstractmethod82 def is_in_place(self) -> bool:83 """84 Whether the algorithm sorts in-place (modifies the original array).85 86 In-place: Uses O(1) extra memory (just swaps elements)87 Not in-place: Creates new arrays (uses O(n) extra memory)88 """89 pass90 91 @property92 def description(self) -> str:93 """Human-readable description of the algorithm."""94 stability = "Stable" if self.is_stable else "Unstable"95 memory = "In-place" if self.is_in_place else "Out-of-place"96 return f"{self.name} ({stability}, {memory})"97 98 # -------------------------------------------------------------------------99 # Abstract Method: sort (MUST be implemented by subclasses)100 # -------------------------------------------------------------------------101 102 @abstractmethod103 def sort(self, data: List[GestureImage]) -> Generator[Step, None, List[GestureImage]]:104 """105 Sort the data and yield steps for visualization.106 107 This is a GENERATOR function (uses yield instead of return).108 It allows us to pause the algorithm after each step for visualization.109 110 Args:111 data: List of GestureImage objects to sort112 113 Yields:114 Step objects describing each operation115 116 Returns:117 The sorted list118 """119 pass120 121 # -------------------------------------------------------------------------122 # Concrete Methods (shared by all subclasses)123 # -------------------------------------------------------------------------124 125 def run_full(self, data: List[GestureImage]) -> Tuple[List[GestureImage], List[Step]]:126 """127 Run the sort and collect all steps (non-generator version).128 129 Use this when you want all steps at once, not one at a time.130 131 Args:132 data: List to sort133 134 Returns:135 Tuple of (sorted_list, list_of_all_steps)136 """137 steps = []138 result = None139 140 # Consume the generator and collect steps141 generator = self.sort(data.copy())142 try:143 while True:144 step = next(generator)145 steps.append(step)146 except StopIteration as e:147 result = e.value # The return value of the generator148 149 return result if result else data, steps150 151 def _create_step(152 self,153 step_type: StepType,154 indices: List[int],155 description: str,156 data: List[GestureImage],157 depth: int = 0,158 highlight: List[int] = None,159 metadata: dict = None160 ) -> Step:161 """162 Helper method to create a Step object.163 164 The underscore prefix indicates this is for internal use.165 """166 return Step(167 step_type=step_type,168 indices=indices,169 description=description,170 depth=depth,171 array_state=[img for img in data], # Copy the current state172 highlight_indices=highlight or [],173 metadata=metadata or {}174 )175 176 177# ==============================================================================178# ABSTRACT CLASS: SearchAlgorithm (The Interface for Search Algorithms)179# ==============================================================================180 181class SearchAlgorithm(ABC):182 """183 Abstract base class (interface) for all search algorithms.184 185 This is similar to SortingAlgorithm but for searching.186 By having a common interface, we can swap between different187 search algorithms easily (Linear Search, Binary Search, etc.)188 189 ┌─────────────────────────────────────────────────────────────────────────┐190 │ 🔄 PROCEDURAL vs OOP: Search Functions │191 │ │192 │ PROCEDURAL: │193 │ def linear_search(arr, target): ... │194 │ def binary_search(arr, target): ... │195 │ # No clear structure, different return types, etc. │196 │ │197 │ OOP: │198 │ class SearchAlgorithm(ABC): │199 │ def search(self, data, target) -> Generator[Step]: ... │200 │ │201 │ class LinearSearch(SearchAlgorithm): ... │202 │ class BinarySearch(SearchAlgorithm): ... │203 │ │204 │ # All search algorithms follow the same pattern! │205 └─────────────────────────────────────────────────────────────────────────┘206 """207 208 @property209 @abstractmethod210 def name(self) -> str:211 """The display name of the algorithm."""212 pass213 214 @property215 @abstractmethod216 def requires_sorted(self) -> bool:217 """Whether the algorithm requires sorted input."""218 pass219 220 @property221 def description(self) -> str:222 """Human-readable description."""223 sorted_req = "requires sorted input" if self.requires_sorted else "works on unsorted"224 return f"{self.name} ({sorted_req})"225 226 @abstractmethod227 def search(228 self,229 data: List[GestureImage],230 target: GestureImage231 ) -> Generator[Step, None, Optional[int]]:232 """233 Search for target in data and yield steps for visualization.234 235 Args:236 data: List to search in237 target: Element to find238 239 Yields:240 Step objects describing each operation241 242 Returns:243 Index of target if found, None otherwise244 """245 pass246 247 def run_full(248 self,249 data: List[GestureImage],250 target: GestureImage251 ) -> Tuple[Optional[int], List[Step]]:252 """253 Run the search and collect all steps.254 255 Returns:256 Tuple of (result_index, list_of_all_steps)257 """258 steps = []259 result = None260 261 generator = self.search(data, target)262 try:263 while True:264 step = next(generator)265 steps.append(step)266 except StopIteration as e:267 result = e.value268 269 return result, steps270 271 def _create_step(272 self,273 step_type: StepType,274 indices: List[int],275 description: str,276 data: List[GestureImage],277 highlight: List[int] = None,278 metadata: dict = None279 ) -> Step:280 """Helper to create Step objects."""281 return Step(282 step_type=step_type,283 indices=indices,284 description=description,285 depth=0,286 array_state=[img for img in data],287 highlight_indices=highlight or [],288 metadata=metadata or {}289 )290