# Source code for algebraixlib.structure

r"""
The Structure of a MathObject
===============================

This module provides facilities to represent the structure of a MathObject. What we call
'structure' is a representation of the minimal :term:power set a given MathObject belongs to
(or should belong to) that can be expressed with the following elements.

The structural elements we use are:

-   CartesianProduct: The :term:ground set of a :class:~.Couplet is the :term:Cartesian
product of the ground sets of the :term:left and :term:right component.
-   PowerSet: The ground set of a :term:set is the :term:power set of the ground set of its
elements.
-   :class:~Union: The ground set of the elements of a :term:set is the :term:union of the
ground sets of the individual elements.

Depending on the type of structure, we use one or two genesis sets:

-   GenesisSetA: The :term:set A (:math:A) is the :term:set of all :class:~.Atom\s.
-   GenesisSetM: The term:set M (:math:M) is the ground set of all MathObject\s that can be
represented in a given system.

In addition to these, there is the structure of an empty set. It is represented by an instance of
Structure and is the only case that is represented by an instance of that class. It is a subset
of all other structures.

.. note:: The :term:set M (:math:M) is finite; essentially it is the set of all instances of
MathObject that fit into a given system. This also implies that there is a power set
:math:P(M) that is *not* an element of :math:M. (It follows that not *every* 'set of math
objects' is an element of :math:M.) Since :math:A \subset M, :math:A is of course also
finite.

Corresponding to the two genesis sets, we use two different forms to represent the structure of a
MathObject:

-   **Absolute structure**: An :term:absolute structure does not contain a reference to the set
:math:M.
-   **Relative structure**: A relative structure contains a reference to the set :math:M. Such
structures are typically used to compare absolute structures against them, to see whether a
given absolute structure fulfills a minimal structural criterion.

Example Code
============

.. code::

from algebraixlib.mathobjects import Set
from algebraixlib.structure import PowerSet, GenesisSetM
Set([1, 2]).get_ground_set()
# Output: PowerSet(GenesisSetA())
Set([1, 2]).get_ground_set().is_subset(PowerSet(GenesisSetM()))
# Output: True

API
===

"""

# Copyright Algebraix Data Corporation 2015 - 2017
#
# This file is part of algebraixlib <http://github.com/AlgebraixData/algebraixlib>.
#
# algebraixlib is free software: you can redistribute it and/or modify it under the terms of version
#
# algebraixlib is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without
# even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public License along with algebraixlib.
# --------------------------------------------------------------------------------------------------
import abc as _abc
import collections as _collections

import algebraixlib.util.miscellaneous as _misc

# --------------------------------------------------------------------------------------------------

[docs]class Structure(object):
"""Represent the :term:ground set of a MathObject in structural terms. An instance of this
class is the empty :term:set.

.. note:: This class serves a double purpose. On one hand it is the base class for all nodes in
the structure tree, and on the other hand it is the representative of the whole tree (where
the top level node of the tree of interest is typically a subclass of this class). This
is common practice and should not pose a problem, but it is probably helpful to be aware of
it.
"""
@_abc.abstractmethod
[docs]    def is_subset(self, other) -> bool:
"""Return True if self is a subset of other.

:param other: Must be an instance of Structure.
:return: Is always True for type Structure.
"""
assert isinstance(other, Structure)
return True

@_abc.abstractmethod
[docs]    def get_powerset_level(self, other) -> int:
"""Return the number of power set levels between self and other.

:param other: Must be an instance of Structure.
:return: An integer >= 0. Is always 0 for type Structure.
"""
assert isinstance(other, Structure)
return 0

@_abc.abstractmethod
[docs]    def is_same(self, other) -> bool:
"""Return True if self is structurally equivalent to other.

:param other: Must be an instance of Structure.
:return: True if self is structurally equivalent to other.
"""
assert isinstance(other, Structure)
return type(other) == Structure

# ----------------------------------------------------------------------------------------------

[docs]    def __eq__(self, other):
"""Map to is_same. Is called for the operator ==."""
return self.is_same(other)

[docs]    def __ne__(self, other):
"""Map to the negation of is_same. Is called for the operator !=."""
return not self.is_same(other)

[docs]    def __le__(self, other):
"""Map to is_subset. Is called for the operator <=."""
return self.is_subset(other)

@_abc.abstractmethod
[docs]    def __hash__(self):
"""Return a hash based on the member values. (It must match the implementation of is_same,
to which __eq__ redirects equality comparisons.)
"""
return hash(_misc.get_full_class_name(self))

@_abc.abstractmethod
[docs]    def __repr__(self):
"""Return the instance's code representation."""
return 'Structure()'

