1 /*
2  * Copyright 2017-2018 Tom van Dijk, Johannes Kepler University Linz
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef QPT_HPP
18 #define QPT_HPP
19 
20 #include "solver.hpp"
21 #include "uintqueue.hpp"
22 
23 namespace pg {
24 
25 class QPTSolver : public Solver
26 {
27 public:
28     QPTSolver(Oink *oink, Game *game);
29     virtual ~QPTSolver();
30 
31     virtual void run();
32 
33 protected:
34     int *pm_nodes;
35     int *strategy;
36 
37     int pl;              // current measures of <pl> parity
38     int k;               // current measures: <k> components
39     int max, maxo;       // highest priority for current player / opponent
40     unsigned long goal;  // number of vertices of <pl> parity
41 
42     long lift_count;
43     long lift_attempt;
44 
45     uintqueue todo;
46     bitset dirty;
47 
48     bool bounded = false;
49 
50     bool lift(int v, int target);
51     void liftloop();
52     void updateState(unsigned long &_n0, unsigned long &_n1, int &_max0, int &_max1, int &_k0, int &_k1);
53 
todo_push(int node)54     void todo_push(int node) {
55         if (dirty[node]) return;
56         todo.push(node);
57         dirty[node] = 1;
58 #ifndef NDEBUG
59         if (trace >= 3) logger << "push(" << node << ")" << std::endl;
60 #endif
61     }
62 
todo_pop()63     int todo_pop() {
64         int node = todo.pop();
65         dirty[node] = 0;
66 #ifndef NDEBUG
67         if (trace >= 3) logger << "pop() => " << node << std::endl;
68 #endif
69         return node;
70     }
71 };
72 
73 class BoundedQPTSolver : public QPTSolver
74 {
75 public:
BoundedQPTSolver(Oink * oink,Game * game)76     BoundedQPTSolver(Oink *oink, Game *game) : QPTSolver(oink, game) { bounded = true; }
~BoundedQPTSolver()77     virtual ~BoundedQPTSolver() { }
78 };
79 
80 }
81 
82 #endif
83