# Path: discodop/util.py
# def slice_bounds(seq, slice_obj, allow_step=False):
# 	"""Calculate the effective (start, stop) bounds of a slice.
# 
# 	Takes into account ``None`` indices and negative indices.
# 
# 	:returns: tuple ``(start, stop, 1)``, s.t. ``0 <= start <= stop <= len(seq)``
# 	:raises ValueError: if slice_obj.step is not None.
# 	:param allow_step: If true, then the slice object may have a non-None step.
# 		If it does, then return a tuple (start, stop, step)."""
# 	start, stop = (slice_obj.start, slice_obj.stop)
# 	if allow_step:
# 		slice_obj.step = 1 if slice_obj.step is None else slice_obj.step
# 		# Use a recursive call without allow_step to find the slice
# 		# bounds. If step is negative, then the roles of start and
# 		# stop (in terms of default values, etc), are swapped.
# 		if slice_obj.step < 0:
# 			start, stop, _ = slice_bounds(seq, slice(stop, start))
# 		else:
# 			start, stop, _ = slice_bounds(seq, slice(start, stop))
# 		return start, stop, slice_obj.step
# 	elif slice_obj.step not in (None, 1):
# 		raise ValueError('slices with steps are not supported by %s' %
# 				seq.__class__.__name__)
# 	start = 0 if start is None else start
# 	stop = len(seq) if stop is None else stop
# 	start = max(0, len(seq) + start) if start < 0 else start
# 	stop = max(0, len(seq) + stop) if stop < 0 else stop
# 	if stop > 0:  # Make sure stop doesn't go past the end of the list.
# 		try:  # Avoid calculating len(seq), may be expensive for lazy sequences
# 			seq[stop - 1]
# 		except IndexError:
# 			stop = len(seq)
# 	start = min(start, stop)
# 	return start, stop, 1
# 
# ANSICOLOR = {
# 		'black': 30,
# 		'red': 31,
# 		'green': 32,
# 		'yellow': 33,
# 		'blue': 34,
# 		'magenta': 35,
# 		'cyan': 36,
# 		'white': 37,
# }
# 
# def graphemelength(text):
# 	"""Return number of graphemes in string."""
# 	return grapheme.length(text)
# 
# def graphemecenter(text, width, fillchar=' '):
# 	"""Return text centered in a string of *grapheme* length width (not len()).
# 
# 	Padding is done using the specified fillchar (default is an ASCII space).
# 	The original string is returned if width is less than or equal to len(s).
# 	"""
# 	length = grapheme.length(text)
# 	if length > width:
# 		return text
# 	a = (width - length) // 2
# 	b = a + (width - length) % 2
# 	return (a * fillchar) + text + (b * fillchar)


import re
import random
from itertools import count
from operator import itemgetter
from collections import defaultdict, OrderedDict
from html import escape as htmlescape
from .util import slice_bounds, ANSICOLOR, graphemelength, graphemecenter
	from .bit import fanout as bitfanout
			else:
				for i in range(len(value) - 1, -1, -1):
					stack.append((value[i], treepos + (i, )))
		raise IndexError('index must be less than or equal to len(self)')

	def treeposition_spanning_leaves(self, start, end):
		"""
		:returns: The tree position of the lowest descendant of this tree
			that dominates ``self.leaves()[start:end]``.
		:raises ValueError: if ``end <= start``."""
		if end <= start:
			raise ValueError('end must be greater than start')
		# Find the tree positions of the start & end leaves,
		# and take the longest common subsequence.
		start_treepos = self.leaf_treeposition(start)
		end_treepos = self.leaf_treeposition(end - 1)
		# Find the first index where they mismatch:
		for i, a in enumerate(start_treepos):
			if i == len(end_treepos) or a != end_treepos[i]:
				return start_treepos[:i]
		return start_treepos

	# === Convert, copy =========================================
	@classmethod
	def convert(cls, val):
		"""Convert a tree between different subtypes of Tree.

		:param cls: the class that will be used for the new tree.
		:param val: The tree that should be converted."""
		if isinstance(val, Tree):

