#!/usr/bin/env python

from random import shuffle, randrange, seed

PAGE_WIDTH = 8.5 * 72
PAGE_HEIGHT = 11.0 * 72
PAGE_MARGIN = 1.0 * 72
FACE = "Helvetica"
TITLE_OFFSET = 2.0 * 72
TITLE_SIZE = 32.0
DIAGRAM_WIDTH = PAGE_WIDTH - 2.0 * PAGE_MARGIN
DIAGRAM_HEIGHT = PAGE_HEIGHT - TITLE_OFFSET - 2.0 * PAGE_MARGIN

EPS = True
EPS_HEIGHT = 5.0 * 72

LIST_LENGTH = 64

class sort:
	def __init__(self):
		self.reset()

	def reset(self):
		self.record = []

	def make_record(self, list):
		self.record.append(list[:])

def is_sorted(list):
	for i in range(0, len(list) - 1):
		if list[i] > list[i + 1]:
			return False
	return True

class bogosort(sort):
	name = "Bogosort"
	filename = "bogosort"

	def sort(self, list):
		self.make_record(list)
		while not is_sorted(list):
			shuffle(list)
			self.make_record(list)

class bm_sort(sort):
	name = "British Museum sort"
	filename = "bm-sort"

	def sort(self, list):
		self.make_record(list)
		while not is_sorted(list):
			a = randrange(0, len(list))
			b = randrange(0, len(list))
			(list[a], list[b]) = (list[b], list[a])
			self.make_record(list)

class mbm_sort(sort):
	name = "Modified British Museum sort"
	filename = "mbm-sort"

	def sort(self, list):
		self.make_record(list)
		while not is_sorted(list):
			while True:
				a = randrange(0, len(list))
				b = randrange(0, len(list))
				if (a < b and list[a] > list[b]) or (a > b and list[a] < list[b]):
					break
			(list[a], list[b]) = (list[b], list[a])
			self.make_record(list)

class stupid_sort(sort):
	name = "Stupid sort"
	filename = "stupid-sort"

	def sort(self, list):
		self.make_record(list)
		while True:
			for i in range(0, len(list) - 1):
				if list[i] > list[i + 1]:
					(list[i], list[i + 1]) = (list[i + 1], list[i])
					break
			else:
				break
			self.make_record(list)

class bubble_sort(sort):
	name = "Bubble sort"
	filename = "bubble-sort"

	def sort(self, list):
		self.make_record(list)
		i = len(list) - 1
		while i > 0:
			last = 0
			for j in range(0, i):
				if list[j] > list[j + 1]:
					(list[j], list[j + 1]) = (list[j + 1], list[j])
					last = j
			i = last
			self.make_record(list)

class cocktail_sort(sort):
	name = "Bidirectional bubble sort"
	filename = "cocktail-sort"

	def sort(self, list):
		self.make_record(list)
		left = 0
		right = len(list) - 1
		while True:
			if left >= right:
				break
			last = left
			for j in range(left, right):
				if list[j] > list[j + 1]:
					(list[j], list[j + 1]) = (list[j + 1], list[j])
					last = j
			right = last
			self.make_record(list)
			if left >= right:
				break
			last = right
			for j in range(right, left, -1):
				if list[j] < list[j - 1]:
					(list[j], list[j - 1]) = (list[j - 1], list[j])
					last = j
			left = last
			self.make_record(list)

class insertion_sort(sort):
	name = "Insertion sort"
	filename = "insertion-sort"

	def sort(self, list):
		self.make_record(list)
		for i in range(1, len(list)):
			val = list[i]
			j = i
			while j > 0 and list[j - 1] > val:
				list[j] = list[j - 1]
				j -= 1
			list[j] = val
			self.make_record(list)

class shell_sort(sort):
	name = "Shell sort"
	filename = "shell-sort"
	shell_steps = [ 63, 31, 15, 7, 3, 1 ]

	def sort(self, list):
		self.make_record(list)
		for step in self.shell_steps:
			for i in range(step, len(list)):
				val = list[i]
				j = i
				while j >= step and list[j - step] > val:
					list[j] = list[j - step]
					j -= step
				list[j] = val
				if i % step == 0:
					self.make_record(list)

