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