Term.h

Go to the documentation of this file.

/* Frobby: Software for monomial ideal computations.
   Copyright (C) 2007 Bjarke Hammersholt Roune (www.broune.com)
 
   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.
 
   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, see http://www.gnu.org/licenses/.
*/
#ifndef TERM_GUARD
#define TERM_GUARD
 
#include <ostream>
 
class Term {
 public:
 Term(): _exponents(0), _varCount(0) {}
  Term(const Term& term) {initialize(term._exponents, term._varCount);}
  Term(const Exponent* exponents, size_t varCount) {
    initialize(exponents, varCount);
  }
 
 Term(size_t varCount):
  _varCount(varCount) {
    if (varCount > 0) {
      _exponents = allocate(varCount);
      setToIdentity();
    } else
      _exponents = 0;
  }
 
  Term(const string& str);
 
  ~Term() {deallocate(_exponents, _varCount);}
 
  operator Exponent*() {return _exponents;}
  operator const Exponent*() const {return _exponents;}
 
  Exponent* begin() {return _exponents;}
  const Exponent* begin() const {return _exponents;}
 
  Exponent* end() {return _exponents + _varCount;}
  const Exponent* end() const {return _exponents + _varCount;}
 
  size_t getVarCount() const {return _varCount;}
 
  // We need all these versions to make everything work out on
  // different platforms.
  Exponent operator[](int offset) const {
    ASSERT(0 <= offset);
    ASSERT((unsigned int)offset < _varCount);
    return _exponents[offset];
  }
  Exponent operator[](unsigned int offset) const {
    ASSERT(offset < _varCount);
    return _exponents[offset];
  }
  Exponent operator[](unsigned long offset) const {
    ASSERT(offset < _varCount);
    return _exponents[offset];
  }
  Exponent operator[](unsigned long long offset) const {
    ASSERT(offset < _varCount);
    return _exponents[offset];
  }
 
  Exponent& operator[](int offset) {
    ASSERT(0 <= offset);
    ASSERT((unsigned int)offset < _varCount);
    return _exponents[offset];
  }
  Exponent& operator[](unsigned int offset) {
    ASSERT(offset < _varCount);
    return _exponents[offset];
  }
  Exponent& operator[](unsigned long offset) {
    ASSERT(offset < _varCount);
    return _exponents[offset];
  }
  Exponent& operator[](unsigned long long offset) {
    ASSERT(offset < _varCount);
    return _exponents[offset];
  }
 
  bool operator==(const Term& term) const {
    ASSERT(_varCount == term._varCount);
    return (*this) == term._exponents;
  }
  bool operator==(const Exponent* term) const;
  bool operator!=(const Term& term) const {return !(*this == term);}
  bool operator!=(const Exponent* term) const {return !(*this == term);}
 
  Term& operator=(const Term& term) {
    if (_varCount != term._varCount) {
      Exponent* newBuffer = allocate(term._varCount);
      deallocate(_exponents, _varCount);
      _exponents = newBuffer;
      _varCount = term._varCount;
    }
 
    ASSERT(_varCount == term._varCount);
    return (*this) = term._exponents;
  }
 
  Term& operator=(const Exponent* exponents) {
    IF_DEBUG(if (_varCount > 0)) // avoid copy asserting on null pointer
    copy(exponents, exponents + _varCount, _exponents);
    return *this;
  }
 
  inline static bool divides(const Exponent* a, const Exponent* b, size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    ASSERT(b != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var)
      if (a[var] > b[var])
        return false;
    return true;
  }
 
  bool divides(const Term& term) const {
    ASSERT(_varCount == term._varCount);
    return divides(_exponents, term._exponents, _varCount);
  }
 
  bool divides(const Exponent* term) const {
    return divides(_exponents, term, _varCount);
  }
 
  inline static bool dominates(const Exponent* a, const Exponent* b,
                               size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    ASSERT(b != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var)
      if (a[var] < b[var])
        return false;
    return true;
  }
 
  bool dominates(const Term& term) const {
    ASSERT(_varCount == term._varCount);
    return dominates(_exponents, term._exponents, _varCount);
  }
 
  bool dominates(const Exponent* term) const {
    return dominates(_exponents, term, _varCount);
  }
 
  inline static bool strictlyDivides(const Exponent* a, const Exponent* b,
                                     size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    ASSERT(b != 0 || varCount == 0);
    bool bIsIdentity = true;
    for (size_t var = 0; var < varCount; ++var) {
      if (a[var] >= b[var] && a[var] != 0)
        return false;
      if (b[var] != 0)
        bIsIdentity = false;
    }
 
    return !bIsIdentity;
  }
 
  bool strictlyDivides(const Term& term) const {
    ASSERT(_varCount == term._varCount);
    return strictlyDivides(_exponents, term._exponents, _varCount);
  }
 
  bool strictlyDivides(const Exponent* term) const {
    return strictlyDivides(_exponents, term, _varCount);
  }
 
