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 SSPM_HPP
18 #define SSPM_HPP
19 
20 #include "oink.hpp"
21 #include "solver.hpp"
22 #include "uintqueue.hpp"
23 
24 namespace pg {
25 
26 class SSPMSolver : public Solver
27 {
28 public:
29     SSPMSolver(Oink *oink, Game *game);
30     virtual ~SSPMSolver();
31 
32     virtual void run();
33 
34 protected:
35     /**
36      * So the maximal length of bitstrings l := ceil(log2(n_vertices))
37      * And (for even measures) the depth h := # of even priorities
38      *
39      * So we could reasonably assume 0 <= l <= 32
40      *
41      * Two formats are possible to encode the array, apart from the bitstring
42      * - for each bit the depth: log n * log h
43      */
44     int l, h;
45     bitset pm_b;
46     int *pm_d;
47 
48     bitset tmp_b;
49     int *tmp_d;
50 
51     bitset best_b;
52     int *best_d;
53 
54     bitset test_b;
55     int *test_d;
56 
57     uintqueue Q;
58     bitset dirty;
59     bitset unstable;
60 
61     bool bounded = false;
62 
63     int *cap; // caps!
64     uint64_t *lift_counters;
65 
66     // Copy pm[idx] into tmp
67     void to_tmp(int idx);
68     // Copy tmp into pm[idx]
69     void from_tmp(int idx);
70     // Copy pm[idx] into best
71     void to_best(int idx);
72     // Copy best into pm[idx]
73     void from_best(int idx);
74     // Copy tmp into best
75     void tmp_to_best();
76     // Copy tmp into test
77     void tmp_to_test();
78 
79     // Render pm[idx] to given ostream
80     void stream_pm(std::ostream &out, int idx);
81     // Render tmp to given ostream
82     void stream_tmp(std::ostream &out, int h);
83     // Render best to given ostream
84     void stream_best(std::ostream &out, int h);
85 
86     // Compare tmp to best
87     int compare(int pindex);
88     // Compare tmp to test
89     int compare_test(int pindex);
90 
91     // Bump tmp given priority p
92     void trunc_tmp(int pindex);
93     void prog_tmp(int pindex, int h);
94     void prog_cap_tmp(int pindex);
95 
96     // Lift node, triggered by change to target
97     bool lift(int node, int target, int &str, int pl);
98 
todo_push(int node)99     inline void todo_push(int node) {
100         if (dirty[node]) return;
101         Q.push(node);
102         dirty[node] = true;
103 #ifndef NDEBUG
104         if (trace >= 2) logger << "push(" << node << ")" << std::endl;
105 #endif
106     }
107 
todo_pop()108     inline int todo_pop() {
109         int node = Q.pop();
110         dirty[node] = false;
111 #ifndef NDEBUG
112         if (trace >= 2) logger << "pop() => " << node << std::endl;
113 #endif
114         return node;
115     }
116 
117     int lift_count = 0;
118     int lift_attempt = 0;
119 
120     void run(int nbits, int depth, int player);
121 };
122 
123 class BoundedSSPMSolver : public SSPMSolver
124 {
125 public:
BoundedSSPMSolver(Oink * oink,Game * game)126     BoundedSSPMSolver(Oink *oink, Game *game) : SSPMSolver(oink, game) { bounded = true; }
~BoundedSSPMSolver()127     virtual ~BoundedSSPMSolver() { }
128 };
129 
130 }
131 
132 #endif
133