## Growable Arrays

### October 16, 2009

We represent an element of a growable array as a list of length three with the element in its `car`, the left child in its `cadr`, and the right child in its `caddr`; the nil array is represented as the null list. `Get` is simple:

```(define (get arr sub)   (cond ((null? arr) (error 'get "array out of bounds"))         ((= sub 1) (car arr))         ((even? sub) (get (cadr arr) (quotient sub 2)))         (else (get (caddr arr) (quotient sub 2)))))```

`Put` isn’t much harder. The `null?` clause signals an error only if the current subscript is greater than one; otherwise, it extends the array by adding a new element with nil children. The two recursive clauses build the return array as they go:

```(define (put arr sub val)   (cond ((null? arr)           (if (= sub 1)               (list val '() '())               (error 'put "array out of bounds")))         ((= sub 1)           (list val '() '()))         ((even? sub)           (list (car arr)                 (put (cadr arr) (quotient sub 2) val)                 (caddr arr)))         (else (list (car arr) (cadr arr)                     (put (caddr arr) (quotient sub 2) val)))))```

`Hirem` replaces the sub‘th element of the array with a leaf represented by nil, raising an error if that element doesn’t exist. However, it does not check that sub is the upper bound of the array:

```(define (hirem arr sub)   (cond ((null? arr) (error 'hirem "array out of bounds"))         ((= sub 1) '())         ((even? sub)           (list (car arr)                 (hirem (cadr arr) (quotient sub 2))                 (caddr arr)))         (else (list (car arr) (cadr arr)                     (hirem (caddr arr) (quotient sub 2))))))```

In practice, it is normal to pair the tree with a count of the elements in the array; you’ll probably want to write a set of functions or macros to wrap the tree-manipulation functions given above:

```> (define x (list 0)) > (set! x (cons (+ (car x) 1) (put (cdr x) 1 "alfa"))) > (set! x (cons (+ (car x) 1) (put (cdr x) 2 "bravo"))) > (set! x (cons (+ (car x) 1) (put (cdr x) 3 "charlie"))) > (set! x (cons (+ (car x) 1) (put (cdr x) 4 "delta"))) > (set! x (cons (+ (car x) 1) (put (cdr x) 5 "echo"))) > (set! x (cons (+ (car x) 1) (put (cdr x) 6 "foxtrot"))) > (set! x (cons (+ (car x) 1) (put (cdr x) 7 "golf"))) > (get (cdr x) 7) "golf" > (get (cdr x) 12) Error in get: array out of bounds > (set! x (cons (- (car x) 1) (hirem (cdr x) (car x)))) > (get (cdr x) 7) Error in get: array out of bounds```

You can run the code at http://programmingpraxis.codepad.org/gFUCaHuY.

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
```