## page was renamed from Main/HSECompLing/m2012/Solution4
= Разбор задачи =

Я не удержусь, и добавлю несколько комментариев / нравоучений
по поводу этого примера...

== Про etree: ==

Мне помнится, что из вас почти никто так и не пытался использовать
etree, так что прошу вас посмотреть в мою версию, чтобы иметь какое-то
представление о том, как оно применяется в жизни. Сравните это с
вашими решениями на регулярных выражениях, устыдитесь и проникнетесь
тем, мимо какой полезной штуки вы прошли не глядя! (Я не акцентирую
ваше внимание на том, что etree сделан в согласии со стандартом XML, и
поэтому он никак не зависит от того, где автор какого-нибудь XML-ника
решил сделать перенос строки). Попробуйте хотя бы посчитать число
строк, которое заняло решение какой-то подзадачки у вас на регулярных
выражениях, и сколько строк потребовалось здесь!

Дабы проще было разбираться, попробуйте отследить путь переменных:

 * GUI.xml -- это разобранное в etree дерево всего файла;
 * GUI.xmls[sentence] -- это словарь, в котором ключ -- текст предложения, значения -- XML-дерево для одного предложения;
 * Tree.sentence -- это XML-дерево для одного пердложения.

== Про преобразование деревьев: ==

В ваших решениях я наблюдал несколько подходов к решению задачи: как
нам перевести деревья из представления, где у каждого узла известен
родитель (в котором они в syntagrus), к представлению, в котором у
каждого родителя известны дети (которое мы умеем рисовать).
Большинство подходов сводились, в конечном счёте, к следующему: мы
создаём родителя, а потом проходим по списку всех известных вершин
дерева, и если у кого-нибудь данный узел указывался в качестве
родителя, то добавляли его в качестве ребёнка. Собственно, мой подход
здесь ничем не отличается.

Это решение работает за квадратичное время от количества вершин, но
так как предложений даже с сотней слов уже почти не бывает (а 100^2 =
10000, что не очень много), то такое время работы вполне приемлемо.

Эту задачу можно решать и за линейное время, совсем просто.
Предположим, parents -- словарь, в котором по ключу узлу можно
получить значение родителя узла. Мы хотим сделать словарь children, в
котором по ключу родителю лежит список детей:

{{{#!python
children = {}
for node in parents:
    parent = parents[node]
    if parent not in children:
         children[parent] = []
    children[parent].append(node)
}}}

Доска почёта: Аня Выборнова и Егор Лакомкин изобрели такой же подход.

== Про рисование интерфейса: ==

В лице класса GUI и того, как он запускается, я демонстрирую здесь
довольно общепринятый сейчас подход к тому, как делать интерфейсы (что
графические, что вебовские -- впрочем, в flask оно выглядит проще). А
именно: мы заводим класс (здесь GUI), в котором есть один-несколько
методов для рисования (здесь это create_ui*), несколько методов,
которые обрабатывают события (здесь это open, search, redraw), и метод
run, запуск которого и есть запуск всей программы.

Про всякое рисование окошек я здесь показал почти все возможности,
которые есть в Tkinter, надеюсь, этот код не выглядит страшным.

== Про оформление кода: ==

Хорошим тоном считается:

 * чтобы перед каждым определемнием функции или класса оставлять по пустой строке (последование придерживание такой идеи для большинства из вас не характерно);
 * чтобы название переменной или функции было достаточно информативным и не требовало комментариев (здесь и ко мне есть нарекания; и здесь и у большинства из вас всё хорошо);
 * чтобы все константы были вынесены наверх и названы содержательным образом;
 * чтобы код функции всегда укладывался в десять строк (эта константа специфична для питона; для других языков тут правила другие); 
 * чтобы функция, которой предполагается пользоваться только другим функциям того же класса/модуля, начинались с подчёркивания; 
 * чтобы всё, что касается одной темы, было рядом, а всё, что касается разных тем, было далеко 
 * чтобы не было слишком длинных строк (длиннее 70-80 букв).

Ещё хорошим тоном считается иметь гораздо больше договорённостей с
собой о том, как делать мелочи (чтобы одинаковые вещи всегда делались
одинаково) и соблюдать их. Думаю, моё решение вполне можно
воспринимать и как пример применения этих идей к жизни. Не нужно
стремиться к тому, чтобы ваш код был похож на мой, но я очень
рекомендую, чтобы вы старались делать код столь же упорядоченным. Это
упрощает чтение кода -- и в первую очередь, вам же самим во время
отладки.

