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
|
/**** , [ bobocheTree.hh ],
Copyright (c) 2008 Universite d'Orleans - Jeremie Vautard
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*************************************************************************/
#ifndef __BOBOCHE_TREE__
#define __BOBOCHE_TREE__
#include <vector>
#include <iostream>
#include <string>
#include "StrategyNode.hh"
#include "qecode.hh"
using namespace std;
class Strategy;
class StrategyImp {
friend class Strategy;
private:
unsigned int pointers; // number of Strategy objects pointing to this
StrategyNode zetag; // Node information
vector<Strategy> nodes; // children of this node
unsigned int todos; // number of todo nodes recursively present in the children
StrategyImp* father;
void todosUpdate(int i);
StrategyImp();
public:
StrategyImp(StrategyNode tag);
~StrategyImp();
};
/** \brief Strategy of a QCSP+ problem
*
* This class represents a solution of a QCSP+. Basically it consists in the tree-representation of the winning strategy.
* 3 spacial cases exists : the trivially true strategy, the trivially false strategy (used for the UNSAT answer),
* and the "Dummy" node, used to link together each tree of a strategy which first player is universal (such a strategy is not a tree but a forest)
*/
class QECODE_VTABLE_EXPORT Strategy {
friend class StrategyImp;
private:
StrategyImp* imp;
void todosUpdate(int i) {imp->todosUpdate(i);}
Strategy(StrategyImp* imp);
public:
QECODE_EXPORT Strategy(); ///< default constructor
QECODE_EXPORT Strategy(StrategyNode tag); ///< builds a strategy on a given strategy node (deprecated)
/* \brief builds a one node (sub)strategy
*
* this method builds a one-node strategy that will typically be attached as child of another strategy. A strategy node embeds informations about quantification,
* scope and values of variables that must be provided
* @param qt quantifier of the scope this node represents
* @param VMin index of the first variable of the scope this node represents
* @param VMax index of the last variable of the scope this node represents
* @param values values taken by the variables between VMin and VMax in this part of the strategy
*/
QECODE_EXPORT Strategy(bool qt,int VMin, int VMax, int scope,vector<int> values);
QECODE_EXPORT Strategy(const Strategy& tree); ///< copy constructor
QECODE_EXPORT Strategy& operator = (const Strategy& rvalue);
QECODE_EXPORT ~Strategy();
QECODE_EXPORT StrategyNode getTag();///< DEPRECATED returns the StrategyNode object corresponding to the root of this strategy
QECODE_EXPORT forceinline unsigned int degree() {return imp->nodes.size();}///< returns this strategy's number of children
QECODE_EXPORT Strategy getChild(int i); ///< returns the i-th child of this strategy
QECODE_EXPORT Strategy getFather();
QECODE_EXPORT bool hasFather();
QECODE_EXPORT Strategy getSubStrategy(vector<int> position); ///< returns the substrategy at given position, dummy if does not exists
QECODE_EXPORT void attach(Strategy child);///< attach the strategy given in parameter as a child of the current strategy
QECODE_EXPORT void detach(unsigned int i); ///< detach the i-th child of this strategy (provided it exists)
QECODE_EXPORT void detach(Strategy son);
QECODE_EXPORT forceinline bool isFalse() {return imp->zetag.isFalse();} ///< returns wether this strategy represents the UNSAT answer
QECODE_EXPORT forceinline bool isTrue() {return imp->zetag.isTrue();} ///< returns wether this strategy is trivially true
QECODE_EXPORT forceinline bool isComplete() {return ((imp->todos) == 0);} ///< returns wether this is a complete sub-strategy (without todo nodes)
QECODE_EXPORT forceinline bool isDummy() {return imp->zetag.isDummy();} ///< returns wether this strategy is a set of
QECODE_EXPORT forceinline bool isTodo() {return imp->zetag.isTodo();} ///< return wether this strategy is a "ToDo" marker or not
QECODE_EXPORT static Strategy STrue(); ///< returns the trivially true strategy
QECODE_EXPORT static Strategy SFalse(); ///< returns the trivially false strategy
QECODE_EXPORT static Strategy Dummy(); ///< returns a "dummy" node
QECODE_EXPORT static Strategy Stodo(); ///< returns a "todo" node
QECODE_EXPORT forceinline bool quantifier() {return imp->zetag.quantifier;} ///< returns the quantifier of the root (true for universal, false for existential)
QECODE_EXPORT forceinline int VMin() {return imp->zetag.Vmin;} ///< returns the index of the first variable of the scope of the root
QECODE_EXPORT forceinline int VMax() {return imp->zetag.Vmax;} ///< returns the index of the last variable of the scope of the root
QECODE_EXPORT forceinline int scope() {return imp->zetag.scope;} ///< returns the scope of the root
QECODE_EXPORT forceinline vector<int> values() {return imp->zetag.valeurs;} ///< returns the values taken by the variables of the scope of the root in this (sub)strategy
QECODE_EXPORT forceinline int value(int var) {return imp->zetag.valeurs[var];}
QECODE_EXPORT forceinline void* id() {return imp;} ///< Return an identifier for this strategy (this identifier is shared among multiples instances of this strategy)
QECODE_EXPORT vector<int> getPosition();
QECODE_EXPORT forceinline int nbTodos() {return imp->todos;}
QECODE_EXPORT int checkIntegrity();
};
#endif
|
