## Growable Arrays

### October 16, 2009

Most programming languages provide a data structure called an array that provides constant-time access and update to its elements, at the cost of fixing the size of the array in advance of its use; Scheme calls that data structure a vector. In their book The Practice of Programming, Brian Kernighan and Rob Pike describe arrays that can grow during use, using the C language and its `realloc` function to double the size of an array when needed. In this exercise we will create a tree-based data structure that provides logarithmic-time access and update to its elements without requiring periodic reallocations, based on the functional arrays in Lawrence Paulson’s book ML for the Working Programmer.

A growable array has subscripts from 1 to n, where n is the current number of elements in the array. The elements are stored in a binary tree. To find the k‘th element of the array, start at the root and repeatedly divide k by two until it becomes one, moving left if the remainder is zero and right if the remainder is one. For instance, the 12th element of the array is found by moving left, left and right from the root, as shown in the diagram at right. The operations on a growable array are `get`, which retrieves an element of the array, `put`, which returns a new array containing the element, and `hirem`, which shrinks the array by a single element. The `put` operation can increase the upper bound of the array by one.

Your task is to implement the growable array data structure. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Pages: 1 2

### 6 Responses to “Growable Arrays”

1. [...] today’s Programming Praxis we’re going to implement a growable array, which is a data structure with [...]

2. Remco Niemeijer said

```data Grow a = Empty | Grow { val :: a, l :: Grow a, r:: Grow a }

walk :: (Int -> Grow a -> b) -> Int -> Grow a -> b
walk f i = f (div i 2) . if even i then l else r

modify :: Grow a -> (Int -> Grow a -> Grow a) -> Int -> Grow a -> Grow a
modify d _ _ Empty         = d
modify _ f i g | even i    = g { l = walk f i g }
| otherwise = g { r = walk f i g }

get :: Int -> Grow a -> Maybe a
get _ Empty = Nothing
get 1 g     = Just \$ val g
get i g     = walk get i g

put :: Int -> a -> Grow a -> Grow a
put 1 x Empty = Grow x Empty Empty
put 1 x g     = g { val = x }
put i x g     = modify (error "array out of bounds") (`put` x) i g

hirem :: Int -> Grow a -> Grow a
hirem 1 = const Empty
hirem i = modify Empty hirem i
```
3. A python solution. joedoliner.com for comments and test code.

```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)
```
4. Skrud said

Here’s another python solution. This one uses a wrapper class around the root node which keeps track of the current upper bound and uses that for put() and hirem(). I’m sure hirem() could be cleaner, though. :-S

```class GrowableArrayNode:
def __init__(self, item=None):
self.item = item
self.left = None
self.right = None

def put(self, item, index):
if index == 1:
self.item = item
elif index % 2 == 0:
if not self.left:
self.left = GrowableArrayNode()
self.left.put(item, index/2)
else:
if not self.right:
self.right = GrowableArrayNode()
self.right.put(item, index/2)

def get(self, index):
if index == 1:
return self.item

if index % 2 == 0:
return self.left.get(index / 2)
else: return self.right.get(index / 2)

def traverse(self):
if self.left:
for x in self.left.traverse():
yield x
yield self
if self.right:
for x in self.right.traverse():
yield x

def hirem(self,index):
if index / 2 == 1:
if index % 2 == 0:
self.left = None
else:
self.right = None
elif index % 2 == 0:
self.left.hirem(index / 2)
else:
self.right.hirem(index / 2)

class GrowableArray:
def __init__(self):
self.root = None

def get(self,index):
if self.root == None:
return None

return self.root.get(index)

def put(self,item):
if self.root == None:
self.root = GrowableArrayNode()
self.cur = 0
self.cur += 1
self.root.put(item,self.cur)

def print_items(self):
for node in self.root.traverse():
print node.item

def hirem(self):
if self.root:
self.root.hirem(self.cur)
self.cur -= 1
```