Coverage for local/lib/python2.7/site-packages/sage/combinat/e_one_star.py : 91%

r""" 

Substitutions over unit cube faces (Rauzy fractals) 

This module implements the `E_1^*(\sigma)` substitution 

associated with a one-dimensional substitution `\sigma`, 

that acts on unit faces of dimension `(d-1)` in `\RR^d`. 

This module defines the following classes and functions: 

- ``Face`` - a class to model a face 

- ``Patch`` - a class to model a finite set of faces 

- ``E1Star`` - a class to model the `E_1^*(\sigma)` application 

defined by the substitution sigma 

See the documentation of these objects for more information. 

The convention for the choice of the unit faces and the 

definition of `E_1^*(\sigma)` varies from article to article. 

Here, unit faces are defined by 

.. MATH:: 

\begin{array}{ccc} 

\,[x, 1]^* & = & \{x + \lambda e_2 + \mu e_3 : \lambda, \mu \in [0,1]\} \\ 

\,[x, 2]^* & = & \{x + \lambda e_1 + \mu e_3 : \lambda, \mu \in [0,1]\} \\ 

\,[x, 3]^* & = & \{x + \lambda e_1 + \mu e_2 : \lambda, \mu \in [0,1]\} 

\end{array} 

and the dual substitution `E_1^*(\sigma)` is defined by 

.. MATH:: 

E_1^*(\sigma)([x,i]^*) = 

\bigcup_{k = 1,2,3} \; \bigcup_{s | \sigma(k) = pis} 

[M^{-1}(x + \ell(s)), k]^*, 

where `\ell(s)` is the abelianized of `s`, and `M` is the matrix of `\sigma`. 

AUTHORS: 

- Franco Saliola (2009): initial version 

- Vincent Delecroix, Timo Jolivet, Stepan Starosta, Sebastien Labbe (2010-05): redesign 

- Timo Jolivet (2010-08, 2010-09, 2011): redesign 

REFERENCES: 

.. [AI] \P. Arnoux, S. Ito, 

Pisot substitutions and Rauzy fractals, 

Bull. Belg. Math. Soc. 8 (2), 2001, pp. 181--207 

.. [SAI] \Y. Sano, P. Arnoux, S. Ito, 

Higher dimensional extensions of substitutions and their dual maps, 

J. Anal. Math. 83, 2001, pp. 183--206 

EXAMPLES: 

We start by drawing a simple three-face patch:: 

sage: from sage.combinat.e_one_star import E1Star, Face, Patch 

sage: x = [Face((0,0,0),1), Face((0,0,0),2), Face((0,0,0),3)] 

sage: P = Patch(x) 

sage: P 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(0, 0, 0), 3]*] 

sage: P.plot() #not tested 

We apply a substitution to this patch, and draw the result:: 

sage: sigma = WordMorphism({1:[1,2], 2:[1,3], 3:[1]}) 

sage: E = E1Star(sigma) 

sage: E(P) 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(0, 0, 0), 3]*, [(0, 1, -1), 2]*, [(1, 0, -1), 1]*] 

sage: E(P).plot() #not tested 

.. NOTE:: 

- The type of a face is given by an integer in ``[1, ..., d]`` 

where ``d`` is the length of the vector of the face. 

- The alphabet of the domain and the codomain of `\sigma` must be 

equal, and they must be of the form ``[1, ..., d]``, where ``d`` 

is a positive integer corresponding to the length of the vectors 

of the faces on which `E_1^*(\sigma)` will act. 

:: 

sage: P = Patch([Face((0,0,0),1), Face((0,0,0),2), Face((0,0,0),3)]) 

sage: sigma = WordMorphism({1:[1,2], 2:[1,3], 3:[1]}) 

sage: E = E1Star(sigma) 

sage: E(P) 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(0, 0, 0), 3]*, [(0, 1, -1), 2]*, [(1, 0, -1), 1]*] 

The application of an ``E1Star`` substitution assigns to each new face the color of its preimage. 

The ``repaint`` method allows us to repaint the faces of a patch. 

A single color can also be assigned to every face, by specifying a list of a single color:: 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P = E(P, 5) 

sage: P.repaint(['green']) 

sage: P.plot() #not tested 

A list of colors allows us to color the faces sequentially:: 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P = E(P) 

sage: P.repaint(['red', 'yellow', 'green', 'blue', 'black']) 

sage: P = E(P, 3) 

sage: P.plot() #not tested 

All the color schemes from ``list(matplotlib.cm.datad)`` can be used:: 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P.repaint(cmap='summer') 

sage: P = E(P, 3) 

sage: P.plot() #not tested 

sage: P.repaint(cmap='hsv') 

sage: P = E(P, 2) 

sage: P.plot() #not tested 

It is also possible to specify a dictionary to color the faces according to their type:: 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P = E(P, 5) 

sage: P.repaint({1:(0.7, 0.7, 0.7), 2:(0.5,0.5,0.5), 3:(0.3,0.3,0.3)}) 

sage: P.plot() #not tested 

sage: P.repaint({1:'red', 2:'yellow', 3:'green'}) 

sage: P.plot() #not tested 

Let us look at a nice big patch in 3D:: 

sage: sigma = WordMorphism({1:[1,2], 2:[3], 3:[1]}) 

sage: E = E1Star(sigma) 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P = P + P.translate([-1,1,0]) 

sage: P = E(P, 11) 

sage: P.plot3d() #not tested 

Plotting with TikZ pictures is possible:: 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: s = P.plot_tikz() 

sage: print(s) #not tested 

\begin{tikzpicture} 

[x={(-0.216506cm,-0.125000cm)}, y={(0.216506cm,-0.125000cm)}, z={(0.000000cm,0.250000cm)}] 

\definecolor{facecolor}{rgb}{0.000,1.000,0.000} 

\fill[fill=facecolor, draw=black, shift={(0,0,0)}] 

(0, 0, 0) -- (0, 0, 1) -- (1, 0, 1) -- (1, 0, 0) -- cycle; 

\definecolor{facecolor}{rgb}{1.000,0.000,0.000} 

\fill[fill=facecolor, draw=black, shift={(0,0,0)}] 

(0, 0, 0) -- (0, 1, 0) -- (0, 1, 1) -- (0, 0, 1) -- cycle; 

\definecolor{facecolor}{rgb}{0.000,0.000,1.000} 

\fill[fill=facecolor, draw=black, shift={(0,0,0)}] 

(0, 0, 0) -- (1, 0, 0) -- (1, 1, 0) -- (0, 1, 0) -- cycle; 

\end{tikzpicture} 

Plotting patches made of unit segments instead of unit faces:: 

sage: P = Patch([Face([0,0], 1), Face([0,0], 2)]) 

sage: E = E1Star(WordMorphism({1:[1,2],2:[1]})) 

sage: F = E1Star(WordMorphism({1:[1,1,2],2:[2,1]})) 

sage: E(P,5).plot() 

Graphics object consisting of 21 graphics primitives 

sage: F(P,3).plot() 

Graphics object consisting of 34 graphics primitives 

Everything works in any dimension (except for the plotting features 

which only work in dimension two or three):: 

sage: P = Patch([Face((0,0,0,0),1), Face((0,0,0,0),4)]) 

sage: sigma = WordMorphism({1:[1,2], 2:[1,3], 3:[1,4], 4:[1]}) 

sage: E = E1Star(sigma) 

sage: E(P) 

Patch: [[(0, 0, 0, 0), 3]*, [(0, 0, 0, 0), 4]*, [(0, 0, 1, -1), 3]*, [(0, 1, 0, -1), 2]*, [(1, 0, 0, -1), 1]*] 

:: 

sage: sigma = WordMorphism({1:[1,2],2:[1,3],3:[1,4],4:[1,5],5:[1,6],6:[1,7],7:[1,8],8:[1,9],9:[1,10],10:[1,11],11:[1,12],12:[1]}) 

sage: E = E1Star(sigma) 

sage: E 

E_1^*(1->12, 10->1,11, 11->1,12, 12->1, 2->13, 3->14, 4->15, 5->16, 6->17, 7->18, 8->19, 9->1,10) 

sage: P = Patch([Face((0,0,0,0,0,0,0,0,0,0,0,0),t) for t in [1,2,3]]) 

sage: for x in sorted(list(E(P)), key=lambda x : (x.vector(),x.type())): print(x) 

[(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1]* 

[(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), 2]* 

[(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), 12]* 

[(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1), 11]* 

[(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, -1), 10]* 

[(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -1), 9]* 

[(0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, -1), 8]* 

[(0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, -1), 7]* 

[(0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1), 6]* 

[(0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, -1), 5]* 

[(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, -1), 4]* 

[(0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, -1), 3]* 

[(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1), 2]* 

[(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1), 1]* 

""" 

