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