base.pyx

r"""
Base classes for triangulations

We provide (fast) cython implementations here.

AUTHORS:

- Volker Braun (2010-09-14): initial version.
"""


########################################################################
#       Copyright (C) 2010 Volker Braun <[email protected]>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#                  http://www.gnu.org/licenses/
########################################################################



from sage.structure.sage_object cimport SageObject
from sage.structure.parent cimport Parent
from sage.categories.sets_cat import Sets
from sage.matrix.constructor import matrix
from sage.misc.misc import uniq
from sage.misc.cachefunc import cached_method

from functions cimport binomial
from triangulations cimport \
    triangulations_ptr, init_triangulations, next_triangulation, delete_triangulations


########################################################################
cdef class Point(SageObject):
    r"""
    A point of a point configuration.

    Note that the coordinates of the points of a point configuration
    are somewhat arbitrary. What counts are the abstract linear
    relations between the points, for example encoded by the
    :meth:`~sage.geometry.triangulation.point_configuration.PointConfiguration.circuits`.

    .. Warning::
    
        You should not create :class:`Point` objects manually. The
        constructor of :class:`PointConfiguration_base` takes care of
        this for you.

    INPUT:

    - ``point_configuration`` -- :class:`PointConfiguration_base`. The
      point configuration to which the point belongs.

    - ``i`` -- integer. The index of the point in the point
      configuration.

    - ``projective`` -- the projective coordinates of the point.

    - ``affine`` -- the affine coordinates of the point.

    - ``reduced`` -- the reduced (with linearities removed)
      coordinates of the point.

    EXAMPLES::
     
        sage: pc = PointConfiguration([(0,0)])
        sage: from sage.geometry.triangulation.base import Point
        sage: Point(pc, 123, (0,0,1), (0,0), ())
        P(0, 0)
    """

    cdef int _index
    cdef tuple _projective, _affine, _reduced_affine
    cdef object _point_configuration
    cdef object _reduced_affine_vector, _reduced_projective_vector


    def __init__(self, point_configuration, i, projective, affine, reduced):
        r"""
        Construct a :class:`Point`.
        
        EXAMPLES::
        
            sage: pc = PointConfiguration([(0,0)])
            sage: from sage.geometry.triangulation.base import Point
            sage: Point(pc, 123, (0,0,1), (0,0), ())   # indirect doctest
            P(0, 0)
        """
        self._index = i
        self._projective = tuple(projective)
        self._affine = tuple(affine)
        self._reduced_affine = tuple(reduced)
        self._point_configuration = point_configuration
        V = point_configuration.reduced_affine_vector_space()
        self._reduced_affine_vector = V(self._reduced_affine)
        P = point_configuration.reduced_projective_vector_space()
        self._reduced_projective_vector = P(self.reduced_projective())


    cpdef point_configuration(self):
        r"""
        Return the point configuration to which the point belongs.
        
        OUTPUT:

        A :class:`~sage.geometry.triangulation.point_configuration.PointConfiguration`.

        EXAMPLES:

            sage: pc = PointConfiguration([ (0,0), (1,0), (0,1) ])
            sage: p = pc.point(0)
            sage: p is pc.point(0)
            True
            sage: p.point_configuration() is pc
            True
        """
        return self._point_configuration


    def __iter__(self):
        r"""
        Iterate through the affine ambient space coordinates of the point.
        
        EXAMPLES::
     
            sage: pc = PointConfiguration([(0,0)])
            sage: from sage.geometry.triangulation.base import Point
            sage: p = Point(pc, 123, (1,2,1), (3,4), ()) 
            sage: list(p)  # indirect doctest
            [3, 4]
        """
        return self._affine.__iter__()


    def __len__(self):
        r"""
        Return the affine ambient space dimension.
        
        EXAMPLES::
        
            sage: pc = PointConfiguration([(0,0)])
            sage: from sage.geometry.triangulation.base import Point
            sage: p = Point(pc, 123, (1,2,1), (3,4), ()) 
            sage: len(p)
            2
            sage: p.__len__()
            2
        """
        return len(self._affine)


    cpdef index(self):
        """
        Return the index of the point in the point configuration.

        EXAMPLES::
        
            sage: pc = PointConfiguration([[0, 1], [0, 0], [1, 0]])
            sage: p = pc.point(2); p
            P(1, 0)
            sage: p.index()
            2
        """
        return self._index

        
    cpdef projective(self):
        r"""
        Return the projective coordinates of the point in the ambient space.

        OUTPUT:

        A tuple containing the coordinates.

        EXAMPLES::
        
            sage: pc = PointConfiguration([[10, 0, 1], [10, 0, 0], [10, 2, 3]])
            sage: p = pc.point(2); p
            P(10, 2, 3)
            sage: p.affine()
            (10, 2, 3)
            sage: p.projective()
            (10, 2, 3, 1)
            sage: p.reduced_affine()
            (2, 2)
            sage: p.reduced_projective()
            (2, 2, 1)
            sage: p.reduced_affine_vector()
            (2, 2)
        """
        return self._projective

    
    cpdef affine(self):
        r"""
        Return the affine coordinates of the point in the ambient space.

        OUTPUT:

        A tuple containing the coordinates.

        EXAMPLES::
        
            sage: pc = PointConfiguration([[10, 0, 1], [10, 0, 0], [10, 2, 3]])
            sage: p = pc.point(2); p
            P(10, 2, 3)
            sage: p.affine()
            (10, 2, 3)
            sage: p.projective()
            (10, 2, 3, 1)
            sage: p.reduced_affine()
            (2, 2)
            sage: p.reduced_projective()
            (2, 2, 1)
            sage: p.reduced_affine_vector()
            (2, 2)
        """
        return self._affine

    
    cpdef reduced_affine(self):
        r"""
        Return the affine coordinates of the point on the hyperplane
        spanned by the point configuration.

        OUTPUT:

        A tuple containing the coordinates.

        EXAMPLES::
        
            sage: pc = PointConfiguration([[10, 0, 1], [10, 0, 0], [10, 2, 3]])
            sage: p = pc.point(2); p
            P(10, 2, 3)
            sage: p.affine()
            (10, 2, 3)
            sage: p.projective()
            (10, 2, 3, 1)
            sage: p.reduced_affine()
            (2, 2)
            sage: p.reduced_projective()
            (2, 2, 1)
            sage: p.reduced_affine_vector()
            (2, 2)
        """
        return self._reduced_affine


    cpdef reduced_projective(self):
        r"""
        Return the projective coordinates of the point on the hyperplane
        spanned by the point configuration.

        OUTPUT:

        A tuple containing the coordinates.

        EXAMPLES::
        
            sage: pc = PointConfiguration([[10, 0, 1], [10, 0, 0], [10, 2, 3]])
            sage: p = pc.point(2); p
            P(10, 2, 3)
            sage: p.affine()
            (10, 2, 3)
            sage: p.projective()
            (10, 2, 3, 1)
            sage: p.reduced_affine()
            (2, 2)
            sage: p.reduced_projective()
            (2, 2, 1)
            sage: p.reduced_affine_vector()
            (2, 2)
        """
        return tuple(self._reduced_affine)+(1,)

    
    cpdef reduced_affine_vector(self):
        """
        Return the affine coordinates of the point on the hyperplane
        spanned by the point configuration.

        OUTPUT:

        A tuple containing the coordinates.

        EXAMPLES::
        
            sage: pc = PointConfiguration([[10, 0, 1], [10, 0, 0], [10, 2, 3]])
            sage: p = pc.point(2); p
            P(10, 2, 3)
            sage: p.affine()
            (10, 2, 3)
            sage: p.projective()
            (10, 2, 3, 1)
            sage: p.reduced_affine()
            (2, 2)
            sage: p.reduced_projective()
            (2, 2, 1)
            sage: p.reduced_affine_vector()
            (2, 2)
        """
        return self._reduced_affine_vector


    cpdef reduced_projective_vector(self):
        """
        Return the affine coordinates of the point on the hyperplane
        spanned by the point configuration.

        OUTPUT:

        A tuple containing the coordinates.

        EXAMPLES::
        
            sage: pc = PointConfiguration([[10, 0, 1], [10, 0, 0], [10, 2, 3]])
            sage: p = pc.point(2); p
            P(10, 2, 3)
            sage: p.affine()
            (10, 2, 3)
            sage: p.projective()
            (10, 2, 3, 1)
            sage: p.reduced_affine()
            (2, 2)
            sage: p.reduced_projective()
            (2, 2, 1)
            sage: p.reduced_affine_vector()
            (2, 2)
            sage: type(p.reduced_affine_vector())
            <type 'sage.modules.vector_rational_dense.Vector_rational_dense'>
        """
        return self._reduced_projective_vector


    cpdef _repr_(self):
        """
        Return a string representation of the point.

        OUTPUT:
        
        String.
        
        EXAMPLES::

            sage: pc = PointConfiguration([[10, 0, 1], [10, 0, 0]])
            sage: from sage.geometry.triangulation.base import Point
            sage: p = Point(pc, 123, (0,0,1), (0,0), (0,))
            sage: p._repr_()
            'P(0, 0)'
        """
        return 'P'+str(self._affine)