class selection_sort(sort):
	name = "Selection sort"
	filename = "selection-sort"

	def sort(self, list):
		self.make_record(list)
		for i in range(0, len(list) - 1):
			min = i
			for j in range(i + 1, len(list)):
				if list[j] < list[min]:
					min = j
			(list[i], list[min]) = (list[min], list[i])
			self.make_record(list)

class quicksort(sort):
	name = "Quicksort"
	filename = "quicksort"

	def sort(self, list, low = 0, high = None):
		if high is None:
			high = len(list)
			self.make_record(list)
		if high - low <= 1:
			return
		# pivot = randrange(low, high)
		# (list[low], list[pivot]) = (list[pivot], list[low])
		i = low + 1
		for j in range(i, high):
			if list[j] < list[low]:
				(list[i], list[j]) = (list[j], list[i])
				i += 1
		(list[low], list[i - 1]) = (list[i - 1], list[low])
		self.make_record(list)
		self.sort(list, low, i - 1)
		self.sort(list, i, high)

class merge_sort(sort):
	name = "Merge sort"
	filename = "merge-sort"

	def merge(self, a, b):
		if len(a) == 0:
			return b
		elif len(b) == 0:
			return a
		elif a[0] < b[0]:
			return a[0:1] + self.merge(a[1:], b)
		else:
			return b[0:1] + self.merge(a, b[1:])

	def sort(self, list, low = 0, high = None):
		if high is None:
			high = len(list)
			self.make_record(list)
		if high - low <= 1:
			return list
		mid = (high - low) // 2 + low
		list[low:high] = self.merge(self.sort(list, low, mid)[low:mid],
			self.sort(list, mid, high)[mid:high])
		self.make_record(list)
		return list

class heapsort(sort):
	name = "Heapsort"
	filename = "heapsort"

	def sift(self, list, val, left, right):
		i = left
		while True:
			j = i * 2 + 1
			if j < right - 1 and list[j] < list[j + 1]:
				j = j + 1
			if j < right and val < list[j]:
				list[i] = list[j]
				i = j
			else:
				break
		list[i] = val

	def sort(self, list):
		self.make_record(list)

		left = len(list) // 2
		right = len(list)
	
		while left > 0:
			left -= 1
			self.sift(list, list[left], left, right)
			self.make_record(list)
	
		while right > 0:
			right -= 1
			val = list[right]
			list[right] = list[0]
			self.sift(list, val, left, right)
			self.make_record(list)

def document_start(file):
	global num_pages

	num_pages = 0
	file.write(
"""%!PS-Adobe-3.0
%%BoundingBox: 0 0 """ + ("%u %u" % (PAGE_WIDTH, PAGE_WIDTH)) + """
%%HiResBoundingBox: 0 0 """ + ("%.3g %.3g" % (PAGE_WIDTH, PAGE_WIDTH)) + """
%%Pages: (atend)
%%EndComments

/color { /p exch """ + ("%.3g" % (LIST_LENGTH - 1)) + """ div def
	p 1 3 div lt { p 3 mul } { 1.0 } ifelse p mul 0.9 mul 0.1 add
	p 2 3 div lt { 0.0 } { p 3 mul 2 sub } ifelse p mul 0.9 mul 0.1 add
	p 1 3 div lt { 1.0 } { p 2 3 div lt { 1 p sub 3 mul 1 sub } { 0.0 } ifelse } ifelse p mul 0.9 mul 0.1 add
	setcolor
} def
/drawsquare { /size exch def
	newpath 0 0 moveto size 0 rlineto 0 size rlineto size neg 0 rlineto closepath
	fill
} def
""")

def document_end(file):
	global num_pages

	file.write(
"""
%%Trailer
%%Pages: """ + ("%u" % num_pages) + """
%%EOF
""")

def page_output(file, sort):
	global num_pages

	num_pages += 1
	file.write(
"""
%%Page: """ + ("%u %u" % (num_pages, num_pages)) + """

/DeviceRGB setcolorspace

""")
	file.write("%.3g %.3g moveto\n" % (PAGE_MARGIN, PAGE_HEIGHT - TITLE_OFFSET))
	file.write("/%s findfont %.3g scalefont setfont (%s) show\n" % (FACE, TITLE_SIZE, sort.name))
	file.write("\n")

	squaresize = min(DIAGRAM_WIDTH / len(sort.record),
		DIAGRAM_HEIGHT / LIST_LENGTH)
	file.write("gsave\n")
	file.write("%.3g %.3g translate\n"
		% (PAGE_MARGIN + (DIAGRAM_WIDTH - squaresize * len(sort.record)) / 2,
			PAGE_MARGIN + (DIAGRAM_HEIGHT - squaresize * LIST_LENGTH) / 2))
	for i in range(0, len(sort.record)):
		file.write("gsave\n")
		file.write("/a [")
		for j in range(0, len(sort.record[i])):
			file.write(" %u" % sort.record[i][j])
		file.write(" ] def\n")
		file.write(
"""0 1 a length 1 sub {
	a exch get color %.3g drawsquare
	0 %.3g translate
} for
""" % (squaresize, squaresize))
		file.write("grestore\n")
		file.write("%.3g 0 translate\n" % squaresize)
	file.write("grestore\n")
	file.write("showpage\n")

def eps_output(file, sort):
	width = float(len(sort.record)) / LIST_LENGTH * EPS_HEIGHT
	file.write(
"""%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 0 0 """ + ("%u %u" % (width, EPS_HEIGHT)) + """
%%HiResBoundingBox: 0 0 """ + ("%.3g %.3g" % (width, EPS_HEIGHT)) + """
%%Pages: (atend)
%%EndComments

/color { /p exch """ + ("%.3g" % (LIST_LENGTH - 1)) + """ div def
	p 1 3 div lt { p 3 mul } { 1.0 } ifelse p mul 0.9 mul 0.1 add
	p 2 3 div lt { 0.0 } { p 3 mul 2 sub } ifelse p mul 0.9 mul 0.1 add
	p 1 3 div lt { 1.0 } { p 2 3 div lt { 1 p sub 3 mul 1 sub } { 0.0 } ifelse } ifelse p mul 0.9 mul 0.1 add
	setcolor
} def
/drawsquare { /size exch def
	newpath 0 0 moveto size 0 rlineto 0 size rlineto size neg 0 rlineto closepath
	fill
} def
""")

	file.write(
"""
/DeviceRGB setcolorspace
""")

	squaresize = min(width / len(sort.record),
		EPS_HEIGHT / LIST_LENGTH)
	file.write("gsave\n")
	for i in range(0, len(sort.record)):
		file.write("gsave\n")
		file.write("/a [")
		for j in range(0, len(sort.record[i])):
			file.write(" %u" % sort.record[i][j])
		file.write(" ] def\n")
		file.write(
"""0 1 a length 1 sub {
	a exch get color %.3g drawsquare
	0 %.3g translate
} for
""" % (squaresize, squaresize))
		file.write("grestore\n")
		file.write("%.3g 0 translate\n" % squaresize)
	file.write("grestore\n")
	file.write(
"""
%%Trailer
%%EOF
""")

def main():
	sorts = [
		# bogosort(),
		# bm_sort(),
		# mbm_sort(),
		# stupid_sort(),
		bubble_sort(),
		cocktail_sort(),
		insertion_sort(),
		shell_sort(),
		selection_sort(),
		quicksort(),
		merge_sort(),
		heapsort()
	]

	original = range(0, LIST_LENGTH)

	seed(6)
	shuffle(original)
	# original = original[::-1]

	if EPS:
		for sort in sorts:
			file = open(sort.filename + ".eps", "w")
			sort.sort(original[:])
			print sort.name, len(sort.record)
			eps_output(file, sort)
			file.close()
	else:
		file = open("sort-diagrams.ps", "w")
		document_start(file)
	
		for sort in sorts:
			sort.sort(original[:])
			print sort.name, len(sort.record)
			page_output(file, sort)
	
		document_end(file)
		file.close()

if __name__ == "__main__":
	main()