[al_arrays_ap_impl_dynamic_array] #algo #arrays #aproblem #size
Create our own Dynamic Array class!
use a built in library ctypes
NB. A quick note on public vs private methods, we can use an underscore _ before the method name to keep it non-public.
import ctypes
#planning
# dynarray class must implement
# append element,
# index element
# resize array
# length of elements
class DynamicArray(object):
'''
DYNAMIC ARRAY CLASS (Similar to Python List)
'''
def __init__(self):
self.n = 0 # Count actual elements (Default is 0)
self.capacity = 1 # Default Capacity
self.A = self._make_array(self.capacity)
def __len__(self):
"""
Return number of elements sorted in array
"""
return self.n
def __getitem__(self,k):
"""
Return element at index k
"""
if not 0 <= k <self.n:
return IndexError('K is out of bounds!') # Check it k index is in bounds of array
return self.A[k] #Retrieve from array at index k
def append(self, ele):
"""
Add element to end of the array
"""
if self.n == self.capacity:
self._resize(2*self.capacity) #Double capacity if not enough room
self.A[self.n] = ele #Set self.n index to element
self.n += 1
def _resize(self,new_cap):
"""
Resize internal array to capacity new_cap
"""
print('called _resize() curr capacity:{} new capacity:{}'
.format(self.capacity,new_cap))
B = self._make_array(new_cap) # New bigger array
for k in range(self.n): # Reference all existing values
B[k] = self.A[k]
self.A = B # Call A the new bigger array
self.capacity = new_cap # Reset the capacity
def _make_array(self,new_cap):
"""
Returns a new array with new_cap capacity
"""
return (new_cap * ctypes.py_object)()
#testing
ar=DynamicArray()
ar.append(10)
ar.append(11)
ar.append(12)
ar[0]
len(ar) #3