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.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
6 Comments »

6 Responses to “Growable Arrays”

  1. Programming Praxis – Growable Arrays « Bonsai Code said
    October 16, 2009 at 12:42 PM

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

  2. Remco Niemeijer said
    October 16, 2009 at 12:43 PM

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

    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
  5. Joe Doliner said
    October 17, 2009 at 12:09 AM

    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)
  6. Skrud said
    October 27, 2009 at 7:08 PM

    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

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

%d bloggers like this: