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

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 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. 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'
    				return self.key
    		elif (index%2 == 0):
    			if (self.left):
    				return self.left.get(index >> 1)
    				print 'index out of bounds'
    			if (self.right):
    				return self.right.get(index >> 1)
    				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)
    			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)
    			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
    				self.right = None
    		elif index % 2 == 0:
    			self.left.hirem(index / 2)
    			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
    	def print_items(self):
    		for node in self.root.traverse():
    			print node.item
    	def hirem(self):
    		if self.root:
    			self.cur -= 1

Leave a Reply

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

You are commenting using your 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


Get every new post delivered to your Inbox.

Join 678 other followers

%d bloggers like this: