/*
 * Copyright (c) 2014, killerbee13
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 * * Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * * Redistributions in binary form must reproduce the above
 *   copyright notice, this list of conditions and the following disclaimer
 *   in the documentation and/or other materials provided with the
 *   distribution.
 * * Neither the name of the copyright holder nor the names of its
 *   contributors may be used to endorse or promote products derived from
 *   this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 */


#ifndef  SIMPLE_ALGORITHMS_H_INCLUDED
#define  SIMPLE_ALGORITHMS_H_INCLUDED

//Header containing frequently reused code that is not as easily done without helper functions

#include <cmath>
#include <complex>
#include <algorithm>
#include <numeric>
#include <istream>
#include <fstream>
#include <cctype>
#include <utility>
#include <limits>
#include <array>
#include <tuple>

#include <typeinfo>
#include <exception>
#include <stdexcept>


#if __has_cpp_attribute(fallthrough)
#define fallthrough fallthrough
#elif __has_cpp_attribute(clang::fallthrough)
#define fallthrough clang::fallthrough
#elif __has_cpp_attribute(gnu::fallthrough)
#define fallthrough gnu::fallthrough
#else
#define fallthrough fallthrough
#endif

#if __has_cpp_attribute(maybe_unused)
#define maybe_unused maybe_unused
#elif __has_cpp_attribute(gnu::unused)
#define maybe_unused gnu::unused
#else //Just let the compiler show the warning
#define maybe_unused maybe_unused
#endif

#if !FRC_NO_CONVERT
#include <sstream>
#include <string>
//This is the only one that should throw an exception
template <typename T>
inline T fromStr(const std::string& val) {
	std::stringstream ss(val);
	T ret;
	if (!(ss>>ret).fail())
		return ret;
	else throw std::runtime_error("\""+val+"\" is not a "+typeid(T).name());
}
template<> inline std::string fromStr(const std::string& val) {
	return val;
}

template <typename T>
inline T fromStr(const std::string& val, const char* type) {
	std::stringstream ss(val);
	T ret;
	if (!(ss>>ret).fail())
		return ret;
	else throw std::runtime_error("\""+val+"\" is not a "+type);
}
template<> inline std::string fromStr(const std::string& val, [[maybe_unused]] const char* type) {
	return val;
}
#define pFromStr(type, val) fromStr< type >( (val), #type )

template <typename T>
inline std::string toStr(T val) {
	std::stringstream ss;
	ss<<val;
	return ss.str();
}

#if !FRC_NO_TIME
#include <chrono>
using namespace std::string_literals;
template <int maxBufLen = 256, typename clock, typename duration>
inline std::string time_to_str(std::chrono::time_point<clock,duration>& tp, const std::string& fmt = "%F %T"s) {
	std::time_t time = clock::to_time_t(tp);
	std::tm* tmb = std::localtime(&time);
	std::string ret{maxBufLen, '\0'};
	std::strftime(&ret.front(), maxBufLen, fmt.c_str(), tmb);
	return ret;
}
#endif

#endif

#if !FRC_NO_ICU
#include <unicode/unistr.h>
//For elegance
template <typename string=std::string>
inline string toUTF8(const icu::UnicodeString& s)
{
	string res;
	return s.toUTF8String(res);
}
//For consistency
template <typename string>
inline icu::UnicodeString fromUTF8(string s)
{
	return icu::UnicodeString::fromUTF8(s);
}
//For elegance
template <typename string=std::u32string>
inline string toUTF32(const icu::UnicodeString& s)
{
	string res(s.countChar32(), '\0');
	UErrorCode ec{U_ZERO_ERROR};
	s.toUTF32(reinterpret_cast<UChar32*>(&res[0]), res.size(), ec);
	if (U_FAILURE(ec)) {
		throw ec;
	}
	return res;
}
//For consistency
template <typename string>
inline icu::UnicodeString fromUTF32(string s)
{
	return icu::UnicodeString::fromUTF32(s.data(), s.length());
}

inline std::ostream& operator<<(std::ostream& os, const icu::UnicodeString& str)
{
	return os<<toUTF8(str);
}

//ICU basically provides a + so I might as well translate it
inline std::string operator+(std::string lhs, const icu::UnicodeString& str)
{
	return str.toUTF8String(lhs);
}

#if !FRC_NO_CONVERT

//For debugging
std::string d_toUTF8(const icu::UnicodeString& s);
icu::UnicodeString d_fromUTF8(std::string s);

