#ifndef CPU_KNAPSACK_SERIAL_HPP
#define CPU_KNAPSACK_SERIAL_HPP

#include "data.hpp"

#include <vector>
#include <cstdint>

class SerialImplementation
{
private:
	std::uint64_t mMinSize;
	std::uint64_t mMaxSize;
	result_t mBestResult;
	std::uint64_t mBestPriority;

	// this function is not actualy used in serial implementation, but it may be handy...
	std::pair<std::uint64_t, std::uint64_t> getSizeAndPriority(const items_t& items, selection_t selection)
	{
		std::uint64_t size = 0;
		std::uint64_t priority = 0;
		for (std::size_t i = 0; i < items.size(); ++i) {
			if ((selection >> i) & 1) {
				size += items[i].size;
				priority += items[i].priority;
			}
		}
		return { size, priority };
	}

	void backtrack(const items_t& items, std::size_t index, selection_t selection, std::uint64_t size, std::uint64_t priority)
	{
		selection_t newSelection = selection | (1ULL << index);
		uint64_t newSize = size + items[index].size;
		uint64_t newPriority = priority + items[index].priority;

		if (newSize >= mMinSize && newSize <= mMaxSize && newPriority >= mBestPriority) {
			// we are in the range [min,max] size and at least matching the priority
			if (newPriority > mBestPriority) {
				// a better solution is found, so we can clear the previous results
				mBestResult.clear();
				mBestPriority = newPriority;
			}
			// either a better solution is found or a solution with the same priority, so we can add it to the results
			mBestResult.push_back(newSelection);
		}

		if (index + 1 < items.size()) {
			if (newSize < mMaxSize) {
				// we can still add more items, so we can continue with the new selection
				backtrack(items, index + 1, newSelection, newSize, newPriority);
			}
			backtrack(items, index + 1, selection, size, priority);
		}
	}

public:
	SerialImplementation(std::size_t items, std::uint64_t minSize, std::uint64_t maxSize)
		: mMinSize(minSize), mMaxSize(maxSize), mBestPriority(0)
	{
		// any allocation of supporting data structures can be done here (size is the number of log records)
	}

	std::uint64_t operator()(const items_t &items, result_t &result)
	{
		backtrack(items, 0, 0, 0, 0);
		result.swap(mBestResult);
		return mBestPriority;
	}
};


#endif