class Tree(object):
	"""A mutable, labeled, n-ary tree structure.

	Each Tree represents a single hierarchical grouping of leaves and subtrees.
	A tree's children are encoded as a list of leaves and subtrees, where
	a leaf is a basic (non-tree) value; and a subtree is a nested Tree. Any
	other properties that a Tree defines are known as node properties, and are
	used to add information about individual hierarchical groupings. For
	example, syntax trees use a label property to label syntactic constituents
	with phrase labels, such as "NP" and "VP".
	Several Tree methods use tree positions to specify children or descendants
	of a tree. Tree positions are defined as follows:

	- The tree position ``i`` specifies a Tree's ith child.
	- The tree position () specifies the Tree itself.
	- If ``p`` is the tree position of descendant ``d``, then
		``p + (i,)`` specifies the ith child of ``d``.

	i.e., every tree position is either a single index ``i``,
	specifying ``self[i]``; or a sequence ``(i1, i2, ..., iN)``,
	specifying ``self[i1][i2]...[iN]``.

	The constructor can be called in two ways:

	- ``Tree(label, children)`` constructs a new tree with the specified label
		and list of children.
	- ``Tree(s)`` constructs a new tree by parsing the string s. Equivalent to
		calling the class method ``Tree.parse(s)``.
		NB: expects integers as leaves by default;
		use ``Tree.parse(s, parse_leaf=None)`` to interpret leaves as strings.
	"""

	# NB: _parent is only used by ParentedTree subclass, but __slots__
	# does not work with multiple inheritance.
	__slots__ = (
			'label',  # a string with the label of this constituent
			'children',  # a list of Tree instances or terminals
			'source',  # a list/tuple with extra treebank attributes
			'type',  # one of None, HEAD, COMPLEMENT, or MODIFIER
			'_parent',  # if this is a ParentedTree, the parent node, or None.
			)

	def __new__(cls, label_or_str=None, children=None):
		if label_or_str is None:
			return object.__new__(cls)  # used by copy.deepcopy
		if children is None:
			if not isinstance(label_or_str, str):
				raise TypeError("%s: Expected a label and child list "
						"or a single string; got: %s" % (
						cls.__name__, type(label_or_str)))
			return cls.parse(label_or_str)
		if (isinstance(children, str)
				or not hasattr(children, '__iter__')):
			raise TypeError("%s() argument 2 should be a list, not a "
					"string" % cls.__name__)
		return object.__new__(cls)

	def __init__(self, label_or_str, children=None):
		# Because __new__ may delegate to Tree.parse(), the __init__
		# method may end up getting called more than once (once when
		# constructing the return value for Tree.parse; and again when
		# __new__ returns). We therefore check if `children` is None
		# (which will cause __new__ to call Tree.parse()); if so, then
		# __init__ has already been called once, so just return.
		if children is None:
			return
		# list.__init__(self, children)
		self.label = label_or_str
		self.children = list(children)
		self.source = self.type = None

	# === Comparison operators ==================================
	def __eq__(self, other):
		if not isinstance(other, Tree):
			return False
		return (self.label == other.label
				and self.children == other.children)

	def __ne__(self, other):
		return not self.__eq__(other)

	def __lt__(self, other):
		if not isinstance(other, Tree):
			return False
		return (self.label < other.label
				or self.children < other.children)

	def __le__(self, other):
		if not isinstance(other, Tree):
			return False
		return (self.label <= other.label
				or self.children <= other.children)

	def __gt__(self, other):
		if not isinstance(other, Tree):
			return True
		return (self.label > other.label
				or self.children > other.children)

	def __ge__(self, other):
		if not isinstance(other, Tree):
			return False
		return (self.label >= other.label
				or self.children >= other.children)

	# === Delegated list operations ==============================
	def append(self, child):
		"""Append ``child`` to this node."""
		self.children.append(child)

	def extend(self, children):
		"""Extend this node's children with an iterable."""
		self.children.extend(children)

	def insert(self, index, child):
		"""Insert child at integer index."""
		self.children.insert(index, child)

	def pop(self, index=-1):
		"""Remove child at specified integer index (or default to last)."""
		return self.children.pop(index)

	def remove(self, child):
		"""Remove child, based on equality."""
		self.children.remove(child)

	def index(self, child):
		"""Return index of child, based on equality."""
		return self.children.index(child)

	def __iter__(self):
		return self.children.__iter__()

	def __len__(self):
		return self.children.__len__()

	def __bool__(self):
		return bool(self.children)

	# === Disabled list operations ==============================
	def __mul__(self, _):
		raise TypeError('Tree does not support multiplication')

	def __rmul__(self, _):
		raise TypeError('Tree does not support multiplication')

	def __add__(self, _):
		raise TypeError('Tree does not support addition')

	def __radd__(self, _):
		raise TypeError('Tree does not support addition')

	# === Indexing (with support for tree positions) ============
	def __getitem__(self, index):
		if isinstance(index, (int, slice)):
			return self.children.__getitem__(index)
		else:
			if index == ():
				return self
			elif len(index) == 1:
				return self[int(index[0])]
			return self[int(index[0])][index[1:]]

	def __setitem__(self, index, value):
		if isinstance(index, (int, slice)):
			return self.children.__setitem__(index, value)
		else:
			if index == ():
				raise IndexError('The tree position () may not be '
						'assigned to.')
			elif len(index) == 1:
				self[index[0]] = value
			else:
				self[index[0]][index[1:]] = value

	def __delitem__(self, index):
		if isinstance(index, (int, slice)):
			return self.children.__delitem__(index)
		else:
			if index == ():
				raise IndexError('The tree position () may not be deleted.')
			elif len(index) == 1:
				del self[index[0]]
			else:
				del self[index[0]][index[1:]]

	# === Basic tree operations =================================
	def leaves(self):
		""":returns: list containing this tree's leaves.

		The order reflects the order of the tree's hierarchical structure."""
		leaves = []
		for child in self.children:
			if isinstance(child, Tree):
				leaves.extend(child.leaves())
			else:
				leaves.append(child)
		return leaves

	def height(self):
		""":returns: The longest distance from this node to a leaf node.

		- The height of a tree containing no children is 1;
		- the height of a tree containing only leaves is 2;
		- the height of any other tree is one plus the maximum of its
			children's heights."""
		max_child_height = 0
		for child in self.children:
			if isinstance(child, Tree):
				max_child_height = max(max_child_height, child.height())
			else:
				max_child_height = max(max_child_height, 1)
		return 1 + max_child_height

	def subtrees(self, condition=None):
		"""Yield subtrees of this tree in depth-first, pre-order traversal.

		:param condition: a function ``Tree -> bool`` to filter which nodes are
			yielded (does not affect whether children are visited).

		NB: store traversal as list before any structural modifications."""
		# Non-recursive version
		agenda = [self]
		while agenda:
			node = agenda.pop()
			if isinstance(node, Tree):
				if condition is None or condition(node):
					yield node
				agenda.extend(node[::-1])

	def postorder(self, condition=None):
		"""A generator that does a post-order traversal of this tree.

		Similar to Tree.subtrees() which does a pre-order traversal.
		NB: store traversal as list before any structural modifications.

		:yields: Tree objects."""
		# Non-recursive; requires no parent pointers but uses O(n) space.
		agenda = [self]
		visited = set()
		while agenda:
			node = agenda[-1]
			if not isinstance(node, Tree):
				agenda.pop()
			elif id(node) in visited:
				agenda.pop()
				if condition is None or condition(node):
					yield node
			else:
				agenda.extend(node[::-1])
				visited.add(id(node))

	def find(self, condition):
		"""Return first child s.t. ``condition(child)`` is True, or None."""
		for child in self:
			if condition(child):
				return child
		return None

	def pos(self, nodes=False):
		"""Collect preterminals (part-of-speech nodes).

		:param nodes: if True, return a sequence of preterminal Tree objects
			instead of tuples. NB: a preterminal that dominates multiple
			terminals is returned once.
		:returns: a list of tuples containing leaves and pre-terminals
			(part-of-speech tags). The order reflects the order of the tree's
			hierarchical structure. A preterminal that dominates multiple
			terminals generates a tuple for each terminal."""
		agenda = [self]
		result = []
		while agenda:
			node = agenda.pop()
			if not isinstance(node, Tree):
				continue
			agenda.extend(node[::-1])
			for child in node:
				if not isinstance(child, Tree):
					if nodes:
						result.append(node)
						break
					result.append((child, node.label))
		return result

	def treepositions(self, order='preorder'):
		""":param order: One of preorder, postorder, bothorder, leaves."""
		positions = []
		if order in ('preorder', 'bothorder'):
			positions.append(())
		for i, child in enumerate(self.children):
			if isinstance(child, Tree):
				childpos = child.treepositions(order)
				positions.extend((i, ) + p for p in childpos)
			else:
				positions.append((i, ))
		if order in ('postorder', 'bothorder'):
			positions.append(())
		return positions

	def leaf_treeposition(self, index):
		"""
		:returns: The tree position of the index-th leaf in this tree;
			i.e., if ``tp=self.leaf_treeposition(i)``, then
			``self[tp]==self.leaves()[i]``.
		:raises IndexError: if this tree contains fewer than ``index + 1``
			leaves, or if ``index < 0``."""
		if index < 0:
			raise IndexError('index must be non-negative')
		stack = [(self, ())]
		while stack:
			value, treepos = stack.pop()
			if not isinstance(value, Tree):
				if index == 0:
					return treepos
				else:
					index -= 1
			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]
			tree = cls(val.label, children)
			tree.source = None if val.source is None else val.source[:]
			tree.type = val.type
			if (isinstance(val, ImmutableTree)
					and isinstance(cls, ImmutableTree)):
				tree.bitset = val.bitset  # pylint: disable=W0201,E0237
			return tree
		return val

	def copy(self, deep=False):
		"""Create a copy of this tree."""
		if not deep:
			return self.__class__(self.label, self)
		return self.__class__.convert(self)

	def _frozen_class(self):
		"""The frozen version of this class."""
		return ImmutableTree

	def freeze(self, leaf_freezer=None):
		""":returns: an immutable version of this tree."""
		frozen_class = self._frozen_class()
		if leaf_freezer is None:
			newcopy = frozen_class.convert(self)
		else:
			newcopy = self.copy(deep=True)
			for pos in newcopy.treepositions('leaves'):
				newcopy[pos] = leaf_freezer(newcopy[pos])
			newcopy = frozen_class.convert(newcopy)
		hash(newcopy)  # Make sure the leaves are hashable.
		return newcopy

	# === Parsing ===============================================
	@classmethod
	def parse(cls, s, parse_label=None, parse_leaf=int,
			label_pattern=None, leaf_pattern=None):
		"""Parse a bracketed tree string and return the resulting tree.
		Trees are represented as nested bracketings, such as:
		``(S (NP (NNP John)) (VP (V runs)))``

		:param s: The string to parse
		:param parse_label, parse_leaf: If specified, these functions are
			applied to the substrings of s corresponding to labels and leaves
			(respectively) to obtain the values for those labels and leaves.
			They should have the following signature: parse_label(str) -> value
		:param label_pattern, leaf_pattern: Regular expression patterns used to
			find label and leaf substrings in s. By default, both label and
			leaf patterns are defined to match any sequence of non-whitespace
			non-bracket characters.
		:returns: A tree corresponding to the string representation s.
			If this class method is called using a subclass of Tree, then it
			will return a tree of that type."""
		# Construct a regexp that will tokenize the string.
		open_b, close_b = '()'
		open_pattern, close_pattern = (re.escape(open_b), re.escape(close_b))
		if label_pattern is None:
			label_pattern = r'[^\s%s%s]+' % (open_pattern, close_pattern)
		if leaf_pattern is None:
			leaf_pattern = r'[^\s%s%s]+' % (open_pattern, close_pattern)
		token_re = re.compile(r'%s\s*(%s)?|%s|(%s)' % (
				open_pattern, label_pattern, close_pattern, leaf_pattern))
		# Walk through each token, updating a stack of trees.
		stack = [(None, [])]  # list of (label, children) tuples
		for match in token_re.finditer(s):
			token = match.group()
			if token[0] == open_b:  # Beginning of a tree/subtree
				if len(stack) == 1 and stack[0][1]:
					cls._parse_error(s, match, 'end-of-string')
				label = token[1:].lstrip()
				if parse_label is not None:
					label = parse_label(label)
				stack.append((label, []))
			elif token == close_b:  # End of a tree/subtree
				if len(stack) == 1:
					if stack[0][1]:
						cls._parse_error(s, match, 'end-of-string')
					else:
						cls._parse_error(s, match, open_b)
				label, children = stack.pop()
				stack[-1][1].append(cls(label, children))
			else:  # Leaf node
				if len(stack) == 1:
					cls._parse_error(s, match, open_b)
				if parse_leaf is not None:
					token = parse_leaf(token)
				stack[-1][1].append(token)
		# check that we got exactly one complete tree.
		if len(stack) > 1:
			cls._parse_error(s, 'end-of-string', close_b)
		elif stack[0][1]:
			assert stack[0][0] is None and len(stack[0][1]) == 1
		else:
			cls._parse_error(s, 'end-of-string', open_b)
		tree = stack[0][1][0]
		return tree

	@classmethod
	def _parse_error(cls, orig, match, expecting):
		"""Display a friendly error message when parsing a tree string fails.

		:param orig: The string we're parsing.
		:param match: regexp match of the problem token.
		:param expecting: what we expected to see instead."""
		# Construct a basic error message
		if match == 'end-of-string':
			pos, token = len(orig), 'end-of-string'
		else:
			pos, token = match.start(), match.group()
		msg = '%s.parse(): expected %r but got %r\n%sat index %d.' % (
			cls.__name__, expecting, token, ' ' * 12, pos)
		# Add a display showing the error token itself:
		s = orig.replace('\n', ' ').replace('\t', ' ')
		offset = pos
		if len(s) > pos + 10:
			s = s[:pos + 10] + '...'
		if pos > 10:
			s = '...' + s[pos - 10:]
			offset = 13
		msg += '\n%s"%s"\n%s^' % (' ' * 16, s, ' ' * (17 + offset))
		msg += '\n%s' % orig
		raise ValueError(msg)

	# === String Representations ================================
	def __repr__(self):
		childstr = ", ".join(repr(c) for c in self)
		return '%s(%r, [%s])' % (self.__class__.__name__, self.label, childstr)

	def __str__(self):
		return self._pprint_flat('()')

	def pprint(self, margin=70, indent=0, brackets='()'):
		"""	:returns: A pretty-printed string representation of this tree.
		:param margin: The right margin at which to do line-wrapping.
		:param indent: The indentation level at which printing begins. This
			number is used to decide how far to indent subsequent lines."""
		# Try writing it on one line.
		s = self._pprint_flat(brackets)
		if len(s) + indent < margin:
			return s
		# If it doesn't fit on one line, then write it on multi-lines.
		if isinstance(self.label, str):
			s = '%s%s' % (brackets[0], self.label)
		else:
			s = '%s%r' % (brackets[0], self.label)
		for child in self.children:
			if isinstance(child, Tree):
				s += '\n' + ' ' * (indent + 2) + child.pprint(margin,
						indent + 2, brackets)
			elif isinstance(child, tuple):
				s += '\n' + ' ' * (indent + 2) + '/'.join(child)
			elif isinstance(child, str):
				s += '\n' + ' ' * (indent + 2) + '%s' % child
			else:
				s += '\n' + ' ' * (indent + 2) + '%r' % child
		return s + brackets[1]

	def _pprint_flat(self, brackets):
		"""Pretty-printing helper function."""
		childstrs = []
		for child in self.children:
			if isinstance(child, Tree):
				childstrs.append(child._pprint_flat(brackets))
			elif isinstance(child, str) or child is None:
				childstrs.append(child or '')
			else:
				childstrs.append(repr(child))
		if isinstance(self.label, str):
			return '%s%s %s%s' % (brackets[0], self.label,
									' '.join(childstrs), brackets[1])
		else:
			return '%s%r %s%s' % (brackets[0], self.label,
					' '.join(childstrs), brackets[1])

	def draw(self):
		""":returns: an ASCII art visualization of tree."""
		return DrawTree(self, ['%d' % a for a in self.leaves()]).text()

	def _repr_svg_(self):
		"""Return a rich representation for IPython notebook."""
		return DrawTree(self, ['%d' % a for a in self.leaves()]).svg() class ParentedTree(Tree):
	"""A Tree that maintains parent pointers for single-parented trees.

	The parent pointers are updated whenever any change is made to a tree's
	structure.

	The following read-only property values are automatically updated
	whenever the structure of a parented tree is modified: parent,
	parent_index, left_sibling, right_sibling, root, treeposition.
	Each ParentedTree may have at most one parent; i.e., subtrees may not be
	shared. Any attempt to reuse a single ParentedTree as a child of more than
	one parent (or as multiple children of the same parent) will cause a
	ValueError exception to be raised. ParentedTrees should never be used in
	the same tree as Trees or MultiParentedTrees. Mixing tree implementations
	may result in incorrect parent pointers and in TypeError exceptions.

	The ParentedTree class redefines all operations that modify a
	tree's structure to call two methods, which are used by subclasses to
	update parent information:

	- ``_setparent()`` is called whenever a new child is added.
	- ``_delparent()`` is called whenever a child is removed."""
	__slots__ = ()

	def __init__(self, label_or_str, children=None):
		if children is None:
			return  # see note in Tree.__init__()
		self._parent = None
		super().__init__(label_or_str, children)
		# iterate over self.children, *not* children,
		# because children might be an iterator.
		for i, child in enumerate(self.children):
			if isinstance(child, Tree):
				self._setparent(child, i, dry_run=True)
		for i, child in enumerate(self.children):
			if isinstance(child, Tree):
				self._setparent(child, i)

	def _frozen_class(self):
		return ImmutableParentedTree

	# === Properties =================================================
	def _get_parent_index(self):
		"""The index of this tree in its parent.

		i.e., ptree.parent[ptree.parent_index] is ptree.
		Note that ptree.parent_index is not necessarily equal to
		ptree.parent.index(ptree), since the index() method
		returns the first child that is _equal_ to its argument."""
		if self._parent is None:
			return None
		for i, child in enumerate(self._parent):
			if child is self:
				return i
		raise ValueError('expected to find self in self._parent!')

	def _get_left_sibling(self):
		"""The left sibling of this tree, or None if it has none."""
		parent_index = self._get_parent_index()
		if self._parent and parent_index > 0:
			return self._parent[parent_index - 1]  # pylint: disable=E1136
		return None  # no left sibling

	def _get_right_sibling(self):
		"""The right sibling of this tree, or None if it has none."""
		parent_index = self._get_parent_index()
		if self._parent and parent_index < (len(self._parent) - 1):
			return self._parent[parent_index + 1]  # pylint: disable=E1136
		return None  # no right sibling

	def _get_treeposition(self):
		"""The tree position of this tree, relative to the root of the tree.

		i.e., ptree.root[ptree.treeposition] is ptree."""
		if self._parent is None:
			return ()
		return (self._parent._get_treeposition()
				+ (self._get_parent_index(), ))

	def _get_root(self):
		""":returns: the root of this tree."""
		node = self
		while node._parent is not None:
			node = node._parent
		return node

	parent = property(lambda self: self._parent,
			doc="""The parent of this tree, or None if it has no parent.""")
	parent_index = property(_get_parent_index, doc=_get_parent_index.__doc__)
	left_sibling = property(_get_left_sibling, doc=_get_left_sibling.__doc__)
	right_sibling = property(_get_right_sibling, doc=_get_right_sibling.__doc__)
	root = property(_get_root, doc=_get_root.__doc__)
	treeposition = property(_get_treeposition, doc=_get_treeposition.__doc__)

	# === Parent Management ==========================================
	def _delparent(self, child, index):
		"""Update child's parent pointer to not point to self.

		This method is only called if child's type is Tree; i.e., it is not
		called when removing a leaf from a tree. This method is always called
		before the child is actually removed from self's child list.

		:param index: The index of child in self."""
		assert isinstance(child, ParentedTree)
		assert self[index] is child and child._parent is self
		child._parent = None

	def _setparent(self, child, _index, dry_run=False):
		"""Update child's parent pointer to point to self.

		This method is only called if child's type is Tree; i.e., it is not
		called when adding a leaf to a tree. This method is always called
		before the child is actually added to self's child list. Typically, if
		child is a tree, then its type needs to match self's type. This
		prevents mixing of different tree types (single-, multi-, and
		non-parented).

		:param index: The index of child in self.
		:param dry_run: If true, the don't actually set the child's parent
			pointer; just check for any error conditions, and raise an
			exception if one is found.
		:raises TypeError: if child is a tree with an inappropriate type."""
		if not isinstance(child, ParentedTree):
			raise TypeError('Cannot insert a non-ParentedTree '
					'into a ParentedTree')
		if child._parent is not None:
			raise ValueError('Cannot insert a subtree that already '
					'has a parent.')
		if not dry_run:
			child._parent = self

	# === Methods that add/remove children ======================
	# Every method that adds or removes a child must make
	# appropriate calls to _setparent() and _delparent().
	def __delitem__(self, index):
		if isinstance(index, slice):  # del ptree[start:stop]
			start, stop, _ = slice_bounds(self, index)
			# Clear all the children pointers.
			for i in range(start, stop):
				if isinstance(self[i], Tree):
					self._delparent(self[i], i)
			# Delete the children from our child list.
			super().__delitem__(index)
		elif isinstance(index, int):  # del ptree[i]
			if index < 0:
				index += len(self)
			if index < 0:
				raise IndexError('index out of range')
			# Clear the child's parent pointer.
			if isinstance(self[index], Tree):
				self._delparent(self[index], index)
			# Remove the child from our child list.
			super().__delitem__(index)
		elif index == ():  # del ptree[()]
			raise IndexError('The tree position () may not be deleted.')
		elif len(index) == 1:  # del ptree[(i, )]
			del self[index[0]]
		else:  # del ptree[i1, i2, i3]
			del self[index[0]][index[1:]]

	def __setitem__(self, index, value):
		if isinstance(index, slice):  # ptree[start:stop] = value
			start, stop, _ = slice_bounds(self, index)
			# make a copy of value, in case it's an iterator
			if not isinstance(value, (list, tuple)):
				value = list(value)
			# Check for any error conditions, so we can avoid ending
			# up in an inconsistent state if an error does occur.
			for i, child in enumerate(value):
				if isinstance(child, Tree):
					self._setparent(child, start + i, dry_run=True)
			# clear the child pointers of all parents we're removing
			for i in range(start, stop):
				if isinstance(self[i], Tree):
					self._delparent(self[i], i)
			# set the child pointers of the new children. We do this
			# after clearing *all* child pointers, in case we're e.g.
			# reversing the elements in a tree.
			for i, child in enumerate(value):
				if isinstance(child, Tree):
					self._setparent(child, start + i)
			# finally, update the content of the child list itself.
			super().__setitem__(index, value)
		elif isinstance(index, int):  # ptree[i] = value
			if index < 0:
				index += len(self)
			if index < 0:
				raise IndexError('index out of range')
			# if the value is not changing, do nothing.
			if value is self[index]:
				return
			# Set the new child's parent pointer.
			if isinstance(value, Tree):
				self._setparent(value, index)
			# Remove the old child's parent pointer
			if isinstance(self[index], Tree):
				self._delparent(self[index], index)
			# Update our child list.
			super().__setitem__(index, value)
		elif index == ():  # ptree[()] = value
			raise IndexError('The tree position () may not be assigned to.')
		elif len(index) == 1:  # ptree[(i, )] = value
			self[index[0]] = value
		else:  # ptree[i1, i2, i3] = value
			self[index[0]][index[1:]] = value

	def append(self, child):
		if isinstance(child, Tree):
			self._setparent(child, len(self))
		super().append(child)

	def extend(self, children):
		for child in children:
			if isinstance(child, Tree):
				self._setparent(child, len(self))
			super().append(child)

	def insert(self, index, child):
		# Handle negative indexes. Note that if index < -len(self),
		# we do *not* raise an IndexError, unlike __getitem__. This
		# is done for consistency with list.__getitem__ and list.index.
		if index < 0:
			index += len(self)
		if index < 0:
			index = 0
		# Set the child's parent, and update our child list.
		if isinstance(child, Tree):
			self._setparent(child, index)
		super().insert(index, child)

	def pop(self, index=-1):
		if index < 0:
			index += len(self)
		if index < 0:
			raise IndexError('index out of range')
		if isinstance(self[index], Tree):
			self._delparent(self[index], index)
		return super().pop(index)

	# NB: like `list`, this is done by equality, not identity!
	# To remove a specific child, use del ptree[i].
	def remove(self, child):
		index = self.index(child)
		if isinstance(self[index], Tree):
			self._delparent(self[index], index)
		super().remove(child)

	def detach(self):
		"""Remove this node from its parent node, if it has one.

		:returns: self, s.t. self.parent is None."""
		if self.parent is None:
			return self
		return self.parent.pop(self.parent_index)

	def disown(self):
		"""Detach children of this node and return as list."""
		children = [child for child in self]
		self[:] = []
		return children

	def spliceabove(self, label):
		"""Insert a new node between this node and its parent."""
		i = self.parent_index
		parent = self.parent
		newnode = ParentedTree(label, [self.detach()])
		parent.insert(i, newnode)
		return newnode

	def splicebelow(self, label):
		"""Insert a new node between this node and its children."""
		newnode = ParentedTree(label, self.disown())
		self.append(newnode)
		return newnode

	def prune(self):
		"""Replace this node with its children."""
		i = self.parent_index
		children = self.disown()
		self.parent[i:i + 1] = children  # pylint: disable=E1137 class ImmutableTree(Tree):
	"""A tree which may not be modified.; has a hash() value.

	NB: the ``label`` and ``children`` attributes should not be modified, but
	this is not enforced.

	This class has the following optimizations compared to Tree objects:
		- precomputed ``hash()`` value
		- precomputed ``leaves()`` value of each node
		- a bitset attribute recording the leaf indices dominated by each node
	"""
	__slots__ = ('_hash', '_leaves', 'bitset')

	def __init__(self, label_or_str, children=None):
		if children is None:
			return  # see note in Tree.__init__()
		self._hash = self._leaves = None
		super().__init__(label_or_str, children)
		# Precompute our hash value. This ensures that we're really
		# immutable. It also means we only have to calculate it once.
		try:
			self._hash = hash((self.label, tuple(self)))
		except (TypeError, ValueError) as err:
			raise ValueError('ImmutableTree\'s label and children '
					'must be immutable:\n%s %r\n%r' % (self.label, self, err))
		else:
			# self._leaves = Tree.leaves(self)
			self._addleaves()
			try:
				self.bitset = sum(1 << n for n in self._leaves)
			except TypeError as err:
				self.bitset = None

	def _addleaves(self):
		"""Set leaves attribute of this node and its descendants."""
		leaves = []
		for child in self.children:
			if isinstance(child, Tree):
				if child._leaves is None:
					child._addleaves()
				leaves.extend(child._leaves)
			else:
				leaves.append(child)
		self._leaves = leaves

	def leaves(self):
		return self._leaves

	def __setitem__(self, _index, _value):
		raise ValueError('ImmutableTrees may not be modified')

	def __setslice__(self, _start, _stop, _value):
		raise ValueError('ImmutableTrees may not be modified')

	def __delitem__(self, _index):
		raise ValueError('ImmutableTrees may not be modified')

	def __delslice__(self, _start, _stop):
		raise ValueError('ImmutableTrees may not be modified')

	def __iadd__(self, _):
		raise ValueError('ImmutableTrees may not be modified')

	def __imul__(self, _):
		raise ValueError('ImmutableTrees may not be modified')

	def append(self, _):
		raise ValueError('ImmutableTrees may not be modified')

	def extend(self, _):
		raise ValueError('ImmutableTrees may not be modified')

	def pop(self, _=None):
		raise ValueError('ImmutableTrees may not be modified')

	def remove(self, _):
		raise ValueError('ImmutableTrees may not be modified')

	def __hash__(self):
		return self._hash class DiscTree(ImmutableTree):
	"""Wrap an immutable tree with indices as leaves and a sentence.

	Provides hash & equality."""
	__slots__ = ('sent', )

	def __init__(self, tree, sent):
		self.sent = tuple(sent)
		super().__init__(tree.label, tuple(
				DiscTree(child, sent) if isinstance(child, Tree) else child
				for child in tree))

	def __eq__(self, other):
		"""Test whether two discontinuous trees are equivalent.

		Assumes canonicalized() ordering."""
		if not isinstance(other, Tree):
			return False
		if self.label != other.label or len(self) != len(other):
			return False
		for a, b in zip(self.children, other.children):
			istree = isinstance(a, Tree)
			if istree != isinstance(b, Tree):
				return False
			elif not istree:
				return self.sent[a] == other.sent[b]
			elif not a.__eq__(b):
				return False
		return True

	def __hash__(self):
		return hash((self.label, ) + tuple(child.__hash__()
				if isinstance(child, Tree) else self.sent[child]
				for child in self.children))

	def __repr__(self):
		return "DisctTree(%r, %r)" % (
				super().__repr__(), self.sent) def escape(text):
	"""Escape all occurrences of parentheses and replace None with ''."""
	return '' if text is None else text.replace(
			'(', '#LRB#').replace(')', '#RRB#') def unescape(text):
	"""Reverse escaping of parentheses, frontier spans."""
	return None if text in ('', '#FRONTIER#') else text.replace(
			'#LRB#', '(').replace('#RRB#', ')') def brackettree(treestr, detectdisc=True):
	"""Parse a single tree presented in (disc)bracket format.

	:param detectdisc: if True, enable discbracket detection;
		if False, force bracket format.
	:returns: (tree, sent) tuple of ParentedTree and list of str."""
	# bracket: terminals are not all indices
	if not detectdisc or STRTERMRE.search(treestr):
		sent, cnt = [], count()

		def substleaf(x):
			"""Collect word and return index."""
			sent.append(unescape(x))
			return next(cnt)

		tree = ParentedTree.parse(FRONTIERNTRE.sub(' #FRONTIER#)',
				SUPERFLUOUSSPACERE.sub(')', treestr)),
				parse_leaf=substleaf)
	else:  # discbracket: terminals have indices
		sent = {}

		def substleaf(x):
			"""Collect word and return index."""
			idx, word = x.split('=', 1)
			idx = int(idx)
			sent[idx] = unescape(word)
			return idx

		tree = ParentedTree.parse(
				SUPERFLUOUSSPACERE.sub(')', treestr),
				parse_leaf=substleaf)
		sent = [sent.get(n, None) for n in range(max(sent) + 1)]
	return tree, sent def writediscbrackettree(tree, sent, pretty=False):
	"""Return tree in bracket notation with leaves as ``index=word``."""
	treestr = tree.pprint() if pretty else str(tree)
	return INDEXRE.sub(
			lambda x: ' %s=%s)' % (x.group(1), escape(sent[int(x.group(1))])),
			treestr) + '\n' LEAVESRE = re.compile(r' (?=\))| ([^ ()]+)\s*(?=[\s)])') def openread(filename, encoding='utf8'):
	"""Open stdin/file for reading; decompress gz/lz4/zst files on-the-fly.

	:param encoding: if None, mode is binary; otherwise, text."""
	mode = 'rb' if encoding is None else 'rt'
	if filename == '-':  # TODO: decompress stdin on-the-fly
		return open(sys.stdin.fileno(), mode=mode, encoding=encoding)
	if not isinstance(filename, int):
		if filename.endswith('.gz'):
			return gzip.open(filename, mode=mode, encoding=encoding)
		elif filename.endswith('.zst'):
			return genericdecompressor('zstd', filename, encoding)
		elif filename.endswith('.lz4'):
			return genericdecompressor('lz4', filename, encoding)
	return open(filename, mode=mode, encoding=encoding) def merge(*iterables, key=None):
	"""Generator that performs an n-way merge of sorted iterables.

	>>> list(merge([0, 1, 2], [0, 1, 2, 3]))
	[0, 0, 1, 1, 2, 2, 3]

	Similar to ``heapq.merge``, but ``key`` can be specified.

	NB: while a sort key may be specified, the individual iterables must
	already be sorted with this key."""
	def defaultkey(x):
		"""Default key() function (identity)."""
		return x

	heap = []
	entry = None
	if key is None:
		key = defaultkey

	for cnt, it in enumerate(iterables, 1):
		items = iter(it)
		try:
			item = next(items)
		except StopIteration:
			pass
		else:
			heap.append(Entry((item, items), key(item), cnt))
	heapify(heap)

	while len(heap) > 1:
		try:
			while True:
				entry = heap[0]
				item, iterable = entry.key
				yield item
				item = next(iterable)
				entry.key = (item, iterable)
				entry.value = key(item)
				heapreplace(heap, entry)
		except StopIteration:
			heappop(heap)

	if heap:  # only a single iterator remains, skip heap
		entry = heappop(heap)
		item, iterable = entry.key
		yield item
		yield from iterable