#***************************************************************************** 

# Copyright (C) 2010 Franco Saliola <saliola@gmail.com> 

# Vincent Delecroix <20100.delecroix@gmail.com> 

# Timo Jolivet <timo.jolivet@gmail.com> 

# Stepan Starosta <stepan.starosta@gmail.com> 

# Sebastien Labbe <slabqc at gmail.com> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# as published by the Free Software Foundation; either version 2 of 

# the License, or (at your option) any later version. 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from six.moves import range 

from sage.misc.functional import det 

from sage.structure.sage_object import SageObject 

from sage.combinat.words.morphism import WordMorphism 

from sage.matrix.constructor import matrix 

from sage.modules.free_module_element import vector 

from sage.plot.all import Graphics 

from sage.plot.colors import Color 

from sage.plot.polygon import polygon 

from sage.plot.line import line 

from sage.rings.integer_ring import ZZ 

from sage.misc.latex import LatexExpr 

from sage.misc.cachefunc import cached_method 

from sage.structure.richcmp import richcmp_by_eq_and_lt, richcmp_method 

# matplotlib color maps, loaded on-demand 

cm = None 

@richcmp_method 

class Face(SageObject): 

r""" 

A class to model a unit face of arbitrary dimension. 

A unit face in dimension `d` is represented by 

a `d`-dimensional vector ``v`` and a type ``t`` in `\{1, \ldots, d\}`. 

The type of the face corresponds to the canonical unit vector 

to which the face is orthogonal. 

The optional ``color`` argument is used in plotting functions. 

INPUT: 

- ``v`` - tuple of integers 

- ``t`` - integer in ``[1, ..., len(v)]``, type of the face. The face of type `i` 

is orthogonal to the canonical vector `e_i`. 

- ``color`` - color (optional, default: ``None``) color of the face, 

used for plotting only. If ``None``, its value is guessed from the 

face type. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face((0,2,0), 3) 

sage: f.vector() 

(0, 2, 0) 

sage: f.type() 

3 

:: 

sage: f = Face((0,2,0), 3, color=(0.5, 0.5, 0.5)) 

sage: f.color() 

RGB color (0.5, 0.5, 0.5) 

""" 

