File: ordering.h

package info (click to toggle)
regina-normal 5.1-6
  • links: PTS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 54,488 kB
  • sloc: cpp: 142,029; ansic: 19,218; xml: 9,844; objc: 7,729; perl: 1,190; python: 623; sh: 614; makefile: 34
file content (135 lines) | stat: -rw-r--r-- 5,479 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

/**************************************************************************
 *                                                                        *
 *  Regina - A Normal Surface Theory Calculator                           *
 *  Computational Engine                                                  *
 *                                                                        *
 *  Copyright (c) 1999-2016, Ben Burton                                   *
 *  For further details contact Ben Burton (bab@debian.org).              *
 *                                                                        *
 *  This program is free software; you can redistribute it and/or         *
 *  modify it under the terms of the GNU General Public License as        *
 *  published by the Free Software Foundation; either version 2 of the    *
 *  License, or (at your option) any later version.                       *
 *                                                                        *
 *  As an exception, when this program is distributed through (i) the     *
 *  App Store by Apple Inc.; (ii) the Mac App Store by Apple Inc.; or     *
 *  (iii) Google Play by Google Inc., then that store may impose any      *
 *  digital rights management, device limits and/or redistribution        *
 *  restrictions that are required by its terms of service.               *
 *                                                                        *
 *  This program is distributed in the hope that it will be useful, but   *
 *  WITHOUT ANY WARRANTY; without even the implied warranty of            *
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU     *
 *  General Public License for more details.                              *
 *                                                                        *
 *  You should have received a copy of the GNU General Public             *
 *  License along with this program; if not, write to the Free            *
 *  Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,       *
 *  MA 02110-1301, USA.                                                   *
 *                                                                        *
 **************************************************************************/

/*! \file enumerate/ordering.h
 *  \brief Provides different ways of sorting hyperplanes (or matching
 *  equations) when performing normal surface enumeration.
 */

#ifndef __ORDERING_H
#ifndef __DOXYGEN
#define __ORDERING_H
#endif

#include "regina-core.h"
#include "maths/matrix.h"

namespace regina {

/**
 * \weakgroup enumerate
 * @{
 */

/**
 * A comparison object that sorts hyperplanes by position vectors.
 * This ordering is described in "Optimizing the double description
 * method for normal surface enumeration", B.A. Burton,
 * Mathematics of Computation 79 (2010), 453-484.
 *
 * This comparison object is used to sort hyperplanes into a good
 * order before enumerating vertex or fundamental normal surfaces
 * A hyperplane is described by a row of the \a subspace matrix,
 * as passed to an enumeration routine such as
 * DoubleDescription::enumerateExtremalRays() or
 * HilbertDual::enumerateHilbertBasis().
 *
 * The ordering is defined as follows.  For each hyperplane, we
 * create a <i>position vector</i> (h_1, ..., h_f), where h_i is 0 if the
 * hyperplane contains the ith coordinate axis, or 1 if not.
 * We then compare these position vectors lexicographically.
 *
 * \ifacespython Not present.
 */
class PosOrder {
    private:
        const MatrixInt& matrix_;
            /**< The \a subspace matrix as passed to the enumeration routine. */

    public:
        /**
         * Creates a new helper object for comparing hyperplanes.
         *
         * @param matrix the \a subspace matrix as passed to
         * the normal surface enumeration routine.
         */
        inline PosOrder(const MatrixInt& matrix);

        /**
         * Determines whether the hyperplane described by
         * row \a i of the matrix is smaller
         * than the hyperplane described by row \a j.
         * Here "smaller" is defined by position vectors;
         * see the PosOrder class notes for details.
         *
         * @param i the first matrix row index; this must be between
         * 0 and matrix.rows()-1 inclusive, where \a matrix is
         * the matrix passed to the class constructor.
         * @param j the second matrix row index; this must also be
         * between 0 and matrix.rows()-1 inclusive.
         * @return \c true if and only if the hyperplane described by
         * row \a i is smaller than the hyperplane described by row \a j.
         */
        inline bool operator () (long i, long j) const;
};

/**
 * Deprecated typedef for backward compatibility.  This typedef will
 * be removed in a future release of Regina.
 *
 * \deprecated The class NPosOrder has now been renamed to PosOrder.
 */
REGINA_DEPRECATED typedef PosOrder NPosOrder;

/*@}*/

// Inline functions for PosOrder

inline PosOrder::PosOrder(const MatrixInt& matrix) :
        matrix_(matrix) {
}

inline bool PosOrder::operator () (
        long i, long j) const {
    for (unsigned long c = 0; c < matrix_.columns(); ++c) {
        if (matrix_.entry(i, c) == 0 && matrix_.entry(j, c) != 0)
            return true;
        if (matrix_.entry(i, c) != 0 && matrix_.entry(j, c) == 0)
            return false;
    }
    return false;
}

} // namespace regina

#endif