1 #ifndef _SOL_STORE_QPCHEK
2 #define _SOL_STORE_QPCHEK
3 
4 #include "library/vec1.hpp"
5 #include "library/library.hpp"
6 #include "rbase/rbase.hpp"
7 #include "library/perm.hpp"
8 #include "partition_refinement.hpp"
9 
10 class SolutionStore
11 {
12     RBase* rb;
13     // List of solutions
14     vec1<Permutation> permutations;
15     // List which tells us that solution i was generated when trying to map .first to .second
16     // this is useful for building a stabilizer chain later.
17     vec1<std::pair<int, int> > permutations_from;
18 
19     vec1<int> orbit_mins;
20 
21     // This is here to allow different functions
22     // later.
comparison(int i,int j) const23     bool comparison(int i, int j) const
24     { return IndirectSorter([&](auto i) -> auto& { return (rb->inv_value_ordering)[i]; })(i, j); }
25 
26 public:
SolutionStore(RBase * _rb)27     SolutionStore(RBase* _rb) : rb(_rb), orbit_mins(rb->initial_permstack->domainSize(), -1)
28     { }
29 
isMinimum(int i) const30     bool isMinimum(int i) const
31     {
32         bool isMin = (orbit_mins[i] == -1);
33         if(isMin)
34         { debug_out(1, "SolutionStore", "NotMin: " << i); }
35         return orbit_mins[i] == -1;
36     }
37 
getMins() const38     vec1<int> getMins() const
39     {
40         vec1<int> minimums;
41         for(int i : range1(orbit_mins.size()))
42         {
43             if(isMinimum(i))
44                 minimums.push_back(i);
45         }
46         return minimums;
47     }
48 
walkToMinimum(int pos) const49     int walkToMinimum(int pos) const
50     {
51         while(orbit_mins[pos] != -1)
52         {
53             D_ASSERT(comparison(orbit_mins[pos], pos));
54             pos = orbit_mins[pos];
55         }
56         return pos;
57     }
58 
update_orbit_mins(int min_val,int pos)59     void update_orbit_mins(int min_val, int pos)
60     {
61         D_ASSERT(!comparison(pos, min_val));
62         if(min_val != pos)
63             orbit_mins[pos] = min_val;
64     }
65 
addSolution(const Permutation & sol)66     void addSolution(const Permutation& sol)
67     {
68         permutations.push_back(sol);
69         D_ASSERT(sol.size() == orbit_mins.size());
70         debug_out(3, "SS", "Old orbit_mins:" << orbit_mins);
71         for(int i : range1(sol.size()))
72         {
73             if(sol[i] != i)
74             {
75                 int val1 = walkToMinimum(i);
76                 int val2 = walkToMinimum(sol[i]);
77                 int orbit_min = -1;
78                 if(comparison(val1, val2))
79                     orbit_min = val1;
80                 else
81                     orbit_min = val2;
82 
83                 update_orbit_mins(orbit_min, val1);
84                 update_orbit_mins(orbit_min, val2);
85                 update_orbit_mins(orbit_min, i);
86                 update_orbit_mins(orbit_min, sol[i]);
87             }
88         }
89         debug_out(1, "SS", "Solution found");
90         debug_out(3, "SS", "Sol:" << sol);
91         debug_out(3, "SS", "New orbit_mins:" << orbit_mins);
92     }
93 
markLastSolutionFrom(int from,int to)94     void markLastSolutionFrom(int from, int to)
95     {
96         D_ASSERT(permutations.size() == permutations_from.size() + 1);
97         permutations_from.push_back(std::make_pair(from, to));
98     }
99 
sols() const100     const vec1<Permutation>& sols() const
101     { return permutations; }
102 
solsmap() const103     const vec1<std::pair<int,int> >& solsmap() const
104     { return permutations_from; }
105 
getRBase() const106     const RBase* getRBase() const
107     { return rb; }
108 
operator <<(std::ostream & os,const SolutionStore & ss)109     friend std::ostream& operator<<(std::ostream& os, const SolutionStore& ss)
110     { return os << ss.permutations; }
111 };
112 #endif
113