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

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

My Haskell solution (see http://bonsaicode.wordpress.com/2009/10/16/programming-praxis-growable-arrays/ for a version with comments):

[…] […]

[…] Exercise from: http://programmingpraxis.com/2009/10/16/growable-arrays/ […]

A python solution. joedoliner.com for comments and test code.

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