Frobby  0.9.1
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 
25 namespace 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
SquareFreeTermOps::print
void print(FILE *file, const Word *term, size_t varCount)
Definition: RawSquareFreeTerm.cpp:35
SquareFreeTermOps::invert
void invert(Word *a, size_t varCount)
Make 0 exponents 1 and make 1 exponents 0.
Definition: RawSquareFreeTerm.cpp:311
SquareFreeTermOps::encodeTerm
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...
Definition: RawSquareFreeTerm.cpp:193
SquareFreeTermOps::getWordCount
size_t getWordCount(size_t varCount)
Definition: RawSquareFreeTerm.cpp:91
SquareFreeTermOps::isValid
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.
Definition: RawSquareFreeTerm.cpp:415
SquareFreeTermOps::lexLess
bool lexLess(const Word *a, const Word *b, size_t varCount)
Definition: RawSquareFreeTerm.cpp:158
SquareFreeTermOps::equals
bool equals(const Word *a, const Word *b, size_t varCount)
Returns true if a equals b.
Definition: RawSquareFreeTerm.cpp:397
SquareFreeTermOps::setToAllVarProd
void setToAllVarProd(Word *res, size_t varCount)
Sets all exponents of res to 1.
Definition: RawSquareFreeTerm.cpp:128
SquareFreeTermOps::compact
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...
Definition: RawSquareFreeTerm.cpp:100
SquareFreeTermOps::assign
void assign(Word *a, const Word *b, size_t varCount)
Definition: RawSquareFreeTerm.cpp:186
BitsPerWord
static const size_t BitsPerWord
Definition: stdinc.h:94
SquareFreeTermOps
Definition: RawSquareFreeTerm.cpp:24
SquareFreeTermOps::colonInPlace
void colonInPlace(Word *res, const Word *resEnd, const Word *b)
Definition: RawSquareFreeTerm.cpp:181
SquareFreeTermOps::isRelativelyPrime
bool isRelativelyPrime(const Word *a, const Word *b, size_t varCount)
Definition: RawSquareFreeTerm.cpp:300
SquareFreeTermOps::swap
void swap(Word *a, Word *aEnd, Word *b)
Definition: RawSquareFreeTerm.h:178
SquareFreeTermOps::colon
void colon(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition: RawSquareFreeTerm.cpp:176
SquareFreeTermOps::gcdInPlace
void gcdInPlace(Word *res, const Word *resEnd, const Word *a)
Definition: RawSquareFreeTerm.cpp:288
Exponent
unsigned int Exponent
Definition: stdinc.h:89
SquareFreeTermOps::setExponent
void setExponent(Word *a, size_t var, bool value)
Definition: RawSquareFreeTerm.h:170
SquareFreeTermOps::decrementAtSupport
void decrementAtSupport(const Word *a, size_t *inc, size_t varCount)
For every variable var that divides a, decrement inc[var] by one.
Definition: RawSquareFreeTerm.cpp:356
SquareFreeTermOps::setToIdentity
void setToIdentity(Word *res, const Word *resEnd)
Definition: RawSquareFreeTerm.cpp:115
SquareFreeTermOps::lcmInPlace
void lcmInPlace(Word *res, const Word *resEnd, const Word *a)
Definition: RawSquareFreeTerm.cpp:264
SquareFreeTermOps::toZeroAtSupport
void toZeroAtSupport(const Word *a, size_t *inc, size_t varCount)
For every variable var that divides a, set inc[var] to zero.
Definition: RawSquareFreeTerm.cpp:376
SquareFreeTermOps::getVarIfPure
size_t getVarIfPure(const Word *const a, size_t varCount)
Returns var if a equals var.
Definition: RawSquareFreeTerm.cpp:322
Word
unsigned long Word
The native unsigned type for the CPU.
Definition: stdinc.h:93
SquareFreeTermOps::lcm
void lcm(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition: RawSquareFreeTerm.cpp:251
SquareFreeTermOps::getExponent
bool getExponent(const Word *a, size_t var)
returns true if var divides a and false otherwise.
Definition: RawSquareFreeTerm.h:151
SquareFreeTermOps::newTermParse
Word * newTermParse(const char *strParam)
Allocates and returns a term based on str.
Definition: RawSquareFreeTerm.cpp:25
SquareFreeTermOps::getSizeOfSupport
size_t getSizeOfSupport(const Word *a, size_t varCount)
Definition: RawSquareFreeTerm.cpp:71
SquareFreeTermOps::getWordOffset
size_t getWordOffset(size_t var)
Definition: RawSquareFreeTerm.h:161
SquareFreeTermOps::hasFullSupport
bool hasFullSupport(const Word *a, size_t varCount)
Definition: RawSquareFreeTerm.h:183
SquareFreeTermOps::getBitOffset
size_t getBitOffset(size_t var)
Definition: RawSquareFreeTerm.h:157
SquareFreeTermOps::divides
bool divides(const Word *a, const Word *aEnd, const Word *b)
Returns true if a divides b.
Definition: RawSquareFreeTerm.h:144
SquareFreeTermOps::swap
void swap(Word *a, Word *b, size_t varCount)
Definition: RawSquareFreeTerm.cpp:425
SquareFreeTermOps::deleteTerm
void deleteTerm(Word *term)
Deletes term previously returned by newTerm().
Definition: RawSquareFreeTerm.cpp:154
SquareFreeTermOps::gcd
void gcd(Word *res, const Word *resEnd, const Word *a, const Word *b)
Definition: RawSquareFreeTerm.cpp:276
SquareFreeTermOps::isIdentity
bool isIdentity(const Word *a, Word *aEnd)
Definition: RawSquareFreeTerm.cpp:51
SquareFreeTermOps::newTerm
Word * newTerm(size_t varCount)
Returns identity term of varCount variables.
Definition: RawSquareFreeTerm.cpp:139