1 |
|
/****************************************************************************** |
2 |
|
* Top contributors (to current version): |
3 |
|
* Morgan Deters |
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 |
|
* Path-compressing, backtrackable union-find using an undo |
14 |
|
* stack. Refactored from the UF union-find. |
15 |
|
*/ |
16 |
|
|
17 |
|
#include <iostream> |
18 |
|
|
19 |
|
#include "expr/node.h" |
20 |
|
#include "theory/arrays/union_find.h" |
21 |
|
|
22 |
|
using namespace std; |
23 |
|
|
24 |
|
namespace cvc5 { |
25 |
|
namespace theory { |
26 |
|
namespace arrays { |
27 |
|
|
28 |
|
template <class NodeType, class NodeHash> |
29 |
|
void UnionFind<NodeType, NodeHash>::notify() { |
30 |
|
Trace("arraysuf") << "arraysUF cancelling : " << d_offset << " < " << d_trace.size() << " ?" << endl; |
31 |
|
while(d_offset < d_trace.size()) { |
32 |
|
pair<TNode, TNode> p = d_trace.back(); |
33 |
|
if(p.second.isNull()) { |
34 |
|
d_map.erase(p.first); |
35 |
|
Trace("arraysuf") << "arraysUF " << d_trace.size() << " erasing " << p.first << endl; |
36 |
|
} else { |
37 |
|
d_map[p.first] = p.second; |
38 |
|
Trace("arraysuf") << "arraysUF " << d_trace.size() << " replacing " << p << endl; |
39 |
|
} |
40 |
|
d_trace.pop_back(); |
41 |
|
} |
42 |
|
Trace("arraysuf") << "arraysUF cancelling finished." << endl; |
43 |
|
} |
44 |
|
|
45 |
|
// The following declarations allow us to put functions in the .cpp file |
46 |
|
// instead of the header, since we know which instantiations are needed. |
47 |
|
|
48 |
|
template void UnionFind<Node, std::hash<Node>>::notify(); |
49 |
|
|
50 |
|
template void UnionFind<TNode, std::hash<TNode>>::notify(); |
51 |
|
|
52 |
|
} // namespace arrays |
53 |
|
} // namespace theory |
54 |
28191 |
} // namespace cvc5 |