def __init__(self, v, t, color=None): 

r""" 

Face constructor. See class doc for more information. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face((0,2,0), 3) 

sage: f.vector() 

(0, 2, 0) 

sage: f.type() 

3 

TESTS: 

We test that types can be given by an int (see :trac:`10699`):: 

sage: f = Face((0,2,0), int(1)) 

""" 

self._vector = (ZZ**len(v))(v) 

self._vector.set_immutable() 

if not((t in ZZ) and 1 <= t <= len(v)): 

raise ValueError('The type must be an integer between 1 and len(v)') 

self._type = t 

if color is None: 

if self._type == 1: 

color = Color((1,0,0)) 

elif self._type == 2: 

color = Color((0,1,0)) 

elif self._type == 3: 

color = Color((0,0,1)) 

else: 

color = Color() 

self._color = Color(color) 

def __repr__(self): 

r""" 

String representation of a face. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face((0,0,0,3), 3) 

sage: f 

[(0, 0, 0, 3), 3]* 

:: 

sage: f = Face((0,0,0,3), 3) 

sage: f 

[(0, 0, 0, 3), 3]* 

""" 

return "[%s, %s]*" % (self.vector(), self.type()) 

__richcmp__ = richcmp_by_eq_and_lt('_eq', '_lt') 

def _eq(self, other): 

r""" 

Equality of faces. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face((0,0,0,3), 3) 

sage: g = Face((0,0,0,3), 3) 

sage: f == g 

True 

""" 

return (isinstance(other, Face) and 

self.vector() == other.vector() and 

self.type() == other.type() ) 

def _lt(self, other): 

r""" 

Compare ``self`` and ``other``. 

The vectors of the faces are first compared, 

and the types of the faces are compared if the vectors are equal. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: Face([-2,1,0], 2) < Face([-1,2,2],3) 

True 

sage: Face([-2,1,0], 2) < Face([-2,1,0],3) 

True 

sage: Face([-2,1,0], 2) < Face([-2,1,0],2) 

False 

""" 

if self.vector() < other.vector(): 

return True 

if self.vector() == other.vector(): 

return self.type() < other.type() 

def __hash__(self): 

r""" 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face((0,0,0,3), 3) 

sage: g = Face((0,0,0,3), 3) 

sage: hash(f) == hash(g) 

True 

""" 

return hash((self.vector(), self.type())) 

def __add__(self, other): 

r""" 

Addition of self with a Face, a Patch or a finite iterable of faces. 

INPUT: 

- ``other`` - a Patch or a Face or a finite iterable of faces 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: f = Face([0,0,0], 3) 

sage: g = Face([0,1,-1], 2) 

sage: f + g 

Patch: [[(0, 0, 0), 3]*, [(0, 1, -1), 2]*] 

sage: P = Patch([Face([0,0,0], 1), Face([0,0,0], 2)]) 

sage: f + P 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(0, 0, 0), 3]*] 

Adding a finite iterable of faces:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face([0,0,0], 3) 

sage: f + [f,f] 

Patch: [[(0, 0, 0), 3]*] 

""" 

if isinstance(other, Face): 

return Patch([self, other]) 

else: 

return Patch(other).union(self) 

def vector(self): 

r""" 

Return the vector of the face. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face((0,2,0), 3) 

sage: f.vector() 

(0, 2, 0) 

""" 

return self._vector 

def type(self): 

r""" 

Return the type of the face. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face((0,2,0), 3) 

sage: f.type() 

3 

:: 

sage: f = Face((0,2,0), 3) 

sage: f.type() 

3 

""" 

return self._type 

def color(self, color=None): 

r""" 

Return or change the color of the face. 

INPUT: 

- ``color`` - string, rgb tuple, color (optional, default: ``None``) 

the new color to assign to the face. If ``None``, it returns the 

color of the face. 

OUTPUT: 

color 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face((0,2,0), 3) 

sage: f.color() 

RGB color (0.0, 0.0, 1.0) 

sage: f.color('red') 

sage: f.color() 

RGB color (1.0, 0.0, 0.0) 

""" 

if color is None: 

return self._color 

else: 

self._color = Color(color) 

def _plot(self, projmat, face_contour, opacity): 

r""" 

Return a 2D graphic object representing the face. 

INPUT: 

- ``projmat`` - 2*3 projection matrix (used only for faces in three dimensions) 

- ``face_contour`` - dict, maps the face type to vectors describing 

the contour of unit faces (used only for faces in three dimensions) 

- ``opacity`` - the alpha value for the color of the face 

OUTPUT: 

2D graphic object 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face((0,0,3), 3) 

sage: projmat = matrix(2, [-1.7320508075688772*0.5, 1.7320508075688772*0.5, 0, -0.5, -0.5, 1]) 

sage: face_contour = {} 

sage: face_contour[1] = map(vector, [(0,0,0),(0,1,0),(0,1,1),(0,0,1)]) 

sage: face_contour[2] = map(vector, [(0,0,0),(0,0,1),(1,0,1),(1,0,0)]) 

sage: face_contour[3] = map(vector, [(0,0,0),(1,0,0),(1,1,0),(0,1,0)]) 

sage: G = f._plot(projmat, face_contour, 0.75) 

:: 

sage: f = Face((0,0), 2) 

sage: f._plot(None, None, 1) 

Graphics object consisting of 1 graphics primitive 

""" 

v = self.vector() 

t = self.type() 

G = Graphics() 

if len(v) == 2: 

if t == 1: 

G += line([v, v + vector([0,1])], rgbcolor=self.color(), thickness=1.5, alpha=opacity) 

elif t == 2: 

G += line([v, v + vector([1,0])], rgbcolor=self.color(), thickness=1.5, alpha=opacity) 

elif len(v) == 3: 

G += polygon([projmat*(u+v) for u in face_contour[t]], alpha=opacity, 

thickness=1, rgbcolor=self.color()) 

else: 

raise NotImplementedError("Plotting is implemented only for patches in two or three dimensions.") 

return G 

def _plot3d(self, face_contour): 

r""" 

3D representation of a unit face (Jmol). 

INPUT: 

- ``face_contour`` - dict, maps the face type to vectors describing 

the contour of unit faces 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face 

sage: f = Face((0,0,3), 3) 

sage: face_contour = {1: map(vector, [(0,0,0),(0,1,0),(0,1,1),(0,0,1)]), 2: map(vector, [(0,0,0),(0,0,1),(1,0,1),(1,0,0)]), 3: map(vector, [(0,0,0),(1,0,0),(1,1,0),(0,1,0)])} 

sage: G = f._plot3d(face_contour) #not tested 

""" 

