3: Ordered Arrays

Example 1: Page 56

In [1]:
def find(searchKey):
	lowerBound = 0
	upperBound = nElems - 1

	while(True):
		curIn = (lowerBound + upperBound) / 2
		if v[curIn] == searchKey:
			return curIn	#found it
		elif lowerBound > upperBound:
			return nElems	#can't find it
		else:	#divide range
			if v[curIn] < searchKey:
				lowerBound = curIn + 1	#it's in upper half
			else:
				upperBound = curIn - 1	#it's in lower half
		#end else divide range
	#end while
#end find()

Example 2: Page 58

In [2]:
#demonstrates ordered array class
class OrdArray:
	def __init__(self):	#special method to create objects
	#with instances customized to a specific initial state

		#since private instance variables don't exist in Python,
		#hence using a convention: name prefixed with an underscore, to treat them as non-public part
		self._v = []	#list _v

	def getSize(self):	#return number of elements
		return len(self._v)

	def find(self, searchKey):
		nElems = len(self._v)
		lowerBound = 0
		upperBound = nElems - 1

		while(True):
			curIn = (lowerBound + upperBound) / 2
			if self._v[curIn] == searchKey:
				return curIn	#found it
			elif lowerBound > upperBound:
				return nElems	#can't find it
			else:	#divide range
				if self._v[curIn] < searchKey:
					lowerBound = curIn + 1	#it's in upper half
				else:
					upperBound = curIn - 1	#it's in lower half
			#end else divide range
		#end while
	#end find()

	def insert(self, value):	#put element into array
		j = 0
		for j, val in enumerate(self._v):
			if val > value:
				break
		else:
			j += 1

		self._v.insert(j, value)	#inserting it

	def remove(self, value):	#remove element from array
		try:
			self._v.remove(value)
			return True	#found it
		except ValueError:	#can't find it
			return False

	def display(self):	#display array contents
		print self._v	#display it
#end class OrdArray

arr = OrdArray()	#create the array

arr.insert(77)	#insert 10 items
arr.insert(99)
arr.insert(44)
arr.insert(55)
arr.insert(22)
arr.insert(88)
arr.insert(11)
arr.insert(0)
arr.insert(66)
arr.insert(33)

searchKey = 55	#search for item
if arr.find(searchKey) != arr.getSize():
	print 'Found', searchKey
else:
	print "Can't Find", searchKey

arr.display()	#dislay items

print 'Deleting 0, 55, and 99'
arr.remove(0)	#delete 3 items
arr.remove(55)
arr.remove(99)

arr.display()	#display items again
#end
Found 55
[0, 11, 22, 33, 44, 55, 66, 77, 88, 99]
Deleting 0, 55, and 99
[11, 22, 33, 44, 66, 77, 88]

Example 3: Page 64

In [3]:
class person:
	"""A simple person class"""
	def __init__(self, last, first, a):	#special method to create objects
	#with instances customized to a specific initial state
		
		#since private instance variables don't exist in Python,
		#hence using a convention: name prefixed with an underscore, to treat them as non-public part
		self._lastName = last
		self._firstName = first
		self._age = a

	def displayPerson(self):
		print '	Last name:', self._lastName
		print ', First name:', self._firstName
		print ', Age:', self._age

	def getLast(self):
		return self._lastName	#get last name
#end class Person

Example 4: Page 65

In [1]:
#data items as class objects
class Person:
	"""A simple person class"""
	def __init__(self, last, first, a):	#special method to create objects
	#with instances customized to a specific initial state
		
		#since private instance variables don't exist in Python,
		#hence using a convention: name prefixed with an underscore, to treat them as non-public part
		self._lastName = last
		self._firstName = first
		self._age = a

	def displayPerson(self):
		print '	Last name:', self._lastName, ', First name:', self._firstName, ', Age:', self._age

	def getLast(self):
		return self._lastName	#get last name
#end class Person

class ClassDataArray:
	#since private instance variables don't exist in Python,
	#hence using a convention: name prefixed with an underscore, to treat them as non-public part
	def __init__(self):
		self._v = []	#list to store Person type items

	def __del__(self):	#destructor
		del self._v[:]	#delete each element

	def find(self, searchName):	#find specified value
		for j, val in enumerate(self._v):	#for each element
			if val._lastName == searchName:	#found item?
				break	#exit loop before end
		else:
			j += 1

		if j == len(self._v):	#gone to end?
			return None	#yes, can't find it
		else:
			return self._v[j]	#no, found it
	#end find

	def insert(self, last, first, age):	#put person into the array
		self._v.append(Person(last, first, age))

	def remove(self, searchName):	#delete person from array
		for j, val in enumerate(self._v):	#look for it
			if val._lastName == searchName:
				break
		else:
			j += 1

		if j == len(self._v):	#can't find it
			return False
		else:	#found it
			del self._v[j]	#delete Person object
			return True

	def displayA(self):	#displays array contents
		for j in self._v:	#for each element,
			j.displayPerson()	#display it
#end class ClassDataArray

arr = ClassDataArray()	#array

arr.insert('Evans', 'Patty', 24)	#insert 10 items
arr.insert('Smith', 'Lorraine', 37)
arr.insert('Yee', 'Tom', 43)
arr.insert('Adams', 'Henry', 63)
arr.insert('Hashimoto', 'Sato', 21)
arr.insert('Stimson', 'Henry', 29)
arr.insert('Velasquez', 'Jose', 72)
arr.insert('Lamarque', 'Henry', 54)
arr.insert('Vang', 'Minh', 22)
arr.insert('Creswell', 'Lucinda', 18)

arr.displayA()	#display items

searchKey = 'Stimson'	#search for item
print 'Searching for Stimson'
found = arr.find(searchKey)

if found != None:
	print '	Found',
	found.displayPerson()
else:
	print "	Can't find", searchKey

print 'Deleting Smith, Yee, and Creswell'
arr.remove('Smith')	#delete 3 items
arr.remove('Yee')
arr.remove('Creswell')

arr.displayA()	#display items again
#end
	Last name: Evans , First name: Patty , Age: 24
	Last name: Smith , First name: Lorraine , Age: 37
	Last name: Yee , First name: Tom , Age: 43
	Last name: Adams , First name: Henry , Age: 63
	Last name: Hashimoto , First name: Sato , Age: 21
	Last name: Stimson , First name: Henry , Age: 29
	Last name: Velasquez , First name: Jose , Age: 72
	Last name: Lamarque , First name: Henry , Age: 54
	Last name: Vang , First name: Minh , Age: 22
	Last name: Creswell , First name: Lucinda , Age: 18
Searching for Stimson
	Found 	Last name: Stimson , First name: Henry , Age: 29
Deleting Smith, Yee, and Creswell
	Last name: Evans , First name: Patty , Age: 24
	Last name: Adams , First name: Henry , Age: 63
	Last name: Hashimoto , First name: Sato , Age: 21
	Last name: Stimson , First name: Henry , Age: 29
	Last name: Velasquez , First name: Jose , Age: 72
	Last name: Lamarque , First name: Henry , Age: 54
	Last name: Vang , First name: Minh , Age: 22