  inline static void lcm(Exponent* res,
                         const Exponent* a, const Exponent* b,
                         size_t varCount) {
    ASSERT(res != 0 || varCount == 0);
    ASSERT(a != 0 || varCount == 0);
    ASSERT(b != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var) {
      if (a[var] > b[var])
        res[var] = a[var];
      else
        res[var] = b[var];
    }
  }
 
  void lcm(const Term& a, const Term& b, int position) {
    ASSERT(_varCount == a._varCount);
    ASSERT(_varCount == b._varCount);
    lcm(_exponents + position,
        a._exponents + position,
        b._exponents + position,
        _varCount - position);
  }
 
  void lcm(const Term& a, const Term& b) {
    ASSERT(_varCount == a._varCount);
    ASSERT(_varCount == b._varCount);
    lcm(_exponents, a._exponents, b._exponents, _varCount);
  }
 
  void lcm(const Exponent* a, const Exponent* b) {
    lcm(_exponents, a, b, _varCount);
  }
 
  inline static void gcd(Exponent* res,
                         const Exponent* a, const Exponent* b,
                         size_t varCount) {
    ASSERT(res != 0 || varCount == 0);
    ASSERT(a != 0 || varCount == 0);
    ASSERT(b != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var) {
      if (a[var] < b[var])
        res[var] = a[var];
      else
        res[var] = b[var];
    }
  }
 
  void gcd(const Term& a, const Term& b) {
    ASSERT(_varCount == a._varCount);
    ASSERT(_varCount == b._varCount);
    gcd(a._exponents, b._exponents);
  }
 
  void gcd(const Exponent* a, const Exponent* b) {
    gcd(_exponents, a, b, _varCount);
  }
 
  inline static void product(Exponent* res,
                             const Exponent* a, const Exponent* b,
                             size_t varCount) {
    ASSERT(res != 0 || varCount == 0);
    ASSERT(a != 0 || varCount == 0);
    ASSERT(b != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var)
      res[var] = a[var] + b[var];
  }
 
  void product(const Term& a, const Term& b) {
    ASSERT(_varCount == a._varCount);
    ASSERT(_varCount == b._varCount);
    product(_exponents, a._exponents, b._exponents, _varCount);
  }
 
  void product(const Exponent* a, const Exponent* b) {
    product(_exponents, a, b, _varCount);
  }
 
  inline static void setToIdentity(Exponent* res, size_t varCount) {
    ASSERT(res != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var)
      res[var] = 0;
  }
 
  void setToIdentity() {
    setToIdentity(_exponents, _varCount);
  }
 