v = self.vector() 

t = self.type() 

c = self.color() 

G = polygon([u+v for u in face_contour[t]], rgbcolor=c) 

return G 

class Patch(SageObject): 

r""" 

A class to model a collection of faces. A patch is represented by an immutable set of Faces. 

.. NOTE:: 

The dimension of a patch is the length of the vectors of the faces in the patch, 

which is assumed to be the same for every face in the patch. 

.. NOTE:: 

Since version 4.7.1, Patches are immutable, except for the colors of the faces, 

which are not taken into account for equality tests and hash functions. 

INPUT: 

- ``faces`` - finite iterable of faces 

- ``face_contour`` - dict (optional, default:``None``) maps the face 

type to vectors describing the contour of unit faces. If None, 

defaults contour are assumed for faces of type 1, 2, 3 or 1, 2, 3. 

Used in plotting methods only. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(0, 0, 0), 3]*] 

:: 

sage: face_contour = {} 

sage: face_contour[1] = map(vector, [(0,0,0),(0,1,0),(0,1,1),(0,0,1)]) 

sage: face_contour[2] = map(vector, [(0,0,0),(0,0,1),(1,0,1),(1,0,0)]) 

sage: face_contour[3] = map(vector, [(0,0,0),(1,0,0),(1,1,0),(0,1,0)]) 

sage: Patch([Face((0,0,0),t) for t in [1,2,3]], face_contour=face_contour) 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(0, 0, 0), 3]*] 

""" 

def __init__(self, faces, face_contour=None): 

r""" 

Constructor of a patch (set of faces). See class doc for more information. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(0, 0, 0), 3]*] 

TESTS: 

We test that colors are not anymore mixed up between 

Patches (see :trac:`11255`):: 

sage: P = Patch([Face([0,0,0],2)]) 

sage: Q = Patch(P) 

sage: next(iter(P)).color() 

RGB color (0.0, 1.0, 0.0) 

sage: next(iter(Q)).color('yellow') 

sage: next(iter(P)).color() 

RGB color (0.0, 1.0, 0.0) 

""" 

self._faces = frozenset(Face(f.vector(), f.type(), f.color()) for f in faces) 

try: 

f0 = next(iter(self._faces)) 

except StopIteration: 

self._dimension = None 

else: 

self._dimension = len(f0.vector()) 

if not face_contour is None: 

self._face_contour = face_contour 

else: 

self._face_contour = { 

1: [vector(_) for _ in [(0,0,0),(0,1,0),(0,1,1),(0,0,1)]], 

2: [vector(_) for _ in [(0,0,0),(0,0,1),(1,0,1),(1,0,0)]], 

3: [vector(_) for _ in [(0,0,0),(1,0,0),(1,1,0),(0,1,0)]] 

} 

def __eq__(self, other): 

r""" 

Equality test for Patch. 

INPUT: 

- ``other`` - an object 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import E1Star, Face, Patch 

sage: P = Patch([Face((0,0,0),1), Face((0,0,0),2), Face((0,0,0),3)]) 

sage: Q = Patch([Face((0,1,0),1), Face((0,0,0),3)]) 

sage: P == P 

True 

sage: P == Q 

False 

sage: P == 4 

False 

:: 

sage: s = WordMorphism({1:[1,3], 2:[1,2,3], 3:[3]}) 

sage: t = WordMorphism({1:[1,2,3], 2:[2,3], 3:[3]}) 

sage: P = Patch([Face((0,0,0), 1), Face((0,0,0), 2), Face((0,0,0), 3)]) 

sage: E1Star(s)(P) == E1Star(t)(P) 

False 

sage: E1Star(s*t)(P) == E1Star(t)(E1Star(s)(P)) 

True 

""" 

return (isinstance(other, Patch) and self._faces == other._faces) 

def __hash__(self): 

r""" 

Hash function of Patch. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: x = [Face((0,0,0),t) for t in [1,2,3]] 

sage: P = Patch(x) 

sage: hash(P) #random 

-4839605361791007520 

TESTS: 

We test that two equal patches have the same hash (see :trac:`11255`):: 

sage: P = Patch([Face([0,0,0],1), Face([0,0,0],2)]) 

sage: Q = Patch([Face([0,0,0],2), Face([0,0,0],1)]) 

sage: P == Q 

True 

sage: hash(P) == hash(Q) 

True 

Changing the color does not affect the hash value:: 

sage: p = Patch([Face((0,0,0), t) for t in [1,2,3]]) 

sage: H1 = hash(p) 

sage: p.repaint(['blue']) 

sage: H2 = hash(p) 

sage: H1 == H2 

True 

""" 

