# Source code for ufl_legacy.exprequals

    # -*- coding: utf-8 -*-

    from collections import defaultdict

    from ufl_legacy.core.expr import Expr
    from ufl_legacy.log import error

    hash_total = defaultdict(int)
    hash_collisions = defaultdict(int)
    hash_equals = defaultdict(int)
    hash_notequals = defaultdict(int)

    def print_collisions():

        keys = sorted(hash_total.keys(), key=lambda x: (hash_collisions[x], x))

        print("Collision statistics ({0} keys):".format(len(keys)))
        print("[key: equals; notequals; collisions]")
        n = max(len(str(k)) for k in keys)
        fmt = ("%%%ds" % n) + ": \t %6d (%3d%%); %6d (%3d%%); %6d (%3d%%) col; tot %d"
        for k in keys:
            co = hash_collisions[k]
            eq = hash_equals[k]
            ne = hash_notequals[k]
            tot = hash_total[k]
            sn, on = k
            # Skip those that are all not equal
            if sn != on and ne == tot:
                continue
            print(fmt % (k, eq, int(100.0 * eq / tot),
                         ne, int(100.0 * ne / tot),
                         co, int(100.0 * co / tot),
                         tot))

    def measure_collisions(equals_func):
        def equals_func_with_collision_measuring(self, other):
            # Call equals
            equal = equals_func(self, other)

            # Get properties
            st = type(self)
            ot = type(other)
            sn = st.__name__
            on = ot.__name__
            sh = hash(self)
            oh = hash(other)
            key = (sn, on)

            # If hashes are the same but objects are not equal, we have a
            # collision
            hash_total[key] += 1
            if sh == oh and not equal:
                hash_collisions[key] += 1
            elif sh != oh and equal:
                error("Equal objects must always have the same hash! Objects are:\n{0}\n{1}".format(self, other))
            elif sh == oh and equal:
                hash_equals[key] += 1
            elif sh != oh and not equal:
                hash_notequals[key] += 1

            return equal
        return equals_func_with_collision_measuring

    # @measure_collisions

    def recursive_expr_equals(self, other):  # Much faster than the more complex algorithms above!
        """Checks whether the two expressions are represented the
        exact same way. This does not check if the expressions are
        mathematically equal or equivalent! Used by sets and dicts."""

        # To handle expr == int/float
        if not isinstance(other, Expr):
            return False

        # Fast cutoff for common case
        if self._ufl_typecode_ != other._ufl_typecode_:
            return False

        # Compare hashes, will cutoff more or less all nonequal types
        if hash(self) != hash(other):
            return False

        # Large objects are costly to compare with themselves
        if self is other:
            return True

        # Terminals
        if self._ufl_is_terminal_:
            # Compare terminals with custom == to capture subclass
            # overloading of __eq__
            return self == other

        # --- Operators, most likely equal, below here is the costly part
        # --- if it recurses through a large tree! ---

        # Recurse manually to call expr_equals directly without the class
        # EQ overhead!
        equal = all(recursive_expr_equals(a, b) for (a, b) in zip(self.ufl_operands,
                                                                  other.ufl_operands))

        return equal

    # @measure_collisions

    def nonrecursive_expr_equals(self, other):
        """Checks whether the two expressions are represented the
        exact same way. This does not check if the expressions are
        mathematically equal or equivalent! Used by sets and dicts."""

        # Fast cutoffs for common cases, type difference or hash
        # difference will cutoff more or less all nonequal types
        if type(self) != type(other) or hash(self) != hash(other):
            return False

        # Large objects are costly to compare with themselves
        if self is other:
            return True

        # Modelled after pre_traversal to avoid recursion:
        left = [(self, other)]
        while left:
            s, o = left.pop()

            if s._ufl_is_terminal_:
                # Compare terminals
                if not s == o:
                    return False
            else:
                # Delve into subtrees
                so = s.ufl_operands
                oo = o.ufl_operands
                if len(so) != len(oo):
                    return False

                for s, o in zip(so, oo):
                    # Fast cutoff for common case
                    if s._ufl_typecode_ != o._ufl_typecode_:
                        return False
                    # Skip subtree if objects are the same
                    if s is o:
                        continue
                    # Append subtree for further inspection
                    left.append((s, o))

        # Equal if we get out of the above loop!
        # Eagerly DAGify to reduce the size of the tree.
        self.ufl_operands = other.ufl_operands
        return True

    # expr_equals = recursive_expr_equals
    expr_equals = nonrecursive_expr_equals