diff options
author | Tim King <taking@cs.nyu.edu> | 2012-04-17 16:07:22 +0000 |
---|---|---|
committer | Tim King <taking@cs.nyu.edu> | 2012-04-17 16:07:22 +0000 |
commit | ccd77233892ace44fd4852999e66534d1c2283ea (patch) | |
tree | a856cacd24508a5839fcdbe728583ff055b64e34 /src/theory/arith/arith_prop_manager.cpp | |
parent | 9644b6e12fbd3b649daafa43c5400d272e27bfb4 (diff) |
Merges branches/arithmetic/atom-database r2979 through 3247 into trunk. Below is a highlight of the changes:
- This introduces a new normal form to arithmetic.
-- Equalities and disequalities are in solved form.
Roughly speaking this means: (= x (+ y z)) is in normal form.
(See the comments in normal_form.h for what this formally requires.)
-- The normal form for inequality atoms always uses GEQ and GT instead of GEQ and LEQ.
Integer atoms always use GEQ.
- Constraint was added to TheoryArith.
-- A constraint is a triple of (k x v) where:
--- k is the type of the constraint (either LowerBound, UpperBound, Equality or Disequality),
--- x is an ArithVar, and
--- v is a DeltaRational value.
-- Constraints are always attached to a ConstraintDatabase.
-- A Constraint has its negation in the ConstraintDatabase [at least for now].
-- Every constraint belongs to a set of constraints for each ArithVar sorted by the delta rational values.
-- This set can be iterated over and provides efficient access to other constraints for this variable.
-- A literal may be attached to a constraint.
-- Constraints with attached literals may be marked as being asserted to the theory (sat context dependent).
-- Constraints can be propagated.
-- Every constraint has a proof (sat context dependent).
-- Proofs can be explained for either conflicts or propagations (if the node was propagated). (These proofs may be different.)
-- Equalities and disequalities can be marked as being split (user context dependent)
- This removes and replaces:
-- src/theory/arith/arith_prop_manager.*
-- src/theory/arith/atom_database.*
-- src/theory/arith/ordered_set.h
- Added isZero(), isOne() and isNegativeOne() to Rational and Integer.
- Added operator+ to CDList::const_iterator.
- Added const_iterator to CDQueue.
- Changes to regression tests.
Diffstat (limited to 'src/theory/arith/arith_prop_manager.cpp')
-rw-r--r-- | src/theory/arith/arith_prop_manager.cpp | 173 |
1 files changed, 0 insertions, 173 deletions
diff --git a/src/theory/arith/arith_prop_manager.cpp b/src/theory/arith/arith_prop_manager.cpp deleted file mode 100644 index dc9b0ddb9..000000000 --- a/src/theory/arith/arith_prop_manager.cpp +++ /dev/null @@ -1,173 +0,0 @@ -/********************* */ -/*! \file arith_prop_manager.cpp - ** \verbatim - ** Original author: taking - ** Major contributors: none - ** Minor contributors (to current version): none - ** This file is part of the CVC4 prototype. - ** Copyright (c) 2009, 2010, 2011 The Analysis of Computer Systems Group (ACSys) - ** Courant Institute of Mathematical Sciences - ** New York University - ** See the file COPYING in the top-level source directory for licensing - ** information.\endverbatim - ** - ** \brief [[ Add one-line brief description here ]] - ** - ** [[ Add lengthier description here ]] - ** \todo document this file - **/ - - -#include "theory/arith/arith_prop_manager.h" - -#include "theory/arith/arith_utilities.h" -#include "context/context.h" -#include "context/cdlist.h" -#include "context/cdhashmap.h" -#include "context/cdo.h" - -using namespace CVC4::kind; -using namespace std; - - -namespace CVC4 { -namespace theory { -namespace arith { - -bool ArithPropManager::isAsserted(TNode n) const{ - Node satValue = d_valuation.getSatValue(n); - if(satValue.isNull()){ - return false; - }else{ - //Assert(satValue.getConst<bool>()); - return true; - } -} - - -Node ArithPropManager::strictlyWeakerAssertedUpperBound(ArithVar v, const DeltaRational& b) const{ - Node bound = boundAsNode(true, v, b); - - Assert(b.getInfinitesimalPart() <= 0); - bool largeEpsilon = (b.getInfinitesimalPart() < -1); - - Node weaker = bound; - do { - if(largeEpsilon){ - weaker = d_atomDatabase.getBestImpliedUpperBound(weaker); - largeEpsilon = false; - }else{ - weaker = d_atomDatabase.getWeakerImpliedUpperBound(weaker); - } - }while(!weaker.isNull() && !isAsserted(weaker)); - return weaker; -} - -Node ArithPropManager::strictlyWeakerAssertedLowerBound(ArithVar v, const DeltaRational& b) const{ - Debug("ArithPropManager") << "strictlyWeakerAssertedLowerBound" << endl; - Node bound = boundAsNode(false, v, b); - - Assert(b.getInfinitesimalPart() >= 0); - bool largeEpsilon = (b.getInfinitesimalPart() > 1); - - Node weaker = bound; - Debug("ArithPropManager") << bound << b << endl; - do { - if(largeEpsilon){ - weaker = d_atomDatabase.getBestImpliedLowerBound(weaker); - largeEpsilon = false; - }else{ - weaker = d_atomDatabase.getWeakerImpliedLowerBound(weaker); - } - }while(!weaker.isNull() && !isAsserted(weaker)); - Debug("ArithPropManager") << "res: " << weaker << endl; - return weaker; -} - -Node ArithPropManager::getBestImpliedLowerBound(ArithVar v, const DeltaRational& b) const{ - Node bound = boundAsNode(false, v, b); - return d_atomDatabase.getBestImpliedLowerBound(bound); -} -Node ArithPropManager::getBestImpliedUpperBound(ArithVar v, const DeltaRational& b) const{ - Node bound = boundAsNode(true, v, b); - return d_atomDatabase.getBestImpliedUpperBound(bound); -} - -Node ArithPropManager::boundAsNode(bool upperbound, ArithVar var, const DeltaRational& b) const { - Assert((!upperbound) || (b.getInfinitesimalPart() <= 0) ); - Assert(upperbound || (b.getInfinitesimalPart() >= 0) ); - - Node varAsNode = d_arithvarNodeMap.asNode(var); - Kind kind; - bool negate; - if(upperbound){ - negate = b.getInfinitesimalPart() < 0; - kind = negate ? GEQ : LEQ; - } else{ - negate = b.getInfinitesimalPart() > 0; - kind = negate ? LEQ : GEQ; - } - - Node righthand = mkRationalNode(b.getNoninfinitesimalPart()); - Node bAsNode = NodeBuilder<2>(kind) << varAsNode << righthand; - - if(negate){ - bAsNode = NodeBuilder<1>(NOT) << bAsNode; - } - - return bAsNode; -} - -bool ArithPropManager::propagateArithVar(bool upperbound, ArithVar var, const DeltaRational& b, TNode reason){ - bool success = false; - - ++d_statistics.d_propagateArithVarCalls; - - Node bAsNode = boundAsNode(upperbound, var ,b); - - Node bestImplied = upperbound ? - d_atomDatabase.getBestImpliedUpperBound(bAsNode): - d_atomDatabase.getBestImpliedLowerBound(bAsNode); - - Debug("ArithPropManager") << upperbound <<","<< var <<","<< b <<","<< reason << endl - << bestImplied << endl; - - if(!bestImplied.isNull()){ - bool asserted = isAsserted(bestImplied); - - if( !asserted && !isPropagated(bestImplied)){ - propagate(bestImplied, reason, false); - ++d_statistics.d_addedPropagation; - success = true; - }else if(!asserted){ - ++d_statistics.d_alreadyPropagatedNode; - }else if(!isPropagated(bestImplied)){ - ++d_statistics.d_alreadySetSatLiteral; - } - } - return success; -} - -ArithPropManager::Statistics::Statistics(): - d_propagateArithVarCalls("arith::prop-manager::propagateArithVarCalls",0), - d_addedPropagation("arith::prop-manager::addedPropagation",0), - d_alreadySetSatLiteral("arith::prop-manager::alreadySetSatLiteral",0), - d_alreadyPropagatedNode("arith::prop-manager::alreadyPropagatedNode",0) -{ - StatisticsRegistry::registerStat(&d_propagateArithVarCalls); - StatisticsRegistry::registerStat(&d_alreadySetSatLiteral); - StatisticsRegistry::registerStat(&d_alreadyPropagatedNode); - StatisticsRegistry::registerStat(&d_addedPropagation); -} - -ArithPropManager::Statistics::~Statistics() -{ - StatisticsRegistry::unregisterStat(&d_propagateArithVarCalls); - StatisticsRegistry::unregisterStat(&d_alreadySetSatLiteral); - StatisticsRegistry::unregisterStat(&d_alreadyPropagatedNode); - StatisticsRegistry::unregisterStat(&d_addedPropagation); -} - -}; /* namesapce arith */ -}; /* namespace theory */ -}; /* namespace CVC4 */ |