return hash(self._faces) 

def __len__(self): 

r""" 

Return the number of faces contained in the patch. 

OUTPUT: 

integer 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: x = [Face((0,0,0),t) for t in [1,2,3]] 

sage: P = Patch(x) 

sage: len(P) #indirect doctest 

3 

""" 

return len(self._faces) 

def __iter__(self): 

r""" 

Return an iterator over the faces of the patch. 

OUTPUT: 

iterator 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: x = [Face((0,0,0),t) for t in [1,2,3]] 

sage: P = Patch(x) 

sage: it = iter(P) 

sage: type(next(it)) 

<class 'sage.combinat.e_one_star.Face'> 

sage: type(next(it)) 

<class 'sage.combinat.e_one_star.Face'> 

sage: type(next(it)) 

<class 'sage.combinat.e_one_star.Face'> 

sage: type(next(it)) 

Traceback (most recent call last): 

... 

StopIteration 

""" 

return iter(self._faces) 

def __add__(self, other): 

r""" 

Addition of patches (union). 

INPUT: 

- ``other`` - a Patch or a Face or a finite iterable of faces 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face([0,0,0], 1), Face([0,0,0], 2)]) 

sage: Q = P.translate([1,-1,0]) 

sage: P + Q 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(1, -1, 0), 1]*, [(1, -1, 0), 2]*] 

sage: P + Face([0,0,0],3) 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(0, 0, 0), 3]*] 

sage: P + [Face([0,0,0],3), Face([1,1,1],2)] 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(0, 0, 0), 3]*, [(1, 1, 1), 2]*] 

""" 

return self.union(other) 

def __sub__(self, other): 

r""" 

Subtraction of patches (difference). 

INPUT: 

- ``other`` - a Patch or a Face or a finite iterable of faces 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P - Face([0,0,0],2) 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 3]*] 

sage: P - P 

Patch: [] 

""" 

return self.difference(other) 

def __repr__(self): 

r""" 

String representation of a patch. 

Displays all the faces if there less than 20, 

otherwise displays only the number of faces. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: x = [Face((0,0,0),t) for t in [1,2,3]] 

sage: P = Patch(x) 

sage: P 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(0, 0, 0), 3]*] 

:: 

sage: x = [Face((0,0,a),1) for a in range(25)] 

sage: P = Patch(x) 

sage: P 

Patch of 25 faces 

""" 

if len(self) <= 20: 

L = list(self) 

L.sort(key=lambda x : (x.vector(),x.type())) 

return "Patch: %s"%L 

else: 

return "Patch of %s faces"%len(self) 

def union(self, other): 

r""" 

Return a Patch consisting of the union of self and other. 

INPUT: 

- ``other`` - a Patch or a Face or a finite iterable of faces 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face((0,0,0),1), Face((0,0,0),2)]) 

sage: P.union(Face((1,2,3), 3)) 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(1, 2, 3), 3]*] 

sage: P.union([Face((1,2,3), 3), Face((2,3,3), 2)]) 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 2]*, [(1, 2, 3), 3]*, [(2, 3, 3), 2]*] 

""" 

if isinstance(other, Face): 

return Patch(self._faces.union([other])) 

else: 

return Patch(self._faces.union(other)) 

def difference(self, other): 

r""" 

Return the difference of self and other. 

INPUT: 

- ``other`` - a finite iterable of faces or a single face 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P.difference(Face([0,0,0],2)) 

Patch: [[(0, 0, 0), 1]*, [(0, 0, 0), 3]*] 

sage: P.difference(P) 

Patch: [] 

""" 

if isinstance(other, Face): 

return Patch(self._faces.difference([other])) 

else: 

return Patch(self._faces.difference(other)) 

def dimension(self): 

r""" 

Return the dimension of the vectors of the faces of self 

It returns ``None`` if self is the empty patch. 

The dimension of a patch is the length of the vectors of the faces in the patch, 

which is assumed to be the same for every face in the patch. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P.dimension() 

3 

TESTS:: 

sage: from sage.combinat.e_one_star import Patch 

sage: p = Patch([]) 

sage: p.dimension() is None 

True 

It works when the patch is created from an iterator:: 

sage: p = Patch(Face((0,0,0),t) for t in [1,2,3]) 

sage: p.dimension() 

3 

""" 

