Frobby 0.9.5
VarSorter.cpp
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2007 Bjarke Hammersholt Roune (www.broune.com)
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see http://www.gnu.org/licenses/.
16*/
17#include "stdinc.h"
18#include "VarSorter.h"
19
20#include "TermTranslator.h"
21
22#include <algorithm>
23
25public:
27 _names(names) {
28 }
29
30 bool operator()(size_t a, size_t b) const {
31 return _names.getName(a) < _names.getName(b);
32 }
33
34private:
35 void operator=(const VarSorterCompare&); // To make unaccessible.
36
38};
39
41 _names(names),
42 _bigTmpTerm(names.getVarCount()),
43 _tmpTerm(names.getVarCount()) {
44 _permutation.reserve(names.getVarCount());
45 for (size_t i = 0; i < names.getVarCount(); ++i)
46 _permutation.push_back(i);
47 sort(_permutation.begin(), _permutation.end(), VarSorterCompare(_names));
48}
49
51 names.clear();
52 for (size_t i = 0; i < _permutation.size(); ++i)
54}
55
56void VarSorter::permute(vector<mpz_class>& term) {
57 ASSERT(term.size() == _bigTmpTerm.size());
58 _bigTmpTerm.swap(term);
59 for (size_t i = 0; i < _permutation.size(); ++i)
60 mpz_swap(term[i].get_mpz_t(), _bigTmpTerm[_permutation[i]].get_mpz_t());
61}
62
64 _tmpTerm = term;
65 for (size_t i = 0; i < _permutation.size(); ++i)
66 std::swap(term[i], _tmpTerm[_permutation[i]]);
67}
68
70 ASSERT(translator->getVarCount() == _permutation.size());
71
72 size_t varCount = _permutation.size();
73 vector<int> done(translator->getVarCount());
74 for (size_t var = 0; var < varCount; ++var) {
75 if (done[var])
76 continue;
77
78 size_t v = var;
79 while (true) {
80 done[v] = true;
81 size_t nextInCycle = _permutation[v];
82 if (done[nextInCycle])
83 break;
84
85 translator->swapVariables(v, nextInCycle);
86 v = nextInCycle;
87 }
88 }
89
90}
TermTranslator handles translation between terms whose exponents are infinite precision integers and ...
void swapVariables(size_t a, size_t b)
size_t getVarCount() const
Defines the variables of a polynomial ring and facilities IO involving them.
Definition: VarNames.h:40
bool addVar(const string &name)
Adds the variable and returns true if name is not already a variable.
Definition: VarNames.cpp:44
size_t getVarCount() const
Returns the current number of variables.
Definition: VarNames.h:113
const string & getName(size_t index) const
The returned reference can become invalid next time addVar is called.
Definition: VarNames.cpp:100
void clear()
Resets the number of variables to zero.
Definition: VarNames.cpp:106
void operator=(const VarSorterCompare &)
const VarNames & _names
Definition: VarSorter.cpp:37
bool operator()(size_t a, size_t b) const
Definition: VarSorter.cpp:30
VarSorterCompare(const VarNames &names)
Definition: VarSorter.cpp:26
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
Definition: hashtable.h:740
unsigned int Exponent
Definition: stdinc.h:89
#define ASSERT(X)
Definition: stdinc.h:86
VarNames _names
Definition: VarSorter.h:43
vector< mpz_class > _bigTmpTerm
Definition: VarSorter.h:44
VarSorter(const VarNames &names)
Definition: VarSorter.cpp:40
vector< size_t > _permutation
Definition: VarSorter.h:42
void getOrderedNames(VarNames &names)
Definition: VarSorter.cpp:50
void permute(vector< mpz_class > &term)
Definition: VarSorter.cpp:56
Term _tmpTerm
Definition: VarSorter.h:45