class Pred(object):
    """
    A superclass for all Pred classes.
    Instances of Pred denote a completely underspecified predicate.
    """

    __slots__ = ()  # Suppress __dict__

    def __str__(self):
        """
        Returns 'predsort', the type name for predicates in Delph-in grammars
        """
        return 'predsort'

    def __repr__(self):
        """
        Returns a string representation
        """
        return 'Pred()'

    def __hash__(self):
        return hash(None)

    def __eq__(self, other):
        """
        Checks pred equality
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return type(other) is Pred

    def __ne__(self, other):
        """
        Checks pred inequality
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return type(other) is not Pred

    def __le__(self, other):
        """
        Checks pred leq comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return True

    def __lt__(self, other):
        """
        Checks pred lt comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return type(other) != Pred

    def __ge__(self, other):
        """
        Checks pred geq comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return type(other) == Pred

    def __gt__(self, other):
        """
        Checks pred gt comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return False

    def is_more_specific(self, other, hierarchy=None):
        """
        Checks whether this object is a more specific pred than the other
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        if hierarchy is not None and str(self) in hierarchy.get(str(other), ()):
            return True
        return False

    def is_less_specific(self, other, hierarchy=None):
        """
        Checks whether this object is a less specific pred than the other
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        if hierarchy is not None and str(other) in hierarchy.get(str(self), ()):
            return True
        return type(other) is not Pred

    @staticmethod
    def normalise_string(string):
        """
        Normalises a predicate string
        """
        # Disallow spaces
        if ' ' in string:
            raise PydmrsValueError('Predicates must not contain spaces')
        # Strip surrounding quotes and disallow other quotes
        if string[0] == '"' and string[-1] == '"':
            string = string[1:-1]
        if string[0] == "'":
            warn('Predicates with opening single-quote have been deprecated',
                 PydmrsDeprecationWarning)
            string = string[1:]
        if '"' in string:
            raise PydmrsValueError('Predicates must not contain quotes')
        # Force lower case
        if not string.islower():
            warn('Predicates must be lower-case', PydmrsWarning)
            string = string.lower()
        # Strip trailing '_rel'
        if string[-4:] == '_rel':
            string = string[:-4]

        return string

    @classmethod
    def from_string(cls, string):
        """
        Instantiates a pred from a string, normalising as necessary
        """
        normalised = cls.normalise_string(string)
        return cls.from_normalised_string(normalised)

    @staticmethod
    def from_normalised_string(string):
        """
        Instantiates a suitable type of Pred, from a string
        """
        if string[0] == '_':
            return RealPred.from_normalised_string(string)
        else:
            return GPred.from_normalised_string(string) class RealPred(namedtuple('RealPredNamedTuple', ('lemma', 'pos', 'sense')), Pred):
    """
    Real predicate, with a lemma, part of speech, and (optional) sense.
    All three fields can be underspecified by using '?'.
    The pos can also be underspecified as 'u'.
    The sense can also be underspecified as 'unknown'.
    """

    __slots__ = ()  # Suppress __dict__

    def __new__(cls, lemma, pos, sense=None):
        """
        Create a new instance, allowing the sense to be optional,
        and requiring non-empty lemma and pos
        """
        if lemma is None:
            raise PydmrsValueError('a RealPred must have lemma')
        if pos is None:
            raise PydmrsValueError('a RealPred must have pos')
        if ' ' in lemma or ' ' in pos or (sense and ' ' in sense):
            raise PydmrsValueError('the values of a RealPred must not contain spaces')
        return super().__new__(cls, lemma, pos, sense)

    def __str__(self):
        """
        Return a string, with leading underscore
        """
        if self.sense:
            return "_{}_{}_{}".format(*self)
        else:
            return "_{}_{}".format(*self)

    def __repr__(self):
        """
        Return a string, as "RealPred(lemma, pos, sense)"
        """
        if self.sense:
            return "RealPred({}, {}, {})".format(*(repr(x) for x in self))
        else:
            return "RealPred({}, {})".format(*(repr(x) for x in self))

    def __hash__(self):
        return super().__hash__()

    def __eq__(self, other):
        """
        Checks pred equality
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return isinstance(other, RealPred) and super().__eq__(other)

    def __ne__(self, other):
        """
        Checks pred inequality
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return not isinstance(other, RealPred) or super().__ne__(other)

    def __le__(self, other):
        """
        Checks pred leq comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        if not isinstance(other, RealPred):
            return False
        if self.sense is None:
            return self[:2] <= other[:2]
        if other.sense is None:
            return self[:2] < other[:2]
        return super().__le__(other)

    def __lt__(self, other):
        """
        Checks pred lt comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        if not isinstance(other, RealPred):
            return False
        if other.sense is None:
            return self[:2] < other[:2]
        if self.sense is None:
            return self[:2] <= other[:2]
        return super().__lt__(other)

    def __ge__(self, other):
        """
        Checks pred geq comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        if not isinstance(other, RealPred):
            return True
        if other.sense is None:
            return self[:2] >= other[:2]
        if self.sense is None:
            return self[:2] > other[:2]
        return super().__ge__(other)

    def __gt__(self, other):
        """
        Checks pred gt comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        if not isinstance(other, RealPred):
            return True
        if self.sense is None:
            return self[:2] > other[:2]
        if other.sense is None:
            return self[:2] >= other[:2]
        return super().__gt__(other)

    def is_more_specific(self, other, hierarchy=None):
        """
        Checks whether this object is a more specific pred than the other
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        if hierarchy is not None and str(self) in hierarchy.get(str(other), ()):
            return True
        elif type(other) is Pred:
            return True
        elif not isinstance(other, RealPred):
            return False
        result = False
        if self.lemma != '?' and other.lemma == '?':
            result = True
        elif self.lemma != other.lemma:
            return False
        if self.pos not in ('u', '?') and other.pos in ('u', '?'):
            result = True
        elif self.pos != other.pos:
            return False
        if other.sense == '?':
            result = True
        elif self.sense != other.sense:
            return False
        return result

    def is_less_specific(self, other, hierarchy=None):
        """
        Checks whether this object is a less specific pred than the other
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        if hierarchy is not None and str(other) in hierarchy.get(str(self), ()):
            return True
        elif not isinstance(other, RealPred):
            return False
        result = False
        if self.lemma == '?' and other.lemma != '?':
            result = True
        elif self.lemma != other.lemma:
            return False
        if self.pos in ('u', '?') and other.pos not in ('u', '?'):
            result = True
        elif self.pos != other.pos:
            return False
        if self.sense == '?':
            result = True
        elif self.sense != other.sense:
            return False
        return result

    @staticmethod
    def from_normalised_string(string):
        """
        Create a new instance from a normalised string.
        :param string: Input string
        :return: RealPred object
        """
        # Require initial underscore
        if string[0] != '_':
            raise PydmrsValueError("RealPred strings must begin with an underscore")
        # Split into 2 or 3 parts
        # This allows the lemma to contain underscores, which sometimes happens in the ERG
        parts = string[1:].rsplit('_', 2)
        # Require at least 2 parts
        if len(parts) < 2:
            raise PydmrsValueError(
                "RealPred strings must have a part of speech separated by an underscore")
        return RealPred(*parts) class GPred(namedtuple('GPredNamedTuple', ('name')), Pred):
    """
    Grammar predicate, with a rel name.
    The name can be underspecified by using '?'.
    """

    __slots__ = ()  # Suppress __dict__

    def __new__(cls, name):
        """
        Create a new instance, requiring non-empty name
        """
        if not name:
            raise PydmrsValueError('a GPred must have non-empty name')
        return super().__new__(cls, name)

    def __str__(self):
        """
        Return a string
        """
        return str(self.name)

    def __repr__(self):
        """
        Return a string, as "GPred(name)"
        """
        return "GPred({})".format(repr(self.name))

    def __hash__(self):
        return super().__hash__()

    def __eq__(self, other):
        """
        Checks pred equality
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return isinstance(other, GPred) and super().__eq__(other)

    def __ne__(self, other):
        """
        Checks pred inequality
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return not isinstance(other, GPred) or super().__ne__(other)

    def __le__(self, other):
        """
        Checks pred leq comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return isinstance(other, RealPred) or (isinstance(other, GPred) and super().__le__(other))

    def __lt__(self, other):
        """
        Checks pred lt comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return isinstance(other, RealPred) or (isinstance(other, GPred) and super().__lt__(other))

    def __ge__(self, other):
        """
        Checks pred geq comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return isinstance(other, Pred) or (isinstance(other, GPred) and super().__ge__(other))

    def __gt__(self, other):
        """
        Checks pred gt comparison (Pred < GPred < RealPred)
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        return isinstance(other, Pred) or (isinstance(other, GPred) and super().__gt__(other))

    def is_more_specific(self, other, hierarchy=None):
        """
        Checks whether this object is a more specific pred than the other
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        if hierarchy is not None and str(self) in hierarchy.get(str(other), ()):
            return True
        return type(other) is Pred or (isinstance(other, GPred) and (self.name != '?' and other.name == '?'))

    def is_less_specific(self, other, hierarchy=None):
        """
        Checks whether this object is a less specific pred than the other
        """
        if not isinstance(other, Pred):
            raise PydmrsTypeError()
        if hierarchy is not None and str(other) in hierarchy.get(str(self), ()):
            return True
        return isinstance(other, GPred) and (self.name == '?' and other.name != '?')

    @staticmethod
    def from_normalised_string(string):
        """
        Create a new instance from a normalised string.
        """
        if string[0] == '_':
            raise PydmrsValueError("GPred strings must not begin with an underscore")
        else:
            return GPred(string) class Sortinfo(MutableMapping, metaclass=SortinfoMeta):
    """
    A superclass for all Sortinfo classes.
    Instances of Sortinfo denote completely underspecified sortinfo.
    Subclasses of Sortinfo must specify __slots__ (and optionally, cvarsort)
    """
    __slots__ = ()
    cvarsort = 'i'

    # Container methods

    def __iter__(self):
        """
        Iterate through all features, including 'cvarsort'
        """
        return chain(('cvarsort',), iter(self.features))

    def __len__(self):
        """
        Return the number of features, including 'cvarsort'
        """
        return 1 + len(self.features)

    def __contains__(self, feature):
        """
        Check if a feature is present in the class
        """
        return feature == 'cvarsort' or feature in self.features

    def is_specified(self, feature):
        """
        Returns True if value of feature is not '?' or 'u'
        """
        return feature == 'cvarsort' or (feature in self.features and self[feature] not in ('u', '?', None))

    # For convenience, we can also get features which are not None

    def iter_specified(self):
        """
        Return (feature, value) pairs where value is specified and not '?' or 'u'
        """
        for feat in self.features:
            if hasattr(self, feat):
                val = self[feat]
                if val != 'u' and val != '?' and val is not None:
                    yield feat, val

    # Setters and getters
    # Allows both attribute and dictionary access
    # Features and values must all be lowercase

    def __getattribute__(self, feature):
        try:
            return super().__getattribute__(feature)
        except AttributeError:
            if feature in self.features:
                return None
            else:
                raise

    def __setattr__(self, feature, value):
        """
        Set the value of a feature, converting it to lowercase unless it's None
        """
        feature = feature.lower()
        if value is not None:
            value = value.lower()
        super().__setattr__(feature, value)

    def __delattr__(self, feature):
        """
        Set the value of a feature to None
        """
        setattr(self, feature, None)

    def __setitem__(self, feature, value):
        """
        Set items as attributes
        """
        setattr(self, feature, value)

    def __getitem__(self, feature):
        """
        Get the value of a feature, including 'cvarsort'
        """
        feature = feature.lower()
        if feature == 'cvarsort':
            return self.cvarsort
        elif hasattr(self, feature):
            return getattr(self, feature)
        elif feature in self.features:
            return None
        else:
            raise PydmrsKeyError("{} has no feature {}".format(type(self), feature))

    def __delitem__(self, feature):
        """
        Set the value of a feature to None
        """
        self[feature] = None

    # Initialisation

    def __init__(self, *args, **kwargs):
        """
        Initialise values of features, from positional or keyword arguments
        If a feature is not given, its value is set to None
        """
        if len(args) > len(self.features):
            raise PydmrsTypeError(
                "{} takes {} arguments, but {} were given".format(type(self).__name__,
                                                                  len(self.features),
                                                                  len(args)))
        for i, value in enumerate(args):
            setattr(self, self.features[i], value)
        for feature, value in kwargs.items():
            setattr(self, feature, value)

    # Conversion to strings and dicts

    def __str__(self):
        """
        Returns a string of the form:
        cvarsort[feature1=value1, feature2=value2, ...]
        """
        spec_feats = ', '.join('{}={}'.format(feat, self[feat]) for feat in self.features if self[feat] is not None)
        if spec_feats:
            return '{}[{}]'.format(self.cvarsort, spec_feats)
        else:
            return self.cvarsort

    def __repr__(self):
        """
        Return a string that can be evaluated
        """
        return '{}({})'.format(type(self).__name__, ', '.join(repr(self[feat]) for feat in self.features if hasattr(self, feat)))

    def as_dict(self):
        """
        Return a dict mapping from features to values, including 'cvarsort'
        """
        return dict(self.items())

    # Conversion from strings and dicts

    @classmethod
    def from_dict(cls, dictionary, **kwargs):
        """
        Instantiates a Sortinfo object from dictionary,
        normalising as necessary
        """
        normalised = cls.normalise_dict(dictionary, **kwargs)
        return cls.from_normalised_dict(normalised)

    @staticmethod
    def normalise_dict(dictionary, convert_plus_minus=True, convert_legacy_prontype=True):
        """
        Normalise a sortinfo dictionary - convert keys to lowercase and correct cvarsort if necessary
        """
        # Convert all keys to lowercase (so that we can check if certain keys exist)
        # Values are left untouched until the object is constructed (e.g. in case of None)
        dictionary = {key.lower(): value for key, value in dictionary.items()}
        # Find the cvarsort
        try:
            dictionary['cvarsort'] = dictionary['cvarsort'].lower()
        except KeyError:
            raise PydmrsValueError('Sortinfo must have cvarsort')
        # Correct cvarsort
        # 'p' is underspecified for 'h' or 'x'
        if dictionary['cvarsort'] == 'p':
            dictionary['cvarsort'] = 'x'
        # Look for features that are evidence for 'x' or 'e'
        elif dictionary['cvarsort'] not in 'ex' and len(dictionary) > 1:
            if any(key in dictionary for key in EventSortinfo.features):  # event evidence
                dictionary['cvarsort'] = 'e'
            elif any(key in dictionary for key in InstanceSortinfo.features) \
                 or 'prontype' in dictionary:  # instance evidence
                dictionary['cvarsort'] = 'x'
        
        if convert_plus_minus:
            for key, value in dictionary.items():
                if value == 'plus':
                    dictionary[key] = '+'
                if value == 'minus':
                    dictionary[key] = '-'
        
        if convert_legacy_prontype and 'prontype' in dictionary:
            pt = dictionary.pop('prontype')
            dictionary['pt'] = LegacyInstanceSortinfo.prontype_to_pt.get(pt, pt)
        
        return dictionary

    # In subclasses, _from_normalised_dict will override from_normalised_dict
    # See SortinfoMeta for details
    @staticmethod
    def from_normalised_dict(dictionary):
        """
        Instantiate a suitable type of Sortinfo from a dictionary,
        mapping from features to values (including cvarsort)
        """
        cvarsort = dictionary['cvarsort']
        # Instantiate an appropriate type of Sortinfo
        if cvarsort == 'e':
            return EventSortinfo.from_normalised_dict(dictionary)
        elif cvarsort == 'x':
            if 'prontype' in dictionary:
                return LegacyInstanceSortinfo.from_normalised_dict(dictionary)
            else:
                return InstanceSortinfo.from_normalised_dict(dictionary)
        else:
            return Sortinfo()

    @classmethod
    def _from_normalised_dict(cls, dictionary):
        """
        Instantiate from a dictionary mapping features to values
        """
        if 'cvarsort' in dictionary and dictionary['cvarsort'] != cls.cvarsort:
            raise PydmrsValueError('{} must have cvarsort {}, not {}'.format(cls.__name__,
                                                                             cls.cvarsort,
                                                                             dictionary['cvarsort']))
        return cls(**{key: value for key, value in dictionary.items() if key != 'cvarsort'})

    @classmethod
    def from_string(cls, string, **kwargs):
        """
        Instantiate from a string of the form:
        cvarsort[feature1=value1, feature2=value2, ...]
        """
        # Force lowercase
        string = string.lower()
        # Dictionary mapping from features to values
        dictionary = {'cvarsort': string[0]}
        if len(string) > 1:
            if not (string[1] == '[' and string[-1] == ']'):
                raise PydmrsValueError('Sortinfo string must include features in square brackets')
            for item in string[2:-1].split(','):
                key, value = item.split('=')
                dictionary[key.strip()] = value.strip()
        # Convert the dictionary
        return cls.from_dict(dictionary, **kwargs)

    # Comparison methods

    def __eq__(self, other):
        """
        Checks two Sortinfos for equality.
        Returns True if all specified features are the same.
        """
        return isinstance(other, Sortinfo) and self.cvarsort == other.cvarsort \
               and set(self.iter_specified()) == set(other.iter_specified())

    def __ne__(self, other):
        return not self == other

    def is_more_specific(self, other):
        """
        Checks whether this object is a more specific sortinfo than the other
        (underspecified value: '?' or 'u')
        """
        if not isinstance(other, Sortinfo):
            raise PydmrsTypeError()
        if other.cvarsort == 'i':
            return self.cvarsort != 'i'
        if self.cvarsort != other.cvarsort:
            return False
        for key, value in other.iter_specified():
            if not self.is_specified(key):
                return False
            elif value != self[key]:
                if key == 'tense' and value == 'tensed' and self[key] != 'untensed':
                    continue
                else:
                    return False
        only_this_specified = set(other.iter_specified()).difference(other.iter_specified())
        if not only_this_specified:
            return False
        return True

    def is_less_specific(self, other):
        """
        Checks whether this object is a less specific sortinfo than the other
        (underspecified value: '?' or 'u')
        """
        if not isinstance(other, Sortinfo):
            raise PydmrsTypeError()
        if self.cvarsort == 'i':
            return other.cvarsort != 'i'
        if self.cvarsort != other.cvarsort:
            return False
        for key, value in self.iter_specified():
            if not other.is_specified(key):
                return False
            elif value != other[key]:
                if key == 'tense' and value == 'tensed' and other[key] != 'untensed':
                    continue
                else:
                    return False
        only_other_specified = set(other.iter_specified()).difference(self.iter_specified())
        if not only_other_specified:
            return False
        return True class EventSortinfo(Sortinfo):
    """
    Event sortinfo
    """
    cvarsort = 'e'
    __slots__ = ('sf', 'tense', 'mood', 'perf', 'prog')
    # Sentence force, tense, mood, perfect, progressive class InstanceSortinfo(Sortinfo):
    """
    Instance sortinfo
    """
    cvarsort = 'x'
    __slots__ = ('pers', 'num', 'gend', 'ind', 'pt')
    # Person, number, gender, individuated, pronoun type
    
    def convert_to_legacy(self):
        new = LegacyInstanceSortinfo(*(self[x] for x in self.features))
        # Convert prontype value if there is a conversion (else leave the same)
        new.prontype = LegacyInstanceSortinfo.pt_to_prontype.get(new.prontype, new.prontype)
        return new class Link(namedtuple('LinkNamedTuple', ('start', 'end', 'rargname', 'post'))):
    """
    A link
    """

    __slots__ = ()  # Suppress __dict__

    def __new__(cls, start, end, rargname, post):
        """
        Create a new instance, forcing strings to be uppercase
        """
        if isinstance(rargname, str):
            rargname = rargname.upper()
        if isinstance(post, str):
            post = post.upper()
        if start == end:
            warn("Link start must not equal link end.", PydmrsWarning)
        # TODO: Pydelphin uses MOD/EQ for undirected links - make compatible.
        if rargname in ('', 'NONE', 'NULL', 'NIL'):
            rargname = None
        if post in ('', 'NONE', 'NULL', 'NIL'):
            post = None
        return super().__new__(cls, start, end, rargname, post)

    def __str__(self):
        return "({} - {}/{} -> {})".format(self.start, self.rargname, self.post, self.end)

    def __repr__(self):
        return "Link({}, {}, {}, {})".format(*(repr(x) for x in self))

    @property
    def label(self):
        return LinkLabel(self.rargname, self.post)

    @property
    def labelstring(self):
        return "{}/{}".format(self.rargname, self.post)

    def to_xml(self):
        xlink = ET.Element('link')
        xlink.set('from', str(self.start))
        xlink.set('to', str(self.end))
        xrargname = ET.SubElement(xlink, 'rargname')
        xrargname.text = self.rargname
        xpost = ET.SubElement(xlink, 'post')
        xpost.text = self.post
        return xlink

    @classmethod
    def from_xml(cls, elem):
        start = int(elem.get('from'))
        end = int(elem.get('to'))
        rargname = None
        post = None
        for sub in elem:
            if sub.tag == 'rargname':
                if sub.text != 'MOD':
                    rargname = sub.text
            elif sub.tag == 'post':
                post = sub.text
            else:
                raise PydmrsValueError(sub.tag)
        return Link(start, end, rargname, post)
 class Node(object):
    """
    A DMRS node
    """

    def __init__(self, nodeid=None, pred=None, sortinfo=None, cfrom=None, cto=None, surface=None, base=None, carg=None):
        self.nodeid = nodeid
        self.surface = surface
        self.base = base

        if cto and cfrom and cto < cfrom:
            raise PydmrsValueError('Incorrect span: cto < cfrom.')
        self.cfrom = cfrom
        self.cto = cto

        if isinstance(pred, str):
            self.pred = Pred.from_string(pred)
        else:
            self.pred = pred

        if carg and carg[0] == '"' and carg[-1] == '"':
            carg = carg[1:-1]
        if carg and '"' in carg:
            raise PydmrsValueError('Cargs must not contain quotes.')
        self.carg = carg

        if not sortinfo:  # Allow no sortinfo
            self.sortinfo = None
        elif isinstance(sortinfo, Sortinfo):  # Allow Sortinfo instances
            self.sortinfo = sortinfo
        elif isinstance(sortinfo, dict):  # Allow initialising sortinfo from a dict
            self.sortinfo = Sortinfo.from_dict(sortinfo)
        elif isinstance(sortinfo, list):  # Allow initialising sortinfo from (key,value) pairs
            self.sortinfo = Sortinfo.from_dict({x: y for x, y in sortinfo})
        else:
            raise PydmrsTypeError("unsupported type for sortinfo")

    def __str__(self):
        string = str(self.pred)
        if self.carg:
            string += '({})'.format(self.carg)
        if self.sortinfo:
            string += ' {}'.format(self.sortinfo)
        return string

    def __eq__(self, other):
        """
        Checks two nodes for equality (predicate, carg, sortinfo)
        """
        return isinstance(other, Node) \
            and self.pred == other.pred \
            and self.carg == other.carg \
            and self.sortinfo == other.sortinfo

    def is_more_specific(self, other, hierarchy=None):
        """
        Checks whether this object is a more specific node than the other (predicate, carg, sortinfo)
        """
        if not isinstance(other, Node):
            raise PydmrsTypeError()
        result = False
        if other.pred is not None and \
            ((self.pred is None and type(other.pred) == Pred) or
             (self.pred is not None and self.pred.is_more_specific(other.pred, hierarchy=hierarchy))):
            result = True
        elif (self.pred is None) != (other.pred is None) or self.pred != other.pred:
            return False
        if self.carg != '?' and other.carg == '?':
            result = True
        elif self.carg != other.carg:
            return False
        if other.sortinfo is not None and \
            ((self.sortinfo is None and type(other.sortinfo) == Sortinfo) or
             self.sortinfo is not None and self.sortinfo.is_more_specific(other.sortinfo)):
            result = True
        elif (self.sortinfo is None) != (other.sortinfo is None) or self.sortinfo != other.sortinfo:
            return False
        return result

    def is_less_specific(self, other, hierarchy=None):
        """
        Checks whether this object is a less specific node than the other (predicate, carg, sortinfo)
        """
        if not isinstance(other, Node):
            raise PydmrsTypeError()
        result = False
        if self.pred is not None and \
            ((other.pred is None and type(self.pred) == Pred) or
             (other.pred is not None and self.pred.is_less_specific(other.pred, hierarchy=hierarchy))):
            result = True
        elif (self.pred is None) != (other.pred is None) or self.pred != other.pred:
            return False
        if self.carg == '?' and other.carg != '?':
            result = True
        elif self.carg != other.carg:
            return False
        if self.sortinfo is not None and \
            ((other.sortinfo is None and type(self.sortinfo) == Sortinfo) or
             other.sortinfo is not None and self.sortinfo.is_less_specific(other.sortinfo)):
            result = True
        elif (self.sortinfo is None) != (other.sortinfo is None) or self.sortinfo != other.sortinfo:
            return False
        return result

    @property
    def span(self):
        return self.cfrom, self.cto

    @property
    def is_gpred_node(self):
        return isinstance(self.pred, GPred)

    @property
    def is_realpred_node(self):
        return isinstance(self.pred, RealPred)

    def convert_to(self, cls):
        return cls(self.nodeid,
                   self.pred,
                   self.sortinfo,
                   self.cfrom,
                   self.cto,
                   self.surface,
                   self.base,
                   self.carg)

    def to_xml(self):
        xnode = ET.Element('node')
        xnode.set('nodeid', str(self.nodeid))
        if self.cfrom is not None and self.cto is not None:
            xnode.set('cfrom', str(self.cfrom))
            xnode.set('cto', str(self.cto))
        if self.carg:
            xnode.set('carg', '{}'.format(self.carg))
        if isinstance(self.pred, GPred):
            xpred = ET.SubElement(xnode, 'gpred')
            xpred.text = str(self.pred) + '_rel'
        elif isinstance(self.pred, RealPred):
            xpred = ET.SubElement(xnode, 'realpred')
            xpred.set('lemma', self.pred.lemma)
            xpred.set('pos', self.pred.pos)
            if self.pred.sense:
                xpred.set('sense', self.pred.sense)
        else:
            raise PydmrsTypeError("predicates must be RealPred or GPred objects")
        xsortinfo = ET.SubElement(xnode, 'sortinfo')
        if self.sortinfo:
            for key in self.sortinfo:
                value = self.sortinfo[key]
                if value:
                    xsortinfo.set(key, value)
        return xnode

    @classmethod
    def from_xml(cls, elem, convert_legacy_prontype=True):
        nodeid = int(elem.get('nodeid')) if 'nodeid' in elem.attrib else None
        cfrom = int(elem.get('cfrom')) if 'cfrom' in elem.attrib else None
        cto = int(elem.get('cto')) if 'cto' in elem.attrib else None
        surface = elem.get('surface')
        base = elem.get('base')
        carg = elem.get('carg')

        pred = None  # Default value
        sortinfo = None  # Default value
        for sub in elem:
            if sub.tag == 'realpred':
                try:
                    pred = RealPred(sub.get('lemma').lower(), sub.get('pos'), sub.get('sense'))
                except PydmrsValueError:
                    # If the whole pred name is under 'lemma', rather than split between 'lemma', 'pos', 'sense'
                    pred = RealPred.from_string(sub.get('lemma'))
                    warn("RealPred given as string rather than lemma, pos, sense", PydmrsWarning)
            elif sub.tag == 'gpred':
                try:
                    pred = GPred.from_string(sub.text)
                except PydmrsValueError:
                    # If the string is actually for a RealPred, not a GPred
                    pred = RealPred.from_string(sub.text)
                    warn("RealPred string found in a <gpred> tag", PydmrsWarning)
            elif sub.tag == 'sortinfo':
                if sub.attrib:  # If sub.attrib is empty, leave sortinfo as None
                    sortinfo = Sortinfo.from_dict(sub.attrib,
                                                  convert_legacy_prontype=convert_legacy_prontype)
            else:
                raise PydmrsValueError(sub.tag)
        return cls(nodeid=nodeid, pred=pred, carg=carg, sortinfo=sortinfo, cfrom=cfrom, cto=cto,
                   surface=surface,
                   base=base)
 class ListDmrs(Dmrs):
    """
    A DMRS graph implemented with lists for nodes and links
    """

    def __init__(self, *args, **kwargs):
        """
        Initialise the graph
        """
        self.nodes = []
        self.links = []
        super().__init__(*args, **kwargs)

    def __getitem__(self, nodeid):
        """
        Allow accessing nodes as self[nodeid]
        """
        for n in self.nodes:
            if n.nodeid == nodeid:
                return n
        raise KeyError(nodeid)

    def __iter__(self):
        """
        Allow iterating over nodeids using 'in'
        """
        for n in self.nodes:
            yield n.nodeid

    def __len__(self):
        """
        Return the number of nodes in the graph
        """
        return self.nodes.__len__()

    def count_links(self):
        """
        Return the number of links in the graph
        """
        return self.links.__len__()

    def iter_nodes(self):
        return self.nodes.__iter__()

    def iter_links(self):
        return self.links.__iter__()

    def add_link(self, link):
        """Add a link"""
        self.links.append(link)

    def add_links(self, iterable):
        """Add a number of links"""
        self.links.extend(iterable)

    def remove_link(self, link):
        """Remove a link"""
        if len(link) == 2:
            for n, link in enumerate(self.links):
                if link.start == link[0] and link.end == link[1]:
                    break
            self.links.pop(n)
        else:
            self.links.remove(link)

    def add_node(self, node):
        """Add a node"""
        assert node.nodeid not in self
        assert isinstance(node, self.Node)
        if node.nodeid is None:
            node.nodeid = self.free_nodeid()
        self.nodes.append(node)
        return node.nodeid

    def remove_node(self, nodeid):
        """
        Remove a node and all associated links
        """
        # Remove node:
        for i, node in enumerate(self.nodes):
            if node.nodeid == nodeid:
                self.nodes.pop(i)
                break

        else:  # if nodeid never found
            raise KeyError(nodeid)

        # Remove links:
        remove = []
        for i, link in enumerate(self.links):
            if link.start == nodeid or link.end == nodeid:
                remove.append(i)

        for i in reversed(remove):
            self.links.pop(i)

        # Check if the node was top or index
        if self.top and self.top.nodeid == nodeid:
            self.top = None

        if self.index and self.index.nodeid == nodeid:
            self.index = None

    def renumber_node(self, old_id, new_id):
        """
        Change a node's ID from old_id to new_id
        """
        assert new_id not in self
        self[old_id].nodeid = new_id

        for i, link in enumerate(self.links):
            start, end, rargname, post = link
            if start == old_id:
                self.links[i] = Link(new_id, end, rargname, post)
            elif end == old_id:
                self.links[i] = Link(start, new_id, rargname, post)

    def sort(self):
        """
        Sort the lists of nodes and links by nodeids
        """
        self.nodes.sort(key=attrgetter('nodeid'))
        self.links.sort()
 class AnchorNode(Node):
    """
    A DMRS graph node with an additional anchor id to identify anchor nodes for DMRS mapping.
    """

    def __init__(self, anchors, *args, **kwargs):
        """
        Create a new anchor node instance.
        """
        super().__init__(*args, **kwargs)
        self.anchors = anchors
        self.required = True
        self.requires_target = True

    def before_map(self, dmrs, nodeid):
        """
        Is applied before the target node is mapped.
        :param dmrs Target DMRS graph.
        :param nodeid Target node id.
        """
        pass

    def after_map(self, dmrs, nodeid):
        """
        Is applied after the target node is mapped.
        :param dmrs Target DMRS graph.
        :param nodeid Target node id.
        """
        pass

    def map(self, dmrs, nodeid, hierarchy=None):
        """
        Overrides the values of the target node if they are not underspecified in this anchor node.
        :param dmrs Target DMRS graph.
        :param nodeid Target node id.
        :param hierarchy: An optional predicate hierarchy.
        """
        node = dmrs[nodeid]
        if self == node or self.is_less_specific(node, hierarchy=hierarchy):
            return
        if isinstance(self.pred, RealPred):
            if isinstance(node.pred, RealPred):
                node.pred = RealPred(node.pred.lemma if self.pred.lemma == '?' else self.pred.lemma, node.pred.pos if self.pred.pos in ('u', '?') else self.pred.pos, node.pred.sense if self.pred.sense in ('unknown', '?') else self.pred.sense)
            else:
                node.pred = copy.deepcopy(self.pred)
        elif isinstance(self.pred, GPred):
            if isinstance(node.pred, GPred):
                node.pred = GPred(node.pred.name if self.pred.name == '?' else self.pred.name)
            else:
                node.pred = copy.deepcopy(self.pred)
        elif not isinstance(self.pred, Pred):
            node.pred = None
        if isinstance(self.sortinfo, EventSortinfo):
            if isinstance(node.sortinfo, EventSortinfo):
                node.sortinfo = EventSortinfo(node.sortinfo.sf if self.sortinfo.sf in ('u', '?') else self.sortinfo.sf, node.sortinfo.tense if self.sortinfo.tense in ('u', '?') else self.sortinfo.tense, node.sortinfo.mood if self.sortinfo.mood in ('u', '?') else self.sortinfo.mood, node.sortinfo.perf if self.sortinfo.perf in ('u', '?') else self.sortinfo.perf, node.sortinfo.prog if self.sortinfo.prog in ('u', '?') else self.sortinfo.prog)
            else:
                node.sortinfo = copy.deepcopy(self.sortinfo)
        elif isinstance(self.sortinfo, InstanceSortinfo):
            if isinstance(node.sortinfo, InstanceSortinfo):
                node.sortinfo = InstanceSortinfo(node.sortinfo.pers if self.sortinfo.pers in ('u', '?') else self.sortinfo.pers, node.sortinfo.num if self.sortinfo.num in ('u', '?') else self.sortinfo.num, node.sortinfo.gend if self.sortinfo.gend in ('u', '?') else self.sortinfo.gend, node.sortinfo.ind if self.sortinfo.ind in ('u', '?') else self.sortinfo.ind, node.sortinfo.pt if self.sortinfo.pt in ('u', '?') else self.sortinfo.pt)
            else:
                node.sortinfo = copy.deepcopy(self.sortinfo)
        elif not isinstance(self.sortinfo, Sortinfo):
            node.sortinfo = None
        if self.carg != '?':
            node.carg = self.carg

    def unify(self, other, hierarchy=None):
        """
        Unify nodes.
        :param other: The node to unify with.
        :param hierarchy: An optional predicate hierarchy.
        """
        hierarchy = hierarchy or dict()
        if (
            type(self.pred) is RealPred and
            type(other.pred) is RealPred and
            (self.pred.lemma == other.pred.lemma or self.pred.lemma == '?' or other.pred.lemma == '?') and
            (self.pred.pos == other.pred.pos or self.pred.pos in ('u', '?') or other.pred.pos in ('u', '?')) and
            (self.pred.sense == other.pred.sense or self.pred.sense in ('unknown', '?') or other.pred.sense in ('unknown', '?'))
        ):
            # RealPred and predicate values are either equal or underspecified
            lemma = other.pred.lemma if self.pred.lemma == '?' else self.pred.lemma
            pos = other.pred.pos if self.pred.pos in ('u', '?') else self.pred.pos
            sense = other.pred.sense if self.pred.sense in ('unknown', '?') else self.pred.sense
            self.pred = RealPred(lemma, pos, sense)
        elif (
            type(self.pred) is GPred and
            type(other.pred) is GPred and
            (self.pred.name == other.pred.name or self.pred.name == '?' or other.pred.name == '?')
        ):
            # GPred and predicate values are either equal or underspecified
            name = other.pred.name if self.pred.name == '?' else self.pred.name
            self.pred = GPred(name)
        elif type(self.pred) is Pred or str(other.pred) in hierarchy.get(str(self.pred), ()):
            # predicate is underspecified, or predicate is more general according to the hierarchy
            self.pred = other.pred
        elif type(other.pred) is Pred or str(self.pred) in hierarchy.get(str(other.pred), ()):
            # other is underspecified, or predicate is more specific according to the hierarchy
            pass
        else:
            raise PydmrsError("Node predicates cannot be unified: {}, {}".format(self.pred, other.pred))

        if type(self.sortinfo) is not Sortinfo and isinstance(other.sortinfo, type(self.sortinfo)) and all((self.sortinfo[key] == other.sortinfo[key]) or (self.sortinfo[key] in ('u', '?')) or (other.sortinfo[key] in ('u', '?')) for key in self.sortinfo.features):
            # same sortinfo type and values are either equal or underspecified
            self.sortinfo = type(self.sortinfo)(*(other.sortinfo[key] if self.sortinfo[key] in ('u', '?') else self.sortinfo[key] for key in self.sortinfo.features))
        elif type(self.sortinfo) is Sortinfo and isinstance(other.sortinfo, Sortinfo):
            # sortinfo is underspecified
            self.sortinfo = other.sortinfo
        elif type(other.sortinfo) is Sortinfo and isinstance(self.sortinfo, Sortinfo):
            # other is underspecified
            pass
        elif self.sortinfo is None and other.sortinfo is None:
            pass
        else:
            raise PydmrsError("Node sortinfos cannot be unified: {}, {}".format(self.sortinfo, other.sortinfo))

        if self.carg == other.carg or other.carg == '?':
            # same carg, or other is underspecified
            pass
        elif self.carg == '?':
            # carg is underspecified
            self.carg = other.carg
        else:
            raise PydmrsError("Node cargs cannot be unified: {}, {}".format(self.carg, other.carg)) class OptionalNode(AnchorNode):
    """
    A DMRS anchor node which is not required.
    """

    def __init__(self, *args, **kwargs):
        """
        Create a new optional node instance.
        """
        super().__init__(*args, **kwargs)
        self.required = False
        self.requires_target = False class SubgraphNode(AnchorNode):
    """
    A DMRS anchor node which comprises the subgraph attached to it.
    The attached subgraph consists of the nodes which are connected only via this node to the top node of the graph, and would be disconnected if the subgraph node was removed.
    """

    def __init__(self, *args, **kwargs):
        """
        Create a new subgraph node instance.
        """
        super().__init__(*args, **kwargs)
        self.requires_target = False

    def before_map(self, dmrs, nodeid):
        """
        Removes the subgraph attached to the target node.
        :param dmrs Target DMRS graph (requires the top node specified).
        :param nodeid Target node id.
        """
        assert dmrs.top is not None, 'Top node has to be specified for subgraph node to map.'
        node = dmrs[nodeid]
        dmrs.remove_node(nodeid)
        dmrs.remove_nodes(dmrs.disconnected_nodeids())
        dmrs.add_node(node)
from pydmrs.components import Pred, RealPred, GPred, Sortinfo, EventSortinfo, InstanceSortinfo
from pydmrs.core import Link, Node, ListDmrs
from pydmrs.mapping.mapping import AnchorNode, OptionalNode, SubgraphNode
    import sys


default_sortinfo_classes = dict(
    e=EventSortinfo,
    x=InstanceSortinfo
)

default_sortinfo_shortforms = dict(
    e=dict(
        sf={'p': 'prop', 'q': 'ques', 'o': 'prop-or-ques', 'c': 'comm'},
        tense={'u': 'untensed', 't': 'tensed', 'p': 'pres', 'a': 'past', 'f': 'fut'},
        mood={'i': 'indicative', 's': 'subjunctive'},
        perf={'+': '+', '-': '-'},
        prog={'+': '+', '-': '-', 'b': 'bool'}
    ),
    x=dict(
        pers={'1': '1', '2': '2', '3': '3', 'o': '1-or-3'},
        num={'s': 'sg', 'p': 'pl'},
        gend={'f': 'f', 'm': 'm', 'n': 'n', 'o': 'm-or-f'},
        ind={'+': '+', '-': '-'},
        pt={'s': 'std', 'z': 'zero', 'r': 'refl'}
    )
)


def parse_graphlang(
    string,
    cls=ListDmrs,
    queries=None,
    equalities=None,
    anchors=None,
    sortinfo_classes=None,
    sortinfo_shortforms=None
):
    if queries is None:
        queries = {}
    if equalities is None:
        equalities = {}
    if anchors is None:
        anchors = {}
    if sortinfo_classes is None:
        sortinfo_classes = default_sortinfo_classes
        assert sortinfo_shortforms is None
        sortinfo_shortforms = default_sortinfo_shortforms
    else:
        if sortinfo_shortforms is None:
            sortinfo_shortforms = dict()
        else:
            assert all(cvarsort in sortinfo_classes for cvarsort in sortinfo_shortforms)
        assert 'i' not in sortinfo_classes

        sortinfo_classes['i'] = Sortinfo