@_abc.abstractmethod
[docs]    def __str__(self):
"""Return the instance's string representation."""
return '{}'

[docs]class GenesisSetA(Structure):
r"""The set of all :term:atom\s. Is functionally a singleton."""

[docs]    def is_subset(self, other: Structure) -> bool:
"""Return True if self is a subset of other.

:param other: Must be an instance of Structure.
:return: True if self is a subset of other.
"""
assert isinstance(other, Structure)
return type(other) == GenesisSetA or type(other) == GenesisSetM

[docs]    def get_powerset_level(self, other: Structure) -> int:
"""Return the number of power set levels between self and other.

:param other: Must be an instance of Structure.
:return: An integer >= 0. Is always 0 for type GenesisSetA.
"""
assert isinstance(other, Structure)
return 0

[docs]    def is_same(self, other: Structure) -> bool:
"""Return True if self is structurally equivalent to other.

:param other: Must be an instance of Structure.
:return: True if self is structurally equivalent to other.
"""
assert isinstance(other, Structure)
return type(other) == GenesisSetA

# ----------------------------------------------------------------------------------------------

[docs]    def __hash__(self):
"""Return a hash based on the member values. (It must match the implementation of is_same,
to which Structure.__eq__ redirects equality comparisons.)
"""
return hash(_misc.get_full_class_name(self))

[docs]    def __repr__(self):
"""Return the instance's code representation."""
return 'GenesisSetA()'

[docs]    def __str__(self):
"""Return the instance's string representation."""
return 'A'

[docs]class GenesisSetM(Structure):
r"""The set of all instances of MathObject. Is functionally a singleton.

.. note:: The set :math:M being a superset of :math:A means that subset checking (especially
in :class:~Union) needs to 'know' about this relationship and take it into account.
Representing :math:M as :math:(A \cup A') (where :math:A' = M \setminus A) would make
this more straightforward, but would make the visible representation of :math:M (as union)
non-intuitive.
"""

[docs]    def is_subset(self, other: Structure) -> bool:
"""Return True if self is a subset of other.

:param other: Must be an instance of Structure.
:return: True if self is a subset of other.
"""
assert isinstance(other, Structure)
return type(other) == GenesisSetM

[docs]    def get_powerset_level(self, other):
"""Return the number of power set levels between self and other.

:param other: Must be an instance of Structure.
:return: An integer >= 0. Is always 0 for type GenesisSetM.
"""
assert isinstance(other, Structure)
return 0

[docs]    def is_same(self, other: Structure) -> bool:
"""Return True if self is structurally equivalent to other.

:param other: Must be an instance of Structure.
:return: True if self is structurally equivalent to other.
"""
assert isinstance(other, Structure)
return type(other) == GenesisSetM

# ----------------------------------------------------------------------------------------------

[docs]    def __hash__(self):
"""Return a hash based on the member values. (It must match the implementation of is_same,
to which Structure.__eq__ redirects equality comparisons.)
"""
return hash(_misc.get_full_class_name(self))

[docs]    def __repr__(self):
"""Return the instance's code representation."""
return 'GenesisSetM()'

[docs]    def __str__(self):
"""Return the instance's string representation."""
return 'M'

[docs]class GenesisSetN(Structure):
r"""The set of all integers. Is functionally a singleton."""

[docs]    def is_subset(self, other: Structure) -> bool:
"""Return True if self is a subset of other.

:param other: Must be an instance of Structure.
:return: True if self is a subset of other.
"""
assert isinstance(other, Structure)
return type(other) == GenesisSetN

[docs]    def get_powerset_level(self, other):
"""Return the number of power set levels between self and other.

:param other: Must be an instance of Structure.
:return: An integer >= 0. Is always 0 for type GenesisSetN.
"""
assert isinstance(other, Structure)
return 0

[docs]    def is_same(self, other: Structure) -> bool:
"""Return True if self is structurally equivalent to other.

:param other: Must be an instance of Structure.
:return: True if self is structurally equivalent to other.
"""
assert isinstance(other, Structure)
return type(other) == GenesisSetN

# ----------------------------------------------------------------------------------------------

[docs]    def __hash__(self):
"""Return a hash based on the member values. (It must match the implementation of is_same,
to which Structure.__eq__ redirects equality comparisons.)
"""
return hash(_misc.get_full_class_name(self))

[docs]    def __repr__(self):
"""Return the instance's code representation."""
return 'GenesisSetN()'

[docs]    def __str__(self):
"""Return the instance's string representation."""
return 'N'

[docs]class CartesianProduct(Structure):
"""Represent the :term:Cartesian product node of a structure."""

