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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
/********************* */
/*! \file symmetry_breaking.h
** \verbatim
** Top contributors (to current version):
** Andrew Reynolds, Tim King
** This file is part of the CVC4 project.
** Copyright (c) 2009-2016 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 Pre-process step for first-order reasoning
**/
#include "cvc4_private.h"
#ifndef __CVC4__QUANT_SYMMETRY_BREAKING_H
#define __CVC4__QUANT_SYMMETRY_BREAKING_H
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include "context/cdchunk_list.h"
#include "context/cdhashmap.h"
#include "context/context.h"
#include "context/context_mm.h"
#include "expr/node.h"
#include "expr/type_node.h"
#include "theory/sort_inference.h"
#include "theory/theory.h"
namespace CVC4 {
namespace theory {
namespace uf {
class StrongSolverTheoryUF;
}
class SubsortSymmetryBreaker {
typedef context::CDHashMap<Node, bool, NodeHashFunction> NodeBoolMap;
typedef context::CDHashMap<Node, int, NodeHashFunction> NodeIntMap;
typedef context::CDHashMap<Node, Node, NodeHashFunction> NodeNodeMap;
//typedef context::CDChunkList<int> IntList;
typedef context::CDList<Node> NodeList;
typedef context::CDHashMap<Node, NodeList*, NodeHashFunction> NodeListMap;
private:
/** quantifiers engine */
QuantifiersEngine* d_qe;
eq::EqualityEngine * getEqualityEngine();
bool areDisequal( Node n1, Node n2 );
bool areEqual( Node n1, Node n2 );
Node getRepresentative( Node n );
uf::StrongSolverTheoryUF * getStrongSolver();
std::vector< Node > d_unit_lemmas;
Node d_true;
context::CDO< bool > d_conflict;
public:
SubsortSymmetryBreaker( QuantifiersEngine* qe, context::Context* c );
~SubsortSymmetryBreaker(){}
private:
class TypeInfo {
public:
TypeInfo( context::Context* c );
context::CDO< int > d_max_dom_const_sort;
context::CDO< bool > d_has_dom_const_sort;
};
class SubSortInfo {
public:
SubSortInfo( context::Context* c );
//list of all nodes from this (sub)type
std::vector< Node > d_nodes;
//the current domain constants for this (sub)type
NodeList d_dom_constants;
//# nodes in d_nodes that have been domain constants, size of this distinct # of domain constants seen
unsigned d_dc_nodes;
//the node we are currently watching to become a domain constant
context::CDO< int > d_first_active;
//node to id
std::map< Node, unsigned > d_node_to_id;
Node getBaseConstant() { return d_nodes.empty() ? Node::null() : d_nodes[0]; }
bool hasDomainConstant( Node n );
unsigned getNumDomainConstants();
Node getDomainConstant( int i );
Node getFirstActive(eq::EqualityEngine * ee);
};
std::map< TypeNode, std::vector< int > > d_sub_sorts;
std::map< int, TypeNode > d_sid_to_type;
std::map< TypeNode, TypeInfo * > d_t_info;
std::map< int, SubSortInfo * > d_type_info;
TypeInfo * getTypeInfo( TypeNode tn );
SubSortInfo * getSubSortInfo( TypeNode tn, int sid );
void processFirstActive( TypeNode tn, int sid, int curr_card );
private:
//void printDebugNodeInfo( const char * c, Node n );
void printDebugSubSortInfo( const char * c, TypeNode tn, int sid );
/** fact list */
std::vector< Node > d_pending_lemmas;
std::vector< Node > d_lemmas;
public:
/** new node */
void newEqClass( Node n );
/** merge */
void merge( Node a, Node b );
/** assert disequal */
void assertDisequal( Node a, Node b );
/** check */
bool check( Theory::Effort level );
};
}
}
#endif
|