exprrep.h

很多二维 三维几何计算算法 C++ 类库

/****************************************************************************
 * Core Library Version 1.7, August 2004
 * Copyright (c) 1995-2004 Exact Computation Project
 * All rights reserved.
 *
 * This file is part of CORE (http://cs.nyu.edu/exact/core/); you may
 * redistribute it under the terms of the Q Public License version 1.0.
 * See the file LICENSE.QPL distributed with CORE.
 *
 * Licensees holding a valid commercial license may use this file in
 * accordance with the commercial license agreement provided with the
 * software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 *
 *
 * File: ExprRep.h
 * Synopsis: Internal Representation of Expr.
 * 
 * Written by 
 *       Koji Ouchi <[e-mail]>
 *       Chee Yap <[e-mail]>
 *       Igor Pechtchanski <[e-mail]>
 *       Vijay Karamcheti <[e-mail]>
 *       Chen Li <[e-mail]>
 *       Zilin Du <[e-mail]>
 *       Sylvain Pion <[e-mail]> 
 *       Vikram Sharma<[e-mail]>
 *
 * WWW URL: http://cs.nyu.edu/exact/
 * Email: [e-mail]
 *
 * $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/Core/include/CGAL/CORE/ExprRep.h $
 * $Id: ExprRep.h 37060 2007-03-13 18:10:39Z reichel $
 ***************************************************************************/

#ifndef _CORE_EXPRREP_H_
#define _CORE_EXPRREP_H_

#include <CGAL/CORE/Real.h>
#include <CGAL/CORE/Filter.h>
#include <CGAL/CORE/poly/Sturm.h>

CORE_BEGIN_NAMESPACE

#ifdef CORE_DEBUG_BOUND
// These counters are incremented each time each bound is recognized as equal
// to the best one in computeBound().
extern unsigned int BFMSS_counter;
extern unsigned int Measure_counter;
// extern unsigned int Cauchy_counter;
extern unsigned int LiYap_counter;
// These counters are incremented each time each bound is recognized as equal
// to the best one in computeBound(), and it's strictly the best.
extern unsigned int BFMSS_only_counter;
extern unsigned int Measure_only_counter;
// extern unsigned int Cauchy_only_counter;
extern unsigned int LiYap_only_counter;
// This counter is incremented each time the precision needed matches the
// root bound.
extern unsigned int rootBoundHitCounter;
#endif

const extLong EXTLONG_BIG = (1L << 30);
const extLong EXTLONG_SMALL = -(1L << 30);

const double log_5 = log(double(5))/log(double(2));

// Returns the ceil of log_2(5^a).
inline extLong ceilLg5(const extLong & a) {
#if defined (_MSC_VER) || defined (__sgi)
  return (int) ::ceil(log_5 * a.toLong());
#else
  return (int) std::ceil(log_5 * a.toLong());
#endif
}

/// \struct NodeInfo
/// \brief store information of a node
struct NodeInfo {
  Real     appValue;		///< current approximate value
  bool     appComputed;  	///< true if the approx value been computed
  bool     flagsComputed;  	///< true if rootBound parameters have been computed
  extLong  knownPrecision; 	///< Precision achieved by current approx value

#ifdef CORE_DEBUG
  extLong relPrecision;
  extLong absPrecision;
  unsigned long numNodes;
#endif

  /// d_e bounds the degree of the minimal polynomial of a DAG expression
  /** Basically, d_e is equal to 2^k where k is the number of square-root nodes
   *   in the DAG.  If there are other kinds of non-linear nodes, this is
   *   generalized accordingly.   */
  extLong d_e;

  bool visited;   	///< flag in counting # of sqrts
  int sign; 		///< sign of the value being represented.

  extLong  uMSB; ///< upper bound of the position of Most Significant Bit
  extLong  lMSB; ///< lower bound of the position of Most Significant Bit

  // For the degree-length method mentioned in Chee's book.
  /* the degree of defining polynomial P(X) obtained from Resultant calculus
   * (deprecated now) */
  // extLong degree;

  // extLong length; ///< length is really lg(|| P(X) ||)
  extLong measure; ///< measure is really lg(Measure)

