ImplementapopmethodfortheDynamicArrayclass,giveninCodeFrag- ment 5.3, that removes the last element of the array, and that shrinks the capacity, N, of the array by half any time the number of elements in the array goes below N/4.

import ctypes # provides low-level arrays class DynamicArray:

A dynamic array class akin to a simplified Python list.

def init (self): Create an empty array. self. n = 0 self. capacity = 1 self. A = self. make array(self. capacity)

# count actual elements # default array capacity # low-level array

def len (self): Return number of elements stored in the array. return self. n

def getitem (self, k): Return element at index k. ifnot0<=k

raise IndexError( invalid index ) return self. A[k]

def append(self, obj): Add object to end of the array. if self. n == self. capacity:

self. resize(2 self. capacity) self. A[self. n] = obj self. n += 1

def resize(self, c): Resize internal array to capacity c. B = self. make array(c) for k in range(self. n):

B[k] = self. A[k] self. A = B self. capacity = c

def make array(self, c): Return new array with capacity c. return (c ctypes.py object)( )

# retrieve from array

# not enough room # so double capacity

# nonpublic utitity

# new (bigger) array # for each existing value

# use the bigger array

# nonpublic utitity # see ctypes documentation

Code Fragment 5.3: An implementation of a DynamicArray class, using a raw array from the ctypes module as storage.