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.

About these ads

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

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

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: