LukasKalbertodt/meta.cpp

## meta.cpp
/**
 * --- Template Meta Program to solve the Partial Knapsack Problem  ---
 *
 * This little piece of code solves the partial knapsack problem at compile
 * time. This is not useful in any way. I just wanted to discover the
 * possibilities of template meta programming.
 * Note that this code is absolutly awful. First of all: It's a "pure" template
 * meta program, which is ugly on it's own. Furthermore my code is ugly in
 * particular. The motivation to clean up super-ugly code to get a little bit
 * less ugly code is... not that high.
 *
 * \author Lukas Kalbertodt <lukas.kalbertodt@gmail.com>
 */
#include <array>        // Just for output
#include <cstdint>
#include <iostream>     // Just for output
#include <ratio>        // representation of rational numbers
#include <tuple>        // Just for output
#include <type_traits>  // useful type traits


// ############################################################################
// Basic Helper Stuff
// ############################################################################

// compile time struct to hold an ID, a Cost and a Weight
template <int ID, int C, int W> struct Item {
  static constexpr int cost = C;
  static constexpr int weight = W;
};

// is used to store a list of items
template <typename... Is> struct ItemList {};

// helper struct to concatenate lists (empty base declaration)
template <typename, typename> struct Concat;

// specialization for two item lists
template <typename... IAs, typename... IBs>
struct Concat<ItemList<IAs...>, ItemList<IBs...>> {
  using type = ItemList<IAs..., IBs...>;
};

// ------------------- RemoveElement -------------------------------------------
// helper struct to remove one element Needle of a list Os
// (empty base declaration)
template <typename Needle, typename... Os> struct RemoveElement;

// specialization for empty list -> result is empty list
template <typename Needle> struct RemoveElement<Needle> {
  using type = ItemList<>;
};

// specialization for a list in which the first element differs from the Needle
// -> result is Concat<Head, RemoveElement<Needle, Tail>
template <typename Needle, typename Head, typename... Tail>
struct RemoveElement<Needle, Head, Tail...> {
  using type
    = typename Concat<ItemList<Head>,
                      typename RemoveElement<Needle,
                                            Tail...>::type>::type;
};

// specialization for a list in which the first element equals the Needle
// -> result is RemoveElement<Needle, Tail>
template <typename Needle, typename... Tail>
struct RemoveElement<Needle, Needle, Tail...> {
  using type = typename RemoveElement<Needle,
                                      Tail...>::type;
};


// ############################################################################
// Sorting
// ############################################################################

// ------------------- MaxItemBelow -------------------------------------------
// returns the item with the maximal Cost/Weight ratio that is less than the
// std::ratio given as first parameter (Cut).
// Note: I don't actually use the "Below"-Feature of this anymore. This whole
// program should still run without that, but I'm to lazy to remove it ;)
template <typename Cut, typename... Ts> struct MaxItemBelow;

// specialization for just one item -> maximum is this item of course
template <std::intmax_t Num, std::intmax_t Den, typename I>
struct MaxItemBelow<std::ratio<Num, Den>, I> {
  using max = I;
};

// specialization for a list with at least two items ->
// It removes one element (from those two) and "calls" itself in a recursive way
// with a list which size is decreased by one. To decide which item is dropped
// it evaluates this expression:
// valid(i0) && (i0 > i1 || !valid(i1)) , where
// valid() checks if the value of the item is below the Cut.
// In other words: With each recursive "call" it removes one elment from the
// list that is not the maximum below the Cut, until just one item is left
template <std::intmax_t Num, std::intmax_t Den,
          int ID0, int C0, int W0,
          int ID1, int C1, int W1,
          int... IDs, int... Cs, int... Ws>
struct MaxItemBelow<std::ratio<Num, Den>,
                    Item<ID0, C0, W0>,
                    Item<ID1, C1, W1>,
                    Item<IDs, Cs, Ws>...>
  : MaxItemBelow<std::ratio<Num, Den>,
                 typename std::
                   conditional<std::ratio_less<std::ratio<C0, W0>,
                                               std::ratio<Num, Den>>::value && (
                                   std::ratio_greater<std::ratio<C0, W0>,
                                                      std::ratio<C1, W1>>::value
                                   || !std::ratio_less<std::ratio<C1, W1>,
                                                       std::ratio<Num,
                                                                  Den>>::value),
                               Item<ID0, C0, W0>,
                               Item<ID1, C1, W1>>::type,
                 Item<IDs, Cs, Ws>...> {};


// ------------------- SortHelper  --------------------------------------------
// sorts all items in the given list whose value is below Max
template <typename Max, typename List> struct SortHelper;

