Last active
April 29, 2016 07:37
-
-
Save AtomKrieg/6fb6d3d8ae80842efb1d7d81d275017e to your computer and use it in GitHub Desktop.
Sort obj by M functions with cashes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <utility> | |
#include <vector> | |
#include <algorithm> | |
#include <unordered_map> | |
using key_type = unsigned; | |
struct SomeClass | |
{ | |
SomeClass(key_type _x1, key_type _x2, key_type _x3) | |
:x1(_x1), x2(_x2), x3(_x3) | |
{} | |
key_type x1, x2, x3; | |
void print() const | |
{ | |
std::cout << x1 << x2 << x3 << "\n"; | |
} | |
}; | |
template <size_t M> | |
key_type key(const SomeClass& val) {} | |
template<> | |
key_type key<1>(const SomeClass& val) {return val.x1;} | |
template<> | |
key_type key<2>(const SomeClass& val) {return val.x2;} | |
template<> | |
key_type key<3>(const SomeClass& val) {return val.x3;} | |
using SSPair = std::pair<size_t, size_t>; | |
struct PairHasher | |
{ | |
size_t operator()(const SSPair& p) const | |
{ | |
return (p.first * 0x1f1f1f1f) ^ p.second; | |
} | |
}; | |
struct KeyCasher | |
{ | |
size_t idx; | |
using PVector = std::vector<SomeClass> *; | |
static PVector data; | |
using HashMap = std::unordered_map<SSPair, key_type, PairHasher>; | |
static HashMap value; | |
template<size_t M> | |
key_type cashed_key() const | |
{ | |
std::pair<size_t, size_t> p {idx, M}; | |
if (value.find(p) == value.end()) | |
{ | |
key_type val = key<M>((*data)[idx]); | |
value[p] = val; | |
return val; | |
} | |
return value[p]; | |
} | |
void print() const | |
{ | |
(*data)[idx].print(); | |
} | |
}; | |
KeyCasher::PVector KeyCasher::data = nullptr; | |
KeyCasher::HashMap KeyCasher::value; | |
bool cmp(const KeyCasher& lft, const KeyCasher& rgt) | |
{ | |
key_type lkey, rkey; | |
lkey = lft.cashed_key<1>(); | |
rkey = rgt.cashed_key<1>(); | |
if (lkey != rkey) | |
return lkey < rkey; | |
lkey = lft.cashed_key<2>(); | |
rkey = rgt.cashed_key<2>(); | |
if (lkey != rkey) | |
return lkey < rkey; | |
lkey = lft.cashed_key<3>(); | |
rkey = rgt.cashed_key<3>(); | |
return lkey < rkey; | |
} | |
std::vector<SomeClass> input { | |
{1,1,1}, {1,1,2}, {1,1,3}, | |
{1,2,1}, {1,2,2}, {1,2,3}, | |
{1,3,1}, {1,3,2}, {1,3,3}, | |
{2,1,1}, {2,1,2}, {2,1,3}, | |
{2,2,1}, {2,2,2}, {2,2,3}, | |
{2,3,1}, {2,3,2}, {2,3,3}, | |
{3,1,1}, {3,1,2}, {3,1,3}, | |
{3,2,1}, {3,2,2}, {3,2,3}, | |
{3,3,1}, {3,3,2}, {3,3,3} | |
}; | |
int main() | |
{ | |
using namespace std; | |
random_shuffle(input.begin(), input.end()); | |
cout << "shuffled\n"; | |
for(const auto& val: input) | |
val.print(); | |
vector<KeyCasher> output(input.size()); | |
KeyCasher::data = &input; | |
for(int i=0; i < output.size(); ++i) | |
output[i].idx = i; | |
sort(output.begin(), output.end(), cmp); | |
cout << "\nsorted\n"; | |
for(const auto& val: output) | |
val.print(); | |
system("pause"); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment