$ python study.py 
Unsorted:[
  {'last': 'Chiappetta', 'user': 'johnny', 'key': 'abcxyz', 'first': 'Jonathan'}
  {'last': 'Dada', 'user': 'zdada', 'key': 'iowa', 'first': 'Zain'}
  {'last': 'Xray', 'user': 'yx', 'key': 'xy', 'first': 'Yvan'}
  {'last': 'Bob', 'user': 'abob', 'key': 'zyxcba', 'first': 'Alex'}
  {'last': 'Bob', 'user': 'bchar', 'key': 'hmmm', 'first': 'Charlie'}
]
Sorted:[
  {'last': 'Bob', 'user': 'abob', 'key': 'zyxcba', 'first': 'Alex'}
  {'last': 'Bob', 'user': 'bchar', 'key': 'hmmm', 'first': 'Charlie'}
  {'last': 'Chiappetta', 'user': 'johnny', 'key': 'abcxyz', 'first': 'Jonathan'}
  {'last': 'Xray', 'user': 'yx', 'key': 'xy', 'first': 'Yvan'}
  {'last': 'Dada', 'user': 'zdada', 'key': 'iowa', 'first': 'Zain'}
]
('Search=Dave:', None)
('Search=Jon:', {'last': 'Chiappetta', 'user': 'johnny', 'key': 'abcxyz', 'first': 'Jonathan'})
('Search=J Chi:', {'last': 'Chiappetta', 'user': 'johnny', 'key': 'abcxyz', 'first': 'Jonathan'})
('Search=J Chip:', None)

class contact:
	def __init__(self, firstName, lastName, username, pubKey):
		self.data = {"first":firstName, "last":lastName, "user":username, "key":pubKey}
		self.next = None
	
	def getData(self):
		return self.data
	
	def setData(self, dataContact):
		self.data = dataContact
	
	def getNext(self):
		return self.next
	
	def setNext(self, nextContact):
		self.next = nextContact

class contactList:
	def __init__(self):
		self.head = None
	
	def append(self, contact):
		if (self.head == None):
			self.head = contact
		else:
			temp = self.head
			while (temp.getNext() != None):
				temp = temp.getNext()
			temp.setNext(contact)
	
	def get(self):
		contacts = ""
		temp = self.head
		while (temp != None):
			contacts += ("  " + str(temp.getData()) + "\n")
			temp = temp.getNext()
		return ("[\n" + contacts + "]")
	
	def leng(self):
		indx = 0
		temp = self.head
		while (temp != None):
			indx += 1
			temp = temp.getNext()
		return indx
	
	def getin(self, gind):
		indx = 0
		temp = self.head
		while (temp != None):
			if (indx == gind):
				return temp
			temp = temp.getNext()
			indx += 1
		return None
	
	def swap(self, a, b):
		ac = self.getin(a)
		bc = self.getin(b)
		temp = ac.getData()
		ac.setData(bc.getData())
		bc.setData(temp)
	
	def sort(self, beg=-1, end=-1):
		if (beg < 0):
			beg = 0
		if (end < 0):
			end = self.leng()
		if ((end - beg) < 2):
			return 0
		# todo: use head && next instead of index lookup
		pivot = beg
		p = self.getin(pivot)
		z = p.getData()
		indx = (pivot + 1)
		hi = -1
		while (indx < end):
			a = self.getin(indx)
			b = a.getData()
			if ((b["first"] + b["last"]) < (z["first"] + z["last"])):
				if (hi > -1):
					self.swap(hi, indx)
					hi += 1
			else:
				if (hi < 0):
					hi = indx
			indx += 1
		if (hi < 0):
			hi = (end - 1)
		elif (hi > 0):
			hi = (hi - 1)
		self.swap(pivot, hi)
		self.sort(beg, hi)
		self.sort(hi + 1, end)
	
	def search(self, fullname, beg=-1, end=-1):
		if (beg < 0):
			beg = 0
		if (end < 0):
			end = self.leng()
		if ((end - beg) < 1):
			return None
		fulllist = fullname.split(" ")
		fulllist.append("")
		first = fulllist[0]; flen = len(first)
		last = fulllist[1]; llen = len(last)
		mid = (((end - beg) / 2) + beg)
		mc = self.getin(mid)
		md = mc.getData()
		fname = md["first"][:flen]
		lname = md["last"][:llen]
		if ((fname == first) and (lname == last)):
			return mc
		if ((fname > first) or (lname > last)):
			end = (mid - 1)
			mid = -1
		elif ((fname < first) or (lname < last)):
			beg = (mid + 1)
			mid = -1
		if (mid != -1):
			return None
		return self.search(fullname, beg=beg, end=end)

def main():
	contactBook = contactList()
	
	newContact = contact("Jonathan", "Chiappetta", "johnny", "abcxyz")
	contactBook.append(newContact)
	
	newContact = contact("Zain", "Dada", "zdada", "iowa")
	contactBook.append(newContact)
	
	newContact = contact("Yvan", "Xray", "yx", "xy")
	contactBook.append(newContact)
	
	newContact = contact("Alex", "Bob", "abob", "zyxcba")
	contactBook.append(newContact)
	
	newContact = contact("Charlie", "Bob", "bchar", "hmmm")
	contactBook.append(newContact)
	
	print("Unsorted:" + contactBook.get())
	
	contactBook.sort()
	print("Sorted:" + contactBook.get())
	
	print("Search=Dave:", contactBook.search("Charlie"))
	print("Search=Jon:", contactBook.search("Jon").getData())
	print("Search=J Chi:", contactBook.search("J Chi").getData())
	print("Search=J Chip:", contactBook.search("J Chip"))

if (__name__ == "__main__"):
	main()