########################################################################
cdef class PointConfiguration_base(Parent):
    r"""
    The cython abstract base class for
    :class:`~sage.geometry.triangulation.PointConfiguration`.

    .. WARNING::

        You should not instantiate this base class, but only its
        derived class
        :class:`~sage.geometry.triangulation.point_configuration.PointConfiguration`.
    """

    def __init__(self, points, defined_affine):
        r"""
        Construct a :class:`PointConfiguration_base`.
        
        INPUT:

        - ``points`` -- a tuple of tuples of projective coordinates
          with ``1`` as the final coordinate.
        
        - ``defined_affine`` -- Boolean. Whether the point
          configuration is defined as a configuration of affine (as
          opposed to projective) points.

        TESTS::
        
            sage: from sage.geometry.triangulation.base import PointConfiguration_base
            sage: PointConfiguration_base(((1,2,1),(2,3,1),(3,4,1)), False)  # indirect doctest
            <type 'sage.geometry.triangulation.base.PointConfiguration_base'>
        """
        Parent.__init__(self, category = Sets())
        self._init_points(points)
        self._is_affine = defined_affine


    cdef tuple _pts
    cdef int _ambient_dim
    cdef int _dim
    cdef object _base_ring
    cdef bint _is_affine
    cdef object _reduced_affine_vector_space, _reduced_projective_vector_space


    cdef _init_points(self, tuple projective_points):
        """
        Internal method to determine coordinates of points.

        EXAMPLES::
        
            sage: p = PointConfiguration([[0, 1], [0, 0], [1, 0]])   # indirect doctest
            sage: p.points()  
            (P(0, 1), P(0, 0), P(1, 0))

        Special cases::

            sage: PointConfiguration([])
            A point configuration in QQ^0 consisting of 0 points. The 
            triangulations of this point configuration are assumed to 
            be connected, not necessarily fine, not necessarily regular.
            sage: PointConfiguration([(1,2,3)])
            A point configuration in QQ^3 consisting of 1 point. The 
            triangulations of this point configuration are assumed to 
            be connected, not necessarily fine, not necessarily regular.
        """
        n = len(projective_points)
        if n==0:
            self._ambient_dim = 0
            self._dim = -1
            self._pts = tuple()
            return
    
        # We now are sure that projective_points is not empty
        self._ambient_dim = len(projective_points[0])-1
        assert all([ len(p)==self._ambient_dim+1 for p in projective_points ]), \
            'The given point coordinates must all have the same length.'
        assert len(uniq(projective_points)) == len(projective_points), \
            'Not all points are pairwise distinct.'
        
        proj = matrix(projective_points).transpose()
        self._base_ring = proj.base_ring()

        if all([ x==1 for x in proj.row(self.ambient_dim()) ]):
            aff = proj.submatrix(0,0,nrows=self.ambient_dim())
        else:
            raise NotImplementedError # TODO

        if n>1:
            # shift first point to origin
            red = matrix([ aff.column(i)-aff.column(0) for i in range(0,n) ]).transpose()
            # pick linearly independent rows
            red = matrix([ red.row(i) for i in red.pivot_rows()])
        else:
            red = matrix(0,1)
        self._dim = red.nrows()

        from sage.modules.free_module import VectorSpace
        self._reduced_affine_vector_space = VectorSpace(self._base_ring.fraction_field(), self._dim)
        self._reduced_projective_vector_space = VectorSpace(self._base_ring.fraction_field(), self._dim+1)
        self._pts = tuple([ Point(self, i, proj.column(i), aff.column(i), red.column(i))
                           for i in range(0,n) ])
                 

    cpdef reduced_affine_vector_space(self):
        """
        Return the vector space that contains the affine points.
        
        OUTPUT: 

        A vector space over the fraction field of :meth:`base_ring`.
        
        EXAMPLES::

            sage: p = PointConfiguration([[0,0,0], [1,2,3]])
            sage: p.base_ring()
            Integer Ring
            sage: p.reduced_affine_vector_space()
            Vector space of dimension 1 over Rational Field
            sage: p.reduced_projective_vector_space()
            Vector space of dimension 2 over Rational Field
        """
        return self._reduced_affine_vector_space


    cpdef reduced_projective_vector_space(self):
        """
        Return the vector space that is spanned by the homogeneous
        coordinates.
        
        OUTPUT: 

        A vector space over the fraction field of :meth:`base_ring`.
        
        EXAMPLES::

            sage: p = PointConfiguration([[0,0,0], [1,2,3]])
            sage: p.base_ring()
            Integer Ring
            sage: p.reduced_affine_vector_space()
            Vector space of dimension 1 over Rational Field
            sage: p.reduced_projective_vector_space()
            Vector space of dimension 2 over Rational Field
        """
        return self._reduced_projective_vector_space


    cpdef ambient_dim(self):
        """
        Return the dimension of the ambient space of the point
        configuration.

        See also :meth:`dimension`

        EXAMPLES::
        
            sage: p = PointConfiguration([[0,0,0]])
            sage: p.ambient_dim()
            3
            sage: p.dim()
            0
        """
        return self._ambient_dim


    cpdef dim(self):
        """
        Return the actual dimension of the point
        configuration.

        See also :meth:`ambient_dim`

        EXAMPLES::
        
            sage: p = PointConfiguration([[0,0,0]])
            sage: p.ambient_dim()
            3
            sage: p.dim()
            0
        """
        return self._dim


    cpdef base_ring(self):
        r"""
        Return the base ring, that is, the ring containing the
        coordinates of the points.
        
        OUTPUT: 

        A ring.

        EXAMPLES::

            sage: p = PointConfiguration([(0,0)])
            sage: p.base_ring()
            Integer Ring

            sage: p = PointConfiguration([(1/2,3)])
            sage: p.base_ring()
            Rational Field
            
            sage: p = PointConfiguration([(0.2, 5)])
            sage: p.base_ring()
            Real Field with 53 bits of precision
        """
        return self._base_ring


    cpdef bint is_affine(self):
        """
        Whether the configuration is defined by affine points.

        OUTPUT:
        
        Boolean. If true, the homogeneous coordinates all have `1` as
        their last entry.
        
        EXAMPLES::

            sage: p = PointConfiguration([(0.2, 5), (3, 0.1)])
            sage: p.is_affine()
            True

            sage: p = PointConfiguration([(0.2, 5, 1), (3, 0.1, 1)], projective=True)
            sage: p.is_affine()
            False
        """
        return self._is_affine


    def _assert_is_affine(self):
        """
        Raise a ``ValueError`` if the point configuration is not
        defined by affine points.

        EXAMPLES::

            sage: p = PointConfiguration([(0.2, 5), (3, 0.1)])
            sage: p._assert_is_affine()
            sage: p = PointConfiguration([(0.2, 5, 1), (3, 0.1, 1)], projective=True)
            sage: p._assert_is_affine()
            Traceback (most recent call last):
            ...
            ValueError: The point configuration contains projective points.
        """
        if not self.is_affine():
            raise ValueError('The point configuration contains projective points.')


    def __getitem__(self, i):
        """
        Return the ``i``-th point.

        Same as :meth:`point`.
        
        INPUT:

        - ``i`` -- integer.

        OUTPUT:

        The ``i``-th point of the point configuration.
        
        EXAMPLES::

            sage: p = PointConfiguration([[1,0], [2,3], [3,2]])
            sage: [ p[i] for i in range(0,p.n_points()) ] 
            [P(1, 0), P(2, 3), P(3, 2)]
            sage: list(p)
            [P(1, 0), P(2, 3), P(3, 2)]
            sage: list(p.points())
            [P(1, 0), P(2, 3), P(3, 2)]
            sage: [ p.point(i) for i in range(0,p.n_points()) ] 
            [P(1, 0), P(2, 3), P(3, 2)]
        """
        return self._pts[i]


    cpdef n_points(self):
        """
        Return the number of points. 

        Same as ``len(self)``.

        EXAMPLES::
        
            sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]]) 
            sage: p
            A point configuration in QQ^2 consisting of 5 points. The 
            triangulations of this point configuration are assumed to 
            be connected, not necessarily fine, not necessarily regular.
            sage: len(p)
            5
            sage: p.n_points()
            5
        """
        return len(self._pts)
    

    cpdef points(self):
        """
        Return a list of the points.

        OUTPUT:
        
        Returns a list of the points. See also the :meth:`__iter__`
        method, which returns the corresponding generator.

        EXAMPLES::

            sage: pconfig = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]]) 
            sage: list(pconfig)
            [P(0, 0), P(0, 1), P(1, 0), P(1, 1), P(-1, -1)]
            sage: [ p for p in pconfig.points() ]
            [P(0, 0), P(0, 1), P(1, 0), P(1, 1), P(-1, -1)]
            sage: pconfig.point(0)
            P(0, 0)
            sage: pconfig.point(1)
            P(0, 1)
            sage: pconfig.point( pconfig.n_points()-1 )
            P(-1, -1)
        """
        return self._pts


    def point(self, i):
        """
        Return the i-th point of the configuration.

        Same as :meth:`__getitem__`

        INPUT:
        
        - ``i`` -- integer.

        OUTPUT:
        
        A point of the point configuration.

        EXAMPLES::

            sage: pconfig = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]]) 
            sage: list(pconfig)
            [P(0, 0), P(0, 1), P(1, 0), P(1, 1), P(-1, -1)]
            sage: [ p for p in pconfig.points() ]
            [P(0, 0), P(0, 1), P(1, 0), P(1, 1), P(-1, -1)]
            sage: pconfig.point(0)
            P(0, 0)
            sage: pconfig[0]
            P(0, 0)
            sage: pconfig.point(1)
            P(0, 1)
            sage: pconfig.point( pconfig.n_points()-1 )
            P(-1, -1)
        """
        return self._pts[i]


    def __len__(self): 
        """
        Return the number of points. 

        Same as :meth:`n_points`

        EXAMPLES::
        
            sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]]) 
            sage: p
            A point configuration in QQ^2 consisting of 5 points. The 
            triangulations of this point configuration are assumed to 
            be connected, not necessarily fine, not necessarily regular.
            sage: len(p)
            5
            sage: p.n_points()
            5
        """
        return len(self._pts)


    cpdef simplex_to_int(self, simplex):
        r"""
        Returns an integer that uniquely identifies the given simplex.

        See also the inverse method :meth:`int_to_simplex`.

        The enumeration is compatible with [PUNTOS]_.

        INPUT:
        
        - ``simplex`` -- iterable, for example a list. The elements
          are the vertex indices of the simplex.

        OUTPUT: 
        
        An integer that uniquely specifies the simplex.
        
        EXAMPLES::

            sage: U=matrix([
            ...      [ 0, 0, 0, 0, 0, 2, 4,-1, 1, 1, 0, 0, 1, 0],
            ...      [ 0, 0, 0, 1, 0, 0,-1, 0, 0, 0, 0, 0, 0, 0],
            ...      [ 0, 2, 0, 0, 0, 0,-1, 0, 1, 0, 1, 0, 0, 1],
            ...      [ 0, 1, 1, 0, 0, 1, 0,-2, 1, 0, 0,-1, 1, 1],
            ...      [ 0, 0, 0, 0, 1, 0,-1, 0, 0, 0, 0, 0, 0, 0]
            ...   ])
            sage: pc = PointConfiguration(U.columns())
            sage: pc.simplex_to_int([1,3,4,7,10,13])
            1678
            sage: pc.int_to_simplex(1678)
            (1, 3, 4, 7, 10, 13)
        """
        cdef int s = 1
        cdef int k = 1
        cdef int n = self.n_points()
        cdef int d = len(simplex)
        assert d==self.dim()+1
        cdef int i, j
        for i in range(1,d+1):
            l = simplex[i-1]+1
            for j in range(k,l):
                s += binomial(n-j,d-i)
            k = l+1
        return s


    cpdef int_to_simplex(self, int s):
        r"""
        Reverses the enumeration of possible simplices in
        :meth:`simplex_to_int`.

        The enumeration is compatible with [PUNTOS]_.

        INPUT:

        - ``s`` -- int. An integer that uniquely specifies a simplex. 

        OUTPUT:

        An ordered tuple consisting of the indices of the vertices of
        the simplex.
        
        EXAMPLES::

            sage: U=matrix([
            ...      [ 0, 0, 0, 0, 0, 2, 4,-1, 1, 1, 0, 0, 1, 0],
            ...      [ 0, 0, 0, 1, 0, 0,-1, 0, 0, 0, 0, 0, 0, 0],
            ...      [ 0, 2, 0, 0, 0, 0,-1, 0, 1, 0, 1, 0, 0, 1],
            ...      [ 0, 1, 1, 0, 0, 1, 0,-2, 1, 0, 0,-1, 1, 1],
            ...      [ 0, 0, 0, 0, 1, 0,-1, 0, 0, 0, 0, 0, 0, 0]
            ...   ])
            sage: pc = PointConfiguration(U.columns())
            sage: pc.simplex_to_int([1,3,4,7,10,13])
            1678
            sage: pc.int_to_simplex(1678)
            (1, 3, 4, 7, 10, 13)
        """
        simplex = []
        cdef int l = 0
        cdef int n = self.n_points()
        cdef int d = self.dim()+1
        cdef int k, b
        for k in range(1,d):
            l += 1
            i = l
            j = 1
            b = binomial(n-l,d-k)
            while (s>b) and (b>0):
                j += 1
                l += 1
                s -= b
                b = binomial(n-l,d-k)
            simplex.append(l-1)
        simplex.append(s+l-1)
        assert len(simplex) == d
        return tuple(simplex)

    

