# Copyright 2013 Mark Dickinson
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#   http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""
Tools to analyze the Python object graph and find reference cycles.

"""
import gc
import itertools

import six

from refcycle.annotations import object_annotation, annotated_references
from refcycle.annotated_graph import (
    AnnotatedEdge,
    AnnotatedGraph,
    AnnotatedVertex,
)
from refcycle.element_transform_set import ElementTransformSet
from refcycle.key_transform_dict import KeyTransformDict
from refcycle.i_directed_graph import IDirectedGraph


class ObjectGraph(IDirectedGraph):
    """Directed graph representing a collection of Python objects and the
    references between them.

    An ObjectGraph can be constructed directly from an existing iterable
    collection of objects::

        >>> from refcycle import ObjectGraph
        >>> inner = [1, 2, 3]
        >>> outer = [inner] * 3
        >>> graph = ObjectGraph([outer, inner])
        >>> graph
        <refcycle.object_graph.ObjectGraph object of size 2 at 0x100470ed0>

    This constructs a graph whose vertices are the two Python objects ``inner``
    and ``outer``.  All references between the given objects are automatically
    added as graph edges.

    The ObjectGraph acts as a container for those objects, much like a set::

        >>> inner in graph
        True
        >>> 2 in graph
        False
        >>> len(graph)
        2
        >>> list(graph)
        [[[1, 2, 3], [1, 2, 3], [1, 2, 3]], [1, 2, 3]]

    We can find the referrers and referents of any particular object in the
    graph using the :meth:`~refcycle.object_graph.ObjectGraph.parents` and
    :meth:`~refcycle.object_graph.ObjectGraph.children` methods.

        >>> graph.children(outer)
        [[1, 2, 3], [1, 2, 3], [1, 2, 3]]

    Here we see ``inner`` occurring three times as a child of ``outer``,
    because there are three distinct references from ``outer`` to ``inner``.

    """
    ###########################################################################
    ### IDirectedGraph interface.
    ###########################################################################

    def head(self, edge):
        """
        Return the head (target, destination) of the given edge.

        """
        return self._head[edge]

    def tail(self, edge):
        """
        Return the tail (source) of the given edge.

        """
        return self._tail[edge]

    def out_edges(self, vertex):
        """
        Return a list of the edges leaving this vertex.

        """
        return self._out_edges[vertex]

    def in_edges(self, vertex):
        """
        Return a list of the edges entering this vertex.

        """
        return self._in_edges[vertex]

    @property
    def vertices(self):
        """
        Return collection of vertices of the graph.

        """
        return self._vertices

    @property
    def edges(self):
        """
        Return collection of edges of the graph.

        """
        return self._edges

    def full_subgraph(self, objects):
        """
        Return the subgraph of this graph whose vertices
        are the given ones and whose edges are the edges
        of the original graph between those vertices.

        """
        vertices = ElementTransformSet(transform=id)
        out_edges = KeyTransformDict(transform=id)
        in_edges = KeyTransformDict(transform=id)
        for obj in objects:
            vertices.add(obj)
            out_edges[obj] = []
            in_edges[obj] = []

        edges = set()
        head = {}
        tail = {}

        for referrer in vertices:
            for edge in self._out_edges[referrer]:
                referent = self._head[edge]
                if referent not in vertices:
                    continue
                edges.add(edge)
                tail[edge] = referrer
                head[edge] = referent
                out_edges[referrer].append(edge)
                in_edges[referent].append(edge)

        return ObjectGraph._raw(
            vertices=vertices,
            edges=edges,
            out_edges=out_edges,
            in_edges=in_edges,
            head=head,
            tail=tail,
        )

    ###########################################################################
    ### Set and dict overrides.
    ###########################################################################

    @classmethod