2
/**************************************************************************
4
* Regina - A Normal Surface Theory Calculator *
5
* Computational Engine *
7
* Copyright (c) 1999-2013, Ben Burton *
8
* For further details contact Ben Burton (bab@debian.org). *
10
* This program is free software; you can redistribute it and/or *
11
* modify it under the terms of the GNU General Public License as *
12
* published by the Free Software Foundation; either version 2 of the *
13
* License, or (at your option) any later version. *
15
* As an exception, when this program is distributed through (i) the *
16
* App Store by Apple Inc.; (ii) the Mac App Store by Apple Inc.; or *
17
* (iii) Google Play by Google Inc., then that store may impose any *
18
* digital rights management, device limits and/or redistribution *
19
* restrictions that are required by its terms of service. *
21
* This program is distributed in the hope that it will be useful, but *
22
* WITHOUT ANY WARRANTY; without even the implied warranty of *
23
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
24
* General Public License for more details. *
26
* You should have received a copy of the GNU General Public *
27
* License along with this program; if not, write to the Free *
28
* Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, *
29
* MA 02110-1301, USA. *
31
**************************************************************************/
35
/*! \file generic/ngenericisomorphism.h
36
* \brief Deals with combinatorial isomorphisms of \a n-manifold
40
#ifndef __NGENERALISOMORPHISM_H
42
#define __NGENERALISOMORPHISM_H
45
#include "regina-core.h"
46
#include "shareableobject.h"
47
#include "generic/dimtraits.h"
48
#include "generic/nfacetspec.h"
58
* A dimension-agnostic base class that represents a combinatorial
59
* isomorphism from one \a dim-manifold triangulation into another.
61
* Each dimension that Regina works with (2, 3 and 4) offers its own
62
* subclass with richer functionality; users typically do not need to
63
* work with this template base class directly.
65
* In essence, a combinatorial isomorphism from triangulation T to
66
* triangulation U is a one-to-one map from the simplices of T to the
67
* simplices of U that allows relabelling of both the simplices and
68
* their facets (or equivalently, their vertices), and that preserves
69
* gluings across adjacent simplices.
71
* More precisely: An isomorphism consists of (i) a one-to-one map f
72
* from the simplices of T to the simplices of U, and (ii) for each
73
* simplex S of T, a permutation f_S of the facets (0,...,\a dim) of S,
74
* for which the following condition holds:
76
* - If facet k of simplex S and facet k' of simplex S'
77
* are identified in T, then facet f_S(k) of f(S) and facet f_S'(k')
78
* of f(S') are identified in U. Moreover, their gluing is consistent
79
* with the facet/vertex permutations; that is, there is a commutative
80
* square involving the gluing maps in T and U and the permutations
83
* Isomorphisms can be <i>boundary complete</i> or
84
* <i>boundary incomplete</i>. A boundary complete isomorphism
85
* satisfies the additional condition:
87
* - If facet x is a boundary facet of T then facet f(x) is a boundary
90
* A boundary complete isomorphism thus indicates that a copy of
91
* triangulation T is present as an entire component (or components) of U,
92
* whereas a boundary incomplete isomorphism represents an embedding of a
93
* copy of triangulation T as a subcomplex of some possibly larger component
94
* (or components) of U.
96
* Note that in all cases triangulation U may contain more simplices
97
* than triangulation T.
99
* \pre The dimension argument \a dim is either 2, 3 or 4.
101
* \ifacespython Not present, though the dimension-specific subclasses
102
* (such as NIsomorphism and Dim4Isomorphism) are available for Python users.
107
class REGINA_API NGenericIsomorphism : public ShareableObject {
109
typedef typename DimTraits<dim>::Isomorphism Isomorphism;
110
/**< The isomorphism class used by triangulations of this
111
specific dimension. Typically this is a subclass of
112
NGenericIsomorphism<dim>. */
113
typedef typename DimTraits<dim>::Perm Perm;
114
/**< The permutation class used to glue together facets of
115
simplices when building triangulations in this dimension. */
116
typedef typename DimTraits<dim>::Simplex Simplex;
117
/**< The class that represents a top-level simplex of a
118
triangulation in this dimension. */
119
typedef typename DimTraits<dim>::Triangulation Triangulation;
120
/**< The triangulation class specific to this dimension. */
123
unsigned nSimplices_;
124
/**< The number of simplices in the source triangulation. */
126
/**< The simplex of the destination triangulation that
127
each simplex of the source triangulation maps to. */
129
/**< The permutation applied to the facets of each
134
* Creates a new isomorphism with no initialisation.
136
* @param nSimplices the number of simplices in the source
137
* triangulation associated with this isomorphism; this may be zero.
139
NGenericIsomorphism(unsigned nSimplices);
141
* Creates a new isomorphism identical to the given isomorphism.
143
* @param cloneMe the isomorphism upon which to base the new
146
NGenericIsomorphism(const NGenericIsomorphism& cloneMe);
148
* Destroys this isomorphism.
150
~NGenericIsomorphism();
153
* Returns the number of simplices in the source triangulation
154
* associated with this isomorphism. Note that this is always
155
* less than or equal to the number of simplices in the
156
* destination triangulation.
158
* @return the number of simplices in the source triangulation.
160
unsigned getSourceSimplices() const;
163
* Determines the image of the given source simplex under
166
* \ifacespython This is not available for Python users, even in
167
* the dimension-specific subclasses. However, the read-only
168
* version of this routine is.
170
* @param sourceSimp the index of the source simplex; this must
171
* be between 0 and <tt>getSourceSimplices()-1</tt> inclusive.
172
* @return a reference to the index of the destination simplex
173
* that the source simplex maps to.
175
int& simpImage(unsigned sourceSimp);
177
* Determines the image of the given source simplex under
180
* @param sourceSimp the index of the source simplex; this must
181
* be between 0 and <tt>getSourceSimplices()-1</tt> inclusive.
182
* @return the index of the destination simplex
183
* that the source simplex maps to.
185
int simpImage(unsigned sourceSimp) const;
187
* Returns a read-write reference to the permutation that is
188
* applied to the (\a dim + 1) facets of the given source simplex
189
* under this isomorphism.
190
* Facet \a i of source simplex \a sourceSimp will be mapped to
191
* facet <tt>facetPerm(sourceSimp)[i]</tt> of simplex
192
* <tt>simpImage(sourceSimp)</tt>.
194
* \ifacespython This is not available for Python users, even in
195
* the dimension-specific subclasses. However, the read-only
196
* version of this routine is.
198
* @param sourceSimp the index of the source simplex containing
199
* the original (\a dim + 1) facets; this must be between 0 and
200
* <tt>getSourceSimplices()-1</tt> inclusive.
201
* @return a read-write reference to the permutation applied to the
202
* facets of the source simplex.
204
Perm& facetPerm(unsigned sourceSimp);
206
* Determines the permutation that is applied to the (\a dim + 1)
207
* facets of the given source simplex under this isomorphism.
208
* Facet \a i of source simplex \a sourceSimp will be mapped to
209
* face <tt>facetPerm(sourceSimp)[i]</tt> of simplex
210
* <tt>simpImage(sourceSimp)</tt>.
212
* @param sourceSimp the index of the source simplex containing
213
* the original (\a dim + 1) facets; this must be between 0 and
214
* <tt>getSourceSimplices()-1</tt> inclusive.
215
* @return the permutation applied to the facets of the
218
Perm facetPerm(unsigned sourceSimp) const;
220
* Determines the image of the given source simplex facet
221
* under this isomorphism. Note that a value only is returned; this
222
* routine cannot be used to alter the isomorphism.
224
* @param source the given source simplex facet; this must
225
* be one of the (\a dim + 1) facets of one of the getSourceSimplices()
226
* simplices in the source triangulation.
227
* @return the image of the source simplex facet under this
230
NFacetSpec<dim> operator [] (const NFacetSpec<dim>& source) const;
233
* Determines whether or not this is an identity isomorphism.
235
* In an identity isomorphism, each simplex image is itself,
236
* and within each simplex the facet/vertex permutation is
237
* the identity permutation.
239
* @return \c true if this is an identity isomorphism, or
240
* \c false otherwise.
242
bool isIdentity() const;
245
* This NGenericIsomorphism object represents a combinatorial
246
* identification from a triangulation T to a triangulation U.
247
* This routine produces the triangulation U, i.e. the range. The
248
* input parameter (original) represents the domain, T.
250
* The given triangulation (call this T) is not modified in any way.
251
* A new triangulation (call this U) is returned, so that this
252
* isomorphism represents a one-to-one, onto and boundary complete
253
* isomorphism from T to U. That is, T and U are combinatorially
254
* identical triangulations, and this isomorphism describes the
255
* corresponding mapping between simplex and simplex facets.
257
* The resulting triangulation U is newly created, and must be
258
* destroyed by the caller of this routine.
260
* There are several preconditions to this routine. This
261
* routine does a small amount of sanity checking (and returns 0
262
* if an error is detected), but it certainly does not check the
263
* entire set of preconditions. It is up to the caller of this
264
* routine to verify that all of the following preconditions are
267
* \pre The number of simplices in the given triangulation is
268
* precisely the number returned by getSourceSimplices() for
270
* \pre This is a valid isomorphism (i.e., it has been properly
271
* initialised, so that all simplex images are non-negative
272
* and distinct, and all facet permutations are real permutations
274
* \pre Each simplex image for this isomorphism lies
275
* between 0 and <tt>getSourceSimplices()-1</tt> inclusive
276
* (i.e., this isomorphism does not represent a mapping from a
277
* smaller triangulation into a larger triangulation).
279
* @param original the triangulation to which this isomorphism
281
* @return the resulting new triangulation, or 0 if a problem
282
* was encountered (i.e., an unmet precondition was noticed).
284
Triangulation* apply(const Triangulation* original) const;
287
* Applies this isomorphism to the given triangulation,
288
* modifying the given triangulation directly.
290
* This is similar to apply(), except that instead of creating a
291
* new triangulation, the simplices and vertices of the given
292
* triangulation are modified directly.
294
* See apply() for further details on how this operation is performed.
296
* As with apply(), there are several preconditions to this routine.
297
* This routine does a small amount of sanity checking (and returns
298
* without changes if an error is detected), but it certainly does
299
* not check the entire set of preconditions. It is up to the
300
* caller of this routine to verify that all of the following
301
* preconditions are met.
303
* \pre The number of simplices in the given triangulation is
304
* precisely the number returned by getSourceSimplices() for
306
* \pre This is a valid isomorphism (i.e., it has been properly
307
* initialised, so that all simplex images are non-negative
308
* and distinct, and all facet permutations are real permutations
310
* \pre Each simplex image for this isomorphism lies
311
* between 0 and <tt>getSourceSimplices()-1</tt> inclusive
312
* (i.e., this isomorphism does not represent a mapping from a
313
* smaller triangulation into a larger triangulation).
315
* @param tri the triangulation to which this isomorphism
318
void applyInPlace(Triangulation* tri) const;
320
void writeTextShort(std::ostream& out) const;
321
void writeTextLong(std::ostream& out) const;
324
* Returns a random isomorphism for the given number of
325
* simplices. This isomorphism will reorder simplices
326
* 0 to <tt>nSimplices-1</tt> in a random fashion, and for
327
* each simplex a random permutation of its (\a dim + 1) vertices
330
* The isomorphism will be newly constructed, and must be
331
* destroyed by the caller of this routine. The new isomorphism
332
* will be of the appropriate dimension-specific subclass
333
* (e.g., NIsomorphism for \a dim=3, or Dim2Isomorphism for
336
* Note that both the STL random number generator and the
337
* standard C function rand() are used in this routine. All
338
* possible isomorphisms for the given number of simplices are
341
* @param nSimplices the number of simplices that the new
342
* isomorphism should operate upon.
343
* @return the newly constructed random isomorphism.
345
static Isomorphism* random(unsigned nSimplices);
350
// Inline functions for NGenericIsomorphism
353
inline NGenericIsomorphism<dim>::NGenericIsomorphism(unsigned nSimplices) :
354
nSimplices_(nSimplices),
355
simpImage_(nSimplices > 0 ? new int[nSimplices] : 0),
356
facetPerm_(nSimplices > 0 ? new Perm[nSimplices] : 0) {
360
inline NGenericIsomorphism<dim>::~NGenericIsomorphism() {
361
// Always safe to delete null.
367
inline unsigned NGenericIsomorphism<dim>::getSourceSimplices() const {
372
inline int& NGenericIsomorphism<dim>::simpImage(unsigned sourceSimp) {
373
return simpImage_[sourceSimp];
377
inline int NGenericIsomorphism<dim>::simpImage(unsigned sourceSimp) const {
378
return simpImage_[sourceSimp];
382
inline typename NGenericIsomorphism<dim>::Perm&
383
NGenericIsomorphism<dim>::facetPerm(
384
unsigned sourceSimp) {
385
return facetPerm_[sourceSimp];
389
inline typename NGenericIsomorphism<dim>::Perm
390
NGenericIsomorphism<dim>::facetPerm(
391
unsigned sourceSimp) const {
392
return facetPerm_[sourceSimp];
396
inline NFacetSpec<dim> NGenericIsomorphism<dim>::operator [] (
397
const NFacetSpec<dim>& source) const {
398
return NFacetSpec<dim>(simpImage_[source.simp],
399
facetPerm_[source.simp][source.facet]);
402
} // namespace regina