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 |
|
namespace cvc5 { |
19 |
|
namespace theory { |
20 |
|
namespace sets { |
21 |
|
|
22 |
40 |
SetEnumerator::SetEnumerator(TypeNode type, TypeEnumeratorProperties* tep) |
23 |
|
: TypeEnumeratorBase<SetEnumerator>(type), |
24 |
40 |
d_nodeManager(NodeManager::currentNM()), |
25 |
80 |
d_elementEnumerator(type.getSetElementType(), tep), |
26 |
|
d_isFinished(false), |
27 |
|
d_currentSetIndex(0), |
28 |
160 |
d_currentSet() |
29 |
|
{ |
30 |
40 |
d_currentSet = d_nodeManager->mkConst(EmptySet(type)); |
31 |
40 |
} |
32 |
|
|
33 |
10 |
SetEnumerator::SetEnumerator(const SetEnumerator& enumerator) |
34 |
20 |
: TypeEnumeratorBase<SetEnumerator>(enumerator.getType()), |
35 |
10 |
d_nodeManager(enumerator.d_nodeManager), |
36 |
|
d_elementEnumerator(enumerator.d_elementEnumerator), |
37 |
10 |
d_isFinished(enumerator.d_isFinished), |
38 |
10 |
d_currentSetIndex(enumerator.d_currentSetIndex), |
39 |
60 |
d_currentSet(enumerator.d_currentSet) |
40 |
|
{ |
41 |
10 |
} |
42 |
|
|
43 |
92 |
SetEnumerator::~SetEnumerator() {} |
44 |
|
|
45 |
182 |
Node SetEnumerator::operator*() |
46 |
|
{ |
47 |
182 |
if (d_isFinished) |
48 |
|
{ |
49 |
18 |
throw NoMoreValuesException(getType()); |
50 |
|
} |
51 |
|
|
52 |
328 |
Trace("set-type-enum") << "SetEnumerator::operator* d_currentSet = " |
53 |
164 |
<< d_currentSet << std::endl; |
54 |
|
|
55 |
164 |
return d_currentSet; |
56 |
|
} |
57 |
|
|
58 |
102 |
SetEnumerator& SetEnumerator::operator++() |
59 |
|
{ |
60 |
102 |
if (d_isFinished) |
61 |
|
{ |
62 |
32 |
Trace("set-type-enum") << "SetEnumerator::operator++ finished!" |
63 |
16 |
<< std::endl; |
64 |
32 |
Trace("set-type-enum") << "SetEnumerator::operator++ d_currentSet = " |
65 |
16 |
<< d_currentSet << std::endl; |
66 |
16 |
return *this; |
67 |
|
} |
68 |
|
|
69 |
86 |
d_currentSetIndex++; |
70 |
|
|
71 |
|
// if the index is a power of 2, get a new element from d_elementEnumerator |
72 |
86 |
if (d_currentSetIndex == static_cast<unsigned>(1 << d_elementsSoFar.size())) |
73 |
|
{ |
74 |
|
// if there are no more values from d_elementEnumerator, set d_isFinished |
75 |
|
// to true |
76 |
46 |
if (d_elementEnumerator.isFinished()) |
77 |
|
{ |
78 |
6 |
d_isFinished = true; |
79 |
|
|
80 |
12 |
Trace("set-type-enum") |
81 |
6 |
<< "SetEnumerator::operator++ finished!" << std::endl; |
82 |
12 |
Trace("set-type-enum") |
83 |
6 |
<< "SetEnumerator::operator++ d_currentSet = " << d_currentSet |
84 |
6 |
<< std::endl; |
85 |
6 |
return *this; |
86 |
|
} |
87 |
|
|
88 |
|
// get a new element and return it as a singleton set |
89 |
80 |
Node element = *d_elementEnumerator; |
90 |
40 |
d_elementsSoFar.push_back(element); |
91 |
80 |
TypeNode elementType = d_elementEnumerator.getType(); |
92 |
40 |
d_currentSet = d_nodeManager->mkSingleton(elementType, element); |
93 |
40 |
d_elementEnumerator++; |
94 |
|
} |
95 |
|
else |
96 |
|
{ |
97 |
|
// determine which elements are included in the set |
98 |
80 |
BitVector indices = BitVector(d_elementsSoFar.size(), d_currentSetIndex); |
99 |
80 |
std::vector<Node> elements; |
100 |
166 |
for (unsigned i = 0; i < d_elementsSoFar.size(); i++) |
101 |
|
{ |
102 |
|
// add the element to the set if its corresponding bit is set |
103 |
126 |
if (indices.isBitSet(i)) |
104 |
|
{ |
105 |
96 |
elements.push_back(d_elementsSoFar[i]); |
106 |
|
} |
107 |
|
} |
108 |
80 |
d_currentSet = NormalForm::elementsToSet( |
109 |
120 |
std::set<TNode>(elements.begin(), elements.end()), getType()); |
110 |
|
} |
111 |
|
|
112 |
80 |
Assert(d_currentSet.isConst()); |
113 |
80 |
Assert(d_currentSet == Rewriter::rewrite(d_currentSet)); |
114 |
|
|
115 |
160 |
Trace("set-type-enum") << "SetEnumerator::operator++ d_elementsSoFar = " |
116 |
80 |
<< d_elementsSoFar << std::endl; |
117 |
160 |
Trace("set-type-enum") << "SetEnumerator::operator++ d_currentSet = " |
118 |
80 |
<< d_currentSet << std::endl; |
119 |
|
|
120 |
80 |
return *this; |
121 |
|
} |
122 |
|
|
123 |
200 |
bool SetEnumerator::isFinished() |
124 |
|
{ |
125 |
400 |
Trace("set-type-enum") << "SetEnumerator::isFinished = " << d_isFinished |
126 |
200 |
<< std::endl; |
127 |
200 |
return d_isFinished; |
128 |
|
} |
129 |
|
|
130 |
|
} // namespace sets |
131 |
|
} // namespace theory |
132 |
27735 |
} // namespace cvc5 |