// std library
#include <stdexcept>
#include <exception>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>

// boost library
#include <boost/icl/interval_set.hpp>
namespace bicl = boost::icl;


class Interval
{
 public:
	typedef std::size_t  base_t;

	Interval(base_t const& aCorner=0, base_t const& aExtent=0) : Corner(aCorner), Extent(aExtent) { std::cout << "create interval(" << Corner << "," << Extent << ")\n"; }

	base_t const& lower () const { return Corner; }
	base_t        upper () const { return Corner+Extent-1; }

	bool operator==(Interval const& idem) const { return (Corner==idem.Corner && Extent==idem.Extent); }
	bool operator!=(Interval const& idem) const { return (Corner!=idem.Corner || Extent!=idem.Extent); }
	bool operator< (Interval const& idem) const { return (Corner!=idem.Corner ?  Corner< idem.Corner : Extent< idem.Extent); }
	friend std::ostream& operator<<(std::ostream& os, Interval const& idem) { return os << "[" << idem.Corner << "%" << idem.Extent << "]"; }

 private:
	base_t Corner;
	base_t Extent;
};


typedef bicl::interval_set<Interval::base_t, std::less, Interval>  IntervalSet;


namespace boost
{

namespace icl
{


template<> struct interval_traits<Interval>
{
	typedef Interval                interval_type;   //2.1 Interval will be the interval_type.
	typedef interval_type::base_t   domain_type;     //2.2 The elements of the interval are discrete.
	typedef std::less<domain_type>  domain_compare;  //2.3 This is the way our element shall be ordered.

	static interval_type construct(const domain_type& lo, const domain_type& up) { return interval_type(lo, (up >= lo ? up-lo+1 : 0)); } //3.1 Construction of intervals
	static domain_type   lower(const interval_type& inter_val) { return inter_val.lower(); }; //3.2 Interval of values
	static domain_type   upper(const interval_type& inter_val) { return inter_val.upper(); }; //3.2 Interval of values
};


template<> struct interval_bound_type<Interval>
{
	typedef interval_bound_type type;
	BOOST_STATIC_CONSTANT(bound_type, value = interval_bounds::static_closed); //4.1 Actual definition
};


} // icl
} // boost


class Selection
{
 public:
	typedef std::size_t  base_t;
	typedef double       real_t;

	Selection(base_t const& aCorner, base_t const& aExtent) { Intervals.insert(Interval(aCorner,aExtent)); }
	Selection(IntervalSet const& aIntervals=IntervalSet()) : Intervals(aIntervals) {}

	bool empty   () const { return Intervals.empty(); }

	bool operator==(Selection const& idem) const { return (Intervals==idem.Intervals); }
	bool operator!=(Selection const& idem) const { return !operator==(idem); }

	Selection& operator+=(Selection const& idem) { Intervals+=idem.Intervals; return *this; }
	Selection  operator+ (Selection const& idem) const { return Selection(*this)+=idem; }
	Selection& operator&=(Selection const& idem) { Intervals&=idem.Intervals; return *this; }
	Selection  operator& (Selection const& idem) const { return Selection(*this)&=idem; }
	Selection& operator-=(Selection const& idem) { Intervals-=idem.Intervals; return *this; }
	Selection  operator- (Selection const& idem) const { return Selection(*this)-=idem; }

	friend std::ostream& operator<<(std::ostream& os, Selection const& idem)
	{
		for (IntervalSet::const_iterator it=idem.Intervals.begin(); it != idem.Intervals.end(); ++it) { os << *it; }
		if  (idem.empty()) { os << "[empty]"; }
		return os;
	}

 private:
	IntervalSet Intervals;
};



//! Test basic shape behaviour.
int main(int argc, char** argv)
{
	typedef Selection  sel_t;

	sel_t ShapoidA  ( 2, 9);
	sel_t ShapoidB  (11,10);
	sel_t ShapoidC  (21,10);
	sel_t ShapoidAB ( 2,19);
	sel_t ShapoidBC (11,20);
	sel_t ShapoidABC( 2,29);

	IntervalSet AC;
	AC.insert(Interval( 2, 9));
	AC.insert(Interval(21,10));
	sel_t ShapoidAC (AC);

	std::cout << "CHECK INTERVALS" << std::endl << std::boolalpha;
	std::cout << (ShapoidA+ShapoidB == ShapoidAB) << " -> <A+B>: " << ShapoidA+ShapoidB << " == " << "<AB>: " << ShapoidAB << std::endl;
	std::cout << (ShapoidA+ShapoidC == ShapoidAC) << " -> <A+C>: " << ShapoidA+ShapoidC << " == " << "<AC>: " << ShapoidAC << std::endl;
	std::cout << (ShapoidB+ShapoidC == ShapoidBC) << " -> <B+C>: " << ShapoidB+ShapoidC << " == " << "<BC>: " << ShapoidBC << std::endl;
	std::cout << (ShapoidA+ShapoidB+ShapoidC == ShapoidABC) << " -> <A+B+C>: " << ShapoidA+ShapoidB+ShapoidC << " == " << "<ABC>: " << ShapoidABC << std::endl;
	std::cout << "DIFFERENCE BUG:\n";
	std::cout << (ShapoidABC-ShapoidA == ShapoidBC) << " -> <ABC-A>: " << ShapoidABC-ShapoidA << " == <BC>: " << ShapoidBC << std::endl;
}