← Back to branch summary

~ubuntu-branches/ubuntu/vivid/regina-normal/vivid

« back to all changes in this revision

Viewing changes to engine/enumerate/nmaxadmissible-impl.h

  • Committer: Package Import Robot
  • Author(s): Ben Burton
  • Date: 2013-11-02 11:44:32 UTC
  • mfrom: (1.2.8)
  • Revision ID: package-import@ubuntu.com-20131102114432-acgci6b1pb2hjl8q
Tags: 4.95-1
* New upstream release.
* The python module is now installed in a standard location beneath
  /usr/lib/python2.7/dist-packages.
* Switched python packaging from python-support to dh_python2.

Show diffs side-by-side

added added

removed removed

Lines of Context:
engine/enumerate/nmaxadmissible-impl.h
 
1
 
 
2
/**************************************************************************
 
3
 *                                                                        *
 
4
 *  Regina - A Normal Surface Theory Calculator                           *
 
5
 *  Computational Engine                                                  *
 
6
 *                                                                        *
 
7
 *  Copyright (c) 1999-2013, Ben Burton                                   *
 
8
 *  For further details contact Ben Burton (bab@debian.org).              *
 
9
 *                                                                        *
 
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.                       *
 
14
 *                                                                        *
 
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.               *
 
20
 *                                                                        *
 
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.                              *
 
25
 *                                                                        *
 
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.                                                   *
 
30
 *                                                                        *
 
31
 **************************************************************************/
 
32
 
 
33
/* end stub */
 
34
 
 
35
/* To be included from nmaxadmissible.h. */
 
36
 
 
37
#ifndef __NMAXADMISSIBLE_IMPL_H
 
38
#ifndef __DOXYGEN
 
39
#define __NMAXADMISSIBLE_IMPL_H
 
40
#endif
 
41
 
 
42
#include "enumerate/nenumconstraint.h"
 
43
#include "enumerate/nmaxadmissible.h"
 
44
#include <algorithm>
 
45
#include <list>
 
46
 
 
47
namespace regina {
 
48
 
 
49
template <class BitmaskType, class RayIterator>
 
50
std::vector<BitmaskType>* NMaxAdmissible::enumerate(
 
51
        RayIterator beginExtremalRays, RayIterator endExtremalRays,
 
52
        const NEnumConstraintList* constraints) {
 
53
    if (beginExtremalRays == endExtremalRays) {
 
54
        // Input is empty, so output is empty.
 
55
        return new std::vector<BitmaskType>();
 
56
    }
 
57
 
 
58
    size_t dim = (*beginExtremalRays)->size();
 
59
    BitmaskType b(dim);
 
60
    int i;
 
61
 
 
62
    // Rewrite the constraints as bitmasks.
 
63
    std::vector<BitmaskType> constMasks;
 
64
    if (constraints) {
 
65
        NEnumConstraintList::const_iterator cit;
 
66
        std::set<unsigned long>::const_iterator sit; 
 
67
        for (cit = constraints->begin(); cit != constraints->end(); ++cit) {
 
68
            b.reset();
 
69
            for (sit = cit->begin(); sit != cit->end(); ++sit)
 
70
                b.set(*sit, true);
 
71
            constMasks.push_back(b);
 
72
        }
 
73
    }
 
74
 
 
75
    // Create a set of bitmasks representing the admissible 1-faces of
 
76
    // the cone, i.e., the set of admissible extremal rays.
 
77
    std::vector<BitmaskType> rays;
 
78
    for (RayIterator rit = beginExtremalRays; rit != endExtremalRays; ++rit) {
 
79
        for (i = 0; i < dim; ++i)
 
80
            b.set(i, (**rit)[i] != 0);
 
81
        rays.push_back(b);
 
82
    }
 
83
 
 
84
    // Create a working set of admissible faces.
 
85
    // We initialise this to the set of all admissible 1-faces, as above.
 
86
    std::list<BitmaskType> faces(rays.begin(), rays.end());
 
87
 
 
88
    // Create the final set of faces to return.
 
89
    std::vector<BitmaskType>* maxFaces = new std::vector<BitmaskType>();
 
90
 
 
91
    // Keep expanding the faces using additional extremal rays until we can
 
92
    // expand no more.
 
93
    // The ith iteration of the following loop enumerates _all_ admissible
 
94
    // faces of dimension i+1, and identifies all _maximal_ admissible
 
95
    // faces of dimension i.
 
96
    std::list<BitmaskType> nextDim;
 
97
    typename std::vector<BitmaskType>::const_iterator r, c;
 
98
    typename std::list<BitmaskType>::const_iterator f;
 
99
    typename std::list<BitmaskType>::iterator n, next;
 
100
    bool isMax, broken;
 
101
    while (! faces.empty()) {
 
102
        for (f = faces.begin(); f != faces.end(); ++f) {
 
103
            // Expand this face by combining with other extremal rays.
 
104
            isMax = true;
 
105
            for (r = rays.begin(); r != rays.end(); ++r) {
 
106
                BitmaskType comb(*f);
 
107
                comb |= *r;
 
108
 
 
109
                // Ignore rays already in this face.
 
110
                if (comb == *f)
 
111
                    continue;
 
112
 
 
113
                // Ignore rays that will break admissibility.
 
114
                broken = false;
 
115
                for (c = constMasks.begin(); c != constMasks.end(); ++c) {
 
116
                    b = comb;
 
117
                    b &= *c;
 
118
                    if (! b.atMostOneBit()) {
 
119
                        broken = true;
 
120
                        break;
 
121
                    }
 
122
                }
 
123
                if (broken)
 
124
                    continue;
 
125
 
 
126
                // comb expands *f to a higher-dimensional superface.
 
127
                isMax = false;
 
128
 
 
129
                // Strip out duplicates, and also strip out superfaces of
 
130
                // too high a dimension (since we only want to step up one
 
131
                // dimension at a time).
 
132
                broken = false;
 
133
                n = nextDim.begin();
 
134
                while (n != nextDim.end()) {
 
135
                    next = n;
 
136
                    ++next;
 
137
                    if (*n <= comb) {
 
138
                        // comb has too high a dimension, or is a duplicate.
 
139
                        broken = true;
 
140
                        break;
 
141
                    }
 
142
                    if (comb <= *n) {
 
143
                        // *n has too high a dimension.
 
144
                        nextDim.erase(n);
 
145
                    }
 
146
                    n = next;
 
147
                }
 
148
                if (! broken)
 
149
                    nextDim.push_back(comb);
 
150
            }
 
151
            if (isMax)
 
152
                maxFaces->push_back(*f);
 
153
        }
 
154
        std::swap(nextDim, faces);
 
155
        nextDim.clear();
 
156
    }
 
157
 
 
158
    // All done!
 
159
    return maxFaces;
 
160
}
 
161
 
 
162
} // namespace regina
 
163
 
 
164
#endif