main.cpp

#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>

#include <arpa/inet.h>
#include <endian.h>

unsigned to_num(const std::string& ip) {
	return be32toh(inet_addr(ip.c_str()));
}

constexpr int tree_depth = 15;

struct Range {
	unsigned from, to;
	unsigned range;
	std::string name;
};

struct Node {
	Node(int depth, unsigned min, unsigned max)
		: mid(((long long)max + (long long)min) / 2)
		, children(nullptr)
	{
		if (depth < tree_depth) {
			children = new Node[2] {
				Node(depth + 1, min, mid),
				Node(depth + 1, mid, max)
			};
		}
	}
	~Node() {
		delete[] children;
	}

	void load(const Range & range) {
		if (!children) {
			ranges.push_back(range);
		} else {
			if (range.to < mid)
				children[0].load(range);
			else if (range.from > mid)
				children[1].load(range);
			else
				ranges.push_back(range);
		}
	}

	void sort() {
		std::sort(ranges.begin(), ranges.end(),
			[](const Range &l1, const Range &l2){
				return l1.range < l2.range;
			}
		);
		if (children) {
			children[0].sort();
			children[1].sort();
		}
	}

	const Range* search(unsigned num) const {
		if (children) {
			int index = num < mid ? 0 : 1;
			const Range *best = children[index].search(num);
			for (const Range &range : ranges) {
				if (best && range.range > best->range)
					return best;
				if (range.from <= num && num <= range.to)
					return &range;
			}
			return best;
		} else {
			for (const Range &range : ranges)
				if (range.from <= num && num <= range.to)
					return &range;
			return nullptr;
		}
	}

	unsigned mid;
	Node *children;
	std::vector<Range> ranges;
};
#include <chrono>
using namespace std::chrono;
int main() {
	auto t0 = high_resolution_clock::now();
	std::cout.sync_with_stdio(false);
	Node node(0, 0, 4294967295u); // 255.255.255.255

	std::ifstream input("range_1M.txt");
	std::string from_s, to_s, name;
	while (input >> from_s >> to_s) {
		input.ignore();
		std::getline(input, name);
		unsigned from = to_num(from_s), to = to_num(to_s);
		node.load(Range{from, to, to-from, name});
	}

	node.sort();

	auto t1 = high_resolution_clock::now();

	std::ifstream queries("query_10k.txt");
	std::string query_s;
	while (queries >> query_s) {
		unsigned query = to_num(query_s);
		const Range *best = node.search(query);
		std::cout
			<< query_s << " "
			<< (best ? best->name : "<unknown>")
			<< "\n";
	}
	auto t2 = high_resolution_clock::now();
	auto dt = duration_cast<microseconds>(t1-t0);
	std::cerr << dt.count() << "\n";
	dt = duration_cast<microseconds>(t2-t1);
	std::cerr << dt.count() << "\n";
}