template <typename T>
inline T fromStr(const icu::UnicodeString& val, const char* type) {
	return fromStr<T>(toUTF8(val), type);
}

template <typename T>
inline T fromStr(const icu::UnicodeString& val) {
	return fromStr<T>(toUTF8(val));
}
#endif
#endif

template <typename string, typename vector>
inline string join(const vector& in, const string& joiner={}) {
	if (in.size() == 0) {
		return {};
	} else if (in.size() == 1) {
		return *in.begin();
	} else {
		return std::accumulate(
			std::next(std::begin(in)), std::end(in),
			*in.begin(),
			[&joiner](const string& a, const string& b) -> string
			{return a+joiner+b;}
		);
	}
}

template<typename string>
inline string reverseStr(string val) {
	std::reverse(val.begin(), val.end());
	return val;
}

template<typename string>
inline string toLower(string str) {
	std::transform(str.begin(), str.end(), str.begin(), ::tolower);
	return str;
}

template<typename string>
inline string toUpper(string str) {
	std::transform(str.begin(), str.end(), str.begin(), ::toupper);
	return str;
}

#include <vector>
#include <string>
#include <sstream>
template <typename T>
inline std::vector<T> listToVec(std::string list)
{
	std::vector<T> ret;
	std::stringstream ss(list);
	std::string tmp;
	while(!(ss>>tmp).fail()) {
		ret.push_back(fromStr<T>(tmp));
	}
	/*
	while(list.find_first_of(" ,") != std::string::npos) {
	 std::string entry = list.substr(0, list.find_first_of(" ,"));
	 ret.push_back(fromStr<T>(entry));
	 list = list.substr(entry.size());
	 if (list.find_first_of(" ,") == std::string::npos) {
		entry = list.substr(0, list.find_first_of(" ,"));
		ret.push_back(fromStr<T>(entry));
		list = list.substr(entry.size());
	 }
	}*/
	return ret;
}

template<typename string>
inline string repeat(string val, int count) {
	string tmp;
	for (int i = 0; i < count; ++i) {
	 tmp += val;
	}
	return tmp;
}

inline std::string repeat(char val, int count) {
	return std::string(count, val);
}

#if !FRC_NO_BUILD
#include <iterator>
#include <algorithm>
#include <type_traits>
template<typename Array, typename InputIt,
		typename UnaryFunction,
		typename std::enable_if<std::is_convertible<typename std::tuple_size<Array>::value_type, size_t>::value, int>::type = 0>
inline Array build(InputIt first, InputIt last, UnaryFunction f) {
	Array out;
	std::transform(first, last, out.begin(), f);
	return out;
}
// template<typename Array, typename ExecutionPolicy,
		// typename InputIt, typename UnaryFunction,
		// typename std::enable_if<std::is_convertible<typename std::tuple_size<Array>::value_type, size_t>::value, int>::type = 0>
// inline Array build(ExecutionPolicy&& policy, InputIt first,
		// InputIt last, UnaryFunction f) {
	// Array out;
	// std::transform(policy, first, last, out.begin(), f);
	// return out;
// }
template<typename Array, typename InputIt, typename InputIt2,
		typename BinaryFunction,
		typename std::enable_if<std::is_convertible<typename std::tuple_size<Array>::value_type, size_t>::value, int>::type = 0>
inline Array build(InputIt first, InputIt last,
		InputIt2 first2, BinaryFunction f) {
	Array out;
	std::transform(first, last, first2, out.begin(), f);
	return out;
}
// template<typename Array, typename ExecutionPolicy,
		// typename InputIt, typename InputIt2, typename BinaryFunction,
		// typename std::enable_if<std::is_convertible<typename std::tuple_size<Array>::value_type, size_t>::value, int>::type = 0>
// inline Array build(ExecutionPolicy&& policy, InputIt first,
		// InputIt last, InputIt2 first2, BinaryFunction f) {
	// Array out;
	// std::transform(policy, first, last, first2, out.begin(), f);
	// return out;
// }

template<typename Container, typename InputIt,
		typename UnaryFunction>
inline Container build(InputIt first, InputIt last, UnaryFunction f,
		[[maybe_unused]] typename Container::allocator_type = {}) {
	Container out;
	std::transform(first, last, std::back_inserter(out), f);
	return static_cast<void>(out.resize(out.size())), out;
}
// template<typename Container, typename ExecutionPolicy,
		// typename InputIt, typename UnaryFunction>
