import math
import sys

from lxml import etree

def main():
	# NOTE: Developed with Python 3.4 and lxml 3.3.5

	# Validate the input
	if len(sys.argv) < 3:
		print('\nERROR: Not enough arguments provided!')
		print('\nUSAGE: key_classify.py <input file> <table size>\n')
		return -1

	# Attempt to open the input file
	try:
		input_xml = open(sys.argv[1], 'r')
	except IOError:
		print('\nERROR: unable to open file "{:s}"'.format(sys.argv[1]))
		return

	# Determine the table size; test if the supplied table size argument is a 
	# power of 2; if not then use the next smallest power of 2
	table_size = int(sys.argv[2])
	table_size_log2 = math.log(table_size, 2)
	compare_bits = math.floor(table_size_log2)
	table_size_check = 2**compare_bits
	if (table_size_check != table_size):
		print('WARNING: {:d} is not a power of 2, using {:d}, which is the '
			  'next smallest power of 2, instead\n'.format(table_size, 
			  											   table_size_check))
		table_size = table_size_check

	# Parse the input file into an ElementTree
	sys.stdout.write('Parsing input xml file...')
	sys.stdout.flush()
	tree = etree.parse(input_xml)
	input_xml.close()
	sys.stdout.write('DONE\n')

	# root = tree.getroot()



	# Calculate the number of characters (bytes) to slice off the front of each 
	# title
	compare_chars = math.ceil(compare_bits / 8.0)

	# Calculate the number of bits to right shift the sliced bytes so that only
	# "compare_bits" bits are left
	shift_bits = (compare_chars * 8) - compare_bits


	# Get all article title text using an XPath expression
	namespace_mapping = {'w': 'http://www.mediawiki.org/xml/export-0.8/'}
	article_titles = tree.xpath('(//w:page/w:title/text())', 
			   	   			  	namespaces=namespace_mapping)

	# Iterate over the titles and classify them
	counts = {}
	for idx, article_title in enumerate(article_titles):

		if article_title.startswith('Talk:'):
			continue

		# Conver the title to raw bytes, then slice based on the number of 
		# "compare_chars" and covert to an integer
		title_bytes = bytearray(article_title, 'utf-8')
		sliced_bytes_int = int.from_bytes(title_bytes[0:compare_chars], 
										  byteorder='big')

		# Calculate the histogram index by taking the integer of the comparison 
		# characters and right shifting it so that only "compare_bits" are used
		index = sliced_bytes_int >> shift_bits

		# Debug
		# print(idx, article_title, title_bytes[0:compare_chars], sliced_bytes_int, 
		# 	  '0x{:X}'.format(sliced_bytes_int), '0x{:X}'.format(index))

		# Classify, i.e. build the histogram
		if index in counts:
			counts[index] += 1
		else:
			counts[index] = 1

	# After building the histogram print out the results
	for index in sorted(counts.keys()):
		print(index, counts[index])


if __name__ == '__main__':
	sys.exit(main())