# Path: discodop/util.py
# def slice_bounds(seq, slice_obj, allow_step=False):
# 	"""Calculate the effective (start, stop) bounds of a slice.
# 
# 	Takes into account ``None`` indices and negative indices.
# 
# 	:returns: tuple ``(start, stop, 1)``, s.t. ``0 <= start <= stop <= len(seq)``
# 	:raises ValueError: if slice_obj.step is not None.
# 	:param allow_step: If true, then the slice object may have a non-None step.
# 		If it does, then return a tuple (start, stop, step)."""
# 	start, stop = (slice_obj.start, slice_obj.stop)
# 	if allow_step:
# 		slice_obj.step = 1 if slice_obj.step is None else slice_obj.step
# 		# Use a recursive call without allow_step to find the slice
# 		# bounds. If step is negative, then the roles of start and
# 		# stop (in terms of default values, etc), are swapped.
# 		if slice_obj.step < 0:
# 			start, stop, _ = slice_bounds(seq, slice(stop, start))
# 		else:
# 			start, stop, _ = slice_bounds(seq, slice(start, stop))
# 		return start, stop, slice_obj.step
# 	elif slice_obj.step not in (None, 1):
# 		raise ValueError('slices with steps are not supported by %s' %
# 				seq.__class__.__name__)
# 	start = 0 if start is None else start
# 	stop = len(seq) if stop is None else stop
# 	start = max(0, len(seq) + start) if start < 0 else start
# 	stop = max(0, len(seq) + stop) if stop < 0 else stop
# 	if stop > 0:  # Make sure stop doesn't go past the end of the list.
# 		try:  # Avoid calculating len(seq), may be expensive for lazy sequences
# 			seq[stop - 1]
# 		except IndexError:
# 			stop = len(seq)
# 	start = min(start, stop)
# 	return start, stop, 1
# 
# ANSICOLOR = {
# 		'black': 30,
# 		'red': 31,
# 		'green': 32,
# 		'yellow': 33,
# 		'blue': 34,
# 		'magenta': 35,
# 		'cyan': 36,
# 		'white': 37,
# }
# 
# def graphemelength(text):
# 	"""Return number of graphemes in string."""
# 	return grapheme.length(text)
# 
# def graphemecenter(text, width, fillchar=' '):
# 	"""Return text centered in a string of *grapheme* length width (not len()).
# 
# 	Padding is done using the specified fillchar (default is an ASCII space).
# 	The original string is returned if width is less than or equal to len(s).
# 	"""
# 	length = grapheme.length(text)
# 	if length > width:
# 		return text
# 	a = (width - length) // 2
# 	b = a + (width - length) % 2
# 	return (a * fillchar) + text + (b * fillchar)


# Path: discodop/tree.py
import re
import random
from itertools import count
from operator import itemgetter
from collections import defaultdict, OrderedDict
from html import escape as htmlescape
from .util import slice_bounds, ANSICOLOR, graphemelength, graphemecenter
	from .bit import fanout as bitfanout

			else:
				for i in range(len(value) - 1, -1, -1):
					stack.append((value[i], treepos + (i, )))
		raise IndexError('index must be less than or equal to len(self)')

	def treeposition_spanning_leaves(self, start, end):
		"""
		:returns: The tree position of the lowest descendant of this tree
			that dominates ``self.leaves()[start:end]``.
		:raises ValueError: if ``end <= start``."""
		if end <= start:
			raise ValueError('end must be greater than start')
		# Find the tree positions of the start & end leaves,
		# and take the longest common subsequence.
		start_treepos = self.leaf_treeposition(start)
		end_treepos = self.leaf_treeposition(end - 1)
		# Find the first index where they mismatch:
		for i, a in enumerate(start_treepos):
			if i == len(end_treepos) or a != end_treepos[i]:
				return start_treepos[:i]
		return start_treepos

	# === Convert, copy =========================================
	@classmethod
	def convert(cls, val):
		"""Convert a tree between different subtypes of Tree.

		:param cls: the class that will be used for the new tree.
		:param val: The tree that should be converted."""
		if isinstance(val, Tree):

			children = [cls.convert(child) for child in val]