// inline Container build(ExecutionPolicy&& policy, InputIt first,
		// InputIt last, UnaryFunction f,
		// [[maybe_unused]] typename Container::allocator_type = {}) {
	// Container out;
	// std::transform(policy, first, last, std::back_inserter(out), f);
	// return static_cast<void>(out.resize(out.size())), out;
// }
template<typename Container, typename InputIt, typename InputIt2,
		typename BinaryFunction>
inline Container build(InputIt first, InputIt last,
		InputIt2 first2, BinaryFunction f,
		[[maybe_unused]] typename Container::allocator_type = {}) {
	Container out;
	std::transform(first, last, first2, std::back_inserter(out), f);
	return out;
}
// template<typename Container, typename ExecutionPolicy,
		// typename InputIt, typename InputIt2, typename BinaryFunction>
// inline Container build(ExecutionPolicy&& policy, InputIt first,
		// InputIt last, InputIt2 first2, BinaryFunction f,
		// [[maybe_unused]] typename Container::allocator_type = {}) {
	// Container out;
	// std::transform(policy, first, last, first2,
		// std::back_inserter(out), f);
	// return out;
// }

template<typename Array, typename Functor,
		typename std::enable_if<std::is_convertible<typename std::tuple_size<Array>::value_type, size_t>::value, int>::type = 0>
inline Array build(Functor f, size_t size = std::tuple_size<Array>::value) {
	Array out;
	std::generate_n(out.begin(), size, f);
	return out;
}
// template<typename Array, typename ExecutionPolicy,
		// typename Functor,
		// typename std::enable_if<std::is_convertible<typename std::tuple_size<Array>::value_type, size_t>::value, int>::type = 0>
// inline Array build(ExecutionPolicy&& policy, Functor f, size_t size = std::tuple_size<Array>::value) {
	// Array out;
	// std::generate_n(policy, out.begin(), size, f);
	// return out;
// }

template<typename Container, typename Functor>
inline Container build(Functor f, size_t size,
		[[maybe_unused]] typename Container::allocator_type = {}) {
	Container out(size);
	std::generate_n(out.begin(), size, f);
	return out;
}
// template<typename Container, typename ExecutionPolicy,
		// typename Functor>
// inline Container build(ExecutionPolicy&& policy, Functor f, size_t size,
		// [[maybe_unused]] typename Container::allocator_type = {}) {
	// Container out(size);
	// std::generate_n(policy, out.begin(), size, f);
	// return out;
// }

#include <numeric>
template<typename Container, typename T, typename I=T>
inline Container buildiota(size_t count, T value, I incr = 1) {
	Container out;
	while (count-->0) {
		out.push_back(value);
		value+=incr;
	}
	return out;
}
template<typename Array, typename T, typename I,
		typename std::enable_if<std::is_convertible<typename std::tuple_size<Array>::value_type, size_t>::value, int>::type = 0>
constexpr inline Array buildiota(T value, I incr = 1) {
	auto f = [&]{
		auto ovalue = value;
		value+=incr;
		return ovalue;
	};
	Array out;
	std::generate(out.begin(), out.end(), f);
	return out;
}

template<typename Container, typename T>
size_t find_in(const Container& c, const T& v) {
	return std::find(std::begin(c), std::end(c), v) - std::begin(c);
}
// template<typename ExecutionPolicy, typename Container, typename T>
// size_t find_in(ExecutionPolicy&& policy, const Container& c, const T& v) {
	// return std::find(policy, std::begin(c), std::end(c), v) - std::begin(c);
// }
template<typename Container, typename UnaryPredicate>
size_t find_in_if(const Container& c, UnaryPredicate p) {
	return std::find_if(std::begin(c), std::end(c), p) - std::begin(c);
}
// template<typename ExecutionPolicy, typename Container, typename UnaryPredicate>
// size_t find_in_if(ExecutionPolicy&& policy, const Container& c, UnaryPredicate p) {
	// return std::find_if(policy, std::begin(c), std::end(c), p) - std::begin(c);
// }
template<typename Container, typename UnaryPredicate>
size_t find_in_if_not(const Container& c, UnaryPredicate p) {
	return std::find_if_not(std::begin(c), std::end(c), p) - std::begin(c);
}
// template<typename ExecutionPolicy, typename Container, typename UnaryPredicate>
// size_t find_in_if_not(ExecutionPolicy&& policy, const Container& c, UnaryPredicate p) {
	// return std::find_if_not(policy, std::begin(c), std::end(c), p) - std::begin(c);
