blob: 58ad36da9cc6f4b3e974027c86f78d190feca054 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
/********************* */
/*! \file node_trie.cpp
** \verbatim
** Top contributors (to current version):
** Andrew Reynolds
** This file is part of the CVC4 project.
** Copyright (c) 2009-2020 by the authors listed in the file AUTHORS
** in the top-level source directory and their institutional affiliations.
** All rights reserved. See the file COPYING in the top-level source
** directory for licensing information.\endverbatim
**
** \brief Implementation of a trie class for Nodes and TNodes.
**/
#include "expr/node_trie.h"
namespace CVC4 {
namespace theory {
template <bool ref_count>
NodeTemplate<ref_count> NodeTemplateTrie<ref_count>::existsTerm(
const std::vector<NodeTemplate<ref_count>>& reps) const
{
const NodeTemplateTrie<ref_count>* tnt = this;
typename std::map<NodeTemplate<ref_count>,
NodeTemplateTrie<ref_count>>::const_iterator it;
for (const NodeTemplate<ref_count> r : reps)
{
it = tnt->d_data.find(r);
if (it == tnt->d_data.end())
{
// didn't find this child, return null
return Node::null();
}
tnt = &it->second;
}
if (tnt->d_data.empty())
{
return Node::null();
}
return tnt->d_data.begin()->first;
}
template TNode NodeTemplateTrie<false>::existsTerm(
const std::vector<TNode>& reps) const;
template Node NodeTemplateTrie<true>::existsTerm(
const std::vector<Node>& reps) const;
template <bool ref_count>
NodeTemplate<ref_count> NodeTemplateTrie<ref_count>::addOrGetTerm(
NodeTemplate<ref_count> n, const std::vector<NodeTemplate<ref_count>>& reps)
{
NodeTemplateTrie<ref_count>* tnt = this;
for (const NodeTemplate<ref_count> r : reps)
{
tnt = &(tnt->d_data[r]);
}
if (tnt->d_data.empty())
{
// Store n in d_data. This should be interpretted as the "data" and not as a
// reference to a child.
tnt->d_data[n].clear();
return n;
}
return tnt->d_data.begin()->first;
}
template TNode NodeTemplateTrie<false>::addOrGetTerm(
TNode n, const std::vector<TNode>& reps);
template Node NodeTemplateTrie<true>::addOrGetTerm(
Node n, const std::vector<Node>& reps);
template <bool ref_count>
void NodeTemplateTrie<ref_count>::debugPrint(const char* c,
unsigned depth) const
{
for (const std::pair<const NodeTemplate<ref_count>,
NodeTemplateTrie<ref_count>>& p : d_data)
{
for (unsigned i = 0; i < depth; i++)
{
Trace(c) << " ";
}
Trace(c) << p.first << std::endl;
p.second.debugPrint(c, depth + 1);
}
}
template void NodeTemplateTrie<false>::debugPrint(const char* c,
unsigned depth) const;
template void NodeTemplateTrie<true>::debugPrint(const char* c,
unsigned depth) const;
} // namespace theory
} // namespace CVC4
|