// specialization for one item in the list -> the list is already sorted
template <typename Max, typename I>
struct SortHelper<Max, ItemList<I>> {
  using type = ItemList<I>;
};

// specialization for a list containing more than one item ->
// max is the maximal item below Max
// newlist is the given list without 'max'
// type is a list of items containing all items in the input list with 'max'
// at the beginning
template <typename Max, typename I0, typename... Is>
struct SortHelper<Max, ItemList<I0, Is...>> {
private:
  using max = typename MaxItemBelow<Max, I0, Is...>::max;
  using newlist = typename RemoveElement<max, I0, Is...>::type;

public:
  using type
    = typename Concat<ItemList<max>,
                      typename SortHelper<std::ratio<max::cost, max::weight>,
                                          newlist>::type>::type;
};


// ------------------- PackHelper  --------------------------------------------
// Gets a sorted list of items and creates a list of
// {ItemID, num, den} where num/den is how much of the ItemID is used in the
// result. WL = weight left
template <int WL, bool OverZero, typename... Is>
struct PackHelper;

// specialization for a list with at least one element and a knapsack with
// space left ->
// We calculate how much of that item fits into the knapsack: If the item weight
// is less than the available weight in the knapsack, we can fit everything of
// the item (1). Else we fit as much as we can, which is
// (left_available_weight/item_weight).
// After calculating the share of the current item we recurse.
template <int WL, int ID0, int C0, int W0, int... IDs, int... Cs, int... Ws>
struct PackHelper<WL, true, ItemList<Item<ID0, C0, W0>, Item<IDs, Cs, Ws>...>> {
private:
  using head = Item<ID0,
                        (W0 < WL) ? 1 : std::ratio<WL, W0>::num,
                        (W0 < WL) ? 1 : std::ratio<WL, W0>::den>;
  using tail = typename PackHelper<WL - W0,
                                   ((WL - W0) > 0),
                                   ItemList<Item<IDs, Cs, Ws>...>>::type;

public:
  using type = typename Concat<ItemList<head>, tail>::type;
};

// specialization for a full knapsack with still items left ->
// We can't fit any more items into the knapsack
template <int WL, typename... Is>
struct PackHelper<WL, false, ItemList<Is...>> {
  using type = ItemList<>;
};

// specialization for an empty list and a knapsack which is not full ->
// We don't have to process any more items (easy problem instance)
template <int WL>
struct PackHelper<WL, true, ItemList<>> {
  using type = ItemList<>;
};


// ############################################################################
// knapsack
// ############################################################################
// Main "public" "function": Instance of the partial knapsack problem as
// template parameter: Max is the the size of the knapsack followed by a list
// of items
template <int Max, typename... Is>
struct Knapsack {
private:
  // sorts the list of items
  using sorted = typename SortHelper<std::ratio<0, 1>, ItemList<Is...>>::type;

public:
  // the resulting item list where (cost/weight) is the share of the item ID
  using Result = typename PackHelper<Max, (Max > 0), sorted>::type;
};


// ############################################################################
// OutHelper
// ############################################################################
// Just some helper structs to create an array of the compile time template list
// to print it on the screen... Similar to STL's implementation in his variadic
// sorter:
// https://onedrive.live.com/?cid=e66e02dc83efb165&id=E66E02DC83EFB165%21306
template <typename Is>
struct OutHelper;

template <int... IDs, int... Cs, int... Ws>
struct OutHelper<ItemList<Item<IDs,Cs, Ws>...>> {
  static const std::array<std::tuple<int, int, int>, sizeof...(IDs)> arr;
};

template <int... IDs, int... Cs, int... Ws>
const std::array<std::tuple<int, int, int>, sizeof...(IDs)>
  OutHelper<ItemList<Item<IDs, Cs, Ws>...>>::arr
  = {{std::make_tuple(IDs, Cs, Ws)...}};


