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 SPM_HPP 18 #define SPM_HPP 19 20 #include <queue> 21 22 #include "oink.hpp" 23 #include "solver.hpp" 24 25 namespace pg { 26 27 class SPMSolver : public Solver 28 { 29 public: 30 SPMSolver(Oink *oink, Game *game); 31 virtual ~SPMSolver(); 32 33 virtual void run(); 34 35 int64_t lift_attempt = 0; 36 int64_t lift_count = 0; 37 38 protected: 39 int *pms; 40 int *tmp, *best; 41 int *strategy; 42 int *counts; 43 int64_t k; 44 45 std::deque<int> todo; 46 int *dirty; 47 int *unstable; 48 49 bool canlift(int node, int pl); 50 bool lift(int node, int target); 51 bool pm_less(int *a, int *b, int d, int pl); 52 void pm_copy(int *dst, int *src, int pl); 53 int pm_cycles(int *a, int pl); 54 void pm_stream(std::ostream &out, int *pm); 55 void Prog(int *dst, int *src, int d, int pl); 56 void update(int pl); 57 todo_push(int node)58 void todo_push(int node) { 59 if (dirty[node]) return; 60 todo.push_back(node); 61 dirty[node] = 1; 62 #ifndef NDEBUG 63 if (trace >= 2) logger << "push(" << node << ")" << std::endl; 64 #endif 65 } 66 todo_pop()67 int todo_pop() { 68 int node = todo.front(); 69 todo.pop_front(); 70 dirty[node] = 0; 71 if (trace >= 2) logger << "pop() => " << node << std::endl; 72 return node; 73 } 74 }; 75 76 } 77 78 #endif 79