  // For our new bound.
  /// 2^{high(E)} is an UPPER bound for the moduli of ALL conjugates of E.
  /** In our papers, high is equal to log_2(\overline{\mu(E)}). */
  extLong high;
  /// 2^{-low(E)} is LOWER bound on the moduli of ALL NON_ZERO conjugate of E.
  /** BE CAREFUL!  NOTE THAT UNLIKE "high", the sign of low is negated here!
      In our papers, low is equal to -log_2(\underline{\nu(E)})  */
  extLong low;
  /// \brief upper bound of the leading coefficient of minimal defining
  ///        polynomial of $E$.
  extLong lc;
  /// \brief upper bound of the last non-zero coefficient of minimal defining
  ///        polynomial of $E$.
  extLong tc;

  // For the 2-ary BFMSS bound.
  extLong v2p, v2m;
  // For the 5-ary BFMSS bound.
  extLong v5p, v5m;
  /// 2^u25 is an upper bound for the moduli of all the conjugates of U(E)
  /** where E = 2^v2*5^v5*U(E)/L(E), U(E) and L(E) are division-free. */
  extLong u25;
  /// 2^l25 is an upper bound for the moduli of all the conjugates of L(E)
  /** where E = 2^v2*5^v5*U(E)/L(E), U(E) and L(E) are division-free. */
  extLong l25;

  int ratFlag;		///< rational flag
  BigRat* ratValue;	///< rational value

  /// default constructor
  NodeInfo();
};//NodeInfo struct

//  forward reference
// class Expr;

/// \class ExprRep
/// \brief The sharable, internal representation of expressions
//  Members: private: int refCount,
//            public:  NodeInfo* nodeInfo,
//                     filteredFp ffVal.
class ExprRep {
public:
  /// \name Constructor and Destructor
  //@{
  /// default constructor
  ExprRep();
  /// virtual destructor for this base class
  virtual ~ExprRep() {
    if (nodeInfo != NULL) // This check is only for optimization.
      delete nodeInfo;
  }
  //@}

  /// \name Reference Counting
  //@{
  /// increase reference counter
  void incRef() {
    ++refCount;
  }
  /// decrease reference counter
  void decRef() {
    if (--refCount == 0)
      delete this;
  }
  /// return reference counter
  int getRefCount() const {
    return refCount;
  }
  /// check whether reference counter == 1
  int isUnique() const {
    return refCount == 1;
  }
  //@}

  /// \name Helper Functions
  //@{
  /// Get the approximate value
  const Real & getAppValue(const extLong& relPrec = defRelPrec,
                           const extLong& absPrec = defAbsPrec);
  /// Get the sign.
  int getSign();
  int getExactSign();

  const Real& appValue() const {
    return nodeInfo->appValue;
  }
  Real& appValue() {
    return nodeInfo->appValue;
  }

  const bool& appComputed() const {
    return nodeInfo->appComputed;
  }
  bool& appComputed() {
    return nodeInfo->appComputed;
  }

  const bool& flagsComputed() const {
    return nodeInfo->flagsComputed;
  }
  bool& flagsComputed() {
    return nodeInfo->flagsComputed;
  }

  const extLong& knownPrecision() const {
    return nodeInfo->knownPrecision;
  }
  extLong& knownPrecision() {
    return nodeInfo->knownPrecision;
  }

#ifdef CORE_DEBUG
  const extLong& relPrecision() const {
    return nodeInfo->relPrecision;
  }
  extLong& relPrecision() {
    return nodeInfo->relPrecision;
  }

  const extLong& absPrecision() const {
    return nodeInfo->absPrecision;
  }
  extLong& absPrecision() {
    return nodeInfo->absPrecision;
  }

  const unsigned long& numNodes() const {
    return nodeInfo->numNodes;
  }
  unsigned long& numNodes() {
    return nodeInfo->numNodes;
  }
#endif

  const extLong& d_e() const {
    return nodeInfo->d_e;
  }
  extLong& d_e() {
    return nodeInfo->d_e;
  }

  const bool& visited() const {
    return nodeInfo->visited;
  }
  bool& visited() {
    return nodeInfo->visited;
  }

  const int& sign() const {
    return nodeInfo->sign;
  }
  int& sign() {
    return nodeInfo->sign;
  }