int main() {
  using namespace std;

  // "call" the solver with a knapsack instance
  //                                      ID | C | W        C/W
  using res = OutHelper<Knapsack<200, Item<0, 20, 100>,  // 0,2
                                      Item<1, 15, 80>,   // 0,1875
                                      Item<2, 15, 40>,   // 0,375
                                      Item<3, 10, 20>    // 0,5
                                      >::Result>;

  // print result
  for (auto& e : res::arr) {
    cout << "ID " << get<0>(e) << ":\t" << static_cast<float>(get<1>(e)) / get<2>(e) << endl;
  }
  cout << endl;
}
	/**
	* --- Template Meta Program to solve the Partial Knapsack Problem ---
	*
	* This little piece of code solves the partial knapsack problem at compile
	* time. This is not useful in any way. I just wanted to discover the
	* possibilities of template meta programming.
	* Note that this code is absolutly awful. First of all: It's a "pure" template
	* meta program, which is ugly on it's own. Furthermore my code is ugly in
	* particular. The motivation to clean up super-ugly code to get a little bit
	* less ugly code is... not that high.
	*
	* \author Lukas Kalbertodt <lukas.kalbertodt@gmail.com>
	*/
	#include <array> // Just for output
	#include <cstdint>
	#include <iostream> // Just for output
	#include <ratio> // representation of rational numbers
	#include <tuple> // Just for output
	#include <type_traits> // useful type traits


	// ############################################################################
	// Basic Helper Stuff
	// ############################################################################

	// compile time struct to hold an ID, a Cost and a Weight
	template <int ID, int C, int W> struct Item {
	static constexpr int cost = C;
	static constexpr int weight = W;
	};

	// is used to store a list of items
	template <typename... Is> struct ItemList {};

	// helper struct to concatenate lists (empty base declaration)
	template <typename, typename> struct Concat;

	// specialization for two item lists
	template <typename... IAs, typename... IBs>
	struct Concat<ItemList<IAs...>, ItemList<IBs...>> {
	using type = ItemList<IAs..., IBs...>;
	};

	// ------------------- RemoveElement -------------------------------------------
	// helper struct to remove one element Needle of a list Os
	// (empty base declaration)
	template <typename Needle, typename... Os> struct RemoveElement;

	// specialization for empty list -> result is empty list
	template <typename Needle> struct RemoveElement<Needle> {
	using type = ItemList<>;
	};

	// specialization for a list in which the first element differs from the Needle
	// -> result is Concat<Head, RemoveElement<Needle, Tail>
	template <typename Needle, typename Head, typename... Tail>
	struct RemoveElement<Needle, Head, Tail...> {
	using type
	= typename Concat<ItemList<Head>,
	typename RemoveElement<Needle,
	Tail...>::type>::type;
	};

	// specialization for a list in which the first element equals the Needle
	// -> result is RemoveElement<Needle, Tail>
	template <typename Needle, typename... Tail>
	struct RemoveElement<Needle, Needle, Tail...> {
	using type = typename RemoveElement<Needle,
	Tail...>::type;
	};



	// ############################################################################
	// Sorting
	// ############################################################################

	// ------------------- MaxItemBelow -------------------------------------------
	// returns the item with the maximal Cost/Weight ratio that is less than the
	// std::ratio given as first parameter (Cut).
	// Note: I don't actually use the "Below"-Feature of this anymore. This whole
	// program should still run without that, but I'm to lazy to remove it ;)
	template <typename Cut, typename... Ts> struct MaxItemBelow;

	// specialization for just one item -> maximum is this item of course
	template <std::intmax_t Num, std::intmax_t Den, typename I>
	struct MaxItemBelow<std::ratio<Num, Den>, I> {
	using max = I;
	};

	// specialization for a list with at least two items ->
	// It removes one element (from those two) and "calls" itself in a recursive way
	// with a list which size is decreased by one. To decide which item is dropped
	// it evaluates this expression:
	// valid(i0) && (i0 > i1 \|\| !valid(i1)) , where
	// valid() checks if the value of the item is below the Cut.
	// In other words: With each recursive "call" it removes one elment from the
	// list that is not the maximum below the Cut, until just one item is left
	template <std::intmax_t Num, std::intmax_t Den,
	int ID0, int C0, int W0,
	int ID1, int C1, int W1,
	int... IDs, int... Cs, int... Ws>
	struct MaxItemBelow<std::ratio<Num, Den>,
	Item<ID0, C0, W0>,
	Item<ID1, C1, W1>,
	Item<IDs, Cs, Ws>...>
	: MaxItemBelow<std::ratio<Num, Den>,
	typename std::
	conditional<std::ratio_less<std::ratio<C0, W0>,
	std::ratio<Num, Den>>::value && (
	std::ratio_greater<std::ratio<C0, W0>,
	std::ratio<C1, W1>>::value
	\|\| !std::ratio_less<std::ratio<C1, W1>,
	std::ratio<Num,
	Den>>::value),
	Item<ID0, C0, W0>,
	Item<ID1, C1, W1>>::type,
	Item<IDs, Cs, Ws>...> {};



	// ------------------- SortHelper --------------------------------------------
	// sorts all items in the given list whose value is below Max
	template <typename Max, typename List> struct SortHelper;

	// specialization for one item in the list -> the list is already sorted
	template <typename Max, typename I>
	struct SortHelper<Max, ItemList<I>> {
	using type = ItemList<I>;
	};

	// specialization for a list containing more than one item ->
	// max is the maximal item below Max
	// newlist is the given list without 'max'
	// type is a list of items containing all items in the input list with 'max'
	// at the beginning
	template <typename Max, typename I0, typename... Is>
	struct SortHelper<Max, ItemList<I0, Is...>> {
	private:
	using max = typename MaxItemBelow<Max, I0, Is...>::max;
	using newlist = typename RemoveElement<max, I0, Is...>::type;

	public:
	using type
	= typename Concat<ItemList<max>,
	typename SortHelper<std::ratio<max::cost, max::weight>,
	newlist>::type>::type;
	};




	// ------------------- PackHelper --------------------------------------------
	// Gets a sorted list of items and creates a list of
	// {ItemID, num, den} where num/den is how much of the ItemID is used in the
	// result. WL = weight left
	template <int WL, bool OverZero, typename... Is>
	struct PackHelper;

	// specialization for a list with at least one element and a knapsack with
	// space left ->
	// We calculate how much of that item fits into the knapsack: If the item weight
	// is less than the available weight in the knapsack, we can fit everything of
	// the item (1). Else we fit as much as we can, which is
	// (left_available_weight/item_weight).
	// After calculating the share of the current item we recurse.
	template <int WL, int ID0, int C0, int W0, int... IDs, int... Cs, int... Ws>
	struct PackHelper<WL, true, ItemList<Item<ID0, C0, W0>, Item<IDs, Cs, Ws>...>> {
	private:
	using head = Item<ID0,
	(W0 < WL) ? 1 : std::ratio<WL, W0>::num,
	(W0 < WL) ? 1 : std::ratio<WL, W0>::den>;
	using tail = typename PackHelper<WL - W0,
	((WL - W0) > 0),
	ItemList<Item<IDs, Cs, Ws>...>>::type;

	public:
	using type = typename Concat<ItemList<head>, tail>::type;
	};

	// specialization for a full knapsack with still items left ->
	// We can't fit any more items into the knapsack
	template <int WL, typename... Is>
	struct PackHelper<WL, false, ItemList<Is...>> {
	using type = ItemList<>;
	};

	// specialization for an empty list and a knapsack which is not full ->
	// We don't have to process any more items (easy problem instance)
	template <int WL>
	struct PackHelper<WL, true, ItemList<>> {
	using type = ItemList<>;
	};


	// ############################################################################
	// knapsack
	// ############################################################################
	// Main "public" "function": Instance of the partial knapsack problem as
	// template parameter: Max is the the size of the knapsack followed by a list
	// of items
	template <int Max, typename... Is>
	struct Knapsack {
	private:
	// sorts the list of items
	using sorted = typename SortHelper<std::ratio<0, 1>, ItemList<Is...>>::type;

	public:
	// the resulting item list where (cost/weight) is the share of the item ID
	using Result = typename PackHelper<Max, (Max > 0), sorted>::type;
	};


	// ############################################################################
	// OutHelper
	// ############################################################################
	// Just some helper structs to create an array of the compile time template list
	// to print it on the screen... Similar to STL's implementation in his variadic
	// sorter:
	// https://onedrive.live.com/?cid=e66e02dc83efb165&id=E66E02DC83EFB165%21306
	template <typename Is>
	struct OutHelper;

	template <int... IDs, int... Cs, int... Ws>
	struct OutHelper<ItemList<Item<IDs,Cs, Ws>...>> {
	static const std::array<std::tuple<int, int, int>, sizeof...(IDs)> arr;
	};

	template <int... IDs, int... Cs, int... Ws>
	const std::array<std::tuple<int, int, int>, sizeof...(IDs)>
	OutHelper<ItemList<Item<IDs, Cs, Ws>...>>::arr
	= {{std::make_tuple(IDs, Cs, Ws)...}};




	int main() {
	using namespace std;

	// "call" the solver with a knapsack instance
	// ID \| C \| W C/W
	using res = OutHelper<Knapsack<200, Item<0, 20, 100>, // 0,2
	Item<1, 15, 80>, // 0,1875
	Item<2, 15, 40>, // 0,375
	Item<3, 10, 20> // 0,5
	>::Result>;

	// print result
	for (auto& e : res::arr) {
	cout << "ID " << get<0>(e) << ":\t" << static_cast<float>(get<1>(e)) / get<2>(e) << endl;
	}
	cout << endl;
	}