/*=======================================================================================
	Sparse Bit Vectors Demo
	Copyright (c) 2001, Joel de Guzman
=======================================================================================*/
#include <vector>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>


struct Range {

	Range()
	: from(0), to(-1) {}

	Range(int from_)
	: from(from_), to(from_) {}

	Range(int from_, int to_)
	: from(from_), to(to_) {}

	bool
	IsValid() const
	{ return from <= to; }

	bool
	Includes(int val) const
	{ return from <= val && to >= val; }

	bool
	Includes(Range const& range) const
	{ return from <= range.from && to >= range.to; }

	bool
	IsAdjacent(int val) const
	{ return (from-1) <= val && (to+1) >= val; }

	bool
	IsAdjacent(Range const& range) const
	{ return IsAdjacent(range.from) || IsAdjacent(range.to); }

	void
	Merge(Range const& range)
	{
		assert(IsAdjacent(range));
		from = std::min(from, range.from);
		to = std::max(to, range.to);
	}

	friend bool
	operator < (Range const& a, Range const& b)
	{ return a.from < b.from; }

	friend bool
	operator == (Range const& a, Range const& b)
	{ return (a.from == b.from) && (a.to == b.to); }

	int	from;
	int	to;
};


struct Region1D {

	Range	Bounds() const;
	bool	Test(Range const& range) const;
	void	Set(Range const& range);
	void	Clear(Range const& range);

	void	Invert();
	void	Union(Region1D const& region);
	void	Intersection(Region1D const& region);
	void	Difference(Region1D const& region);
	void	Xor(Region1D const& region);


	typedef std::vector<Range>::iterator iterator;
	typedef std::vector<Range>::const_iterator const_iterator;

	void	Merge(iterator iter, Range const& range);

	std::vector<Range>	v;
};


Range
Region1D::Bounds() const
{
	if (v.size() == 0)
		return Range();
	return Range(v.begin()->from, (v.end()-1)->to);
}

bool
Region1D::Test(Range const& range) const
{
	if (const_iterator iter = std::lower_bound(v.begin(), v.end(), range))
	{
		if (iter != v.end() && iter->Includes(range))
			return true;
		if (iter != v.begin())
			return (--iter)->Includes(range);
	}
	return false;
}


void
Region1D::Merge(iterator iter, Range const& range)
{
	iter->Merge(range);
	iterator i = iter + 1;

	while (i != v.end() && iter->IsAdjacent(*i))
		iter->Merge(*i++);

	v.erase(iter+1, i);
}


void
Region1D::Set(Range const& range)
{
	if (iterator iter = std::lower_bound(v.begin(), v.end(), range))
	{
		if (iter != v.end() && iter->Includes(range) ||
			((iter != v.begin()) && (iter - 1)->Includes(range)))
			return;

		if (iter != v.begin() && (iter - 1)->IsAdjacent(range))
			Merge(--iter, range);

		else if (iter != v.end() && iter->IsAdjacent(range))
			Merge(iter, range);

		else
			v.insert(iter, range);
	}
	else
	{
		v.push_back(range);
	}
}


void
Region1D::Clear(Range const& range)
{
	if (iterator iter = std::lower_bound(v.begin(), v.end(), range))
	{
		iterator left_iter;

		if ((iter != v.begin()) && (left_iter = (iter - 1))->Includes(range.from))
			if (left_iter->to > range.to)
			{
				int save_to = left_iter->to;
				left_iter->to = range.from-1;
				v.insert(iter, Range(range.to+1, save_to));
				return;
			}
			else
			{
				left_iter->to = range.from-1;
			}

		iterator i = iter;
		while (i != v.end() && range.Includes(*i))
			i++;
		if (i != v.end() && i->Includes(range.to))
			i->from = range.to+1;
		v.erase(iter, i);
	}
}


void
Region1D::Invert()
{
	Region1D	inv;
	inv.Set(Range(INT_MIN, INT_MAX));
	inv.Difference(*this);
	v.swap(inv.v);
}


void
Region1D::Union(Region1D const& region)
{
	for (const_iterator iter = region.v.begin(); iter != region.v.end(); ++iter)
		Set(*iter);
}


void
Region1D::Intersection(Region1D const& region)
{
	Region1D	inv;
	inv.Set(Range(INT_MIN, INT_MAX));
	inv.Difference(region);
	Difference(inv);
}


void
Region1D::Difference(Region1D const& region)
{
	for (const_iterator iter = region.v.begin(); iter != region.v.end(); ++iter)
		Clear(*iter);
}


void
Region1D::Xor(Region1D const& region)
{
	Region1D	bma = region;
	bma.Difference(*this);
	Difference(region);
	Union(bma);
}


static void
DrawRuler(char const* str)
{
	std::cout << std::endl << std::endl;
	std::cout << "\t_____________________________________________________________\n";
	std::cout << "\t" << str << std::endl;
	std::cout << "\t_____________________________________________________________\n";
	std::cout << "\t0         1          2        3         4         5         6\n";
	std::cout << "\t0123456789012345678901234567890123456789012345678901234567890\n\n";
}


static void
Draw(Region1D const& a, char const* str)
{
	std::cout << str << "\t";

	for (int i = 0; i <= 60; i++)
		if (a.Test(i))
			std::cout << "*";
		else
			std::cout << " ";
	std::cout << std::endl;
}

int
main()
{
	Region1D	a, b, c;

	a.Set(Range(5, 25));
	a.Set(Range(35, 55));
	b.Set(Range(15, 45));
	c = a;

	DrawRuler("INITIAL");
	Draw(a, "a:");
	Draw(b, "b:");

	DrawRuler("INVERSE a = ~a");
	a.Invert();
	Draw(a, "~a:");
	a.Invert();
	Draw(a, "~a:");

	DrawRuler("UNION a |= b");
	Draw(a, "a:");
	Draw(b, "b:");
	a.Union(b);
	Draw(a, "r:");
	a = c;

	DrawRuler("DIFFERENCE a -= b");
	Draw(a, "a:");
	Draw(b, "b:");
	a.Difference(b);
	Draw(a, "r:");
	a = c;

	DrawRuler("INTERSECTION a &= b");
	Draw(a, "a:");
	Draw(b, "b:");
	a.Intersection(b);
	Draw(a, "r:");
	a = c;

	DrawRuler("XOR a ^= b");
	Draw(a, "a:");
	Draw(b, "b:");
	a.Xor(b);
	Draw(a, "r:");
	a = c;
}