def __init__(self, left, right):
"""
:param left: The :term:ground set of the :term:left component of a :term:couplet. Must
be an instance of Structure.
:param right: The ground set of the :term:right component of a couplet. Must be an
instance of Structure.
"""
right_is_struct = isinstance(right, Structure)
right_not_struct = type(right) != Structure
assert right_is_struct and right_not_struct
self._left = left
self._right = right

@property
def left(self) -> Structure:
"""Read-only access to the :term:left structure."""
return self._left

@property
def right(self) -> Structure:
"""Read-only access to the :term:right structure."""
return self._right

[docs]    def is_subset(self, other: Structure) -> bool:
"""Return True if self is a subset of other.

In order for self to be a :term:subset of other, other must be:

-   A CartesianProduct and both left and right components must be subsets of left and
right components of other, or
-   A :class:~Union that contains an instance of CartesianProduct where both left and
right component are subsets of left and right components of other, or
-   GenesisSetM (everything in our system is a subset of :math:M).

:param other: Must be an instance of Structure.
:return: True if self is a :term:subset of other.
"""
assert isinstance(other, Structure)

def is_subset_of_cart_prod(cart_prod: CartesianProduct):
return (self.left <= cart_prod.left) and (self.right <= cart_prod.right)

if isinstance(other, GenesisSetM):
return True
elif isinstance(other, CartesianProduct):
return is_subset_of_cart_prod(other)
elif isinstance(other, Union):
for union_elem in other.data:
if isinstance(union_elem, CartesianProduct):
if is_subset_of_cart_prod(union_elem):
return True
return False

[docs]    def get_powerset_level(self, other: Structure) -> int:
"""Return the number of power set levels between self and other.

:param other: Must be an instance of Structure.
:return: An integer >= 0. Is always 0 for type CartesianProduct.
"""
assert isinstance(other, Structure)
return 0

[docs]    def is_same(self, other: Structure) -> bool:
"""Return True if self is structurally equivalent to other.

:param other: Must be an instance of Structure.
:return: True if self is structurally equivalent to other.
"""
assert isinstance(other, Structure)
if isinstance(other, CartesianProduct):
return (self.left == other.left) and (self.right == other.right)
return False

# ----------------------------------------------------------------------------------------------

[docs]    def __hash__(self):
"""Return a hash based on the member values. (It must match the implementation of is_same,
to which Structure.__eq__ redirects equality comparisons.) Is always cached.
"""
return _misc.get_hash(_misc.get_full_class_name(self), self.left, self.right)

[docs]    def __repr__(self):
"""Return the instance's code representation."""
return 'CartesianProduct(left={left}, right={right})'.format(
left=repr(self.left), right=repr(self.right))

[docs]    def __str__(self):
"""Return the instance's string representation."""
return '({left} x {right})'.format(left=str(self.left), right=str(self.right))

[docs]class Union(Structure):
"""Represent the :term:union node of a structure.

No member of this instance is a :term:subset of another member, and no member of this union
is a union itself (union arguments get 'unioned into' this union).
"""

def __init__(self, iterable):
"""
:param iterable: An Iterable
<https://docs.python.org/3.4/library/collections.abc.html?highlight=iterable#collections.abc.Iterable>_
of one or more sets to be unioned. All elements must be an instance of Structure.
"""
assert isinstance(iterable, _collections.Iterable)

"""Add an element (a Structure) to the union if it is not already in it."""
assert isinstance(new_element, Structure)
for existing_element in writeable_union:
if new_element.is_subset(existing_element):
# To be added element is subset of existing element: nothing to add.
break
elif existing_element.is_subset(new_element):
# To be added element is (real) superset of existing element: exchange them.
writeable_union.remove(existing_element)
break
else:
# To be added element is neither subset nor superset of existing: add it.

writeable_union = set()
for new_structure in iterable:
if isinstance(new_structure, Union):
# If the structure to be added is a union, add it element by element.
for element in new_structure.data:
else:
assert len(writeable_union) > 0
self._data = frozenset(writeable_union)

@property
def data(self) -> frozenset:
"""Read-only access to the raw collection (frozenset) of the union members."""
return self._data

[docs]    def is_subset(self, other: Structure) -> bool:
"""Return True if self is a :term:subset of other.

Is True if every element of this :term:union is a subset of other:

-   If other is a union, we compare against each element of it.
-   If other is not a union, we compare directly against it.

Is also True if other is GenesisSetM (everything in our system is an element of
:math:M).

:param other: Must be an instance of Structure.
:return: True if self is a subset of other.
"""
assert isinstance(other, Structure)

