dsa.array
Module containing array classes.
1""" Module containing array classes. """ 2 3class Array: 4 """ 5 A static array implementation. 6 7 Special Methods: 8 Index Operator: array[index] 9 Assignment: array[index] = value 10 11 Equality: 12 Array instances can be compared for equality with other Array or DynamicArray instances (but not CircularArray), based on their contents. 13 """ 14 def __init__(self, contents=None, capacity: int=10): 15 """ 16 Initialize the array with optional contents and a fixed capacity. 17 18 Args: 19 contents: An optional iterable to fill array with default values. 20 capacity (int): The initial size of the array (default is 10) 21 """ 22 self._array = [ None ] * capacity 23 #: number of elements currently in array 24 self.count = 0 25 26 if contents: 27 self.extend(contents) 28 29 def append(self, element): 30 """ 31 Append an element to the array. Raise an exception if capacity is exceeded. 32 33 Args: 34 element: The element to append. 35 36 Raises: 37 Exception: If the array is full. 38 """ 39 if self.count >= self.capacity(): 40 raise Exception(f"Capacity Error: Maximum capacity {len(self)} reached.") 41 42 self._array[self.count] = element 43 self.count += 1 44 45 def extend(self, array): 46 """ 47 Append multiple elements from a given array. 48 49 Args: 50 array: An iterable containing elements to append. 51 52 Raises: 53 Exception: If appending the elements exceeds the array's capacity. 54 """ 55 for e in array: 56 self.append(e) 57 58 def insert(self, index: int, element): 59 """ 60 Insert an element at a specified index, shifting existing elements to the right. 61 62 Args: 63 index (int): The index at which to insert the element. 64 element: The element to insert. 65 66 Raises: 67 IndexError: If the index is out of bounds. 68 """ 69 if index == self.count: 70 self.append(element) 71 return 72 73 if index < 0 or index > self.count: 74 raise IndexError 75 76 self.shift_right(index) 77 self._array[index] = element 78 self.count += 1 79 80 def shift_right(self, start: int): 81 """ 82 Helper method to shift elements to the right from a specified start index until the last element. 83 (May delete an element but does not affect the count.) 84 Args: 85 start (int): The index at which to start shifting (inclusive). 86 87 Raises: 88 Exception: If the array is full and cannot accommodate the shift. 89 """ 90 if self.count >= len(self._array): 91 raise Exception(f"Capacity Error: Maximum capacity {len(self)} reached.") 92 end = self.count 93 for i in range(end, start, -1): 94 self._array[i] = self._array[i - 1] 95 96 def delete(self, index: int): 97 """ 98 Delete an element at a specified index, shifting subsequent elements to the left. 99 100 Args: 101 index (int): The index of the element to delete. 102 103 Raises: 104 IndexError: If index is out of bounds. 105 """ 106 if index < 0 or index >= self.count: 107 raise IndexError 108 109 self.shift_left(index) 110 self.count -= 1 111 112 def shift_left(self, start: int): 113 """ 114 Helper method to shift elements to the left starting at a start index. 115 (May delete an element but does not affect the count.) 116 117 Args: 118 start (int): The starting index of the shift. 119 """ 120 for i in range(start, self.count - 1): 121 self._array[i] = self._array[i + 1] 122 123 def __getitem__(self, index: int): 124 """ 125 Retrieve the element at the specified index. 126 127 Args: 128 index (int): The index of the element. 129 130 Returns: 131 The element at the specified index. 132 133 Raises: 134 IndexError: If the index is out of bounds. 135 """ 136 if index < 0 or index >= self.count: 137 raise IndexError 138 return self._array[index] 139 140 def __setitem__(self, index: int, value): 141 """ 142 Set a new value at the specified index. 143 144 Args: 145 index (int): The index at which to set the value. 146 value: The new value to assign. 147 148 Raises: 149 IndexError: If the index is out of bounds. 150 """ 151 if index < 0 or index >= self.count: 152 raise IndexError 153 self._array[index] = value 154 155 def __len__(self) -> int: 156 """ 157 Return the number of elements in the array. 158 159 Returns: 160 The number of elements in the array. 161 """ 162 return self.count 163 164 def is_empty(self) -> bool: 165 """ 166 Check if the array is empty. 167 168 Returns: 169 True if the array is empty, False otherwise. 170 """ 171 return self.count == 0 172 173 def capacity(self) -> int: 174 """ 175 Get the total capacity of the array. 176 177 Returns: 178 The capacity of the array. 179 """ 180 return len(self._array) 181 182 def to_list(self) -> list: 183 """ 184 Convert the array's elements to a standard Python list. 185 186 Returns: 187 A list containing the elements of the array. 188 """ 189 return self._array[:self.count] 190 191 @classmethod 192 def from_list(cls, mylist: list): 193 """ 194 Create an array from a standard Python list. 195 196 Args: 197 mylist: A Python list to initialize the array. 198 199 Returns: 200 An instance of the Array class. 201 """ 202 list_instance = cls() 203 list_instance.extend(mylist) 204 205 return list_instance 206 207 def __repr__(self): 208 """ 209 Represent the array's contents, count, and capacity. 210 211 Returns: 212 A string representation of the array. 213 """ 214 return f'{self.to_list()} Count: {self.count} Capacity: {self.capacity()}' 215 216 def __eq__(self, other): 217 """ 218 Compare this array to another for equality. 219 220 Args: 221 other: The object to compare with. 222 223 Returns: 224 True if both objects are Array, DynamicArray, or CircularArray instances and their contents are equal. 225 For non-array types, returns NotImplemented to allow reverse comparison. 226 """ 227 if isinstance(other, (Array, DynamicArray, CircularArray)): 228 return self.to_list() == other.to_list() 229 return NotImplemented 230 231class DynamicArray(Array): 232 """ 233 A dynamic array implementation. Capacity will adjust as needed. 234 235 Special Methods: 236 Index Operator: array[index] 237 Assignment: array[index] = value 238 239 Equality: 240 DynamicArray instances can be compared for equality with other DynamicArray or Array instances (but not CircularArray), based on their contents. 241 """ 242 243 def grow(self): 244 """ 245 Helper method to double the capacity of the current array. 246 """ 247 new_size = len(self._array) * 2 248 new_array = [ None ] * new_size 249 250 # copy elements 251 for i in range(len(self._array)): 252 new_array[i] = self._array[i] 253 254 self._array = new_array 255 256 def shrink(self): 257 """ 258 Helper method to halve the capacity of the current array. 259 """ 260 new_size = len(self._array) // 2 261 new_array = [ None ] * new_size 262 263 # copy elements 264 for i in range(new_size): 265 new_array[i] = self._array[i] 266 267 self._array = new_array 268 269 def check_capacity(self): 270 """ 271 if count >= capacity, grow the array. 272 if count <= 1/4 of capacity, shrink the array. 273 """ 274 if self.count >= len(self._array): 275 self.grow() 276 elif self.count * 4 <= len(self._array): 277 self.shrink() 278 279 def append(self, element): 280 """ 281 Append an element to the array. Adjust the capacity as needed. 282 283 Args: 284 element: The element to append. 285 """ 286 self.check_capacity() 287 288 self._array[self.count] = element 289 self.count += 1 290 291 def extend(self, array): 292 """ 293 Append multiple elements from a given array. Adjust the capacity as needed. 294 295 Args: 296 array: An iterable containing elements to append. 297 """ 298 for e in array: 299 self.append(e) 300 301 def insert(self, index: int, element): 302 """ 303 Insert an element at a specified index, shifting existing elements to the right. Adjust the capacity as needed. 304 305 Args: 306 index (int): The index at which to insert the element. 307 element: The element to insert. 308 """ 309 if index >= self.count or index < 0: 310 raise IndexError 311 312 self.check_capacity() 313 314 self.shift_right(index) 315 self._array[index] = element 316 self.count += 1 317 318 def delete(self, index: int): 319 """ 320 Delete an element at a specified index, shifting subsequent elements to the left. Adjust the capacity as needed. 321 322 Args: 323 index (int): The index of the element to delete. 324 """ 325 if index >= self.count or index < 0: 326 raise IndexError 327 328 self.check_capacity() 329 330 self.shift_left(index) 331 self.count -= 1 332 333 334class CircularArray(Array): 335 """ 336 A circular array implementation. 337 338 Special Methods: 339 340 Index Operator: 341 array[index] 342 343 Assignment: 344 array[index] = value 345 """ 346 def __init__(self, contents=None, capacity: int=10): 347 """ 348 Initialize the circular array with optional contents and a fixed capacity. 349 350 Args: 351 contents: An optional iterable to fill array with default values. 352 capacity (int): The initial size of the array (default is 10) 353 """ 354 super().__init__(None, capacity) 355 #: index of the first element in the circular array 356 self._start = 0 357 if contents: 358 self.extend(contents) 359 360 def __getitem__(self, index: int): 361 """ 362 Retrieve the element at the specified index. 363 364 Args: 365 index (int): The index of the element. 366 367 Returns: 368 The element at the specified index. 369 370 Raises: 371 IndexError: If the index is out of bounds. 372 """ 373 if index < 0 or index >= self.count: 374 raise IndexError 375 return self._array[(self._start + index) % len(self._array)] 376 377 def __setitem__(self, index: int, value): 378 """ 379 Set a new value at the specified index. 380 381 Args: 382 index (int): The index at which to set the value. 383 value: The new value to assign. 384 385 Raises: 386 IndexError: If the index is out of bounds. 387 """ 388 if index < 0 or index >= self.count: 389 raise IndexError 390 self._array[(self._start + index) % len(self._array)] = value 391 392 def append(self, element): 393 """ 394 Append an element to the circular array. If appending exceeds capacity, it will wrap around to the oldest element. 395 396 Args: 397 element: The element to append. 398 """ 399 # self._array[(self._start + self.count) % len(self._array)] = element 400 # if self.count < self.capacity(): 401 # self.count += 1 402 # else: 403 # self._start = (self._start + 1) % len(self._array) 404 index = (self._start + self.count) % len(self._array) 405 self._array[index] = element 406 407 if self.count < self.capacity(): 408 self.count += 1 409 else: 410 self._start = (self._start + 1) % len(self._array) # Overwrite oldest element 411 412 def raw_view(self): 413 """ 414 Return a raw view of the array. 415 416 Returns: 417 A raw view of the array. 418 """ 419 return self._array 420 421 def to_list(self): 422 """ 423 Convert the array's elements to a standard Python list. 424 425 Returns: 426 A list containing the elements of the array. 427 """ 428 output_list = [] 429 for i in range(self.count): 430 output_list.append(self._array[(self._start + i) % len(self._array)]) 431 return output_list 432 433 def insert(self, index: int, element): 434 """ 435 Insert an element at a specified index, shifting existing elements to the right. 436 437 Args: 438 index (int): The index at which to insert the element. 439 element: The element to insert. 440 441 Raises: 442 IndexError: If the index is out of bounds. 443 Exception: If the array is full. 444 """ 445 if index < 0 or index > self.count: 446 raise IndexError 447 if self.count >= self.capacity(): 448 raise Exception(f"Capacity Error: Maximum capacity {self.capacity()} reached.") 449 # Shift elements to the right 450 for i in range(self.count, index, -1): 451 self._array[(self._start + i) % self.capacity()] = self._array[(self._start + i - 1) % self.capacity()] 452 self._array[(self._start + index) % self.capacity()] = element 453 self.count += 1 454 455 456 def delete(self, index: int): 457 """ 458 Delete an element at a specified index, shifting subsequent elements to the left. 459 460 Args: 461 index (int): The index of the element to delete. 462 463 Raises: 464 IndexError: If the index is out of bounds. 465 """ 466 if index < 0 or index >= self.count: 467 raise IndexError 468 # Shift elements to the left 469 for i in range(index, self.count - 1): 470 self._array[(self._start + i) % self.capacity()] = self._array[(self._start + i + 1) % self.capacity()] 471 self.count -= 1
class
Array:
4class Array: 5 """ 6 A static array implementation. 7 8 Special Methods: 9 Index Operator: array[index] 10 Assignment: array[index] = value 11 12 Equality: 13 Array instances can be compared for equality with other Array or DynamicArray instances (but not CircularArray), based on their contents. 14 """ 15 def __init__(self, contents=None, capacity: int=10): 16 """ 17 Initialize the array with optional contents and a fixed capacity. 18 19 Args: 20 contents: An optional iterable to fill array with default values. 21 capacity (int): The initial size of the array (default is 10) 22 """ 23 self._array = [ None ] * capacity 24 #: number of elements currently in array 25 self.count = 0 26 27 if contents: 28 self.extend(contents) 29 30 def append(self, element): 31 """ 32 Append an element to the array. Raise an exception if capacity is exceeded. 33 34 Args: 35 element: The element to append. 36 37 Raises: 38 Exception: If the array is full. 39 """ 40 if self.count >= self.capacity(): 41 raise Exception(f"Capacity Error: Maximum capacity {len(self)} reached.") 42 43 self._array[self.count] = element 44 self.count += 1 45 46 def extend(self, array): 47 """ 48 Append multiple elements from a given array. 49 50 Args: 51 array: An iterable containing elements to append. 52 53 Raises: 54 Exception: If appending the elements exceeds the array's capacity. 55 """ 56 for e in array: 57 self.append(e) 58 59 def insert(self, index: int, element): 60 """ 61 Insert an element at a specified index, shifting existing elements to the right. 62 63 Args: 64 index (int): The index at which to insert the element. 65 element: The element to insert. 66 67 Raises: 68 IndexError: If the index is out of bounds. 69 """ 70 if index == self.count: 71 self.append(element) 72 return 73 74 if index < 0 or index > self.count: 75 raise IndexError 76 77 self.shift_right(index) 78 self._array[index] = element 79 self.count += 1 80 81 def shift_right(self, start: int): 82 """ 83 Helper method to shift elements to the right from a specified start index until the last element. 84 (May delete an element but does not affect the count.) 85 Args: 86 start (int): The index at which to start shifting (inclusive). 87 88 Raises: 89 Exception: If the array is full and cannot accommodate the shift. 90 """ 91 if self.count >= len(self._array): 92 raise Exception(f"Capacity Error: Maximum capacity {len(self)} reached.") 93 end = self.count 94 for i in range(end, start, -1): 95 self._array[i] = self._array[i - 1] 96 97 def delete(self, index: int): 98 """ 99 Delete an element at a specified index, shifting subsequent elements to the left. 100 101 Args: 102 index (int): The index of the element to delete. 103 104 Raises: 105 IndexError: If index is out of bounds. 106 """ 107 if index < 0 or index >= self.count: 108 raise IndexError 109 110 self.shift_left(index) 111 self.count -= 1 112 113 def shift_left(self, start: int): 114 """ 115 Helper method to shift elements to the left starting at a start index. 116 (May delete an element but does not affect the count.) 117 118 Args: 119 start (int): The starting index of the shift. 120 """ 121 for i in range(start, self.count - 1): 122 self._array[i] = self._array[i + 1] 123 124 def __getitem__(self, index: int): 125 """ 126 Retrieve the element at the specified index. 127 128 Args: 129 index (int): The index of the element. 130 131 Returns: 132 The element at the specified index. 133 134 Raises: 135 IndexError: If the index is out of bounds. 136 """ 137 if index < 0 or index >= self.count: 138 raise IndexError 139 return self._array[index] 140 141 def __setitem__(self, index: int, value): 142 """ 143 Set a new value at the specified index. 144 145 Args: 146 index (int): The index at which to set the value. 147 value: The new value to assign. 148 149 Raises: 150 IndexError: If the index is out of bounds. 151 """ 152 if index < 0 or index >= self.count: 153 raise IndexError 154 self._array[index] = value 155 156 def __len__(self) -> int: 157 """ 158 Return the number of elements in the array. 159 160 Returns: 161 The number of elements in the array. 162 """ 163 return self.count 164 165 def is_empty(self) -> bool: 166 """ 167 Check if the array is empty. 168 169 Returns: 170 True if the array is empty, False otherwise. 171 """ 172 return self.count == 0 173 174 def capacity(self) -> int: 175 """ 176 Get the total capacity of the array. 177 178 Returns: 179 The capacity of the array. 180 """ 181 return len(self._array) 182 183 def to_list(self) -> list: 184 """ 185 Convert the array's elements to a standard Python list. 186 187 Returns: 188 A list containing the elements of the array. 189 """ 190 return self._array[:self.count] 191 192 @classmethod 193 def from_list(cls, mylist: list): 194 """ 195 Create an array from a standard Python list. 196 197 Args: 198 mylist: A Python list to initialize the array. 199 200 Returns: 201 An instance of the Array class. 202 """ 203 list_instance = cls() 204 list_instance.extend(mylist) 205 206 return list_instance 207 208 def __repr__(self): 209 """ 210 Represent the array's contents, count, and capacity. 211 212 Returns: 213 A string representation of the array. 214 """ 215 return f'{self.to_list()} Count: {self.count} Capacity: {self.capacity()}' 216 217 def __eq__(self, other): 218 """ 219 Compare this array to another for equality. 220 221 Args: 222 other: The object to compare with. 223 224 Returns: 225 True if both objects are Array, DynamicArray, or CircularArray instances and their contents are equal. 226 For non-array types, returns NotImplemented to allow reverse comparison. 227 """ 228 if isinstance(other, (Array, DynamicArray, CircularArray)): 229 return self.to_list() == other.to_list() 230 return NotImplemented
A static array implementation.
Special Methods: Index Operator: array[index] Assignment: array[index] = value
Equality: Array instances can be compared for equality with other Array or DynamicArray instances (but not CircularArray), based on their contents.
Array(contents=None, capacity: int = 10)
15 def __init__(self, contents=None, capacity: int=10): 16 """ 17 Initialize the array with optional contents and a fixed capacity. 18 19 Args: 20 contents: An optional iterable to fill array with default values. 21 capacity (int): The initial size of the array (default is 10) 22 """ 23 self._array = [ None ] * capacity 24 #: number of elements currently in array 25 self.count = 0 26 27 if contents: 28 self.extend(contents)
Initialize the array with optional contents and a fixed capacity.
Args: contents: An optional iterable to fill array with default values. capacity (int): The initial size of the array (default is 10)
def
append(self, element):
30 def append(self, element): 31 """ 32 Append an element to the array. Raise an exception if capacity is exceeded. 33 34 Args: 35 element: The element to append. 36 37 Raises: 38 Exception: If the array is full. 39 """ 40 if self.count >= self.capacity(): 41 raise Exception(f"Capacity Error: Maximum capacity {len(self)} reached.") 42 43 self._array[self.count] = element 44 self.count += 1
Append an element to the array. Raise an exception if capacity is exceeded.
Args: element: The element to append.
Raises: Exception: If the array is full.
def
extend(self, array):
46 def extend(self, array): 47 """ 48 Append multiple elements from a given array. 49 50 Args: 51 array: An iterable containing elements to append. 52 53 Raises: 54 Exception: If appending the elements exceeds the array's capacity. 55 """ 56 for e in array: 57 self.append(e)
Append multiple elements from a given array.
Args: array: An iterable containing elements to append.
Raises: Exception: If appending the elements exceeds the array's capacity.
def
insert(self, index: int, element):
59 def insert(self, index: int, element): 60 """ 61 Insert an element at a specified index, shifting existing elements to the right. 62 63 Args: 64 index (int): The index at which to insert the element. 65 element: The element to insert. 66 67 Raises: 68 IndexError: If the index is out of bounds. 69 """ 70 if index == self.count: 71 self.append(element) 72 return 73 74 if index < 0 or index > self.count: 75 raise IndexError 76 77 self.shift_right(index) 78 self._array[index] = element 79 self.count += 1
Insert an element at a specified index, shifting existing elements to the right.
Args: index (int): The index at which to insert the element. element: The element to insert.
Raises: IndexError: If the index is out of bounds.
def
shift_right(self, start: int):
81 def shift_right(self, start: int): 82 """ 83 Helper method to shift elements to the right from a specified start index until the last element. 84 (May delete an element but does not affect the count.) 85 Args: 86 start (int): The index at which to start shifting (inclusive). 87 88 Raises: 89 Exception: If the array is full and cannot accommodate the shift. 90 """ 91 if self.count >= len(self._array): 92 raise Exception(f"Capacity Error: Maximum capacity {len(self)} reached.") 93 end = self.count 94 for i in range(end, start, -1): 95 self._array[i] = self._array[i - 1]
Helper method to shift elements to the right from a specified start index until the last element. (May delete an element but does not affect the count.) Args: start (int): The index at which to start shifting (inclusive).
Raises: Exception: If the array is full and cannot accommodate the shift.
def
delete(self, index: int):
97 def delete(self, index: int): 98 """ 99 Delete an element at a specified index, shifting subsequent elements to the left. 100 101 Args: 102 index (int): The index of the element to delete. 103 104 Raises: 105 IndexError: If index is out of bounds. 106 """ 107 if index < 0 or index >= self.count: 108 raise IndexError 109 110 self.shift_left(index) 111 self.count -= 1
Delete an element at a specified index, shifting subsequent elements to the left.
Args: index (int): The index of the element to delete.
Raises:
IndexError: If index is out of bounds.
def
shift_left(self, start: int):
113 def shift_left(self, start: int): 114 """ 115 Helper method to shift elements to the left starting at a start index. 116 (May delete an element but does not affect the count.) 117 118 Args: 119 start (int): The starting index of the shift. 120 """ 121 for i in range(start, self.count - 1): 122 self._array[i] = self._array[i + 1]
Helper method to shift elements to the left starting at a start index. (May delete an element but does not affect the count.)
Args: start (int): The starting index of the shift.
def
is_empty(self) -> bool:
165 def is_empty(self) -> bool: 166 """ 167 Check if the array is empty. 168 169 Returns: 170 True if the array is empty, False otherwise. 171 """ 172 return self.count == 0
Check if the array is empty.
Returns: True if the array is empty, False otherwise.
def
capacity(self) -> int:
174 def capacity(self) -> int: 175 """ 176 Get the total capacity of the array. 177 178 Returns: 179 The capacity of the array. 180 """ 181 return len(self._array)
Get the total capacity of the array.
Returns: The capacity of the array.
def
to_list(self) -> list:
183 def to_list(self) -> list: 184 """ 185 Convert the array's elements to a standard Python list. 186 187 Returns: 188 A list containing the elements of the array. 189 """ 190 return self._array[:self.count]
Convert the array's elements to a standard Python list.
Returns: A list containing the elements of the array.
@classmethod
def
from_list(cls, mylist: list):
192 @classmethod 193 def from_list(cls, mylist: list): 194 """ 195 Create an array from a standard Python list. 196 197 Args: 198 mylist: A Python list to initialize the array. 199 200 Returns: 201 An instance of the Array class. 202 """ 203 list_instance = cls() 204 list_instance.extend(mylist) 205 206 return list_instance
Create an array from a standard Python list.
Args: mylist: A Python list to initialize the array.
Returns: An instance of the Array class.
232class DynamicArray(Array): 233 """ 234 A dynamic array implementation. Capacity will adjust as needed. 235 236 Special Methods: 237 Index Operator: array[index] 238 Assignment: array[index] = value 239 240 Equality: 241 DynamicArray instances can be compared for equality with other DynamicArray or Array instances (but not CircularArray), based on their contents. 242 """ 243 244 def grow(self): 245 """ 246 Helper method to double the capacity of the current array. 247 """ 248 new_size = len(self._array) * 2 249 new_array = [ None ] * new_size 250 251 # copy elements 252 for i in range(len(self._array)): 253 new_array[i] = self._array[i] 254 255 self._array = new_array 256 257 def shrink(self): 258 """ 259 Helper method to halve the capacity of the current array. 260 """ 261 new_size = len(self._array) // 2 262 new_array = [ None ] * new_size 263 264 # copy elements 265 for i in range(new_size): 266 new_array[i] = self._array[i] 267 268 self._array = new_array 269 270 def check_capacity(self): 271 """ 272 if count >= capacity, grow the array. 273 if count <= 1/4 of capacity, shrink the array. 274 """ 275 if self.count >= len(self._array): 276 self.grow() 277 elif self.count * 4 <= len(self._array): 278 self.shrink() 279 280 def append(self, element): 281 """ 282 Append an element to the array. Adjust the capacity as needed. 283 284 Args: 285 element: The element to append. 286 """ 287 self.check_capacity() 288 289 self._array[self.count] = element 290 self.count += 1 291 292 def extend(self, array): 293 """ 294 Append multiple elements from a given array. Adjust the capacity as needed. 295 296 Args: 297 array: An iterable containing elements to append. 298 """ 299 for e in array: 300 self.append(e) 301 302 def insert(self, index: int, element): 303 """ 304 Insert an element at a specified index, shifting existing elements to the right. Adjust the capacity as needed. 305 306 Args: 307 index (int): The index at which to insert the element. 308 element: The element to insert. 309 """ 310 if index >= self.count or index < 0: 311 raise IndexError 312 313 self.check_capacity() 314 315 self.shift_right(index) 316 self._array[index] = element 317 self.count += 1 318 319 def delete(self, index: int): 320 """ 321 Delete an element at a specified index, shifting subsequent elements to the left. Adjust the capacity as needed. 322 323 Args: 324 index (int): The index of the element to delete. 325 """ 326 if index >= self.count or index < 0: 327 raise IndexError 328 329 self.check_capacity() 330 331 self.shift_left(index) 332 self.count -= 1
A dynamic array implementation. Capacity will adjust as needed.
Special Methods: Index Operator: array[index] Assignment: array[index] = value
Equality: DynamicArray instances can be compared for equality with other DynamicArray or Array instances (but not CircularArray), based on their contents.
def
grow(self):
244 def grow(self): 245 """ 246 Helper method to double the capacity of the current array. 247 """ 248 new_size = len(self._array) * 2 249 new_array = [ None ] * new_size 250 251 # copy elements 252 for i in range(len(self._array)): 253 new_array[i] = self._array[i] 254 255 self._array = new_array
Helper method to double the capacity of the current array.
def
shrink(self):
257 def shrink(self): 258 """ 259 Helper method to halve the capacity of the current array. 260 """ 261 new_size = len(self._array) // 2 262 new_array = [ None ] * new_size 263 264 # copy elements 265 for i in range(new_size): 266 new_array[i] = self._array[i] 267 268 self._array = new_array
Helper method to halve the capacity of the current array.
def
check_capacity(self):
270 def check_capacity(self): 271 """ 272 if count >= capacity, grow the array. 273 if count <= 1/4 of capacity, shrink the array. 274 """ 275 if self.count >= len(self._array): 276 self.grow() 277 elif self.count * 4 <= len(self._array): 278 self.shrink()
if count >= capacity, grow the array. if count <= 1/4 of capacity, shrink the array.
def
append(self, element):
280 def append(self, element): 281 """ 282 Append an element to the array. Adjust the capacity as needed. 283 284 Args: 285 element: The element to append. 286 """ 287 self.check_capacity() 288 289 self._array[self.count] = element 290 self.count += 1
Append an element to the array. Adjust the capacity as needed.
Args: element: The element to append.
def
extend(self, array):
292 def extend(self, array): 293 """ 294 Append multiple elements from a given array. Adjust the capacity as needed. 295 296 Args: 297 array: An iterable containing elements to append. 298 """ 299 for e in array: 300 self.append(e)
Append multiple elements from a given array. Adjust the capacity as needed.
Args: array: An iterable containing elements to append.
def
insert(self, index: int, element):
302 def insert(self, index: int, element): 303 """ 304 Insert an element at a specified index, shifting existing elements to the right. Adjust the capacity as needed. 305 306 Args: 307 index (int): The index at which to insert the element. 308 element: The element to insert. 309 """ 310 if index >= self.count or index < 0: 311 raise IndexError 312 313 self.check_capacity() 314 315 self.shift_right(index) 316 self._array[index] = element 317 self.count += 1
Insert an element at a specified index, shifting existing elements to the right. Adjust the capacity as needed.
Args: index (int): The index at which to insert the element. element: The element to insert.
def
delete(self, index: int):
319 def delete(self, index: int): 320 """ 321 Delete an element at a specified index, shifting subsequent elements to the left. Adjust the capacity as needed. 322 323 Args: 324 index (int): The index of the element to delete. 325 """ 326 if index >= self.count or index < 0: 327 raise IndexError 328 329 self.check_capacity() 330 331 self.shift_left(index) 332 self.count -= 1
Delete an element at a specified index, shifting subsequent elements to the left. Adjust the capacity as needed.
Args: index (int): The index of the element to delete.
Inherited Members
335class CircularArray(Array): 336 """ 337 A circular array implementation. 338 339 Special Methods: 340 341 Index Operator: 342 array[index] 343 344 Assignment: 345 array[index] = value 346 """ 347 def __init__(self, contents=None, capacity: int=10): 348 """ 349 Initialize the circular array with optional contents and a fixed capacity. 350 351 Args: 352 contents: An optional iterable to fill array with default values. 353 capacity (int): The initial size of the array (default is 10) 354 """ 355 super().__init__(None, capacity) 356 #: index of the first element in the circular array 357 self._start = 0 358 if contents: 359 self.extend(contents) 360 361 def __getitem__(self, index: int): 362 """ 363 Retrieve the element at the specified index. 364 365 Args: 366 index (int): The index of the element. 367 368 Returns: 369 The element at the specified index. 370 371 Raises: 372 IndexError: If the index is out of bounds. 373 """ 374 if index < 0 or index >= self.count: 375 raise IndexError 376 return self._array[(self._start + index) % len(self._array)] 377 378 def __setitem__(self, index: int, value): 379 """ 380 Set a new value at the specified index. 381 382 Args: 383 index (int): The index at which to set the value. 384 value: The new value to assign. 385 386 Raises: 387 IndexError: If the index is out of bounds. 388 """ 389 if index < 0 or index >= self.count: 390 raise IndexError 391 self._array[(self._start + index) % len(self._array)] = value 392 393 def append(self, element): 394 """ 395 Append an element to the circular array. If appending exceeds capacity, it will wrap around to the oldest element. 396 397 Args: 398 element: The element to append. 399 """ 400 # self._array[(self._start + self.count) % len(self._array)] = element 401 # if self.count < self.capacity(): 402 # self.count += 1 403 # else: 404 # self._start = (self._start + 1) % len(self._array) 405 index = (self._start + self.count) % len(self._array) 406 self._array[index] = element 407 408 if self.count < self.capacity(): 409 self.count += 1 410 else: 411 self._start = (self._start + 1) % len(self._array) # Overwrite oldest element 412 413 def raw_view(self): 414 """ 415 Return a raw view of the array. 416 417 Returns: 418 A raw view of the array. 419 """ 420 return self._array 421 422 def to_list(self): 423 """ 424 Convert the array's elements to a standard Python list. 425 426 Returns: 427 A list containing the elements of the array. 428 """ 429 output_list = [] 430 for i in range(self.count): 431 output_list.append(self._array[(self._start + i) % len(self._array)]) 432 return output_list 433 434 def insert(self, index: int, element): 435 """ 436 Insert an element at a specified index, shifting existing elements to the right. 437 438 Args: 439 index (int): The index at which to insert the element. 440 element: The element to insert. 441 442 Raises: 443 IndexError: If the index is out of bounds. 444 Exception: If the array is full. 445 """ 446 if index < 0 or index > self.count: 447 raise IndexError 448 if self.count >= self.capacity(): 449 raise Exception(f"Capacity Error: Maximum capacity {self.capacity()} reached.") 450 # Shift elements to the right 451 for i in range(self.count, index, -1): 452 self._array[(self._start + i) % self.capacity()] = self._array[(self._start + i - 1) % self.capacity()] 453 self._array[(self._start + index) % self.capacity()] = element 454 self.count += 1 455 456 457 def delete(self, index: int): 458 """ 459 Delete an element at a specified index, shifting subsequent elements to the left. 460 461 Args: 462 index (int): The index of the element to delete. 463 464 Raises: 465 IndexError: If the index is out of bounds. 466 """ 467 if index < 0 or index >= self.count: 468 raise IndexError 469 # Shift elements to the left 470 for i in range(index, self.count - 1): 471 self._array[(self._start + i) % self.capacity()] = self._array[(self._start + i + 1) % self.capacity()] 472 self.count -= 1
A circular array implementation.
Special Methods:
Index Operator:
array[index]
Assignment:
array[index] = value
CircularArray(contents=None, capacity: int = 10)
347 def __init__(self, contents=None, capacity: int=10): 348 """ 349 Initialize the circular array with optional contents and a fixed capacity. 350 351 Args: 352 contents: An optional iterable to fill array with default values. 353 capacity (int): The initial size of the array (default is 10) 354 """ 355 super().__init__(None, capacity) 356 #: index of the first element in the circular array 357 self._start = 0 358 if contents: 359 self.extend(contents)
Initialize the circular array with optional contents and a fixed capacity.
Args: contents: An optional iterable to fill array with default values. capacity (int): The initial size of the array (default is 10)
def
append(self, element):
393 def append(self, element): 394 """ 395 Append an element to the circular array. If appending exceeds capacity, it will wrap around to the oldest element. 396 397 Args: 398 element: The element to append. 399 """ 400 # self._array[(self._start + self.count) % len(self._array)] = element 401 # if self.count < self.capacity(): 402 # self.count += 1 403 # else: 404 # self._start = (self._start + 1) % len(self._array) 405 index = (self._start + self.count) % len(self._array) 406 self._array[index] = element 407 408 if self.count < self.capacity(): 409 self.count += 1 410 else: 411 self._start = (self._start + 1) % len(self._array) # Overwrite oldest element
Append an element to the circular array. If appending exceeds capacity, it will wrap around to the oldest element.
Args: element: The element to append.
def
raw_view(self):
413 def raw_view(self): 414 """ 415 Return a raw view of the array. 416 417 Returns: 418 A raw view of the array. 419 """ 420 return self._array
Return a raw view of the array.
Returns: A raw view of the array.
def
to_list(self):
422 def to_list(self): 423 """ 424 Convert the array's elements to a standard Python list. 425 426 Returns: 427 A list containing the elements of the array. 428 """ 429 output_list = [] 430 for i in range(self.count): 431 output_list.append(self._array[(self._start + i) % len(self._array)]) 432 return output_list
Convert the array's elements to a standard Python list.
Returns: A list containing the elements of the array.
def
insert(self, index: int, element):
434 def insert(self, index: int, element): 435 """ 436 Insert an element at a specified index, shifting existing elements to the right. 437 438 Args: 439 index (int): The index at which to insert the element. 440 element: The element to insert. 441 442 Raises: 443 IndexError: If the index is out of bounds. 444 Exception: If the array is full. 445 """ 446 if index < 0 or index > self.count: 447 raise IndexError 448 if self.count >= self.capacity(): 449 raise Exception(f"Capacity Error: Maximum capacity {self.capacity()} reached.") 450 # Shift elements to the right 451 for i in range(self.count, index, -1): 452 self._array[(self._start + i) % self.capacity()] = self._array[(self._start + i - 1) % self.capacity()] 453 self._array[(self._start + index) % self.capacity()] = element 454 self.count += 1
Insert an element at a specified index, shifting existing elements to the right.
Args: index (int): The index at which to insert the element. element: The element to insert.
Raises: IndexError: If the index is out of bounds. Exception: If the array is full.
def
delete(self, index: int):
457 def delete(self, index: int): 458 """ 459 Delete an element at a specified index, shifting subsequent elements to the left. 460 461 Args: 462 index (int): The index of the element to delete. 463 464 Raises: 465 IndexError: If the index is out of bounds. 466 """ 467 if index < 0 or index >= self.count: 468 raise IndexError 469 # Shift elements to the left 470 for i in range(index, self.count - 1): 471 self._array[(self._start + i) % self.capacity()] = self._array[(self._start + i + 1) % self.capacity()] 472 self.count -= 1
Delete an element at a specified index, shifting subsequent elements to the left.
Args: index (int): The index of the element to delete.
Raises: IndexError: If the index is out of bounds.