Instantly share code, notes, and snippets.

Embed
What would you like to do?
C++11: Implementation of list comprehension in SQL-like form
// List comprehension in C++11 in form of SQL-like syntax
// Example code from http://vitiy.info/cpp11-writing-list-comprehension-in-form-of-sql/
// Written by Victor Laskin (victor.laskin@gmail.com)
#include <iostream>
#include <functional>
#include <vector>
#include <future>
#include <algorithm>
using namespace std;
// This is for converting lambda / pointer into correponding std::function<>
template <typename Fun>
struct fn_is_ptr: std::integral_constant<bool, std::is_pointer<Fun>::value
&& std::is_function< typename std::remove_pointer<Fun>::type>::value>
{};
template <typename ReturnType, typename... Args, class = typename std::enable_if<fn_is_ptr< ReturnType(*)(Args...) >::value>::type>
std::function<ReturnType(Args...)> to_fn (ReturnType (*fp)(Args...))
{
return std::function<ReturnType(Args...)>(fp);
}
template <typename Function>
struct function_traits : public function_traits<decltype(&Function::operator())>
{};
template <typename ClassType, typename ReturnType, typename... Args>
struct function_traits<ReturnType(ClassType::*)(Args...) const>
{
typedef ReturnType (*pointer)(Args...);
typedef std::function<ReturnType(Args...)> function;
};
template <typename Function, class = typename std::enable_if<!fn_is_ptr<Function>::value>::type>
typename function_traits<Function>::function to_fn(Function& lambda)
{
return typename function_traits<Function>::function(lambda);
}
template <typename Function, class = typename std::enable_if<!fn_is_ptr<Function>::value>::type>
typename function_traits<Function>::function to_fn(const Function& lambda)
{
return typename function_traits<Function>::function(lambda);
}
// Range of natural integers
class Naturals
{
int min;
int max;
public:
Naturals() : min(1),max(1000) {}
Naturals(int min, int max) : min(min),max(max) {}
int at(int i) const { return i + min; } ;
int size() const { return max - min + 1; } ;
class Iterator {
int position;
public:
Iterator(int _position):position(_position) {}
int& operator*() { return position; }
Iterator& operator++() { ++position; return *this; }
bool operator!=(const Iterator& it) const { return position != it.position; }
};
Iterator begin() const { return { min }; }
Iterator end() const { return { max }; }
};
// Additional options
class SelectOption {
private:
virtual bool imPolymorphic() { return true; }
};
class SelectOptionLimit : public SelectOption {
public:
int limit;
SelectOptionLimit(int limit) : limit(limit) {}
};
class SelectOptionSort : public SelectOption {};
class SelectOptionDistict : public SelectOption {};
class SelectContinuation : public SelectOption {
public:
vector<int> indexes;
SelectContinuation(){}
template <typename... Args>
SelectContinuation(Args... args) : indexes{ args... } { }
};
/// Main iterations
template <typename Src, typename... Args>
inline typename std::enable_if< std::is_object<decltype(std::declval<Src>().begin()) >::value, Src&&>::type
getSource(Src && src, Args&&... args) {
return std::forward<Src&&>(src);
}
template <typename F, typename... Args, typename FRes = decltype(std::declval<F>()(std::declval<Args>()...))>
inline typename std::enable_if<std::is_object< decltype(std::declval<F>()(std::declval<Args>()...)) >::value, FRes >::type
getSource(F && f, Args&&... args)
{
return std::forward<FRes>(f(std::forward<Args>(args)...));
}
template<std::size_t I = 0, typename FuncT, typename... Tp, typename... Args>
inline typename std::enable_if<I == sizeof...(Tp), bool>::type
for_each_in_sources(const std::tuple<Tp...> &, FuncT& f, Args&... args)
{
return f(args...);
}
template<std::size_t I = 0, typename FuncT, typename... Tp, typename... Args>
inline typename std::enable_if< I < sizeof...(Tp), bool>::type
for_each_in_sources(const std::tuple<Tp...>& t, FuncT& f, Args&... args)
{
bool isFinished;
auto&& src = getSource(std::get<I>(t), args...);
for(auto& element : src)
{
isFinished = for_each_in_sources<I + 1, FuncT, Tp...>(t, f, args..., element);
if (isFinished) break;
}
return isFinished;
}
template<std::size_t I = 0, typename FuncT, typename... Tp, typename... Args>
inline typename std::enable_if<I == sizeof...(Tp), bool>::type
for_each_in_sources_indexed(const std::tuple<Tp...> &, FuncT& f, vector<int>& indexes, Args&&... args)
{
return f(args...);
}
template<std::size_t I = 0, typename FuncT, typename... Tp, typename... Args>
inline typename std::enable_if< I < sizeof...(Tp), bool>::type
for_each_in_sources_indexed(const std::tuple<Tp...>& t, FuncT& f, vector<int>& indexes, Args&&... args)
{
bool isFinished;
auto&& src = getSource(std::get<I>(t), args...);
int size = src.size();
int i = indexes[I];
if (I != 0) if (i >= size) i = 0;
if (i >= size) return false;
for (; i < size; i++)
{
isFinished = for_each_in_sources_indexed<I + 1, FuncT, Tp...>(t, f, indexes, args..., src.at(i));
if (isFinished) break;
}
indexes[I] = ++i;
return isFinished;
}
template <typename R, typename... Args, typename... Sources, typename... Options>
vector<R> select(const std::function<R(Args...)>& f, ///< output expression
const std::tuple<Sources...>& sources, ///< list of sources
const std::function<bool(Args...)>& filter, ///< composition of filters
const Options&... options ///< other options and flags
)
{
int limit = -1;
bool isDistinct = false;
bool isSorted = false;
vector<int>* indexes = nullptr;
for_each_argument([&](const SelectOption& option){
if (auto opt = dynamic_cast<const SelectOptionLimit*>(&option)) { limit = opt->limit; };
if (dynamic_cast<const SelectOptionSort*>(&option)) { isSorted = true; };
if (dynamic_cast<const SelectOptionDistict*>(&option)) { isDistinct = true; };
if (auto opt = dynamic_cast<const SelectContinuation*>(&option)) { indexes = &( (const_cast<SelectContinuation*>(opt))->indexes ); };
}, (options)...);
vector<R> result;
int count = 0;
auto process = [&](const Args&... args){
if (filter(args...))
{
result.push_back(f(args...));
count++;
}
return (count == limit); // isFinished
};
if (indexes == nullptr)
for_each_in_sources(sources, process);
else
{
if (indexes->size() == 0)
{
indexes->resize(std::tuple_size<std::tuple<Sources...>>::value);
std::fill(indexes->begin(), indexes->end(), 0);
}
for_each_in_sources_indexed(sources, process, *indexes);
}
// sort results
if ((isDistinct) || (isSorted))
std::sort(result.begin(), result.end());
// remove duplicates
if (isDistinct)
{
auto last = std::unique(result.begin(), result.end());
result.erase(last, result.end());
}
return result;
}
template <typename R, typename... Args, typename... Sources, typename... Options>
inline vector<R> select(std::function<R(Args...)> f,
const std::tuple<Sources...>& sources,
const Options&... options)
{
return select(f, sources, to_fn([](Args... args){ return true; }), options...);
}
// EVIL WAY
#define SELECT(X) select(to_fn(X),
//#define FROM(...) std::forward_as_tuple(__VA_ARGS__)
#define FROM(...) std::make_tuple(__VA_ARGS__)
#define WHERE(...) ,to_fn(__VA_ARGS__)
#define SORT ,SelectOptionSort()
#define DISTINCT ,SelectOptionDistict()
#define LIMIT(X) ,SelectOptionLimit(X))
#define NOLIMIT LIMIT(-1)
template <typename R, typename... Args, typename... Sources, typename... Options>
std::function<vector<R>()> select_lazy(const std::function<R(Args...)>& f, ///< output expression
const std::tuple<Sources...>& sources, ///< list of sources
const std::function<bool(Args...)>& filter, ///< composition of filters
const Options&... options ///< other options and flags
)
{
return to_fn([=](){ return select(f, sources, filter, options...); });
}
template <typename R, typename... Args, typename... Sources, typename... Options>
std::function<vector<R>(const SelectContinuation& job)> select_concurrent(
const std::function<R(Args...)>& f, ///< output expression
const std::tuple<Sources...>& sources, ///< list of sources
const std::function<bool(Args...)>& filter, ///< composition of filters
const Options&... options ///< other options and flags
)
{
return to_fn([=](const SelectContinuation& job){ return select(f, sources, filter, job, options...); });
}
#define CONCURRENTSELECT(X) select_concurrent(to_fn(X),
#define LAZYSELECT(X) select_lazy(to_fn(X),
#define LAZY(X) ,(X)
/// Call function for each argument
template <class F, class... Args>
void for_each_argument(F f, Args&&... args) {
(void)(int[]){(f(forward<Args>(args)), 0)...};
}
int main() {
// EXAMPLES
auto print = [](vector<int>& list){ cout << "List: "; for (int x : list) cout << x << " "; cout << endl;};
cout << "10 naturals" << endl;
auto result = SELECT([](int x){ return x; }) FROM(Naturals()) LIMIT(10);
print(result);
cout << "Distinct test" << endl;
result = SELECT([](int x, int y){ return x+y; }) FROM(Naturals(), Naturals())
WHERE([](int x, int y){ return (x*x + y*y < 25); }) DISTINCT LIMIT(10);
print(result);
cout << "Intersection" << endl;
vector<int> ints = {11,2,1,5,6,7};
vector<int> ints2 = {3,4,5,7,8,11};
result = SELECT([](int x, int y){ return x; })
FROM(ints, ints2)
WHERE([](int x, int y){ return (x == y); }) SORT NOLIMIT;
print(result);
// Simple map operation as list comprehension
cout << "Map" << endl;
result = SELECT([](int x){ return x + 5; }) FROM(ints) NOLIMIT;
print(result);
cout << "Pythagorean Triplets" << endl;
SelectContinuation state;
auto lazypyth = LAZYSELECT([&](int x, int y, int z){ return make_tuple(z,y,x); })
FROM(Naturals(1,100000000),
[](int x){ return Naturals(1,x); },
[](int x,int y){ return Naturals(1,y); })
WHERE([&](int x, int y, int z){ return x*x == y*y + z*z; })
LAZY(state) LIMIT(5);
auto pyth = lazypyth();
cout << "Part1:" << endl;
for (auto line: pyth) cout << " -> " << get<0>(line) << " " << get<1>(line) << " " << get<2>(line) << endl;
pyth = lazypyth();
cout << "Part2:" << endl;
for (auto line: pyth) cout << " -> " << get<0>(line) << " " << get<1>(line) << " " << get<2>(line) << endl;
return 0;
}
@dgu123

This comment has been minimized.

dgu123 commented Feb 17, 2015

really good

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment