1 #ifndef ALGORITHMS_HPP_YPAQW
2 #define ALGORITHMS_HPP_YPAQW
3
4 #include "library/vec1.hpp"
5 #include "library.hpp"
6 #include "perm.hpp"
7 #include <algorithm>
8
9 // Some generally useful functions
10
11 template<typename Container>
contains_no_repeats(Container con)12 bool contains_no_repeats(Container con)
13 {
14 std::sort(con.begin(), con.end());
15 auto it = con.begin();
16 while(it != con.end())
17 {
18 auto it2 = it;
19 ++it2;
20 if(it2 != con.end() && *it == *it2)
21 return false;
22 ++it;
23 }
24 return true;
25 }
26
27 enum MissingPoints
28 { MissingPoints_Free, MissingPoints_Fixed };
29
partitionToList(const vec1<vec1<int>> & part,int size,MissingPoints mp)30 inline vec1<int> partitionToList(const vec1<vec1<int> >& part, int size, MissingPoints mp)
31 {
32 vec1<int> vec(size, 0);
33 int covered = 1;
34 for(int i : range1(part.size()))
35 {
36 for(int val : part[i])
37 {
38 D_ASSERT(vec[val] == 0);
39 vec[val] = i;
40 covered++;
41 }
42 }
43 // Maybe the permutation is missing some values of the end. These
44 // should all be treated as defined by 'MissingPoints'
45 if(mp == MissingPoints_Fixed)
46 {
47 for(int i : range1(vec.size()))
48 {
49 if(vec[i] == 0)
50 vec[i] = vec.size() + 1 + i; // (is +1 required? It doesn't hurt)
51 }
52 }
53 return vec;
54 }
55
56 template<MissingPoints mp>
57 class SparseFunction
58 {
59 std::map<int, int> const* m;
60 public:
61
SparseFunction(std::map<int,int> const * _m)62 SparseFunction(std::map<int, int> const* _m) : m(_m)
63 { }
64
SparseFunction(const SparseFunction & sf)65 SparseFunction(const SparseFunction& sf) : m(sf.m)
66 { }
67
operator ()(int i) const68 int operator()(int i) const
69 {
70 std::map<int, int>::const_iterator it = m->find(i);
71 if(it == m->end())
72 {
73 if(mp == MissingPoints_Free)
74 return 0;
75 else
76 abort();
77 }
78 else
79 return it->second;
80 }
81
operator <<(std::ostream & o,const SparseFunction & sf)82 friend std::ostream& operator<<(std::ostream& o, const SparseFunction& sf)
83 { return o << *(sf.m); }
84 };
85
86
partitionToMap(const vec1<vec1<int>> & part)87 inline std::map<int, int> partitionToMap(const vec1<vec1<int> >& part)
88 {
89 std::map<int, int> m;
90 int covered = 1;
91 for(int i : range1(part.size()))
92 {
93 for(int val : part[i])
94 {
95 D_ASSERT(m[val] == 0);
96 m[val] = i;
97 covered++;
98 }
99 }
100
101 return m;
102 }
103
104
invertVecAsPermutation(const vec1<int> & v)105 inline vec1<int> invertVecAsPermutation(const vec1<int>& v)
106 {
107 vec1<int> ret(v.size());
108 for(int i : range1(v.size()))
109 {
110 ret[v[i]] = i;
111 }
112 return ret;
113 }
114
115 #endif
116