this repo has no description
dekker.one
1/**** , [ bobocheTree.hh ],
2 Copyright (c) 2008 Universite d'Orleans - Jeremie Vautard
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 THE SOFTWARE.
21 *************************************************************************/
22
23#ifndef __BOBOCHE_TREE__
24#define __BOBOCHE_TREE__
25#include <vector>
26#include <iostream>
27#include <string>
28#include "StrategyNode.hh"
29#include "qecode.hh"
30
31using namespace std;
32class Strategy;
33
34class StrategyImp {
35 friend class Strategy;
36private:
37 unsigned int pointers; // number of Strategy objects pointing to this
38 StrategyNode zetag; // Node information
39 vector<Strategy> nodes; // children of this node
40 unsigned int todos; // number of todo nodes recursively present in the children
41 StrategyImp* father;
42 void todosUpdate(int i);
43 StrategyImp();
44
45public:
46 StrategyImp(StrategyNode tag);
47 ~StrategyImp();
48};
49
50/** \brief Strategy of a QCSP+ problem
51 *
52 * This class represents a solution of a QCSP+. Basically it consists in the tree-representation of the winning strategy.
53 * 3 spacial cases exists : the trivially true strategy, the trivially false strategy (used for the UNSAT answer),
54 * 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)
55 */
56class QECODE_VTABLE_EXPORT Strategy {
57 friend class StrategyImp;
58private:
59 StrategyImp* imp;
60 void todosUpdate(int i) {imp->todosUpdate(i);}
61 Strategy(StrategyImp* imp);
62public:
63 QECODE_EXPORT Strategy(); ///< default constructor
64 QECODE_EXPORT Strategy(StrategyNode tag); ///< builds a strategy on a given strategy node (deprecated)
65
66 /* \brief builds a one node (sub)strategy
67 *
68 * this method builds a one-node strategy that will typically be attached as child of another strategy. A strategy node embeds informations about quantification,
69 * scope and values of variables that must be provided
70 * @param qt quantifier of the scope this node represents
71 * @param VMin index of the first variable of the scope this node represents
72 * @param VMax index of the last variable of the scope this node represents
73 * @param values values taken by the variables between VMin and VMax in this part of the strategy
74 */
75 QECODE_EXPORT Strategy(bool qt,int VMin, int VMax, int scope,vector<int> values);
76 QECODE_EXPORT Strategy(const Strategy& tree); ///< copy constructor
77 QECODE_EXPORT Strategy& operator = (const Strategy& rvalue);
78 QECODE_EXPORT ~Strategy();
79 QECODE_EXPORT StrategyNode getTag();///< DEPRECATED returns the StrategyNode object corresponding to the root of this strategy
80 QECODE_EXPORT forceinline unsigned int degree() {return imp->nodes.size();}///< returns this strategy's number of children
81 QECODE_EXPORT Strategy getChild(int i); ///< returns the i-th child of this strategy
82 QECODE_EXPORT Strategy getFather();
83 QECODE_EXPORT bool hasFather();
84 QECODE_EXPORT Strategy getSubStrategy(vector<int> position); ///< returns the substrategy at given position, dummy if does not exists
85 QECODE_EXPORT void attach(Strategy child);///< attach the strategy given in parameter as a child of the current strategy
86 QECODE_EXPORT void detach(unsigned int i); ///< detach the i-th child of this strategy (provided it exists)
87 QECODE_EXPORT void detach(Strategy son);
88 QECODE_EXPORT forceinline bool isFalse() {return imp->zetag.isFalse();} ///< returns wether this strategy represents the UNSAT answer
89 QECODE_EXPORT forceinline bool isTrue() {return imp->zetag.isTrue();} ///< returns wether this strategy is trivially true
90 QECODE_EXPORT forceinline bool isComplete() {return ((imp->todos) == 0);} ///< returns wether this is a complete sub-strategy (without todo nodes)
91 QECODE_EXPORT forceinline bool isDummy() {return imp->zetag.isDummy();} ///< returns wether this strategy is a set of
92 QECODE_EXPORT forceinline bool isTodo() {return imp->zetag.isTodo();} ///< return wether this strategy is a "ToDo" marker or not
93
94 QECODE_EXPORT static Strategy STrue(); ///< returns the trivially true strategy
95 QECODE_EXPORT static Strategy SFalse(); ///< returns the trivially false strategy
96 QECODE_EXPORT static Strategy Dummy(); ///< returns a "dummy" node
97 QECODE_EXPORT static Strategy Stodo(); ///< returns a "todo" node
98 QECODE_EXPORT forceinline bool quantifier() {return imp->zetag.quantifier;} ///< returns the quantifier of the root (true for universal, false for existential)
99 QECODE_EXPORT forceinline int VMin() {return imp->zetag.Vmin;} ///< returns the index of the first variable of the scope of the root
100 QECODE_EXPORT forceinline int VMax() {return imp->zetag.Vmax;} ///< returns the index of the last variable of the scope of the root
101 QECODE_EXPORT forceinline int scope() {return imp->zetag.scope;} ///< returns the scope of the root
102 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
103 QECODE_EXPORT forceinline int value(int var) {return imp->zetag.valeurs[var];}
104 QECODE_EXPORT forceinline void* id() {return imp;} ///< Return an identifier for this strategy (this identifier is shared among multiples instances of this strategy)
105 QECODE_EXPORT vector<int> getPosition();
106 QECODE_EXPORT forceinline int nbTodos() {return imp->todos;}
107
108 QECODE_EXPORT int checkIntegrity();
109};
110
111
112#endif