  inline static bool isIdentity(const Exponent* a, size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var)
      if (a[var] != 0)
        return false;
    return true;
  }
 
  bool isIdentity() const {
    return isIdentity(_exponents, _varCount);
  }
 
  inline static bool isSquareFree(const Exponent* a, size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var)
      if (a[var] >= 2)
        return false;
    return true;
  }
 
  bool isSquareFree() const {
    return isSquareFree(_exponents, _varCount);
  }
 
  inline static size_t getFirstNonZeroExponent(const Exponent* a, size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var)
      if (a[var] != 0)
        return var;
    return varCount;
  }
 
  size_t getFirstNonZeroExponent() const {
    return getFirstNonZeroExponent(_exponents, _varCount);
  }
 
  inline static size_t getMiddleNonZeroExponent(const Exponent* a, size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    size_t nonZeroOffset = getSizeOfSupport(a, varCount) / 2;
    for (size_t var = 0; var < varCount; ++var) {
      if (a[var] != 0) {
        if (nonZeroOffset == 0)
          return var;
        --nonZeroOffset;
      }
    }
 
    ASSERT(isIdentity(a, varCount));
    return varCount;
  }
 
  size_t getMiddleNonZeroExponent() const {
    return getMiddleNonZeroExponent(_exponents, _varCount);
  }
 
  inline static size_t getFirstMaxExponent(const Exponent* a, size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    size_t max = 0;
    for (size_t var = 1; var < varCount; ++var)
      if (a[max] < a[var])
        max = var;
    return max;
  }
 
  size_t getFirstMaxExponent() const {
    return getFirstMaxExponent(_exponents, _varCount);
  }
 
  size_t getMaxExponent() const {
    ASSERT(_varCount > 0);
    return _exponents[getFirstMaxExponent()];
  }
 
  inline static size_t getSizeOfSupport(const Exponent* a, size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    size_t size = 0;
    for (size_t var = 0; var < varCount; ++var)
      if (a[var] != 0)
        ++size;
    return size;
  }
 
  size_t getSizeOfSupport() const {
    return getSizeOfSupport(_exponents, _varCount);
  }
 
  static bool sharesNonZeroExponent(const Exponent* a, const Exponent* b,
                                    size_t varCount) {
    for (size_t var = 0; var < varCount; ++var)
      if (a[var] != 0 && a[var] == b[var])
        return true;
    return false;
  }
 
  inline static size_t getHashCode(const Exponent* a, size_t varCount) {
    size_t hashCode = varCount;
    for (size_t var = 0; var < varCount; ++var)
      hashCode = 31 * hashCode + a[var];
    return hashCode;
  }
 
  size_t getHashCode() const {
    return getHashCode(_exponents, _varCount);
  }
 
  bool sharesNonZeroExponent(const Exponent* a) const {
    return sharesNonZeroExponent(_exponents, a, _varCount);
  }
 
  bool sharesNonZeroExponent(const Term& a) const {
    return sharesNonZeroExponent(a._exponents);
  }
 
  inline static bool hasSameSupport(const Exponent* a, const Exponent* b,
                                    size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    ASSERT(b != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var) {
      if (a[var] == 0) {
        if (b[var] != 0)
          return false;
      } else {
        ASSERT(a[var] != 0);
        if (b[var] == 0)
          return false;
      }
    }
    return true;
  }
 
  bool hasSameSupport(const Term& a) const {
    ASSERT(_varCount == a._varCount);
    return hasSameSupport(a._exponents);
  }
 
  bool hasSameSupport(const Exponent* a) const {
    return hasSameSupport(_exponents, a, _varCount);
  }
 
  inline static void colon(Exponent* res,
                           const Exponent* a, const Exponent* b,
                           size_t varCount) {
    ASSERT(res != 0 || varCount == 0);
    ASSERT(a != 0 || varCount == 0);
    ASSERT(b != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var) {
      if (a[var] > b[var])
        res[var] = a[var] - b[var];
      else
        res[var] = 0;
    }
  }
 
  void colon(const Term& a, const Term& b) {
    ASSERT(_varCount == a._varCount);
    ASSERT(_varCount == b._varCount);
    colon(a._exponents, b._exponents);
  }
 
  void colon(const Exponent* a, const Exponent* b) {
    colon(_exponents, a, b, _varCount);
  }
 
  inline static void encodedDual(Exponent* res,
                                 const Exponent* dualOf, const Exponent* point,
                                 size_t varCount) {
    ASSERT(res != 0 || varCount == 0);
    ASSERT(dualOf != 0 || varCount == 0);
    ASSERT(point != 0 || varCount == 0);
 
    for (size_t var = 0; var < varCount; ++var) {
      ASSERT(dualOf[var] <= point[var]);
      if (dualOf[var] != 0)
        res[var] = point[var] - dualOf[var] + 1;
      else
        res[var] = 0;
    }
  }
 
  void encodedDual(const Term& dualOf, const Term& point) {
    ASSERT(_varCount == dualOf._varCount);
    ASSERT(_varCount == point._varCount);
    encodedDual(dualOf._exponents, point._exponents);
  }
 
  void encodedDual(const Exponent* dualOf, const Exponent* point) {
    encodedDual(_exponents, dualOf, point, _varCount);
  }
 
  inline static void decrement(Exponent* a, size_t varCount) {
    ASSERT(a != 0 || varCount == 0);
    for (size_t var = 0; var < varCount; ++var)
      if (a[var] > 0)
        a[var] -= 1;
  }
 
  void decrement() {
    decrement(_exponents, _varCount);
  }
 
  void swap(Term& term) {
    std::swap(_varCount, term._varCount);
 
    Exponent* tmp = _exponents;
    _exponents = term._exponents;
    term._exponents = tmp;
  }
 
  void reset(size_t newVarCount) {
    if (newVarCount != _varCount) {
      Exponent* newBuffer = allocate(newVarCount);
 
      deallocate(_exponents, _varCount);
      _varCount = newVarCount;
      _exponents = newBuffer;
    }
    setToIdentity();
  }
 
  void clear() {
    deallocate(_exponents, _varCount);
    _exponents = 0;
    _varCount = 0;
  }
 
  static void print(FILE* file, const Exponent* e, size_t varCount);
 
  static void print(ostream& out, const Exponent* e, size_t varCount);
 
  void print(FILE* file) const {
    print(file, _exponents, _varCount);
  }
 
  void print(ostream& out) const {
    print(out, _exponents, _varCount);
  }
 
 
 private:
  static Exponent* allocate(size_t size);
  static void deallocate(Exponent* p, size_t size);
 
  void initialize(const Exponent* exponents, size_t varCount) {
    if (varCount > 0) {
      ASSERT(exponents != 0);
      _exponents = allocate(varCount);
      copy(exponents, exponents + varCount, _exponents);
    } else
      _exponents = 0;
    _varCount = varCount;
  }
 
  Exponent* _exponents;
  size_t _varCount;
};
 
inline void swap(Term& a, Term& b) { a.swap(b); }
 
 
inline ostream& operator<<(ostream& out, const Term& term) {
  term.print(out);
  return out;
}
 
#endif