def _slice(text, start, end):
	if end:
		return text[start:-end]
	else:
		return text[start:]


def _apply(text, change, selection=None):
	pos, before, after = change

	if selection:
		d = diff(before, after, 0)
		if pos + d[0] <= selection[0]:
			selection[0] += len(after) - len(before)
		if pos + d[0] <= selection[1]:
			selection[1] += len(after) - len(before)

	return text[0:pos] + after + text[pos + len(before):]


def apply(text, change, selection=None):
	start, end, before, after = change

	# special handling for resets
	if start == 0 and end == 0 and before == '' and text != '':
		start, end, before, after = diff(text, after, 3)

	# try exact match
	if text[start:].startswith(before):
		return _apply(text, [start, before, after], selection)

	# try exact match in similar position
	best = -1
	best_dist = len(text)
	for i in range(len(text)):
		if not text[i:].startswith(before):
			continue
		dist = abs(i - start)
		if dist < best_dist:
			best = i
			best_dist = dist
		else:
			break

	if best != -1:
		return _apply(text, [best, before, after], selection)

	# otherwise, ignore the change
	return text


def unapply(text, change, selection=None):
	start, end, before, after = change
	return apply(text, [start, end, after, before], selection)


def diff(text1, text2, ctx):
	start = 0
	end = 0

	while (
		start < len(text1)
		and start < len(text2)
		and text1[start] == text2[start]
	):
		start += 1
	while (
		start + end < len(text1)
		and start + end < len(text2)
		and text1[-(end + 1)] == text2[-(end + 1)]
	):
		end += 1

	start = max(0, start - ctx)
	end = max(0, end - ctx)

	return [start, end, _slice(text1, start, end), _slice(text2, start, end)]


def merge(change1, change2):
	start1, end1, before1, after1 = change1
	start2, end2, before2, after2 = change2

	if start1 + len(after1) + end1 == start2 + len(before2) + end2:
		# merge subsequent inserts
		if start2 >= start1 and after1[start2 - start1:].startswith(before2):
			after = _apply(after1, [start2 - start1, before2, after2])
			return [[start1, end1, before1, after]]

		# merge subsequent deletes (inverse insert)
		if start1 >= start2 and before2[start1 - start2:].startswith(after1):
			before = _apply(before2, [start1 - start2, after1, before1])
			return [[start2, end2, before, after2]]

	return [change1, change2]


def push_change(changes, change):
	if not changes:
		changes.append(change)
	else:
		last = changes.pop()
		merged = merge(last, change)
		for change in merged:
			changes.append(change)