import io
import re
import gzip
import codecs
import numpy as np
	import logging
	import logging
	import logging
from operator import mul, itemgetter
from itertools import count, islice, repeat
from collections import defaultdict, Counter, OrderedDict
from .tree import (Tree, ParentedTree, ImmutableTree, DiscTree,
		escape, unescape, brackettree, writediscbrackettree)
from .treebank import LEAVESRE
from .util import openread, merge as utilmerge
from functools import reduce  # pylint: disable=redefined-builtin
	from .fragments import recurringfragments
	from .fragments import allfragments
	from .fragments import recurringfragments, allfragments
	from discodop._fragments import pygetsent
	from .treetransforms import factorconstituent, addbitsets
	# 	  terminal or non-terminal child: A, B, C)
	# 	- Non-leaf, non-spine nodes of auxiliary tree (i.e., any node with
	# 	  at least one child which is not part of the path from root to foot
	# 	  node: H).
	#
	# Within the osTAG reduction to CFG, nodes are addressed with a
	# unique label (@n or @n-m; sentence and node number), and the spine
	# of an auxiliary tree has auxiliary tree node labels (A) and the original
	# adjunction site (B) in an applicative notation: A[B]:
	#  Initial tree                      Auxiliary tree applied to node Y:
	#       A                               F[Y]$
	#  B@2--|--C@3                      G[Y]$-|---H@1
	#  |        |                        |         |
	#  D        E                        Y$*       I

	rules = Counter()  # rule => freq
	lexicalrules = defaultdict(Counter)  # token => lhs => freq
	decorator = SpinedTreeDecorator(memoize=packedgraph)
	decinittrees = []
	decauxtrees = []
	# Given an unaddressed label, all addressed root labels
	# of auxiliary trees that can be used in an adjunction on this label.
	auxroots = defaultdict(set)  # NP => {NP@12, NP@17, ...}

	# Given an unaddressed label, all addressed labels where an adjunction can
	# be initiated.
	adjsites = defaultdict(set)  # NP => {NP@12, NP@17, ...}

	# Given addressed node N on the spine of an auxiliary tree, collect all
	# nodes M s.t. the auxiliary tree of N can be adjoined at node M;
	# i.e., nodepairs[A] = {B, ...} implies generating A[B]
	nodepairs = defaultdict(set)  # NP@3 => {NP@5, NP@9, ... }

	# assign addresses to all nodes, collect adjunction sites
	for tree, weight in inittrees.items():
		tree, sent = brackettree(tree, detectdisc=True)
		dectree = decorator.decorate(tree, sent, False)
		decinittrees.append((dectree, sent, weight))
		for node in dectree.subtrees():
			if not (substitutionsite(node, sent) or preterminal(node, sent)):
				adjsites[REMOVEDEC.sub('', node.label)].add(node.label)
	logging.info('decorated initial trees')
	for tree, weight in auxtrees.items():
		tree, sent = brackettree(tree, detectdisc=True)
		dectree = decorator.decorate(tree, sent, True)
		decauxtrees.append((dectree, sent, weight))
		auxroots[REMOVEDEC.sub('', dectree.label)].add(dectree.label)
		for node in dectree.subtrees():
			if spinal(node):
				# NB: this is a reference; labels added to adjoinable later on
				# will be found through this key.
				nodepairs[node.label] = adjsites[
						REMOVEDEC.sub('', dectree.label)]
			elif not substitutionsite(node, sent):
				adjsites[REMOVEDEC.sub('', node.label)].add(node.label)
	logging.info('decorated aux trees')

	# extract rules
	for tree, sent, weight in decinittrees:
		for node in tree.subtrees(lambda n: not substitutionsite(n, sent)):
			if isinstance(node[0], int):
				lexicalrules[sent[node[0]]][node.label] += (
						weight if node is tree else 1)
			else:
				yfstr = '01' if len(node) == 2 else '0'
				rule = '%s\t%s\t%s' % (
						node.label,
						'\t'.join(child.label for child in node),
						yfstr)
				rules[rule] += weight if node is tree else 1
	logging.info('extracted initial tree rules')
	cnt = 0
	for tree, sent, weight in decauxtrees:
		for node in tree.subtrees(lambda n: not substitutionsite(n, sent)):
			if isinstance(node[0], int):
				if sent[node[0]] != '*':  # rule type 1; skip foot node
					lexicalrules[sent[node[0]]][node.label] += 1
			else:
				yfstr = '01' if len(node) == 2 else '0'
				# rule type 2
				if spinal(node):  # and isinstance(node[0], Tree):
					# replace lhs, spine node label with all possible NxM
					for adjsite in nodepairs[node.label]:
						newlhs = '%s[%s]' % (node.label, adjsite)
						newrhs = '\t'.join(spinallabel(child, sent, adjsite)
								for child in node)
						newrule = '%s\t%s\t%s' % (newlhs, newrhs, yfstr)
						rules[newrule] += 1
				else:  # rule type 1
					rule = '%s\t%s\t%s' % (
							node.label,
							'\t'.join(child.label for child in node),
							yfstr)
					rules[rule] += 1
			# rule type 3 (type 4 eliminated):
			# M => N(M) s.t. N is an aux root node
			for m in adjsites[REMOVEDEC.sub('', tree.label)]:
				rule = '%s\t%s\t0' % (m, '%s[%s]' % (tree.label, m))
				rules[rule] += weight
		cnt += 1
		if cnt % 100 == 0:
			logging.info('proccessed aux tree %d / %d', cnt, len(auxtrees))
	logging.info('extracted auxiliary tree rules')

	if extrarules is not None:
		for ((lhs, _), (token, )), weight in extrarules.items():
			lexicalrules[token][lhs] += weight
	# NB: assumes normalization is taken care of in Grammar() constructor
	rulesstr = ''.join('%s\t%d\n' % (rule, weight)
			for rule, weight in rules.items())
	lexicon = ''.join('%s\t%s\n' % (word,
			'\t'.join('%s %g' % (lhs, weight)
				for lhs, weight in lexicalrules[word].items()))
			for word in lexicalrules)
	return rulesstr, lexicon


# start ostag helper functions
def extractinit(tree, root, foot):
	"""Return copy of tree where ``foot`` is substituted for ``foot``."""

	return Tree(tree.label, [