return self._dimension 

def faces_of_vector(self, v): 

r""" 

Return a list of the faces whose vector is ``v``. 

INPUT: 

- ``v`` - a vector 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face((0,0,0),1), Face((1,2,0),3), Face((1,2,0),1)]) 

sage: P.faces_of_vector([1,2,0]) 

[[(1, 2, 0), 3]*, [(1, 2, 0), 1]*] 

""" 

v = vector(v) 

return [f for f in self if f.vector() == v] 

def faces_of_type(self, t): 

r""" 

Return a list of the faces that have type ``t``. 

INPUT: 

- ``t`` - integer or any other type 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face((0,0,0),1), Face((1,2,0),3), Face((1,2,0),1)]) 

sage: P.faces_of_type(1) 

[[(0, 0, 0), 1]*, [(1, 2, 0), 1]*] 

""" 

return [f for f in self if f.type() == t] 

def faces_of_color(self, color): 

r""" 

Return a list of the faces that have the given color. 

INPUT: 

- ``color`` - color 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face((0,0,0),1, 'red'), Face((1,2,0),3, 'blue'), Face((1,2,0),1, 'red')]) 

sage: P.faces_of_color('red') 

[[(0, 0, 0), 1]*, [(1, 2, 0), 1]*] 

""" 

color = tuple(Color(color)) 

return [f for f in self if tuple(f.color()) == color] 

def translate(self, v): 

r""" 

Return a translated copy of self by vector ``v``. 

INPUT: 

- ``v`` - vector or tuple 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: P = Patch([Face((0,0,0),1), Face((1,2,0),3), Face((1,2,0),1)]) 

sage: P.translate([-1,-2,0]) 

Patch: [[(-1, -2, 0), 1]*, [(0, 0, 0), 1]*, [(0, 0, 0), 3]*] 

""" 

v = vector(v) 

return Patch(Face(f.vector()+v, f.type(), f.color()) for f in self) 

def occurrences_of(self, other): 

r""" 

Return all positions at which other appears in self, that is, 

all vectors v such that ``set(other.translate(v)) <= set(self)``. 

INPUT: 

- ``other`` - a Patch 

OUTPUT: 

a list of vectors 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import Face, Patch, E1Star 

sage: P = Patch([Face([0,0,0], 1), Face([0,0,0], 2), Face([0,0,0], 3)]) 

sage: Q = Patch([Face([0,0,0], 1), Face([0,0,0], 2)]) 

sage: P.occurrences_of(Q) 

[(0, 0, 0)] 

sage: Q = Q.translate([1,2,3]) 

sage: P.occurrences_of(Q) 

[(-1, -2, -3)] 

:: 

sage: E = E1Star(WordMorphism({1:[1,2], 2:[1,3], 3:[1]})) 

sage: P = Patch([Face([0,0,0], 1), Face([0,0,0], 2), Face([0,0,0], 3)]) 

sage: P = E(P,4) 

sage: Q = Patch([Face([0,0,0], 1), Face([0,0,0], 2)]) 

sage: L = P.occurrences_of(Q) 

sage: sorted(L) 

[(0, 0, 0), (0, 0, 1), (0, 1, -1), (1, 0, -1), (1, 1, -3), (1, 1, -2)] 

""" 

f0 = next(iter(other)) 

x = f0.vector() 

t = f0.type() 

L = self.faces_of_type(t) 

positions = [] 

for f in L: 

y = f.vector() 

if other.translate(y-x)._faces.issubset(self._faces): 

positions.append(y-x) 

return positions 

def repaint(self, cmap='Set1'): 