// }

#include <random>
template <typename Container, typename R>
inline Container buildsample(const Container& pop, size_t count, R& r)
{
	std::uniform_real_distribution<double> d(0,1);
	Container samples;
	if (count >= pop.size()) {
		samples = pop;
	} else {
		for (size_t t = 0; samples.size() < count; ++t) {
			if ((pop.size()-t)*d(r) < (count-samples.size())) {
				samples.push_back(pop[t]);
			}
		}
	}
	return samples;
}

#endif

///@TODO: refactor
template <typename Array, typename RandomGenerator>
inline int chooseCategorical(Array cats, RandomGenerator& r)
{
	std::uniform_real_distribution<double> uniform(0.0, std::accumulate(cats.begin(), cats.end(), 0.0));
	double choose = uniform(r);
	for (int stop = 0; stop != cats.size(); ++stop) {
		choose -= cats[stop];
		if (choose <= 0) {
			return stop;
		}
	}
#if __has_builtin(__builtin_unreachable)
	__builtin_unreachable();
#else
	return cats.size()-1;
#endif
}

template<typename Number>
constexpr inline int digitsOf(Number val)
{
	return std::ceil(std::log10(val));
}

template<typename Number>
constexpr inline int digitsOf(Number val, int base)
{
	return std::ceil(std::log(val)/std::log(base));
}

template<typename ForwardIterator>
inline int digitsList(ForwardIterator first, ForwardIterator last)
{
	return digitsOf(*std::max_element(first, last));
}

template<typename ForwardIterator>
inline int digitsList(ForwardIterator first, ForwardIterator last, int base)
{
	return digitsOf(*std::max_element(first, last), base);
}

#include <iomanip>
//Not working
template<typename ostream_type, typename ForwardIterator>
inline ostream_type& padList(ostream_type& os, ForwardIterator first, ForwardIterator last, char fill=' ', int base=10)
{
//os<<std::setw(std::ceil(std::log(*std::max_element(first, last))/std::log(base)))<<std::setfill(fill);

	//save state of os
	char fills = os.fill(); std::streamsize widths = os.width();

	os<<std::setw(digitsList(first, last, base))<<std::setfill(fill);

	for (ForwardIterator it = first; it != last; ++it) {
		os<<' '<<*it;
	}
	//restore state of os
	os<<std::setw(widths)<<std::setfill(fills);
	return os;
}

//Consume all non-spaces to first break, then eat that, too
inline std::istream& eatWord(std::istream& is)
{
	do {is.get();} while (!isspace(is.peek()));
	return is;
}

//Eat spaces, don't eat an extra
inline std::istream& eatSpace(std::istream& is)
{
	while (isspace(is.peek())) is.get();
	return is;
}

inline std::string url_encode(const std::string &value) {
	std::ostringstream escaped;
	escaped.fill('0');
	escaped << std::hex;

	for (std::string::const_iterator i = value.begin(), n = value.end(); i != n; ++i) {
		std::string::value_type c = (*i);

		// Keep alphanumeric and other accepted characters intact
		if (isalnum(c) || c == '-' || c == '_' || c == '.' || c == '~') {
			escaped << c;
			continue;
		}

		// Any other characters are percent-encoded
		escaped << std::uppercase;
		escaped << '%' << std::setw(2) << int((unsigned char) c);
		escaped << std::nouppercase;
	}

	return escaped.str();
}

template<typename string>
inline std::string get_file_contents(string filename)
{
	std::ifstream in{filename, std::ios::in | std::ios::binary};
	in.exceptions(std::ios::badbit);
	std::string contents;
	std::array<char,128> buf;
	while (in) {
		in.read(buf.begin(), buf.size());
		contents.append(buf.begin(), in.gcount());
	}
	return contents;
}

template<typename T, typename F>
inline constexpr T quantizeRange(F min, F delta, F val)
{
	return static_cast<T>((val-min)*std::numeric_limits<T>::max()*delta);
}

//Memnonic aids

template <typename T>
using Ptr = T*;

template <typename T>
using PtrToConst = T const*;

template <typename T>
using ConstPtr = T* const;

template <typename T>
using ConstPtrToConst = T const* const;

#endif //SIMPLE_ALGORITHMS_H_INCLUDED