  const extLong& uMSB() const {
    return nodeInfo->uMSB;
  }
  extLong& uMSB() {
    return nodeInfo->uMSB;
  }

  const extLong& lMSB() const {
    return nodeInfo->lMSB;
  }
  extLong& lMSB() {
    return nodeInfo->lMSB;
  }

  //  const extLong& length() const { return nodeInfo->length; }
  //  extLong& length() { return nodeInfo->length; }

  const extLong& measure() const {
    return nodeInfo->measure;
  }
  extLong& measure() {
    return nodeInfo->measure;
  }

  const extLong& high() const {
    return nodeInfo->high;
  }
  extLong& high() {
    return nodeInfo->high;
  }

  const extLong& low() const {
    return nodeInfo->low;
  }
  extLong& low() {
    return nodeInfo->low;
  }

  const extLong& lc() const {
    return nodeInfo->lc;
  }
  extLong& lc() {
    return nodeInfo->lc;
  }

  const extLong& tc() const {
    return nodeInfo->tc;
  }
  extLong& tc() {
    return nodeInfo->tc;
  }

  const extLong& v2p() const {
    return nodeInfo->v2p;
  }
  extLong& v2p() {
    return nodeInfo->v2p;
  }

  const extLong& v2m() const {
    return nodeInfo->v2m;
  }
  extLong& v2m() {
    return nodeInfo->v2m;
  }

  extLong v2() const {
    return v2p()-v2m();
  }

  const extLong& v5p() const {
    return nodeInfo->v5p;
  }
  extLong& v5p() {
    return nodeInfo->v5p;
  }

  const extLong& v5m() const {
    return nodeInfo->v5m;
  }
  extLong& v5m() {
    return nodeInfo->v5m;
  }

  extLong v5() const {
    return v5p()-v5m();
  }

  const extLong& u25() const {
    return nodeInfo->u25;
  }
  extLong& u25() {
    return nodeInfo->u25;
  }

  const extLong& l25() const {
    return nodeInfo->l25;
  }
  extLong& l25() {
    return nodeInfo->l25;
  }

  const int& ratFlag() const {
    return nodeInfo->ratFlag;
  }
  int& ratFlag() {
    return nodeInfo->ratFlag;
  }

  const BigRat* ratValue() const {
    return nodeInfo->ratValue;
  }
  BigRat*& ratValue() {
    return nodeInfo->ratValue;
  }

  /// Get BigFloat
  BigInt BigIntValue();
  BigRat BigRatValue();
  BigFloat BigFloatValue();
  /// represent as a string in decimal value
  // toString() Joaquin Grech 31/5/2003
  std::string toString(long prec=defOutputDigits, bool sci=false) {
    return (getAppValue(defRelPrec, defAbsPrec)).toString(prec,sci);
  }
  //@}

  /// \name Debug functions
  //@{
  /// dump the contents in this DAG node
  const std::string dump(int = OPERATOR_VALUE) const;
  /// print debug information in list mode
  virtual void debugList(int level, int depthLimit) const = 0;
  /// print debug information in tree mode
  virtual void debugTree(int level, int indent, int depthLimit) const = 0;
  //@}

  /// \name I/O Stream
  //@{
  friend std::ostream& operator<<(std::ostream&, ExprRep&);
  //@}

private:
  int refCount;    // reference count

public:
  enum {OPERATOR_ONLY, VALUE_ONLY, OPERATOR_VALUE, FULL_DUMP};

  NodeInfo* nodeInfo;	///< node information
  filteredFp ffVal;	///< filtered value

  /// \name Approximation Functions
  //@{
  /// initialize nodeInfo
  virtual void initNodeInfo() = 0;
  /// compute the sign, uMSB, lMSB, etc.
  virtual void computeExactFlags() = 0;
  /// compute the minimal root bound
  extLong computeBound();
  /// driver function to approximate
  void approx(const extLong& relPrec, const extLong& absPrec);
  /// compute an approximate value satifying the specified precisions
  virtual void computeApproxValue(const extLong&, const extLong&) = 0;
  /// Test whether the current approx. value satisfies [relPrec, absPrec]
  bool withinKnownPrecision(const extLong&, const extLong&);
  //@}

  /// \name Misc Functions
  //@{
  /// reduce current node