== Код программы ==

{{{#!python
# coding: utf-8
import Tkinter
import tkFileDialog
from xml.etree import ElementTree

class Tree(object):
	dx = 25
	dy = 25
	font = 'Arial'

	def __init__(self, canvas, sentence, id=None):
		if id is None:
			self.word = sentence.find('.//*[@DOM="_root"]')
			id = self.word.attrib['ID']
		else:
			self.word = sentence.find('.//*[@ID="{0}"]'.format(id))
		self.canvas = canvas
		self.sentence = sentence
		self.children = [Tree(canvas, sentence, word.attrib['ID'])
			for word in sentence.findall('.//*[@DOM="{0}"]'.format(id))]

	def draw(self):
		self._draw_node(self.dx, self.dy)
		self._row = [self]
		while self._row:
			self._draw_row()
			self._next_row()

	def _draw_row(self):
		max_x = self.dx
		for parent in self._row:
			for child in parent.children:
				child._draw_node(max_x, parent.y1 + self.dy)
				max_x = child.x1 + self.dx
				parent._draw_line(child)

	def _draw_node(self, x, y):
		self.canvas_id = self.canvas.create_text(
			(x, y),
			text=self.word.text,
			anchor='nw',
			justify='center',
			font=self.font,
		)
		self.x0, self.y0, self.x1, self.y1 = self.canvas.bbox(self.canvas_id)

	def _draw_line(self, child):
		x0, y0 = (self.x0 + self.x1) / 2, self.y1
		x1, y1 = (child.x0 + child.x1) / 2, child.y0
		self.canvas.create_line((x0,y0), (x1,y1), arrow='last')

	def _next_row(self):
		result = []
		for parent in self._row:
			for child in parent.children:
				result.append(child)
		self._row = result

class GUI(object):
	W, H = 500, 500

	def __init__(self):
		self.xmls = {}
		self.xml = ElementTree.fromstring("<xml/>")
		self.create_ui()

	def create_ui(self):
		self.root = Tkinter.Tk()
		self.create_ui_top()
		self.create_ui_middle()
		self.create_ui_bottom()

	def create_ui_top(self):
		top = Tkinter.Frame(self.root)
		self.query = query = Tkinter.Entry(top)
		search = Tkinter.Button(top, text="Search", command=self.search)
		openfile = Tkinter.Button(top, text="Open file", command=self.open)
		query.pack(side="left", fill="both", expand="yes")
		search.pack(side="left")
		openfile.pack(side="left")
		top.pack(side="top", fill="x")
		query.bind("<Return>", self.search)

	def create_ui_middle(self):
		middle = Tkinter.Frame(self.root)
		self.sentences = sentences = Tkinter.Listbox(middle)
		scroll = Tkinter.Scrollbar(middle, command=sentences.yview)
		sentences['yscrollcommand'] = scroll.set
		sentences.pack(side="left", fill="both", expand="yes")
		scroll.pack(side="left", fill="y")
		middle.pack(side="top", fill="both", expand="yes")
		sentences.bind("<<ListboxSelect>>", self.redraw)

	def create_ui_bottom(self):
		self.canvas = canvas = Tkinter.Canvas(self.root,
			width=self.W, height=self.H, background="white")
		canvas.pack(side="top", fill="both", expand="yes")

	def open(self):
		file = tkFileDialog.askopenfile()
		self.xml = ElementTree.parse(file).getroot()

	def search(self, ev=None):
		query = self.query.get()
		self.xmls = {}
		self.sentences.delete(0, "end")
		xml_sentences = self.xml.findall(u'.//*[@LEMMA="{0}"]/..'.format(query.upper()))
		for xml_sentence in xml_sentences:
			sentence = "".join(word.text + word.tail for word in xml_sentence)
			sentence = "".join(xml_sentence.itertext())
			sentence = sentence.replace("\n", "")
			self.xmls[sentence] = xml_sentence
			self.sentences.insert("end", sentence)
		if not xml_sentences:
			self.sentences.insert("end", "nothing found")

	def redraw(self, event):
		self.canvas.delete("all")
		sentence = self.sentences.get("active")
		xml_sentence = self.xmls[sentence]
		Tree(self.canvas, xml_sentence).draw()

	def run(self):
		return self.root.mainloop()

if __name__ == "__main__":
	GUI().run()
}}}