-
Notifications
You must be signed in to change notification settings - Fork 10
/
sspm.hpp
130 lines (106 loc) · 3.09 KB
/
sspm.hpp
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
119
120
121
122
123
124
125
126
127
128
129
130
/*
* Copyright 2017-2018 Tom van Dijk, Johannes Kepler University Linz
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef SSPM_HPP
#define SSPM_HPP
#include "solver.hpp"
namespace pg {
class SSPMSolver : public Solver
{
public:
SSPMSolver(Oink *oink, Game *game);
virtual ~SSPMSolver();
virtual void run();
protected:
/**
* So the maximal length of bitstrings l := ceil(log2(n_vertices))
* And (for even measures) the depth h := # of even priorities
*
* So we could reasonably assume 0 <= l <= 32
*
* Two formats are possible to encode the array, apart from the bitstring
* - for each bit the depth: log n * log h
*/
int l, h;
bitset pm_b;
int *pm_d;
bitset tmp_b;
int *tmp_d;
bitset best_b;
int *best_d;
bitset test_b;
int *test_d;
uintqueue Q;
bitset dirty;
bitset unstable;
bool bounded = false;
int *cap; // caps!
uint64_t *lift_counters;
// Copy pm[idx] into tmp
void to_tmp(int idx);
// Copy tmp into pm[idx]
void from_tmp(int idx);
// Copy pm[idx] into best
void to_best(int idx);
// Copy best into pm[idx]
void from_best(int idx);
// Copy tmp into best
void tmp_to_best();
// Copy tmp into test
void tmp_to_test();
// Render pm[idx] to given ostream
void stream_pm(std::ostream &out, int idx);
// Render tmp to given ostream
void stream_tmp(std::ostream &out, int h);
// Render best to given ostream
void stream_best(std::ostream &out, int h);
// Compare tmp to best
int compare(int pindex);
// Compare tmp to test
int compare_test(int pindex);
// Bump tmp given priority p
void trunc_tmp(int pindex);
void prog_tmp(int pindex, int h);
void prog_cap_tmp(int pindex);
// Lift node, triggered by change to target
bool lift(int node, int target, int &str, int pl);
inline void todo_push(int node) {
if (dirty[node]) return;
Q.push(node);
dirty[node] = true;
#ifndef NDEBUG
if (trace >= 2) logger << "push(" << node << ")" << std::endl;
#endif
}
inline int todo_pop() {
int node = Q.pop();
dirty[node] = false;
#ifndef NDEBUG
if (trace >= 2) logger << "pop() => " << node << std::endl;
#endif
return node;
}
int lift_count = 0;
int lift_attempt = 0;
void run(int nbits, int depth, int player);
};
class BoundedSSPMSolver : public SSPMSolver
{
public:
BoundedSSPMSolver(Oink *oink, Game *game) : SSPMSolver(oink, game) { bounded = true; }
virtual ~BoundedSSPMSolver() { }
};
}
#endif