Frobby 0.9.5
RawSquareFreeTerm.h
Go to the documentation of this file.
1/* Frobby: Software for monomial ideal computations.
2 Copyright (C) 2010 University of Aarhus
3 Contact Bjarke Hammersholt Roune for license information (www.broune.com)
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see http://www.gnu.org/licenses/.
17*/
18#ifndef RAW_SQUARE_FREE_TERM_GUARD
19#define RAW_SQUARE_FREE_TERM_GUARD
20
21#include <ostream>
22#include <algorithm>
23#include <vector>
24
25namespace SquareFreeTermOps {
26 bool isIdentity(const Word* a, Word* aEnd);
27
28 bool isIdentity(const Word* a, size_t varCount);
29
30 size_t getSizeOfSupport(const Word* a, size_t varCount);
31
32 size_t getWordCount(size_t varCount);
33
45 void compact(Word* compacted, const Word* term,
46 const Word* remove, size_t varCount);
47
48 void setToIdentity(Word* res, const Word* resEnd);
49
50 void setToIdentity(Word* res, size_t varCount);
51
53 void setToAllVarProd(Word* res, size_t varCount);
54
57 Word* newTerm(size_t varCount);
58
64 Word* newTermParse(const char* str);
65
67 void deleteTerm(Word* term);
68
70 bool divides(const Word* a, const Word* aEnd, const Word* b);
71
72 bool lexLess(const Word* a, const Word* b, size_t varCount);
73
74 void colon(Word* res, const Word* resEnd, const Word* a, const Word* b);
75 void colonInPlace(Word* res, const Word* resEnd, const Word* b);
76
77 void assign(Word* a, const Word* aEnd, const Word* b);
78
79 void assign(Word* a, const Word* b, size_t varCount);
80
84 bool encodeTerm(Word* encoded, const Exponent* term, const size_t varCount);
85 bool encodeTerm(Word* encoded, const std::vector<mpz_class>& term, const size_t varCount);
86 bool encodeTerm(Word* encoded, const std::vector<std::string>& it, const size_t varCount);
87
88 inline size_t getBitOffset(size_t var);
89
90 inline size_t getWordOffset(size_t var);
91
92 bool hasFullSupport(const Word* a, size_t varCount);
93
94 void lcm(Word* res, const Word* resEnd,
95 const Word* a, const Word* b);
96
97 void lcm(Word* res, const Word* a, const Word* b, size_t varCount);
98
99 void lcmInPlace(Word* res, const Word* resEnd, const Word* a);
100
101 void lcmInPlace(Word* res, const Word* a, size_t varCount);
102
103 void gcd(Word* res, const Word* resEnd, const Word* a, const Word* b);
104 void gcd(Word* res, const Word* a, const Word* b, size_t varCount);
105
106 void gcdInPlace(Word* res, const Word* resEnd, const Word* a);
107
108 void gcdInPlace(Word* res, const Word* a, size_t varCount);
109
110 bool isRelativelyPrime(const Word* a, const Word* aEnd, const Word* b);
111
112 bool isRelativelyPrime(const Word* a, const Word* b, size_t varCount);
113
114 void setExponent(Word* a, size_t var, bool value);
115
117 bool getExponent(const Word* a, size_t var);
118
119 void swap(Word* a, Word* b, size_t varCount);
120 void swap(Word* a, Word* aEnd, Word* b);
121
123 void invert(Word* a, size_t varCount);
124
127 size_t getVarIfPure(const Word* const a, size_t varCount);
128
130 void decrementAtSupport(const Word* a, size_t* inc, size_t varCount);
131
133 void toZeroAtSupport(const Word* a, size_t* inc, size_t varCount);
134
136 bool equals(const Word* a, const Word* b, size_t varCount);
137
142 bool isValid(const Word* a, size_t varCount);
143
144 inline bool divides(const Word* a, const Word* aEnd, const Word* b) {
145 for (; a != aEnd; ++a, ++b)
146 if ((*a & (~*b)) != 0)
147 return false;
148 return true;
149 }
150
151 inline bool getExponent(const Word* a, size_t var) {
152 const Word word = a[getWordOffset(var)];
153 const Word bitMask = ((Word)1) << getBitOffset(var);
154 return word & bitMask;
155 }
156
157 inline size_t getBitOffset(size_t var) {
158 return var % BitsPerWord;
159 }
160
161 inline size_t getWordOffset(size_t var) {
162 return var / BitsPerWord;
163 }
164
165 inline void assign(Word* a, const Word* aEnd, const Word* b) {
166 for (; a != aEnd; ++a, ++b)
167 *a = *b;
168 }
169
170 inline void setExponent(Word* a, size_t var, bool value) {
171 Word& word = a[getWordOffset(var)];
172 const size_t bitOffset = getBitOffset(var);
173 const Word setBit = ((Word)1) << bitOffset;
174 const Word valueBit = ((Word)value) << bitOffset;
175 word = (word & (~setBit)) | valueBit;
176 }
177
178 inline void swap(Word* a, Word* aEnd, Word* b) {
179 for (; a != aEnd; ++a, ++b)
180 std::swap(*a, *b);
181 }
182
183 inline bool hasFullSupport(const Word* a, size_t varCount) {
184 const Word allOnes = ~((Word)0);
185 for (; varCount >= BitsPerWord; varCount -= BitsPerWord, ++a)
186 if (*a != allOnes)
187 return false;
188 if (varCount == 0)
189 return true;
190
191 const Word fullSupportWord = (((Word)1) << varCount) - 1;
192 return *a == fullSupportWord;
193 }
194
195 inline bool isRelativelyPrime(const Word* a, const Word* aEnd, const Word* b) {
196 for (; a != aEnd; ++a, ++b)
197 if ((*a) & (*b))
198 return false;
199 return true;
200 }
201
202 void print(FILE* file, const Word* term, size_t varCount);
203 void print(ostream& out, const Word* term, size_t varCount);
204}
205
206#endif
size_t getWordOffset(size_t var)
void setExponent(Word *a, size_t var, bool value)
Word * newTerm(size_t varCount)
Returns identity term of varCount variables.
bool isValid(const Word *a, size_t varCount)
The unused bits at the end of the last word must be zero for the functions here to work correctly.
size_t getWordCount(size_t varCount)
void colon(Word *res, const Word *resEnd, const Word *a, const Word *b)
size_t getBitOffset(size_t var)
bool encodeTerm(Word *encoded, const Exponent *term, const size_t varCount)
Assigns the RawSquareFreeTerm-encoded form of term to encoded and returns true if term is square free...
size_t getVarIfPure(const Word *const a, size_t varCount)
Returns var if a equals var.
Word * newTermParse(const char *strParam)
Allocates and returns a term based on str.
void invert(Word *a, size_t varCount)
Make 0 exponents 1 and make 1 exponents 0.
void decrementAtSupport(const Word *a, size_t *inc, size_t varCount)
For every variable var that divides a, decrement inc[var] by one.
bool lexLess(const Word *a, const Word *b, size_t varCount)
bool isIdentity(const Word *a, Word *aEnd)
bool hasFullSupport(const Word *a, size_t varCount)
void toZeroAtSupport(const Word *a, size_t *inc, size_t varCount)
For every variable var that divides a, set inc[var] to zero.
size_t getSizeOfSupport(const Word *a, size_t varCount)
void colonInPlace(Word *res, const Word *resEnd, const Word *b)
void lcmInPlace(Word *res, const Word *resEnd, const Word *a)
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
void print(FILE *file, const Word *term, size_t varCount)
void compact(Word *compacted, const Word *term, const Word *remove, size_t varCount)
For every variable var that divides remove, remove the space for that variable in term and put the re...
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
void setToAllVarProd(Word *res, size_t varCount)
Sets all exponents of res to 1.
bool equals(const Word *a, const Word *b, size_t varCount)
Returns true if a equals b.
bool divides(const Word *a, const Word *aEnd, const Word *b)
Returns true if a divides b.
void swap(Word *a, Word *b, size_t varCount)
void deleteTerm(Word *term)
Deletes term previously returned by newTerm().
void gcdInPlace(Word *res, const Word *resEnd, const Word *a)
void assign(Word *a, const Word *b, size_t varCount)
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
void setToIdentity(Word *res, const Word *resEnd)
unsigned int Exponent
Definition stdinc.h:89
static const size_t BitsPerWord
Definition stdinc.h:94
unsigned long Word
The native unsigned type for the CPU.
Definition stdinc.h:93