van Emde Boas Tree

vanemdeboas.hpp

#include <memory>
#include <vector>
#include <cmath>
#include <iostream>

#define NIL			(-1)
#define LOG2(x)		ceil(log2(x))
#define SQRT_C(x)	(1<<static_cast<int>(ceil(LOG2(x)/2)))
#define SQRT_F(x)	(1<<static_cast<int>(floor(LOG2(x)/2)))
#define HIGH(x)		(x/SQRT_F(_u))
#define LOW(x)		(x%SQRT_F(_u))
#define INDEX(x,y)	(x*SQRT_F(_u)+y)

#define INSERT_EMPTY(ptr, x)	do { ptr->_max = ptr->_min = x; } while (0)

class VanEmdeBoas
{
	template <typename T> using vector = std::vector<T>;
	template <typename T> using shared_ptr = std::shared_ptr<T>;

	shared_ptr<VanEmdeBoas> _summary;
	vector<shared_ptr<VanEmdeBoas>> _cluster;
	int _min = NIL, _max = NIL;
	int _u;
public:
	VanEmdeBoas(int u): _u(u)
	{
		if (u > 2) {
			_summary = std::make_shared<VanEmdeBoas>(SQRT_C(u));
			_cluster = vector<shared_ptr<VanEmdeBoas>>(SQRT_C(u));
			for (shared_ptr<VanEmdeBoas> &ptr : _cluster)
				ptr = std::make_shared<VanEmdeBoas>(SQRT_F(u));
		}
	}

	int min()
	{
		return _min;
	}

	int max()
	{
		return _max;
	}

	bool member(int x)
	{
		if (x == _min || x == _max)						// x is the maximum or minimum
			return true;
		else if (_u == 2)								// VEB(2)
			return false;
		return _cluster[HIGH(x)]->member(LOW(x));
	}

	int successor(int x)
	{
		if (_u == 2) {									// VEB(2)
			if (x == 0 && _max == 1)
				return 1;
			else
				return NIL;
		} else if (_min != NIL && x < _min) {			// x is less than minimum
			return _min;
		} else {
			int max_low = _cluster[HIGH(x)]->max();
			if (max_low != NIL && LOW(x) < max_low) {	// cluster[HIGGH(x)] has values greater than x
				int offset = _cluster[HIGH(x)]->successor(LOW(x));
				return INDEX(HIGH(x), offset);
			} else {									// cluster[HIGGH(x)] doesn't have values greater than x
				int succ_cluster = _summary->successor(HIGH(x));
				if (succ_cluster == NIL) {
					return NIL;
				} else {
					int offset = _cluster[succ_cluster]->min();
					return INDEX(succ_cluster, offset);
				}
			}
		}
	}

	int predecessor(int x)
	{
		if (_u == 2) {									// VEB(2)
			if (x == 1 && _min == 0)
				return 0;
			else
				return NIL;
		} else if (_max != NIL && _max < x) {			// x is greater than maximum
			return _max;
		} else {
			int min_low = _cluster[HIGH(x)]->min();
			if (min_low != NIL && min_low < LOW(x)) {	// cluster[HIGGH(x)] has values less than x
				int offset = _cluster[HIGH(x)]->predecessor(LOW(x));
				return INDEX(HIGH(x), offset);
			} else {									// cluster[HIGGH(x)] doesn't have values less than x
				int pred_cluster = _summary->predecessor(HIGH(x));
				if (pred_cluster == NIL) {
					if (_min != NIL && x > _min)		// minimum is less than x
						return _min;
					return NIL;
				} else {
					int offset = _cluster[pred_cluster]->max();
					return INDEX(pred_cluster, offset);
				}
			}
		}
	}

	void insert(int x)
	{
		if (_min == NIL) {								// vEB has no member
			INSERT_EMPTY(this, x);
		} else {
			if (x < _min)								// x is less than minimum
				std::swap(x, _min);
			if (_u > 2)
				if (_cluster[HIGH(x)]->min() == NIL) {
					_summary->insert(HIGH(x));
					INSERT_EMPTY(_cluster[HIGH(x)], LOW(x));
				} else {
					_cluster[HIGH(x)]->insert(LOW(x));
				}
			if (x > _max)								// update maximum
				_max = x;
		}
	}

	void remove(int x)
	{
		if (_min == _max && _max == x) {			// vEB has noly one member
			_min = _max = NIL;
		} else if (_u == 2) {						// vEB(2)
			_max = _min = x == 0;
		} else {									// x is the minimum
			if (x == _min) {
				int first_cluster = _summary->min();
				x = INDEX(first_cluster, _cluster[first_cluster]->min());
				_min = x;
			}
			_cluster[HIGH(x)]->remove(LOW(x));
			if (_cluster[HIGH(x)]->min() == NIL) {	// cluster[HIGH(x)] be empty
				_summary->remove(HIGH(x));
				if (x == _max) {
					int summary_max = _summary->max();
					if (summary_max == NIL)
						_max = _min;
					else 
						_max = INDEX(summary_max, _cluster[summary_max]->max());
				}
			} else if (x == _max) {					
				_max = INDEX(HIGH(x), _cluster[HIGH(x)]->max());
			}
		}
	}

	void print(int level = 0)
	{
		for (int i = 0; i < level; i++)
			std::cout << '\t';
		std::cout << "vEB(" << _u << ')' << std::endl;
		for (int i = 0; i < level; i++)
			std::cout << '\t';
		std::cout << "min: " << _min << ", max: " << _max << std::endl;
		if (_u > 2) {
			for (int i = 0; i < level; i++)
				std::cout << '\t';
			std::cout << "summary: " << std::endl; 
			_summary->print(level+1);
			for (int i = 0; i < level; i++)
				std::cout << '\t';
			std::cout << "clusters: " << std::endl; 
			for (const shared_ptr<VanEmdeBoas> &ptr : _cluster)
				ptr->print(level+1);
		}
	}
};