Exercise from: http://programmingpraxis.com/2009/10/16/growable-arrays/
Our goal here is to implement an array which is capable of dynamically growing as we add elements to it at the cost of logarithmic runtime for put and get functions instead of the constant runtime of standard arrays.
The indexing scheme seems a bit weird at first until we notice the pattern that the left subtree of 1 is all even and the right subtree is all odd. So given and index we simply consider its parity and choose the correct subtree. Then we apply this recursively to the subtree with the index halved (rounded down). Here it is implemented in python:
class exArray(): key = None left = None right = None def get(self, index): if (index == 0): print 'index out of bounds' elif (index == 1): if (self.key == None): print 'index out of bounds' else: return self.key elif (index%2 == 0): if (self.left): return self.left.get(index >> 1) else: print 'index out of bounds' else: if (self.right): return self.right.get(index >> 1) else: print 'index out of bounds' def put(self, index, key): if (index == 0): print 'index out of bounds' elif (index == 1): self.key = key elif (index%2 == 0): if (not self.left): self.left = exArray() self.left.put(index >> 1, key) else: if (not self.right): self.right = exArray() self.right.put(index >> 1, key)
Full code: exArray.py
import exArray exArray.test(array_size)