1 //
2 // untitled
3 //
4 // Created by on 2008-04-16.
5 // Copyright (c) 2008 The PolyBoRi Team. See LICENSE file.
6 // PolyBoRi Project
7 #include <polybori/groebner/groebner_defs.h>
8 #include <polybori/groebner/polynomial_properties.h>
9 #include <iostream>
10 using namespace std;
11 BEGIN_NAMESPACE_PBORIGB
12
do_is_rewriteable(const Polynomial & p,const MonomialSet & leading_terms)13 Polynomial do_is_rewriteable(const Polynomial& p, const MonomialSet& leading_terms){
14 //don't change ordering
15 if (p.isZero()) return p.ring().zero();
16 if (leading_terms.ownsOne()) return p.ring().one();
17 //case leading terms contains one is checked
18 MonomialSet::navigator l_nav=leading_terms.navigation();
19 Polynomial::navigator p_nav=p.navigation();
20 idx_type p_i=*p_nav;
21 idx_type l_i=*l_nav;
22 bool changed=true;
23 while (changed){
24 changed=false;
25 while ((l_i=(*l_nav))<p_i){
26 l_nav.incrementElse();
27 changed=true;
28 }
29 //idx_type l_i=*l_nav;
30 while(((p_i=*p_nav)<l_i)&& (p_nav.elseBranch().isEmpty())){
31 p_nav.incrementThen();
32 changed=true;
33 }
34 while((!(p_nav.isConstant()))&&(l_i==p_i) &&(p_nav.elseBranch().isEmpty()) && (l_nav.elseBranch().isEmpty())){
35 p_nav.incrementThen();
36 l_nav.incrementThen();
37 l_i=*l_nav;
38 p_i=*p_nav;
39 changed=true;
40 }
41 }
42 PBORI_ASSERT(l_i==*l_nav);
43 PBORI_ASSERT(p_i==*p_nav);
44 PBORI_ASSERT(p_i<=l_i);
45
46
47
48 typedef PBORI::CacheManager<CCacheTypes::mod_mon_set>
49 cache_mgr_type_mod_mon_set;
50 cache_mgr_type_mod_mon_set cache_mgr_mod_mon_set(p.ring());
51 typedef PBORI::CacheManager<CCacheTypes::is_rewriteable>
52 cache_mgr_type;
53 cache_mgr_type cache_mgr(p.ring());
54 PBORI_ASSERT(!(p.isZero()));
55 PBORI_ASSERT(!(p_nav.isEmpty()));
56 if (cache_mgr.generate(l_nav).ownsOne()){
57 return cache_mgr.one();
58 }
59 PBORI_ASSERT(!(cache_mgr.generate(l_nav).ownsOne()));
60
61 if (p_nav.isTerminated()){
62 return cache_mgr.zero();
63 }
64 if (l_nav.isEmpty()){
65 return cache_mgr.zero();
66 }
67 PBORI_ASSERT(!(p_nav.isConstant()));
68
69 Polynomial::navigator cached= cache_mgr.find(p_nav,l_nav);
70 if (cached.isValid()) {
71 return Polynomial(cache_mgr.generate(cached));
72
73 }
74 MonomialSet::navigator cached_mod_mon_set= cache_mgr.find(p_nav,l_nav);
75 if (cached_mod_mon_set.isValid()){
76 return (cached_mod_mon_set==p_nav)?cache_mgr.zero():cache_mgr.one();
77 }
78
79 PBORI_ASSERT (!(l_nav.isConstant()));
80 Polynomial p0=cache_mgr.generate(p_nav.elseBranch());
81 Polynomial p1=cache_mgr.generate(p_nav.thenBranch());
82 Polynomial res(p.ring());
83 if (l_i>p_i){
84 MonomialSet l_curr=cache_mgr.generate(l_nav);
85 if (((do_is_rewriteable(p0,l_curr)).isOne())||(do_is_rewriteable(p1,l_curr).isOne())){
86 res=cache_mgr.one();
87 }else{
88 res= cache_mgr.zero();
89 }
90 } else{
91 PBORI_ASSERT(l_i==p_i);
92 MonomialSet l0=cache_mgr.generate(l_nav.elseBranch());
93 MonomialSet l1=cache_mgr.generate(l_nav.thenBranch());
94 if ((do_is_rewriteable(p0,l0).isOne())||(do_is_rewriteable(p1,l1).isOne())||(do_is_rewriteable(p1,l0).isOne())){
95 res=cache_mgr.one();
96 } else{
97 res= cache_mgr.zero();
98 }
99 }
100 cache_mgr.insert(p_nav,l_nav,res.navigation());
101 return res;
102
103 }
is_rewriteable(const Polynomial & p,const MonomialSet & leading_terms)104 bool is_rewriteable(const Polynomial& p, const MonomialSet& leading_terms){
105 return (do_is_rewriteable(p,leading_terms).isOne())?true:false;
106 }
107 END_NAMESPACE_PBORIGB
108