r""" 

Repaints all the faces of self from the given color map. 

This only changes the colors of the faces of self. 

INPUT: 

- ``cmap`` - color map (default: ``'Set1'``). It can be one of the 

following : 

- string -- A coloring map. For available coloring map names type: 

``sorted(colormaps)`` 

- list -- a list of colors to assign cyclically to the faces. 

A list of a single color colors all the faces with the same color. 

- dict -- a dict of face types mapped to colors, to color the 

faces according to their type. 

- ``{}``, the empty dict - shortcut for 

``{1:'red', 2:'green', 3:'blue'}``. 

EXAMPLES: 

Using a color map:: 

sage: from sage.combinat.e_one_star import Face, Patch 

sage: color = (0, 0, 0) 

sage: P = Patch([Face((0,0,0),t,color) for t in [1,2,3]]) 

sage: for f in P: f.color() 

RGB color (0.0, 0.0, 0.0) 

RGB color (0.0, 0.0, 0.0) 

RGB color (0.0, 0.0, 0.0) 

sage: P.repaint() 

sage: next(iter(P)).color() #random 

RGB color (0.498..., 0.432..., 0.522...) 

Using a list of colors:: 

sage: P = Patch([Face((0,0,0),t,color) for t in [1,2,3]]) 

sage: P.repaint([(0.9, 0.9, 0.9), (0.65,0.65,0.65), (0.4,0.4,0.4)]) 

sage: for f in P: f.color() 

RGB color (0.9, 0.9, 0.9) 

RGB color (0.65, 0.65, 0.65) 

RGB color (0.4, 0.4, 0.4) 

Using a dictionary to color faces according to their type:: 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P.repaint({1:'black', 2:'yellow', 3:'green'}) 

sage: P.plot() #not tested 

sage: P.repaint({}) 

sage: P.plot() #not tested 

""" 

if cmap == {}: 

cmap = {1: 'red', 2:'green', 3:'blue'} 

if isinstance(cmap, dict): 

for f in self: 

f.color(cmap[f.type()]) 

elif isinstance(cmap, list): 

L = len(cmap) 

for i, f in enumerate(self): 

f.color(cmap[i % L]) 

elif isinstance(cmap, str): 

# matplotlib color maps 

global cm 

if not cm: 

from matplotlib import cm 

if not cmap in cm.datad: 

raise RuntimeError("Color map %s not known (type sorted(colors) for valid names)" % cmap) 

cmap = cm.__dict__[cmap] 

dim = float(len(self)) 

for i,f in enumerate(self): 

f.color(cmap(i/dim)[:3]) 

else: 

raise TypeError("Type of cmap (=%s) must be dict, list or str" %cmap) 

def plot(self, projmat=None, opacity=0.75): 

r""" 

Return a 2D graphic object depicting the patch. 

INPUT: 

- ``projmat`` - matrix (optional, default: ``None``) the projection 

matrix. Its number of lines must be two. Its number of columns 

must equal the dimension of the ambient space of the faces. If 

``None``, the isometric projection is used by default. 

- ``opacity`` - float between ``0`` and ``1`` (optional, default: ``0.75``) 

opacity of the face 

.. WARNING:: 

Plotting is implemented only for patches in two or three dimensions. 

EXAMPLES:: 

sage: from sage.combinat.e_one_star import E1Star, Face, Patch 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P.plot() 

Graphics object consisting of 3 graphics primitives 

:: 

sage: sigma = WordMorphism({1:[1,2], 2:[1,3], 3:[1]}) 

sage: E = E1Star(sigma) 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: P = E(P, 5) 

sage: P.plot() 

Graphics object consisting of 57 graphics primitives 

Plot with a different projection matrix:: 

sage: sigma = WordMorphism({1:[1,2], 2:[1,3], 3:[1]}) 

sage: E = E1Star(sigma) 

sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]]) 

sage: M = matrix(2, 3, [1,0,-1,0.3,1,-3]) 

sage: P = E(P, 3) 

sage: P.plot(projmat=M) 

Graphics object consisting of 17 graphics primitives 

Plot patches made of unit segments:: 

sage: P = Patch([Face([0,0], 1), Face([0,0], 2)]) 

sage: E = E1Star(WordMorphism({1:[1,2],2:[1]})) 

sage: F = E1Star(WordMorphism({1:[1,1,2],2:[2,1]})) 

sage: E(P,5).plot() 

Graphics object consisting of 21 graphics primitives 

sage: F(P,3).plot() 

Graphics object consisting of 34 graphics primitives 

""" 

if self.dimension() == 2: 

G = Graphics() 

for face in self: 

G += face._plot(None, None, 1) 

G.set_aspect_ratio(1) 

return G 

if self.dimension() == 3: 

if projmat is None: 

projmat = matrix(2, [-1.7320508075688772*0.5, 1.7320508075688772*0.5, 0, -0.5, -0.5, 1]) 

G = Graphics() 

for face in self: 

G += face._plot(projmat, self._face_contour, opacity) 

G.set_aspect_ratio(1) 

return G 

else: 

raise NotImplementedError("Plotting is implemented only for patches in two or three dimensions.") 

def plot3d(self):