libscatter/include/scatter/scatter.h

#pragma once
#include <stdint.h>
#include "9float.hpp"
using scatter_key_t = ninefloat::Q<__int128,64>;
static const scatter_key_t scatter_key_increment = ninefloat::Q<__int128,64>::min_increment();
#include <vector>
#include <numeric>
#include <type_traits>
#include <iostream>

namespace StorageTree {

	namespace _impl {

		template<class childs>
		struct subdivision {
			uint64_t weight;
			std::vector<childs> content;
			scatter_key_t begin;
			scatter_key_t end;
			static constexpr bool divisible = true;
		};

		struct daemon_impl {
			uint64_t weight;
			scatter_key_t begin;
			scatter_key_t end;
			static constexpr bool divisible = false;
		};

		template<class T>
		constexpr T max(T any = 0)
		{
			if(any>any+scatter_key_increment) {
				return any;
			}

			return max(any+scatter_key_increment);
		}
	}


	using daemon        = _impl::daemon_impl;
	using server        = _impl::subdivision<daemon>;
	using subrack       = _impl::subdivision<server>;
	using rack          = _impl::subdivision<subrack>;
	using room          = _impl::subdivision<rack>;
	using datacenter    = _impl::subdivision<room>;
	using root          = _impl::subdivision<datacenter>;

	template<class T>
	uint64_t total_weight(T& root)
	{
		uint64_t ret=0;

		for(auto& val : root.content) {
			ret+=total_weight(val);
		}

		return ret;
	}

	template<>
	uint64_t total_weight<daemon>(daemon& root)
	{
		return root.weight;
	}

	template<class T>
	scatter_key_t update_weights(T& root, uint64_t total, double sub_ratio=1, scatter_key_t begin=0, double ratio=0.5)
	{
        auto b = begin;
		for(auto& elem : root.content) {
            std::cout<<"UP"<<std::endl;
			b = update_weights(
			            elem,
			            total,
			            sub_ratio*root.content.size(),
			            b,
			            ratio
			        )+scatter_key_increment;
		}

		return begin;
	}

	template<>
	scatter_key_t update_weights<daemon>(daemon& root, uint64_t total, double sub_ratio, scatter_key_t begin, double ratio)
	{
		root.begin = begin;
		root.end = begin+scatter_key_t(0.5)*((scatter_key_t(1/sub_ratio)*scatter_key_t(ratio)+scatter_key_t((double)root.weight/(double)total)*scatter_key_t(1-ratio)));
        std::cout<<"Starts: "<<(uint64_t)root.begin.data()<<" Ends: "<<(uint64_t)root.end.data()<<std::endl;
		return root.end;
	}

    template<class T, typename... Args>
    void add_rule(T& root, uint64_t weight, size_t idx, std::tuple<Args...> Var)
    {
        if(idx<root.content.size())
            add_rule(root.content.at(idx),weight,Var...);
        else if(idx==root.content.size())
        {
            root.content.emplace_back();
            add_rule(root.content.at(idx),weight,Var...);  
        }
        else
            throw std::runtime_error("libscatter: Bad rule, are you sure the order is right?");
    }

    template<>
    void add_rule<daemon,size_t>(daemon& root, uint64_t weight,std::tuple<>)
    {
        root.weight=weight;
    }
}