def is_subset_of_union(elem, union):
for union_elem in union:
if elem.is_subset(union_elem):
return True  # If elem is a subset of any element of union, return True.
return False  # Only return False if elem is not a subset of any element of union.

if isinstance(other, GenesisSetM):
return True
elif isinstance(other, Union):
for element in self.data:
if not is_subset_of_union(element, other.data):
return False  # If any element is not a subset of other, return False.
else:
for element in self.data:
if not element.is_subset(other):
return False  # If any element is not a subset of other, return False.
return True  # Only return True if all elements are a subset of other.

[docs]    def get_powerset_level(self, other: Structure) -> int:
"""Return the number of power set levels between self and other.

:param other: Must be an instance of Structure.
:return: An integer >= 0. Is always 0 for type CartesianProduct.
"""
assert isinstance(other, Structure)
return 0

[docs]    def is_same(self, other: Structure) -> bool:
"""Return True if self is structurally equivalent to other.

:param other: Must be an instance of Structure.
:return: True if self is structurally equivalent to other.
"""
assert isinstance(other, Structure)
if isinstance(other, Union):
return self.data == other.data
else:
if len(self.data) == 1:
# Compare the one element against 'other'.
return _misc.get_single_iter_elem(self.data).is_same(other)
else:
# self is a 'real' union, so the 'other' must also be a union.
return False

# ----------------------------------------------------------------------------------------------

[docs]    def __hash__(self):
"""Return a hash based on the member values. (It must match the implementation of is_same,
to which Structure.__eq__ redirects equality comparisons.) Is always cached.
"""
return _misc.get_hash(_misc.get_full_class_name(self), self.data)

[docs]    def __repr__(self):
"""Return the instance's code representation."""
unsorted_strings = [repr(elem) for elem in self.data]
return 'Union([{elems}])'.format(elems=', '.join(elem for elem in sorted(unsorted_strings)))

[docs]    def __str__(self):
"""Return the instance's string representation."""
if len(self.data) == 1:
return str(_misc.get_single_iter_elem(self.data))
else:
unsorted_strings = [str(elem) for elem in self.data]
return '({elems})'.format(elems=' U '.join(elem for elem in sorted(unsorted_strings)))

[docs]class PowerSet(Structure):
"""Represent the :term:power set node of a structure."""

def __init__(self, elements_struct):
"""
:param elements_struct: The structure of the elements of the :term:set of which we are
representing the power set. Must be an instance of Structure.
"""
assert isinstance(elements_struct, Structure)
self._base_set = elements_struct

@property
def base_set(self) -> Structure:
return self._base_set

[docs]    def is_subset(self, other: Structure) -> bool:
"""Return True if self is a :term:subset of other.

:param other: Must be an instance of Structure.
:return: True if self is a subset of other.
"""
assert isinstance(other, Structure)
if isinstance(other, GenesisSetM):
return True
elif isinstance(other, PowerSet):
return self._base_set.is_subset(other._base_set)
return False

[docs]    def get_powerset_level(self, other: Structure) -> int:
"""Return the number of :term:power set levels between self and other.

:param other: Must be an instance of Structure.
:return: The number of power set levels (>= 0) that are between self and other.
A result of 0 may mean that the two ground sets are equal or that they are not related.
"""

def recurse_through_powerset_levels(structure_under_test, powerset_level=0):
if type(structure_under_test) != PowerSet:
return 0
powerset_level += 1
if structure_under_test.base_set.is_subset(other):
return powerset_level
return recurse_through_powerset_levels(structure_under_test.base_set, powerset_level)

return recurse_through_powerset_levels(self)

[docs]    def is_same(self, other: Structure) -> bool:
"""Return True if self is structurally equivalent to other.

:param other: Must be an instance of Structure.
:return: True if self is structurally equivalent to other.
"""
assert isinstance(other, Structure)
if isinstance(other, PowerSet):
return self._base_set == other._base_set
return False

# ----------------------------------------------------------------------------------------------

[docs]    def __hash__(self):
"""Return a hash based on the member values. (It must match the implementation of is_same,
to which Structure.__eq__ redirects equality comparisons.) Is always cached.
"""
return _misc.get_hash(_misc.get_full_class_name(self), self.base_set)

[docs]    def __repr__(self):
"""Return the instance's code representation."""
return 'PowerSet({elems})'.format(elems=repr(self._base_set))

[docs]    def __str__(self):
"""Return the instance's string representation."""
elem_str = str(self._base_set)
# If the base set starts with a P (PowerSet) or a parenthesis, don't add parentheses.
if elem_str[0] == 'P' or elem_str[0] == '(':
return 'P{elem}'.format(elem=elem_str)
else:
return 'P({elem})'.format(elem=elem_str)