########################################################################
cdef class ConnectedTriangulationsIterator(SageObject):
    r"""
    A Python shim for the C++-class 'triangulations'

    INPUT:

    - ``point_configuration`` -- a
      :class:`~sage.geometry.triangulation.point_configuration.PointConfiguration`.
    
    - ``seed`` -- a regular triangulation or ``None`` (default). In
      the latter case, a suitable triangulation is generated
      automatically. Otherwise, you can explicitly specify the seed
      triangulation as
    
        * A
          :class:`~sage.geometry.triangulation.element.Triangulation`
          object, or

        * an iterable of iterables specifying the vertices of the simplices, or

        * an iterable of integers, which are then considered the
          enumerated simplices (see
          :meth:`~PointConfiguration_base.simplex_to_int`.

    - ``star`` -- either ``None`` (default) or an integer. If an
      integer is passed, all returned triangulations will be star with
      respect to the

    - ``fine`` -- boolean (default: ``False``). Whether to return only
      fine triangulations, that is, simplicial decompositions that
      make use of all the points of the configuration.

    OUTPUT:

    An iterator. The generated values are tuples of
    integers, which encode simplices of the triangulation. The output
    is a suitable input to
    :class:`~sage.geometry.triangulation.element.Triangulation`.

    EXAMPLES::
    
        sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
        sage: from sage.geometry.triangulation.base import ConnectedTriangulationsIterator
        sage: ci = ConnectedTriangulationsIterator(p)
        sage: ci.next()
        (9, 10)
        sage: ci.next()
        (2, 3, 4, 5)
        sage: ci.next()
        (7, 8)
        sage: ci.next()
        (1, 3, 5, 7)
        sage: ci.next()
        Traceback (most recent call last):
        ...
        StopIteration

    You can reconstruct the triangulation from the compressed output via::

        sage: from sage.geometry.triangulation.element import Triangulation
        sage: Triangulation((2, 3, 4, 5), p)
        (<0,1,3>, <0,1,4>, <0,2,3>, <0,2,4>)

    How to use the restrictions::

        sage: ci = ConnectedTriangulationsIterator(p, fine=True)
        sage: list(ci)
        [(2, 3, 4, 5), (1, 3, 5, 7)]
        sage: ci = ConnectedTriangulationsIterator(p, star=1)
        sage: list(ci)
        [(7, 8)]
        sage: ci = ConnectedTriangulationsIterator(p, star=1, fine=True)
        sage: list(ci)
        []
    """
    
    cdef triangulations_ptr _tp


    def __cinit__(self):
        """
        The Cython constructor.
        
        TESTS::
        
            sage: from sage.geometry.triangulation.base import ConnectedTriangulationsIterator
            sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
            sage: ConnectedTriangulationsIterator(p, fine=True)   # indirect doctest
            <type 'sage.geometry.triangulation.base.ConnectedTriangulationsIterator'>
        """
        self._tp = NULL


    def __init__(self, point_configuration, seed=None, star=None, fine=False):
        r"""
        The Python constructor.

        See :class:`ConnectedTriangulationsIterator` for a description
        of the arguments.

        TESTS::

            sage: p = PointConfiguration([[0,4],[2,3],[3,2],[4,0],[3,-2],[2,-3],[0,-4],[-2,-3],[-3,-2],[-4,0],[-3,2],[-2,3]])
            sage: from sage.geometry.triangulation.base import ConnectedTriangulationsIterator
            sage: ci = ConnectedTriangulationsIterator(p)
            sage: len(list(ci))    # long time (23s on sage.math, 2011)
            16796   
            sage: ci = ConnectedTriangulationsIterator(p, star=3)
            sage: len(list(ci))    # long time (23s on sage.math, 2011)
            1
        """
        if star==None:
            star = -1
        if seed==None:
            seed = point_configuration.lexicographic_triangulation().enumerate_simplices()
        try:
            enumerated_simplices_seed = seed.enumerated_simplices()
        except AttributeError:
            enumerated_simplices_seed = tuple([ int(t) for t in seed ])
        assert self._tp == NULL
        self._tp = init_triangulations(point_configuration.n_points(),
                                       point_configuration.dim()+1,
                                       star, fine,
                                       enumerated_simplices_seed, 
                                       point_configuration.bistellar_flips())


    def __dealloc__(self):
        r"""
        The Cython destructor.
        """
        delete_triangulations(self._tp)


    def __iter__(self):
        r"""
        The iterator interface: Start iterating.
        
        TESTS::
        
            sage: from sage.geometry.triangulation.base import ConnectedTriangulationsIterator
            sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
            sage: ci = ConnectedTriangulationsIterator(p, fine=True)
            sage: ci.__iter__()
            <type 'sage.geometry.triangulation.base.ConnectedTriangulationsIterator'>
            sage: ci.__iter__() is ci
            True
        """
        return self


    def __next__(self):
        r"""
        The iterator interface: Next iteration.

        EXAMPLES::

            sage: from sage.geometry.triangulation.base import ConnectedTriangulationsIterator
            sage: p = PointConfiguration([[0,0],[0,1],[1,0],[1,1],[-1,-1]])
            sage: ci = ConnectedTriangulationsIterator(p)
            sage: ci.__next__()
            (9, 10)
        """
        t = next_triangulation(self._tp)
        if len(t)==0:
            raise StopIteration
        return t