← Back to branch summary

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

« back to all changes in this revision

Viewing changes to engine/enumerate/nmaxadmissible.tcc

  • 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.tcc
32
32
 
33
33
/* end stub */
34
34
 
35
 
/* To be included from nmaxadmissible.h. */
36
 
 
37
 
#ifndef __NMAXADMISSIBLE_TCC
38
 
#ifndef __DOXYGEN
39
 
#define __NMAXADMISSIBLE_TCC
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
 
    unsigned 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
 
35
/*! \file enumerate/nmaxadmissible.tcc
 
36
 *  \brief Deprecated header.
 
37
 */
 
38
 
 
39
#warning This header is deprecated; please use nmaxadmissible-impl.h instead.
 
40
 
 
41
#include "enumerate/nmaxadmissible-impl.h"
 
42