7 #define EDGE_IS_VAR_CONSTANT 2
9 #define EDGE_MASK (NEGATE_EDGE | EDGE_IS_VAR_CONSTANT)
14 typedef struct Edge Edge;
17 typedef struct Node Node;
31 typedef enum NodeType NodeType;
39 typedef struct Node Node;
43 IncrementalSolver *solver;
48 typedef struct CNF CNF;
50 static inline Edge constraintNegate(Edge e) {
51 Edge eneg = { (Node *) (((uintptr_t) e.node_ptr) ^ NEGATE_EDGE)};
55 static inline bool sameNodeVarEdge(Edge e1, Edge e2) {
56 return !(((uintptr_t) e1.node_ptr ^ (uintptr_t) e2.node_ptr) & (~(uintptr_t) NEGATE_EDGE));
59 static inline bool sameSignEdge(Edge e1, Edge e2) {
60 return !(((uintptr_t) e1.node_ptr ^ (uintptr_t) e2.node_ptr) & NEGATE_EDGE);
63 static inline bool sameNodeOppSign(Edge e1, Edge e2) {
64 return (((uintptr_t) e1.node_ptr) ^ ((uintptr_t)e2.node_ptr)) == NEGATE_EDGE;
67 static inline bool isNegEdge(Edge e) {
68 return ((uintptr_t)e.node_ptr) & NEGATE_EDGE;
71 static inline bool isPosEdge(Edge e) {
72 return !(((uintptr_t)e.node_ptr) & NEGATE_EDGE);
75 static inline bool isNodeEdge(Edge e) {
76 return !(((uintptr_t)e.node_ptr) & EDGE_IS_VAR_CONSTANT);
79 static inline bool isNegNodeEdge(Edge e) {
80 return (((uintptr_t) e.node_ptr) & (NEGATE_EDGE | EDGE_IS_VAR_CONSTANT)) == NEGATE_EDGE;
83 static inline Node *getNodePtrFromEdge(Edge e) {
84 return (Node *) (((uintptr_t) e.node_ptr) & ~((uintptr_t) EDGE_MASK));
87 static inline NodeType getNodeType(Edge e) {
88 Node *n = getNodePtrFromEdge(e);
92 static inline bool equalsEdge(Edge e1, Edge e2) {
93 return e1.node_ptr == e2.node_ptr;
96 static inline bool ltEdge(Edge e1, Edge e2) {
97 return (uintptr_t) e1.node_ptr < (uintptr_t) e2.node_ptr;
100 static inline uint getNodeSize(Edge e) {
101 Node *n = getNodePtrFromEdge(e);
105 static inline Edge *getEdgeArray(Edge e) {
106 Node *n = getNodePtrFromEdge(e);
110 static inline Edge getNonNeg(Edge e) {
111 Edge enew = {(Node *)(((uintptr_t)e.node_ptr) & (~((uintptr_t)NEGATE_EDGE)))};
115 static inline bool edgeIsConst(Edge e) {
116 return (((uintptr_t) e.node_ptr) & ~((uintptr_t)NEGATE_EDGE)) == EDGE_IS_VAR_CONSTANT;
119 static inline bool edgeIsNull(Edge e) {
120 return e.node_ptr == NULL;
123 static inline bool edgeIsVarConst(Edge e) {
124 return ((uintptr_t)e.node_ptr) & EDGE_IS_VAR_CONSTANT;
127 static inline Edge constraintNegateIf(Edge e, bool negate) {
128 Edge eret = {(Node *)(((uintptr_t)e.node_ptr) ^ negate)};
132 static inline Literal getEdgeVar(Edge e) {
133 int val = (int) (((uintptr_t) e.node_ptr) >> VAR_SHIFT);
134 return isNegEdge(e) ? -val : val;
138 void deleteCNF(CNF *cnf);
139 void resetCNF(CNF *cnf);
141 uint hashNode(NodeType type, uint numEdges, Edge *edges);
142 Node *allocNode(NodeType type, uint numEdges, Edge *edges);
143 bool compareNodes(Node *node, NodeType type, uint numEdges, Edge *edges);
144 Edge create(CNF *cnf, NodeType type, uint numEdges, Edge *edges);
145 Edge constraintOR(CNF *cnf, uint numEdges, Edge *edges);
146 Edge constraintAND(CNF *cnf, uint numEdges, Edge *edges);
147 Edge constraintOR2(CNF *cnf, Edge left, Edge right);
148 Edge constraintAND2(CNF *cnf, Edge left, Edge right);
149 Edge constraintIMPLIES(CNF *cnf, Edge left, Edge right);
150 Edge constraintIFF(CNF *cnf, Edge left, Edge right);
151 static inline Edge constraintXOR(CNF *cnf, Edge left, Edge right) {return constraintNegate(constraintIFF(cnf, left,right));}
152 Edge constraintITE(CNF *cnf, Edge cond, Edge thenedge, Edge elseedge);
153 Edge constraintNewVar(CNF *cnf);
154 void countPass(CNF *cnf);
155 void countConstraint(CNF *cnf, VectorEdge *stack, Edge e);
156 void addConstraintCNF(CNF *cnf, Edge constraint);
157 int solveCNF(CNF *cnf);
158 bool getValueCNF(CNF *cnf, Edge var);
159 void printCNF(Edge e);
162 Edge generateBinaryConstraint(CNF *cnf, uint numvars, Edge *vars, uint value);
163 Edge generateLTValueConstraint(CNF *cnf, uint numvars, Edge *vars, uint value);
164 Edge generateEquivNVConstraint(CNF *cnf, uint numvars, Edge *var1, Edge *var2);
165 Edge generateLTConstraint(CNF *cnf, uint numvars, Edge *var1, Edge *var2);
166 Edge generateLTEConstraint(CNF *cnf, uint numvars, Edge *var1, Edge *var2);