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

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 comment