1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Mudathir Mohamed, Andres Noetzli |
4 |
|
* |
5 |
|
* This file is part of the cvc5 project. |
6 |
|
* |
7 |
|
* Copyright (c) 2009-2021 by the authors listed in the file AUTHORS |
8 |
|
* in the top-level source directory and their institutional affiliations. |
9 |
|
* All rights reserved. See the file COPYING in the top-level source |
10 |
|
* directory for licensing information. |
11 |
|
* **************************************************************************** |
12 |
|
* |
13 |
|
* Set enumerator implementation. |
14 |
|
*/ |
15 |
|
|
16 |
|
#include "theory/sets/theory_sets_type_enumerator.h" |
17 |
|
|
18 |
|
#include "util/bitvector.h" |
19 |
|
|
20 |
|
namespace cvc5 { |
21 |
|
namespace theory { |
22 |
|
namespace sets { |
23 |
|
|
24 |
37 |
SetEnumerator::SetEnumerator(TypeNode type, TypeEnumeratorProperties* tep) |
25 |
|
: TypeEnumeratorBase<SetEnumerator>(type), |
26 |
37 |
d_nodeManager(NodeManager::currentNM()), |
27 |
74 |
d_elementEnumerator(type.getSetElementType(), tep), |
28 |
|
d_isFinished(false), |
29 |
|
d_currentSetIndex(0), |
30 |
148 |
d_currentSet() |
31 |
|
{ |
32 |
37 |
d_currentSet = d_nodeManager->mkConst(EmptySet(type)); |
33 |
37 |
} |
34 |
|
|
35 |
7 |
SetEnumerator::SetEnumerator(const SetEnumerator& enumerator) |
36 |
14 |
: TypeEnumeratorBase<SetEnumerator>(enumerator.getType()), |
37 |
7 |
d_nodeManager(enumerator.d_nodeManager), |
38 |
|
d_elementEnumerator(enumerator.d_elementEnumerator), |
39 |
7 |
d_isFinished(enumerator.d_isFinished), |
40 |
7 |
d_currentSetIndex(enumerator.d_currentSetIndex), |
41 |
42 |
d_currentSet(enumerator.d_currentSet) |
42 |
|
{ |
43 |
7 |
} |
44 |
|
|
45 |
80 |
SetEnumerator::~SetEnumerator() {} |
46 |
|
|
47 |
173 |
Node SetEnumerator::operator*() |
48 |
|
{ |
49 |
173 |
if (d_isFinished) |
50 |
|
{ |
51 |
18 |
throw NoMoreValuesException(getType()); |
52 |
|
} |
53 |
|
|
54 |
310 |
Trace("set-type-enum") << "SetEnumerator::operator* d_currentSet = " |
55 |
155 |
<< d_currentSet << std::endl; |
56 |
|
|
57 |
155 |
return d_currentSet; |
58 |
|
} |
59 |
|
|
60 |
99 |
SetEnumerator& SetEnumerator::operator++() |
61 |
|
{ |
62 |
99 |
if (d_isFinished) |
63 |
|
{ |
64 |
32 |
Trace("set-type-enum") << "SetEnumerator::operator++ finished!" |
65 |
16 |
<< std::endl; |
66 |
32 |
Trace("set-type-enum") << "SetEnumerator::operator++ d_currentSet = " |
67 |
16 |
<< d_currentSet << std::endl; |
68 |
16 |
return *this; |
69 |
|
} |
70 |
|
|
71 |
83 |
d_currentSetIndex++; |
72 |
|
|
73 |
|
// if the index is a power of 2, get a new element from d_elementEnumerator |
74 |
83 |
if (d_currentSetIndex == static_cast<unsigned>(1 << d_elementsSoFar.size())) |
75 |
|
{ |
76 |
|
// if there are no more values from d_elementEnumerator, set d_isFinished |
77 |
|
// to true |
78 |
43 |
if (d_elementEnumerator.isFinished()) |
79 |
|
{ |
80 |
6 |
d_isFinished = true; |
81 |
|
|
82 |
12 |
Trace("set-type-enum") |
83 |
6 |
<< "SetEnumerator::operator++ finished!" << std::endl; |
84 |
12 |
Trace("set-type-enum") |
85 |
6 |
<< "SetEnumerator::operator++ d_currentSet = " << d_currentSet |
86 |
6 |
<< std::endl; |
87 |
6 |
return *this; |
88 |
|
} |
89 |
|
|
90 |
|
// get a new element and return it as a singleton set |
91 |
74 |
Node element = *d_elementEnumerator; |
92 |
37 |
d_elementsSoFar.push_back(element); |
93 |
74 |
TypeNode elementType = d_elementEnumerator.getType(); |
94 |
37 |
d_currentSet = d_nodeManager->mkSingleton(elementType, element); |
95 |
37 |
d_elementEnumerator++; |
96 |
|
} |
97 |
|
else |
98 |
|
{ |
99 |
|
// determine which elements are included in the set |
100 |
80 |
BitVector indices = BitVector(d_elementsSoFar.size(), d_currentSetIndex); |
101 |
80 |
std::vector<Node> elements; |
102 |
166 |
for (unsigned i = 0; i < d_elementsSoFar.size(); i++) |
103 |
|
{ |
104 |
|
// add the element to the set if its corresponding bit is set |
105 |
126 |
if (indices.isBitSet(i)) |
106 |
|
{ |
107 |
96 |
elements.push_back(d_elementsSoFar[i]); |
108 |
|
} |
109 |
|
} |
110 |
80 |
d_currentSet = NormalForm::elementsToSet( |
111 |
120 |
std::set<TNode>(elements.begin(), elements.end()), getType()); |
112 |
|
} |
113 |
|
|
114 |
77 |
Assert(d_currentSet.isConst()); |
115 |
77 |
Assert(d_currentSet == Rewriter::rewrite(d_currentSet)); |
116 |
|
|
117 |
154 |
Trace("set-type-enum") << "SetEnumerator::operator++ d_elementsSoFar = " |
118 |
77 |
<< d_elementsSoFar << std::endl; |
119 |
154 |
Trace("set-type-enum") << "SetEnumerator::operator++ d_currentSet = " |
120 |
77 |
<< d_currentSet << std::endl; |
121 |
|
|
122 |
77 |
return *this; |
123 |
|
} |
124 |
|
|
125 |
188 |
bool SetEnumerator::isFinished() |
126 |
|
{ |
127 |
376 |
Trace("set-type-enum") << "SetEnumerator::isFinished = " << d_isFinished |
128 |
188 |
<< std::endl; |
129 |
188 |
return d_isFinished; |
130 |
|
} |
131 |
|
|
132 |
|
} // namespace sets |
133 |
|
} // namespace theory |
134 |
22746 |
} // namespace cvc5 |