1 /*
2  * Copyright 2020 Tom van Dijk
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 TL_HPP
18 #define TL_HPP
19 
20 #include "oink.hpp"
21 #include "solver.hpp"
22 
23 namespace pg {
24 
25 class TLSolver : public Solver
26 {
27 public:
28     TLSolver(Oink *oink, Game *game);
29     virtual ~TLSolver();
30 
31     virtual void run();
32 
33 protected:
34     int iterations = 0;
35     int dominions = 0;
36     int tangles = 0;
37     int steps = 0;
38 
39     std::vector<int*> tout; // for each tangle
40     std::vector<int> *tin; // for each normal vertex
41     std::vector<int*> tv; // the tangle (vertex-strategy pairs)
42     std::vector<int> tpr; // priority of a tangle
43     std::vector<unsigned int> tescs; // number of escapes of a tangle
44 
45     uintqueue Q; // main queue when attracting vertices
46 
47     int *str; // stores currently assigned strategy of each vertex
48     unsigned int *escs; // stores remaining escapes of each vertex
49 
50     uintqueue pea_state; // v,i,...
51     uintqueue pea_S;  // S
52     unsigned int* pea_vidx;    // rindex
53     bitset pea_root;  // root
54     int pea_curidx;   // index
55 
56     std::vector<int> tangle; // stores the new tangle
57     uintqueue tangleto; // stores the vertices the tangle can escape to
58     bitset escapes; // which escapes we considered
59 
60     bitset R; // remaining region (in tl)
61     bitset Z; // current region (in tl)
62     bitset G; // the unsolved game
63     bitset S; // solved vertices (in queue Q)
64     bitset V; // heads 1
65     bitset W; // heads 2
66 
67     bitset Even; // accumulate even regions
68     bitset Odd; // accumulate odd regions
69 
70     inline void attractVertices(const int pl, int v, bitset &R, bitset &Z);
71     bool attractTangle(const int t, const int pl, bitset &Z, int maxpr);
72     inline void attractTangles(const int pl, int v, bitset &Z, int maxpr);
73 
74     bool tl(void);
75     bool extractTangles(int i, bitset &R, int *str);
76 };
77 
78 }
79 
80 #endif
81